braid-core 0.1.4

use super::super::antimatter::AntimatterCrdt;
use super::super::crdt_trait::PrunableCrdt;
use crate::core::error::Result;
use std::collections::{HashMap, HashSet};

pub fn ancestors<T: PrunableCrdt + Clone>(
    crdt: &AntimatterCrdt<T>,
    versions: &HashMap<String, bool>,
    ignore_nonexistent: bool,
) -> Result<HashMap<String, bool>> {
    let mut result = HashMap::new();
    let mut stack: Vec<String> = versions.keys().cloned().collect();
    let mut visited = HashSet::new();

    while let Some(v) = stack.pop() {
        if visited.contains(&v) {
            continue;
        }
        visited.insert(v.clone());
        result.insert(v.clone(), true);

        if let Some(parents) = crdt.t.get(&v) {
            for p in parents {
                stack.push(p.clone());
            }
        } else if !ignore_nonexistent && !v.is_empty() {
            // In a real implementation we might error here if version is missing
        }
    }

    Ok(result)
}

pub fn descendants<T: PrunableCrdt + Clone>(
    crdt: &AntimatterCrdt<T>,
    versions: &HashMap<String, bool>,
    ignore_nonexistent: bool,
) -> Result<HashMap<String, bool>> {
    let mut result = HashMap::new();
    let child_map = get_child_map(crdt);

    let mut stack: Vec<String> = versions.keys().cloned().collect();
    let mut visited = HashSet::new();

    while let Some(v) = stack.pop() {
        if visited.contains(&v) {
            continue;
        }
        visited.insert(v.clone());
        result.insert(v.clone(), true);

        if let Some(children) = child_map.get(&v) {
            for c in children {
                stack.push(c.clone());
            }
        } else if !ignore_nonexistent && !v.is_empty() && !crdt.t.contains_key(&v) {
            // Version not found
        }
    }

    Ok(result)
}

pub fn get_child_map<T: PrunableCrdt + Clone>(
    crdt: &AntimatterCrdt<T>,
) -> HashMap<String, HashSet<String>> {
    let mut child_map: HashMap<String, HashSet<String>> = HashMap::new();
    for (version, parents) in &crdt.t {
        for p in parents {
            child_map
                .entry(p.clone())
                .or_insert_with(HashSet::new)
                .insert(version.clone());
        }
    }
    child_map
}