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 }
libcollections/btree.rs:266:38-266:38 -struct- definition:
//does not contain a rightmost child.
struct Leaf<K, V> {
elts: Vec<LeafElt<K, V>>
references:- 15280: fn new(vec: Vec<LeafElt<K, V>>) -> Leaf<K, V> {
281: Leaf {
282: elts: vec
--
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() {
--
424: impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Leaf<K, V> {
425: ///Returns a string representation of a Leaf.
libcollections/btree.rs:670:65-670:65 -struct- definition:
//A BranchElt has a left child in insertion to a key-value pair.
struct BranchElt<K, V> {
left: Box<Node<K, V>>,
references:- 16724: fn new(k: K, v: V, n: Box<Node<K, V>>) -> BranchElt<K, V> {
725: BranchElt {
726: left: n,
--
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
--
758: ///Fulfills TotalOrd for BranchElts
759: fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
760: self.key.cmp(&other.key)
--
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
libcollections/btree.rs:271:76-271:76 -struct- definition:
//Vector of values with children, plus a rightmost child (greater than all)
struct Branch<K, V> {
elts: Vec<BranchElt<K,V>>,
references:- 15439: -> Branch<K, V> {
440: Branch {
441: elts: vec,
--
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() {
--
653: impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Branch<K, V> {
654: ///Returns a string representation of a Branch.
libcollections/btree.rs:24:22-24:22 -struct- definition:
pub struct BTree<K, V> {
root: Node<K, V>,
len: uint,
references:- 1736: pub fn new(k: K, v: V, lb: uint) -> BTree<K, V> {
37: BTree {
38: root: Node::new_leaf(vec!(LeafElt::new(k, v))),
--
49: lb: uint) -> BTree<K, V> {
50: BTree {
51: root: n,
--
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());
--
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)
--
116: impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for BTree<K, V> {
117: ///Returns a string representation of the BTree
libcollections/btree.rs:664:58-664:58 -struct- definition:
//A LeafElt contains no left child, but a key-value pair.
struct LeafElt<K, V> {
key: K,
references:- 16679: fn new(k: K, v: V) -> LeafElt<K, V> {
680: LeafElt {
681: key: k,
--
708: impl<K: TotalOrd, V: TotalEq> TotalOrd for LeafElt<K, V> {
709: ///Returns an ordering based on the keys of the LeafElts.
--
715: impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for LeafElt<K, V> {
716: ///Returns a string representation of a LeafElt.
libcollections/btree.rs:128:55-128:55 -enum- definition:
//Leaves contain LeafElts, which do not have children.
enum Node<K, V> {
LeafNode(Leaf<K, V>),
references:- 24167: impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
168: ///Returns the corresponding value to the provided key.
--
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);
--
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 {