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.
4 //
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.
10
11 //! A double-ended queue implemented as a circular buffer
12 //!
13 //! RingBuf implements the trait Deque. It should be imported with `use
14 //! collections::deque::Deque`.
15
16 use std::cmp;
17 use std::iter::{Rev, RandomAccessIterator};
18
19 use deque::Deque;
20
21 static INITIAL_CAPACITY: uint = 8u; // 2^3
22 static MINIMUM_CAPACITY: uint = 2u;
23
24 /// RingBuf is a circular buffer that implements Deque.
25 #[deriving(Clone)]
26 pub struct RingBuf<T> {
27 nelts: uint,
28 lo: uint,
29 elts: Vec<Option<T>>
30 }
31
32 impl<T> Container for RingBuf<T> {
33 /// Return the number of elements in the RingBuf
34 fn len(&self) -> uint { self.nelts }
35 }
36
37 impl<T> Mutable for RingBuf<T> {
38 /// Clear the RingBuf, removing all values.
39 fn clear(&mut self) {
40 for x in self.elts.mut_iter() { *x = None }
41 self.nelts = 0;
42 self.lo = 0;
43 }
44 }
45
46 impl<T> Deque<T> for RingBuf<T> {
47 /// Return a reference to the first element in the RingBuf
48 fn front<'a>(&'a self) -> Option<&'a T> {
49 if self.nelts > 0 { Some(self.get(0)) } else { None }
50 }
51
52 /// Return a mutable reference to the first element in the RingBuf
53 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
54 if self.nelts > 0 { Some(self.get_mut(0)) } else { None }
55 }
56
57 /// Return a reference to the last element in the RingBuf
58 fn back<'a>(&'a self) -> Option<&'a T> {
59 if self.nelts > 0 { Some(self.get(self.nelts - 1)) } else { None }
60 }
61
62 /// Return a mutable reference to the last element in the RingBuf
63 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
64 if self.nelts > 0 { Some(self.get_mut(self.nelts - 1)) } else { None }
65 }
66
67 /// Remove and return the first element in the RingBuf, or None if it is empty
68 fn pop_front(&mut self) -> Option<T> {
69 let result = self.elts.get_mut(self.lo).take();
70 if result.is_some() {
71 self.lo = (self.lo + 1u) % self.elts.len();
72 self.nelts -= 1u;
73 }
74 result
75 }
76
77 /// Remove and return the last element in the RingBuf, or None if it is empty
78 fn pop_back(&mut self) -> Option<T> {
79 if self.nelts > 0 {
80 self.nelts -= 1;
81 let hi = self.raw_index(self.nelts);
82 self.elts.get_mut(hi).take()
83 } else {
84 None
85 }
86 }
87
88 /// Prepend an element to the RingBuf
89 fn push_front(&mut self, t: T) {
90 if self.nelts == self.elts.len() {
91 grow(self.nelts, &mut self.lo, &mut self.elts);
92 }
93 if self.lo == 0u {
94 self.lo = self.elts.len() - 1u;
95 } else { self.lo -= 1u; }
96 *self.elts.get_mut(self.lo) = Some(t);
97 self.nelts += 1u;
98 }
99
100 /// Append an element to the RingBuf
101 fn push_back(&mut self, t: T) {
102 if self.nelts == self.elts.len() {
103 grow(self.nelts, &mut self.lo, &mut self.elts);
104 }
105 let hi = self.raw_index(self.nelts);
106 *self.elts.get_mut(hi) = Some(t);
107 self.nelts += 1u;
108 }
109 }
110
111 impl<T> RingBuf<T> {
112 /// Create an empty RingBuf
113 pub fn new() -> RingBuf<T> {
114 RingBuf::with_capacity(INITIAL_CAPACITY)
115 }
116
117 /// Create an empty RingBuf with space for at least `n` elements.
118 pub fn with_capacity(n: uint) -> RingBuf<T> {
119 RingBuf{nelts: 0, lo: 0,
120 elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
121 }
122
123 /// Retrieve an element in the RingBuf by index
124 ///
125 /// Fails if there is no element with the given index
126 pub fn get<'a>(&'a self, i: uint) -> &'a T {
127 let idx = self.raw_index(i);
128 match *self.elts.get(idx) {
129 None => fail!(),
130 Some(ref v) => v
131 }
132 }
133
134 /// Retrieve an element in the RingBuf by index
135 ///
136 /// Fails if there is no element with the given index
137 pub fn get_mut<'a>(&'a mut self, i: uint) -> &'a mut T {
138 let idx = self.raw_index(i);
139 match *self.elts.get_mut(idx) {
140 None => fail!(),
141 Some(ref mut v) => v
142 }
143 }
144
145 /// Swap elements at indices `i` and `j`
146 ///
147 /// `i` and `j` may be equal.
148 ///
149 /// Fails if there is no element with the given index
150 pub fn swap(&mut self, i: uint, j: uint) {
151 assert!(i < self.len());
152 assert!(j < self.len());
153 let ri = self.raw_index(i);
154 let rj = self.raw_index(j);
155 self.elts.as_mut_slice().swap(ri, rj);
156 }
157
158 /// Return index in underlying vec for a given logical element index
159 fn raw_index(&self, idx: uint) -> uint {
160 raw_index(self.lo, self.elts.len(), idx)
161 }
162
163 /// Reserve capacity for exactly `n` elements in the given RingBuf,
164 /// doing nothing if `self`'s capacity is already equal to or greater
165 /// than the requested capacity
166 ///
167 /// # Arguments
168 ///
169 /// * n - The number of elements to reserve space for
170 pub fn reserve_exact(&mut self, n: uint) {
171 self.elts.reserve_exact(n);
172 }
173
174 /// Reserve capacity for at least `n` elements in the given RingBuf,
175 /// over-allocating in case the caller needs to reserve additional
176 /// space.
177 ///
178 /// Do nothing if `self`'s capacity is already equal to or greater
179 /// than the requested capacity.
180 ///
181 /// # Arguments
182 ///
183 /// * n - The number of elements to reserve space for
184 pub fn reserve(&mut self, n: uint) {
185 self.elts.reserve(n);
186 }
187
188 /// Front-to-back iterator.
189 pub fn iter<'a>(&'a self) -> Items<'a, T> {
190 Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
191 }
192
193 #[deprecated = "replaced by .iter().rev()"]
194 pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
195 self.iter().rev()
196 }
197
198 /// Front-to-back iterator which returns mutable values.
199 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
200 let start_index = raw_index(self.lo, self.elts.len(), 0);
201 let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
202
203 // Divide up the array
204 if end_index <= start_index {
205 // Items to iterate goes from:
206 // start_index to self.elts.len()
207 // and then
208 // 0 to end_index
209 let (temp, remaining1) = self.elts.mut_split_at(start_index);
210 let (remaining2, _) = temp.mut_split_at(end_index);
211 MutItems { remaining1: remaining1,
212 remaining2: remaining2,
213 nelts: self.nelts }
214 } else {
215 // Items to iterate goes from start_index to end_index:
216 let (empty, elts) = self.elts.mut_split_at(0);
217 let remaining1 = elts.mut_slice(start_index, end_index);
218 MutItems { remaining1: remaining1,
219 remaining2: empty,
220 nelts: self.nelts }
221 }
222 }
223
224 #[deprecated = "replaced by .mut_iter().rev()"]
225 pub fn mut_rev_iter<'a>(&'a mut self) -> Rev<MutItems<'a, T>> {
226 self.mut_iter().rev()
227 }
228 }
229
230 /// RingBuf iterator
231 pub struct Items<'a, T> {
232 lo: uint,
233 index: uint,
234 rindex: uint,
235 elts: &'a [Option<T>],
236 }
237
238 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
239 #[inline]
240 fn next(&mut self) -> Option<&'a T> {
241 if self.index == self.rindex {
242 return None;
243 }
244 let raw_index = raw_index(self.lo, self.elts.len(), self.index);
245 self.index += 1;
246 Some(self.elts[raw_index].get_ref())
247 }
248
249 #[inline]
250 fn size_hint(&self) -> (uint, Option<uint>) {
251 let len = self.rindex - self.index;
252 (len, Some(len))
253 }
254 }
255
256 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
257 #[inline]
258 fn next_back(&mut self) -> Option<&'a T> {
259 if self.index == self.rindex {
260 return None;
261 }
262 self.rindex -= 1;
263 let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
264 Some(self.elts[raw_index].get_ref())
265 }
266 }
267
268 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
269
270 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
271 #[inline]
272 fn indexable(&self) -> uint { self.rindex - self.index }
273
274 #[inline]
275 fn idx(&mut self, j: uint) -> Option<&'a T> {
276 if j >= self.indexable() {
277 None
278 } else {
279 let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
280 Some(self.elts[raw_index].get_ref())
281 }
282 }
283 }
284
285 /// RingBuf mutable iterator
286 pub struct MutItems<'a, T> {
287 remaining1: &'a mut [Option<T>],
288 remaining2: &'a mut [Option<T>],
289 nelts: uint,
290 }
291
292 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
293 #[inline]
294 fn next(&mut self) -> Option<&'a mut T> {
295 if self.nelts == 0 {
296 return None;
297 }
298 let r = if self.remaining1.len() > 0 {
299 &mut self.remaining1
300 } else {
301 assert!(self.remaining2.len() > 0);
302 &mut self.remaining2
303 };
304 self.nelts -= 1;
305 Some(r.mut_shift_ref().unwrap().get_mut_ref())
306 }
307
308 #[inline]
309 fn size_hint(&self) -> (uint, Option<uint>) {
310 (self.nelts, Some(self.nelts))
311 }
312 }
313
314 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
315 #[inline]
316 fn next_back(&mut self) -> Option<&'a mut T> {
317 if self.nelts == 0 {
318 return None;
319 }
320 let r = if self.remaining2.len() > 0 {
321 &mut self.remaining2
322 } else {
323 assert!(self.remaining1.len() > 0);
324 &mut self.remaining1
325 };
326 self.nelts -= 1;
327 Some(r.mut_pop_ref().unwrap().get_mut_ref())
328 }
329 }
330
331 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
332
333 /// Grow is only called on full elts, so nelts is also len(elts), unlike
334 /// elsewhere.
335 fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
336 assert_eq!(nelts, elts.len());
337 let lo = *loptr;
338 let newlen = nelts * 2;
339 elts.reserve(newlen);
340
341 /* fill with None */
342 for _ in range(elts.len(), elts.capacity()) {
343 elts.push(None);
344 }
345
346 /*
347 Move the shortest half into the newly reserved area.
348 lo ---->|
349 nelts ----------->|
350 [o o o|o o o o o]
351 A [. . .|o o o o o o o o|. . . . .]
352 B [o o o|. . . . . . . .|o o o o o]
353 */
354
355 assert!(newlen - nelts/2 >= nelts);
356 if lo <= (nelts - lo) { // A
357 for i in range(0u, lo) {
358 elts.as_mut_slice().swap(i, nelts + i);
359 }
360 } else { // B
361 for i in range(lo, nelts) {
362 elts.as_mut_slice().swap(i, newlen - nelts + i);
363 }
364 *loptr += newlen - nelts;
365 }
366 }
367
368 /// Return index in underlying vec for a given logical element index
369 fn raw_index(lo: uint, len: uint, index: uint) -> uint {
370 if lo >= len - index {
371 lo + index - len
372 } else {
373 lo + index
374 }
375 }
376
377 impl<A: Eq> Eq for RingBuf<A> {
378 fn eq(&self, other: &RingBuf<A>) -> bool {
379 self.nelts == other.nelts &&
380 self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
381 }
382 fn ne(&self, other: &RingBuf<A>) -> bool {
383 !self.eq(other)
384 }
385 }
386
387 impl<A> FromIterator<A> for RingBuf<A> {
388 fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
389 let (lower, _) = iterator.size_hint();
390 let mut deq = RingBuf::with_capacity(lower);
391 deq.extend(iterator);
392 deq
393 }
394 }
395
396 impl<A> Extendable<A> for RingBuf<A> {
397 fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
398 for elt in iterator {
399 self.push_back(elt);
400 }
401 }
402 }
403
404 #[cfg(test)]
405 mod tests {
406 extern crate test;
407 use self::test::Bencher;
408 use deque::Deque;
409 use std::clone::Clone;
410 use std::cmp::Eq;
411 use std::fmt::Show;
412 use super::RingBuf;
413
414 #[test]
415 fn test_simple() {
416 let mut d = RingBuf::new();
417 assert_eq!(d.len(), 0u);
418 d.push_front(17);
419 d.push_front(42);
420 d.push_back(137);
421 assert_eq!(d.len(), 3u);
422 d.push_back(137);
423 assert_eq!(d.len(), 4u);
424 debug!("{:?}", d.front());
425 assert_eq!(*d.front().unwrap(), 42);
426 debug!("{:?}", d.back());
427 assert_eq!(*d.back().unwrap(), 137);
428 let mut i = d.pop_front();
429 debug!("{:?}", i);
430 assert_eq!(i, Some(42));
431 i = d.pop_back();
432 debug!("{:?}", i);
433 assert_eq!(i, Some(137));
434 i = d.pop_back();
435 debug!("{:?}", i);
436 assert_eq!(i, Some(137));
437 i = d.pop_back();
438 debug!("{:?}", i);
439 assert_eq!(i, Some(17));
440 assert_eq!(d.len(), 0u);
441 d.push_back(3);
442 assert_eq!(d.len(), 1u);
443 d.push_front(2);
444 assert_eq!(d.len(), 2u);
445 d.push_back(4);
446 assert_eq!(d.len(), 3u);
447 d.push_front(1);
448 assert_eq!(d.len(), 4u);
449 debug!("{:?}", d.get(0));
450 debug!("{:?}", d.get(1));
451 debug!("{:?}", d.get(2));
452 debug!("{:?}", d.get(3));
453 assert_eq!(*d.get(0), 1);
454 assert_eq!(*d.get(1), 2);
455 assert_eq!(*d.get(2), 3);
456 assert_eq!(*d.get(3), 4);
457 }
458
459 #[test]
460 fn test_boxes() {
461 let a: @int = @5;
462 let b: @int = @72;
463 let c: @int = @64;
464 let d: @int = @175;
465
466 let mut deq = RingBuf::new();
467 assert_eq!(deq.len(), 0);
468 deq.push_front(a);
469 deq.push_front(b);
470 deq.push_back(c);
471 assert_eq!(deq.len(), 3);
472 deq.push_back(d);
473 assert_eq!(deq.len(), 4);
474 assert_eq!(deq.front(), Some(&b));
475 assert_eq!(deq.back(), Some(&d));
476 assert_eq!(deq.pop_front(), Some(b));
477 assert_eq!(deq.pop_back(), Some(d));
478 assert_eq!(deq.pop_back(), Some(c));
479 assert_eq!(deq.pop_back(), Some(a));
480 assert_eq!(deq.len(), 0);
481 deq.push_back(c);
482 assert_eq!(deq.len(), 1);
483 deq.push_front(b);
484 assert_eq!(deq.len(), 2);
485 deq.push_back(d);
486 assert_eq!(deq.len(), 3);
487 deq.push_front(a);
488 assert_eq!(deq.len(), 4);
489 assert_eq!(*deq.get(0), a);
490 assert_eq!(*deq.get(1), b);
491 assert_eq!(*deq.get(2), c);
492 assert_eq!(*deq.get(3), d);
493 }
494
495 #[cfg(test)]
496 fn test_parameterized<T:Clone + Eq + Show>(a: T, b: T, c: T, d: T) {
497 let mut deq = RingBuf::new();
498 assert_eq!(deq.len(), 0);
499 deq.push_front(a.clone());
500 deq.push_front(b.clone());
501 deq.push_back(c.clone());
502 assert_eq!(deq.len(), 3);
503 deq.push_back(d.clone());
504 assert_eq!(deq.len(), 4);
505 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
506 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
507 assert_eq!(deq.pop_front().unwrap(), b.clone());
508 assert_eq!(deq.pop_back().unwrap(), d.clone());
509 assert_eq!(deq.pop_back().unwrap(), c.clone());
510 assert_eq!(deq.pop_back().unwrap(), a.clone());
511 assert_eq!(deq.len(), 0);
512 deq.push_back(c.clone());
513 assert_eq!(deq.len(), 1);
514 deq.push_front(b.clone());
515 assert_eq!(deq.len(), 2);
516 deq.push_back(d.clone());
517 assert_eq!(deq.len(), 3);
518 deq.push_front(a.clone());
519 assert_eq!(deq.len(), 4);
520 assert_eq!((*deq.get(0)).clone(), a.clone());
521 assert_eq!((*deq.get(1)).clone(), b.clone());
522 assert_eq!((*deq.get(2)).clone(), c.clone());
523 assert_eq!((*deq.get(3)).clone(), d.clone());
524 }
525
526 #[test]
527 fn test_push_front_grow() {
528 let mut deq = RingBuf::new();
529 for i in range(0u, 66) {
530 deq.push_front(i);
531 }
532 assert_eq!(deq.len(), 66);
533
534 for i in range(0u, 66) {
535 assert_eq!(*deq.get(i), 65 - i);
536 }
537
538 let mut deq = RingBuf::new();
539 for i in range(0u, 66) {
540 deq.push_back(i);
541 }
542
543 for i in range(0u, 66) {
544 assert_eq!(*deq.get(i), i);
545 }
546 }
547
548 #[bench]
549 fn bench_new(b: &mut test::Bencher) {
550 b.iter(|| {
551 let _: RingBuf<u64> = RingBuf::new();
552 })
553 }
554
555 #[bench]
556 fn bench_push_back(b: &mut test::Bencher) {
557 let mut deq = RingBuf::new();
558 b.iter(|| {
559 deq.push_back(0);
560 })
561 }
562
563 #[bench]
564 fn bench_push_front(b: &mut test::Bencher) {
565 let mut deq = RingBuf::new();
566 b.iter(|| {
567 deq.push_front(0);
568 })
569 }
570
571 #[bench]
572 fn bench_grow(b: &mut test::Bencher) {
573 let mut deq = RingBuf::new();
574 b.iter(|| {
575 for _ in range(0, 65) {
576 deq.push_front(1);
577 }
578 })
579 }
580
581 #[deriving(Clone, Eq, Show)]
582 enum Taggy {
583 One(int),
584 Two(int, int),
585 Three(int, int, int),
586 }
587
588 #[deriving(Clone, Eq, Show)]
589 enum Taggypar<T> {
590 Onepar(int),
591 Twopar(int, int),
592 Threepar(int, int, int),
593 }
594
595 #[deriving(Clone, Eq, Show)]
596 struct RecCy {
597 x: int,
598 y: int,
599 t: Taggy
600 }
601
602 #[test]
603 fn test_param_int() {
604 test_parameterized::<int>(5, 72, 64, 175);
605 }
606
607 #[test]
608 fn test_param_at_int() {
609 test_parameterized::<@int>(@5, @72, @64, @175);
610 }
611
612 #[test]
613 fn test_param_taggy() {
614 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
615 }
616
617 #[test]
618 fn test_param_taggypar() {
619 test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
620 Twopar::<int>(1, 2),
621 Threepar::<int>(1, 2, 3),
622 Twopar::<int>(17, 42));
623 }
624
625 #[test]
626 fn test_param_reccy() {
627 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
628 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
629 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
630 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
631 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
632 }
633
634 #[test]
635 fn test_with_capacity() {
636 let mut d = RingBuf::with_capacity(0);
637 d.push_back(1);
638 assert_eq!(d.len(), 1);
639 let mut d = RingBuf::with_capacity(50);
640 d.push_back(1);
641 assert_eq!(d.len(), 1);
642 }
643
644 #[test]
645 fn test_reserve_exact() {
646 let mut d = RingBuf::new();
647 d.push_back(0u64);
648 d.reserve_exact(50);
649 assert_eq!(d.elts.capacity(), 50);
650 let mut d = RingBuf::new();
651 d.push_back(0u32);
652 d.reserve_exact(50);
653 assert_eq!(d.elts.capacity(), 50);
654 }
655
656 #[test]
657 fn test_reserve() {
658 let mut d = RingBuf::new();
659 d.push_back(0u64);
660 d.reserve(50);
661 assert_eq!(d.elts.capacity(), 64);
662 let mut d = RingBuf::new();
663 d.push_back(0u32);
664 d.reserve(50);
665 assert_eq!(d.elts.capacity(), 64);
666 }
667
668 #[test]
669 fn test_swap() {
670 let mut d: RingBuf<int> = range(0, 5).collect();
671 d.pop_front();
672 d.swap(0, 3);
673 assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
674 }
675
676 #[test]
677 fn test_iter() {
678 let mut d = RingBuf::new();
679 assert_eq!(d.iter().next(), None);
680 assert_eq!(d.iter().size_hint(), (0, Some(0)));
681
682 for i in range(0, 5) {
683 d.push_back(i);
684 }
685 assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&0,&1,&2,&3,&4]);
686
687 for i in range(6, 9) {
688 d.push_front(i);
689 }
690 assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&8,&7,&6,&0,&1,&2,&3,&4]);
691
692 let mut it = d.iter();
693 let mut len = d.len();
694 loop {
695 match it.next() {
696 None => break,
697 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
698 }
699 }
700 }
701
702 #[test]
703 fn test_rev_iter() {
704 let mut d = RingBuf::new();
705 assert_eq!(d.iter().rev().next(), None);
706
707 for i in range(0, 5) {
708 d.push_back(i);
709 }
710 assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0]);
711
712 for i in range(6, 9) {
713 d.push_front(i);
714 }
715 assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0,&6,&7,&8]);
716 }
717
718 #[test]
719 fn test_mut_rev_iter_wrap() {
720 let mut d = RingBuf::with_capacity(3);
721 assert!(d.mut_iter().rev().next().is_none());
722
723 d.push_back(1);
724 d.push_back(2);
725 d.push_back(3);
726 assert_eq!(d.pop_front(), Some(1));
727 d.push_back(4);
728
729 assert_eq!(d.mut_iter().rev().map(|x| *x).collect::<Vec<int>>(),
730 vec!(4, 3, 2));
731 }
732
733 #[test]
734 fn test_mut_iter() {
735 let mut d = RingBuf::new();
736 assert!(d.mut_iter().next().is_none());
737
738 for i in range(0u, 3) {
739 d.push_front(i);
740 }
741
742 for (i, elt) in d.mut_iter().enumerate() {
743 assert_eq!(*elt, 2 - i);
744 *elt = i;
745 }
746
747 {
748 let mut it = d.mut_iter();
749 assert_eq!(*it.next().unwrap(), 0);
750 assert_eq!(*it.next().unwrap(), 1);
751 assert_eq!(*it.next().unwrap(), 2);
752 assert!(it.next().is_none());
753 }
754 }
755
756 #[test]
757 fn test_mut_rev_iter() {
758 let mut d = RingBuf::new();
759 assert!(d.mut_iter().rev().next().is_none());
760
761 for i in range(0u, 3) {
762 d.push_front(i);
763 }
764
765 for (i, elt) in d.mut_iter().rev().enumerate() {
766 assert_eq!(*elt, i);
767 *elt = i;
768 }
769
770 {
771 let mut it = d.mut_iter().rev();
772 assert_eq!(*it.next().unwrap(), 0);
773 assert_eq!(*it.next().unwrap(), 1);
774 assert_eq!(*it.next().unwrap(), 2);
775 assert!(it.next().is_none());
776 }
777 }
778
779 #[test]
780 fn test_from_iter() {
781 use std::iter;
782 let v = vec!(1,2,3,4,5,6,7);
783 let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
784 let u: Vec<int> = deq.iter().map(|&x| x).collect();
785 assert_eq!(u, v);
786
787 let mut seq = iter::count(0u, 2).take(256);
788 let deq: RingBuf<uint> = seq.collect();
789 for (i, &x) in deq.iter().enumerate() {
790 assert_eq!(2*i, x);
791 }
792 assert_eq!(deq.len(), 256);
793 }
794
795 #[test]
796 fn test_clone() {
797 let mut d = RingBuf::new();
798 d.push_front(17);
799 d.push_front(42);
800 d.push_back(137);
801 d.push_back(137);
802 assert_eq!(d.len(), 4u);
803 let mut e = d.clone();
804 assert_eq!(e.len(), 4u);
805 while !d.is_empty() {
806 assert_eq!(d.pop_back(), e.pop_back());
807 }
808 assert_eq!(d.len(), 0u);
809 assert_eq!(e.len(), 0u);
810 }
811
812 #[test]
813 fn test_eq() {
814 let mut d = RingBuf::new();
815 assert!(d == RingBuf::with_capacity(0));
816 d.push_front(137);
817 d.push_front(17);
818 d.push_front(42);
819 d.push_back(137);
820 let mut e = RingBuf::with_capacity(0);
821 e.push_back(42);
822 e.push_back(17);
823 e.push_back(137);
824 e.push_back(137);
825 assert!(&e == &d);
826 e.pop_back();
827 e.push_back(0);
828 assert!(e != d);
829 e.clear();
830 assert!(e == RingBuf::new());
831 }
832 }
libcollections/ringbuf.rs:368:69-368:69 -fn- definition:
/// Return index in underlying vec for a given logical element index
fn raw_index(lo: uint, len: uint, index: uint) -> uint {
if lo >= len - index {
references:- 6278: } else {
279: let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
280: Some(self.elts[raw_index].get_ref())
libcollections/ringbuf.rs:285:29-285:29 -struct- definition:
/// RingBuf mutable iterator
pub struct MutItems<'a, T> {
remaining1: &'a mut [Option<T>],
references:- 7217: let remaining1 = elts.mut_slice(start_index, end_index);
218: MutItems { remaining1: remaining1,
219: remaining2: empty,
--
292: impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
293: #[inline]
--
314: impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
315: #[inline]
--
331: impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
libcollections/ringbuf.rs:25:19-25:19 -struct- definition:
pub struct RingBuf<T> {
nelts: uint,
lo: uint,
references:- 17118: pub fn with_capacity(n: uint) -> RingBuf<T> {
119: RingBuf{nelts: 0, lo: 0,
120: elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
--
396: impl<A> Extendable<A> for RingBuf<A> {
397: fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
libcollections/ringbuf.rs:334:15-334:15 -fn- definition:
/// elsewhere.
fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
assert_eq!(nelts, elts.len());
references:- 290: if self.nelts == self.elts.len() {
91: grow(self.nelts, &mut self.lo, &mut self.elts);
92: }
--
102: if self.nelts == self.elts.len() {
103: grow(self.nelts, &mut self.lo, &mut self.elts);
104: }
libcollections/ringbuf.rs:230:21-230:21 -struct- definition:
/// RingBuf iterator
pub struct Items<'a, T> {
lo: uint,
references:- 7189: pub fn iter<'a>(&'a self) -> Items<'a, T> {
190: Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
191: }
--
193: #[deprecated = "replaced by .iter().rev()"]
194: pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
195: self.iter().rev()
--
256: impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
257: #[inline]
--
270: impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
271: #[inline]