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
|
// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
/*!
* Collection types.
*/
#![crate_id = "collections#0.11.0"]
#![experimental]
#![crate_type = "rlib"]
#![license = "MIT/ASL2"]
#![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
html_favicon_url = "http://www.rust-lang.org/favicon.ico",
html_root_url = "http://doc.rust-lang.org/0.11.0/",
html_playground_url = "http://play.rust-lang.org/")]
#![feature(macro_rules, managed_boxes, default_type_params, phase, globs)]
#![feature(unsafe_destructor)]
#![no_std]
#[phase(plugin, link)] extern crate core;
extern crate alloc;
#[cfg(test)] extern crate native;
#[cfg(test)] extern crate test;
#[cfg(test)] extern crate debug;
#[cfg(test)] #[phase(plugin, link)] extern crate std;
#[cfg(test)] #[phase(plugin, link)] extern crate log;
use core::prelude::*;
pub use core::collections::Collection;
pub use bitv::{Bitv, BitvSet};
pub use btree::BTree;
pub use dlist::DList;
pub use enum_set::EnumSet;
pub use priority_queue::PriorityQueue;
pub use ringbuf::RingBuf;
pub use smallintmap::SmallIntMap;
pub use string::String;
pub use treemap::{TreeMap, TreeSet};
pub use trie::{TrieMap, TrieSet};
pub use vec::Vec;
mod macros;
pub mod bitv;
pub mod btree;
pub mod dlist;
pub mod enum_set;
pub mod priority_queue;
pub mod ringbuf;
pub mod smallintmap;
pub mod treemap;
pub mod trie;
pub mod slice;
pub mod str;
pub mod string;
pub mod vec;
pub mod hash;
// Internal unicode fiddly bits for the str module
mod unicode;
mod deque;
/// A trait to represent mutable containers
pub trait Mutable: Collection {
/// Clear the container, removing all values.
fn clear(&mut self);
}
/// A map is a key-value store where values may be looked up by their keys. This
/// trait provides basic operations to operate on these stores.
pub trait Map<K, V>: Collection {
/// Return a reference to the value corresponding to the key
fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
/// Return true if the map contains a value for the specified key
#[inline]
fn contains_key(&self, key: &K) -> bool {
self.find(key).is_some()
}
}
/// This trait provides basic operations to modify the contents of a map.
pub trait MutableMap<K, V>: Map<K, V> + Mutable {
/// Insert a key-value pair into the map. An existing value for a
/// key is replaced by the new value. Return true if the key did
/// not already exist in the map.
#[inline]
fn insert(&mut self, key: K, value: V) -> bool {
self.swap(key, value).is_none()
}
/// Remove a key-value pair from the map. Return true if the key
/// was present in the map, otherwise false.
#[inline]
fn remove(&mut self, key: &K) -> bool {
self.pop(key).is_some()
}
/// Insert a key-value pair from the map. If the key already had a value
/// present in the map, that value is returned. Otherwise None is returned.
fn swap(&mut self, k: K, v: V) -> Option<V>;
/// Removes a key from the map, returning the value at the key if the key
/// was previously in the map.
fn pop(&mut self, k: &K) -> Option<V>;
/// Return a mutable reference to the value corresponding to the key
fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
}
/// A set is a group of objects which are each distinct from one another. This
/// trait represents actions which can be performed on sets to iterate over
/// them.
pub trait Set<T>: Collection {
/// Return true if the set contains a value
fn contains(&self, value: &T) -> bool;
/// Return true if the set has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
fn is_disjoint(&self, other: &Self) -> bool;
/// Return true if the set is a subset of another
fn is_subset(&self, other: &Self) -> bool;
/// Return true if the set is a superset of another
fn is_superset(&self, other: &Self) -> bool {
other.is_subset(self)
}
// FIXME #8154: Add difference, sym. difference, intersection and union iterators
}
/// This trait represents actions which can be performed on sets to mutate
/// them.
pub trait MutableSet<T>: Set<T> + Mutable {
/// Add a value to the set. Return true if the value was not already
/// present in the set.
fn insert(&mut self, value: T) -> bool;
/// Remove a value from the set. Return true if the value was
/// present in the set.
fn remove(&mut self, value: &T) -> bool;
}
/// A double-ended sequence that allows querying, insertion and deletion at both
/// ends.
pub trait Deque<T> : Mutable {
/// Provide a reference to the front element, or None if the sequence is
/// empty
fn front<'a>(&'a self) -> Option<&'a T>;
/// Provide a mutable reference to the front element, or None if the
/// sequence is empty
fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
/// Provide a reference to the back element, or None if the sequence is
/// empty
fn back<'a>(&'a self) -> Option<&'a T>;
/// Provide a mutable reference to the back element, or None if the sequence
/// is empty
fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
/// Insert an element first in the sequence
fn push_front(&mut self, elt: T);
/// Insert an element last in the sequence
fn push_back(&mut self, elt: T);
/// Remove the last element and return it, or None if the sequence is empty
fn pop_back(&mut self) -> Option<T>;
/// Remove the first element and return it, or None if the sequence is empty
fn pop_front(&mut self) -> Option<T>;
}
// FIXME(#14344) this shouldn't be necessary
#[doc(hidden)]
pub fn fixme_14344_be_sure_to_link_to_collections() {}
#[cfg(not(test))]
mod std {
pub use core::fmt; // necessary for fail!()
pub use core::option; // necessary for fail!()
pub use core::clone; // deriving(Clone)
pub use core::cmp; // deriving(Eq, Ord, etc.)
pub use hash; // deriving(Hash)
}
|
