From fd5f8d90c5cc593e6aa43a978a1498f88558cc39 Mon Sep 17 00:00:00 2001 From: Daniel Micay Date: Thu, 11 Jul 2013 00:23:59 -0400 Subject: iterator: add DoubleEndedIterator concept This implements the trait for vector iterators, replacing the reverse iterator types. The methods will stay, for implementing the future reverse Iterable traits and convenience. This can also be trivially implemented for circular buffers and other variants of arrays like strings and `SmallIntMap`/`SmallIntSet`. The `DoubleEndedIterator` trait will allow for implementing algorithms like in-place reverse on generic mutable iterators. The naming (`Range` vs. `Iterator`, `Bidirectional` vs. `DoubleEnded`) can be bikeshedded in the future. --- src/libstd/iterator.rs | 52 +++++++++++++++++++++++++++++++++++ src/libstd/vec.rs | 74 ++++++++++++++++++++++---------------------------- 2 files changed, 85 insertions(+), 41 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs index 4f5f1bd85c7..a17fea24b2c 100644 --- a/src/libstd/iterator.rs +++ b/src/libstd/iterator.rs @@ -47,6 +47,49 @@ pub trait Iterator { fn size_hint(&self) -> (uint, Option) { (0, None) } } +/// A range iterator able to yield elements from both ends +pub trait DoubleEndedIterator: Iterator { + /// Yield an element from the end of the range, returning `None` if the range is empty. + fn next_back(&mut self) -> Option; +} + +/// Iterator adaptors provided for every `DoubleEndedIterator` implementation. +/// +/// In the future these will be default methods instead of a utility trait. +pub trait DoubleEndedIteratorUtil { + /// Flip the direction of the iterator + fn invert(self) -> InvertIterator; +} + +/// Iterator adaptors provided for every `DoubleEndedIterator` implementation. +/// +/// In the future these will be default methods instead of a utility trait. +impl> DoubleEndedIteratorUtil for T { + /// Flip the direction of the iterator + #[inline] + fn invert(self) -> InvertIterator { + InvertIterator{iter: self} + } +} + +/// An double-ended iterator with the direction inverted +// FIXME #6967: Dummy A parameter to get around type inference bug +pub struct InvertIterator { + priv iter: T +} + +impl> Iterator for InvertIterator { + #[inline] + fn next(&mut self) -> Option { self.iter.next_back() } + #[inline] + fn size_hint(&self) -> (uint, Option) { self.iter.size_hint() } +} + +impl> DoubleEndedIterator for InvertIterator { + #[inline] + fn next_back(&mut self) -> Option { self.iter.next() } +} + /// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also /// implementations of the `Iterator` trait. /// @@ -1474,4 +1517,13 @@ mod tests { let xs = [-3, 0, 1, 5, -10]; assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0); } + + #[test] + fn test_invert() { + let xs = [2, 4, 6, 8, 10, 12, 14, 16]; + let mut it = xs.iter(); + it.next(); + it.next(); + assert_eq!(it.invert().transform(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]); + } } diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index 825dc4cc187..5576b4ad704 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -18,7 +18,7 @@ use container::{Container, Mutable}; use cmp; use cmp::{Eq, TotalEq, TotalOrd, Ordering, Less, Equal, Greater}; use clone::Clone; -use iterator::{FromIterator, Iterator, IteratorUtil}; +use iterator::*; use kinds::Copy; use libc::c_void; use num::Zero; @@ -760,12 +760,7 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { } #[inline] fn rev_iter(self) -> VecRevIterator<'self, T> { - unsafe { - let p = vec::raw::to_ptr(self); - VecRevIterator{ptr: p.offset(self.len() - 1), - end: p.offset(-1), - lifetime: cast::transmute(p)} - } + self.iter().invert() } /// Returns an iterator over the subslices of the vector which are @@ -1717,13 +1712,9 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] { } } + #[inline] fn mut_rev_iter(self) -> VecMutRevIterator<'self, T> { - unsafe { - let p = vec::raw::to_mut_ptr(self); - VecMutRevIterator{ptr: p.offset(self.len() - 1), - end: p.offset(-1), - lifetime: cast::transmute(p)} - } + self.mut_iter().invert() } /** @@ -2083,17 +2074,17 @@ macro_rules! iterator { priv lifetime: $elem // FIXME: #5922 } };*/ - (impl $name:ident -> $elem:ty, $step:expr) => { - // could be implemented with &[T] with .slice(), but this avoids bounds checks + (impl $name:ident -> $elem:ty) => { impl<'self, T> Iterator<$elem> for $name<'self, T> { #[inline] fn next(&mut self) -> Option<$elem> { + // could be implemented with slices, but this avoids bounds checks unsafe { if self.ptr == self.end { None } else { let old = self.ptr; - self.ptr = self.ptr.offset($step); + self.ptr = self.ptr.offset(1); Some(cast::transmute(old)) } } @@ -2101,11 +2092,7 @@ macro_rules! iterator { #[inline] fn size_hint(&self) -> (uint, Option) { - let diff = if $step > 0 { - (self.end as uint) - (self.ptr as uint) - } else { - (self.ptr as uint) - (self.end as uint) - }; + let diff = (self.end as uint) - (self.ptr as uint); let exact = diff / size_of::<$elem>(); (exact, Some(exact)) } @@ -2113,6 +2100,25 @@ macro_rules! iterator { } } +macro_rules! double_ended_iterator { + (impl $name:ident -> $elem:ty) => { + impl<'self, T> DoubleEndedIterator<$elem> for $name<'self, T> { + #[inline] + fn next_back(&mut self) -> Option<$elem> { + // could be implemented with slices, but this avoids bounds checks + unsafe { + if self.end == self.ptr { + None + } else { + self.end = self.end.offset(-1); + Some(cast::transmute(self.end)) + } + } + } + } + } +} + //iterator!{struct VecIterator -> *T, &'self T} /// An iterator for iterating over a vector. pub struct VecIterator<'self, T> { @@ -2120,16 +2126,9 @@ pub struct VecIterator<'self, T> { priv end: *T, priv lifetime: &'self T // FIXME: #5922 } -iterator!{impl VecIterator -> &'self T, 1} - -//iterator!{struct VecRevIterator -> *T, &'self T} -/// An iterator for iterating over a vector in reverse. -pub struct VecRevIterator<'self, T> { - priv ptr: *T, - priv end: *T, - priv lifetime: &'self T // FIXME: #5922 -} -iterator!{impl VecRevIterator -> &'self T, -1} +iterator!{impl VecIterator -> &'self T} +double_ended_iterator!{impl VecIterator -> &'self T} +pub type VecRevIterator<'self, T> = InvertIterator<&'self T, VecIterator<'self, T>>; //iterator!{struct VecMutIterator -> *mut T, &'self mut T} /// An iterator for mutating the elements of a vector. @@ -2138,16 +2137,9 @@ pub struct VecMutIterator<'self, T> { priv end: *mut T, priv lifetime: &'self mut T // FIXME: #5922 } -iterator!{impl VecMutIterator -> &'self mut T, 1} - -//iterator!{struct VecMutRevIterator -> *mut T, &'self mut T} -/// An iterator for mutating the elements of a vector in reverse. -pub struct VecMutRevIterator<'self, T> { - priv ptr: *mut T, - priv end: *mut T, - priv lifetime: &'self mut T // FIXME: #5922 -} -iterator!{impl VecMutRevIterator -> &'self mut T, -1} +iterator!{impl VecMutIterator -> &'self mut T} +double_ended_iterator!{impl VecMutIterator -> &'self mut T} +pub type VecMutRevIterator<'self, T> = InvertIterator<&'self mut T, VecMutIterator<'self, T>>; /// An iterator that moves out of a vector. pub struct VecConsumeIterator { -- cgit 1.4.1-3-g733a5