1 // Copyright 2013-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.
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.
15 #![crate_id = "collections#0.11.0"]
17 #![crate_type = "rlib"]
18 #![license = "MIT/ASL2"]
19 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
20 html_favicon_url = "http://www.rust-lang.org/favicon.ico",
21 html_root_url = "http://doc.rust-lang.org/0.11.0/",
22 html_playground_url = "http://play.rust-lang.org/")]
24 #![feature(macro_rules, managed_boxes, default_type_params, phase, globs)]
25 #![feature(unsafe_destructor)]
28 #[phase(plugin, link)] extern crate core;
31 #[cfg(test)] extern crate native;
32 #[cfg(test)] extern crate test;
33 #[cfg(test)] extern crate debug;
35 #[cfg(test)] #[phase(plugin, link)] extern crate std;
36 #[cfg(test)] #[phase(plugin, link)] extern crate log;
40 pub use core::collections::Collection;
41 pub use bitv::{Bitv, BitvSet};
44 pub use enum_set::EnumSet;
45 pub use priority_queue::PriorityQueue;
46 pub use ringbuf::RingBuf;
47 pub use smallintmap::SmallIntMap;
48 pub use string::String;
49 pub use treemap::{TreeMap, TreeSet};
50 pub use trie::{TrieMap, TrieSet};
59 pub mod priority_queue;
70 // Internal unicode fiddly bits for the str module
75 /// A trait to represent mutable containers
76 pub trait Mutable: Collection {
77 /// Clear the container, removing all values.
81 /// A map is a key-value store where values may be looked up by their keys. This
82 /// trait provides basic operations to operate on these stores.
83 pub trait Map<K, V>: Collection {
84 /// Return a reference to the value corresponding to the key
85 fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
87 /// Return true if the map contains a value for the specified key
89 fn contains_key(&self, key: &K) -> bool {
90 self.find(key).is_some()
94 /// This trait provides basic operations to modify the contents of a map.
95 pub trait MutableMap<K, V>: Map<K, V> + Mutable {
96 /// Insert a key-value pair into the map. An existing value for a
97 /// key is replaced by the new value. Return true if the key did
98 /// not already exist in the map.
100 fn insert(&mut self, key: K, value: V) -> bool {
101 self.swap(key, value).is_none()
104 /// Remove a key-value pair from the map. Return true if the key
105 /// was present in the map, otherwise false.
107 fn remove(&mut self, key: &K) -> bool {
108 self.pop(key).is_some()
111 /// Insert a key-value pair from the map. If the key already had a value
112 /// present in the map, that value is returned. Otherwise None is returned.
113 fn swap(&mut self, k: K, v: V) -> Option<V>;
115 /// Removes a key from the map, returning the value at the key if the key
116 /// was previously in the map.
117 fn pop(&mut self, k: &K) -> Option<V>;
119 /// Return a mutable reference to the value corresponding to the key
120 fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
123 /// A set is a group of objects which are each distinct from one another. This
124 /// trait represents actions which can be performed on sets to iterate over
126 pub trait Set<T>: Collection {
127 /// Return true if the set contains a value
128 fn contains(&self, value: &T) -> bool;
130 /// Return true if the set has no elements in common with `other`.
131 /// This is equivalent to checking for an empty intersection.
132 fn is_disjoint(&self, other: &Self) -> bool;
134 /// Return true if the set is a subset of another
135 fn is_subset(&self, other: &Self) -> bool;
137 /// Return true if the set is a superset of another
138 fn is_superset(&self, other: &Self) -> bool {
139 other.is_subset(self)
142 // FIXME #8154: Add difference, sym. difference, intersection and union iterators
145 /// This trait represents actions which can be performed on sets to mutate
147 pub trait MutableSet<T>: Set<T> + Mutable {
148 /// Add a value to the set. Return true if the value was not already
149 /// present in the set.
150 fn insert(&mut self, value: T) -> bool;
152 /// Remove a value from the set. Return true if the value was
153 /// present in the set.
154 fn remove(&mut self, value: &T) -> bool;
157 /// A double-ended sequence that allows querying, insertion and deletion at both
159 pub trait Deque<T> : Mutable {
160 /// Provide a reference to the front element, or None if the sequence is
162 fn front<'a>(&'a self) -> Option<&'a T>;
164 /// Provide a mutable reference to the front element, or None if the
165 /// sequence is empty
166 fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
168 /// Provide a reference to the back element, or None if the sequence is
170 fn back<'a>(&'a self) -> Option<&'a T>;
172 /// Provide a mutable reference to the back element, or None if the sequence
174 fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
176 /// Insert an element first in the sequence
177 fn push_front(&mut self, elt: T);
179 /// Insert an element last in the sequence
180 fn push_back(&mut self, elt: T);
182 /// Remove the last element and return it, or None if the sequence is empty
183 fn pop_back(&mut self) -> Option<T>;
185 /// Remove the first element and return it, or None if the sequence is empty
186 fn pop_front(&mut self) -> Option<T>;
189 // FIXME(#14344) this shouldn't be necessary
191 pub fn fixme_14344_be_sure_to_link_to_collections() {}
195 pub use core::fmt; // necessary for fail!()
196 pub use core::option; // necessary for fail!()
197 pub use core::clone; // deriving(Clone)
198 pub use core::cmp; // deriving(Eq, Ord, etc.)
199 pub use hash; // deriving(Hash)