flo-l/rust-sliding_windows

This repository contains a non-copying implementation of a sliding windows iterator adaptor.

sliding_windows

This crate offers an Iterator adaptor, which yields "sliding windows" over the elements returned by the wrapped iterator.

It's worth to note that it does not copy elements, which makes the code several orders of mignitudes faster than naive copying variants.

As a consequence it violates the Iterator protocol slightly. It is not possible to have two Windows into the data available at the same time. This is checked during runtime.

The backing storage is a Vec, so this Iterator adaptor is not ideal for very large windows (>20 elements or very huge elements).

I'd happily accept a PR to implement the same functionality with a VecDeque or similar, see this issue.

Links

• Documentation
• crates.io

Install

Add this to your Cargo.toml.

[dependencies]
sliding_windows = "3.0"

Example

extern crate sliding_windows;
use sliding_windows::{IterExt, Storage};

fn main() {
    let mut storage: Storage<u32> = Storage::new(3);

    for x in (0..5).sliding_windows(&mut storage) {
        println!("{:?}", x);
    }
}

// This outputs:
// Window[0, 1, 2]
// Window[1, 2, 3]
// Window[2, 3, 4]

For more examples please consult the Documentation.

This functionality in other languages/crates

• Ruby: #each_cons
• Python: window
• Rust (just for slices): .windows()
• Rust (for all Iterators, but copying): .slide()

rust-sliding_windows's Issues

Performance improvements

Instead of using VecDeque as storage it's also possible to improve performance immensely by just using a bigger Vec and shifting all elements just when it's end is reached. Eg. a Vec with size = window_size * 2 would be a lot more CPU efficient but would just use a bit more memory.

Implement Storage with VecDeque or similar

Storage is currently implemented using a Vec as a backing storage. This becomes inefficient for huge window sizes, as the whole array needs to be shifted on every call to next() sometimes.

As noted in #1 it's very hard to implement Storage generically over any container.

• One would lose the ability of Window to deref to a (mut) slice.
• Window probably has to implement Iterator or Index/IndexMut.

I'd be happy to merge a PR that implements Storage generically over containers if good solutions to the above problems are found and if no functionality gets lost.

Anyway I'd also merge a PR implementing another adaptor, which uses a VecDeque or anything efficient for huge window sizes.

Use Cow to make this fully Iterator compliant

Just leaving this here as a note to myself.

Needs polishing

Before announcing this on reddit etc. this repo needs some polishing.

Wishlist

• better readme
• shorter/better type names (SlidingWindowStorage is horrible)
• more storage types (VecDeque), maybe a trait so users can implement their own won't be done
• macro to make usage even easier Is this really needed?