src/liballoc/collections/btree/search.rs

   1 use core::borrow::Borrow;
   2 use core::cmp::Ordering;
   3
   4 use super::node::{Handle, NodeRef, marker, ForceResult::*};
   5
   6 use SearchResult::*;
   7
   8 pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
   9     Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
  10     GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>)
  11 }
  12
  13 pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
  14     mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
  15     key: &Q
  16 ) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
  17         where Q: Ord, K: Borrow<Q> {
  18
  19     loop {
  20         match search_node(node, key) {
  21             Found(handle) => return Found(handle),
  22             GoDown(handle) => match handle.force() {
  23                 Leaf(leaf) => return GoDown(leaf),
  24                 Internal(internal) => {
  25                     node = internal.descend();
  26                     continue;
  27                 }
  28             }
  29         }
  30     }
  31 }
  32
  33 pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
  34     node: NodeRef<BorrowType, K, V, Type>,
  35     key: &Q
  36 ) -> SearchResult<BorrowType, K, V, Type, Type>
  37         where Q: Ord, K: Borrow<Q> {
  38
  39     match search_linear(&node, key) {
  40         (idx, true) => Found(
  41             Handle::new_kv(node, idx)
  42         ),
  43         (idx, false) => SearchResult::GoDown(
  44             Handle::new_edge(node, idx)
  45         )
  46     }
  47 }
  48
  49 pub fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
  50     node: &NodeRef<BorrowType, K, V, Type>,
  51     key: &Q
  52 ) -> (usize, bool)
  53         where Q: Ord, K: Borrow<Q> {
  54
  55     for (i, k) in node.keys().iter().enumerate() {
  56         match key.cmp(k.borrow()) {
  57             Ordering::Greater => {},
  58             Ordering::Equal => return (i, true),
  59             Ordering::Less => return (i, false)
  60         }
  61     }
  62     (node.keys().len(), false)
  63 }