binary_tree/
lib.rs

1//! Provides a collection of binary tree based data structures and algorithms.
2//!
3//! ## Terminology
4//!
5//! * The root of a tree is considered to be at the top.
6//! * Height of a node is the length of the longest path to _its_ leaves. Thus
7//!   all leaf nodes have zero height.
8
9#[cfg(feature="quickcheck")]
10extern crate quickcheck;
11
12pub mod cow;
13pub mod count;
14pub mod iter;
15pub mod test;
16pub mod unbox;
17
18use std::mem;
19use std::ops::DerefMut;
20
21pub trait BinaryTree {
22    type Node: Node;
23
24    fn root(&self) -> Option<&Self::Node>;
25}
26
27unsafe fn borrow<'a, T, U>(raw: *const T, _: &'a U) -> &'a T {
28    &*raw
29}
30
31unsafe fn borrow_mut<'a, T, U>(raw: *mut T, _: &'a U) -> &'a mut T {
32    &mut *raw
33}
34
35/// Generic methods for traversing a binary tree.
36pub trait Node {
37    type Value;
38
39    /// Get a reference to the left subtree
40    fn left(&self) -> Option<&Self>;
41
42    /// Get a reference to the right subtree
43    fn right(&self) -> Option<&Self>;
44
45    /// Returns the value of the current node.
46    fn value(&self) -> &Self::Value;
47
48    /// Walk down the tree
49    fn walk<'a, F>(&'a self, mut step_in: F)
50        where F: FnMut(&'a Self) -> WalkAction
51    {
52        use WalkAction::*;
53
54        let mut subtree = Some(self);
55        while let Some(mut st) = subtree {
56            let action = step_in(&mut st);
57            subtree = match action {
58                Left => st.left(),
59                Right => st.right(),
60                Stop => break,
61            };
62        }
63    }
64}
65
66/// Mutating methods on a Binary Tree node.
67pub trait NodeMut: Node + Sized {
68    type NodePtr: Sized + DerefMut<Target = Self>;
69
70    /// Try to detach the left sub-tree
71    fn detach_left(&mut self) -> Option<Self::NodePtr>;
72
73    /// Try to detach the right sub-tree
74    fn detach_right(&mut self) -> Option<Self::NodePtr>;
75
76    /// Replace the left subtree with `tree` and return the old one.
77    fn insert_left(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>;
78
79    /// Replace the right subtree with `tree` and return the old one.
80    fn insert_right(&mut self, tree: Option<Self::NodePtr>) -> Option<Self::NodePtr>;
81
82    /// Returns a mutable reference to the value of the current node.
83    fn value_mut(&mut self) -> &mut Self::Value;
84
85    /// Consume a Node and return its parts: (value, left, right)
86    fn into_parts(self) -> (Self::Value, Option<Self::NodePtr>, Option<Self::NodePtr>);
87
88    /// Returns a mutable reference to the left child
89    fn left_mut(&mut self) -> Option<&mut Self>;
90
91    /// Returns a mutable reference to the right child
92    fn right_mut(&mut self) -> Option<&mut Self>;
93
94    /// Try to rotate the tree left if right subtree exists
95    fn rotate_left(&mut self) -> Result<(), ()> {
96        if let Some(mut self2) = self.detach_right() {
97            let mid = self2.detach_left();
98            self.insert_right(mid);
99            mem::swap(self, &mut self2);
100            self.insert_left(Some(self2));
101            Ok(())
102        } else {
103            Err(())
104        }
105    }
106
107    /// Try to rotate the tree right if left subtree exists
108    fn rotate_right(&mut self) -> Result<(), ()> {
109        if let Some(mut self2) = self.detach_left() {
110            let mid = self2.detach_right();
111            self.insert_left(mid);
112            mem::swap(self, &mut self2);
113            self.insert_right(Some(self2));
114            Ok(())
115        } else {
116            Err(())
117        }
118    }
119
120    /// Simple mutable walk
121    ///
122    /// Note that the type of `step_in` is almost identical to that in
123    /// `Node::walk`, but not exactly so. Here, `step_in` does not get a
124    /// reference which lives as long as `self` so that it cannot leak
125    /// references out to its environment.
126    fn walk_mut<'a, FI, FS>(&'a mut self, mut step_in: FI, stop: FS)
127        where FI: FnMut(&Self) -> WalkAction,
128              FS: FnOnce(&'a mut Self)
129    {
130        use WalkAction::*;
131
132        let mut node: *mut _ = self;
133        loop {
134            let action = {
135                let pin = ();
136                step_in(unsafe { borrow(node, &pin) })
137            };
138            let next = match action {
139                Left => unsafe { borrow_mut(node, self) }.left_mut(),
140                Right => unsafe { borrow_mut(node, self) }.right_mut(),
141                Stop => break,
142            };
143            if let Some(st) = next {
144                node = st;
145            } else {
146                break;
147            }
148        }
149        stop(unsafe { borrow_mut(node, self) });
150    }
151
152    /// Walks down the tree by detaching subtrees, then up reattaching them
153    /// back. `step_in` should guide the path taken, `stop` will be called on
154    /// the node where either `step_in` returned `Stop` or it was not possible
155    /// to proceed. Then `step_out` will be called for each node along the way
156    /// to root, except the final one (that for which `stop` was called).
157    fn walk_reshape<FI, FS, FO>(&mut self, mut step_in: FI, stop: FS, mut step_out: FO)
158        where FI: FnMut(&mut Self) -> WalkAction,
159              FS: FnOnce(&mut Self),
160              FO: FnMut(&mut Self, WalkAction)
161    {
162        use WalkAction::*;
163
164        let mut stack = Vec::with_capacity(8);
165        let root_action = step_in(self);
166        let mut subtree = match root_action {
167            Left => self.detach_left(),
168            Right => self.detach_right(),
169            Stop => None,
170        };
171        let mut action = root_action;
172        while action != Stop {
173            if let Some(mut st) = subtree {
174                action = step_in(&mut st);
175                subtree = match action {
176                    Left => st.detach_left(),
177                    Right => st.detach_right(),
178                    Stop => None,
179                };
180                stack.push((st, action));
181            } else {
182                break;
183            }
184        }
185        if let Some((mut sst, _)) = stack.pop() {
186            //               -^- the final action is irrelevant
187            stop(&mut sst);
188            while let Some((mut st, action)) = stack.pop() {
189                match action {
190                    Left => st.insert_left(Some(sst)),
191                    Right => st.insert_right(Some(sst)),
192                    Stop => unreachable!(),
193                };
194                step_out(&mut st, action);
195                sst = st;
196            }
197            match root_action {
198                Left => self.insert_left(Some(sst)),
199                Right => self.insert_right(Some(sst)),
200                Stop => unreachable!(),
201            };
202            step_out(self, root_action);
203        } else {
204            stop(self)
205        }
206    }
207
208    /// Insert `new_node` in-order before `self`. `step_out` will be invoked for
209    /// all nodes in path from (excluding) the point of insertion, to
210    /// (including) `self`, unless `self` is the point of insertion.
211    fn insert_before<F>(&mut self, new_node: Self::NodePtr, mut step_out: F)
212        where F: FnMut(&mut Self, WalkAction)
213    {
214        use WalkAction::*;
215
216        if let Some(mut left) = self.detach_left() {
217            left.walk_reshape(|_| Right,
218                              move |node| {
219                                  node.insert_right(Some(new_node));
220                              },
221                              &mut step_out);
222            self.insert_left(Some(left));
223            step_out(self, Left);
224        } else {
225            self.insert_left(Some(new_node));
226        }
227    }
228
229    /// Extract out a node. This can be used in conjuction with `try_remove` to
230    /// remove any node except the root.
231    ///
232    /// The closure `extract` should try to take out the desired node from its
233    /// first argument and move it to its second argument (possibly using
234    /// `try_remove`). If it was unable to do it, the final node that was
235    /// visited will be taken out and returned, unless it is the root itself.
236    ///
237    /// Note that, similar to `walk_reshape`, `step_out` is not called for the
238    /// finally visited node (that for which `extract` was called).
239    ///
240    /// See the source of `CountTree::remove` for an example use.
241    fn walk_extract<FI, FE, FO>(&mut self, step_in: FI, extract: FE, mut step_out: FO) -> Option<Self::NodePtr>
242        where FI: FnMut(&mut Self) -> WalkAction,
243              FE: FnOnce(&mut Self, &mut Option<Self::NodePtr>),
244              FO: FnMut(&mut Self, WalkAction)
245    {
246        use WalkAction::*;
247
248        let ret = std::cell::RefCell::new(None);
249        self.walk_reshape(step_in,
250                          |node| extract(node, &mut *ret.borrow_mut()),
251                          |node, action| {
252                              if ret.borrow().is_none() {
253                                  // take out the last visited node if `extract` was unable to
254                                  *ret.borrow_mut() = match action {
255                                      Left => node.detach_left(),
256                                      Right => node.detach_right(),
257                                      Stop => unreachable!(),
258                                  };
259                              }
260                              step_out(node, action);
261                          });
262        ret.into_inner()
263    }
264
265    /// Replace this node with one of its descendant, returns `None` if it has
266    /// no children.
267    fn try_remove<F>(&mut self, mut step_out: F) -> Option<Self::NodePtr>
268        where F: FnMut(&mut Self, WalkAction)
269    {
270        use WalkAction::*;
271
272        if let Some(mut left) = self.detach_left() {
273            if self.right().is_none() {
274                mem::swap(&mut *left, self);
275                Some(left)
276            } else {
277                // fetch the rightmost descendant of left into pio (previous-in-order of self)
278                let mut pio = left.walk_extract(|_| Right,
279                                                |node, ret| {
280                                                    if let Some(mut left) = node.detach_left() {
281                                                        // the rightmost node has a left child
282                                                        mem::swap(&mut *left, node);
283                                                        *ret = Some(left);
284                                                    }
285                                                },
286                                                &mut step_out);
287                if let Some(ref mut pio) = pio {
288                    pio.insert_left(Some(left));
289                } else {
290                    // left had no right child
291                    pio = Some(left);
292                }
293                let mut pio = pio.unwrap();
294                pio.insert_right(self.detach_right());
295                step_out(&mut pio, Left);
296                mem::swap(&mut *pio, self);
297                Some(pio) // old self
298            }
299        } else if let Some(mut right) = self.detach_right() {
300            mem::swap(&mut *right, self);
301            Some(right)
302        } else {
303            None
304        }
305    }
306}
307
308#[derive(Clone, Copy, PartialEq)]
309/// List of actions during a `Node::walk` or `NodeMut::walk_*`.
310pub enum WalkAction {
311    /// Enter(ed) the left child
312    Left,
313    /// Enter(ed) the right child
314    Right,
315    /// Stop walking
316    Stop,
317}
binary_tree/lib.rs

binary_tree/
lib.rs
