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