1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
14 //! Starting implementation of a btree for rust.
15 //! Structure inspired by github user davidhalperin's gist.
17 ///A B-tree contains a root node (which contains a vector of elements),
18 ///a length (the height of the tree), and lower and upper bounds on the
19 ///number of elements that a given node can contain.
23 use alloc::boxed::Box;
31 pub struct BTree<K, V> {
38 impl<K: Ord, V> BTree<K, V> {
40 ///Returns new BTree with root node (leaf) and user-supplied lower bound
41 ///The lower bound applies to every node except the root node.
42 pub fn new(k: K, v: V, lb: uint) -> BTree<K, V> {
44 root: Node::new_leaf(vec!(LeafElt::new(k, v))),
51 ///Helper function for clone: returns new BTree with supplied root node,
52 ///length, and lower bound. For use when the length is known already.
53 fn new_with_node_len(n: Node<K, V>,
55 lb: uint) -> BTree<K, V> {
65 //We would probably want to remove the dependence on the Clone trait in the future.
66 //It is here as a crutch to ensure values can be passed around through the tree's nodes
67 //especially during insertions and deletions.
68 impl<K: Clone + Ord, V: Clone> BTree<K, V> {
69 ///Returns the value of a given key, which may not exist in the tree.
70 ///Calls the root node's get method.
71 pub fn get(self, k: K) -> Option<V> {
72 return self.root.get(k);
75 ///An insert method that uses the clone() feature for support.
76 pub fn insert(mut self, k: K, v: V) -> BTree<K, V> {
77 let (a, b) = self.root.clone().insert(k, v, self.upper_bound.clone());
81 self.root = Node::new_leaf(leaf.clone().elts);
83 BranchNode(branch) => {
84 self.root = Node::new_branch(branch.clone().elts,
85 branch.clone().rightmost_child);
93 impl<K: Clone + Ord, V: Clone> Clone for BTree<K, V> {
94 ///Implements the Clone trait for the BTree.
95 ///Uses a helper function/constructor to produce a new BTree.
96 fn clone(&self) -> BTree<K, V> {
97 BTree::new_with_node_len(self.root.clone(), self.len, self.lower_bound)
101 impl<K: Ord, V: Eq> PartialEq for BTree<K, V> {
102 fn eq(&self, other: &BTree<K, V>) -> bool {
103 self.root.cmp(&other.root) == Equal
107 impl<K: Ord, V: Eq> Eq for BTree<K, V> {}
109 impl<K: Ord, V: Eq> PartialOrd for BTree<K, V> {
110 fn partial_cmp(&self, other: &BTree<K, V>) -> Option<Ordering> {
111 Some(self.cmp(other))
115 impl<K: Ord, V: Eq> Ord for BTree<K, V> {
116 ///Returns an ordering based on the root nodes of each BTree.
117 fn cmp(&self, other: &BTree<K, V>) -> Ordering {
118 self.root.cmp(&other.root)
122 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for BTree<K, V> {
123 ///Returns a string representation of the BTree
124 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
131 //A node is either a LeafNode or a BranchNode, which contain either a Leaf or a Branch.
132 //Branches contain BranchElts, which contain a left child (another node) and a key-value
133 //pair. Branches also contain the rightmost child of the elements in the array.
134 //Leaves contain LeafElts, which do not have children.
136 LeafNode(Leaf<K, V>),
137 BranchNode(Branch<K, V>)
141 //Node functions/methods
142 impl<K: Ord, V> Node<K, V> {
143 ///Creates a new leaf node given a vector of elements.
144 fn new_leaf(vec: Vec<LeafElt<K, V>>) -> Node<K,V> {
145 LeafNode(Leaf::new(vec))
148 ///Creates a new branch node given a vector of an elements and a pointer to a rightmost child.
149 fn new_branch(vec: Vec<BranchElt<K, V>>, right: Box<Node<K, V>>)
151 BranchNode(Branch::new(vec, right))
154 ///Determines whether the given Node contains a Branch or a Leaf.
156 fn is_leaf(&self) -> bool {
158 &LeafNode(..) => true,
159 &BranchNode(..) => false
163 ///A binary search function for Nodes.
164 ///Calls either the Branch's or the Leaf's bsearch function.
165 fn bsearch_node(&self, k: K) -> Option<uint> {
167 &LeafNode(ref leaf) => leaf.bsearch_leaf(k),
168 &BranchNode(ref branch) => branch.bsearch_branch(k)
173 impl<K: Clone + Ord, V: Clone> Node<K, V> {
174 ///Returns the corresponding value to the provided key.
175 ///get() is called in different ways on a branch or a leaf.
176 fn get(&self, k: K) -> Option<V> {
178 LeafNode(ref leaf) => return leaf.get(k),
179 BranchNode(ref branch) => return branch.get(k)
183 ///Matches on the Node, then performs and returns the appropriate insert method.
184 fn insert(self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
186 LeafNode(leaf) => leaf.insert(k, v, ub),
187 BranchNode(branch) => branch.insert(k, v, ub)
192 impl<K: Clone + Ord, V: Clone> Clone for Node<K, V> {
193 ///Returns a new node based on whether or not it is a branch or a leaf.
194 fn clone(&self) -> Node<K, V> {
196 LeafNode(ref leaf) => {
197 Node::new_leaf(leaf.elts.clone())
199 BranchNode(ref branch) => {
200 Node::new_branch(branch.elts.clone(),
201 branch.rightmost_child.clone())
207 impl<K: Ord, V: Eq> PartialEq for Node<K, V> {
208 fn eq(&self, other: &Node<K, V>) -> bool {
210 BranchNode(ref branch) => {
215 BranchNode(ref branch2) => branch.cmp(branch2) == Equal,
216 LeafNode(..) => false
219 LeafNode(ref leaf) => {
221 LeafNode(ref leaf2) => leaf.cmp(leaf2) == Equal,
222 BranchNode(..) => false
229 impl<K: Ord, V: Eq> Eq for Node<K, V> {}
231 impl<K: Ord, V: Eq> PartialOrd for Node<K, V> {
232 fn partial_cmp(&self, other: &Node<K, V>) -> Option<Ordering> {
233 Some(self.cmp(other))
237 impl<K: Ord, V: Eq> Ord for Node<K, V> {
238 ///Implementation of Ord for Nodes.
239 fn cmp(&self, other: &Node<K, V>) -> Ordering {
241 LeafNode(ref leaf) => {
243 LeafNode(ref leaf2) => leaf.cmp(leaf2),
244 BranchNode(_) => Less
247 BranchNode(ref branch) => {
249 BranchNode(ref branch2) => branch.cmp(branch2),
250 LeafNode(_) => Greater
257 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Node<K, V> {
258 ///Returns a string representation of a Node.
259 ///Will iterate over the Node and show "Key: x, value: y, child: () // "
260 ///for all elements in the Node. "Child" only exists if the Node contains
262 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
264 LeafNode(ref leaf) => leaf.fmt(f),
265 BranchNode(ref branch) => branch.fmt(f),
271 //A leaf is a vector with elements that contain no children. A leaf also
272 //does not contain a rightmost child.
274 elts: Vec<LeafElt<K, V>>
277 //Vector of values with children, plus a rightmost child (greater than all)
278 struct Branch<K, V> {
279 elts: Vec<BranchElt<K,V>>,
280 rightmost_child: Box<Node<K, V>>,
284 impl<K: Ord, V> Leaf<K, V> {
285 ///Creates a new Leaf from a vector of LeafElts.
286 fn new(vec: Vec<LeafElt<K, V>>) -> Leaf<K, V> {
292 ///Searches a leaf for a spot for a new element using a binary search.
293 ///Returns None if the element is already in the vector.
294 fn bsearch_leaf(&self, k: K) -> Option<uint> {
295 let mut high: uint = self.elts.len();
296 let mut low: uint = 0;
297 let mut midpoint: uint = (high - low) / 2 ;
298 if midpoint == high {
302 let order = self.elts.get(midpoint).key.cmp(&k);
309 if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
310 return Some(midpoint);
314 midpoint = midpoint / 2;
324 if midpoint + 1 < self.elts.len() {
325 if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
326 return Some(midpoint);
330 midpoint = (high + low) / 2;
335 return Some(self.elts.len());
344 impl<K: Clone + Ord, V: Clone> Leaf<K, V> {
345 ///Returns the corresponding value to the supplied key.
346 fn get(&self, k: K) -> Option<V> {
347 for s in self.elts.iter() {
348 let order = s.key.cmp(&k);
350 Equal => return Some(s.value.clone()),
357 ///Uses clone() to facilitate inserting new elements into a tree.
358 fn insert(mut self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
359 let to_insert = LeafElt::new(k, v);
360 let index: Option<uint> = self.bsearch_leaf(to_insert.clone().key);
361 //Check index to see whether we actually inserted the element into the vector.
363 //If the index is None, the new element already exists in the vector.
365 return (Node::new_leaf(self.clone().elts), false);
367 //If there is an index, insert at that index.
369 if i >= self.elts.len() {
370 self.elts.push(to_insert.clone());
373 self.elts.insert(i, to_insert.clone());
377 //If we have overfilled the vector (by making its size greater than the
378 //upper bound), we return a new Branch with one element and two children.
379 if self.elts.len() > ub {
380 let midpoint_opt = self.elts.remove(ub / 2);
381 let midpoint = midpoint_opt.unwrap();
382 let (left_leaf, right_leaf) = self.elts.partition(|le|
383 le.key.cmp(&midpoint.key.clone())
385 let branch_return = Node::new_branch(vec!(BranchElt::new(midpoint.key.clone(),
386 midpoint.value.clone(),
387 box Node::new_leaf(left_leaf))),
388 box Node::new_leaf(right_leaf));
389 return (branch_return, true);
391 (Node::new_leaf(self.elts.clone()), true)
395 impl<K: Clone + Ord, V: Clone> Clone for Leaf<K, V> {
396 ///Returns a new Leaf with the same elts.
397 fn clone(&self) -> Leaf<K, V> {
398 Leaf::new(self.elts.clone())
402 impl<K: Ord, V: Eq> PartialEq for Leaf<K, V> {
403 fn eq(&self, other: &Leaf<K, V>) -> bool {
404 self.elts == other.elts
408 impl<K: Ord, V: Eq> Eq for Leaf<K, V> {}
410 impl<K: Ord, V: Eq> PartialOrd for Leaf<K, V> {
411 fn partial_cmp(&self, other: &Leaf<K, V>) -> Option<Ordering> {
412 Some(self.cmp(other))
416 impl<K: Ord, V: Eq> Ord for Leaf<K, V> {
417 ///Returns an ordering based on the first element of each Leaf.
418 fn cmp(&self, other: &Leaf<K, V>) -> Ordering {
419 if self.elts.len() > other.elts.len() {
422 if self.elts.len() < other.elts.len() {
425 self.elts.get(0).cmp(other.elts.get(0))
430 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Leaf<K, V> {
431 ///Returns a string representation of a Leaf.
432 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
433 for (i, s) in self.elts.iter().enumerate() {
434 if i != 0 { try!(write!(f, " // ")) }
435 try!(write!(f, "{}", *s))
442 impl<K: Ord, V> Branch<K, V> {
443 ///Creates a new Branch from a vector of BranchElts and a rightmost child (a node).
444 fn new(vec: Vec<BranchElt<K, V>>, right: Box<Node<K, V>>)
448 rightmost_child: right
452 fn bsearch_branch(&self, k: K) -> Option<uint> {
453 let mut midpoint: uint = self.elts.len() / 2;
454 let mut high: uint = self.elts.len();
455 let mut low: uint = 0u;
456 if midpoint == high {
460 let order = self.elts.get(midpoint).key.cmp(&k);
467 if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
468 return Some(midpoint);
472 midpoint = (midpoint - low) / 2;
482 if midpoint + 1 < self.elts.len() {
483 if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
484 return Some(midpoint);
488 midpoint = (high - midpoint) / 2;
493 return Some(self.elts.len());
501 impl<K: Clone + Ord, V: Clone> Branch<K, V> {
502 ///Returns the corresponding value to the supplied key.
503 ///If the key is not there, find the child that might hold it.
504 fn get(&self, k: K) -> Option<V> {
505 for s in self.elts.iter() {
506 let order = s.key.cmp(&k);
508 Less => return s.left.get(k),
509 Equal => return Some(s.value.clone()),
513 self.rightmost_child.get(k)
516 ///An insert method that uses .clone() for support.
517 fn insert(mut self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
518 let mut new_branch = Node::new_branch(self.clone().elts, self.clone().rightmost_child);
519 let mut outcome = false;
520 let index: Option<uint> = new_branch.bsearch_node(k.clone());
521 //First, find which path down the tree will lead to the appropriate leaf
522 //for the key-value pair.
523 match index.clone() {
525 return (Node::new_branch(self.clone().elts,
526 self.clone().rightmost_child),
530 if i == self.elts.len() {
531 let new_outcome = self.clone().rightmost_child.insert(k.clone(),
534 new_branch = new_outcome.clone().val0();
535 outcome = new_outcome.val1();
538 let new_outcome = self.elts.get(i).left.clone().insert(k.clone(),
541 new_branch = new_outcome.clone().val0();
542 outcome = new_outcome.val1();
544 //Check to see whether a branch or a leaf was returned from the
546 match new_branch.clone() {
547 //If we have a leaf, we do not need to resize the tree,
548 //so we can return false.
550 if i == self.elts.len() {
551 self.rightmost_child = box new_branch.clone();
554 self.elts.get_mut(i).left = box new_branch.clone();
556 return (Node::new_branch(self.clone().elts,
557 self.clone().rightmost_child),
560 //If we have a branch, we might need to refactor the tree.
565 //If we inserted something into the tree, do the following:
567 match new_branch.clone() {
568 //If we have a new leaf node, integrate it into the current branch
569 //and return it, saying we have inserted a new element.
571 if index.unwrap() == self.elts.len() {
572 self.rightmost_child = box new_branch;
575 self.elts.get_mut(index.unwrap()).left = box new_branch;
577 return (Node::new_branch(self.clone().elts,
578 self.clone().rightmost_child),
581 //If we have a new branch node, attempt to insert it into the tree
582 //as with the key-value pair, then check to see if the node is overfull.
583 BranchNode(branch) => {
584 let new_elt = branch.elts.get(0).clone();
585 let new_elt_index = self.bsearch_branch(new_elt.clone().key);
586 match new_elt_index {
588 return (Node::new_branch(self.clone().elts,
589 self.clone().rightmost_child),
593 self.elts.insert(i, new_elt);
594 if i + 1 >= self.elts.len() {
595 self.rightmost_child = branch.clone().rightmost_child;
598 self.elts.get_mut(i + 1).left =
599 branch.clone().rightmost_child;
605 //If the current node is overfilled, create a new branch with one element
607 if self.elts.len() > ub {
608 let midpoint = self.elts.remove(ub / 2).unwrap();
609 let (new_left, new_right) = self.clone().elts.partition(|le|
610 midpoint.key.cmp(&le.key)
612 new_branch = Node::new_branch(
613 vec!(BranchElt::new(midpoint.clone().key,
614 midpoint.clone().value,
615 box Node::new_branch(new_left,
616 midpoint.clone().left))),
617 box Node::new_branch(new_right, self.clone().rightmost_child));
618 return (new_branch, true);
621 (Node::new_branch(self.elts.clone(), self.rightmost_child.clone()), outcome)
625 impl<K: Clone + Ord, V: Clone> Clone for Branch<K, V> {
626 ///Returns a new branch using the clone methods of the Branch's internal variables.
627 fn clone(&self) -> Branch<K, V> {
628 Branch::new(self.elts.clone(), self.rightmost_child.clone())
632 impl<K: Ord, V: Eq> PartialEq for Branch<K, V> {
633 fn eq(&self, other: &Branch<K, V>) -> bool {
634 self.elts == other.elts
638 impl<K: Ord, V: Eq> Eq for Branch<K, V> {}
640 impl<K: Ord, V: Eq> PartialOrd for Branch<K, V> {
641 fn partial_cmp(&self, other: &Branch<K, V>) -> Option<Ordering> {
642 Some(self.cmp(other))
646 impl<K: Ord, V: Eq> Ord for Branch<K, V> {
647 ///Compares the first elements of two branches to determine an ordering
648 fn cmp(&self, other: &Branch<K, V>) -> Ordering {
649 if self.elts.len() > other.elts.len() {
652 if self.elts.len() < other.elts.len() {
655 self.elts.get(0).cmp(other.elts.get(0))
659 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Branch<K, V> {
660 ///Returns a string representation of a Branch.
661 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
662 for (i, s) in self.elts.iter().enumerate() {
663 if i != 0 { try!(write!(f, " // ")) }
664 try!(write!(f, "{}", *s))
666 write!(f, " // rightmost child: ({}) ", *self.rightmost_child)
670 //A LeafElt contains no left child, but a key-value pair.
671 struct LeafElt<K, V> {
676 //A BranchElt has a left child in insertion to a key-value pair.
677 struct BranchElt<K, V> {
678 left: Box<Node<K, V>>,
683 impl<K: Ord, V> LeafElt<K, V> {
684 ///Creates a new LeafElt from a supplied key-value pair.
685 fn new(k: K, v: V) -> LeafElt<K, V> {
693 impl<K: Clone + Ord, V: Clone> Clone for LeafElt<K, V> {
694 ///Returns a new LeafElt by cloning the key and value.
695 fn clone(&self) -> LeafElt<K, V> {
696 LeafElt::new(self.key.clone(), self.value.clone())
700 impl<K: Ord, V: Eq> PartialEq for LeafElt<K, V> {
701 fn eq(&self, other: &LeafElt<K, V>) -> bool {
702 self.key == other.key && self.value == other.value
706 impl<K: Ord, V: Eq> Eq for LeafElt<K, V> {}
708 impl<K: Ord, V: Eq> PartialOrd for LeafElt<K, V> {
709 fn partial_cmp(&self, other: &LeafElt<K, V>) -> Option<Ordering> {
710 Some(self.cmp(other))
714 impl<K: Ord, V: Eq> Ord for LeafElt<K, V> {
715 ///Returns an ordering based on the keys of the LeafElts.
716 fn cmp(&self, other: &LeafElt<K, V>) -> Ordering {
717 self.key.cmp(&other.key)
721 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for LeafElt<K, V> {
722 ///Returns a string representation of a LeafElt.
723 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
724 write!(f, "Key: {}, value: {};", self.key, self.value)
728 impl<K: Ord, V> BranchElt<K, V> {
729 ///Creates a new BranchElt from a supplied key, value, and left child.
730 fn new(k: K, v: V, n: Box<Node<K, V>>) -> BranchElt<K, V> {
740 impl<K: Clone + Ord, V: Clone> Clone for BranchElt<K, V> {
741 ///Returns a new BranchElt by cloning the key, value, and left child.
742 fn clone(&self) -> BranchElt<K, V> {
743 BranchElt::new(self.key.clone(),
749 impl<K: Ord, V: Eq> PartialEq for BranchElt<K, V>{
750 fn eq(&self, other: &BranchElt<K, V>) -> bool {
751 self.key == other.key && self.value == other.value
755 impl<K: Ord, V: Eq> Eq for BranchElt<K, V>{}
757 impl<K: Ord, V: Eq> PartialOrd for BranchElt<K, V> {
758 fn partial_cmp(&self, other: &BranchElt<K, V>) -> Option<Ordering> {
759 Some(self.cmp(other))
763 impl<K: Ord, V: Eq> Ord for BranchElt<K, V> {
764 ///Fulfills Ord for BranchElts
765 fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
766 self.key.cmp(&other.key)
770 impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for BranchElt<K, V> {
771 /// Returns string containing key, value, and child (which should recur to a
772 /// leaf) Consider changing in future to be more readable.
773 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
774 write!(f, "Key: {}, value: {}, (child: {})",
775 self.key, self.value, *self.left)
783 use super::{BTree, Node, LeafElt};
785 //Tests the functionality of the insert methods (which are unfinished).
787 fn insert_test_one() {
788 let b = BTree::new(1i, "abc".to_string(), 2);
789 let is_insert = b.insert(2i, "xyz".to_string());
790 assert!(is_insert.root.is_leaf());
794 fn insert_test_two() {
795 let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
796 let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
797 let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
798 let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3));
799 let b = BTree::new_with_node_len(n, 3, 2);
800 //println!("{}", b.clone().insert(4, "ddd".to_string()).to_string());
801 assert!(b.insert(4, "ddd".to_string()).root.is_leaf());
805 fn insert_test_three() {
806 let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
807 let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
808 let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
809 let leaf_elt_4 = LeafElt::new(4i, "ddd".to_string());
810 let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
811 let b = BTree::new_with_node_len(n, 3, 2);
812 //println!("{}", b.clone().insert(5, "eee".to_string()).to_string());
813 assert!(!b.insert(5, "eee".to_string()).root.is_leaf());
817 fn insert_test_four() {
818 let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
819 let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
820 let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
821 let leaf_elt_4 = LeafElt::new(4i, "ddd".to_string());
822 let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
823 let mut b = BTree::new_with_node_len(n, 3, 2);
824 b = b.clone().insert(5, "eee".to_string());
825 b = b.clone().insert(6, "fff".to_string());
826 b = b.clone().insert(7, "ggg".to_string());
827 b = b.clone().insert(8, "hhh".to_string());
828 b = b.clone().insert(0, "omg".to_string());
829 //println!("{}", b.clone().to_string());
830 assert!(!b.root.is_leaf());
834 fn bsearch_test_one() {
835 let b = BTree::new(1i, "abc".to_string(), 2u);
836 assert_eq!(Some(1), b.root.bsearch_node(2));
840 fn bsearch_test_two() {
841 let b = BTree::new(1i, "abc".to_string(), 2u);
842 assert_eq!(Some(0), b.root.bsearch_node(0));
846 fn bsearch_test_three() {
847 let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
848 let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
849 let leaf_elt_3 = LeafElt::new(4i, "ccc".to_string());
850 let leaf_elt_4 = LeafElt::new(5i, "ddd".to_string());
851 let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
852 let b = BTree::new_with_node_len(n, 3, 2);
853 assert_eq!(Some(2), b.root.bsearch_node(3));
857 fn bsearch_test_four() {
858 let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
859 let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
860 let leaf_elt_3 = LeafElt::new(4i, "ccc".to_string());
861 let leaf_elt_4 = LeafElt::new(5i, "ddd".to_string());
862 let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
863 let b = BTree::new_with_node_len(n, 3, 2);
864 assert_eq!(Some(4), b.root.bsearch_node(800));
867 //Tests the functionality of the get method.
870 let b = BTree::new(1i, "abc".to_string(), 2);
872 assert_eq!(val, Some("abc".to_string()));
875 //Tests the BTree's clone() method.
877 fn btree_clone_test() {
878 let b = BTree::new(1i, "abc".to_string(), 2);
880 assert!(b.root == b2.root)
883 //Tests the BTree's cmp() method when one node is "less than" another.
885 fn btree_cmp_test_less() {
886 let b = BTree::new(1i, "abc".to_string(), 2);
887 let b2 = BTree::new(2i, "bcd".to_string(), 2);
888 assert!(&b.cmp(&b2) == &Less)
891 //Tests the BTree's cmp() method when two nodes are equal.
893 fn btree_cmp_test_eq() {
894 let b = BTree::new(1i, "abc".to_string(), 2);
895 let b2 = BTree::new(1i, "bcd".to_string(), 2);
896 assert!(&b.cmp(&b2) == &Equal)
899 //Tests the BTree's cmp() method when one node is "greater than" another.
901 fn btree_cmp_test_greater() {
902 let b = BTree::new(1i, "abc".to_string(), 2);
903 let b2 = BTree::new(2i, "bcd".to_string(), 2);
904 assert!(&b2.cmp(&b) == &Greater)
907 //Tests the BTree's to_string() method.
909 fn btree_tostr_test() {
910 let b = BTree::new(1i, "abc".to_string(), 2);
911 assert_eq!(b.to_string(), "Key: 1, value: abc;".to_string())