1 // Copyright 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 //! Container traits for collections
12
13 use std::container::Mutable;
14
15 /// A double-ended sequence that allows querying, insertion and deletion at both ends.
16 pub trait Deque<T> : Mutable {
17 /// Provide a reference to the front element, or None if the sequence is empty
18 fn front<'a>(&'a self) -> Option<&'a T>;
19
20 /// Provide a mutable reference to the front element, or None if the sequence is empty
21 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
22
23 /// Provide a reference to the back element, or None if the sequence is empty
24 fn back<'a>(&'a self) -> Option<&'a T>;
25
26 /// Provide a mutable reference to the back element, or None if the sequence is empty
27 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
28
29 /// Insert an element first in the sequence
30 fn push_front(&mut self, elt: T);
31
32 /// Insert an element last in the sequence
33 fn push_back(&mut self, elt: T);
34
35 /// Remove the last element and return it, or None if the sequence is empty
36 fn pop_back(&mut self) -> Option<T>;
37
38 /// Remove the first element and return it, or None if the sequence is empty
39 fn pop_front(&mut self) -> Option<T>;
40 }
41
42 #[cfg(test)]
43 pub mod bench {
44 extern crate test;
45 use self::test::Bencher;
46 use std::container::MutableMap;
47 use rand;
48 use rand::Rng;
49
50 pub fn insert_rand_n<M:MutableMap<uint,uint>>(n: uint,
51 map: &mut M,
52 b: &mut Bencher) {
53 // setup
54 let mut rng = rand::weak_rng();
55
56 map.clear();
57 for _ in range(0, n) {
58 map.insert(rng.gen::<uint>() % n, 1);
59 }
60
61 // measure
62 b.iter(|| {
63 let k = rng.gen::<uint>() % n;
64 map.insert(k, 1);
65 map.remove(&k);
66 })
67 }
68
69 pub fn insert_seq_n<M:MutableMap<uint,uint>>(n: uint,
70 map: &mut M,
71 b: &mut Bencher) {
72 // setup
73 map.clear();
74 for i in range(0u, n) {
75 map.insert(i*2, 1);
76 }
77
78 // measure
79 let mut i = 1;
80 b.iter(|| {
81 map.insert(i, 1);
82 map.remove(&i);
83 i = (i + 2) % n;
84 })
85 }
86
87 pub fn find_rand_n<M:MutableMap<uint,uint>>(n: uint,
88 map: &mut M,
89 b: &mut Bencher) {
90 // setup
91 let mut rng = rand::weak_rng();
92 let mut keys = Vec::from_fn(n, |_| rng.gen::<uint>() % n);
93
94 for k in keys.iter() {
95 map.insert(*k, 1);
96 }
97
98 rng.shuffle(keys.as_mut_slice());
99
100 // measure
101 let mut i = 0;
102 b.iter(|| {
103 map.find(keys.get(i));
104 i = (i + 1) % n;
105 })
106 }
107
108 pub fn find_seq_n<M:MutableMap<uint,uint>>(n: uint,
109 map: &mut M,
110 b: &mut Bencher) {
111 // setup
112 for i in range(0u, n) {
113 map.insert(i, 1);
114 }
115
116 // measure
117 let mut i = 0;
118 b.iter(|| {
119 let x = map.find(&i);
120 i = (i + 1) % n;
121 x
122 })
123 }
124 }