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