[−][src]Crate sorted_iter
This crate provides set and relational operations for all iterators in the standard library that are known at compile time to be sorted.
Set operations
use sorted_iter::SortedIteratorExt; let primes = btreeset! { 2, 3, 5, 7, 11, 13u64 }.into_iter(); let fibs = btreeset! { 1, 2, 3, 5, 8, 13u64 }.into_iter(); let fib_primes = primes.intersection(fibs);
For available set operations, see SortedIterator. For sorted iterators in the std lib, see instances the for SortedByItem marker trait.
Relational operations
use sorted_iter::SortedPairIteratorExt; let cities = btreemap! { 1 => "New York", 2 => "Tokyo", 3u8 => "Berlin" }.into_iter(); let countries = btreemap! { 1 => "USA", 2 => "Japan", 3u8 => "Germany" }.into_iter(); let cities_and_countries = cities.join(countries);
For available relational operations, see SortedPairIterator. For sorted iterators in the std lib, see instances the for SortedByKey marker trait.
Transformations that retain order are allowed
use sorted_iter::*; let odd = (1..31).step_by(2); let multiples_of_3 = (3..30).step_by(3); let either = odd.union(multiples_of_3);
Transformations that can change the order lose the sorted property
use sorted_iter::*; // we have no idea what map does to the order. could be anything! let a = (1..31).map(|x| -x); let b = (3..30).step_by(3); let either = a.union(b); // does not compile!
Assuming sort ordering
For most std lib iterators, this library already provides instances. But there will occasionally be an iterator from a third party library where you know that it is properly sorted.
For this case, there is an escape hatch:
// the assume_ extensions have to be implicitly imported use sorted_iter::*; use sorted_iter::assume::*; let odd = vec![1,3,5,7u8].into_iter().assume_sorted_by_item(); let even = vec![2,4,6,8u8].into_iter().assume_sorted_by_item(); let all = odd.union(even); let cities = vec![(1u8, "New York")].into_iter().assume_sorted_by_key(); let countries = vec![(1u8, "USA")].into_iter().assume_sorted_by_key(); let cities_and_countries = cities.join(countries);
Marking your own iterators
If you have a library and want to mark some iterators as sorted, this is possible by implementing the appropriate marker trait, SortedByItem or SortedByKey.
// marker traits are not at top level, since usually you don't need them use sorted_iter::sorted_iterator::SortedByItem; use sorted_iter::sorted_pair_iterator::SortedByKey; struct MySortedIter<T> { whatever: T } struct MySortedPairIter<K, V> { whatever: (K, V) } impl<T> SortedByItem for MySortedIter<T> {} impl<K, V> SortedByKey for MySortedPairIter<K, V> {}
Modules
assume | extension traits for unchecked conversions from iterators to sorted iterators |
sorted_iterator | implementation of the sorted_iterator set operations |
sorted_pair_iterator | implementation of the sorted_pair_iterator relational operations |
Traits
SortedIteratorExt | set operations for iterators where the items are sorted according to the natural order |
SortedPairIteratorExt | relational operations for iterators of pairs where the items are sorted according to the key |