Crate window_sort_iterator

Expand description

An iterator adapter that sorts items within a sliding window.

This applies a sliding window over the iterator, sorts items within that window, and yields them in order within that window. The implementation uses a std::collections::BinaryHeap, so the default direction is from highest to lowest item. In order to change the sorting direction, use std::cmp::Reverse.

This is useful in situations where you, e.g., have an of items which are mostly sorted which is possibly large, so you don’t want to keep it in memory to be sorted. If you can define some reasonable bounds on the “scrambledness” of the iterator, you can then un-scramble it with this.

Internally, the algorithm tries to keep the heap filled as long as the underlying iterator produces items. When the heap is filled or the underlying iterator does not yield anymore items, the next item is popped off the heap.

Examples

Basic usage: Adapt an iterator to be sorted.

use window_sort_iterator::WindowSortIterExt;

let a = &[4, 2, 3, 1];
let mut it = a.iter().cloned().window_sort(2);
assert_eq!(Some(4), it.next());
assert_eq!(Some(3), it.next());
assert_eq!(Some(2), it.next());
assert_eq!(Some(1), it.next());
assert_eq!(None, it.next());

Reverse, to use a min-heap:

use std::cmp::Reverse;
use window_sort_iterator::window_sort;

let a = &[1, 4, 2, 3];
let mut it = window_sort(a.iter().cloned().map(|i| Reverse(i)), 2).map(|i| i.0);
assert_eq!(Some(1), it.next());
assert_eq!(Some(2), it.next());
assert_eq!(Some(3), it.next());
assert_eq!(Some(4), it.next());
assert_eq!(None, it.next())

Crate window_sort_iterator

Examples

Structs

Traits

Functions