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 //! This crate implements a double-ended queue with `O(1)` amortized inserts and removals from both
12 //! ends of the container. It also has `O(1)` indexing like a vector. The contained elements are
13 //! not required to be copyable, and the queue will be sendable if the contained type is sendable.
15 #![stable(feature = "rust1", since = "1.0.0")]
19 use core::cmp::Ordering;
20 use core::default::Default;
22 use core::iter::{self, repeat, FromIterator, RandomAccessIterator};
25 use core::num::{Int, UnsignedInt};
26 use core::ops::{Index, IndexMut};
28 use core::raw::Slice as RawSlice;
30 use std::hash::{Writer, Hash, Hasher};
35 static INITIAL_CAPACITY: uint = 7u; // 2^3 - 1
36 static MINIMUM_CAPACITY: uint = 1u; // 2 - 1
38 /// `RingBuf` is a circular buffer, which can be used as a double-ended queue efficiently.
39 #[stable(feature = "rust1", since = "1.0.0")]
40 pub struct RingBuf<T> {
41 // tail and head are pointers into the buffer. Tail always points
42 // to the first element that could be read, Head always points
43 // to where data should be written.
44 // If tail == head the buffer is empty. The length of the ringbuf
45 // is defined as the distance between the two.
53 #[stable(feature = "rust1", since = "1.0.0")]
54 unsafe impl<T: Send> Send for RingBuf<T> {}
56 #[stable(feature = "rust1", since = "1.0.0")]
57 unsafe impl<T: Sync> Sync for RingBuf<T> {}
59 #[stable(feature = "rust1", since = "1.0.0")]
60 impl<T: Clone> Clone for RingBuf<T> {
61 fn clone(&self) -> RingBuf<T> {
62 self.iter().map(|t| t.clone()).collect()
67 #[stable(feature = "rust1", since = "1.0.0")]
68 impl<T> Drop for RingBuf<T> {
72 if mem::size_of::<T>() != 0 {
73 heap::deallocate(self.ptr as *mut u8,
74 self.cap * mem::size_of::<T>(),
75 mem::min_align_of::<T>())
81 #[stable(feature = "rust1", since = "1.0.0")]
82 impl<T> Default for RingBuf<T> {
84 fn default() -> RingBuf<T> { RingBuf::new() }
88 /// Turn ptr into a slice
90 unsafe fn buffer_as_slice(&self) -> &[T] {
91 mem::transmute(RawSlice { data: self.ptr, len: self.cap })
94 /// Turn ptr into a mut slice
96 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
97 mem::transmute(RawSlice { data: self.ptr, len: self.cap })
100 /// Moves an element out of the buffer
102 unsafe fn buffer_read(&mut self, off: uint) -> T {
103 ptr::read(self.ptr.offset(off as int))
106 /// Writes an element into the buffer, moving it.
108 unsafe fn buffer_write(&mut self, off: uint, t: T) {
109 ptr::write(self.ptr.offset(off as int), t);
112 /// Returns true iff the buffer is at capacity
114 fn is_full(&self) -> bool { self.cap - self.len() == 1 }
116 /// Returns the index in the underlying buffer for a given logical element index.
118 fn wrap_index(&self, idx: uint) -> uint { wrap_index(idx, self.cap) }
120 /// Copies a contiguous block of memory len long from src to dst
122 unsafe fn copy(&self, dst: uint, src: uint, len: uint) {
123 debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
125 debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
128 self.ptr.offset(dst as int),
129 self.ptr.offset(src as int),
133 /// Copies a contiguous block of memory len long from src to dst
135 unsafe fn copy_nonoverlapping(&self, dst: uint, src: uint, len: uint) {
136 debug_assert!(dst + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
138 debug_assert!(src + len <= self.cap, "dst={} src={} len={} cap={}", dst, src, len,
140 ptr::copy_nonoverlapping_memory(
141 self.ptr.offset(dst as int),
142 self.ptr.offset(src as int),
148 /// Creates an empty `RingBuf`.
149 #[stable(feature = "rust1", since = "1.0.0")]
150 pub fn new() -> RingBuf<T> {
151 RingBuf::with_capacity(INITIAL_CAPACITY)
154 /// Creates an empty `RingBuf` with space for at least `n` elements.
155 #[stable(feature = "rust1", since = "1.0.0")]
156 pub fn with_capacity(n: uint) -> RingBuf<T> {
157 // +1 since the ringbuffer always leaves one space empty
158 let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
159 assert!(cap > n, "capacity overflow");
160 let size = cap.checked_mul(mem::size_of::<T>())
161 .expect("capacity overflow");
163 let ptr = if mem::size_of::<T>() != 0 {
165 let ptr = heap::allocate(size, mem::min_align_of::<T>()) as *mut T;;
166 if ptr.is_null() { ::alloc::oom() }
170 heap::EMPTY as *mut T
181 /// Retrieves an element in the `RingBuf` by index.
186 /// use std::collections::RingBuf;
188 /// let mut buf = RingBuf::new();
189 /// buf.push_back(3i);
190 /// buf.push_back(4);
191 /// buf.push_back(5);
192 /// assert_eq!(buf.get(1).unwrap(), &4);
194 #[stable(feature = "rust1", since = "1.0.0")]
195 pub fn get(&self, i: uint) -> Option<&T> {
197 let idx = self.wrap_index(self.tail + i);
198 unsafe { Some(&*self.ptr.offset(idx as int)) }
204 /// Retrieves an element in the `RingBuf` mutably by index.
209 /// use std::collections::RingBuf;
211 /// let mut buf = RingBuf::new();
212 /// buf.push_back(3i);
213 /// buf.push_back(4);
214 /// buf.push_back(5);
215 /// match buf.get_mut(1) {
222 /// assert_eq!(buf[1], 7);
224 #[stable(feature = "rust1", since = "1.0.0")]
225 pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
227 let idx = self.wrap_index(self.tail + i);
228 unsafe { Some(&mut *self.ptr.offset(idx as int)) }
234 /// Swaps elements at indices `i` and `j`.
236 /// `i` and `j` may be equal.
238 /// Fails if there is no element with either index.
243 /// use std::collections::RingBuf;
245 /// let mut buf = RingBuf::new();
246 /// buf.push_back(3i);
247 /// buf.push_back(4);
248 /// buf.push_back(5);
250 /// assert_eq!(buf[0], 5);
251 /// assert_eq!(buf[2], 3);
253 #[stable(feature = "rust1", since = "1.0.0")]
254 pub fn swap(&mut self, i: uint, j: uint) {
255 assert!(i < self.len());
256 assert!(j < self.len());
257 let ri = self.wrap_index(self.tail + i);
258 let rj = self.wrap_index(self.tail + j);
260 ptr::swap(self.ptr.offset(ri as int), self.ptr.offset(rj as int))
264 /// Returns the number of elements the `RingBuf` can hold without
270 /// use std::collections::RingBuf;
272 /// let buf: RingBuf<int> = RingBuf::with_capacity(10);
273 /// assert!(buf.capacity() >= 10);
276 #[stable(feature = "rust1", since = "1.0.0")]
277 pub fn capacity(&self) -> uint { self.cap - 1 }
279 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
280 /// given `RingBuf`. Does nothing if the capacity is already sufficient.
282 /// Note that the allocator may give the collection more space than it requests. Therefore
283 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
284 /// insertions are expected.
288 /// Panics if the new capacity overflows `uint`.
293 /// use std::collections::RingBuf;
295 /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
296 /// buf.reserve_exact(10);
297 /// assert!(buf.capacity() >= 11);
299 #[stable(feature = "rust1", since = "1.0.0")]
300 pub fn reserve_exact(&mut self, additional: uint) {
301 self.reserve(additional);
304 /// Reserves capacity for at least `additional` more elements to be inserted in the given
305 /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations.
309 /// Panics if the new capacity overflows `uint`.
314 /// use std::collections::RingBuf;
316 /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
318 /// assert!(buf.capacity() >= 11);
320 #[stable(feature = "rust1", since = "1.0.0")]
321 pub fn reserve(&mut self, additional: uint) {
322 let new_len = self.len() + additional;
323 assert!(new_len + 1 > self.len(), "capacity overflow");
324 if new_len > self.capacity() {
325 let count = (new_len + 1).next_power_of_two();
326 assert!(count >= new_len + 1);
328 if mem::size_of::<T>() != 0 {
329 let old = self.cap * mem::size_of::<T>();
330 let new = count.checked_mul(mem::size_of::<T>())
331 .expect("capacity overflow");
333 self.ptr = heap::reallocate(self.ptr as *mut u8,
336 mem::min_align_of::<T>()) as *mut T;
337 if self.ptr.is_null() { ::alloc::oom() }
341 // Move the shortest contiguous section of the ring buffer
343 // [o o o o o o o . ]
345 // A [o o o o o o o . . . . . . . . . ]
347 // [o o . o o o o o ]
349 // B [. . . o o o o o o o . . . . . . ]
351 // [o o o o o . o o ]
353 // C [o o o o o . . . . . . . . . o o ]
355 let oldcap = self.cap;
358 if self.tail <= self.head { // A
360 } else if self.head < oldcap - self.tail { // B
362 self.copy_nonoverlapping(oldcap, 0, self.head);
365 debug_assert!(self.head > self.tail);
367 let new_tail = count - (oldcap - self.tail);
369 self.copy_nonoverlapping(new_tail, self.tail, oldcap - self.tail);
371 self.tail = new_tail;
372 debug_assert!(self.head < self.tail);
374 debug_assert!(self.head < self.cap);
375 debug_assert!(self.tail < self.cap);
376 debug_assert!(self.cap.count_ones() == 1);
380 /// Shrinks the capacity of the ringbuf as much as possible.
382 /// It will drop down as close as possible to the length but the allocator may still inform the
383 /// ringbuf that there is space for a few more elements.
388 /// use std::collections::RingBuf;
390 /// let mut buf = RingBuf::with_capacity(15);
391 /// buf.extend(range(0u, 4));
392 /// assert_eq!(buf.capacity(), 15);
393 /// buf.shrink_to_fit();
394 /// assert!(buf.capacity() >= 4);
396 pub fn shrink_to_fit(&mut self) {
397 // +1 since the ringbuffer always leaves one space empty
398 // len + 1 can't overflow for an existing, well-formed ringbuf.
399 let target_cap = cmp::max(self.len() + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
400 if target_cap < self.cap {
401 // There are three cases of interest:
402 // All elements are out of desired bounds
403 // Elements are contiguous, and head is out of desired bounds
404 // Elements are discontiguous, and tail is out of desired bounds
406 // At all other times, element positions are unaffected.
408 // Indicates that elements at the head should be moved.
409 let head_outside = self.head == 0 || self.head >= target_cap;
410 // Move elements from out of desired bounds (positions after target_cap)
411 if self.tail >= target_cap && head_outside {
413 // [. . . . . . . . o o o o o o o . ]
415 // [o o o o o o o . ]
417 self.copy_nonoverlapping(0, self.tail, self.len());
419 self.head = self.len();
421 } else if self.tail != 0 && self.tail < target_cap && head_outside {
423 // [. . . o o o o o o o . . . . . . ]
425 // [o o . o o o o o ]
426 let len = self.wrap_index(self.head - target_cap);
428 self.copy_nonoverlapping(0, target_cap, len);
431 debug_assert!(self.head < self.tail);
432 } else if self.tail >= target_cap {
434 // [o o o o o . . . . . . . . . o o ]
436 // [o o o o o . o o ]
437 debug_assert!(self.wrap_index(self.head - 1) < target_cap);
438 let len = self.cap - self.tail;
439 let new_tail = target_cap - len;
441 self.copy_nonoverlapping(new_tail, self.tail, len);
443 self.tail = new_tail;
444 debug_assert!(self.head < self.tail);
447 if mem::size_of::<T>() != 0 {
448 let old = self.cap * mem::size_of::<T>();
449 let new_size = target_cap * mem::size_of::<T>();
451 self.ptr = heap::reallocate(self.ptr as *mut u8,
454 mem::min_align_of::<T>()) as *mut T;
455 if self.ptr.is_null() { ::alloc::oom() }
458 self.cap = target_cap;
459 debug_assert!(self.head < self.cap);
460 debug_assert!(self.tail < self.cap);
461 debug_assert!(self.cap.count_ones() == 1);
465 /// Shorten a ringbuf, dropping excess elements from the back.
467 /// If `len` is greater than the ringbuf's current length, this has no
473 /// use std::collections::RingBuf;
475 /// let mut buf = RingBuf::new();
476 /// buf.push_back(5i);
477 /// buf.push_back(10i);
478 /// buf.push_back(15);
480 /// assert_eq!(buf.len(), 1);
481 /// assert_eq!(Some(&5), buf.get(0));
483 #[unstable(feature = "collections",
484 reason = "matches collection reform specification; waiting on panic semantics")]
485 pub fn truncate(&mut self, len: uint) {
486 for _ in range(len, self.len()) {
491 /// Returns a front-to-back iterator.
496 /// use std::collections::RingBuf;
498 /// let mut buf = RingBuf::new();
499 /// buf.push_back(5i);
500 /// buf.push_back(3);
501 /// buf.push_back(4);
502 /// let b: &[_] = &[&5, &3, &4];
503 /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b);
505 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn iter(&self) -> Iter<T> {
510 ring: unsafe { self.buffer_as_slice() }
514 /// Returns a front-to-back iterator that returns mutable references.
519 /// use std::collections::RingBuf;
521 /// let mut buf = RingBuf::new();
522 /// buf.push_back(5i);
523 /// buf.push_back(3);
524 /// buf.push_back(4);
525 /// for num in buf.iter_mut() {
528 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
529 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut int>>()[], b);
531 #[stable(feature = "rust1", since = "1.0.0")]
532 pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
538 marker: marker::ContravariantLifetime::<'a>,
542 /// Consumes the list into an iterator yielding elements by value.
543 #[stable(feature = "rust1", since = "1.0.0")]
544 pub fn into_iter(self) -> IntoIter<T> {
550 /// Returns a pair of slices which contain, in order, the contents of the
553 #[unstable(feature = "collections",
554 reason = "matches collection reform specification, waiting for dust to settle")]
555 pub fn as_slices<'a>(&'a self) -> (&'a [T], &'a [T]) {
557 let contiguous = self.is_contiguous();
558 let buf = self.buffer_as_slice();
560 let (empty, buf) = buf.split_at(0);
561 (&buf[self.tail..self.head], empty)
563 let (mid, right) = buf.split_at(self.tail);
564 let (left, _) = mid.split_at(self.head);
570 /// Returns a pair of slices which contain, in order, the contents of the
573 #[unstable(feature = "collections",
574 reason = "matches collection reform specification, waiting for dust to settle")]
575 pub fn as_mut_slices<'a>(&'a mut self) -> (&'a mut [T], &'a mut [T]) {
577 let contiguous = self.is_contiguous();
578 let head = self.head;
579 let tail = self.tail;
580 let buf = self.buffer_as_mut_slice();
583 let (empty, buf) = buf.split_at_mut(0);
584 (&mut buf[tail .. head], empty)
586 let (mid, right) = buf.split_at_mut(tail);
587 let (left, _) = mid.split_at_mut(head);
594 /// Returns the number of elements in the `RingBuf`.
599 /// use std::collections::RingBuf;
601 /// let mut v = RingBuf::new();
602 /// assert_eq!(v.len(), 0);
604 /// assert_eq!(v.len(), 1);
606 #[stable(feature = "rust1", since = "1.0.0")]
607 pub fn len(&self) -> uint { count(self.tail, self.head, self.cap) }
609 /// Returns true if the buffer contains no elements
614 /// use std::collections::RingBuf;
616 /// let mut v = RingBuf::new();
617 /// assert!(v.is_empty());
618 /// v.push_front(1i);
619 /// assert!(!v.is_empty());
621 #[stable(feature = "rust1", since = "1.0.0")]
622 pub fn is_empty(&self) -> bool { self.len() == 0 }
624 /// Creates a draining iterator that clears the `RingBuf` and iterates over
625 /// the removed items from start to end.
630 /// use std::collections::RingBuf;
632 /// let mut v = RingBuf::new();
634 /// assert_eq!(v.drain().next(), Some(1));
635 /// assert!(v.is_empty());
638 #[unstable(feature = "collections",
639 reason = "matches collection reform specification, waiting for dust to settle")]
640 pub fn drain(&mut self) -> Drain<T> {
646 /// Clears the buffer, removing all values.
651 /// use std::collections::RingBuf;
653 /// let mut v = RingBuf::new();
656 /// assert!(v.is_empty());
658 #[stable(feature = "rust1", since = "1.0.0")]
660 pub fn clear(&mut self) {
664 /// Provides a reference to the front element, or `None` if the sequence is
670 /// use std::collections::RingBuf;
672 /// let mut d = RingBuf::new();
673 /// assert_eq!(d.front(), None);
677 /// assert_eq!(d.front(), Some(&1i));
679 #[stable(feature = "rust1", since = "1.0.0")]
680 pub fn front(&self) -> Option<&T> {
681 if !self.is_empty() { Some(&self[0]) } else { None }
684 /// Provides a mutable reference to the front element, or `None` if the
685 /// sequence is empty.
690 /// use std::collections::RingBuf;
692 /// let mut d = RingBuf::new();
693 /// assert_eq!(d.front_mut(), None);
697 /// match d.front_mut() {
698 /// Some(x) => *x = 9i,
701 /// assert_eq!(d.front(), Some(&9i));
703 #[stable(feature = "rust1", since = "1.0.0")]
704 pub fn front_mut(&mut self) -> Option<&mut T> {
705 if !self.is_empty() { Some(&mut self[0]) } else { None }
708 /// Provides a reference to the back element, or `None` if the sequence is
714 /// use std::collections::RingBuf;
716 /// let mut d = RingBuf::new();
717 /// assert_eq!(d.back(), None);
721 /// assert_eq!(d.back(), Some(&2i));
723 #[stable(feature = "rust1", since = "1.0.0")]
724 pub fn back(&self) -> Option<&T> {
725 if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
728 /// Provides a mutable reference to the back element, or `None` if the
729 /// sequence is empty.
734 /// use std::collections::RingBuf;
736 /// let mut d = RingBuf::new();
737 /// assert_eq!(d.back(), None);
741 /// match d.back_mut() {
742 /// Some(x) => *x = 9i,
745 /// assert_eq!(d.back(), Some(&9i));
747 #[stable(feature = "rust1", since = "1.0.0")]
748 pub fn back_mut(&mut self) -> Option<&mut T> {
749 let len = self.len();
750 if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
753 /// Removes the first element and returns it, or `None` if the sequence is
759 /// use std::collections::RingBuf;
761 /// let mut d = RingBuf::new();
765 /// assert_eq!(d.pop_front(), Some(1i));
766 /// assert_eq!(d.pop_front(), Some(2i));
767 /// assert_eq!(d.pop_front(), None);
769 #[stable(feature = "rust1", since = "1.0.0")]
770 pub fn pop_front(&mut self) -> Option<T> {
774 let tail = self.tail;
775 self.tail = self.wrap_index(self.tail + 1);
776 unsafe { Some(self.buffer_read(tail)) }
780 /// Inserts an element first in the sequence.
785 /// use std::collections::RingBuf;
787 /// let mut d = RingBuf::new();
788 /// d.push_front(1i);
789 /// d.push_front(2i);
790 /// assert_eq!(d.front(), Some(&2i));
792 #[stable(feature = "rust1", since = "1.0.0")]
793 pub fn push_front(&mut self, t: T) {
796 debug_assert!(!self.is_full());
799 self.tail = self.wrap_index(self.tail - 1);
800 let tail = self.tail;
801 unsafe { self.buffer_write(tail, t); }
804 /// Appends an element to the back of a buffer
809 /// use std::collections::RingBuf;
811 /// let mut buf = RingBuf::new();
812 /// buf.push_back(1i);
813 /// buf.push_back(3);
814 /// assert_eq!(3, *buf.back().unwrap());
816 #[stable(feature = "rust1", since = "1.0.0")]
817 pub fn push_back(&mut self, t: T) {
820 debug_assert!(!self.is_full());
823 let head = self.head;
824 self.head = self.wrap_index(self.head + 1);
825 unsafe { self.buffer_write(head, t) }
828 /// Removes the last element from a buffer and returns it, or `None` if
834 /// use std::collections::RingBuf;
836 /// let mut buf = RingBuf::new();
837 /// assert_eq!(buf.pop_back(), None);
838 /// buf.push_back(1i);
839 /// buf.push_back(3);
840 /// assert_eq!(buf.pop_back(), Some(3));
842 #[stable(feature = "rust1", since = "1.0.0")]
843 pub fn pop_back(&mut self) -> Option<T> {
847 self.head = self.wrap_index(self.head - 1);
848 let head = self.head;
849 unsafe { Some(self.buffer_read(head)) }
854 fn is_contiguous(&self) -> bool {
855 self.tail <= self.head
858 /// Removes an element from anywhere in the ringbuf and returns it, replacing it with the last
861 /// This does not preserve ordering, but is O(1).
863 /// Returns `None` if `index` is out of bounds.
868 /// use std::collections::RingBuf;
870 /// let mut buf = RingBuf::new();
871 /// assert_eq!(buf.swap_back_remove(0), None);
872 /// buf.push_back(5i);
873 /// buf.push_back(99);
874 /// buf.push_back(15);
875 /// buf.push_back(20);
876 /// buf.push_back(10);
877 /// assert_eq!(buf.swap_back_remove(1), Some(99));
879 #[unstable(feature = "collections",
880 reason = "the naming of this function may be altered")]
881 pub fn swap_back_remove(&mut self, index: uint) -> Option<T> {
882 let length = self.len();
883 if length > 0 && index < length - 1 {
884 self.swap(index, length - 1);
885 } else if index >= length {
891 /// Removes an element from anywhere in the ringbuf and returns it, replacing it with the first
894 /// This does not preserve ordering, but is O(1).
896 /// Returns `None` if `index` is out of bounds.
901 /// use std::collections::RingBuf;
903 /// let mut buf = RingBuf::new();
904 /// assert_eq!(buf.swap_front_remove(0), None);
905 /// buf.push_back(15i);
906 /// buf.push_back(5);
907 /// buf.push_back(10);
908 /// buf.push_back(99);
909 /// buf.push_back(20i);
910 /// assert_eq!(buf.swap_front_remove(3), Some(99));
912 #[unstable(feature = "collections",
913 reason = "the naming of this function may be altered")]
914 pub fn swap_front_remove(&mut self, index: uint) -> Option<T> {
915 let length = self.len();
916 if length > 0 && index < length && index != 0 {
918 } else if index >= length {
924 /// Inserts an element at position `i` within the ringbuf. Whichever
925 /// end is closer to the insertion point will be moved to make room,
926 /// and all the affected elements will be moved to new positions.
930 /// Panics if `i` is greater than ringbuf's length
934 /// use std::collections::RingBuf;
936 /// let mut buf = RingBuf::new();
937 /// buf.push_back(10i);
938 /// buf.push_back(12);
939 /// buf.insert(1,11);
940 /// assert_eq!(Some(&11), buf.get(1));
942 pub fn insert(&mut self, i: uint, t: T) {
943 assert!(i <= self.len(), "index out of bounds");
946 debug_assert!(!self.is_full());
949 // Move the least number of elements in the ring buffer and insert
952 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
954 // There are three main cases:
955 // Elements are contiguous
956 // - special case when tail is 0
957 // Elements are discontiguous and the insert is in the tail section
958 // Elements are discontiguous and the insert is in the head section
960 // For each of those there are two more cases:
961 // Insert is closer to tail
962 // Insert is closer to head
964 // Key: H - self.head
967 // I - Insertion element
968 // A - The element that should be after the insertion point
969 // M - Indicates element was moved
971 let idx = self.wrap_index(self.tail + i);
973 let distance_to_tail = i;
974 let distance_to_head = self.len() - i;
976 let contiguous = self.is_contiguous();
978 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
979 (true, true, _) if i == 0 => {
984 // [A o o o o o o . . . . . . . . .]
987 // [A o o o o o o o . . . . . I]
990 self.tail = self.wrap_index(self.tail - 1);
992 (true, true, _) => unsafe {
993 // contiguous, insert closer to tail:
996 // [. . . o o A o o o o . . . . . .]
999 // [. . o o I A o o o o . . . . . .]
1002 // contiguous, insert closer to tail and tail is 0:
1006 // [o o A o o o o . . . . . . . . .]
1009 // [o I A o o o o o . . . . . . . o]
1012 let new_tail = self.wrap_index(self.tail - 1);
1014 self.copy(new_tail, self.tail, 1);
1015 // Already moved the tail, so we only copy `i - 1` elements.
1016 self.copy(self.tail, self.tail + 1, i - 1);
1018 self.tail = new_tail;
1020 (true, false, _) => unsafe {
1021 // contiguous, insert closer to head:
1024 // [. . . o o o o A o o . . . . . .]
1027 // [. . . o o o o I A o o . . . . .]
1030 self.copy(idx + 1, idx, self.head - idx);
1031 self.head = self.wrap_index(self.head + 1);
1033 (false, true, true) => unsafe {
1034 // discontiguous, insert closer to tail, tail section:
1037 // [o o o o o o . . . . . o o A o o]
1040 // [o o o o o o . . . . o o I A o o]
1043 self.copy(self.tail - 1, self.tail, i);
1046 (false, false, true) => unsafe {
1047 // discontiguous, insert closer to head, tail section:
1050 // [o o . . . . . . . o o o o o A o]
1053 // [o o o . . . . . . o o o o o I A]
1056 // copy elements up to new head
1057 self.copy(1, 0, self.head);
1059 // copy last element into empty spot at bottom of buffer
1060 self.copy(0, self.cap - 1, 1);
1062 // move elements from idx to end forward not including ^ element
1063 self.copy(idx + 1, idx, self.cap - 1 - idx);
1067 (false, true, false) if idx == 0 => unsafe {
1068 // discontiguous, insert is closer to tail, head section,
1069 // and is at index zero in the internal buffer:
1072 // [A o o o o o o o o o . . . o o o]
1075 // [A o o o o o o o o o . . o o o I]
1078 // copy elements up to new tail
1079 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
1081 // copy last element into empty spot at bottom of buffer
1082 self.copy(self.cap - 1, 0, 1);
1086 (false, true, false) => unsafe {
1087 // discontiguous, insert closer to tail, head section:
1090 // [o o o A o o o o o o . . . o o o]
1093 // [o o I A o o o o o o . . o o o o]
1096 // copy elements up to new tail
1097 self.copy(self.tail - 1, self.tail, self.cap - self.tail);
1099 // copy last element into empty spot at bottom of buffer
1100 self.copy(self.cap - 1, 0, 1);
1102 // move elements from idx-1 to end forward not including ^ element
1103 self.copy(0, 1, idx - 1);
1107 (false, false, false) => unsafe {
1108 // discontiguous, insert closer to head, head section:
1111 // [o o o o A o o . . . . . . o o o]
1114 // [o o o o I A o o . . . . . o o o]
1117 self.copy(idx + 1, idx, self.head - idx);
1122 // tail might've been changed so we need to recalculate
1123 let new_idx = self.wrap_index(self.tail + i);
1125 self.buffer_write(new_idx, t);
1129 /// Removes and returns the element at position `i` from the ringbuf.
1130 /// Whichever end is closer to the removal point will be moved to make
1131 /// room, and all the affected elements will be moved to new positions.
1132 /// Returns `None` if `i` is out of bounds.
1136 /// use std::collections::RingBuf;
1138 /// let mut buf = RingBuf::new();
1139 /// buf.push_back(5i);
1140 /// buf.push_back(10i);
1141 /// buf.push_back(12i);
1142 /// buf.push_back(15);
1144 /// assert_eq!(Some(&15), buf.get(2));
1146 #[stable(feature = "rust1", since = "1.0.0")]
1147 pub fn remove(&mut self, i: uint) -> Option<T> {
1148 if self.is_empty() || self.len() <= i {
1152 // There are three main cases:
1153 // Elements are contiguous
1154 // Elements are discontiguous and the removal is in the tail section
1155 // Elements are discontiguous and the removal is in the head section
1156 // - special case when elements are technically contiguous,
1157 // but self.head = 0
1159 // For each of those there are two more cases:
1160 // Insert is closer to tail
1161 // Insert is closer to head
1163 // Key: H - self.head
1165 // o - Valid element
1166 // x - Element marked for removal
1167 // R - Indicates element that is being removed
1168 // M - Indicates element was moved
1170 let idx = self.wrap_index(self.tail + i);
1173 Some(self.buffer_read(idx))
1176 let distance_to_tail = i;
1177 let distance_to_head = self.len() - i;
1179 let contiguous = self.is_contiguous();
1181 match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
1182 (true, true, _) => unsafe {
1183 // contiguous, remove closer to tail:
1186 // [. . . o o x o o o o . . . . . .]
1189 // [. . . . o o o o o o . . . . . .]
1192 self.copy(self.tail + 1, self.tail, i);
1195 (true, false, _) => unsafe {
1196 // contiguous, remove closer to head:
1199 // [. . . o o o o x o o . . . . . .]
1202 // [. . . o o o o o o . . . . . . .]
1205 self.copy(idx, idx + 1, self.head - idx - 1);
1208 (false, true, true) => unsafe {
1209 // discontiguous, remove closer to tail, tail section:
1212 // [o o o o o o . . . . . o o x o o]
1215 // [o o o o o o . . . . . . o o o o]
1218 self.copy(self.tail + 1, self.tail, i);
1219 self.tail = self.wrap_index(self.tail + 1);
1221 (false, false, false) => unsafe {
1222 // discontiguous, remove closer to head, head section:
1225 // [o o o o x o o . . . . . . o o o]
1228 // [o o o o o o . . . . . . . o o o]
1231 self.copy(idx, idx + 1, self.head - idx - 1);
1234 (false, false, true) => unsafe {
1235 // discontiguous, remove closer to head, tail section:
1238 // [o o o . . . . . . o o o o o x o]
1241 // [o o . . . . . . . o o o o o o o]
1244 // or quasi-discontiguous, remove next to head, tail section:
1247 // [. . . . . . . . . o o o o o x o]
1250 // [. . . . . . . . . o o o o o o .]
1253 // draw in elements in the tail section
1254 self.copy(idx, idx + 1, self.cap - idx - 1);
1256 // Prevents underflow.
1258 // copy first element into empty spot
1259 self.copy(self.cap - 1, 0, 1);
1261 // move elements in the head section backwards
1262 self.copy(0, 1, self.head - 1);
1265 self.head = self.wrap_index(self.head - 1);
1267 (false, true, false) => unsafe {
1268 // discontiguous, remove closer to tail, head section:
1271 // [o o x o o o o o o o . . . o o o]
1274 // [o o o o o o o o o o . . . . o o]
1277 // draw in elements up to idx
1278 self.copy(1, 0, idx);
1280 // copy last element into empty spot
1281 self.copy(0, self.cap - 1, 1);
1283 // move elements from tail to end forward, excluding the last one
1284 self.copy(self.tail + 1, self.tail, self.cap - self.tail - 1);
1286 self.tail = self.wrap_index(self.tail + 1);
1294 impl<T: Clone> RingBuf<T> {
1295 /// Modifies the ringbuf in-place so that `len()` is equal to new_len,
1296 /// either by removing excess elements or by appending copies of a value to the back.
1301 /// use std::collections::RingBuf;
1303 /// let mut buf = RingBuf::new();
1304 /// buf.push_back(5i);
1305 /// buf.push_back(10i);
1306 /// buf.push_back(15);
1307 /// buf.resize(2, 0);
1308 /// buf.resize(6, 20);
1309 /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(buf.iter()) {
1310 /// assert_eq!(a, b);
1313 #[unstable(feature = "collections",
1314 reason = "matches collection reform specification; waiting on panic semantics")]
1315 pub fn resize(&mut self, new_len: uint, value: T) {
1316 let len = self.len();
1319 self.extend(repeat(value).take(new_len - len))
1321 self.truncate(new_len);
1326 /// Returns the index in the underlying buffer for a given logical element index.
1328 fn wrap_index(index: uint, size: uint) -> uint {
1329 // size is always a power of 2
1333 /// Calculate the number of elements left to be read in the buffer
1335 fn count(tail: uint, head: uint, size: uint) -> uint {
1336 // size is always a power of 2
1337 (head - tail) & (size - 1)
1340 /// `RingBuf` iterator.
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 pub struct Iter<'a, T:'a> {
1348 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1349 impl<'a, T> Clone for Iter<'a, T> {
1350 fn clone(&self) -> Iter<'a, T> {
1359 #[stable(feature = "rust1", since = "1.0.0")]
1360 impl<'a, T> Iterator for Iter<'a, T> {
1364 fn next(&mut self) -> Option<&'a T> {
1365 if self.tail == self.head {
1368 let tail = self.tail;
1369 self.tail = wrap_index(self.tail + 1, self.ring.len());
1370 unsafe { Some(self.ring.get_unchecked(tail)) }
1374 fn size_hint(&self) -> (uint, Option<uint>) {
1375 let len = count(self.tail, self.head, self.ring.len());
1380 #[stable(feature = "rust1", since = "1.0.0")]
1381 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1383 fn next_back(&mut self) -> Option<&'a T> {
1384 if self.tail == self.head {
1387 self.head = wrap_index(self.head - 1, self.ring.len());
1388 unsafe { Some(self.ring.get_unchecked(self.head)) }
1392 #[stable(feature = "rust1", since = "1.0.0")]
1393 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
1395 #[stable(feature = "rust1", since = "1.0.0")]
1396 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
1398 fn indexable(&self) -> uint {
1399 let (len, _) = self.size_hint();
1404 fn idx(&mut self, j: uint) -> Option<&'a T> {
1405 if j >= self.indexable() {
1408 let idx = wrap_index(self.tail + j, self.ring.len());
1409 unsafe { Some(self.ring.get_unchecked(idx)) }
1414 // FIXME This was implemented differently from Iter because of a problem
1415 // with returning the mutable reference. I couldn't find a way to
1416 // make the lifetime checker happy so, but there should be a way.
1417 /// `RingBuf` mutable iterator.
1418 #[stable(feature = "rust1", since = "1.0.0")]
1419 pub struct IterMut<'a, T:'a> {
1424 marker: marker::ContravariantLifetime<'a>,
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 impl<'a, T> Iterator for IterMut<'a, T> {
1429 type Item = &'a mut T;
1432 fn next(&mut self) -> Option<&'a mut T> {
1433 if self.tail == self.head {
1436 let tail = self.tail;
1437 self.tail = wrap_index(self.tail + 1, self.cap);
1440 Some(&mut *self.ptr.offset(tail as int))
1445 fn size_hint(&self) -> (uint, Option<uint>) {
1446 let len = count(self.tail, self.head, self.cap);
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1454 fn next_back(&mut self) -> Option<&'a mut T> {
1455 if self.tail == self.head {
1458 self.head = wrap_index(self.head - 1, self.cap);
1461 Some(&mut *self.ptr.offset(self.head as int))
1466 #[stable(feature = "rust1", since = "1.0.0")]
1467 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
1469 /// A by-value RingBuf iterator
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 pub struct IntoIter<T> {
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<T> Iterator for IntoIter<T> {
1480 fn next(&mut self) -> Option<T> {
1481 self.inner.pop_front()
1485 fn size_hint(&self) -> (uint, Option<uint>) {
1486 let len = self.inner.len();
1491 #[stable(feature = "rust1", since = "1.0.0")]
1492 impl<T> DoubleEndedIterator for IntoIter<T> {
1494 fn next_back(&mut self) -> Option<T> {
1495 self.inner.pop_back()
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 impl<T> ExactSizeIterator for IntoIter<T> {}
1502 /// A draining RingBuf iterator
1503 #[unstable(feature = "collections",
1504 reason = "matches collection reform specification, waiting for dust to settle")]
1505 pub struct Drain<'a, T: 'a> {
1506 inner: &'a mut RingBuf<T>,
1509 #[unsafe_destructor]
1510 #[stable(feature = "rust1", since = "1.0.0")]
1511 impl<'a, T: 'a> Drop for Drain<'a, T> {
1512 fn drop(&mut self) {
1514 self.inner.head = 0;
1515 self.inner.tail = 0;
1519 #[stable(feature = "rust1", since = "1.0.0")]
1520 impl<'a, T: 'a> Iterator for Drain<'a, T> {
1524 fn next(&mut self) -> Option<T> {
1525 self.inner.pop_front()
1529 fn size_hint(&self) -> (uint, Option<uint>) {
1530 let len = self.inner.len();
1535 #[stable(feature = "rust1", since = "1.0.0")]
1536 impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
1538 fn next_back(&mut self) -> Option<T> {
1539 self.inner.pop_back()
1543 #[stable(feature = "rust1", since = "1.0.0")]
1544 impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {}
1546 #[stable(feature = "rust1", since = "1.0.0")]
1547 impl<A: PartialEq> PartialEq for RingBuf<A> {
1548 fn eq(&self, other: &RingBuf<A>) -> bool {
1549 self.len() == other.len() &&
1550 self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
1554 #[stable(feature = "rust1", since = "1.0.0")]
1555 impl<A: Eq> Eq for RingBuf<A> {}
1557 #[stable(feature = "rust1", since = "1.0.0")]
1558 impl<A: PartialOrd> PartialOrd for RingBuf<A> {
1559 fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
1560 iter::order::partial_cmp(self.iter(), other.iter())
1564 #[stable(feature = "rust1", since = "1.0.0")]
1565 impl<A: Ord> Ord for RingBuf<A> {
1567 fn cmp(&self, other: &RingBuf<A>) -> Ordering {
1568 iter::order::cmp(self.iter(), other.iter())
1572 #[stable(feature = "rust1", since = "1.0.0")]
1573 impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> {
1574 fn hash(&self, state: &mut S) {
1575 self.len().hash(state);
1576 for elt in self.iter() {
1582 #[stable(feature = "rust1", since = "1.0.0")]
1583 impl<A> Index<uint> for RingBuf<A> {
1587 fn index<'a>(&'a self, i: &uint) -> &'a A {
1588 self.get(*i).expect("Out of bounds access")
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 impl<A> IndexMut<uint> for RingBuf<A> {
1597 fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1598 self.get_mut(*i).expect("Out of bounds access")
1602 #[stable(feature = "rust1", since = "1.0.0")]
1603 impl<A> FromIterator<A> for RingBuf<A> {
1604 fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> {
1605 let (lower, _) = iterator.size_hint();
1606 let mut deq = RingBuf::with_capacity(lower);
1607 deq.extend(iterator);
1612 #[stable(feature = "rust1", since = "1.0.0")]
1613 impl<A> Extend<A> for RingBuf<A> {
1614 fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
1615 for elt in iterator {
1616 self.push_back(elt);
1621 #[stable(feature = "rust1", since = "1.0.0")]
1622 impl<T: fmt::Debug> fmt::Debug for RingBuf<T> {
1623 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1624 try!(write!(f, "RingBuf ["));
1626 for (i, e) in self.iter().enumerate() {
1627 if i != 0 { try!(write!(f, ", ")); }
1628 try!(write!(f, "{:?}", *e));
1638 use self::Taggypar::*;
1641 use std::fmt::Debug;
1642 use std::hash::{self, SipHasher};
1649 #[allow(deprecated)]
1651 let mut d = RingBuf::new();
1652 assert_eq!(d.len(), 0u);
1656 assert_eq!(d.len(), 3u);
1658 assert_eq!(d.len(), 4u);
1659 assert_eq!(*d.front().unwrap(), 42);
1660 assert_eq!(*d.back().unwrap(), 137);
1661 let mut i = d.pop_front();
1662 assert_eq!(i, Some(42));
1664 assert_eq!(i, Some(137));
1666 assert_eq!(i, Some(137));
1668 assert_eq!(i, Some(17));
1669 assert_eq!(d.len(), 0u);
1671 assert_eq!(d.len(), 1u);
1673 assert_eq!(d.len(), 2u);
1675 assert_eq!(d.len(), 3u);
1677 assert_eq!(d.len(), 4u);
1682 assert_eq!(d[0], 1);
1683 assert_eq!(d[1], 2);
1684 assert_eq!(d[2], 3);
1685 assert_eq!(d[3], 4);
1689 fn test_parameterized<T:Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
1690 let mut deq = RingBuf::new();
1691 assert_eq!(deq.len(), 0);
1692 deq.push_front(a.clone());
1693 deq.push_front(b.clone());
1694 deq.push_back(c.clone());
1695 assert_eq!(deq.len(), 3);
1696 deq.push_back(d.clone());
1697 assert_eq!(deq.len(), 4);
1698 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
1699 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
1700 assert_eq!(deq.pop_front().unwrap(), b.clone());
1701 assert_eq!(deq.pop_back().unwrap(), d.clone());
1702 assert_eq!(deq.pop_back().unwrap(), c.clone());
1703 assert_eq!(deq.pop_back().unwrap(), a.clone());
1704 assert_eq!(deq.len(), 0);
1705 deq.push_back(c.clone());
1706 assert_eq!(deq.len(), 1);
1707 deq.push_front(b.clone());
1708 assert_eq!(deq.len(), 2);
1709 deq.push_back(d.clone());
1710 assert_eq!(deq.len(), 3);
1711 deq.push_front(a.clone());
1712 assert_eq!(deq.len(), 4);
1713 assert_eq!(deq[0].clone(), a.clone());
1714 assert_eq!(deq[1].clone(), b.clone());
1715 assert_eq!(deq[2].clone(), c.clone());
1716 assert_eq!(deq[3].clone(), d.clone());
1720 fn test_push_front_grow() {
1721 let mut deq = RingBuf::new();
1722 for i in range(0u, 66) {
1725 assert_eq!(deq.len(), 66);
1727 for i in range(0u, 66) {
1728 assert_eq!(deq[i], 65 - i);
1731 let mut deq = RingBuf::new();
1732 for i in range(0u, 66) {
1736 for i in range(0u, 66) {
1737 assert_eq!(deq[i], i);
1743 let mut deq = RingBuf::new();
1744 for i in range(1u, 4) {
1747 assert_eq!(deq[1], 2);
1752 fn test_index_out_of_bounds() {
1753 let mut deq = RingBuf::new();
1754 for i in range(1u, 4) {
1761 fn bench_new(b: &mut test::Bencher) {
1763 let ring: RingBuf<u64> = RingBuf::new();
1764 test::black_box(ring);
1769 fn bench_push_back_100(b: &mut test::Bencher) {
1770 let mut deq = RingBuf::with_capacity(101);
1772 for i in range(0i, 100) {
1781 fn bench_push_front_100(b: &mut test::Bencher) {
1782 let mut deq = RingBuf::with_capacity(101);
1784 for i in range(0i, 100) {
1793 fn bench_pop_back_100(b: &mut test::Bencher) {
1794 let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1799 while !deq.is_empty() {
1800 test::black_box(deq.pop_back());
1806 fn bench_pop_front_100(b: &mut test::Bencher) {
1807 let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1812 while !deq.is_empty() {
1813 test::black_box(deq.pop_front());
1819 fn bench_grow_1025(b: &mut test::Bencher) {
1821 let mut deq = RingBuf::new();
1822 for i in range(0i, 1025) {
1825 test::black_box(deq);
1830 fn bench_iter_1000(b: &mut test::Bencher) {
1831 let ring: RingBuf<int> = range(0i, 1000).collect();
1835 for &i in ring.iter() {
1838 test::black_box(sum);
1843 fn bench_mut_iter_1000(b: &mut test::Bencher) {
1844 let mut ring: RingBuf<int> = range(0i, 1000).collect();
1848 for i in ring.iter_mut() {
1851 test::black_box(sum);
1855 #[derive(Clone, PartialEq, Show)]
1859 Three(int, int, int),
1862 #[derive(Clone, PartialEq, Show)]
1866 Threepar(int, int, int),
1869 #[derive(Clone, PartialEq, Show)]
1877 fn test_param_int() {
1878 test_parameterized::<int>(5, 72, 64, 175);
1882 fn test_param_taggy() {
1883 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1887 fn test_param_taggypar() {
1888 test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
1889 Twopar::<int>(1, 2),
1890 Threepar::<int>(1, 2, 3),
1891 Twopar::<int>(17, 42));
1895 fn test_param_reccy() {
1896 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1897 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1898 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1899 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1900 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1904 fn test_with_capacity() {
1905 let mut d = RingBuf::with_capacity(0);
1907 assert_eq!(d.len(), 1);
1908 let mut d = RingBuf::with_capacity(50);
1910 assert_eq!(d.len(), 1);
1914 fn test_with_capacity_non_power_two() {
1915 let mut d3 = RingBuf::with_capacity(3);
1920 assert_eq!(d3.pop_front(), Some(1));
1922 assert_eq!(d3.front(), None);
1929 assert_eq!(d3.pop_front(), Some(3));
1931 // Pushing the lo past half way point to trigger
1932 // the 'B' scenario for growth
1939 // There used to be a bug here about how the
1940 // RingBuf made growth assumptions about the
1941 // underlying Vec which didn't hold and lead
1943 // (Vec grows to next power of two)
1944 //good- [9, 12, 15, X, X, X, X, |6]
1945 //bug- [15, 12, X, X, X, |6, X, X]
1946 assert_eq!(d3.pop_front(), Some(6));
1948 // Which leads us to the following state which
1949 // would be a failure case.
1950 //bug- [15, 12, X, X, X, X, |X, X]
1951 assert_eq!(d3.front(), Some(&9));
1955 fn test_reserve_exact() {
1956 let mut d = RingBuf::new();
1958 d.reserve_exact(50);
1959 assert!(d.capacity() >= 51);
1960 let mut d = RingBuf::new();
1962 d.reserve_exact(50);
1963 assert!(d.capacity() >= 51);
1968 let mut d = RingBuf::new();
1971 assert!(d.capacity() >= 51);
1972 let mut d = RingBuf::new();
1975 assert!(d.capacity() >= 51);
1980 let mut d: RingBuf<int> = range(0i, 5).collect();
1983 assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
1988 let mut d = RingBuf::new();
1989 assert_eq!(d.iter().next(), None);
1990 assert_eq!(d.iter().size_hint(), (0, Some(0)));
1992 for i in range(0i, 5) {
1996 let b: &[_] = &[&0,&1,&2,&3,&4];
1997 assert_eq!(d.iter().collect::<Vec<&int>>(), b);
2000 for i in range(6i, 9) {
2004 let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
2005 assert_eq!(d.iter().collect::<Vec<&int>>(), b);
2008 let mut it = d.iter();
2009 let mut len = d.len();
2013 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
2019 fn test_rev_iter() {
2020 let mut d = RingBuf::new();
2021 assert_eq!(d.iter().rev().next(), None);
2023 for i in range(0i, 5) {
2027 let b: &[_] = &[&4,&3,&2,&1,&0];
2028 assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
2031 for i in range(6i, 9) {
2034 let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
2035 assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
2039 fn test_mut_rev_iter_wrap() {
2040 let mut d = RingBuf::with_capacity(3);
2041 assert!(d.iter_mut().rev().next().is_none());
2046 assert_eq!(d.pop_front(), Some(1));
2049 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
2054 fn test_mut_iter() {
2055 let mut d = RingBuf::new();
2056 assert!(d.iter_mut().next().is_none());
2058 for i in range(0u, 3) {
2062 for (i, elt) in d.iter_mut().enumerate() {
2063 assert_eq!(*elt, 2 - i);
2068 let mut it = d.iter_mut();
2069 assert_eq!(*it.next().unwrap(), 0);
2070 assert_eq!(*it.next().unwrap(), 1);
2071 assert_eq!(*it.next().unwrap(), 2);
2072 assert!(it.next().is_none());
2077 fn test_mut_rev_iter() {
2078 let mut d = RingBuf::new();
2079 assert!(d.iter_mut().rev().next().is_none());
2081 for i in range(0u, 3) {
2085 for (i, elt) in d.iter_mut().rev().enumerate() {
2086 assert_eq!(*elt, i);
2091 let mut it = d.iter_mut().rev();
2092 assert_eq!(*it.next().unwrap(), 0);
2093 assert_eq!(*it.next().unwrap(), 1);
2094 assert_eq!(*it.next().unwrap(), 2);
2095 assert!(it.next().is_none());
2100 fn test_into_iter() {
2104 let d: RingBuf<int> = RingBuf::new();
2105 let mut iter = d.into_iter();
2107 assert_eq!(iter.size_hint(), (0, Some(0)));
2108 assert_eq!(iter.next(), None);
2109 assert_eq!(iter.size_hint(), (0, Some(0)));
2114 let mut d = RingBuf::new();
2115 for i in range(0i, 5) {
2119 let b = vec![0,1,2,3,4];
2120 assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
2125 let mut d = RingBuf::new();
2126 for i in range(0i, 5) {
2129 for i in range(6, 9) {
2133 let b = vec![8,7,6,0,1,2,3,4];
2134 assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
2139 let mut d = RingBuf::new();
2140 for i in range(0i, 5) {
2143 for i in range(6, 9) {
2147 let mut it = d.into_iter();
2148 assert_eq!(it.size_hint(), (8, Some(8)));
2149 assert_eq!(it.next(), Some(8));
2150 assert_eq!(it.size_hint(), (7, Some(7)));
2151 assert_eq!(it.next_back(), Some(4));
2152 assert_eq!(it.size_hint(), (6, Some(6)));
2153 assert_eq!(it.next(), Some(7));
2154 assert_eq!(it.size_hint(), (5, Some(5)));
2163 let mut d: RingBuf<int> = RingBuf::new();
2166 let mut iter = d.drain();
2168 assert_eq!(iter.size_hint(), (0, Some(0)));
2169 assert_eq!(iter.next(), None);
2170 assert_eq!(iter.size_hint(), (0, Some(0)));
2173 assert!(d.is_empty());
2178 let mut d = RingBuf::new();
2179 for i in range(0i, 5) {
2183 assert_eq!(d.drain().collect::<Vec<int>>(), [0, 1, 2, 3, 4]);
2184 assert!(d.is_empty());
2189 let mut d = RingBuf::new();
2190 for i in range(0i, 5) {
2193 for i in range(6, 9) {
2197 assert_eq!(d.drain().collect::<Vec<int>>(), [8,7,6,0,1,2,3,4]);
2198 assert!(d.is_empty());
2203 let mut d = RingBuf::new();
2204 for i in range(0i, 5) {
2207 for i in range(6, 9) {
2212 let mut it = d.drain();
2213 assert_eq!(it.size_hint(), (8, Some(8)));
2214 assert_eq!(it.next(), Some(8));
2215 assert_eq!(it.size_hint(), (7, Some(7)));
2216 assert_eq!(it.next_back(), Some(4));
2217 assert_eq!(it.size_hint(), (6, Some(6)));
2218 assert_eq!(it.next(), Some(7));
2219 assert_eq!(it.size_hint(), (5, Some(5)));
2221 assert!(d.is_empty());
2226 fn test_from_iter() {
2228 let v = vec!(1i,2,3,4,5,6,7);
2229 let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
2230 let u: Vec<int> = deq.iter().map(|&x| x).collect();
2233 let seq = iter::count(0u, 2).take(256);
2234 let deq: RingBuf<uint> = seq.collect();
2235 for (i, &x) in deq.iter().enumerate() {
2238 assert_eq!(deq.len(), 256);
2243 let mut d = RingBuf::new();
2248 assert_eq!(d.len(), 4u);
2249 let mut e = d.clone();
2250 assert_eq!(e.len(), 4u);
2251 while !d.is_empty() {
2252 assert_eq!(d.pop_back(), e.pop_back());
2254 assert_eq!(d.len(), 0u);
2255 assert_eq!(e.len(), 0u);
2260 let mut d = RingBuf::new();
2261 assert!(d == RingBuf::with_capacity(0));
2266 let mut e = RingBuf::with_capacity(0);
2276 assert!(e == RingBuf::new());
2281 let mut x = RingBuf::new();
2282 let mut y = RingBuf::new();
2294 assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
2299 let x = RingBuf::new();
2300 let mut y = RingBuf::new();
2312 let ringbuf: RingBuf<int> = range(0i, 10).collect();
2313 assert_eq!(format!("{:?}", ringbuf), "RingBuf [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
2315 let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
2318 assert_eq!(format!("{:?}", ringbuf), "RingBuf [\"just\", \"one\", \"test\", \"more\"]");
2323 static mut drops: uint = 0;
2325 impl Drop for Elem {
2326 fn drop(&mut self) {
2327 unsafe { drops += 1; }
2331 let mut ring = RingBuf::new();
2332 ring.push_back(Elem);
2333 ring.push_front(Elem);
2334 ring.push_back(Elem);
2335 ring.push_front(Elem);
2338 assert_eq!(unsafe {drops}, 4);
2342 fn test_drop_with_pop() {
2343 static mut drops: uint = 0;
2345 impl Drop for Elem {
2346 fn drop(&mut self) {
2347 unsafe { drops += 1; }
2351 let mut ring = RingBuf::new();
2352 ring.push_back(Elem);
2353 ring.push_front(Elem);
2354 ring.push_back(Elem);
2355 ring.push_front(Elem);
2357 drop(ring.pop_back());
2358 drop(ring.pop_front());
2359 assert_eq!(unsafe {drops}, 2);
2362 assert_eq!(unsafe {drops}, 4);
2366 fn test_drop_clear() {
2367 static mut drops: uint = 0;
2369 impl Drop for Elem {
2370 fn drop(&mut self) {
2371 unsafe { drops += 1; }
2375 let mut ring = RingBuf::new();
2376 ring.push_back(Elem);
2377 ring.push_front(Elem);
2378 ring.push_back(Elem);
2379 ring.push_front(Elem);
2381 assert_eq!(unsafe {drops}, 4);
2384 assert_eq!(unsafe {drops}, 4);
2388 fn test_reserve_grow() {
2389 // test growth path A
2390 // [T o o H] -> [T o o H . . . . ]
2391 let mut ring = RingBuf::with_capacity(4);
2392 for i in range(0i, 3) {
2396 for i in range(0i, 3) {
2397 assert_eq!(ring.pop_front(), Some(i));
2400 // test growth path B
2401 // [H T o o] -> [. T o o H . . . ]
2402 let mut ring = RingBuf::with_capacity(4);
2403 for i in range(0i, 1) {
2405 assert_eq!(ring.pop_front(), Some(i));
2407 for i in range(0i, 3) {
2411 for i in range(0i, 3) {
2412 assert_eq!(ring.pop_front(), Some(i));
2415 // test growth path C
2416 // [o o H T] -> [o o H . . . . T ]
2417 let mut ring = RingBuf::with_capacity(4);
2418 for i in range(0i, 3) {
2420 assert_eq!(ring.pop_front(), Some(i));
2422 for i in range(0i, 3) {
2426 for i in range(0i, 3) {
2427 assert_eq!(ring.pop_front(), Some(i));
2433 let mut ring = RingBuf::new();
2435 assert_eq!(ring.get(0), Some(&0));
2436 assert_eq!(ring.get(1), None);
2439 assert_eq!(ring.get(0), Some(&0));
2440 assert_eq!(ring.get(1), Some(&1));
2441 assert_eq!(ring.get(2), None);
2444 assert_eq!(ring.get(0), Some(&0));
2445 assert_eq!(ring.get(1), Some(&1));
2446 assert_eq!(ring.get(2), Some(&2));
2447 assert_eq!(ring.get(3), None);
2449 assert_eq!(ring.pop_front(), Some(0));
2450 assert_eq!(ring.get(0), Some(&1));
2451 assert_eq!(ring.get(1), Some(&2));
2452 assert_eq!(ring.get(2), None);
2454 assert_eq!(ring.pop_front(), Some(1));
2455 assert_eq!(ring.get(0), Some(&2));
2456 assert_eq!(ring.get(1), None);
2458 assert_eq!(ring.pop_front(), Some(2));
2459 assert_eq!(ring.get(0), None);
2460 assert_eq!(ring.get(1), None);
2465 let mut ring = RingBuf::new();
2466 for i in range(0i, 3) {
2470 match ring.get_mut(1) {
2475 assert_eq!(ring.get_mut(0), Some(&mut 0));
2476 assert_eq!(ring.get_mut(1), Some(&mut -1));
2477 assert_eq!(ring.get_mut(2), Some(&mut 2));
2478 assert_eq!(ring.get_mut(3), None);
2480 assert_eq!(ring.pop_front(), Some(0));
2481 assert_eq!(ring.get_mut(0), Some(&mut -1));
2482 assert_eq!(ring.get_mut(1), Some(&mut 2));
2483 assert_eq!(ring.get_mut(2), None);
2487 fn test_swap_front_back_remove() {
2488 fn test(back: bool) {
2489 // This test checks that every single combination of tail position and length is tested.
2490 // Capacity 15 should be large enough to cover every case.
2491 let mut tester = RingBuf::with_capacity(15);
2492 let usable_cap = tester.capacity();
2493 let final_len = usable_cap / 2;
2495 for len in range(0, final_len) {
2496 let expected = if back {
2497 range(0, len).collect()
2499 range(0, len).rev().collect()
2501 for tail_pos in range(0, usable_cap) {
2502 tester.tail = tail_pos;
2503 tester.head = tail_pos;
2505 for i in range(0, len * 2) {
2506 tester.push_front(i);
2508 for i in range(0, len) {
2509 assert_eq!(tester.swap_back_remove(i), Some(len * 2 - 1 - i));
2512 for i in range(0, len * 2) {
2513 tester.push_back(i);
2515 for i in range(0, len) {
2516 let idx = tester.len() - 1 - i;
2517 assert_eq!(tester.swap_front_remove(idx), Some(len * 2 - 1 - i));
2520 assert!(tester.tail < tester.cap);
2521 assert!(tester.head < tester.cap);
2522 assert_eq!(tester, expected);
2532 // This test checks that every single combination of tail position, length, and
2533 // insertion position is tested. Capacity 15 should be large enough to cover every case.
2535 let mut tester = RingBuf::with_capacity(15);
2536 // can't guarantee we got 15, so have to get what we got.
2537 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2538 // this test isn't covering what it wants to
2539 let cap = tester.capacity();
2542 // len is the length *after* insertion
2543 for len in range(1, cap) {
2544 // 0, 1, 2, .., len - 1
2545 let expected = iter::count(0, 1).take(len).collect();
2546 for tail_pos in range(0, cap) {
2547 for to_insert in range(0, len) {
2548 tester.tail = tail_pos;
2549 tester.head = tail_pos;
2550 for i in range(0, len) {
2552 tester.push_back(i);
2555 tester.insert(to_insert, to_insert);
2556 assert!(tester.tail < tester.cap);
2557 assert!(tester.head < tester.cap);
2558 assert_eq!(tester, expected);
2566 // This test checks that every single combination of tail position, length, and
2567 // removal position is tested. Capacity 15 should be large enough to cover every case.
2569 let mut tester = RingBuf::with_capacity(15);
2570 // can't guarantee we got 15, so have to get what we got.
2571 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2572 // this test isn't covering what it wants to
2573 let cap = tester.capacity();
2575 // len is the length *after* removal
2576 for len in range(0, cap - 1) {
2577 // 0, 1, 2, .., len - 1
2578 let expected = iter::count(0, 1).take(len).collect();
2579 for tail_pos in range(0, cap) {
2580 for to_remove in range(0, len + 1) {
2581 tester.tail = tail_pos;
2582 tester.head = tail_pos;
2583 for i in range(0, len) {
2585 tester.push_back(1234);
2587 tester.push_back(i);
2589 if to_remove == len {
2590 tester.push_back(1234);
2592 tester.remove(to_remove);
2593 assert!(tester.tail < tester.cap);
2594 assert!(tester.head < tester.cap);
2595 assert_eq!(tester, expected);
2602 fn test_shrink_to_fit() {
2603 // This test checks that every single combination of head and tail position,
2604 // is tested. Capacity 15 should be large enough to cover every case.
2606 let mut tester = RingBuf::with_capacity(15);
2607 // can't guarantee we got 15, so have to get what we got.
2608 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2609 // this test isn't covering what it wants to
2610 let cap = tester.capacity();
2612 let max_cap = tester.capacity();
2614 for len in range(0, cap + 1) {
2615 // 0, 1, 2, .., len - 1
2616 let expected = iter::count(0, 1).take(len).collect();
2617 for tail_pos in range(0, max_cap + 1) {
2618 tester.tail = tail_pos;
2619 tester.head = tail_pos;
2621 for i in range(0, len) {
2622 tester.push_back(i);
2624 tester.shrink_to_fit();
2625 assert!(tester.capacity() <= cap);
2626 assert!(tester.tail < tester.cap);
2627 assert!(tester.head < tester.cap);
2628 assert_eq!(tester, expected);
2635 let mut ring = RingBuf::new();
2636 ring.push_back(10i);
2637 ring.push_back(20i);
2638 assert_eq!(ring.front(), Some(&10));
2640 assert_eq!(ring.front(), Some(&20));
2642 assert_eq!(ring.front(), None);
2646 fn test_as_slices() {
2647 let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2648 let cap = ring.capacity() as int;
2650 let last = cap - first;
2651 for i in range(0, first) {
2654 let (left, right) = ring.as_slices();
2655 let expected: Vec<_> = range(0, i+1).collect();
2656 assert_eq!(left, expected);
2657 assert_eq!(right, []);
2660 for j in range(-last, 0) {
2662 let (left, right) = ring.as_slices();
2663 let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2664 let expected_right: Vec<_> = range(0, first).collect();
2665 assert_eq!(left, expected_left);
2666 assert_eq!(right, expected_right);
2669 assert_eq!(ring.len() as int, cap);
2670 assert_eq!(ring.capacity() as int, cap);
2674 fn test_as_mut_slices() {
2675 let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2676 let cap = ring.capacity() as int;
2678 let last = cap - first;
2679 for i in range(0, first) {
2682 let (left, right) = ring.as_mut_slices();
2683 let expected: Vec<_> = range(0, i+1).collect();
2684 assert_eq!(left, expected);
2685 assert_eq!(right, []);
2688 for j in range(-last, 0) {
2690 let (left, right) = ring.as_mut_slices();
2691 let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2692 let expected_right: Vec<_> = range(0, first).collect();
2693 assert_eq!(left, expected_left);
2694 assert_eq!(right, expected_right);
2697 assert_eq!(ring.len() as int, cap);
2698 assert_eq!(ring.capacity() as int, cap);