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

```rust extern crate totalordermulti_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;

fn main() { let mut map = TotalOrderMultiMap::::new();

map.insert("key1", mk_box_str("val1"));
map.insert("key1", mk_my_thingy("val2"));
map.insert("key2", mk_box_str("val3"));
map.insert("key1", mk_my_thingy("val4"));
map.insert("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 mkboxstr(inp: &str) -> Box { // sadly we can't cast Box to Box // (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 mkmythingy(inp: &str) -> Box { Box::new(MyThingy { val: inp.to_owned() }) } ```

Missing Parts

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

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