deepmesa::collections

Struct LinkedHashMap

Source 
pub struct LinkedHashMap<K, V>
where
    K: Hash + Eq,
{ /* private fields */ }
Expand description

A fast and flexible LinkedHashMap that combines a std::collections::HashMap and a LinkedList for O(1) inserts, lookups and deletes along with a predictable iteration order.

All the basic functions - get(), get_mut(), get_key_value(), put(), insert(), remove(), remove_entry() - provide constant time performance which is expected to be lower than that of the Hashmap given the added expense of of maintaining and updating the underlying linked list.

§Getting Started

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

assert_eq!(lhm.get(&1), Some(&"a"));
assert_eq!(lhm.get(&2), Some(&"b"));

if let Some(val) = lhm.get_mut(&1) {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));

§Iteration Order

This map holds a LinkedList of all the elements that defines the iteration order. The order is either InsertionOrder or AccessOrder. InsertionOrder is the order in which the keys were inserted into the map from least recently inserted (oldest) to most recently inserted (newest). ReInserting a key (via the insert or put methods) will change the insertion order to make the re-inserted key the most recently inserted (newest) in the order.

AccessOrder is the order in which the keys in the map were last accessed (via the get(), get_key_value(), get_mut() methods) from least-recently accessed (oldest) to most recently accessed (newest). Iterating over the map using one of the iterators - iter(), iter_mut(), keys(), values(), values_mut() - does not affect the order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. The iteration order of the map is always from oldest entry (accessed or inserted) to the newest entry (accessed or inserted).

The map offers iterators over the elements, keys and values with mutable iterators for elements and values. The iterators can also be reversed.

// Construct a map in InsertionOrder
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);


// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);

§Evicting Elements

The Map also supports construction with an evict_eldest function that can be provided to implement a policy for removing entries when new elements are added to the map. A LinkedHashMap with AccessOrder and an eviction function is well suited to building an LRU Cache.

use deepmesa::collections::map::Entry;
pub fn evict<K,V>(len: usize, capacity: usize, e: &Entry<K, V>) -> bool {
    if len > capacity {
        return true;
    }
    return false;
}

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(3, Order::AccessOrder, Some(evict));
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

assert_eq!(lhm.get(&2), Some(&"b"));
lhm.put(4, "d");
assert_eq!(lhm.get(&1), None);

Implementations§

Source§

impl<K, V> LinkedHashMap<K, V>
where K: Hash + Eq,

Source

pub fn new( capacity: usize, order: Order, evict_eldest: Option<fn(_: usize, _: usize, _: &Entry<K, V>) -> bool>, ) -> LinkedHashMap<K, V>

Creates an empty LinkedHashMap with the specified capacity and iteration order. The evict_eldest function can be supplied that is called everytime a new entry is inserted into the map with the current length, capacity and the last entry in the linkedlist (most recently inserted or accessed).

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;
let lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
Source

pub fn with_capacity(capacity: usize) -> LinkedHashMap<K, V>

Creates an empty LinkedHashMap with the specified capacity and InsertionOrder. The underlying list will continue to reallocate additional memory by doubling the capacity everytime the capacity is exceeded. However the list will not deallocate memory when keys are removed.

If the capacity is set to 0, and the underlying list is full, then new memory will be allocated for one new element everytime an element is added to the list.

The underlying hashmap will only allocate memory if the capacity is greater than zero.

§Examples
use deepmesa::collections::LinkedHashMap;
let lhm = LinkedHashMap::<u16, &str>::with_capacity(10);
assert_eq!(lhm.capacity(), 10);
assert_eq!(lhm.len(), 0);
Source

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold before new memory is allocated.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(10, lhm.capacity());
assert_eq!(0, lhm.len());
Source

pub fn len(&self) -> usize

Returns the number or elements in the map.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(lhm.len(), 0);
lhm.insert(1, "a");
assert_eq!(lhm.len(), 1);
Source

pub fn clear(&mut self)

Removes and drops all the key-value pairs this map. This has no effect on the allocated capacity of the map or the underlying list.

This method should complete in O(n) time.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.clear();
assert!(lhm.is_empty());
Source

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements and false otherwise. This method should complete in O(1) time.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert!(lhm.is_empty());
lhm.insert(1, "a");
assert!(!lhm.is_empty());
Source

pub fn contains_key(&self, key: &K) -> bool

Returns true if the map contains a value for the specified key. This method should complete in O(1) time.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.contains_key(&1), true);
assert_eq!(lhm.contains_key(&2), false);
Source

pub fn get(&mut self, key: &K) -> Option<&V>

Returns a reference to the value corresponding to the key. If the Map was created with AccessOrder then the key accessed is moved to the head of the underlying linked list (least recently used).

If the key is not present then this method returns None and the order is unaffected.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

assert_eq!(lhm.get(&1), Some(&"a"));
assert_eq!(lhm.get(&3), None);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);
Source

pub fn get_key_value(&mut self, key: &K) -> Option<(&K, &V)>

Returns the key-value pair corresponding to the supplied key. the Map was created with AccessOrder then the key accessed is moved to the head of the underlying linked list (most recently accessed).

If the key is not present then this method returns None and the order is unaffected.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

assert_eq!(lhm.get_key_value(&1), Some((&1, &"a")));
assert_eq!(lhm.get(&3), None);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);
Source

pub fn get_mut(&mut self, key: &K) -> Option<&mut V>

Returns a mutable reference to the value corresponding to the key. If the Map was created with AccessOrder then the key accessed is moved to the head of the underlying linked list (least recently used).

If the key is not present then this method returns None and the order is unaffected.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

if let Some(val) = lhm.get_mut(&1) {
    *val = "d";
}

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"d")));
assert_eq!(iter.next(), None);
Source

pub fn remove(&mut self, key: &K) -> Option<V>

Removes a key from the map, returning the value at the key if the key was previously in the map. If the key was not present then this method returns None. The iteration order is not affected by this method except to remove the specified key from the underlying linked list.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.remove(&1), Some("a"));
assert_eq!(lhm.remove(&1), None);
Source

pub fn remove_entry(&mut self, key: &K) -> Option<(K, V)>

Removes a key from the map, returning the key value pair at the key if the key was previously in the map. If the key was not present then this method returns None. The iteration order is not affected by this method except to remove the specified key from the underlying linked list.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.remove_entry(&1), Some((1, "a")));
assert_eq!(lhm.remove(&1), None);
Source

pub fn put(&mut self, k: K, v: V)

Inserts a key-value pair into the map. Unlike the insert method this does not return the old value previously stored. The new value inserted is placed at the head of the underlying linked list (least recently used).

#Examples

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
assert_eq!(lhm.is_empty(), false);
Source

pub fn insert(&mut self, k: K, v: V) -> Option<V>

Inserts a key-value pair into the map and returns the old value (if any). If a value was not present for this key then this method returns None. The new value inserted is placed at the head of the underlying linked list (least recently used).

The key is not updated and only the value corresponding to the key is updated.

#Examples

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(lhm.insert(1, "a"), None);
assert_eq!(lhm.is_empty(), false);

lhm.insert(2, "b");
assert_eq!(lhm.insert(2, "c"), Some("b"));
Source

pub fn iter(&self) -> Iter<'_, K, V>

An Iterator that vists all key value pairs in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is (&’a K, &’a V).

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
Source

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

An Iterator that vists all key value pairs in a predictable order with mutable references to the values.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed

The iterator element type is (&’a K, &’a mut V).

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

for (_, val) in lhm.iter_mut() {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));
assert_eq!(lhm.get(&2), Some(&"d"));
Source

pub fn keys(&self) -> Keys<'_, K, V>

An Iterator that vists all keys in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a K.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.keys();
assert_eq!(iter.next(), Some((&1)));
assert_eq!(iter.next(), Some((&2)));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.keys();
assert_eq!(iter.next(), Some((&2)));
assert_eq!(iter.next(), Some((&1)));
Source

pub fn values(&self) -> Values<'_, K, V>

An Iterator that vists all values in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a V.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.values();
assert_eq!(iter.next(), Some((&"a")));
assert_eq!(iter.next(), Some((&"b")));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.values();
assert_eq!(iter.next(), Some((&"b")));
assert_eq!(iter.next(), Some((&"a")));
Source

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

An Iterator that vists all values in a predictable order with mutable references to the values.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a mut V.

§Examples
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

for val in lhm.values_mut() {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));
assert_eq!(lhm.get(&2), Some(&"d"));

Trait Implementations§

Source§

impl<'a, K, V> IntoIterator for &'a LinkedHashMap<K, V>
where K: Hash + Eq,

Source§

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

The type of the elements being iterated over.
Source§

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

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> <&'a LinkedHashMap<K, V> as IntoIterator>::IntoIter

Creates an iterator from a value. Read more
Source§

impl<'a, K, V> IntoIterator for &'a mut LinkedHashMap<K, V>
where K: Hash + Eq,

Source§

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

The type of the elements being iterated over.
Source§

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

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> <&'a mut LinkedHashMap<K, V> as IntoIterator>::IntoIter

Creates an iterator from a value. Read more
Source§

impl<K, V> Send for LinkedHashMap<K, V>
where K: Hash + Eq,

Source§

impl<K, V> Sync for LinkedHashMap<K, V>
where K: Hash + Eq,

Auto Trait Implementations§

§

impl<K, V> Freeze for LinkedHashMap<K, V>

§

impl<K, V> RefUnwindSafe for LinkedHashMap<K, V>
where K: RefUnwindSafe, V: RefUnwindSafe,

§

impl<K, V> Unpin for LinkedHashMap<K, V>

§

impl<K, V> UnwindSafe for LinkedHashMap<K, V>
where K: RefUnwindSafe, V: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.