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) -> Self

where I: IntoIterator<Item = T>, I::IntoIter: ExactSizeIterator,

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().copied());
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);

pub fn iter(&self) -> Iter<'_, T>

Iterator over elements of a collection.

It yields all items in an unspecified order.

Examples

let expected = vec![1, 2, 3, 4, 5];
let coll = OrderedCollection::from(expected.clone());
let mut values: Vec<_> = coll.iter().copied().collect();
values.sort();
assert_eq!(values, expected);

Trait Implementations

impl<T> Drop for OrderedCollection<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> From<OrderedCollection<T>> for Vec<T>

fn from(value: OrderedCollection<T>) -> Self

Converts all elemenets into a new Vec in unspecified order

Examples

let x = vec![1, 2, 3, 4, 5];
let coll = OrderedCollection::from(x.clone());
let mut values = Vec::from(coll);
values.sort();
assert_eq!(values, x);

impl<T: Ord> From<Vec<T>> 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));

impl<'a, T: Ord> IntoIterator for &'a OrderedCollection<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for OrderedCollection<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.