src/libcollections/btree.rs

   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.
   4 //
   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.
  10 //
  11 // btree.rs
  12 //
  13
  14 //! Starting implementation of a btree for rust.
  15 //! Structure inspired by github user davidhalperin's gist.
  16
  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.
  20
  21 use core::prelude::*;
  22
  23 use alloc::owned::Box;
  24 use core::fmt;
  25 use core::fmt::Show;
  26
  27 use Collection;
  28 use vec::Vec;
  29
  30 #[allow(missing_doc)]
  31 pub struct BTree<K, V> {
  32     root: Node<K, V>,
  33     len: uint,
  34     lower_bound: uint,
  35     upper_bound: uint
  36 }
  37
  38 impl<K: Ord, V> BTree<K, V> {
  39
  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> {
  43         BTree {
  44             root: Node::new_leaf(vec!(LeafElt::new(k, v))),
  45             len: 1,
  46             lower_bound: lb,
  47             upper_bound: 2 * lb
  48         }
  49     }
  50
  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>,
  54                          length: uint,
  55                          lb: uint) -> BTree<K, V> {
  56         BTree {
  57             root: n,
  58             len: length,
  59             lower_bound: lb,
  60             upper_bound: 2 * lb
  61         }
  62     }
  63 }
  64
  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);
  73     }
  74
  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());
  78         if b {
  79             match a.clone() {
  80                 LeafNode(leaf) => {
  81                     self.root = Node::new_leaf(leaf.clone().elts);
  82                 }
  83                 BranchNode(branch) => {
  84                     self.root = Node::new_branch(branch.clone().elts,
  85                                                  branch.clone().rightmost_child);
  86                 }
  87             }
  88         }
  89         self
  90     }
  91 }
  92
  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)
  98     }
  99 }
 100
 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
 104     }
 105 }
 106
 107 impl<K: Ord, V: Eq> Eq for BTree<K, V> {}
 108
 109 impl<K: Ord, V: Eq> PartialOrd for BTree<K, V> {
 110     fn lt(&self, other: &BTree<K, V>) -> bool {
 111         self.cmp(other) == Less
 112     }
 113 }
 114
 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)
 119     }
 120 }
 121
 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 {
 125         self.root.fmt(f)
 126     }
 127 }
 128
 129
 130 //Node types
 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.
 135 enum Node<K, V> {
 136     LeafNode(Leaf<K, V>),
 137     BranchNode(Branch<K, V>)
 138 }
 139
 140
 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))
 146     }
 147
 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>>)
 150                   -> Node<K, V> {
 151         BranchNode(Branch::new(vec, right))
 152     }
 153
 154     ///Determines whether the given Node contains a Branch or a Leaf.
 155     ///Used in testing.
 156     fn is_leaf(&self) -> bool {
 157         match self {
 158             &LeafNode(..) => true,
 159             &BranchNode(..) => false
 160         }
 161     }
 162
 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> {
 166          match self {
 167              &LeafNode(ref leaf) => leaf.bsearch_leaf(k),
 168              &BranchNode(ref branch) => branch.bsearch_branch(k)
 169          }
 170      }
 171 }
 172
 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> {
 177         match *self {
 178             LeafNode(ref leaf) => return leaf.get(k),
 179             BranchNode(ref branch) => return branch.get(k)
 180         }
 181     }
 182
 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) {
 185         match self {
 186             LeafNode(leaf) => leaf.insert(k, v, ub),
 187             BranchNode(branch) => branch.insert(k, v, ub)
 188         }
 189     }
 190 }
 191
 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> {
 195         match *self {
 196             LeafNode(ref leaf) => {
 197                 Node::new_leaf(leaf.elts.clone())
 198             }
 199             BranchNode(ref branch) => {
 200                 Node::new_branch(branch.elts.clone(),
 201                                  branch.rightmost_child.clone())
 202             }
 203         }
 204     }
 205 }
 206
 207 impl<K: Ord, V: Eq> PartialEq for Node<K, V> {
 208     fn eq(&self, other: &Node<K, V>) -> bool {
 209         match *self{
 210             BranchNode(ref branch) => {
 211                 if other.is_leaf() {
 212                     return false;
 213                 }
 214                 match *other {
 215                     BranchNode(ref branch2) => branch.cmp(branch2) == Equal,
 216                     LeafNode(..) => false
 217                 }
 218             }
 219             LeafNode(ref leaf) => {
 220                 match *other {
 221                     LeafNode(ref leaf2) => leaf.cmp(leaf2) == Equal,
 222                     BranchNode(..) => false
 223                 }
 224             }
 225         }
 226     }
 227 }
 228
 229 impl<K: Ord, V: Eq> Eq for Node<K, V> {}
 230
 231 impl<K: Ord, V: Eq> PartialOrd for Node<K, V> {
 232     fn lt(&self, other: &Node<K, V>) -> bool {
 233         self.cmp(other) == Less
 234     }
 235 }
 236
 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 {
 240         match *self {
 241             LeafNode(ref leaf) => {
 242                 match *other {
 243                     LeafNode(ref leaf2) => leaf.cmp(leaf2),
 244                     BranchNode(_) => Less
 245                 }
 246             }
 247             BranchNode(ref branch) => {
 248                 match *other {
 249                     BranchNode(ref branch2) => branch.cmp(branch2),
 250                     LeafNode(_) => Greater
 251                 }
 252             }
 253         }
 254     }
 255 }
 256
 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
 261     ///a branch.
 262     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 263         match *self {
 264             LeafNode(ref leaf) => leaf.fmt(f),
 265             BranchNode(ref branch) => branch.fmt(f),
 266         }
 267     }
 268 }
 269
 270
 271 //A leaf is a vector with elements that contain no children.  A leaf also
 272 //does not contain a rightmost child.
 273 struct Leaf<K, V> {
 274     elts: Vec<LeafElt<K, V>>
 275 }
 276
 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>>,
 281 }
 282
 283
 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> {
 287         Leaf {
 288             elts: vec
 289         }
 290     }
 291
 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 {
 299             midpoint = 0;
 300         }
 301         loop {
 302             let order = self.elts.get(midpoint).key.cmp(&k);
 303             match order {
 304                 Equal => {
 305                     return None;
 306                 }
 307                 Greater => {
 308                     if midpoint > 0 {
 309                         if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
 310                             return Some(midpoint);
 311                         }
 312                         else {
 313                             let tmp = midpoint;
 314                             midpoint = midpoint / 2;
 315                             high = tmp;
 316                             continue;
 317                         }
 318                     }
 319                     else {
 320                         return Some(0);
 321                     }
 322                 }
 323                 Less => {
 324                     if midpoint + 1 < self.elts.len() {
 325                         if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
 326                             return Some(midpoint);
 327                         }
 328                         else {
 329                             let tmp = midpoint;
 330                             midpoint = (high + low) / 2;
 331                             low = tmp;
 332                         }
 333                     }
 334                     else {
 335                         return Some(self.elts.len());
 336                     }
 337                 }
 338             }
 339         }
 340     }
 341 }
 342
 343
 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);
 349             match order {
 350                 Equal => return Some(s.value.clone()),
 351                 _ => {}
 352             }
 353         }
 354         return None;
 355     }
 356
 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.
 362         match index {
 363             //If the index is None, the new element already exists in the vector.
 364             None => {
 365                 return (Node::new_leaf(self.clone().elts), false);
 366             }
 367             //If there is an index, insert at that index.
 368             _ => {
 369                 if index.unwrap() >= self.elts.len() {
 370                     self.elts.push(to_insert.clone());
 371                 }
 372                 else {
 373                     self.elts.insert(index.unwrap(), to_insert.clone());
 374                 }
 375             }
 376         }
 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())
 384                                                               == Less);
 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);
 390         }
 391         (Node::new_leaf(self.elts.clone()), true)
 392     }
 393 }
 394
 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())
 399     }
 400 }
 401
 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
 405     }
 406 }
 407
 408 impl<K: Ord, V: Eq> Eq for Leaf<K, V> {}
 409
 410 impl<K: Ord, V: Eq> PartialOrd for Leaf<K, V> {
 411     fn lt(&self, other: &Leaf<K, V>) -> bool {
 412         self.cmp(other) == Less
 413     }
 414 }
 415
 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() {
 420             return Greater;
 421         }
 422         if self.elts.len() < other.elts.len() {
 423             return Less;
 424         }
 425         self.elts.get(0).cmp(other.elts.get(0))
 426     }
 427 }
 428
 429
 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))
 436         }
 437         Ok(())
 438     }
 439 }
 440
 441
 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>>)
 445            -> Branch<K, V> {
 446         Branch {
 447             elts: vec,
 448             rightmost_child: right
 449         }
 450     }
 451
 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 {
 457             midpoint = 0u;
 458         }
 459         loop {
 460             let order = self.elts.get(midpoint).key.cmp(&k);
 461             match order {
 462                 Equal => {
 463                     return None;
 464                 }
 465                 Greater => {
 466                     if midpoint > 0 {
 467                         if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
 468                             return Some(midpoint);
 469                         }
 470                         else {
 471                             let tmp = midpoint;
 472                             midpoint = (midpoint - low) / 2;
 473                             high = tmp;
 474                             continue;
 475                         }
 476                     }
 477                     else {
 478                         return Some(0);
 479                     }
 480                 }
 481                 Less => {
 482                     if midpoint + 1 < self.elts.len() {
 483                         if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
 484                             return Some(midpoint);
 485                         }
 486                         else {
 487                             let tmp = midpoint;
 488                             midpoint = (high - midpoint) / 2;
 489                             low = tmp;
 490                         }
 491                     }
 492                     else {
 493                         return Some(self.elts.len());
 494                     }
 495                 }
 496             }
 497         }
 498     }
 499 }
 500
 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);
 507             match order {
 508                 Less => return s.left.get(k),
 509                 Equal => return Some(s.value.clone()),
 510                 _ => {}
 511             }
 512         }
 513         self.rightmost_child.get(k)
 514     }
 515
 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() {
 524             None => {
 525                 return (Node::new_branch(self.clone().elts,
 526                                          self.clone().rightmost_child),
 527                         outcome);
 528             }
 529             _ => {
 530                 if index.unwrap() == self.elts.len() {
 531                     let new_outcome = self.clone().rightmost_child.insert(k.clone(),
 532                                                                        v.clone(),
 533                                                                        ub.clone());
 534                     new_branch = new_outcome.clone().val0();
 535                     outcome = new_outcome.val1();
 536                 }
 537                 else {
 538                     let new_outcome = self.elts.get(index.unwrap()).left.clone().insert(k.clone(),
 539                                                                                  v.clone(),
 540                                                                                  ub.clone());
 541                     new_branch = new_outcome.clone().val0();
 542                     outcome = new_outcome.val1();
 543                 }
 544                 //Check to see whether a branch or a leaf was returned from the
 545                 //tree traversal.
 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.
 549                     LeafNode(..) => {
 550                         if index.unwrap() == self.elts.len() {
 551                             self.rightmost_child = box new_branch.clone();
 552                         }
 553                         else {
 554                             self.elts.get_mut(index.unwrap()).left = box new_branch.clone();
 555                         }
 556                         return (Node::new_branch(self.clone().elts,
 557                                                  self.clone().rightmost_child),
 558                                 true);
 559                     }
 560                     //If we have a branch, we might need to refactor the tree.
 561                     BranchNode(..) => {}
 562                 }
 563             }
 564         }
 565         //If we inserted something into the tree, do the following:
 566         if outcome {
 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.
 570                 LeafNode(..) => {
 571                     if index.unwrap() == self.elts.len() {
 572                         self.rightmost_child = box new_branch;
 573                     }
 574                     else {
 575                         self.elts.get_mut(index.unwrap()).left = box new_branch;
 576                     }
 577                     return (Node::new_branch(self.clone().elts,
 578                                              self.clone().rightmost_child),
 579                             true);
 580                 }
 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 {
 587                         None => {
 588                             return (Node::new_branch(self.clone().elts,
 589                                                      self.clone().rightmost_child),
 590                                     false);
 591                             }
 592                         _ => {
 593                             self.elts.insert(new_elt_index.unwrap(), new_elt);
 594                             if new_elt_index.unwrap() + 1 >= self.elts.len() {
 595                                 self.rightmost_child = branch.clone().rightmost_child;
 596                             }
 597                             else {
 598                                 self.elts.get_mut(new_elt_index.unwrap() + 1).left =
 599                                     branch.clone().rightmost_child;
 600                             }
 601                         }
 602                     }
 603                 }
 604             }
 605             //If the current node is overfilled, create a new branch with one element
 606             //and two children.
 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)
 611                                                                         == Greater);
 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);
 619             }
 620         }
 621         (Node::new_branch(self.elts.clone(), self.rightmost_child.clone()), outcome)
 622     }
 623 }
 624
 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())
 629     }
 630 }
 631
 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
 635     }
 636 }
 637
 638 impl<K: Ord, V: Eq> Eq for Branch<K, V> {}
 639
 640 impl<K: Ord, V: Eq> PartialOrd for Branch<K, V> {
 641     fn lt(&self, other: &Branch<K, V>) -> bool {
 642         self.cmp(other) == Less
 643     }
 644 }
 645
 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() {
 650             return Greater;
 651         }
 652         if self.elts.len() < other.elts.len() {
 653             return Less;
 654         }
 655         self.elts.get(0).cmp(other.elts.get(0))
 656     }
 657 }
 658
 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))
 665         }
 666         write!(f, " // rightmost child: ({}) ", *self.rightmost_child)
 667     }
 668 }
 669
 670 //A LeafElt contains no left child, but a key-value pair.
 671 struct LeafElt<K, V> {
 672     key: K,
 673     value: V
 674 }
 675
 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>>,
 679     key: K,
 680     value: V
 681 }
 682
 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> {
 686         LeafElt {
 687             key: k,
 688             value: v
 689         }
 690     }
 691 }
 692
 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())
 697     }
 698 }
 699
 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
 703     }
 704 }
 705
 706 impl<K: Ord, V: Eq> Eq for LeafElt<K, V> {}
 707
 708 impl<K: Ord, V: Eq> PartialOrd for LeafElt<K, V> {
 709     fn lt(&self, other: &LeafElt<K, V>) -> bool {
 710         self.cmp(other) == Less
 711     }
 712 }
 713
 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)
 718     }
 719 }
 720
 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)
 725     }
 726 }
 727
 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> {
 731         BranchElt {
 732             left: n,
 733             key: k,
 734             value: v
 735         }
 736     }
 737 }
 738
 739
 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(),
 744                        self.value.clone(),
 745                        self.left.clone())
 746     }
 747 }
 748
 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
 752     }
 753 }
 754
 755 impl<K: Ord, V: Eq> Eq for BranchElt<K, V>{}
 756
 757 impl<K: Ord, V: Eq> PartialOrd for BranchElt<K, V> {
 758     fn lt(&self, other: &BranchElt<K, V>) -> bool {
 759         self.cmp(other) == Less
 760     }
 761 }
 762
 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)
 767     }
 768 }
 769
 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)
 776     }
 777 }
 778
 779 #[cfg(test)]
 780 mod test_btree {
 781     use std::prelude::*;
 782
 783     use super::{BTree, Node, LeafElt};
 784
 785     //Tests the functionality of the insert methods (which are unfinished).
 786     #[test]
 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         //println!("{}", is_insert.clone().to_str());
 791         assert!(is_insert.root.is_leaf());
 792     }
 793
 794     #[test]
 795     fn insert_test_two() {
 796         let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
 797         let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
 798         let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
 799         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3));
 800         let b = BTree::new_with_node_len(n, 3, 2);
 801         //println!("{}", b.clone().insert(4, "ddd".to_string()).to_str());
 802         assert!(b.insert(4, "ddd".to_string()).root.is_leaf());
 803     }
 804
 805     #[test]
 806     fn insert_test_three() {
 807         let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
 808         let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
 809         let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
 810         let leaf_elt_4 = LeafElt::new(4i, "ddd".to_string());
 811         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 812         let b = BTree::new_with_node_len(n, 3, 2);
 813         //println!("{}", b.clone().insert(5, "eee".to_string()).to_str());
 814         assert!(!b.insert(5, "eee".to_string()).root.is_leaf());
 815     }
 816
 817     #[test]
 818     fn insert_test_four() {
 819         let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
 820         let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
 821         let leaf_elt_3 = LeafElt::new(3i, "ccc".to_string());
 822         let leaf_elt_4 = LeafElt::new(4i, "ddd".to_string());
 823         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 824         let mut b = BTree::new_with_node_len(n, 3, 2);
 825         b = b.clone().insert(5, "eee".to_string());
 826         b = b.clone().insert(6, "fff".to_string());
 827         b = b.clone().insert(7, "ggg".to_string());
 828         b = b.clone().insert(8, "hhh".to_string());
 829         b = b.clone().insert(0, "omg".to_string());
 830         //println!("{}", b.clone().to_str());
 831         assert!(!b.root.is_leaf());
 832     }
 833
 834     #[test]
 835     fn bsearch_test_one() {
 836         let b = BTree::new(1i, "abc".to_string(), 2u);
 837         assert_eq!(Some(1), b.root.bsearch_node(2));
 838     }
 839
 840     #[test]
 841     fn bsearch_test_two() {
 842         let b = BTree::new(1i, "abc".to_string(), 2u);
 843         assert_eq!(Some(0), b.root.bsearch_node(0));
 844     }
 845
 846     #[test]
 847     fn bsearch_test_three() {
 848         let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
 849         let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
 850         let leaf_elt_3 = LeafElt::new(4i, "ccc".to_string());
 851         let leaf_elt_4 = LeafElt::new(5i, "ddd".to_string());
 852         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 853         let b = BTree::new_with_node_len(n, 3, 2);
 854         assert_eq!(Some(2), b.root.bsearch_node(3));
 855     }
 856
 857     #[test]
 858     fn bsearch_test_four() {
 859         let leaf_elt_1 = LeafElt::new(1i, "aaa".to_string());
 860         let leaf_elt_2 = LeafElt::new(2i, "bbb".to_string());
 861         let leaf_elt_3 = LeafElt::new(4i, "ccc".to_string());
 862         let leaf_elt_4 = LeafElt::new(5i, "ddd".to_string());
 863         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 864         let b = BTree::new_with_node_len(n, 3, 2);
 865         assert_eq!(Some(4), b.root.bsearch_node(800));
 866     }
 867
 868     //Tests the functionality of the get method.
 869     #[test]
 870     fn get_test() {
 871         let b = BTree::new(1i, "abc".to_string(), 2);
 872         let val = b.get(1);
 873         assert_eq!(val, Some("abc".to_string()));
 874     }
 875
 876     //Tests the BTree's clone() method.
 877     #[test]
 878     fn btree_clone_test() {
 879         let b = BTree::new(1i, "abc".to_string(), 2);
 880         let b2 = b.clone();
 881         assert!(b.root == b2.root)
 882     }
 883
 884     //Tests the BTree's cmp() method when one node is "less than" another.
 885     #[test]
 886     fn btree_cmp_test_less() {
 887         let b = BTree::new(1i, "abc".to_string(), 2);
 888         let b2 = BTree::new(2i, "bcd".to_string(), 2);
 889         assert!(&b.cmp(&b2) == &Less)
 890     }
 891
 892     //Tests the BTree's cmp() method when two nodes are equal.
 893     #[test]
 894     fn btree_cmp_test_eq() {
 895         let b = BTree::new(1i, "abc".to_string(), 2);
 896         let b2 = BTree::new(1i, "bcd".to_string(), 2);
 897         assert!(&b.cmp(&b2) == &Equal)
 898     }
 899
 900     //Tests the BTree's cmp() method when one node is "greater than" another.
 901     #[test]
 902     fn btree_cmp_test_greater() {
 903         let b = BTree::new(1i, "abc".to_string(), 2);
 904         let b2 = BTree::new(2i, "bcd".to_string(), 2);
 905         assert!(&b2.cmp(&b) == &Greater)
 906     }
 907
 908     //Tests the BTree's to_str() method.
 909     #[test]
 910     fn btree_tostr_test() {
 911         let b = BTree::new(1i, "abc".to_string(), 2);
 912         assert_eq!(b.to_str(), "Key: 1, value: abc;".to_string())
 913     }
 914
 915 }