![Build Status] ![Latest Version] ![Docs Badge]
This provides typesafe extension for sorted iterators to perform set and relational operations. By sorted I mean strictly sorted according to the [Ord] instance of the item or key type.
Relational operations
rust
let city = btreemap!{
1 => "New York",
2 => "Tokyo",
};
let country = btreemap!{
1 => "USA",
2 => "Japan",
};
let res: Vec<_> = city.iter().join(country.iter()).collect();
Set operations
rust
let primes = btreeset! { 2u64, 3, 5, 7, 11, 13 };
let fibs = btreeset! { 1u64, 2, 3, 5, 8, 13 };
let primes = primes.iter();
let fibs = fibs.iter();
let nats = 1u64..;
// both primes and fibs
let both = primes.clone().intersection(fibs.clone());
// either primes or fibs
let either = primes.union(fibs).cloned();
// natural numbers that are neither
let neither = nats.difference(either);
It is possible to efficiently define set operations on sorted iterators. Sorted iterators are
very common in the standard library. E.g. the elements of a [BTreeSet] or the keys of a [BTreeMap]
are guaranteed to be sorted according to the element order, as are iterable ranges like 0..100.
There are also a number of operations on iterators that preserve the sort order. E.g. if an iterator is sorted, [take], [take_while] etc. are going to result in a sorted iterator as well.
Since the complete types of iterators are typically visible in rust, it is possible to encode these rules at type level. This is what this crate does.
Iterators of pairs that are sorted according to the first element / key are also very common in the standard library and elsewhere. E.g. the elements of a [BTreeMap] are guaranteed to be sorted according to the key order.
The same rules as for sorted iterators apply for preservation of the sort order, except that there are some additional operations that preserve sort order. Anything that only operates on the value, like e.g. map or filter_map on the value, is guaranteed to preserve the sort order.
The operations that can be defined on sorted pair operations are the relational operations known from relational algebra / SQL, namely join, leftjoin, rightjoin and outer_join.
Instances are provided to allow treating iterators in the standard library that are guaranteed to be sorted as sorted iterators.
Tests are done using the fantastic [quickcheck] crate, by comparing against the operations defined on [BTreeSet] and [BTreeMap].