Expand description
A linked ord with cardinal indexing and O(log n) get/insert/remove anywhere in the List.
The API of List is designed to resemble std::collections::VecDeque but List does
not use a VecDeque; instead each node in the ord is assigned an ordinal value
in the range [0, usize::MAX >> 1), which is stored in a
HashMap of ordinals to values.
This design allows a cardinal index to be resolved to a value in O(log n) time.
List is optimized to handle a random insertion order. A Vec or VecDeque offers better
performance in situations where inserts are append-only or append- and prepend- only.
Example:
use ds_ext::List;
let mut list = List::new();
list.push_front("zero");
assert_eq!(list.len(), 1);
assert_eq!(list.pop_front(), Some("zero"));
assert_eq!(list.len(), 0);
assert!(list.get(0).is_none());
list.push_back("zero");
assert_eq!(list.len(), 1);
assert_eq!(*list.get(0).expect("0"), "zero");
assert_eq!(list.pop_back(), Some("zero"));
assert_eq!(list.len(), 0);
assert!(list.get(0).is_none());
list.push_front("zero");
list.push_back("three");
list.insert(1, "two point five");
list.insert(1, "one");
list.insert(2, "two");
assert_eq!(list.remove(3), Some("two point five"));
assert_eq!(list.len(), 4);
assert_eq!(list.iter().size_hint(), (4, Some(4)));
assert_eq!(list.range(1..3).size_hint(), (2, Some(2)));
assert_eq!(list.range(1..3).map(|s| *s).collect::<Vec<_>>(), ["one", "two"]);
assert_eq!(list.into_iter().collect::<Vec<_>>(), ["zero", "one", "two", "three"]);