columnar/adts/
tree.rs

Help
1#[derive(Clone)]
2pub struct Tree<T> {
3    pub data: T,
4    pub kids: Vec<Tree<T>>,
5}
6
7impl Tree<usize> {
8    pub fn sum(&self) -> usize {
9        self.data + self.kids.iter().map(|x| x.sum()).sum::<usize>()
10    }
11}
12
13/// A stand-in for `Vec<Tree<T>>`
14#[derive(Clone)]
15pub struct Trees<T> {
16    pub groups: Vec<usize>,     // inserted tree delimiters.
17    pub bounds: Vec<usize>,     // node child delimiters.
18    pub values: Vec<T>,         // node values.
19}
20
21/// A stand-in for `&Tree<T>`
22pub struct TreesRef<'a, T> {
23    value: &'a T,
24    lower: usize,
25    upper: usize,
26    nodes: &'a Trees<T>
27}
28
29impl<'a, T> Clone for TreesRef<'a, T> {
30    fn clone(&self) -> Self { *self }
31}
32impl<'a, T> Copy for TreesRef<'a, T> { }
33
34impl<'a, T> TreesRef<'a, T> {
35    pub fn value(&self) -> &T { self.value }
36    pub fn child(&self, index: usize) -> TreesRef<'a, T> {
37        assert!(index < self.upper - self.lower);
38        let child = self.lower + index;
39        TreesRef {
40            value: &self.nodes.values[child],
41            lower: self.nodes.bounds[child],
42            upper: self.nodes.bounds[child+1],
43            nodes: self.nodes,
44        }
45    }
46    pub fn kids(&self) -> usize {
47        self.upper - self.lower
48    }
49}
50
51impl<'a, T: PartialEq> PartialEq<Tree<T>> for TreesRef<'a, T> {
52    fn eq(&self, other: &Tree<T>) -> bool {
53        let mut todo = vec![(*self, other)];
54        while let Some((this, that)) = todo.pop() {
55            if this.value != &that.data {
56                return false;
57            } else if (this.upper - this.lower) != that.kids.len() {
58                return false;
59            } else {
60                for (index, child) in that.kids.iter().enumerate() {
61                    todo.push((this.child(index), child));
62                }
63            }
64        }
65        true
66    }
67}
68
69impl<T> Trees<T> {
70    // Pushes a tree containing data onto `self`.
71    pub fn push(&mut self, tree: Tree<T>) {
72
73        // Our plan is to repeatedly transcribe tree nodes, enqueueing
74        // any child nodes for transcription. When we do, we'll need to
75        // know where they will be written, to leave a forward reference,
76        // and to this end we'll "allocate" space as we go, with a counter.
77        let mut todo = std::collections::VecDeque::default();
78        todo.push_back(tree);
79        while let Some(node) = todo.pop_front() {
80            // children will land at positions in `self.values` determined
81            // by its current length, plus `todo.len()`, plus one (for node).
82            let cursor = self.values.len() + todo.len() + 1;
83            self.values.push(node.data);
84            self.bounds.push(cursor + node.kids.len());
85            for child in node.kids.into_iter() {
86                todo.push_back(child);
87            }
88        }
89
90        self.groups.push(self.values.len());
91    }
92
93    pub fn index(&self, index: usize) -> TreesRef<'_, T> {
94        let root = self.groups[index];
95        TreesRef {
96            value: &self.values[root],
97            lower: self.bounds[root]+1, // +1 because the root .. references itself at the moment.
98            upper: self.bounds[root+1],
99            nodes: self,
100        }
101    }
102
103    pub fn new() -> Self {
104        Self {
105            groups: vec![0],
106            bounds: vec![0],
107            values: Vec::default(),
108        }
109    }
110}
111
112/// LOUDS (level ordered unary degree sequence) is a succinct tree representation.
113mod louds {
114
115    // The tree is encoded by traversing it in a BFS order, with each node producing
116    // as many `1`s as it has children, followed by a `0`. There is also a `1` at the
117    // beginning of the sequence, for the root.
118    //
119    // The logic to determine the child of a node is as follows:
120    //
121    //      child(x, i) = select0(rank1(x) + i − 1) + 1
122    //
123    // It is possible that `i` here starts at 1, which we should fix to be `0`.
124
125
126}
columnar/adts/tree.rs

columnar/adts/
tree.rs
