src/libcollections/lib.rs

   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.
   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 /*!
  12  * Collection types.
  13  */
  14
  15 #![crate_name = "collections"]
  16 #![experimental]
  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/master/",
  22        html_playground_url = "http://play.rust-lang.org/")]
  23
  24 #![feature(macro_rules, managed_boxes, default_type_params, phase, globs)]
  25 #![feature(unsafe_destructor)]
  26 #![no_std]
  27
  28 #[phase(plugin, link)] extern crate core;
  29 extern crate unicode;
  30 extern crate alloc;
  31
  32 #[cfg(test)] extern crate native;
  33 #[cfg(test)] extern crate test;
  34 #[cfg(test)] extern crate debug;
  35
  36 #[cfg(test)] #[phase(plugin, link)] extern crate std;
  37 #[cfg(test)] #[phase(plugin, link)] extern crate log;
  38
  39 use core::prelude::*;
  40
  41 pub use core::collections::Collection;
  42 pub use bitv::{Bitv, BitvSet};
  43 pub use btree::BTree;
  44 pub use dlist::DList;
  45 pub use enum_set::EnumSet;
  46 pub use priority_queue::PriorityQueue;
  47 pub use ringbuf::RingBuf;
  48 pub use smallintmap::SmallIntMap;
  49 pub use string::String;
  50 pub use treemap::{TreeMap, TreeSet};
  51 pub use trie::{TrieMap, TrieSet};
  52 pub use vec::Vec;
  53
  54 mod macros;
  55
  56 pub mod bitv;
  57 pub mod btree;
  58 pub mod dlist;
  59 pub mod enum_set;
  60 pub mod priority_queue;
  61 pub mod ringbuf;
  62 pub mod smallintmap;
  63 pub mod treemap;
  64 pub mod trie;
  65 pub mod slice;
  66 pub mod str;
  67 pub mod string;
  68 pub mod vec;
  69 pub mod hash;
  70
  71 mod deque;
  72
  73 /// A trait to represent mutable containers
  74 pub trait Mutable: Collection {
  75     /// Clear the container, removing all values.
  76     ///
  77     /// # Example
  78     ///
  79     /// ```
  80     /// let mut v = vec![1i, 2, 3];
  81     /// v.clear();
  82     /// assert!(v.is_empty());
  83     /// ```
  84     fn clear(&mut self);
  85 }
  86
  87 /// A map is a key-value store where values may be looked up by their keys. This
  88 /// trait provides basic operations to operate on these stores.
  89 pub trait Map<K, V>: Collection {
  90     /// Return a reference to the value corresponding to the key.
  91     ///
  92     /// # Example
  93     ///
  94     /// ```
  95     /// use std::collections::HashMap;
  96     ///
  97     /// let mut map = HashMap::new();
  98     /// map.insert("a", 1i);
  99     /// assert_eq!(map.find(&"a"), Some(&1i));
 100     /// assert_eq!(map.find(&"b"), None);
 101     /// ```
 102     fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
 103
 104     /// Return true if the map contains a value for the specified key.
 105     ///
 106     /// # Example
 107     ///
 108     /// ```
 109     /// use std::collections::HashMap;
 110     ///
 111     /// let mut map = HashMap::new();
 112     /// map.insert("a", 1i);
 113     /// assert_eq!(map.contains_key(&"a"), true);
 114     /// assert_eq!(map.contains_key(&"b"), false);
 115     /// ```
 116     #[inline]
 117     fn contains_key(&self, key: &K) -> bool {
 118         self.find(key).is_some()
 119     }
 120 }
 121
 122 /// This trait provides basic operations to modify the contents of a map.
 123 pub trait MutableMap<K, V>: Map<K, V> + Mutable {
 124     /// Insert a key-value pair into the map. An existing value for a
 125     /// key is replaced by the new value. Return true if the key did
 126     /// not already exist in the map.
 127     ///
 128     /// # Example
 129     ///
 130     /// ```
 131     /// use std::collections::HashMap;
 132     ///
 133     /// let mut map = HashMap::new();
 134     /// assert_eq!(map.insert("key", 2i), true);
 135     /// assert_eq!(map.insert("key", 9i), false);
 136     /// assert_eq!(map.get(&"key"), &9i);
 137     /// ```
 138     #[inline]
 139     fn insert(&mut self, key: K, value: V) -> bool {
 140         self.swap(key, value).is_none()
 141     }
 142
 143     /// Remove a key-value pair from the map. Return true if the key
 144     /// was present in the map, otherwise false.
 145     ///
 146     /// # Example
 147     ///
 148     /// ```
 149     /// use std::collections::HashMap;
 150     ///
 151     /// let mut map = HashMap::new();
 152     /// assert_eq!(map.remove(&"key"), false);
 153     /// map.insert("key", 2i);
 154     /// assert_eq!(map.remove(&"key"), true);
 155     /// ```
 156     #[inline]
 157     fn remove(&mut self, key: &K) -> bool {
 158         self.pop(key).is_some()
 159     }
 160
 161     /// Insert a key-value pair from the map. If the key already had a value
 162     /// present in the map, that value is returned. Otherwise None is returned.
 163     ///
 164     /// # Example
 165     ///
 166     /// ```
 167     /// use std::collections::HashMap;
 168     ///
 169     /// let mut map = HashMap::new();
 170     /// assert_eq!(map.swap("a", 37i), None);
 171     /// assert_eq!(map.is_empty(), false);
 172     ///
 173     /// map.insert("a", 1i);
 174     /// assert_eq!(map.swap("a", 37i), Some(1i));
 175     /// assert_eq!(map.get(&"a"), &37i);
 176     /// ```
 177     fn swap(&mut self, k: K, v: V) -> Option<V>;
 178
 179     /// Removes a key from the map, returning the value at the key if the key
 180     /// was previously in the map.
 181     ///
 182     /// # Example
 183     ///
 184     /// ```
 185     /// use std::collections::HashMap;
 186     ///
 187     /// let mut map: HashMap<&str, int> = HashMap::new();
 188     /// map.insert("a", 1i);
 189     /// assert_eq!(map.pop(&"a"), Some(1i));
 190     /// assert_eq!(map.pop(&"a"), None);
 191     /// ```
 192     fn pop(&mut self, k: &K) -> Option<V>;
 193
 194     /// Return a mutable reference to the value corresponding to the key.
 195     ///
 196     /// # Example
 197     ///
 198     /// ```
 199     /// use std::collections::HashMap;
 200     ///
 201     /// let mut map = HashMap::new();
 202     /// map.insert("a", 1i);
 203     /// match map.find_mut(&"a") {
 204     ///     Some(x) => *x = 7i,
 205     ///     None => (),
 206     /// }
 207     /// assert_eq!(map.get(&"a"), &7i);
 208     /// ```
 209     fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
 210 }
 211
 212 /// A set is a group of objects which are each distinct from one another. This
 213 /// trait represents actions which can be performed on sets to iterate over
 214 /// them.
 215 pub trait Set<T>: Collection {
 216     /// Return true if the set contains a value.
 217     ///
 218     /// # Example
 219     ///
 220     /// ```
 221     /// use std::collections::HashSet;
 222     ///
 223     /// let set: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 224     /// assert_eq!(set.contains(&1), true);
 225     /// assert_eq!(set.contains(&4), false);
 226     /// ```
 227     fn contains(&self, value: &T) -> bool;
 228
 229     /// Return true if the set has no elements in common with `other`.
 230     /// This is equivalent to checking for an empty intersection.
 231     ///
 232     /// # Example
 233     ///
 234     /// ```
 235     /// use std::collections::HashSet;
 236     ///
 237     /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 238     /// let mut b: HashSet<int> = HashSet::new();
 239     ///
 240     /// assert_eq!(a.is_disjoint(&b), true);
 241     /// b.insert(4);
 242     /// assert_eq!(a.is_disjoint(&b), true);
 243     /// b.insert(1);
 244     /// assert_eq!(a.is_disjoint(&b), false);
 245     /// ```
 246     fn is_disjoint(&self, other: &Self) -> bool;
 247
 248     /// Return true if the set is a subset of another.
 249     ///
 250     /// # Example
 251     ///
 252     /// ```
 253     /// use std::collections::HashSet;
 254     ///
 255     /// let sup: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
 256     /// let mut set: HashSet<int> = HashSet::new();
 257     ///
 258     /// assert_eq!(set.is_subset(&sup), true);
 259     /// set.insert(2);
 260     /// assert_eq!(set.is_subset(&sup), true);
 261     /// set.insert(4);
 262     /// assert_eq!(set.is_subset(&sup), false);
 263     /// ```
 264     fn is_subset(&self, other: &Self) -> bool;
 265
 266     /// Return true if the set is a superset of another.
 267     ///
 268     /// # Example
 269     ///
 270     /// ```
 271     /// use std::collections::HashSet;
 272     ///
 273     /// let sub: HashSet<int> = [1i, 2].iter().map(|&x| x).collect();
 274     /// let mut set: HashSet<int> = HashSet::new();
 275     ///
 276     /// assert_eq!(set.is_superset(&sub), false);
 277     ///
 278     /// set.insert(0);
 279     /// set.insert(1);
 280     /// assert_eq!(set.is_superset(&sub), false);
 281     ///
 282     /// set.insert(2);
 283     /// assert_eq!(set.is_superset(&sub), true);
 284     /// ```
 285     fn is_superset(&self, other: &Self) -> bool {
 286         other.is_subset(self)
 287     }
 288
 289     // FIXME #8154: Add difference, sym. difference, intersection and union iterators
 290 }
 291
 292 /// This trait represents actions which can be performed on sets to mutate
 293 /// them.
 294 pub trait MutableSet<T>: Set<T> + Mutable {
 295     /// Add a value to the set. Return true if the value was not already
 296     /// present in the set.
 297     ///
 298     /// # Example
 299     ///
 300     /// ```
 301     /// use std::collections::HashSet;
 302     ///
 303     /// let mut set = HashSet::new();
 304     ///
 305     /// assert_eq!(set.insert(2i), true);
 306     /// assert_eq!(set.insert(2i), false);
 307     /// assert_eq!(set.len(), 1);
 308     /// ```
 309     fn insert(&mut self, value: T) -> bool;
 310
 311     /// Remove a value from the set. Return true if the value was
 312     /// present in the set.
 313     ///
 314     /// # Example
 315     ///
 316     /// ```
 317     /// use std::collections::HashSet;
 318     ///
 319     /// let mut set = HashSet::new();
 320     ///
 321     /// set.insert(2i);
 322     /// assert_eq!(set.remove(&2), true);
 323     /// assert_eq!(set.remove(&2), false);
 324     /// ```
 325     fn remove(&mut self, value: &T) -> bool;
 326 }
 327
 328 /// A double-ended sequence that allows querying, insertion and deletion at both
 329 /// ends.
 330 ///
 331 /// # Example
 332 ///
 333 /// With a `Deque` we can simulate a queue efficiently:
 334 ///
 335 /// ```
 336 /// use std::collections::{RingBuf, Deque};
 337 ///
 338 /// let mut queue = RingBuf::new();
 339 /// queue.push_back(1i);
 340 /// queue.push_back(2i);
 341 /// queue.push_back(3i);
 342 ///
 343 /// // Will print 1, 2, 3
 344 /// while !queue.is_empty() {
 345 ///     let x = queue.pop_front().unwrap();
 346 ///     println!("{}", x);
 347 /// }
 348 /// ```
 349 ///
 350 /// We can also simulate a stack:
 351 ///
 352 /// ```
 353 /// use std::collections::{RingBuf, Deque};
 354 ///
 355 /// let mut stack = RingBuf::new();
 356 /// stack.push_front(1i);
 357 /// stack.push_front(2i);
 358 /// stack.push_front(3i);
 359 ///
 360 /// // Will print 3, 2, 1
 361 /// while !stack.is_empty() {
 362 ///     let x = stack.pop_front().unwrap();
 363 ///     println!("{}", x);
 364 /// }
 365 /// ```
 366 ///
 367 /// And of course we can mix and match:
 368 ///
 369 /// ```
 370 /// use std::collections::{DList, Deque};
 371 ///
 372 /// let mut deque = DList::new();
 373 ///
 374 /// // Init deque with 1, 2, 3, 4
 375 /// deque.push_front(2i);
 376 /// deque.push_front(1i);
 377 /// deque.push_back(3i);
 378 /// deque.push_back(4i);
 379 ///
 380 /// // Will print (1, 4) and (2, 3)
 381 /// while !deque.is_empty() {
 382 ///     let f = deque.pop_front().unwrap();
 383 ///     let b = deque.pop_back().unwrap();
 384 ///     println!("{}", (f, b));
 385 /// }
 386 /// ```
 387 pub trait Deque<T> : Mutable {
 388     /// Provide a reference to the front element, or `None` if the sequence is
 389     /// empty.
 390     ///
 391     /// # Example
 392     ///
 393     /// ```
 394     /// use std::collections::{RingBuf, Deque};
 395     ///
 396     /// let mut d = RingBuf::new();
 397     /// assert_eq!(d.front(), None);
 398     ///
 399     /// d.push_back(1i);
 400     /// d.push_back(2i);
 401     /// assert_eq!(d.front(), Some(&1i));
 402     /// ```
 403     fn front<'a>(&'a self) -> Option<&'a T>;
 404
 405     /// Provide a mutable reference to the front element, or `None` if the
 406     /// sequence is empty.
 407     ///
 408     /// # Example
 409     ///
 410     /// ```
 411     /// use std::collections::{RingBuf, Deque};
 412     ///
 413     /// let mut d = RingBuf::new();
 414     /// assert_eq!(d.front_mut(), None);
 415     ///
 416     /// d.push_back(1i);
 417     /// d.push_back(2i);
 418     /// match d.front_mut() {
 419     ///     Some(x) => *x = 9i,
 420     ///     None => (),
 421     /// }
 422     /// assert_eq!(d.front(), Some(&9i));
 423     /// ```
 424     fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
 425
 426     /// Provide a reference to the back element, or `None` if the sequence is
 427     /// empty.
 428     ///
 429     /// # Example
 430     ///
 431     /// ```
 432     /// use std::collections::{DList, Deque};
 433     ///
 434     /// let mut d = DList::new();
 435     /// assert_eq!(d.back(), None);
 436     ///
 437     /// d.push_back(1i);
 438     /// d.push_back(2i);
 439     /// assert_eq!(d.back(), Some(&2i));
 440     /// ```
 441     fn back<'a>(&'a self) -> Option<&'a T>;
 442
 443     /// Provide a mutable reference to the back element, or `None` if the sequence
 444     /// is empty.
 445     ///
 446     /// # Example
 447     ///
 448     /// ```
 449     /// use std::collections::{DList, Deque};
 450     ///
 451     /// let mut d = DList::new();
 452     /// assert_eq!(d.back(), None);
 453     ///
 454     /// d.push_back(1i);
 455     /// d.push_back(2i);
 456     /// match d.back_mut() {
 457     ///     Some(x) => *x = 9i,
 458     ///     None => (),
 459     /// }
 460     /// assert_eq!(d.back(), Some(&9i));
 461     /// ```
 462     fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
 463
 464     /// Insert an element first in the sequence.
 465     ///
 466     /// # Example
 467     ///
 468     /// ```
 469     /// use std::collections::{DList, Deque};
 470     ///
 471     /// let mut d = DList::new();
 472     /// d.push_front(1i);
 473     /// d.push_front(2i);
 474     /// assert_eq!(d.front(), Some(&2i));
 475     /// ```
 476     fn push_front(&mut self, elt: T);
 477
 478     /// Insert an element last in the sequence.
 479     ///
 480     /// # Example
 481     ///
 482     /// ```
 483     /// use std::collections::{DList, Deque};
 484     ///
 485     /// let mut d = DList::new();
 486     /// d.push_back(1i);
 487     /// d.push_back(2i);
 488     /// assert_eq!(d.front(), Some(&1i));
 489     /// ```
 490     fn push_back(&mut self, elt: T);
 491
 492     /// Remove the last element and return it, or `None` if the sequence is empty.
 493     ///
 494     /// # Example
 495     ///
 496     /// ```
 497     /// use std::collections::{RingBuf, Deque};
 498     ///
 499     /// let mut d = RingBuf::new();
 500     /// d.push_back(1i);
 501     /// d.push_back(2i);
 502     ///
 503     /// assert_eq!(d.pop_back(), Some(2i));
 504     /// assert_eq!(d.pop_back(), Some(1i));
 505     /// assert_eq!(d.pop_back(), None);
 506     /// ```
 507     fn pop_back(&mut self) -> Option<T>;
 508
 509     /// Remove the first element and return it, or `None` if the sequence is empty.
 510     ///
 511     /// # Example
 512     ///
 513     /// ```
 514     /// use std::collections::{RingBuf, Deque};
 515     ///
 516     /// let mut d = RingBuf::new();
 517     /// d.push_back(1i);
 518     /// d.push_back(2i);
 519     ///
 520     /// assert_eq!(d.pop_front(), Some(1i));
 521     /// assert_eq!(d.pop_front(), Some(2i));
 522     /// assert_eq!(d.pop_front(), None);
 523     /// ```
 524     fn pop_front(&mut self) -> Option<T>;
 525 }
 526
 527 // FIXME(#14344) this shouldn't be necessary
 528 #[doc(hidden)]
 529 pub fn fixme_14344_be_sure_to_link_to_collections() {}
 530
 531 #[cfg(not(test))]
 532 mod std {
 533     pub use core::fmt;      // necessary for fail!()
 534     pub use core::option;   // necessary for fail!()
 535     pub use core::clone;    // deriving(Clone)
 536     pub use core::cmp;      // deriving(Eq, Ord, etc.)
 537     pub use hash;           // deriving(Hash)
 538 }