braid_core/antimatter/algorithm/
bubble.rs

1use super::super::antimatter::AntimatterCrdt;
2use super::super::crdt_trait::PrunableCrdt;
3use crate::core::error::Result;
4use std::collections::{HashMap, HashSet};
5
6pub fn ancestors<T: PrunableCrdt + Clone>(
7    crdt: &AntimatterCrdt<T>,
8    versions: &HashMap<String, bool>,
9    ignore_nonexistent: bool,
10) -> Result<HashMap<String, bool>> {
11    let mut result = HashMap::new();
12    let mut stack: Vec<String> = versions.keys().cloned().collect();
13    let mut visited = HashSet::new();
14
15    while let Some(v) = stack.pop() {
16        if visited.contains(&v) {
17            continue;
18        }
19        visited.insert(v.clone());
20        result.insert(v.clone(), true);
21
22        if let Some(parents) = crdt.t.get(&v) {
23            for p in parents {
24                stack.push(p.clone());
25            }
26        } else if !ignore_nonexistent && !v.is_empty() {
27            // In a real implementation we might error here if version is missing
28        }
29    }
30
31    Ok(result)
32}
33
34pub fn descendants<T: PrunableCrdt + Clone>(
35    crdt: &AntimatterCrdt<T>,
36    versions: &HashMap<String, bool>,
37    ignore_nonexistent: bool,
38) -> Result<HashMap<String, bool>> {
39    let mut result = HashMap::new();
40    let child_map = get_child_map(crdt);
41
42    let mut stack: Vec<String> = versions.keys().cloned().collect();
43    let mut visited = HashSet::new();
44
45    while let Some(v) = stack.pop() {
46        if visited.contains(&v) {
47            continue;
48        }
49        visited.insert(v.clone());
50        result.insert(v.clone(), true);
51
52        if let Some(children) = child_map.get(&v) {
53            for c in children {
54                stack.push(c.clone());
55            }
56        } else if !ignore_nonexistent && !v.is_empty() && !crdt.t.contains_key(&v) {
57            // Version not found
58        }
59    }
60
61    Ok(result)
62}
63
64pub fn get_child_map<T: PrunableCrdt + Clone>(
65    crdt: &AntimatterCrdt<T>,
66) -> HashMap<String, HashSet<String>> {
67    let mut child_map: HashMap<String, HashSet<String>> = HashMap::new();
68    for (version, parents) in &crdt.t {
69        for p in parents {
70            child_map
71                .entry(p.clone())
72                .or_insert_with(HashSet::new)
73                .insert(version.clone());
74        }
75    }
76    child_map
77}
braid_core/antimatter/algorithm/bubble.rs

braid_core/antimatter/algorithm/
bubble.rs
