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 std::fmt;
  22 use std::fmt::Show;
  23
  24 #[allow(missing_doc)]
  25 pub struct BTree<K, V> {
  26     root: Node<K, V>,
  27     len: uint,
  28     lower_bound: uint,
  29     upper_bound: uint
  30 }
  31
  32 impl<K: TotalOrd, V> BTree<K, V> {
  33
  34     ///Returns new BTree with root node (leaf) and user-supplied lower bound
  35     ///The lower bound applies to every node except the root node.
  36     pub fn new(k: K, v: V, lb: uint) -> BTree<K, V> {
  37         BTree {
  38             root: Node::new_leaf(vec!(LeafElt::new(k, v))),
  39             len: 1,
  40             lower_bound: lb,
  41             upper_bound: 2 * lb
  42         }
  43     }
  44
  45     ///Helper function for clone: returns new BTree with supplied root node,
  46     ///length, and lower bound.  For use when the length is known already.
  47     fn new_with_node_len(n: Node<K, V>,
  48                          length: uint,
  49                          lb: uint) -> BTree<K, V> {
  50         BTree {
  51             root: n,
  52             len: length,
  53             lower_bound: lb,
  54             upper_bound: 2 * lb
  55         }
  56     }
  57 }
  58
  59 //We would probably want to remove the dependence on the Clone trait in the future.
  60 //It is here as a crutch to ensure values can be passed around through the tree's nodes
  61 //especially during insertions and deletions.
  62 impl<K: Clone + TotalOrd, V: Clone> BTree<K, V> {
  63     ///Returns the value of a given key, which may not exist in the tree.
  64     ///Calls the root node's get method.
  65     pub fn get(self, k: K) -> Option<V> {
  66         return self.root.get(k);
  67     }
  68
  69     ///An insert method that uses the clone() feature for support.
  70     pub fn insert(mut self, k: K, v: V) -> BTree<K, V> {
  71         let (a, b) = self.root.clone().insert(k, v, self.upper_bound.clone());
  72         if b {
  73             match a.clone() {
  74                 LeafNode(leaf) => {
  75                     self.root = Node::new_leaf(leaf.clone().elts);
  76                 }
  77                 BranchNode(branch) => {
  78                     self.root = Node::new_branch(branch.clone().elts,
  79                                                  branch.clone().rightmost_child);
  80                 }
  81             }
  82         }
  83         self
  84     }
  85 }
  86
  87 impl<K: Clone + TotalOrd, V: Clone> Clone for BTree<K, V> {
  88     ///Implements the Clone trait for the BTree.
  89     ///Uses a helper function/constructor to produce a new BTree.
  90     fn clone(&self) -> BTree<K, V> {
  91         BTree::new_with_node_len(self.root.clone(), self.len, self.lower_bound)
  92     }
  93 }
  94
  95 impl<K: TotalOrd, V: TotalEq> Eq for BTree<K, V> {
  96     fn eq(&self, other: &BTree<K, V>) -> bool {
  97         self.root.cmp(&other.root) == Equal
  98     }
  99 }
 100
 101 impl<K: TotalOrd, V: TotalEq> TotalEq for BTree<K, V> {}
 102
 103 impl<K: TotalOrd, V: TotalEq> Ord for BTree<K, V> {
 104     fn lt(&self, other: &BTree<K, V>) -> bool {
 105         self.cmp(other) == Less
 106     }
 107 }
 108
 109 impl<K: TotalOrd, V: TotalEq> TotalOrd for BTree<K, V> {
 110     ///Returns an ordering based on the root nodes of each BTree.
 111     fn cmp(&self, other: &BTree<K, V>) -> Ordering {
 112         self.root.cmp(&other.root)
 113     }
 114 }
 115
 116 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for BTree<K, V> {
 117     ///Returns a string representation of the BTree
 118     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 119         self.root.fmt(f)
 120     }
 121 }
 122
 123
 124 //Node types
 125 //A node is either a LeafNode or a BranchNode, which contain either a Leaf or a Branch.
 126 //Branches contain BranchElts, which contain a left child (another node) and a key-value
 127 //pair.  Branches also contain the rightmost child of the elements in the array.
 128 //Leaves contain LeafElts, which do not have children.
 129 enum Node<K, V> {
 130     LeafNode(Leaf<K, V>),
 131     BranchNode(Branch<K, V>)
 132 }
 133
 134
 135 //Node functions/methods
 136 impl<K: TotalOrd, V> Node<K, V> {
 137     ///Creates a new leaf node given a vector of elements.
 138     fn new_leaf(vec: Vec<LeafElt<K, V>>) -> Node<K,V> {
 139         LeafNode(Leaf::new(vec))
 140     }
 141
 142     ///Creates a new branch node given a vector of an elements and a pointer to a rightmost child.
 143     fn new_branch(vec: Vec<BranchElt<K, V>>, right: ~Node<K, V>) -> Node<K, V> {
 144         BranchNode(Branch::new(vec, right))
 145     }
 146
 147     ///Determines whether the given Node contains a Branch or a Leaf.
 148     ///Used in testing.
 149     fn is_leaf(&self) -> bool {
 150         match self {
 151             &LeafNode(..) => true,
 152             &BranchNode(..) => false
 153         }
 154     }
 155
 156     ///A binary search function for Nodes.
 157     ///Calls either the Branch's or the Leaf's bsearch function.
 158     fn bsearch_node(&self, k: K) -> Option<uint> {
 159          match self {
 160              &LeafNode(ref leaf) => leaf.bsearch_leaf(k),
 161              &BranchNode(ref branch) => branch.bsearch_branch(k)
 162          }
 163      }
 164 }
 165
 166 impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
 167     ///Returns the corresponding value to the provided key.
 168     ///get() is called in different ways on a branch or a leaf.
 169     fn get(&self, k: K) -> Option<V> {
 170         match *self {
 171             LeafNode(ref leaf) => return leaf.get(k),
 172             BranchNode(ref branch) => return branch.get(k)
 173         }
 174     }
 175
 176     ///Matches on the Node, then performs and returns the appropriate insert method.
 177     fn insert(self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
 178         match self {
 179             LeafNode(leaf) => leaf.insert(k, v, ub),
 180             BranchNode(branch) => branch.insert(k, v, ub)
 181         }
 182     }
 183 }
 184
 185 impl<K: Clone + TotalOrd, V: Clone> Clone for Node<K, V> {
 186     ///Returns a new node based on whether or not it is a branch or a leaf.
 187     fn clone(&self) -> Node<K, V> {
 188         match *self {
 189             LeafNode(ref leaf) => {
 190                 Node::new_leaf(leaf.elts.clone())
 191             }
 192             BranchNode(ref branch) => {
 193                 Node::new_branch(branch.elts.clone(),
 194                                  branch.rightmost_child.clone())
 195             }
 196         }
 197     }
 198 }
 199
 200 impl<K: TotalOrd, V: TotalEq> Eq for Node<K, V> {
 201     fn eq(&self, other: &Node<K, V>) -> bool {
 202         match *self{
 203             BranchNode(ref branch) => {
 204                 if other.is_leaf() {
 205                     return false;
 206                 }
 207                 match *other {
 208                     BranchNode(ref branch2) => branch.cmp(branch2) == Equal,
 209                     LeafNode(..) => false
 210                 }
 211             }
 212             LeafNode(ref leaf) => {
 213                 match *other {
 214                     LeafNode(ref leaf2) => leaf.cmp(leaf2) == Equal,
 215                     BranchNode(..) => false
 216                 }
 217             }
 218         }
 219     }
 220 }
 221
 222 impl<K: TotalOrd, V: TotalEq> TotalEq for Node<K, V> {}
 223
 224 impl<K: TotalOrd, V: TotalEq> Ord for Node<K, V> {
 225     fn lt(&self, other: &Node<K, V>) -> bool {
 226         self.cmp(other) == Less
 227     }
 228 }
 229
 230 impl<K: TotalOrd, V: TotalEq> TotalOrd for Node<K, V> {
 231     ///Implementation of TotalOrd for Nodes.
 232     fn cmp(&self, other: &Node<K, V>) -> Ordering {
 233         match *self {
 234             LeafNode(ref leaf) => {
 235                 match *other {
 236                     LeafNode(ref leaf2) => leaf.cmp(leaf2),
 237                     BranchNode(_) => Less
 238                 }
 239             }
 240             BranchNode(ref branch) => {
 241                 match *other {
 242                     BranchNode(ref branch2) => branch.cmp(branch2),
 243                     LeafNode(_) => Greater
 244                 }
 245             }
 246         }
 247     }
 248 }
 249
 250 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Node<K, V> {
 251     ///Returns a string representation of a Node.
 252     ///Will iterate over the Node and show "Key: x, value: y, child: () // "
 253     ///for all elements in the Node. "Child" only exists if the Node contains
 254     ///a branch.
 255     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 256         match *self {
 257             LeafNode(ref leaf) => leaf.fmt(f),
 258             BranchNode(ref branch) => branch.fmt(f),
 259         }
 260     }
 261 }
 262
 263
 264 //A leaf is a vector with elements that contain no children.  A leaf also
 265 //does not contain a rightmost child.
 266 struct Leaf<K, V> {
 267     elts: Vec<LeafElt<K, V>>
 268 }
 269
 270 //Vector of values with children, plus a rightmost child (greater than all)
 271 struct Branch<K, V> {
 272     elts: Vec<BranchElt<K,V>>,
 273     rightmost_child: ~Node<K, V>
 274 }
 275
 276
 277 impl<K: TotalOrd, V> Leaf<K, V> {
 278     ///Creates a new Leaf from a vector of LeafElts.
 279     fn new(vec: Vec<LeafElt<K, V>>) -> Leaf<K, V> {
 280         Leaf {
 281             elts: vec
 282         }
 283     }
 284
 285     ///Searches a leaf for a spot for a new element using a binary search.
 286     ///Returns None if the element is already in the vector.
 287     fn bsearch_leaf(&self, k: K) -> Option<uint> {
 288         let mut high: uint = self.elts.len();
 289         let mut low: uint = 0;
 290         let mut midpoint: uint = (high - low) / 2 ;
 291         if midpoint == high {
 292             midpoint = 0;
 293         }
 294         loop {
 295             let order = self.elts.get(midpoint).key.cmp(&k);
 296             match order {
 297                 Equal => {
 298                     return None;
 299                 }
 300                 Greater => {
 301                     if midpoint > 0 {
 302                         if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
 303                             return Some(midpoint);
 304                         }
 305                         else {
 306                             let tmp = midpoint;
 307                             midpoint = midpoint / 2;
 308                             high = tmp;
 309                             continue;
 310                         }
 311                     }
 312                     else {
 313                         return Some(0);
 314                     }
 315                 }
 316                 Less => {
 317                     if midpoint + 1 < self.elts.len() {
 318                         if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
 319                             return Some(midpoint);
 320                         }
 321                         else {
 322                             let tmp = midpoint;
 323                             midpoint = (high + low) / 2;
 324                             low = tmp;
 325                         }
 326                     }
 327                     else {
 328                         return Some(self.elts.len());
 329                     }
 330                 }
 331             }
 332         }
 333     }
 334 }
 335
 336
 337 impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
 338     ///Returns the corresponding value to the supplied key.
 339     fn get(&self, k: K) -> Option<V> {
 340         for s in self.elts.iter() {
 341             let order = s.key.cmp(&k);
 342             match order {
 343                 Equal => return Some(s.value.clone()),
 344                 _ => {}
 345             }
 346         }
 347         return None;
 348     }
 349
 350     ///Uses clone() to facilitate inserting new elements into a tree.
 351     fn insert(mut self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
 352         let to_insert = LeafElt::new(k, v);
 353         let index: Option<uint> = self.bsearch_leaf(to_insert.clone().key);
 354         //Check index to see whether we actually inserted the element into the vector.
 355         match index {
 356             //If the index is None, the new element already exists in the vector.
 357             None => {
 358                 return (Node::new_leaf(self.clone().elts), false);
 359             }
 360             //If there is an index, insert at that index.
 361             _ => {
 362                 if index.unwrap() >= self.elts.len() {
 363                     self.elts.push(to_insert.clone());
 364                 }
 365                 else {
 366                     self.elts.insert(index.unwrap(), to_insert.clone());
 367                 }
 368             }
 369         }
 370         //If we have overfilled the vector (by making its size greater than the
 371         //upper bound), we return a new Branch with one element and two children.
 372         if self.elts.len() > ub {
 373             let midpoint_opt = self.elts.remove(ub / 2);
 374             let midpoint = midpoint_opt.unwrap();
 375             let (left_leaf, right_leaf) = self.elts.partition(|le|
 376                                                               le.key.cmp(&midpoint.key.clone())
 377                                                               == Less);
 378             let branch_return = Node::new_branch(vec!(BranchElt::new(midpoint.key.clone(),
 379                                                                   midpoint.value.clone(),
 380                                                              ~Node::new_leaf(left_leaf))),
 381                                             ~Node::new_leaf(right_leaf));
 382             return (branch_return, true);
 383         }
 384         (Node::new_leaf(self.elts.clone()), true)
 385     }
 386 }
 387
 388 impl<K: Clone + TotalOrd, V: Clone> Clone for Leaf<K, V> {
 389     ///Returns a new Leaf with the same elts.
 390     fn clone(&self) -> Leaf<K, V> {
 391         Leaf::new(self.elts.clone())
 392     }
 393 }
 394
 395 impl<K: TotalOrd, V: TotalEq> Eq for Leaf<K, V> {
 396     fn eq(&self, other: &Leaf<K, V>) -> bool {
 397         self.elts == other.elts
 398     }
 399 }
 400
 401 impl<K: TotalOrd, V: TotalEq> TotalEq for Leaf<K, V> {}
 402
 403 impl<K: TotalOrd, V: TotalEq> Ord for Leaf<K, V> {
 404     fn lt(&self, other: &Leaf<K, V>) -> bool {
 405         self.cmp(other) == Less
 406     }
 407 }
 408
 409 impl<K: TotalOrd, V: TotalEq> TotalOrd for Leaf<K, V> {
 410     ///Returns an ordering based on the first element of each Leaf.
 411     fn cmp(&self, other: &Leaf<K, V>) -> Ordering {
 412         if self.elts.len() > other.elts.len() {
 413             return Greater;
 414         }
 415         if self.elts.len() < other.elts.len() {
 416             return Less;
 417         }
 418         self.elts.get(0).cmp(other.elts.get(0))
 419     }
 420 }
 421
 422
 423 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Leaf<K, V> {
 424     ///Returns a string representation of a Leaf.
 425     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 426         for (i, s) in self.elts.iter().enumerate() {
 427             if i != 0 { try!(write!(f.buf, " // ")) }
 428             try!(write!(f.buf, "{}", *s))
 429         }
 430         Ok(())
 431     }
 432 }
 433
 434
 435 impl<K: TotalOrd, V> Branch<K, V> {
 436     ///Creates a new Branch from a vector of BranchElts and a rightmost child (a node).
 437     fn new(vec: Vec<BranchElt<K, V>>, right: ~Node<K, V>) -> Branch<K, V> {
 438         Branch {
 439             elts: vec,
 440             rightmost_child: right
 441         }
 442     }
 443
 444     fn bsearch_branch(&self, k: K) -> Option<uint> {
 445         let mut midpoint: uint = self.elts.len() / 2;
 446         let mut high: uint = self.elts.len();
 447         let mut low: uint = 0u;
 448         if midpoint == high {
 449             midpoint = 0u;
 450         }
 451         loop {
 452             let order = self.elts.get(midpoint).key.cmp(&k);
 453             match order {
 454                 Equal => {
 455                     return None;
 456                 }
 457                 Greater => {
 458                     if midpoint > 0 {
 459                         if self.elts.get(midpoint - 1).key.cmp(&k) == Less {
 460                             return Some(midpoint);
 461                         }
 462                         else {
 463                             let tmp = midpoint;
 464                             midpoint = (midpoint - low) / 2;
 465                             high = tmp;
 466                             continue;
 467                         }
 468                     }
 469                     else {
 470                         return Some(0);
 471                     }
 472                 }
 473                 Less => {
 474                     if midpoint + 1 < self.elts.len() {
 475                         if self.elts.get(midpoint + 1).key.cmp(&k) == Greater {
 476                             return Some(midpoint);
 477                         }
 478                         else {
 479                             let tmp = midpoint;
 480                             midpoint = (high - midpoint) / 2;
 481                             low = tmp;
 482                         }
 483                     }
 484                     else {
 485                         return Some(self.elts.len());
 486                     }
 487                 }
 488             }
 489         }
 490     }
 491 }
 492
 493 impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
 494     ///Returns the corresponding value to the supplied key.
 495     ///If the key is not there, find the child that might hold it.
 496     fn get(&self, k: K) -> Option<V> {
 497         for s in self.elts.iter() {
 498             let order = s.key.cmp(&k);
 499             match order {
 500                 Less => return s.left.get(k),
 501                 Equal => return Some(s.value.clone()),
 502                 _ => {}
 503             }
 504         }
 505         self.rightmost_child.get(k)
 506     }
 507
 508     ///An insert method that uses .clone() for support.
 509     fn insert(mut self, k: K, v: V, ub: uint) -> (Node<K, V>, bool) {
 510         let mut new_branch = Node::new_branch(self.clone().elts, self.clone().rightmost_child);
 511         let mut outcome = false;
 512         let index: Option<uint> = new_branch.bsearch_node(k.clone());
 513         //First, find which path down the tree will lead to the appropriate leaf
 514         //for the key-value pair.
 515         match index.clone() {
 516             None => {
 517                 return (Node::new_branch(self.clone().elts,
 518                                          self.clone().rightmost_child),
 519                         outcome);
 520             }
 521             _ => {
 522                 if index.unwrap() == self.elts.len() {
 523                     let new_outcome = self.clone().rightmost_child.insert(k.clone(),
 524                                                                        v.clone(),
 525                                                                        ub.clone());
 526                     new_branch = new_outcome.clone().val0();
 527                     outcome = new_outcome.val1();
 528                 }
 529                 else {
 530                     let new_outcome = self.elts.get(index.unwrap()).left.clone().insert(k.clone(),
 531                                                                                  v.clone(),
 532                                                                                  ub.clone());
 533                     new_branch = new_outcome.clone().val0();
 534                     outcome = new_outcome.val1();
 535                 }
 536                 //Check to see whether a branch or a leaf was returned from the
 537                 //tree traversal.
 538                 match new_branch.clone() {
 539                     //If we have a leaf, we do not need to resize the tree,
 540                     //so we can return false.
 541                     LeafNode(..) => {
 542                         if index.unwrap() == self.elts.len() {
 543                             self.rightmost_child = ~new_branch.clone();
 544                         }
 545                         else {
 546                             self.elts.get_mut(index.unwrap()).left = ~new_branch.clone();
 547                         }
 548                         return (Node::new_branch(self.clone().elts,
 549                                                  self.clone().rightmost_child),
 550                                 true);
 551                     }
 552                     //If we have a branch, we might need to refactor the tree.
 553                     BranchNode(..) => {}
 554                 }
 555             }
 556         }
 557         //If we inserted something into the tree, do the following:
 558         if outcome {
 559             match new_branch.clone() {
 560                 //If we have a new leaf node, integrate it into the current branch
 561                 //and return it, saying we have inserted a new element.
 562                 LeafNode(..) => {
 563                     if index.unwrap() == self.elts.len() {
 564                         self.rightmost_child = ~new_branch;
 565                     }
 566                     else {
 567                         self.elts.get_mut(index.unwrap()).left = ~new_branch;
 568                     }
 569                     return (Node::new_branch(self.clone().elts,
 570                                              self.clone().rightmost_child),
 571                             true);
 572                 }
 573                 //If we have a new branch node, attempt to insert it into the tree
 574                 //as with the key-value pair, then check to see if the node is overfull.
 575                 BranchNode(branch) => {
 576                     let new_elt = branch.elts.get(0).clone();
 577                     let new_elt_index = self.bsearch_branch(new_elt.clone().key);
 578                     match new_elt_index {
 579                         None => {
 580                             return (Node::new_branch(self.clone().elts,
 581                                                      self.clone().rightmost_child),
 582                                     false);
 583                             }
 584                         _ => {
 585                             self.elts.insert(new_elt_index.unwrap(), new_elt);
 586                             if new_elt_index.unwrap() + 1 >= self.elts.len() {
 587                                 self.rightmost_child = branch.clone().rightmost_child;
 588                             }
 589                             else {
 590                                 self.elts.get_mut(new_elt_index.unwrap() + 1).left =
 591                                     branch.clone().rightmost_child;
 592                             }
 593                         }
 594                     }
 595                 }
 596             }
 597             //If the current node is overfilled, create a new branch with one element
 598             //and two children.
 599             if self.elts.len() > ub {
 600                 let midpoint = self.elts.remove(ub / 2).unwrap();
 601                 let (new_left, new_right) = self.clone().elts.partition(|le|
 602                                                                 midpoint.key.cmp(&le.key)
 603                                                                         == Greater);
 604                 new_branch = Node::new_branch(
 605                     vec!(BranchElt::new(midpoint.clone().key,
 606                                      midpoint.clone().value,
 607                                      ~Node::new_branch(new_left,
 608                                                        midpoint.clone().left))),
 609                     ~Node::new_branch(new_right, self.clone().rightmost_child));
 610                 return (new_branch, true);
 611             }
 612         }
 613         (Node::new_branch(self.elts.clone(), self.rightmost_child.clone()), outcome)
 614     }
 615 }
 616
 617 impl<K: Clone + TotalOrd, V: Clone> Clone for Branch<K, V> {
 618     ///Returns a new branch using the clone methods of the Branch's internal variables.
 619     fn clone(&self) -> Branch<K, V> {
 620         Branch::new(self.elts.clone(), self.rightmost_child.clone())
 621     }
 622 }
 623
 624 impl<K: TotalOrd, V: TotalEq> Eq for Branch<K, V> {
 625     fn eq(&self, other: &Branch<K, V>) -> bool {
 626         self.elts == other.elts
 627     }
 628 }
 629
 630 impl<K: TotalOrd, V: TotalEq> TotalEq for Branch<K, V> {}
 631
 632 impl<K: TotalOrd, V: TotalEq> Ord for Branch<K, V> {
 633     fn lt(&self, other: &Branch<K, V>) -> bool {
 634         self.cmp(other) == Less
 635     }
 636 }
 637
 638 impl<K: TotalOrd, V: TotalEq> TotalOrd for Branch<K, V> {
 639     ///Compares the first elements of two branches to determine an ordering
 640     fn cmp(&self, other: &Branch<K, V>) -> Ordering {
 641         if self.elts.len() > other.elts.len() {
 642             return Greater;
 643         }
 644         if self.elts.len() < other.elts.len() {
 645             return Less;
 646         }
 647         self.elts.get(0).cmp(other.elts.get(0))
 648     }
 649 }
 650
 651 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Branch<K, V> {
 652     ///Returns a string representation of a Branch.
 653     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 654         for (i, s) in self.elts.iter().enumerate() {
 655             if i != 0 { try!(write!(f.buf, " // ")) }
 656             try!(write!(f.buf, "{}", *s))
 657         }
 658         write!(f.buf, " // rightmost child: ({}) ", *self.rightmost_child)
 659     }
 660 }
 661
 662 //A LeafElt containts no left child, but a key-value pair.
 663 struct LeafElt<K, V> {
 664     key: K,
 665     value: V
 666 }
 667
 668 //A BranchElt has a left child in insertition to a key-value pair.
 669 struct BranchElt<K, V> {
 670     left: ~Node<K, V>,
 671     key: K,
 672     value: V
 673 }
 674
 675 impl<K: TotalOrd, V> LeafElt<K, V> {
 676     ///Creates a new LeafElt from a supplied key-value pair.
 677     fn new(k: K, v: V) -> LeafElt<K, V> {
 678         LeafElt {
 679             key: k,
 680             value: v
 681         }
 682     }
 683 }
 684
 685 impl<K: Clone + TotalOrd, V: Clone> Clone for LeafElt<K, V> {
 686     ///Returns a new LeafElt by cloning the key and value.
 687     fn clone(&self) -> LeafElt<K, V> {
 688         LeafElt::new(self.key.clone(), self.value.clone())
 689     }
 690 }
 691
 692 impl<K: TotalOrd, V: TotalEq> Eq for LeafElt<K, V> {
 693     fn eq(&self, other: &LeafElt<K, V>) -> bool {
 694         self.key == other.key && self.value == other.value
 695     }
 696 }
 697
 698 impl<K: TotalOrd, V: TotalEq> TotalEq for LeafElt<K, V> {}
 699
 700 impl<K: TotalOrd, V: TotalEq> Ord for LeafElt<K, V> {
 701     fn lt(&self, other: &LeafElt<K, V>) -> bool {
 702         self.cmp(other) == Less
 703     }
 704 }
 705
 706 impl<K: TotalOrd, V: TotalEq> TotalOrd for LeafElt<K, V> {
 707     ///Returns an ordering based on the keys of the LeafElts.
 708     fn cmp(&self, other: &LeafElt<K, V>) -> Ordering {
 709         self.key.cmp(&other.key)
 710     }
 711 }
 712
 713 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for LeafElt<K, V> {
 714     ///Returns a string representation of a LeafElt.
 715     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 716         write!(f.buf, "Key: {}, value: {};", self.key, self.value)
 717     }
 718 }
 719
 720 impl<K: TotalOrd, V> BranchElt<K, V> {
 721     ///Creates a new BranchElt from a supplied key, value, and left child.
 722     fn new(k: K, v: V, n: ~Node<K, V>) -> BranchElt<K, V> {
 723         BranchElt {
 724             left: n,
 725             key: k,
 726             value: v
 727         }
 728     }
 729 }
 730
 731
 732 impl<K: Clone + TotalOrd, V: Clone> Clone for BranchElt<K, V> {
 733     ///Returns a new BranchElt by cloning the key, value, and left child.
 734     fn clone(&self) -> BranchElt<K, V> {
 735         BranchElt::new(self.key.clone(),
 736                        self.value.clone(),
 737                        self.left.clone())
 738     }
 739 }
 740
 741 impl<K: TotalOrd, V: TotalEq> Eq for BranchElt<K, V>{
 742     fn eq(&self, other: &BranchElt<K, V>) -> bool {
 743         self.key == other.key && self.value == other.value
 744     }
 745 }
 746
 747 impl<K: TotalOrd, V: TotalEq> TotalEq for BranchElt<K, V>{}
 748
 749 impl<K: TotalOrd, V: TotalEq> Ord for BranchElt<K, V> {
 750     fn lt(&self, other: &BranchElt<K, V>) -> bool {
 751         self.cmp(other) == Less
 752     }
 753 }
 754
 755 impl<K: TotalOrd, V: TotalEq> TotalOrd for BranchElt<K, V> {
 756     ///Fulfills TotalOrd for BranchElts
 757     fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
 758         self.key.cmp(&other.key)
 759     }
 760 }
 761
 762 impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for BranchElt<K, V> {
 763     /// Returns string containing key, value, and child (which should recur to a
 764     /// leaf) Consider changing in future to be more readable.
 765     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 766         write!(f.buf, "Key: {}, value: {}, (child: {})",
 767                self.key, self.value, *self.left)
 768     }
 769 }
 770
 771 #[cfg(test)]
 772 mod test_btree {
 773
 774     use super::{BTree, Node, LeafElt};
 775
 776     //Tests the functionality of the insert methods (which are unfinished).
 777     #[test]
 778     fn insert_test_one() {
 779         let b = BTree::new(1, ~"abc", 2);
 780         let is_insert = b.insert(2, ~"xyz");
 781         //println!("{}", is_insert.clone().to_str());
 782         assert!(is_insert.root.is_leaf());
 783     }
 784
 785     #[test]
 786     fn insert_test_two() {
 787         let leaf_elt_1 = LeafElt::new(1, ~"aaa");
 788         let leaf_elt_2 = LeafElt::new(2, ~"bbb");
 789         let leaf_elt_3 = LeafElt::new(3, ~"ccc");
 790         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3));
 791         let b = BTree::new_with_node_len(n, 3, 2);
 792         //println!("{}", b.clone().insert(4, ~"ddd").to_str());
 793         assert!(b.insert(4, ~"ddd").root.is_leaf());
 794     }
 795
 796     #[test]
 797     fn insert_test_three() {
 798         let leaf_elt_1 = LeafElt::new(1, ~"aaa");
 799         let leaf_elt_2 = LeafElt::new(2, ~"bbb");
 800         let leaf_elt_3 = LeafElt::new(3, ~"ccc");
 801         let leaf_elt_4 = LeafElt::new(4, ~"ddd");
 802         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 803         let b = BTree::new_with_node_len(n, 3, 2);
 804         //println!("{}", b.clone().insert(5, ~"eee").to_str());
 805         assert!(!b.insert(5, ~"eee").root.is_leaf());
 806     }
 807
 808     #[test]
 809     fn insert_test_four() {
 810         let leaf_elt_1 = LeafElt::new(1, ~"aaa");
 811         let leaf_elt_2 = LeafElt::new(2, ~"bbb");
 812         let leaf_elt_3 = LeafElt::new(3, ~"ccc");
 813         let leaf_elt_4 = LeafElt::new(4, ~"ddd");
 814         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 815         let mut b = BTree::new_with_node_len(n, 3, 2);
 816         b = b.clone().insert(5, ~"eee");
 817         b = b.clone().insert(6, ~"fff");
 818         b = b.clone().insert(7, ~"ggg");
 819         b = b.clone().insert(8, ~"hhh");
 820         b = b.clone().insert(0, ~"omg");
 821         //println!("{}", b.clone().to_str());
 822         assert!(!b.root.is_leaf());
 823     }
 824
 825     #[test]
 826     fn bsearch_test_one() {
 827         let b = BTree::new(1, ~"abc", 2);
 828         assert_eq!(Some(1), b.root.bsearch_node(2));
 829     }
 830
 831     #[test]
 832     fn bsearch_test_two() {
 833         let b = BTree::new(1, ~"abc", 2);
 834         assert_eq!(Some(0), b.root.bsearch_node(0));
 835     }
 836
 837     #[test]
 838     fn bsearch_test_three() {
 839         let leaf_elt_1 = LeafElt::new(1, ~"aaa");
 840         let leaf_elt_2 = LeafElt::new(2, ~"bbb");
 841         let leaf_elt_3 = LeafElt::new(4, ~"ccc");
 842         let leaf_elt_4 = LeafElt::new(5, ~"ddd");
 843         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 844         let b = BTree::new_with_node_len(n, 3, 2);
 845         assert_eq!(Some(2), b.root.bsearch_node(3));
 846     }
 847
 848     #[test]
 849     fn bsearch_test_four() {
 850         let leaf_elt_1 = LeafElt::new(1, ~"aaa");
 851         let leaf_elt_2 = LeafElt::new(2, ~"bbb");
 852         let leaf_elt_3 = LeafElt::new(4, ~"ccc");
 853         let leaf_elt_4 = LeafElt::new(5, ~"ddd");
 854         let n = Node::new_leaf(vec!(leaf_elt_1, leaf_elt_2, leaf_elt_3, leaf_elt_4));
 855         let b = BTree::new_with_node_len(n, 3, 2);
 856         assert_eq!(Some(4), b.root.bsearch_node(800));
 857     }
 858
 859     //Tests the functionality of the get method.
 860     #[test]
 861     fn get_test() {
 862         let b = BTree::new(1, ~"abc", 2);
 863         let val = b.get(1);
 864         assert_eq!(val, Some(~"abc"));
 865     }
 866
 867     //Tests the BTree's clone() method.
 868     #[test]
 869     fn btree_clone_test() {
 870         let b = BTree::new(1, ~"abc", 2);
 871         let b2 = b.clone();
 872         assert!(b.root == b2.root)
 873     }
 874
 875     //Tests the BTree's cmp() method when one node is "less than" another.
 876     #[test]
 877     fn btree_cmp_test_less() {
 878         let b = BTree::new(1, ~"abc", 2);
 879         let b2 = BTree::new(2, ~"bcd", 2);
 880         assert!(&b.cmp(&b2) == &Less)
 881     }
 882
 883     //Tests the BTree's cmp() method when two nodes are equal.
 884     #[test]
 885     fn btree_cmp_test_eq() {
 886         let b = BTree::new(1, ~"abc", 2);
 887         let b2 = BTree::new(1, ~"bcd", 2);
 888         assert!(&b.cmp(&b2) == &Equal)
 889     }
 890
 891     //Tests the BTree's cmp() method when one node is "greater than" another.
 892     #[test]
 893     fn btree_cmp_test_greater() {
 894         let b = BTree::new(1, ~"abc", 2);
 895         let b2 = BTree::new(2, ~"bcd", 2);
 896         assert!(&b2.cmp(&b) == &Greater)
 897     }
 898
 899     //Tests the BTree's to_str() method.
 900     #[test]
 901     fn btree_tostr_test() {
 902         let b = BTree::new(1, ~"abc", 2);
 903         assert_eq!(b.to_str(), ~"Key: 1, value: abc;")
 904     }
 905
 906 }