src/librustc_data_structures/binary_search_util/mod.rs

   1 #[cfg(test)]
   2 mod tests;
   3
   4 /// Uses a sorted slice `data: &[E]` as a kind of "multi-map". The
   5 /// `key_fn` extracts a key of type `K` from the data, and this
   6 /// function finds the range of elements that match the key. `data`
   7 /// must have been sorted as if by a call to `sort_by_key` for this to
   8 /// work.
   9 pub fn binary_search_slice<E, K>(data: &'d [E], key_fn: impl Fn(&E) -> K, key: &K) -> &'d [E]
  10 where
  11     K: Ord,
  12 {
  13     let mid = match data.binary_search_by_key(key, &key_fn) {
  14         Ok(mid) => mid,
  15         Err(_) => return &[],
  16     };
  17
  18     // We get back *some* element with the given key -- so
  19     // search backwards to find the *first* one.
  20     //
  21     // (It'd be more efficient to use a "galloping" search
  22     // here, but it's not really worth it for small-ish
  23     // amounts of data.)
  24     let mut start = mid;
  25     while start > 0 {
  26         if key_fn(&data[start - 1]) == *key {
  27             start -= 1;
  28         } else {
  29             break;
  30         }
  31     }
  32
  33     // Now search forward to find the *last* one.
  34     //
  35     // (It'd be more efficient to use a "galloping" search
  36     // here, but it's not really worth it for small-ish
  37     // amounts of data.)
  38     let mut end = mid + 1;
  39     let max = data.len();
  40     while end < max {
  41         if key_fn(&data[end]) == *key {
  42             end += 1;
  43         } else {
  44             break;
  45         }
  46     }
  47
  48     &data[start..end]
  49 }