alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::cmp::Reverse;
2use std::collections::{BTreeMap, BTreeSet, BinaryHeap};
3
4use knot_types::{ChangeId, CobId, UnixSeconds};
5
6use crate::change::Change;
7
8#[derive(Debug)]
9pub struct ChangeGraph {
10 root: CobId,
11 changes: BTreeMap<ChangeId, Change>,
12}
13
14impl ChangeGraph {
15 pub(crate) fn new(root: CobId, changes: BTreeMap<ChangeId, Change>) -> Self {
16 Self { root, changes }
17 }
18
19 pub fn root(&self) -> CobId {
20 self.root
21 }
22
23 pub fn len(&self) -> usize {
24 self.changes.len()
25 }
26
27 pub fn is_empty(&self) -> bool {
28 self.changes.is_empty()
29 }
30
31 pub fn causal_order(&self) -> Vec<ChangeId> {
32 order(&self.changes)
33 }
34
35 pub(crate) fn into_ordered(self) -> Vec<Change> {
36 let ordered = order(&self.changes);
37 let mut changes = self.changes;
38 ordered
39 .into_iter()
40 .map(|id| changes.remove(&id).expect("ordered id is in graph"))
41 .collect()
42 }
43}
44
45fn order(changes: &BTreeMap<ChangeId, Change>) -> Vec<ChangeId> {
46 let mut indegree: BTreeMap<ChangeId, usize> = changes
47 .values()
48 .map(|change| {
49 let present = change
50 .parents
51 .iter()
52 .filter(|parent| changes.contains_key(*parent))
53 .count();
54 (change.id, present)
55 })
56 .collect();
57 let children: BTreeMap<ChangeId, Vec<ChangeId>> =
58 changes.values().fold(BTreeMap::new(), |mut acc, change| {
59 change
60 .parents
61 .iter()
62 .filter(|parent| changes.contains_key(*parent))
63 .for_each(|parent| acc.entry(*parent).or_default().push(change.id));
64 acc
65 });
66 let mut ready: BinaryHeap<Reverse<(UnixSeconds, ChangeId)>> = changes
67 .values()
68 .filter(|change| indegree[&change.id] == 0)
69 .map(|change| Reverse(change.sort_key()))
70 .collect();
71 std::iter::from_fn(move || {
72 let Reverse((_, id)) = ready.pop()?;
73 children.get(&id).into_iter().flatten().for_each(|child| {
74 let degree = indegree
75 .get_mut(child)
76 .expect("every child has an indegree entry");
77 *degree -= 1;
78 if *degree == 0 {
79 ready.push(Reverse(changes[child].sort_key()));
80 }
81 });
82 Some(id)
83 })
84 .collect()
85}
86
87#[derive(Debug)]
88pub struct History {
89 root: ChangeId,
90 changes: Vec<Change>,
91}
92
93impl History {
94 pub(crate) fn new(root: ChangeId, changes: Vec<Change>) -> Self {
95 Self { root, changes }
96 }
97
98 pub fn root(&self) -> ChangeId {
99 self.root
100 }
101
102 pub fn changes(&self) -> &[Change] {
103 &self.changes
104 }
105
106 pub fn len(&self) -> usize {
107 self.changes.len()
108 }
109
110 pub fn is_empty(&self) -> bool {
111 self.changes.is_empty()
112 }
113
114 pub fn traverse<A, F: FnMut(A, &Change) -> A>(&self, init: A, f: F) -> A {
115 self.changes.iter().fold(init, f)
116 }
117
118 pub fn tips(&self) -> Vec<ChangeId> {
119 let referenced: BTreeSet<ChangeId> = self
120 .changes
121 .iter()
122 .flat_map(|change| change.parents.iter().copied())
123 .collect();
124 self.changes
125 .iter()
126 .map(|change| change.id)
127 .filter(|id| !referenced.contains(id))
128 .collect()
129 }
130}