1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
//! Collection traits for generic programming.
#![deny(missing_docs)]
#![feature(set_recovery)]
mod std_impls;
/// A collection.
pub trait Collection {
/// The type of the collection's items.
type Item;
/// Checks if the collection contains zero items.
///
/// This is equivalent to `self.len() == 0`, but may be optimized.
fn is_empty(&self) -> bool {
self.len() == 0
}
/// Returns the number of items in the collection.
fn len(&self) -> usize;
}
/// A collection that supports insertion.
pub trait Insert: Collection {
/// Moves all items from the given collection into the collection.
fn append(&mut self, other: &mut Self) where Self: Sized;
}
/// A collection that supports removal.
pub trait Remove: Collection {
/// Removes all items from the collection.
fn clear(&mut self);
}
#[test]
fn test_object_safety() {
let _: &Collection<Item = i32>;
let _: &Remove<Item = i32>;
let _: &Insert<Item = i32>;
}
pub mod map {
//! Maps.
/// A map.
///
/// A map is a collection that associates keys with values, where the keys are distinguished
/// according to some uniqueness criteria.
pub trait Map: super::Collection<Item = (<Self as Map>::Key, <Self as Map>::Value)> {
/// The type of the map's keys.
type Key;
/// The type of the map's values.
type Value;
}
/// A map that supports lookups using keys of type `&Q`.
pub trait Get<Q: ?Sized = <Self as Map>::Key>: Map {
/// Checks if the map contains a key that is equivalent to the given key.
///
/// This is equivalent to `self.get(key).is_some()`, but may be optimized.
fn contains_key(&self, key: &Q) -> bool {
self.get(key).is_some()
}
/// Returns a reference to the value in the map whose key is equivalent to the given key.
///
/// Returns `None` if the map contains no such key.
fn get(&self, key: &Q) -> Option<&Self::Value>;
/// Returns a mutable reference to the value in the map whose key is equivalent to the
/// given key.
///
/// Returns `None` if the map contains no such key.
fn get_mut(&mut self, key: &Q) -> Option<&mut Self::Value>;
}
/// A map that supports removals using keys of type `&Q`.
pub trait Remove<Q: ?Sized = <Self as Map>::Key>: Get<Q> + super::Remove {
/// Removes the key in the map that is equivalent to the given key and returns its value.
///
/// Returns `None` if the map contains no such key.
fn remove(&mut self, key: &Q) -> Option<Self::Value>;
}
/// A map that supports insertion.
pub trait Insert: Map + super::Insert {
/// Inserts the given key and value into the map and returns the previous value
/// corresponding to the given key, if any.
fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
}
/// A map that supports efficient in-place modification.
///
/// `'a` is the lifetime of the map.
pub trait EntryMap<'a>: Insert + Remove {
/// The type of the map's occupied entries.
type OccupiedEntry: OccupiedEntry<'a, Map = Self>;
/// The type of the map's vacant entries.
type VacantEntry: VacantEntry<'a, Map = Self>;
/// Returns the entry in the map corresponding to the given key.
fn entry(&'a mut self, key: Self::Key) -> Entry<Self>;
}
/// An occupied map entry.
///
/// `'a` is the lifetime of the map.
pub trait OccupiedEntry<'a>: Sized {
/// The entry's map type.
type Map: ?Sized + EntryMap<'a, OccupiedEntry = Self>;
/// Returns a reference to the entry's value.
fn get(&self) -> &<Self::Map as Map>::Value;
/// Returns a mutable reference to the entry's value.
fn get_mut(&mut self) -> &mut <Self::Map as Map>::Value;
/// Returns a mutable reference to the entry's value with the same lifetime as the map.
fn into_mut(self) -> &'a mut <Self::Map as Map>::Value;
/// Replaces the entry's value with the given one and returns the old value.
fn insert(&mut self, value: <Self::Map as Map>::Value) -> <Self::Map as Map>::Value {
::std::mem::replace(self.get_mut(), value)
}
/// Removes the entry from the map and returns its value.
fn remove(self) -> <Self::Map as Map>::Value;
}
/// A vacant map entry.
///
/// `'a` is the lifetime of the map.
pub trait VacantEntry<'a>: Sized {
/// The entry's map type.
type Map: ?Sized + EntryMap<'a, VacantEntry = Self>;
/// Inserts the entry into the map with the given value and returns a mutable reference to
/// it with the same lifetime as the map.
fn insert(self, value: <Self::Map as Map>::Value) -> &'a mut <Self::Map as Map>::Value;
}
/// A map entry.
#[derive(Debug)]
pub enum Entry<'a, M: ?Sized + EntryMap<'a>> {
/// An occupied map entry.
Occupied(M::OccupiedEntry),
/// A vacant map entry.
Vacant(M::VacantEntry),
}
impl<'a, M: ?Sized + EntryMap<'a>> Entry<'a, M> {
/// Ensures the entry is occupied by inserting it with the given default value if it is
/// vacant.
pub fn or_insert(self, default: M::Value) -> &'a mut M::Value {
match self {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(e) => e.insert(default),
}
}
/// Ensures the entry is occupied by inserting it with the result of the given function if
/// it is vacant.
pub fn or_insert_with<F: FnOnce() -> M::Value>(self, f: F) -> &'a mut M::Value {
match self {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(e) => e.insert(f()),
}
}
}
#[cfg(test)]
pub fn count<M, I>(items: I) -> M
where
M: Default + for<'a> EntryMap<'a, Value = usize>,
I: IntoIterator<Item = M::Key>,
{
let mut map = M::default();
for item in items { *map.entry(item).or_insert(0) += 1; }
map
}
#[test]
fn test_object_safety() {
let _: &Map<Item = (i32, char), Key = i32, Value = char>;
let _: &Get<i32, Item = (i32, char), Key = i32, Value = char>;
let _: &Remove<i32, Item = (i32, char), Key = i32, Value = char>;
let _: &Insert<Item = (i32, char), Key = i32, Value = char>;
}
}
pub mod seq {
//! Sequences.
/// A sequence that supports insertion.
pub trait PushBack: super::Insert {
/// Pushes the given item onto the back of the sequence.
fn push_back(&mut self, item: Self::Item);
}
/// A queue.
pub trait Queue: PushBack + super::Remove {
/// Returns a reference to the item at the front of the queue.
///
/// Returns `None` if the queue is empty.
fn front(&self) -> Option<&Self::Item>;
/// Returns a mutable reference to the item at the front of the queue.
///
/// Returns `None` if the queue is empty.
fn front_mut(&mut self) -> Option<&mut Self::Item>;
/// Removes and returns the item at the front of the queue.
///
/// Returns `None` if the queue is empty.
fn pop_front(&mut self) -> Option<Self::Item>;
}
/// A stack.
pub trait Stack: PushBack + super::Remove {
/// Returns a reference to the item at the back of the stack.
///
/// Returns `None` if the stack is empty.
fn back(&self) -> Option<&Self::Item>;
/// Returns a mutable reference to the item at the back of the stack.
///
/// Returns `None` if the stack is empty.
fn back_mut(&mut self) -> Option<&mut Self::Item>;
/// Removes and returns the item at the back of the stack.
///
/// Returns `None` if the stack is empty.
fn pop_back(&mut self) -> Option<Self::Item>;
}
/// A deque (double-ended queue).
pub trait Deque: Queue + Stack {
/// Pushes the given item onto the front of the deque.
fn push_front(&mut self, item: Self::Item);
}
#[test]
fn test_object_safety() {
let _: &PushBack<Item = i32>;
let _: &Queue<Item = i32>;
let _: &Stack<Item = i32>;
let _: &Deque<Item = i32>;
}
}
pub mod set {
//! Sets.
use super::Collection;
/// A set.
///
/// A set is a collection whose items are distinguished according to some uniqueness criteria.
pub trait Set: Collection {
/// Checks if the set is disjoint from the given set.
fn is_disjoint(&self, other: &Self) -> bool where Self: Sized;
/// Checks if the set is a subset of the given set.
fn is_subset(&self, other: &Self) -> bool where Self: Sized;
/// Checks if the set is a superset of the given set.
fn is_superset(&self, other: &Self) -> bool where Self: Sized {
other.is_subset(self)
}
}
/// A set that supports retrievals using items of type `&Q`.
pub trait Get<Q: ?Sized = <Self as Collection>::Item>: Set {
/// Checks if the set contains an item that is equivalent to the given item.
///
/// This is equivalent to `self.get(item).is_some()`, but may be optimized.
fn contains(&self, item: &Q) -> bool {
self.get(item).is_some()
}
/// Returns the item in the set that is equivalent to the given item.
///
/// Returns `None` if the set contains no such item.
fn get(&self, item: &Q) -> Option<&Self::Item>;
}
/// A set that supports removal using items of type `&Q`.
pub trait Remove<Q: ?Sized = <Self as Collection>::Item>: Get<Q> + super::Remove {
/// Removes the item in the set that is equivalent to the given item.
///
/// Returns `true` if the set contained such an item, `false` otherwise.
///
/// This is equivalent to `self.take(item).is_some()`, but may be optimized.
fn remove(&mut self, item: &Q) -> bool {
self.take(item).is_some()
}
/// Removes and returns the item in the set that is equivalent to the given item.
///
/// Returns `None` if the set contained no such item.
fn take(&mut self, item: &Q) -> Option<Self::Item>;
}
/// A set that supports insertion.
pub trait Insert: Set + super::Insert {
/// Inserts the given item into the set without replacement.
///
/// Returns `true` if the set contained an equivalent item, `false` otherwise.
fn insert(&mut self, item: Self::Item) -> bool;
/// Inserts the given item into the set with replacement.
///
/// Returns the equivalent item if the set contained one, `None` otherwise.
fn replace(&mut self, item: Self::Item) -> Option<Self::Item>;
}
#[test]
fn test_object_safety() {
let _: &Set<Item = i32>;
let _: &Get<i32, Item = i32>;
let _: &Remove<i32, Item = i32>;
let _: &Insert<Item = i32>;
}
}