Struct immutable_chunkmap::arc::map::Map

pub struct Map<K: Ord + Clone + Debug, V: Clone + Debug> { /* fields omitted */ }

This Map uses a similar strategy to BTreeMap to ensure cache efficient performance on modern hardware while still providing log(N) get, insert, and remove operations.

Examples

use std::string::String;
use self::immutable_chunkmap::rc::map::Map;

let m =
   Map::new()
   .insert(&String::from("1"), &1)
   .insert(&String::from("2"), &2)
   .insert(&String::from("3"), &3);

assert_eq!(m.get("1"), Option::Some(&1));
assert_eq!(m.get("2"), Option::Some(&2));
assert_eq!(m.get("3"), Option::Some(&3));
assert_eq!(m.get("4"), Option::None);

for (k, v) in &m {
  println!("key {}, val: {}", k, v)
}

Methods

impl<K, V> Map<K, V> where     K: Ord + Clone + Debug,     V: Clone + Debug,

pub fn new() -> Self

Create a new empty map

pub fn insert_sorted<E: IntoIterator<Item = (K, V)>>(&self, elts: E) -> Self

This method inserts many elements at once, skipping the intermediate node allocations where possible, which in most cases provides a significant speedup. It is able to skip more allocations if the data is sorted, however it will still work with unsorted data.

#Examples

 use self::immutable_chunkmap::rc::map::Map;

 let mut v = vec![(1, 3), (10, 1), (-12, 2), (44, 0), (50, -1)];
 v.sort_unstable_by_key(|&(k, _)| k);

 let m = Map::new().insert_sorted(v.iter().map(|(k, v)| (*k, *v)));

 for (k, v) in &v {
   assert_eq!(m.get(k), Option::Some(v))
 }

pub fn insert(&self, k: &K, v: &V) -> Self

return a new map with (k, v) inserted into it. If k already exists in the old map, the new map will contain the new binding, not the old. This method runs in log(N) time, where N is the size of the map. k and v will be cloned on insert, and on subsuquent inserts or removals, if k or v is expensive to clone, pass an Rc or Arc pointer to it instead. A Box won't work, because it can't be shared, so clone will deep copy the contents.

pub fn get<'a, Q: ?Sized + Ord + Debug>(&'a self, k: &Q) -> Option<&'a V> where     K: Borrow<Q>,

lookup the mapping for k. If it doesn't exist return None. Runs in log(N) time where N is the size of the map.

pub fn remove<Q: Sized + Ord>(&self, k: &Q) -> Self where     K: Borrow<Q>,

return a new map with the mapping under k removed. Runs in log(N) time, where N is the size of the map

pub fn len(&self) -> usize

get the number of elements in the map O(1)

pub fn range<'a, Q>(     &'a self,     lbound: Bound<Q>,     ubound: Bound<Q> ) -> Iter<'a, Q, K, V> where     Q: Ord,     K: Borrow<Q>,

return an iterator over the subset of elements in the map that are within the specified range.

The returned iterator runs in O(log(N) + M) time, and constant space. N is the number of elements in the tree, and M is the number of elements you examine.

if lbound >= ubound the returned iterator will be empty

Trait Implementations

impl<K: Clone + Ord + Clone + Debug, V: Clone + Clone + Debug> Clone for Map<K, V>

fn clone(&self) -> Map<K, V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug + Ord + Clone + Debug, V: Debug + Clone + Debug> Debug for Map<K, V>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<K: PartialEq + Ord + Clone + Debug, V: PartialEq + Clone + Debug> PartialEq for Map<K, V>

fn eq(&self, other: &Map<K, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Map<K, V>) -> bool

This method tests for !=.

impl<K: Eq + Ord + Clone + Debug, V: Eq + Clone + Debug> Eq for Map<K, V>

impl<K: PartialOrd + Ord + Clone + Debug, V: PartialOrd + Clone + Debug> PartialOrd for Map<K, V>

fn partial_cmp(&self, other: &Map<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Map<K, V>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Map<K, V>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Map<K, V>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Map<K, V>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Ord + Ord + Clone + Debug, V: Ord + Clone + Debug> Ord for Map<K, V>

fn cmp(&self, other: &Map<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<'a, K, V> IntoIterator for &'a Map<K, V> where     K: 'a + Borrow<K> + Ord + Clone + Debug,     V: 'a + Clone + Debug,

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.