Struct ordsearch::OrderedCollection
source · pub struct OrderedCollection<T> { /* private fields */ }
Expand description
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§
source§impl<T: Ord> OrderedCollection<T>
impl<T: Ord> OrderedCollection<T>
sourcepub fn from_sorted_iter<I>(iter: I) -> Selfwhere
I: IntoIterator<Item = T>,
I::IntoIter: ExactSizeIterator<Item = 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));
sourcepub fn from_slice<'a>(v: &'a mut [T]) -> OrderedCollection<&'a T>
pub fn from_slice<'a>(v: &'a mut [T]) -> OrderedCollection<&'a 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));
sourcepub fn find_gte<'a, X>(&'a self, x: X) -> Option<&'a T>where
T: Borrow<X>,
X: Ord,
pub fn find_gte<'a, X>(&'a self, x: X) -> Option<&'a 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);