Some bounds in circular_tuple_windows are unnecessary (I think)

[sgtatham]

The circular_tuple_windows method requires the input iterator to be Clone and also ExactSizeIterator, as well as the item type being Clone.

I recently wanted circular tuple windows of size 2, on an iterator which did not have those additional traits. I implemented it myself using the following code (far less generic than yours, but enough for my purpose at the time), which only requires the item type to be Clone and the iterator itself to be Sized. Extract the first item from the iterator (if any), clone it and put it at the end again (if any), and then take ordinary tuple_windows of the result.

pub trait MyItertools: Iterator {
    fn cyclic_pairs(mut self) -> impl Iterator<Item = (Self::Item, Self::Item)>
    where
        Self::Item: Clone,
        Self: Sized,
    {
        let first = self.next();
        let first_again = first.clone(); // even if it's None
        first
            .into_iter()
            .chain(self)
            .chain(first_again.into_iter())
            .tuple_windows()
    }
}

An extended version of the same technique would surely work to implement circular tuple windows of other sizes without those additional constraints on the iterator.

It's not quite as simple as extending this implementation, because of edge cases when the input list is very short. (If I try to make tuple windows of length 4 by extracting up to 3 initial elements and chaining another copy of them at the end, then I get no output windows at all for a length-1 list, whereas the official circular_tuple_windows would give a tuple (a,a,a,a), so some special cases would be needed to decide how many copies of the initial elements to chain at the end.)

So, would it be possible to replace the implementation of circular_tuple_windows so as to avoid those extra requirements?

If this seems like a good idea in principle, and has no subtle gotchas that you can foresee, I'd be happy to attempt the main implementation. I don't know that my Rust is good enough to get all the outlying parts right, though. (For example, you'd presumably want to propagate ExactSizeIterator from the input if the input has it, and no doubt there are other things of that kind I haven't thought of.)

[phimuemue]

Hi @sgtatham, I think your assessment is correct.

However, I suggest moving away from tuples¹ and going with arrays.

I imagine that circular_array_windows could remember the "to-be-cycled items" in an Option<[Self::Item; N-1]> that is populated on the first next call (using next_array), and keep an index (into the array) to be incremented once the underlying iterator is exhausted.

Footnotes

1. @jswrenn I suggest deprecating tuple-based functions if we have array-based counter parts. The tuple case can always be supported dedicated array-to-tuple conversion. ↩

[sgtatham]

I like the tuples as an output format, because it's convenient to be able to say for (a, b) in thing.circular_tuple_windows() { ... }. But I guess you mean that circular_tuple_windows would still exist as a name but just be a final array→tuple adaptor step on the end of the new circular_array_windows?

[jswrenn]

You can destructure arrays in the same manner. :-) Given that, I'm all for deprecating our tuple methods.

[phimuemue]

But I guess you mean that circular_tuple_windows would still exist as a name but just be a final array→tuple adaptor step on the end of the new circular_array_windows

Either that, or we keep circular_tuple_windows as it is and remove it after it has been deprecated for 12 months.

[sgtatham]

You can destructure arrays in the same manner. :-) Given that, I'm all for deprecating our tuple methods.

Today I learned! Indeed, I can write let [a,b] = some_array just as I'd write let (a,b) = some_tuple. Also I now realise that tuples of up to size 12 implement From of the corresponding array, so if I really did need tuples for some reason (e.g. passing to an existing function that expects one) then it's only a matter of appending .map(Into::into).

OK, so it sounds as if the way forward is to write a .circular_array_windows without the extra trait bounds and see whether you tell me I've done it totally wrong. :-)

[sgtatham]

OK, #1086 is a draft PR. Be gentle with me – I'm still learning 🙂