7 releases
Uses old Rust 2015
0.4.6 | Oct 11, 2019 |
---|---|
0.4.5 | Sep 7, 2018 |
0.4.2 | Aug 27, 2018 |
0.3.0 | Jun 12, 2018 |
#13 in #multimap
211 downloads per month
Used in 9 crates
(2 directly)
66KB
1.5K
SLoC
total-order-multi-map
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 toV::Target
ifV: 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
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
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 ofNone
- requires
DerefMut
instead of justDeref
- has mutable access methods like
get_mut
- split
insert
intoadd
andset
whereset
replaces any value associated with the key prev. with the new value returning the old value
- flatten return value to
v0.4.2
:- mut iter to non mut iter conversions
- Iter from IterMut
- Values from ValuesMut
- EntryValues from EntryValuesMut
- mut iter to non mut iter conversions
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 firstsize
elements
- Added
v0.4.5
:- For entries added
values
,values_mut
methods to iterate over the values associated with the key used to create the entry.
- For entries added
Dependencies
~26KB