//! A double-ended queue implemented using a `Vec` that reuses space after
//! elements are removed.
//!
//! The API is heavily based on `collections.deque` from Python.
//!
//! You can create a ring using any of the available constructors or the `ring!` macro.
//!
//! ```rust
//! # #[macro_use] extern crate ring_queue;
//!
//! use ring_queue::Ring;
//!
//! // `new` for an empty ring.
//! let r: Ring<i32> = Ring::new();
//!
//! // `with_capacity` for allocating the internal vector with the given
//! // capacity.
//! let r2: Ring<i32> = Ring::with_capacity(5);
//!
//! // `ring!` macro for easy initializing the ring.
//! let r3: Ring<i32> = ring![1, 2, 3];
//!
//! // `from_iter` to construct the ring from an iterator.
//! use std::iter::FromIterator;
//! let r4: Ring<i32> = Ring::from_iter(vec![1, 2, 3]);
//! ```
//!
//! Instead of `front` and `back` as a nomenclature, this library uses `left`
//! to refer to the front an nothing to refer to the back, as the Python
//! `collections.deque` library does.
//!
//! Items can be pushed to the left and right as well as popped.
//!
//! ```rust
//! # #[macro_use] extern crate ring_queue;
//!
//! use ring_queue::Ring;
//!
//! let mut r = ring![1, 2, 3];
//! r.push(4);
//! r.push_left(0);
//! assert_eq!(r.pop(), Some(4));
//! assert_eq!(r.pop_left(), Some(0));
//! ```
//!
//! The ring can be rotated either to the left or to the right. Any positive
//! number will rotate `n` steps to the right and any negative number will
//! rotate `n` steps to the left.
//!
//! ```rust
//! # #[macro_use] extern crate ring_queue;
//!
//! use ring_queue::Ring;
//!
//! let mut r = ring![1, 2, 3, 4, 5];
//!
//! r.rotate(1);
//! assert_eq!(r.collect_vec(), vec![5, 1, 2, 3, 4]);
//!
//! r.rotate(-2);
//! assert_eq!(r.collect_vec(), vec![2, 3, 4, 5, 1]);
//! ```
//!
//! Ring implements `collect` to collect the elements in the ring as a vector
//! if the type of the elements implement the `Copy` trait.
//!
//! ```rust
//! # #[macro_use] extern crate ring_queue;
//!
//! use ring_queue::Ring;
//!
//! let mut r = ring![1, 2, 3, 4];
//! assert_eq!(r.collect_vec(), vec![1, 2, 3, 4]);
//! ```
//!
//! It also implements `into_iter` to generate an iterator. However,
//! `into_iter` empties the ring unless the elements implement the `Copy` trait.
//!
//! ```rust
//! # #[macro_use] extern crate ring_queue;
//!
//! use ring_queue::Ring;
//!
//! #[derive(Debug)]
//! struct Foo { a: i32 }
//!
//! let mut r = ring![Foo{a: 1}, Foo{a: 2}];
//! assert_eq!(r.is_empty(), false);
//!
//! for item in r.into_iter() {
//! println!("{:?}", item);
//! }
//!
//! assert_eq!(r.is_empty(), true);
//!
//! let r2 = ring![1, 2, 3, 4];
//! assert_eq!(r2.is_empty(), false);
//!
//! for item in r2.into_iter() {
//! println!("{}", item);
//! }
//!
//! assert_eq!(r2.is_empty(), false);
//! ```
#[derive(Copy, Clone)]
struct Item<T> {
val: Option<T>,
prev: usize,
next: usize,
}
impl<T> Item<T> {
fn reverse(&mut self) {
let prev = self.prev;
self.prev = self.next;
self.next = prev;
}
}
#[macro_export]
macro_rules! ring {
() => ( $crate::Ring::new() );
($($x:expr),*) => (
{
let s: Box<[_]> = Box::new([$($x),*]);
let mut x = s.into_vec();
let mut r = Ring::new();
for i in x.drain(..) {
r.push(i);
}
r
}
);
($($x:expr,)*) => (ring![$($x),*])
}
/// Double-ended queue implemented with a vector that reuses space.
pub struct Ring<T> {
cur: Option<usize>,
items: Vec<Item<T>>,
gaps: Vec<usize>,
}
impl<T> Ring<T>
where
T: Sized,
{
/// Create a new empty `Ring`.
pub fn new() -> Ring<T> {
Ring {
items: Vec::new(),
cur: None,
gaps: Vec::new(),
}
}
/// Create a new empty `Ring` with a predefined capacity.
pub fn with_capacity(capacity: usize) -> Ring<T> {
Ring {
items: Vec::with_capacity(capacity),
cur: None,
gaps: Vec::new(),
}
}
/// Removes the value on the left side of the ring, that is, the head. It
/// will return the popped value, if there was any.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2];
/// assert_eq!(r.pop_left(), Some(1));
/// assert_eq!(r.pop_left(), Some(2));
/// assert_eq!(r.pop_left(), None);
/// # }
/// ```
pub fn pop_left(&mut self) -> Option<T> {
let mut val = None;
self.cur = self.cur.and_then(|c| {
let mut item = Item {
val: None,
next: 0,
prev: 0,
};
std::mem::swap(&mut item, &mut self.items[c]);
val = item.val;
// Remove the value from the item and push it to the gap list.
self.gaps.push(c);
// If the next item is this item, it means there is only one
// element in the ring, so return an empty cursor.
if item.next == c {
None
} else {
self.items[item.prev].next = item.next;
self.items[item.next].prev = item.prev;
Some(item.next)
}
});
val
}
/// Removes the value on the right side of the ring, that is, the tail. It
/// will return the popped value, if there was any.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2];
/// assert_eq!(r.pop(), Some(2));
/// assert_eq!(r.pop(), Some(1));
/// assert_eq!(r.pop(), None);
/// # }
/// ```
pub fn pop(&mut self) -> Option<T> {
match self.cur {
Some(c) => {
let head = self.items[c].prev;
let mut tail = Item {
val: None,
next: 0,
prev: 0,
};
std::mem::swap(&mut tail, &mut self.items[head]);
let val = tail.val;
// Remove the value from the node and push it to the gap list.
tail.val = None;
self.gaps.push(head);
// If the next node is this node, it means there is only one
// element in the ring, so return an empty cursor.
if tail.next != head {
self.items[tail.prev].next = tail.next;
self.items[tail.next].prev = tail.prev;
}
val
}
None => None,
}
}
#[inline]
fn push_item(&mut self, value: T) -> usize {
let (head, prev) = self.cur.map(|c| (c, self.items[c].prev)).unwrap_or((0, 0));
let item = Item {
val: Some(value),
next: head,
prev: prev,
};
let curr = if self.gaps.len() > 0 {
let idx = self.gaps.pop().unwrap();
self.items[idx] = item;
idx
} else {
self.items.push(item);
self.items.len() - 1
};
self.items[prev].next = curr;
self.items[head].prev = curr;
curr
}
/// Inserts a value at the right side of the queue, that is, at the tail.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2, 3];
/// r.push(4);
/// assert_eq!(r.collect_vec(), vec![1, 2, 3, 4]);
/// # }
/// ```
pub fn push(&mut self, value: T) {
let idx = self.push_item(value);
self.cur = self.cur.or(Some(idx));
}
/// Inserts a value at the left side of the queue, that is, at the head.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2, 3];
/// r.push_left(0);
/// assert_eq!(r.collect_vec(), vec![0, 1, 2, 3]);
/// # }
/// ```
pub fn push_left(&mut self, value: T) {
let curr = self.push_item(value);
self.cur = Some(curr);
}
#[inline]
fn rotate_left(&mut self, n: isize) {
self.cur = self.cur.map(|c| {
let mut cur = c;
for _ in n..0 {
cur = self.items[cur].next;
}
cur
});
}
#[inline]
fn rotate_right(&mut self, n: isize) {
self.cur = self.cur.map(|c| {
let mut cur = c;
for _ in 0..n {
cur = self.items[cur].prev;
}
cur
});
}
/// Rotate the deque `n` steps to the right. If `n` is negative, rotate to
/// the left.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2, 3, 4, 5];
///
/// r.rotate(1);
/// assert_eq!(r.collect_vec(), vec![5, 1, 2, 3, 4]);
///
/// r.rotate(-2);
/// assert_eq!(r.collect_vec(), vec![2, 3, 4, 5, 1]);
/// # }
/// ```
pub fn rotate(&mut self, n: isize) -> &mut Self {
if n > 0 {
self.rotate_right(n);
} else if n < 0 {
self.rotate_left(n);
}
self
}
#[inline]
fn peek_left(&self, cur: usize, n: isize) -> Option<&T> {
let mut c = cur;
for _ in n..0 {
c = self.items[c].prev;
}
self.items[c].val.as_ref()
}
#[inline]
fn peek_right(&self, cur: usize, n: isize) -> Option<&T> {
let mut c = cur;
for _ in 0..n {
c = self.items[c].next;
}
self.items[c].val.as_ref()
}
/// Retrieve the element `n` steps to the right from the head. If `n` is
/// negative, the element `n` steps to the left from the head.
/// This method can only be used if the element type implements the `Copy`
/// trait.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let r = ring![1, 2, 3, 4, 5];
/// assert_eq!(r.peek(0), Some(&1));
/// assert_eq!(r.peek(1), Some(&2));
/// assert_eq!(r.peek(-1), Some(&5));
/// # }
/// ```
pub fn peek(&self, n: isize) -> Option<&T> {
match self.cur {
Some(cur) => {
if n < 0 {
self.peek_left(cur, n)
} else {
self.peek_right(cur, n)
}
}
None => None,
}
}
/// Returns the length of the ring.
pub fn len(&self) -> usize {
self.items.len() - self.gaps.len()
}
/// Returns the current capacity of the ring.
pub fn capacity(&self) -> usize {
self.items.capacity()
}
/// Clears the ring, removing all values.
/// Note that this method has no effect on its allocated capacity.
///
/// # Example
///
/// ```
/// use ring_queue::Ring;
///
/// let mut r = Ring::with_capacity(5);
/// r.push(1);
///
/// r.clear();
/// assert_eq!(r.len(), 0);
/// assert_eq!(r.capacity(), 5);
/// ```
pub fn clear(&mut self) {
self.cur = None;
self.gaps.clear();
self.items.clear();
}
/// Moves all the elements of `other` into the right of `Self`, leaving
/// `other` empty.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2, 3];
/// r.append(&mut ring![4, 5, 6]);
/// assert_eq!(r.collect_vec(), vec![1, 2, 3, 4, 5, 6]);
/// # }
/// ```
pub fn append(&mut self, other: &mut Ring<T>) {
for item in other.into_iter() {
self.push(item);
}
}
/// Moves all the elements of `other` into the left of `Self`, leaving
/// `other` empty.
/// Note that elements will be appended to the left in reverse with the
/// same order they had in the other ring. That means they will be, in
/// fact, in reverse order.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![4, 5, 6];
/// r.append_left(&mut ring![3, 2, 1]);
/// assert_eq!(r.collect_vec(), vec![1, 2, 3, 4, 5, 6]);
/// # }
/// ```
pub fn append_left(&mut self, other: &mut Ring<T>) {
for item in other.into_iter() {
self.push_left(item);
}
}
/// Reverses the elements in the ring.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let mut r = ring![1, 2, 3];
/// r.reverse();
/// assert_eq!(r.collect_vec(), vec![3, 2, 1]);
/// # }
/// ```
pub fn reverse(&mut self) {
self.cur = self.cur.map(|cur| {
let mut c = cur;
let tail = self.items[c].prev;
loop {
let next = self.items[c].next;
self.items[c].reverse();
if next == cur {
break;
}
c = next;
}
tail
});
}
/// Returns whether the ring is empty or not.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// assert_eq!(ring![1, 2, 3].is_empty(), false);
/// assert_eq!(Ring::<i32>::new().is_empty(), true);
/// # }
/// ```
pub fn is_empty(&self) -> bool {
self.cur.is_none()
}
/// Return all the elements inside the ring as a vector. In order to use
/// this method, the element type needs to implement the `Copy` trait.
///
/// # Example
///
/// ```
/// # #[macro_use] extern crate ring_queue;
/// # fn main() {
/// use ring_queue::Ring;
///
/// let r = ring![1, 2, 3];
/// assert_eq!(r.collect_vec(), vec![1, 2, 3]);
/// # }
/// ```
pub fn collect_vec(&self) -> Vec<T>
where
T: Copy,
{
let mut v = Vec::with_capacity(self.len());
match self.cur {
Some(cur) => {
let mut c = cur;
loop {
let item = self.items[c];
v.push(item.val.unwrap());
c = item.next;
if c == cur {
break;
}
}
}
None => (),
}
v
}
}
impl<'a, T> std::iter::IntoIterator for &'a Ring<T> where T: Copy {
type Item = T;
type IntoIter = Iter<'a, T>;
/// Creates an iterator that will not consume the current ring. It will,
/// instead, copy the elements one by one to the iterator.
///
/// # Examples
///
/// ```
/// use ring_queue::Ring;
///
/// let mut r = Ring::new();
/// r.push(1);
/// r.push(2);
///
/// for i in r.into_iter() {
/// println!("{}", i);
/// }
///
/// // r is not empty now
/// ```
fn into_iter(self) -> Self::IntoIter {
Iter {
items: &self.items,
head: self.cur.clone(),
pos: self.cur.clone(),
}
}
}
impl<'a, T> std::iter::IntoIterator for &'a mut Ring<T> {
type Item = T;
type IntoIter = IterMut<T>;
/// Creates a consuming iterator, that is, one that moves each value out of
/// the ring (from head to tail). The ring will be empty.
///
/// # Examples
///
/// ```
/// use ring_queue::Ring;
///
/// struct Foo { a: i32 }
///
/// let mut r = Ring::new();
/// r.push(Foo{a: 1});
/// r.push(Foo{a: 2});
///
/// for i in r.into_iter() {
/// println!("{}", i.a);
/// }
///
/// // r is empty now
/// ```
fn into_iter(self) -> Self::IntoIter {
let mut items = Vec::new();
let mut cur = None;
std::mem::swap(&mut items, &mut self.items);
std::mem::swap(&mut cur, &mut self.cur);
self.items.clear();
IterMut {
items: items,
head: cur,
pos: cur,
}
}
}
impl<T> Clone for Ring<T>
where
T: std::clone::Clone,
{
fn clone(&self) -> Self {
Ring {
cur: self.cur,
items: self.items.clone(),
gaps: self.gaps.clone(),
}
}
}
pub struct Iter<'a, T: Copy> {
items: &'a Vec<Item<T>>,
head: Option<usize>,
pos: Option<usize>,
}
impl<'a, T: Copy> Iterator for Iter<'a, T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let mut val = None;
self.pos = self.pos.and_then(|pos| {
let item = self.items[pos];
val = item.val;
if item.next == self.head.unwrap() {
None
} else {
Some(item.next)
}
});
val
}
}
pub struct IterMut<T> {
items: Vec<Item<T>>,
head: Option<usize>,
pos: Option<usize>,
}
impl<T> Iterator for IterMut<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let mut val = None;
self.pos = self.pos.and_then(|pos| {
let mut item = Item {
val: None,
next: 0,
prev: 0,
};
std::mem::swap(&mut item, &mut self.items[pos]);
val = item.val;
if item.next == self.head.unwrap() {
None
} else {
Some(item.next)
}
});
val
}
}
impl<T> std::iter::FromIterator<T> for Ring<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut ring = Ring::new();
for item in iter {
ring.push(item);
}
ring
}
}
use std::fmt;
impl<T: fmt::Debug + Copy> fmt::Debug for Ring<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.write_str("[")?;
match self.cur {
Some(cur) => {
let mut next = cur;
loop {
f.write_fmt(format_args!("{:?}", self.items[next].val.unwrap()))?;
next = self.items[next].next;
if next == cur {
break;
} else {
f.write_str(", ")?;
}
}
}
None => (),
}
f.write_str("]")
}
}
impl<T> std::ops::Index<isize> for Ring<T> {
type Output = T;
fn index(&self, idx: isize) -> &T {
match self.peek(idx) {
Some(r) => r,
None => panic!("tried to access index {} of empty ring", idx),
}
}
}
impl<T: PartialEq> PartialEq for Ring<T> {
fn eq(&self, other: &Ring<T>) -> bool {
if self.len() != other.len() {
return false;
}
let cur = self.cur.unwrap();
let cur2 = other.cur.unwrap();
let mut next = cur;
let mut next2 = cur2;
loop {
let v = &self.items[next].val;
let v2 = &other.items[next2].val;
if v != v2 {
return false;
}
if next == cur && next2 == cur2 {
break;
} else if next == cur || next2 == cur2 {
return false;
}
next = self.items[next].next;
next2 = other.items[next2].next;
}
true
}
}
impl<T: Eq> Eq for Ring<T> {}
#[cfg(test)]
mod tests {
use super::*;
use std::iter::FromIterator;
#[test]
fn test_push() {
let mut r = ring![1, 2];
r.push(3);
assert_eq!(r.collect_vec(), vec![1, 2, 3]);
r.push_left(0);
assert_eq!(r.collect_vec(), vec![0, 1, 2, 3]);
}
#[test]
fn test_debug() {
let r = ring![1, 2, 3];
assert_eq!("[1, 2, 3]", format!("{:?}", r));
}
#[test]
fn test_iter_copyable() {
let r = ring![1, 2, 3];
let mut iter = r.into_iter();
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), None);
assert_eq!(r.len(), 3);
}
#[test]
fn test_iter_nocopyable() {
let mut r = ring![vec![1, 2], vec![3, 4]];
let mut iter = r.into_iter();
assert_eq!(iter.next(), Some(vec![1, 2]));
assert_eq!(iter.next(), Some(vec![3, 4]));
assert_eq!(iter.next(), None);
assert_eq!(r.is_empty(), true);
}
#[test]
fn test_collect() {
let r = ring![1, 2, 3];
assert_eq!(vec![1, 2, 3], r.collect_vec());
}
#[test]
fn test_from_iter() {
let r = Ring::from_iter(vec![1, 2, 3]);
assert_eq!(vec![1, 2, 3], r.collect_vec());
}
#[test]
fn test_peek() {
let r = ring![1, 2, 3, 4];
assert_eq!(r.peek(0), Some(&1));
assert_eq!(r.peek(1), Some(&2));
assert_eq!(r.peek(4), Some(&1));
assert_eq!(r.peek(-1), Some(&4));
assert_eq!(r.peek(-1), Some(&4));
assert_eq!(r.peek(-6), Some(&3));
}
#[test]
fn test_rotate() {
let mut r1 = ring![1, 2, 3, 4];
assert_eq!(r1.rotate(1).collect_vec(), vec![4, 1, 2, 3]);
let mut r2 = ring![1, 2, 3, 4];
assert_eq!(r2.rotate(0).collect_vec(), vec![1, 2, 3, 4]);
let mut r3 = ring![1, 2, 3, 4];
assert_eq!(r3.rotate(-1).collect_vec(), vec![2, 3, 4, 1]);
}
#[test]
fn test_pop() {
let mut r = ring![1, 2, 3, 4];
assert_eq!(r.pop(), Some(4));
assert_eq!(r.pop_left(), Some(1));
assert_eq!(r.collect_vec(), vec![2, 3]);
}
#[test]
fn test_len() {
let r = ring![1, 2, 3, 4];
assert_eq!(r.len(), 4);
}
#[test]
fn test_capacity() {
let r: Ring<i32> = Ring::with_capacity(6);
assert_eq!(r.capacity(), 6);
assert_eq!(r.len(), 0);
}
#[test]
fn test_clear() {
let mut r = Ring::with_capacity(5);
r.push(1);
r.push(2);
r.push(3);
assert_eq!(r.len(), 3);
assert_eq!(r.capacity(), 5);
r.clear();
assert_eq!(r.len(), 0);
assert_eq!(r.capacity(), 5);
}
#[test]
fn test_push_with_gaps() {
let mut r = ring![1, 2, 3, 4, 5];
assert_eq!(r.rotate(-1).pop_left(), Some(2));
assert_eq!(r.gaps.len(), 1);
r.push(6);
assert_eq!(r.gaps.len(), 0);
assert_eq!(r.items[1].val, Some(6));
r.push_left(7);
assert_eq!(r.collect_vec(), vec![7, 3, 4, 5, 1, 6]);
}
#[test]
fn test_append() {
let mut r = ring![1, 2, 3];
r.append(&mut ring![4, 5, 6]);
assert_eq!(r.collect_vec(), vec![1, 2, 3, 4, 5, 6]);
r.append_left(&mut ring![7, 8, 9]);
assert_eq!(r.collect_vec(), vec![9, 8, 7, 1, 2, 3, 4, 5, 6]);
}
#[test]
fn test_reverse() {
let mut r = ring![1, 2, 3];
r.reverse();
assert_eq!(r.collect_vec(), vec![3, 2, 1]);
}
#[test]
fn test_is_empty() {
let mut r = Ring::new();
assert_eq!(r.is_empty(), true);
r.push(1);
assert_eq!(r.is_empty(), false);
r.clear();
assert_eq!(r.is_empty(), true);
}
#[test]
fn test_macro_nocopy() {
let r = ring![vec![1, 2, 3]];
assert_eq!(r.is_empty(), false);
}
#[test]
fn test_eq() {
let r = ring![1, 2, 3];
assert_eq!(r == ring![1, 2], false);
assert_eq!(r == ring![1, 2, 3], true);
assert_eq!(r == ring![], false);
assert_eq!(r != ring![1, 2], true);
assert_eq!(r != ring![1, 2, 3], false);
assert_eq!(r != ring![], true);
}
#[test]
fn test_index() {
let r = ring![1, 2, 3];
assert_eq!(r[0], 1);
assert_eq!(r[1], 2);
assert_eq!(r[-1], 3);
}
}