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