src/liballoc/btree/search.rs

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