#iterator #sorted #set #relational

sorted-iter

Typesafe extensions for sorted iterators, including set and relational operations

6 releases

✓ Uses Rust 2018 edition

new 0.1.5 Nov 14, 2019
0.1.4 Nov 8, 2019

#198 in Data structures

29 downloads per month

MIT/Apache

38KB
846 lines

Build Status Latest Version Docs Badge

Sorted Iter

About

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.

TL;DR;

Relational operations

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

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

Sorted iterators

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.

Sorted pair iterators

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, left_join, right_join and outer_join.

Instances

Instances are provided to allow treating iterators in the standard library that are guaranteed to be sorted as sorted iterators.

Tests

Tests are done using the fantastic quickcheck crate, by comparing against the operations defined on BTreeSet and BTreeMap.

No runtime deps