//! This crate implements a double-ended queue with `O(1)` amortized inserts and removals from both
//! ends of the container. It also has `O(1)` indexing like a vector. The contained elements are
//! not required to be copyable, and the queue will be sendable if the contained type is sendable.
-//! Its interface `Deque` is defined in `collections`.
use core::prelude::*;
// FIXME(conventions): implement shrink_to_fit. Awkward with the current design, but it should
// be scrapped anyway. Defer to rewrite?
-// FIXME(conventions): implement into_iter
-
-/// `RingBuf` is a circular buffer that implements `Deque`.
+/// `RingBuf` is a circular buffer.
pub struct RingBuf<T> {
// tail and head are pointers into the buffer. Tail always points
// to the first element that could be read, Head always points
}
}
+ /// Consumes the list into an iterator yielding elements by value.
+ #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ pub fn into_iter(self) -> MoveItems<T> {
+ MoveItems {
+ inner: self,
+ }
+ }
+
/// Returns the number of elements in the `RingBuf`.
///
/// # Example
}
}
-
-impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
+impl<'a, T> ExactSizeIterator<&'a T> for Items<'a, T> {}
impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
#[inline]
}
let tail = self.tail;
self.tail = wrap_index(self.tail + 1, self.cap);
- if mem::size_of::<T>() != 0 {
- unsafe { Some(&mut *self.ptr.offset(tail as int)) }
- } else {
- // use a non-zero pointer
- Some(unsafe { mem::transmute(1u) })
+
+ unsafe {
+ Some(&mut *self.ptr.offset(tail as int))
}
}
return None;
}
self.head = wrap_index(self.head - 1, self.cap);
- unsafe { Some(&mut *self.ptr.offset(self.head as int)) }
+
+ unsafe {
+ Some(&mut *self.ptr.offset(self.head as int))
+ }
}
}
-impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
+impl<'a, T> ExactSizeIterator<&'a mut T> for MutItems<'a, T> {}
+
+// A by-value RingBuf iterator
+pub struct MoveItems<T> {
+ inner: RingBuf<T>,
+}
+
+impl<T> Iterator<T> for MoveItems<T> {
+ #[inline]
+ fn next(&mut self) -> Option<T> {
+ self.inner.pop_front()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (uint, Option<uint>) {
+ let len = self.inner.len();
+ (len, Some(len))
+ }
+}
+
+impl<T> DoubleEndedIterator<T> for MoveItems<T> {
+ #[inline]
+ fn next_back(&mut self) -> Option<T> {
+ self.inner.pop_back()
+ }
+}
+
+
+impl<T> ExactSizeIterator<T> for MoveItems<T> {}
impl<A: PartialEq> PartialEq for RingBuf<A> {
fn eq(&self, other: &RingBuf<A>) -> bool {
}
{
let b: &[_] = &[&0,&1,&2,&3,&4];
- assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
+ assert_eq!(d.iter().collect::<Vec<&int>>(), b);
}
for i in range(6i, 9) {
}
{
let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
- assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
+ assert_eq!(d.iter().collect::<Vec<&int>>(), b);
}
let mut it = d.iter();
}
{
let b: &[_] = &[&4,&3,&2,&1,&0];
- assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
+ assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
}
for i in range(6i, 9) {
d.push_front(i);
}
let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
- assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
+ assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
}
#[test]
}
}
+ #[test]
+ fn test_into_iter() {
+
+ // Empty iter
+ {
+ let d: RingBuf<int> = RingBuf::new();
+ let mut iter = d.into_iter();
+
+ assert_eq!(iter.size_hint(), (0, Some(0)));
+ assert_eq!(iter.next(), None);
+ assert_eq!(iter.size_hint(), (0, Some(0)));
+ }
+
+ // simple iter
+ {
+ let mut d = RingBuf::new();
+ for i in range(0i, 5) {
+ d.push_back(i);
+ }
+
+ let b = vec![0,1,2,3,4];
+ assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
+ }
+
+ // wrapped iter
+ {
+ let mut d = RingBuf::new();
+ for i in range(0i, 5) {
+ d.push_back(i);
+ }
+ for i in range(6, 9) {
+ d.push_front(i);
+ }
+
+ let b = vec![8,7,6,0,1,2,3,4];
+ assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
+ }
+
+ // partially used
+ {
+ let mut d = RingBuf::new();
+ for i in range(0i, 5) {
+ d.push_back(i);
+ }
+ for i in range(6, 9) {
+ d.push_front(i);
+ }
+
+ let mut it = d.into_iter();
+ assert_eq!(it.size_hint(), (8, Some(8)));
+ assert_eq!(it.next(), Some(8));
+ assert_eq!(it.size_hint(), (7, Some(7)));
+ assert_eq!(it.next_back(), Some(4));
+ assert_eq!(it.size_hint(), (6, Some(6)));
+ assert_eq!(it.next(), Some(7));
+ assert_eq!(it.size_hint(), (5, Some(5)));
+ }
+ }
+
#[test]
fn test_from_iter() {
use std::iter;
let u: Vec<int> = deq.iter().map(|&x| x).collect();
assert_eq!(u, v);
- let mut seq = iter::count(0u, 2).take(256);
+ let seq = iter::count(0u, 2).take(256);
let deq: RingBuf<uint> = seq.collect();
for (i, &x) in deq.iter().enumerate() {
assert_eq!(2*i, x);
#[test]
fn test_show() {
let ringbuf: RingBuf<int> = range(0i, 10).collect();
- assert!(format!("{}", ringbuf).as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+ assert!(format!("{}", ringbuf) == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
.map(|&s| s)
.collect();
- assert!(format!("{}", ringbuf).as_slice() == "[just, one, test, more]");
+ assert!(format!("{}", ringbuf) == "[just, one, test, more]");
}
#[test]
projects / rust.git / blobdiff