Struct immutable_chunkmap::rc::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, 

fn new() -> Self

Create a new empty map

fn insert_sorted(&self, elts: &[(&K, &V)]) -> Self

This method of insertion can be orders of magnitude faster than inserting elements one by one. Assuming you are inserting a large number of elements relative to the size of the map (1/10 +). Assuming your elements are already sorted, or nearly sorted.

A word of warning however. If you're inserting small chunks (< 1/10) relative to the size of the map, or your chunks are not sorted, this method will still work, but it may be significantly slower than adding each element one by one.

Regardless of whether the input is sorted or not, and regardless of it's size relative to the size of the map, this method runs in log(N) time where N is the size of the map.

Examples

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

let v = vec![(1, 3), (10, 1), (-12, 2), (44, 0), (50, -1)];
let mut refs: Vec<(&i64, &i64)> = v.iter().map(|&(ref k, ref v)| (k, v)).collect();
refs.sort_unstable_by_key(|&(k, _)| k);

let m = Map::new().insert_sorted(&refs);

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

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.

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.

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

fn length(&self) -> usize

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

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, __arg_0: &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, __arg_0: &Map<K, V>) -> bool

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

fn ne(&self, __arg_0: &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, __arg_0: &Map<K, V>) -> Option<Ordering>

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

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

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

fn le(&self, __arg_0: &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, __arg_0: &Map<K, V>) -> bool

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

fn ge(&self, __arg_0: &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, __arg_0: &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 + 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, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.