#map #vec #ordered #multimap

total-order-multi-map

A multimap with at the same time keeps the total insertion ordering of all elements

7 releases

0.4.6 Oct 11, 2019
0.4.5 Sep 7, 2018
0.4.2 Aug 27, 2018
0.3.0 Jun 12, 2018

#53 in #vec

Download history 14/week @ 2019-08-01 16/week @ 2019-08-08 11/week @ 2019-08-15 21/week @ 2019-08-22 20/week @ 2019-08-29 27/week @ 2019-09-05 12/week @ 2019-09-12 64/week @ 2019-09-19 10/week @ 2019-09-26 6/week @ 2019-10-03 26/week @ 2019-10-10 22/week @ 2019-10-17 59/week @ 2019-10-24 19/week @ 2019-10-31 4/week @ 2019-11-07

75 downloads per month
Used in 6 crates (1 directly)

MIT/Apache

65KB
1.5K SLoC

total-order-multi-map Crates.io total-order-multi-map License License

A multi-map with at the same time keeps the total insertion ordering of all elements, this means if you insert following key-value pairs: (K1, V1), (K2, V2), (K1, V3) It will remember that the insertion oder was exact this (V1, V2, V3) i.e. it won't collapse the insertion order on a per-key basis.

At the same time it should have similar performance for accessing entries as a normal HashMap (else we could have just created a Vec).

It does so by limiting its values to such which implement StableDeref, e.g. Box<TraitObject> through which it can have more than one reference pointer to a value. While it uses unsafety internally the provided interface is safe. It also makes sure to be unwind + resume safe.

Example

extern crate total_order_multi_map as tomm;

use std::fmt::{self, Display};
use tomm::TotalOrderMultiMap;

/// for now the key has to be copy
type Key = &'static str;

/// the map is made for thinks which dereference
/// e.g. trait objects, through e.g. `String` or
/// `Rc<Debug>` would be fine, too.
type Value = Box<Display>;


fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1").expect("key1 is in the map");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert!(map.get("key1").is_none());

    println!("DONE (I only contain asserts)")
}

//---- some function to create dummy values for the example ----

fn mk_box_str(inp: &str) -> Box<Display> {
    // sadly we can't cast Box<str> to Box<Display>
    // (you would need non static vtables for this...)
    Box::new(inp.to_owned())
}

#[derive(Debug)]
struct MyThingy { val: String }

impl Display for MyThingy {
    fn fmt(&self, fter: &mut fmt::Formatter) -> fmt::Result {
        write!(fter, "{}", self.val)
    }
}

fn mk_my_thingy(inp: &str) -> Box<Display> {
    Box::new(MyThingy { val: inp.to_owned() })
}

Missing Parts

Following thinks can be implemented and should be added to further versions:

  • benchmarks
  • use SmallVec for the multi map
  • allow &mut access to V::Target if V: StableDeref + DerefMut
  • indexed access
    • indexed get off key-value pairs
    • indexed remove
    • indexed get in the return value of get, i.e. a multi map group
  • improved entry api
    • allow access to other values for same key
    • potentially turn the result of entry + insert into the result of get + unwrap
  • improved grouped iteration, maybe??
    • the current implementation groups by key but doesn't indicate when it switches to the next value
  • allow non-copy keys??
    • we still don't want to duplicate/clone keys so we would have to do some trickery there

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Change Log

  • v0.3:
    • TotalOrderMultiMap.retain now accepts a predicate accepting &V::Target instead of &V
  • v0.4.1:
    • flatten return value to get to return empty iterators instead of None
    • requires DerefMut instead of just Deref
    • has mutable access methods like get_mut
    • split insert into add and set where set replaces any value associated with the key prev. with the new value returning the old value
  • v0.4.2:
    • mut iter to non mut iter conversions
      • Iter from IterMut
      • Values from ValuesMut
      • EntryValues from EntryValuesMut
  • v0.4.3:
    • Added missing re-exports. Values, Values, GroupedValuesMut are now public as they should have been from the beginning.
  • v0.4.4:
    • Added truncate method allowing the removal of any think inserted after the first size elements
  • v0.4.5:
    • For entries added values,values_mut methods to iterate over the values associated with the key used to create the entry.

Dependencies

~25KB