Repository: rust-itertools/itertools (language: rust)

Issue:
Added Range iterator
I thought an iterator that iterates over a range of values would be pretty neat to have. Use if you want to!


Discussion / hints:
One potential reason it doesn't exist is that it can be accomplished with skip-take: If I'm reading things correctly here, `.range(a..b)` is equivalent to `.skip(a).take(b.saturating_sub(a))`.

It may still be worth keeping the `range` method, but consider whether the new iterator struct is actually necessary -- reusing `Skip` and `Take` would mean things are automatically double-ended and such where possible.  (And I'm not sure whether supporting `.range(1..)` and `.range(..10)` are actually valuable, since they're equivalent to `.skip(1)` and `.take(10)`.)
This is very similar to [`Vec::drain`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain). Should it use the same name?


@jswrenn I don't think it should be called drain, because it consumes the whole iterator, not just a part of a vector, like drain does. But yeah, the formatting changes were accidental, and reusing skip and take may be a better idea. The problem with those though is that they wouldn't work too well with unlimited iterators. ``range(5..)`` only corresponds to the call ``skip(5)`` and doesn't need a ``take``, but that changes the type of the iterator. This could potentially be fixed by using an enum, though.
I feel pretty strongly that it shouldn't be `drain` because the important part to me about `drain` is that it modifies the receiver even if the return value is not used.  To me this is far more like `Vec::get`.

@TrolledWoods One could also use an associated type for the return type so that `.range(5..)` returns `Skip<_>` and `.range(..5)` returns `Take<_>` and `.range(5..10)` return `Skip<Take<_>>`.
That's a great idea @scottmcm 
Yeah, this is definitely better, now we can have ``range(..)`` be the same as a noop, so we keep ALL the functionality of the underlying iterator!

I was thinking maybe the range standalone function should use IntoIterator instead of Iterator, since it seems like most other standalone functions do that in itertools
And do we really want the access to the range function to be via ``itertools::range::range``? I wanted to avoid the name clash that ``pub use range::range;`` could cause, but maybe I should rename the range.rs file to something like range_traits.rs
I'm going to be honest though, it feels like the associated type version has a few more drawbacks than the previous approach. It adds a new trait, it changes its return type based on the input, it cannot take a generic RangeBounds type, and(giving it some more thought I realized this) you have to pass around the iterator with the range as a type parameter until generic trait types are stable. The current approach is sure a lot easier to implement and less error prone, but I'm not so sure anymore it's the right approach
The trait approach is very close to how the core library implements slice indexing: it defines a trait, [`SliceIndex`](https://doc.rust-lang.org/core/slice/trait.SliceIndex.html), and then implements [`ops::Index` for all indices implementing that trait](https://doc.rust-lang.org/std/primitive.slice.html#impl-Index%3CI%3E). In practice, the burden of this extra trait is small; I think most end-users are completely unaware that `SliceIndex` exists!

Likewise, I don't think implementing iterator indexing with an “`IteratorIndex`” trait would be terribly unergonomic. The symmetry with `SliceIndex` is a point in its favor, too.

Here's what an implementation mirroring `SliceIndex` as closely as possible looks like: https://play.rust-lang.org/?edition=2018&gist=2d908fb28c16fb69070ea857c5aa1143

I'm curious if this is a candidate for standard library inclusion.

Then, making it a trait seems to be very nicely consistant with the standard library! I have really terrible internet at the moment, so it's kindof hard for me to push changes at the moment.
One thing though, since range is so closely mapped by slice.get(), maybe it should just be called get, and support usize indexing as well? So .range(4) (or .get(4)), is just the same as .nth(4). This range thing is for convenience to begin with, so I don't think that this addition would be strange
Agree completely. Both of those changes are already incorporated into the playground URL I linked. :-)
Welp, I don't know about the naming, but I think it's starting to come together quite nicely now
Let's stick to mirroring `SliceIndex` as closely as possible:
- `IterIndex` → `IteratorIndex`
- `IterIndex::get` → `IteratorIndex::index`

Could you also just make sure that indentation consistently uses four spaces? Right now it's a mix of tabs and spaces.





Oh sorry, I prefer tabs for my personal projects, so my editor uses them. I'll rename the things and fix the tabs
Should I rename the module to iterator_index too, or just keep it as iter_index?
`iter_index` is fine, as it's just an internal implementation detail and not publically exposed.
Are there any more tweaks that I should do?
I could limit the IteratorIndex::Output to be an IntoIterator, which could allow people to write some nice generic code with the get if they wanted to. Another option would be to limit the Output to Iterator, but then the .get(5) case would have to return the Option iterator, which I think could be kinda clunky for users
Limit `IteratorIndex` to `Iterator` (that way it'll play nice with method chaining).

The `usize` indexing case should be this:
```
impl<I> IteratorIndex<I> for usize
where
    I: Iterator,
{
    type Output = <Option<I::Item> as IntoIterator>::IntoIter;

    fn index(self, mut iter: I) -> Self::Output {
        iter.nth(self).into_iter()
    }
}
```
Done!
I'm excited to merge this, but I want to first be sure we won't eventually be in conflict with the core library. I've opened an issue on @rust-lang/rust asking whether this PR would be a good core library addition: https://github.com/rust-lang/rust/issues/73482
Did you consider using `dropping` instead of `skip`? That changes the laziness, but you did use `nth` in `IteratorIndex for usize`, which has the same immediate effect.

edit: I guess you'd need to `fuse` though, in case `dropping` exhausts the iterator.
That's a good point. nth isn't consistant with the rest of the things. I think however the better approach is to make ``IteratorIndex for usize`` lazy instead of making everything else pre-evaluated. I think having it be lazy makes more sense. Not sure what you think, though
Another consideration -- slice `get(range)` returns new slices, but `get(usize)` just returns the element, whereas you have `IteratorIndex` returning new iterators in all cases. But if iterator `get(usize)` were to return the element directly, that's literally just `nth`.

It's probably more consistent for iterators to be lazy all around.
I'm of two minds.

## Approach 1: It's just a shorthand
We could have a `get` method that's _just_ a shorthand for `nth`, `take` and `skip`. In this possibility, we have `get(usize)` produce an `Option<Item>`. Ergonomics are _maybe_ slightly diminished, but the explanation of `get` is simpler: `get` is _just_ a shorthand for `nth`, `take` and `skip`.

If an end-user wants to lazily get the `n`<sup>th</sup> element, they still can: they just index on `n..=n`.

I like the ease of explanation, ease of implementation, and flexibility of this approach.

The downside of this approach is `get(usize)` consumes the underlying iterator, but the other index types do not. This is weird for two reasons:
1. First, when using `Iterator::get` in a context that's generic over the indexing type, it's weird that certain instantiations of that type would mutate the consume iterator, but others would not. I don't anticipate `IteratorIndex` to be used by end-users often, so I'm not too worried about this scenario.
2. Second, we're clearly drawing an analogy to `Slice::get`, but this lazy/eager discrepancy weakens the analogy: `Slice::get` _never_ consumes the underlying slice.

## Approach 2: Consistency above all
If we keep the `Iterator` bound on `Output`, then we probably ought to ensure that  `get(usize)` lazily consumes the underlying iterator. However, there's no lazy `nth` in the standard library, so we'd either need to use a combination of `skip` and `take` for this case, or introduce a new `lazy_nth` construct.

I like the semantic consistency of this approach. However, it's not as easy to implement, and (IMO) it's not as easy to explain. It's a lot of work _just_ for a `lazy_nth`. But is there any demand for a `lazy_nth` construct? I struggle to think of a case where I would use it, and a cursory glance at the issues here and on rust-lang/rust doesn't turn up any requests for it.

---

In the absence of demonstrated demand for a `lazy_nth` construct, I have a slight preference towards the first approach, but I'm not really convinced either way.

If this issue proves to be major roadblock, let's just remove the `IteratorIndex` implementation for `usize` (and change the bound on `IteratorIndex::Output` to `IntoIterator`). 

I'm terribly sorry it took so long, I completely forgot about this and it seems github is not very adamant about telling you new messages have appeared. If there's anything more you need do tell!
I'd love to see this merged! It just needs a bit of attention and rebasing. 
Nice.

@TrolledWoods Are you around to finish this awesome feature of yours?

Fix patch:
diff --git a/src/iter_index.rs b/src/iter_index.rs
new file mode 100644
index 000000000..aadaa72a7
--- /dev/null
+++ b/src/iter_index.rs
@@ -0,0 +1,116 @@
+use core::iter::{Skip, Take};
+use core::ops::{Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};
+
+#[cfg(doc)]
+use crate::Itertools;
+
+mod private_iter_index {
+    use core::ops;
+
+    pub trait Sealed {}
+
+    impl Sealed for ops::Range<usize> {}
+    impl Sealed for ops::RangeInclusive<usize> {}
+    impl Sealed for ops::RangeTo<usize> {}
+    impl Sealed for ops::RangeToInclusive<usize> {}
+    impl Sealed for ops::RangeFrom<usize> {}
+    impl Sealed for ops::RangeFull {}
+}
+
+/// Used by [`Itertools::get`] to know which iterator
+/// to turn different ranges into.
+pub trait IteratorIndex<I>: private_iter_index::Sealed
+where
+    I: Iterator,
+{
+    /// The type returned for this type of index.
+    type Output: Iterator<Item = I::Item>;
+
+    /// Returns an adapted iterator for the current index.
+    ///
+    /// Prefer calling [`Itertools::get`] instead
+    /// of calling this directly.
+    fn index(self, from: I) -> Self::Output;
+}
+
+impl<I> IteratorIndex<I> for Range<usize>
+where
+    I: Iterator,
+{
+    type Output = Skip<Take<I>>;
+
+    fn index(self, iter: I) -> Self::Output {
+        iter.take(self.end).skip(self.start)
+    }
+}
+
+impl<I> IteratorIndex<I> for RangeInclusive<usize>
+where
+    I: Iterator,
+{
+    type Output = Take<Skip<I>>;
+
+    fn index(self, iter: I) -> Self::Output {
+        // end - start + 1 without overflowing if possible
+        let length = if *self.end() == usize::MAX {
+            assert_ne!(*self.start(), 0);
+            self.end() - self.start() + 1
+        } else {
+            (self.end() + 1).saturating_sub(*self.start())
+        };
+        iter.skip(*self.start()).take(length)
+    }
+}
+
+impl<I> IteratorIndex<I> for RangeTo<usize>
+where
+    I: Iterator,
+{
+    type Output = Take<I>;
+
+    fn index(self, iter: I) -> Self::Output {
+        iter.take(self.end)
+    }
+}
+
+impl<I> IteratorIndex<I> for RangeToInclusive<usize>
+where
+    I: Iterator,
+{
+    type Output = Take<I>;
+
+    fn index(self, iter: I) -> Self::Output {
+        assert_ne!(self.end, usize::MAX);
+        iter.take(self.end + 1)
+    }
+}
+
+impl<I> IteratorIndex<I> for RangeFrom<usize>
+where
+    I: Iterator,
+{
+    type Output = Skip<I>;
+
+    fn index(self, iter: I) -> Self::Output {
+        iter.skip(self.start)
+    }
+}
+
+impl<I> IteratorIndex<I> for RangeFull
+where
+    I: Iterator,
+{
+    type Output = I;
+
+    fn index(self, iter: I) -> Self::Output {
+        iter
+    }
+}
+
+pub fn get<I, R>(iter: I, index: R) -> R::Output
+where
+    I: IntoIterator,
+    R: IteratorIndex<I::IntoIter>,
+{
+    index.index(iter.into_iter())
+}
diff --git a/src/lib.rs b/src/lib.rs
index 931a28f92..c439fcfef 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -146,6 +146,7 @@ pub mod structs {
 
 /// Traits helpful for using certain `Itertools` methods in generic contexts.
 pub mod traits {
+    pub use crate::iter_index::IteratorIndex;
     pub use crate::tuple_impl::HomogeneousTuple;
 }
 
@@ -194,6 +195,7 @@ mod groupbylazy;
 #[cfg(feature = "use_std")]
 mod grouping_map;
 mod intersperse;
+mod iter_index;
 #[cfg(feature = "use_alloc")]
 mod k_smallest;
 #[cfg(feature = "use_alloc")]
@@ -504,6 +506,56 @@ pub trait Itertools: Iterator {
         intersperse::intersperse_with(self, element)
     }
 
+    /// Returns an iterator over a subsection of the iterator.
+    ///
+    /// Works similarly to [`slice::get`](https://doc.rust-lang.org/std/primitive.slice.html#method.get).
+    ///
+    /// **Panics** for ranges `..=usize::MAX` and `0..=usize::MAX`.
+    ///
+    /// It's a generalisation of [`Iterator::take`] and [`Iterator::skip`],
+    /// and uses these under the hood.
+    /// Therefore, the resulting iterator is:
+    /// - [`ExactSizeIterator`] if the adapted iterator is [`ExactSizeIterator`].
+    /// - [`DoubleEndedIterator`] if the adapted iterator is [`DoubleEndedIterator`] and [`ExactSizeIterator`].
+    ///
+    /// # Unspecified Behavior
+    /// The result of indexing with an exhausted [`core::ops::RangeInclusive`] is unspecified.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// let vec = vec![3, 1, 4, 1, 5];
+    ///
+    /// let mut range: Vec<_> =
+    ///         vec.iter().get(1..=3).copied().collect();
+    /// assert_eq!(&range, &[1, 4, 1]);
+    ///
+    /// // It works with other types of ranges, too
+    /// range = vec.iter().get(..2).copied().collect();
+    /// assert_eq!(&range, &[3, 1]);
+    ///
+    /// range = vec.iter().get(0..1).copied().collect();
+    /// assert_eq!(&range, &[3]);
+    ///
+    /// range = vec.iter().get(2..).copied().collect();
+    /// assert_eq!(&range, &[4, 1, 5]);
+    ///
+    /// range = vec.iter().get(..=2).copied().collect();
+    /// assert_eq!(&range, &[3, 1, 4]);
+    ///
+    /// range = vec.iter().get(..).copied().collect();
+    /// assert_eq!(range, vec);
+    /// ```
+    fn get<R>(self, index: R) -> R::Output
+    where
+        Self: Sized,
+        R: traits::IteratorIndex<Self>,
+    {
+        iter_index::get(self, index)
+    }
+
     /// Create an iterator which iterates over both this and the specified
     /// iterator simultaneously, yielding pairs of two optional elements.
     ///


Test patch:
diff --git a/tests/laziness.rs b/tests/laziness.rs
index 2ce29cb8a..f936decde 100644
--- a/tests/laziness.rs
+++ b/tests/laziness.rs
@@ -63,6 +63,14 @@ must_use_tests! {
     intersperse_with {
         let _ = Panicking.intersperse_with(|| 0);
     }
+    get {
+        let _ = Panicking.get(1..4);
+        let _ = Panicking.get(1..=4);
+        let _ = Panicking.get(1..);
+        let _ = Panicking.get(..4);
+        let _ = Panicking.get(..=4);
+        let _ = Panicking.get(..);
+    }
     zip_longest {
         let _ = Panicking.zip_longest(Panicking);
     }
diff --git a/tests/test_core.rs b/tests/test_core.rs
index b5826ef39..32af246c0 100644
--- a/tests/test_core.rs
+++ b/tests/test_core.rs
@@ -18,6 +18,41 @@ use crate::it::Itertools;
 use core::iter;
 use itertools as it;
 
+#[allow(dead_code)]
+fn get_esi_then_esi<I: ExactSizeIterator + Clone>(it: I) {
+    fn is_esi(_: impl ExactSizeIterator) {}
+    is_esi(it.clone().get(1..4));
+    is_esi(it.clone().get(1..=4));
+    is_esi(it.clone().get(1..));
+    is_esi(it.clone().get(..4));
+    is_esi(it.clone().get(..=4));
+    is_esi(it.get(..));
+}
+
+#[allow(dead_code)]
+fn get_dei_esi_then_dei_esi<I: DoubleEndedIterator + ExactSizeIterator + Clone>(it: I) {
+    fn is_dei_esi(_: impl DoubleEndedIterator + ExactSizeIterator) {}
+    is_dei_esi(it.clone().get(1..4));
+    is_dei_esi(it.clone().get(1..=4));
+    is_dei_esi(it.clone().get(1..));
+    is_dei_esi(it.clone().get(..4));
+    is_dei_esi(it.clone().get(..=4));
+    is_dei_esi(it.get(..));
+}
+
+#[test]
+fn get_1_max() {
+    let mut it = (0..5).get(1..=usize::MAX);
+    assert_eq!(it.next(), Some(1));
+    assert_eq!(it.next_back(), Some(4));
+}
+
+#[test]
+#[should_panic]
+fn get_full_range_inclusive() {
+    let _it = (0..5).get(0..=usize::MAX);
+}
+
 #[test]
 fn product0() {
     let mut prod = iproduct!();