pulldown_cmark_fork/
tree.rs

1// Copyright 2018 Google LLC
2//
3// Use of this source code is governed by an MIT-style
4// license that can be found in the LICENSE file or at
5// https://opensource.org/licenses/MIT.
6
7//! A Vec-based container for a tree structure.
8
9use std::num::NonZeroUsize;
10use std::ops::{Add, Sub};
11
12#[derive(Debug, Eq, PartialEq, Copy, Clone)]
13pub enum TreePointer {
14    Nil,
15    Valid(TreeIndex),
16}
17
18impl TreePointer {
19    pub fn unwrap(self) -> TreeIndex {
20        match self {
21            TreePointer::Nil => panic!("Called unwrap on a Nil value"),
22            TreePointer::Valid(ix) => ix,
23        }
24    }
25}
26
27#[derive(Debug, Eq, PartialEq, Copy, Clone, PartialOrd)]
28pub struct TreeIndex(NonZeroUsize);
29
30impl TreeIndex {
31    fn new(i: usize) -> Self {
32        TreeIndex(NonZeroUsize::new(i).unwrap())
33    }
34
35    pub fn get(self) -> usize {
36        self.0.get()
37    }
38}
39
40impl Add<usize> for TreeIndex {
41    type Output = TreeIndex;
42
43    fn add(self, rhs: usize) -> Self {
44        let inner = self.0.get() + rhs;
45        TreeIndex::new(inner)
46    }
47}
48
49impl Sub<usize> for TreeIndex {
50    type Output = TreeIndex;
51
52    fn sub(self, rhs: usize) -> Self {
53        let inner = self.0.get().checked_sub(rhs).unwrap();
54        TreeIndex::new(inner)
55    }
56}
57
58#[derive(Debug, Clone, Copy)]
59pub struct Node<T> {
60    pub child: TreePointer,
61    pub next: TreePointer,
62    pub item: T,
63}
64
65/// A tree abstraction, intended for fast building as a preorder traversal.
66#[derive(Clone)]
67pub struct Tree<T> {
68    nodes: Vec<Node<T>>,
69    spine: Vec<TreeIndex>, // indices of nodes on path to current node
70    cur: TreePointer,
71}
72
73impl<T: Default> Tree<T> {
74    // Indices start at one, so we place a dummy value at index zero.
75    // The alternative would be subtracting one from every TreeIndex
76    // every time we convert it to usize to index our nodes.
77    pub fn with_capacity(cap: usize) -> Tree<T> {
78        let mut nodes = Vec::with_capacity(cap);
79        nodes.push(Node {
80            child: TreePointer::Nil,
81            next: TreePointer::Nil,
82            item: <T as Default>::default(),
83        });
84        Tree {
85            nodes,
86            spine: Vec::new(),
87            cur: TreePointer::Nil,
88        }
89    }
90
91    /// Returns the index of the element currently in focus.
92    pub fn cur(&self) -> TreePointer {
93        self.cur
94    }
95
96    /// Append one item to the current position in the tree.
97    pub fn append(&mut self, item: T) -> TreeIndex {
98        let ix = self.create_node(item);
99        let this = TreePointer::Valid(ix);
100
101        if let TreePointer::Valid(ix) = self.cur {
102            self[ix].next = this;
103        } else if let Some(&parent) = self.spine.last() {
104            self[parent].child = this;
105        }
106        self.cur = this;
107        ix
108    }
109
110    /// Create an isolated node.
111    pub fn create_node(&mut self, item: T) -> TreeIndex {
112        let this = self.nodes.len();
113        self.nodes.push(Node {
114            child: TreePointer::Nil,
115            next: TreePointer::Nil,
116            item,
117        });
118        TreeIndex::new(this)
119    }
120
121    /// Push down one level, so that new items become children of the current node.
122    /// The new focus index is returned.
123    pub fn push(&mut self) -> TreeIndex {
124        let cur_ix = self.cur.unwrap();
125        self.spine.push(cur_ix);
126        self.cur = self[cur_ix].child;
127        cur_ix
128    }
129
130    /// Pop back up a level.
131    pub fn pop(&mut self) -> Option<TreeIndex> {
132        let ix = self.spine.pop()?;
133        self.cur = TreePointer::Valid(ix);
134        Some(ix)
135    }
136
137    /// Look at the parent node.
138    pub fn peek_up(&self) -> Option<TreeIndex> {
139        self.spine.last().cloned()
140    }
141
142    /// Look at grandparent node.
143    pub fn peek_grandparent(&self) -> Option<TreeIndex> {
144        if self.spine.len() >= 2 {
145            Some(self.spine[self.spine.len() - 2])
146        } else {
147            None
148        }
149    }
150
151    /// Returns true when there are no nodes in the tree, false otherwise.
152    pub fn is_empty(&self) -> bool {
153        self.nodes.len() <= 1
154    }
155
156    /// Returns the length of the spine.
157    pub fn spine_len(&self) -> usize {
158        self.spine.len()
159    }
160
161    /// Resets the focus to the first node added to the tree, if it exists.
162    pub fn reset(&mut self) {
163        self.cur = if self.is_empty() {
164            TreePointer::Nil
165        } else {
166            TreePointer::Valid(TreeIndex::new(1))
167        };
168        self.spine.truncate(0);
169    }
170
171    /// Walks the spine from a root node up to, but not including, the current node.
172    pub fn walk_spine(&self) -> impl std::iter::DoubleEndedIterator<Item = &TreeIndex> {
173        self.spine.iter()
174    }
175
176    /// Moves focus to the next sibling of the given node.
177    pub fn next_sibling(&mut self, cur_ix: TreeIndex) -> TreePointer {
178        self.cur = self[cur_ix].next;
179        self.cur
180    }
181}
182
183impl<T> std::fmt::Debug for Tree<T>
184    where T: std::fmt::Debug
185{
186    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
187        fn debug_tree<T>(tree: &Tree<T>, cur: TreeIndex, indent: usize, f: &mut std::fmt::Formatter) -> std::fmt::Result
188            where T: std::fmt::Debug
189        {
190            for _ in 0..indent {
191                write!(f, "  ")?;
192            }
193            writeln!(f, "{:?}", &tree[cur].item)?;
194            if let TreePointer::Valid(child_ix) = tree[cur].child {
195                debug_tree(tree, child_ix, indent + 1, f)?;
196            }
197            if let TreePointer::Valid(next_ix) = tree[cur].next {
198                debug_tree(tree, next_ix, indent, f)?;
199            }
200            Ok(())
201        }
202
203        if self.nodes.len() > 1 {
204            let cur = TreeIndex(NonZeroUsize::new(1).unwrap());
205            debug_tree(self, cur, 0, f)
206        } else {
207            write!(f, "Empty tree")
208        }
209    }
210}
211
212impl<T> std::ops::Index<TreeIndex> for Tree<T> {
213    type Output = Node<T>;
214
215    fn index(&self, ix: TreeIndex) -> &Self::Output {
216        self.nodes.index(ix.get())
217    }
218}
219
220impl<T> std::ops::IndexMut<TreeIndex> for Tree<T> {
221    fn index_mut(&mut self, ix: TreeIndex) -> &mut Node<T> {
222        self.nodes.index_mut(ix.get())
223    }
224}
pulldown_cmark_fork/tree.rs

pulldown_cmark_fork/
tree.rs
