### 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

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

`let` city `=` `btreemap!``{`
`1` `=>` `"`New York`"``,`
`2` `=>` `"`Tokyo`"``,`
`}``;`
`let` country `=` `btreemap!``{`
`1` `=>` `"`USA`"``,`
`2` `=>` `"`Japan`"``,`
`}``;`
`let` res`:` `Vec``<``_``>` `=` city`.``iter``(``)``.``join``(`country`.``iter``(``)``)``.``collect``(``)``;`

`let` primes `=` `btreeset!` `{` `2``u64``,` `3``,` `5``,` `7``,` `11``,` `13` `}``;`
`let` fibs `=` `btreeset!` `{` `1``u64``,` `2``,` `3``,` `5``,` `8``,` `13` `}``;`
`let` primes `=` primes`.``iter``(``)``;`
`let` fibs `=` fibs`.``iter``(``)``;`
`let` nats `=` `1``u64``..``;`
`//` 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.