Struct ordsearch::OrderedCollection

pub struct OrderedCollection<T> { /* private fields */ }

A collection of ordered items that can efficiently satisfy queries for nearby elements.

The most interesting method here is find_gte.

Examples

let x = OrderedCollection::from(vec![1, 2, 4, 8, 16, 32, 64]);
assert_eq!(x.find_gte(0), Some(&1));
assert_eq!(x.find_gte(1), Some(&1));
assert_eq!(x.find_gte(3), Some(&4));
assert_eq!(x.find_gte(6), Some(&8));
assert_eq!(x.find_gte(8), Some(&8));
assert_eq!(x.find_gte(64), Some(&64));
assert_eq!(x.find_gte(65), None);

Implementations

impl<T: Ord> OrderedCollection<T>

pub fn from_sorted_iter<I>(iter: I) -> Selfwhere I: IntoIterator<Item = T>, I::IntoIter: ExactSizeIterator<Item = T>,

Construct a new OrderedCollection from an iterator over sorted elements.

Note that if the iterator is not sorted, no error will be given, but lookups will give incorrect results. The given iterator must also implement ExactSizeIterator so that we know the size of the lookup array.

Examples

Using an already-sorted iterator:

let mut s = BTreeSet::new();
s.insert(42);
s.insert(89);
s.insert(7);
s.insert(12);
let a = OrderedCollection::from_sorted_iter(s);
assert_eq!(a.find_gte(50), Some(&89));

Sorting a collection and then iterating (in this case, you’d likely use new instead):

let mut v = vec![42, 89, 7, 12];
v.sort_unstable();
let a = OrderedCollection::from_sorted_iter(v);
assert_eq!(a.find_gte(50), Some(&89));

The OrderedCollection can also be over references to somewhere else:

let mut s = BTreeSet::new();
s.insert(42);
s.insert(89);
s.insert(7);
s.insert(12);
let a = OrderedCollection::from_sorted_iter(s.iter());
assert_eq!(a.find_gte(50), Some(&&89));

pub fn from_slice(v: &mut [T]) -> OrderedCollection<&T>

Construct a new OrderedCollection from a slice of elements.

Note that the underlying slice will be reordered!

Examples

let mut vals = [42, 89, 7, 12];
let a = OrderedCollection::from_slice(&mut vals);
assert_eq!(a.find_gte(50), Some(&&89));

pub fn find_gte<X>(&self, x: X) -> Option<&T>where T: Borrow<X>, X: Ord,

Find the smallest value v such that v >= x.

Returns None if there is no such v.

Examples

let x = OrderedCollection::from(vec![1, 2, 4, 8, 16, 32, 64]);
assert_eq!(x.find_gte(0), Some(&1));
assert_eq!(x.find_gte(1), Some(&1));
assert_eq!(x.find_gte(3), Some(&4));
assert_eq!(x.find_gte(6), Some(&8));
assert_eq!(x.find_gte(8), Some(&8));
assert_eq!(x.find_gte(64), Some(&64));
assert_eq!(x.find_gte(65), None);

Trait Implementations

impl<T: Ord> From<Vec<T, Global>> for OrderedCollection<T>

fn from(v: Vec<T>) -> OrderedCollection<T>

Construct a new OrderedCollection from a vector of elements.

Examples

let a = OrderedCollection::from(vec![42, 89, 7, 12]);
assert_eq!(a.find_gte(50), Some(&89));