1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A double-ended queue implemented as a circular buffer
13 //! RingBuf implements the trait Deque. It should be imported with `use
14 //! collections::Deque`.
19 use core::default::Default;
21 use core::iter::RandomAccessIterator;
23 use {Deque, Collection, Mutable};
26 static INITIAL_CAPACITY: uint = 8u; // 2^3
27 static MINIMUM_CAPACITY: uint = 2u;
29 /// RingBuf is a circular buffer that implements Deque.
31 pub struct RingBuf<T> {
37 impl<T> Collection for RingBuf<T> {
38 /// Return the number of elements in the RingBuf
39 fn len(&self) -> uint { self.nelts }
42 impl<T> Mutable for RingBuf<T> {
43 /// Clear the RingBuf, removing all values.
45 for x in self.elts.mut_iter() { *x = None }
51 impl<T> Deque<T> for RingBuf<T> {
52 /// Return a reference to the first element in the RingBuf
53 fn front<'a>(&'a self) -> Option<&'a T> {
54 if self.nelts > 0 { Some(self.get(0)) } else { None }
57 /// Return a mutable reference to the first element in the RingBuf
58 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
59 if self.nelts > 0 { Some(self.get_mut(0)) } else { None }
62 /// Return a reference to the last element in the RingBuf
63 fn back<'a>(&'a self) -> Option<&'a T> {
64 if self.nelts > 0 { Some(self.get(self.nelts - 1)) } else { None }
67 /// Return a mutable reference to the last element in the RingBuf
68 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
69 let nelts = self.nelts;
70 if nelts > 0 { Some(self.get_mut(nelts - 1)) } else { None }
73 /// Remove and return the first element in the RingBuf, or None if it is empty
74 fn pop_front(&mut self) -> Option<T> {
75 let result = self.elts.get_mut(self.lo).take();
77 self.lo = (self.lo + 1u) % self.elts.len();
83 /// Remove and return the last element in the RingBuf, or None if it is empty
84 fn pop_back(&mut self) -> Option<T> {
87 let hi = self.raw_index(self.nelts);
88 self.elts.get_mut(hi).take()
94 /// Prepend an element to the RingBuf
95 fn push_front(&mut self, t: T) {
96 if self.nelts == self.elts.len() {
97 grow(self.nelts, &mut self.lo, &mut self.elts);
100 self.lo = self.elts.len() - 1u;
101 } else { self.lo -= 1u; }
102 *self.elts.get_mut(self.lo) = Some(t);
106 /// Append an element to the RingBuf
107 fn push_back(&mut self, t: T) {
108 if self.nelts == self.elts.len() {
109 grow(self.nelts, &mut self.lo, &mut self.elts);
111 let hi = self.raw_index(self.nelts);
112 *self.elts.get_mut(hi) = Some(t);
117 impl<T> Default for RingBuf<T> {
119 fn default() -> RingBuf<T> { RingBuf::new() }
123 /// Create an empty RingBuf
124 pub fn new() -> RingBuf<T> {
125 RingBuf::with_capacity(INITIAL_CAPACITY)
128 /// Create an empty RingBuf with space for at least `n` elements.
129 pub fn with_capacity(n: uint) -> RingBuf<T> {
130 RingBuf{nelts: 0, lo: 0,
131 elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
134 /// Retrieve an element in the RingBuf by index
136 /// Fails if there is no element with the given index
137 pub fn get<'a>(&'a self, i: uint) -> &'a T {
138 let idx = self.raw_index(i);
139 match *self.elts.get(idx) {
145 /// Retrieve an element in the RingBuf by index
147 /// Fails if there is no element with the given index
148 pub fn get_mut<'a>(&'a mut self, i: uint) -> &'a mut T {
149 let idx = self.raw_index(i);
150 match *self.elts.get_mut(idx) {
156 /// Swap elements at indices `i` and `j`
158 /// `i` and `j` may be equal.
160 /// Fails if there is no element with the given index
161 pub fn swap(&mut self, i: uint, j: uint) {
162 assert!(i < self.len());
163 assert!(j < self.len());
164 let ri = self.raw_index(i);
165 let rj = self.raw_index(j);
166 self.elts.as_mut_slice().swap(ri, rj);
169 /// Return index in underlying vec for a given logical element index
170 fn raw_index(&self, idx: uint) -> uint {
171 raw_index(self.lo, self.elts.len(), idx)
174 /// Reserve capacity for exactly `n` elements in the given RingBuf,
175 /// doing nothing if `self`'s capacity is already equal to or greater
176 /// than the requested capacity
180 /// * n - The number of elements to reserve space for
181 pub fn reserve_exact(&mut self, n: uint) {
182 self.elts.reserve_exact(n);
185 /// Reserve capacity for at least `n` elements in the given RingBuf,
186 /// over-allocating in case the caller needs to reserve additional
189 /// Do nothing if `self`'s capacity is already equal to or greater
190 /// than the requested capacity.
194 /// * n - The number of elements to reserve space for
195 pub fn reserve(&mut self, n: uint) {
196 self.elts.reserve(n);
199 /// Front-to-back iterator.
200 pub fn iter<'a>(&'a self) -> Items<'a, T> {
201 Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
204 /// Front-to-back iterator which returns mutable values.
205 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
206 let start_index = raw_index(self.lo, self.elts.len(), 0);
207 let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
209 // Divide up the array
210 if end_index <= start_index {
211 // Items to iterate goes from:
212 // start_index to self.elts.len()
215 let (temp, remaining1) = self.elts.mut_split_at(start_index);
216 let (remaining2, _) = temp.mut_split_at(end_index);
217 MutItems { remaining1: remaining1,
218 remaining2: remaining2,
221 // Items to iterate goes from start_index to end_index:
222 let (empty, elts) = self.elts.mut_split_at(0);
223 let remaining1 = elts.mut_slice(start_index, end_index);
224 MutItems { remaining1: remaining1,
232 pub struct Items<'a, T> {
236 elts: &'a [Option<T>],
239 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
241 fn next(&mut self) -> Option<&'a T> {
242 if self.index == self.rindex {
245 let raw_index = raw_index(self.lo, self.elts.len(), self.index);
247 Some(self.elts[raw_index].get_ref())
251 fn size_hint(&self) -> (uint, Option<uint>) {
252 let len = self.rindex - self.index;
257 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
259 fn next_back(&mut self) -> Option<&'a T> {
260 if self.index == self.rindex {
264 let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
265 Some(self.elts[raw_index].get_ref())
269 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
271 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
273 fn indexable(&self) -> uint { self.rindex - self.index }
276 fn idx(&mut self, j: uint) -> Option<&'a T> {
277 if j >= self.indexable() {
280 let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
281 Some(self.elts[raw_index].get_ref())
286 /// RingBuf mutable iterator
287 pub struct MutItems<'a, T> {
288 remaining1: &'a mut [Option<T>],
289 remaining2: &'a mut [Option<T>],
293 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
295 fn next(&mut self) -> Option<&'a mut T> {
299 let r = if self.remaining1.len() > 0 {
302 assert!(self.remaining2.len() > 0);
306 Some(r.mut_shift_ref().unwrap().get_mut_ref())
310 fn size_hint(&self) -> (uint, Option<uint>) {
311 (self.nelts, Some(self.nelts))
315 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
317 fn next_back(&mut self) -> Option<&'a mut T> {
321 let r = if self.remaining2.len() > 0 {
324 assert!(self.remaining1.len() > 0);
328 Some(r.mut_pop_ref().unwrap().get_mut_ref())
332 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
334 /// Grow is only called on full elts, so nelts is also len(elts), unlike
336 fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
337 assert_eq!(nelts, elts.len());
339 let newlen = nelts * 2;
340 elts.reserve(newlen);
343 for _ in range(elts.len(), elts.capacity()) {
348 Move the shortest half into the newly reserved area.
352 A [. . .|o o o o o o o o|. . . . .]
353 B [o o o|. . . . . . . .|o o o o o]
356 assert!(newlen - nelts/2 >= nelts);
357 if lo <= (nelts - lo) { // A
358 for i in range(0u, lo) {
359 elts.as_mut_slice().swap(i, nelts + i);
362 for i in range(lo, nelts) {
363 elts.as_mut_slice().swap(i, newlen - nelts + i);
365 *loptr += newlen - nelts;
369 /// Return index in underlying vec for a given logical element index
370 fn raw_index(lo: uint, len: uint, index: uint) -> uint {
371 if lo >= len - index {
378 impl<A: PartialEq> PartialEq for RingBuf<A> {
379 fn eq(&self, other: &RingBuf<A>) -> bool {
380 self.nelts == other.nelts &&
381 self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
383 fn ne(&self, other: &RingBuf<A>) -> bool {
388 impl<A> FromIterator<A> for RingBuf<A> {
389 fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
390 let (lower, _) = iterator.size_hint();
391 let mut deq = RingBuf::with_capacity(lower);
392 deq.extend(iterator);
397 impl<A> Extendable<A> for RingBuf<A> {
398 fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
399 for elt in iterator {
405 impl<T: fmt::Show> fmt::Show for RingBuf<T> {
406 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
407 try!(write!(f, "["));
409 for (i, e) in self.iter().enumerate() {
410 if i != 0 { try!(write!(f, ", ")); }
411 try!(write!(f, "{}", *e));
422 use std::gc::{GC, Gc};
426 use {Deque, Mutable};
432 let mut d = RingBuf::new();
433 assert_eq!(d.len(), 0u);
437 assert_eq!(d.len(), 3u);
439 assert_eq!(d.len(), 4u);
440 debug!("{:?}", d.front());
441 assert_eq!(*d.front().unwrap(), 42);
442 debug!("{:?}", d.back());
443 assert_eq!(*d.back().unwrap(), 137);
444 let mut i = d.pop_front();
446 assert_eq!(i, Some(42));
449 assert_eq!(i, Some(137));
452 assert_eq!(i, Some(137));
455 assert_eq!(i, Some(17));
456 assert_eq!(d.len(), 0u);
458 assert_eq!(d.len(), 1u);
460 assert_eq!(d.len(), 2u);
462 assert_eq!(d.len(), 3u);
464 assert_eq!(d.len(), 4u);
465 debug!("{:?}", d.get(0));
466 debug!("{:?}", d.get(1));
467 debug!("{:?}", d.get(2));
468 debug!("{:?}", d.get(3));
469 assert_eq!(*d.get(0), 1);
470 assert_eq!(*d.get(1), 2);
471 assert_eq!(*d.get(2), 3);
472 assert_eq!(*d.get(3), 4);
477 let a: Gc<int> = box(GC) 5;
478 let b: Gc<int> = box(GC) 72;
479 let c: Gc<int> = box(GC) 64;
480 let d: Gc<int> = box(GC) 175;
482 let mut deq = RingBuf::new();
483 assert_eq!(deq.len(), 0);
487 assert_eq!(deq.len(), 3);
489 assert_eq!(deq.len(), 4);
490 assert_eq!(deq.front(), Some(&b));
491 assert_eq!(deq.back(), Some(&d));
492 assert_eq!(deq.pop_front(), Some(b));
493 assert_eq!(deq.pop_back(), Some(d));
494 assert_eq!(deq.pop_back(), Some(c));
495 assert_eq!(deq.pop_back(), Some(a));
496 assert_eq!(deq.len(), 0);
498 assert_eq!(deq.len(), 1);
500 assert_eq!(deq.len(), 2);
502 assert_eq!(deq.len(), 3);
504 assert_eq!(deq.len(), 4);
505 assert_eq!(*deq.get(0), a);
506 assert_eq!(*deq.get(1), b);
507 assert_eq!(*deq.get(2), c);
508 assert_eq!(*deq.get(3), d);
512 fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
513 let mut deq = RingBuf::new();
514 assert_eq!(deq.len(), 0);
515 deq.push_front(a.clone());
516 deq.push_front(b.clone());
517 deq.push_back(c.clone());
518 assert_eq!(deq.len(), 3);
519 deq.push_back(d.clone());
520 assert_eq!(deq.len(), 4);
521 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
522 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
523 assert_eq!(deq.pop_front().unwrap(), b.clone());
524 assert_eq!(deq.pop_back().unwrap(), d.clone());
525 assert_eq!(deq.pop_back().unwrap(), c.clone());
526 assert_eq!(deq.pop_back().unwrap(), a.clone());
527 assert_eq!(deq.len(), 0);
528 deq.push_back(c.clone());
529 assert_eq!(deq.len(), 1);
530 deq.push_front(b.clone());
531 assert_eq!(deq.len(), 2);
532 deq.push_back(d.clone());
533 assert_eq!(deq.len(), 3);
534 deq.push_front(a.clone());
535 assert_eq!(deq.len(), 4);
536 assert_eq!((*deq.get(0)).clone(), a.clone());
537 assert_eq!((*deq.get(1)).clone(), b.clone());
538 assert_eq!((*deq.get(2)).clone(), c.clone());
539 assert_eq!((*deq.get(3)).clone(), d.clone());
543 fn test_push_front_grow() {
544 let mut deq = RingBuf::new();
545 for i in range(0u, 66) {
548 assert_eq!(deq.len(), 66);
550 for i in range(0u, 66) {
551 assert_eq!(*deq.get(i), 65 - i);
554 let mut deq = RingBuf::new();
555 for i in range(0u, 66) {
559 for i in range(0u, 66) {
560 assert_eq!(*deq.get(i), i);
565 fn bench_new(b: &mut test::Bencher) {
567 let _: RingBuf<u64> = RingBuf::new();
572 fn bench_push_back(b: &mut test::Bencher) {
573 let mut deq = RingBuf::new();
580 fn bench_push_front(b: &mut test::Bencher) {
581 let mut deq = RingBuf::new();
588 fn bench_grow(b: &mut test::Bencher) {
589 let mut deq = RingBuf::new();
591 for _ in range(0i, 65) {
597 #[deriving(Clone, PartialEq, Show)]
601 Three(int, int, int),
604 #[deriving(Clone, PartialEq, Show)]
608 Threepar(int, int, int),
611 #[deriving(Clone, PartialEq, Show)]
619 fn test_param_int() {
620 test_parameterized::<int>(5, 72, 64, 175);
624 fn test_param_at_int() {
625 test_parameterized::<Gc<int>>(box(GC) 5, box(GC) 72,
626 box(GC) 64, box(GC) 175);
630 fn test_param_taggy() {
631 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
635 fn test_param_taggypar() {
636 test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
638 Threepar::<int>(1, 2, 3),
639 Twopar::<int>(17, 42));
643 fn test_param_reccy() {
644 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
645 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
646 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
647 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
648 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
652 fn test_with_capacity() {
653 let mut d = RingBuf::with_capacity(0);
655 assert_eq!(d.len(), 1);
656 let mut d = RingBuf::with_capacity(50);
658 assert_eq!(d.len(), 1);
662 fn test_reserve_exact() {
663 let mut d = RingBuf::new();
666 assert_eq!(d.elts.capacity(), 50);
667 let mut d = RingBuf::new();
670 assert_eq!(d.elts.capacity(), 50);
675 let mut d = RingBuf::new();
678 assert_eq!(d.elts.capacity(), 64);
679 let mut d = RingBuf::new();
682 assert_eq!(d.elts.capacity(), 64);
687 let mut d: RingBuf<int> = range(0i, 5).collect();
690 assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
695 let mut d = RingBuf::new();
696 assert_eq!(d.iter().next(), None);
697 assert_eq!(d.iter().size_hint(), (0, Some(0)));
699 for i in range(0i, 5) {
702 assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&0,&1,&2,&3,&4]);
704 for i in range(6i, 9) {
707 assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&8,&7,&6,&0,&1,&2,&3,&4]);
709 let mut it = d.iter();
710 let mut len = d.len();
714 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
721 let mut d = RingBuf::new();
722 assert_eq!(d.iter().rev().next(), None);
724 for i in range(0i, 5) {
727 assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0]);
729 for i in range(6i, 9) {
732 assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0,&6,&7,&8]);
736 fn test_mut_rev_iter_wrap() {
737 let mut d = RingBuf::with_capacity(3);
738 assert!(d.mut_iter().rev().next().is_none());
743 assert_eq!(d.pop_front(), Some(1));
746 assert_eq!(d.mut_iter().rev().map(|x| *x).collect::<Vec<int>>(),
752 let mut d = RingBuf::new();
753 assert!(d.mut_iter().next().is_none());
755 for i in range(0u, 3) {
759 for (i, elt) in d.mut_iter().enumerate() {
760 assert_eq!(*elt, 2 - i);
765 let mut it = d.mut_iter();
766 assert_eq!(*it.next().unwrap(), 0);
767 assert_eq!(*it.next().unwrap(), 1);
768 assert_eq!(*it.next().unwrap(), 2);
769 assert!(it.next().is_none());
774 fn test_mut_rev_iter() {
775 let mut d = RingBuf::new();
776 assert!(d.mut_iter().rev().next().is_none());
778 for i in range(0u, 3) {
782 for (i, elt) in d.mut_iter().rev().enumerate() {
788 let mut it = d.mut_iter().rev();
789 assert_eq!(*it.next().unwrap(), 0);
790 assert_eq!(*it.next().unwrap(), 1);
791 assert_eq!(*it.next().unwrap(), 2);
792 assert!(it.next().is_none());
797 fn test_from_iter() {
799 let v = vec!(1i,2,3,4,5,6,7);
800 let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
801 let u: Vec<int> = deq.iter().map(|&x| x).collect();
804 let mut seq = iter::count(0u, 2).take(256);
805 let deq: RingBuf<uint> = seq.collect();
806 for (i, &x) in deq.iter().enumerate() {
809 assert_eq!(deq.len(), 256);
814 let mut d = RingBuf::new();
819 assert_eq!(d.len(), 4u);
820 let mut e = d.clone();
821 assert_eq!(e.len(), 4u);
822 while !d.is_empty() {
823 assert_eq!(d.pop_back(), e.pop_back());
825 assert_eq!(d.len(), 0u);
826 assert_eq!(e.len(), 0u);
831 let mut d = RingBuf::new();
832 assert!(d == RingBuf::with_capacity(0));
837 let mut e = RingBuf::with_capacity(0);
847 assert!(e == RingBuf::new());
852 let ringbuf: RingBuf<int> = range(0i, 10).collect();
853 assert!(format!("{}", ringbuf).as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
855 let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
858 assert!(format!("{}", ringbuf).as_slice() == "[just, one, test, more]");