libcollections

1 files changed, 76 insertions, 0 deletions

diff --git a/libcollections/btree/search.rs b/libcollections/btree/search.rs
new file mode 100644
index 0000000..c94b570
--- /dev/null
+++ b/libcollections/btree/search.rs
@@ -0,0 +1,76 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use core::cmp::Ordering;
+
+use borrow::Borrow;
+
+use super::node::{Handle, NodeRef, marker};
+
+use super::node::ForceResult::*;
+use self::SearchResult::*;
+
+pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
+    Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
+    GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>)
+}
+
+pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
+        where Q: Ord, K: Borrow<Q> {
+
+    loop {
+        match search_node(node, key) {
+            Found(handle) => return Found(handle),
+            GoDown(handle) => match handle.force() {
+                Leaf(leaf) => return GoDown(leaf),
+                Internal(internal) => {
+                    node = internal.descend();
+                    continue;
+                }
+            }
+        }
+    }
+}
+
+pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
+    node: NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, Type, Type>
+        where Q: Ord, K: Borrow<Q> {
+
+    match search_linear(&node, key) {
+        (idx, true) => Found(
+            Handle::new_kv(node, idx)
+        ),
+        (idx, false) => SearchResult::GoDown(
+            Handle::new_edge(node, idx)
+        )
+    }
+}
+
+fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
+    node: &NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> (usize, bool)
+        where Q: Ord, K: Borrow<Q> {
+
+    for (i, k) in node.keys().iter().enumerate() {
+        match key.cmp(k.borrow()) {
+            Ordering::Greater => {},
+            Ordering::Equal => return (i, true),
+            Ordering::Less => return (i, false)
+        }
+    }
+    (node.keys().len(), false)
+}
+