pub use self::Entry::*;
use self::TrieNode::*;
use std::cmp::Ordering;
use std::fmt::{self, Debug};
use std::hash::{Hash, Hasher};
use std::iter;
use std::mem;
use std::ops;
use std::ptr;
use std::slice;
#[cfg(target_pointer_width = "32")]
pub const USIZE_BITS: usize = 32;
#[cfg(target_pointer_width = "64")]
pub const USIZE_BITS: usize = 64;
const SHIFT: usize = 4;
const SIZE: usize = 1 << SHIFT;
const MASK: usize = SIZE - 1;
const MAX_DEPTH: usize = USIZE_BITS / SHIFT;
#[derive(Clone)]
pub struct Map<T> {
root: InternalNode<T>,
length: usize
}
struct InternalNode<T> {
count: usize,
children: [TrieNode<T>; SIZE]
}
#[derive(Clone)]
enum TrieNode<T> {
Internal(Box<InternalNode<T>>),
External(usize, T),
Nothing
}
impl<T: PartialEq> PartialEq for Map<T> {
fn eq(&self, other: &Map<T>) -> bool {
self.len() == other.len() &&
self.iter().zip(other.iter()).all(|(a, b)| a == b)
}
}
impl<T: Eq> Eq for Map<T> {}
impl<T: PartialOrd> PartialOrd for Map<T> {
#[inline]
fn partial_cmp(&self, other: &Map<T>) -> Option<Ordering> {
self.iter().partial_cmp(other.iter())
}
}
impl<T: Ord> Ord for Map<T> {
#[inline]
fn cmp(&self, other: &Map<T>) -> Ordering {
self.iter().cmp(other.iter())
}
}
impl<T: Debug> Debug for Map<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<T> Default for Map<T> {
#[inline]
fn default() -> Map<T> { Map::new() }
}
impl<T> Map<T> {
#[inline]
pub fn new() -> Map<T> {
Map{root: InternalNode::new(), length: 0}
}
#[inline]
pub fn each_reverse<'a, F>(&'a self, mut f: F) -> bool
where F: FnMut(&usize, &'a T) -> bool {
self.root.each_reverse(&mut f)
}
pub fn keys(&self) -> Keys<T> { Keys(self.iter()) }
pub fn values(&self) -> Values<T> { Values(self.iter()) }
pub fn iter(&self) -> Iter<T> {
let mut iter = unsafe {Iter::new()};
iter.stack[0] = self.root.children.iter();
iter.length = 1;
iter.remaining = self.length;
iter
}
pub fn iter_mut(&mut self) -> IterMut<T> {
let mut iter = unsafe {IterMut::new()};
iter.stack[0] = self.root.children.iter_mut();
iter.length = 1;
iter.remaining = self.length;
iter
}
#[inline]
pub fn len(&self) -> usize { self.length }
#[inline]
pub fn is_empty(&self) -> bool { self.len() == 0 }
#[inline]
pub fn clear(&mut self) {
self.root = InternalNode::new();
self.length = 0;
}
#[inline]
pub fn get(&self, key: &usize) -> Option<&T> {
let mut node = &self.root;
let mut idx = 0;
loop {
match node.children[chunk(*key, idx)] {
Internal(ref x) => node = &**x,
External(stored, ref value) => {
if stored == *key {
return Some(value)
} else {
return None
}
}
Nothing => return None
}
idx += 1;
}
}
#[inline]
pub fn contains_key(&self, key: &usize) -> bool {
self.get(key).is_some()
}
#[inline]
pub fn get_mut(&mut self, key: &usize) -> Option<&mut T> {
find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
}
pub fn insert(&mut self, key: usize, value: T) -> Option<T> {
let (_, old_val) = insert(&mut self.root.count,
&mut self.root.children[chunk(key, 0)],
key, value, 1);
if old_val.is_none() { self.length += 1 }
old_val
}
pub fn remove(&mut self, key: &usize) -> Option<T> {
let ret = remove(&mut self.root.count,
&mut self.root.children[chunk(*key, 0)],
*key, 1);
if ret.is_some() { self.length -= 1 }
ret
}
}
macro_rules! addr { ($e:expr) => { $e } }
macro_rules! bound {
($iterator_name:ident,
self = $this:expr,
key = $key:expr,
is_upper = $upper:expr,
iter = $iter:ident,
mutability = $($mut_:tt)*) => {
{
let this = $this;
let mut node = unsafe {
mem::transmute::<_, usize>(&this.root) as *mut InternalNode<T>
};
let key = $key;
let mut it = unsafe {$iterator_name::new()};
it.remaining = this.length;
addr!(loop {
let children = unsafe {addr!(& $($mut_)* (*node).children)};
let child_id = chunk(key, it.length);
let (slice_idx, ret) = match children[child_id] {
Internal(ref $($mut_)* n) => {
node = unsafe {
mem::transmute::<_, usize>(&**n)
as *mut InternalNode<T>
};
(child_id + 1, false)
}
External(stored, _) => {
(if stored < key || ($upper && stored == key) {
child_id + 1
} else {
child_id
}, true)
}
Nothing => {
(child_id + 1, true)
}
};
it.stack[it.length] = children[slice_idx..].$iter();
it.length += 1;
if ret { break }
});
it
}
}
}
impl<T> Map<T> {
#[inline]
fn bound(&self, key: usize, upper: bool) -> Range<T> {
Range(bound!(Iter, self = self,
key = key, is_upper = upper,
iter = iter,
mutability = ))
}
pub fn lower_bound(&self, key: usize) -> Range<T> {
self.bound(key, false)
}
pub fn upper_bound(&self, key: usize) -> Range<T> {
self.bound(key, true)
}
#[inline]
fn bound_mut(&mut self, key: usize, upper: bool) -> RangeMut<T> {
RangeMut(bound!(IterMut, self = self,
key = key, is_upper = upper,
iter = iter_mut,
mutability = mut))
}
pub fn lower_bound_mut(&mut self, key: usize) -> RangeMut<T> {
self.bound_mut(key, false)
}
pub fn upper_bound_mut(&mut self, key: usize) -> RangeMut<T> {
self.bound_mut(key, true)
}
}
impl<T> iter::FromIterator<(usize, T)> for Map<T> {
fn from_iter<I: IntoIterator<Item=(usize, T)>>(iter: I) -> Map<T> {
let mut map = Map::new();
map.extend(iter);
map
}
}
impl<T> Extend<(usize, T)> for Map<T> {
fn extend<I: IntoIterator<Item=(usize, T)>>(&mut self, iter: I) {
for (k, v) in iter {
self.insert(k, v);
}
}
}
impl<T: Hash> Hash for Map<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
for elt in self.iter() {
elt.hash(state);
}
}
}
impl<'a, T> ops::Index<&'a usize> for Map<T> {
type Output = T;
#[inline]
fn index(&self, i: &'a usize) -> &T {
self.get(i).expect("key not present")
}
}
impl<'a, T> ops::IndexMut<&'a usize> for Map<T> {
#[inline]
fn index_mut(&mut self, i: &'a usize) -> &mut T {
self.get_mut(i).expect("key not present")
}
}
impl<T:Clone> Clone for InternalNode<T> {
#[inline]
fn clone(&self) -> InternalNode<T> {
let ch = &self.children;
InternalNode {
count: self.count,
children: [ch[0].clone(), ch[1].clone(), ch[2].clone(), ch[3].clone(),
ch[4].clone(), ch[5].clone(), ch[6].clone(), ch[7].clone(),
ch[8].clone(), ch[9].clone(), ch[10].clone(), ch[11].clone(),
ch[12].clone(), ch[13].clone(), ch[14].clone(), ch[15].clone()]}
}
}
impl<T> InternalNode<T> {
#[inline]
fn new() -> InternalNode<T> {
InternalNode{count: 0,
children: [Nothing, Nothing, Nothing, Nothing,
Nothing, Nothing, Nothing, Nothing,
Nothing, Nothing, Nothing, Nothing,
Nothing, Nothing, Nothing, Nothing]}
}
}
impl<T> InternalNode<T> {
fn each_reverse<'a, F>(&'a self, f: &mut F) -> bool
where F: FnMut(&usize, &'a T) -> bool {
for elt in self.children.iter().rev() {
match *elt {
Internal(ref x) => if !x.each_reverse(f) { return false },
External(k, ref v) => if !f(&k, v) { return false },
Nothing => ()
}
}
true
}
}
#[inline]
fn chunk(n: usize, idx: usize) -> usize {
let sh = USIZE_BITS - (SHIFT * (idx + 1));
(n >> sh) & MASK
}
fn find_mut<T>(child: &mut TrieNode<T>, key: usize, idx: usize) -> Option<&mut T> {
match *child {
External(stored, ref mut value) if stored == key => Some(value),
External(..) => None,
Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
Nothing => None
}
}
fn insert<'a, T>(count: &mut usize, start_node: &'a mut TrieNode<T>, key: usize, value: T, idx: usize)
-> (&'a mut T, Option<T>) {
let mut hack = false;
match *start_node {
Nothing => {
*count += 1;
*start_node = External(key, value);
match *start_node {
External(_, ref mut value_ref) => return (value_ref, None),
_ => unreachable!()
}
}
Internal(ref mut x) => {
let x = &mut **x;
return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
}
External(stored_key, _) if stored_key == key => {
hack = true;
}
_ => {}
}
if !hack {
match mem::replace(start_node, Internal(Box::new(InternalNode::new()))) {
External(stored_key, stored_value) => {
match *start_node {
Internal(ref mut new_node) => {
let new_node = &mut **new_node;
insert(&mut new_node.count,
&mut new_node.children[chunk(stored_key, idx)],
stored_key, stored_value, idx + 1);
return insert(&mut new_node.count,
&mut new_node.children[chunk(key, idx)],
key, value, idx + 1);
}
_ => unreachable!()
}
}
_ => unreachable!(),
}
}
if let External(_, ref mut stored_value) = *start_node {
let old_value = mem::replace(stored_value, value);
return (stored_value, Some(old_value));
}
unreachable!();
}
fn remove<T>(count: &mut usize, child: &mut TrieNode<T>, key: usize,
idx: usize) -> Option<T> {
let (ret, this) = match *child {
External(stored, _) if stored == key => {
match mem::replace(child, Nothing) {
External(_, value) => (Some(value), true),
_ => unreachable!()
}
}
External(..) => (None, false),
Internal(ref mut x) => {
let x = &mut **x;
let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
key, idx + 1);
(ret, x.count == 0)
}
Nothing => (None, false)
};
if this {
*child = Nothing;
*count -= 1;
}
return ret;
}
pub enum Entry<'a, T: 'a> {
Occupied(OccupiedEntry<'a, T>),
Vacant(VacantEntry<'a, T>)
}
impl<'a, T> Entry<'a, T> {
pub fn or_insert(self, default: T) -> &'a mut T {
match self {
Occupied(entry) => entry.into_mut(),
Vacant(entry) => entry.insert(default),
}
}
pub fn or_insert_with<F: FnOnce() -> T>(self, default: F) -> &'a mut T {
match self {
Occupied(entry) => entry.into_mut(),
Vacant(entry) => entry.insert(default()),
}
}
}
pub struct OccupiedEntry<'a, T: 'a> {
search_stack: SearchStack<'a, T>
}
pub struct VacantEntry<'a, T: 'a> {
search_stack: SearchStack<'a, T>
}
struct SearchStack<'a, T: 'a> {
map: &'a mut Map<T>,
length: usize,
key: usize,
items: [*mut TrieNode<T>; MAX_DEPTH]
}
impl<'a, T> SearchStack<'a, T> {
fn new(map: &'a mut Map<T>, key: usize) -> SearchStack<'a, T> {
SearchStack {
map: map,
length: 0,
key: key,
items: [ptr::null_mut(); MAX_DEPTH]
}
}
fn push(&mut self, node: *mut TrieNode<T>) {
self.length += 1;
self.items[self.length - 1] = node;
}
fn peek(&self) -> *mut TrieNode<T> {
self.items[self.length - 1]
}
fn peek_ref(&self) -> &'a mut TrieNode<T> {
let item = self.items[self.length - 1];
unsafe { &mut *item }
}
fn pop_ref(&mut self) -> &'a mut TrieNode<T> {
self.length -= 1;
unsafe {
&mut *self.items[self.length]
}
}
fn is_empty(&self) -> bool {
self.length == 0
}
fn get_ref(&self, idx: usize) -> &'a mut TrieNode<T> {
assert!(idx < self.length);
unsafe {
&mut *self.items[idx]
}
}
}
impl<T> Map<T> {
#[inline]
pub fn entry(&mut self, key: usize) -> Entry<T> {
let mut search_stack = SearchStack::new(self, key);
let first_node = &mut search_stack.map.root.children[chunk(key, 0)] as *mut _;
search_stack.push(first_node);
let search_successful: bool;
loop {
match unsafe { next_child(search_stack.peek(), key, search_stack.length) } {
(Some(child), _) => search_stack.push(child),
(None, success) => {
search_successful = success;
break;
}
}
}
if search_successful {
Occupied(OccupiedEntry { search_stack: search_stack })
} else {
Vacant(VacantEntry { search_stack: search_stack })
}
}
}
#[inline]
unsafe fn next_child<T>(node: *mut TrieNode<T>, key: usize, idx: usize)
-> (Option<*mut TrieNode<T>>, bool) {
match *node {
Internal(ref mut node_internal) => {
(Some(&mut node_internal.children[chunk(key, idx)] as *mut _), false)
},
External(stored_key, _) if stored_key == key => (None, true),
External(..) | Nothing => (None, false)
}
}
impl<'a, T> OccupiedEntry<'a, T> {
#[inline]
pub fn get(&self) -> &T {
match *self.search_stack.peek_ref() {
External(_, ref value) => value,
_ => unreachable!()
}
}
#[inline]
pub fn get_mut(&mut self) -> &mut T {
match *self.search_stack.peek_ref() {
External(_, ref mut value) => value,
_ => unreachable!()
}
}
#[inline]
pub fn into_mut(self) -> &'a mut T {
match *self.search_stack.peek_ref() {
External(_, ref mut value) => value,
_ => unreachable!()
}
}
#[inline]
pub fn insert(&mut self, value: T) -> T {
match *self.search_stack.peek_ref() {
External(_, ref mut stored_value) => {
mem::replace(stored_value, value)
}
_ => unreachable!()
}
}
#[inline]
pub fn remove(self) -> T {
let mut search_stack = self.search_stack;
let leaf_node = mem::replace(search_stack.pop_ref(), Nothing);
let value = match leaf_node {
External(_, value) => value,
_ => unreachable!()
};
while !search_stack.is_empty() {
let ancestor = search_stack.pop_ref();
match *ancestor {
Internal(ref mut internal) => {
if internal.count != 1 {
internal.count -= 1;
break;
}
}
_ => unreachable!()
}
*ancestor = Nothing;
}
search_stack.map.length -= 1;
value
}
}
impl<'a, T> VacantEntry<'a, T> {
pub fn insert(self, value: T) -> &'a mut T {
let search_stack = self.search_stack;
let old_length = search_stack.length;
let key = search_stack.key;
search_stack.map.length += 1;
if old_length == 1 {
let mut temp = search_stack.map.root.count;
let (value_ref, _) = insert(&mut temp, search_stack.get_ref(0), key, value, 1);
search_stack.map.root.count = temp;
value_ref
}
else {
match *search_stack.get_ref(old_length - 2) {
Internal(ref mut parent) => {
let parent = &mut **parent;
let (value_ref, _) = insert(&mut parent.count,
&mut parent.children[chunk(key, old_length - 1)],
key, value, old_length);
value_ref
}
_ => unreachable!()
}
}
}
}
pub struct Iter<'a, T:'a> {
stack: [slice::Iter<'a, TrieNode<T>>; MAX_DEPTH],
length: usize,
remaining: usize,
}
impl<'a, T> Clone for Iter<'a, T> {
#[cfg(target_pointer_width="32")]
fn clone(&self) -> Iter<'a, T> {
Iter {
stack: [self.stack[0].clone(), self.stack[1].clone(),
self.stack[2].clone(), self.stack[3].clone(),
self.stack[4].clone(), self.stack[5].clone(),
self.stack[6].clone(), self.stack[7].clone()], ..*self }
}
#[cfg(target_pointer_width="64")]
fn clone(&self) -> Iter<'a, T> {
Iter {
stack: [self.stack[0].clone(), self.stack[1].clone(),
self.stack[2].clone(), self.stack[3].clone(),
self.stack[4].clone(), self.stack[5].clone(),
self.stack[6].clone(), self.stack[7].clone(),
self.stack[8].clone(), self.stack[9].clone(),
self.stack[10].clone(), self.stack[11].clone(),
self.stack[12].clone(), self.stack[13].clone(),
self.stack[14].clone(), self.stack[15].clone()], ..*self }
}
}
pub struct IterMut<'a, T:'a> {
stack: [slice::IterMut<'a, TrieNode<T>>; MAX_DEPTH],
length: usize,
remaining: usize,
}
pub struct Keys<'a, T: 'a>(Iter<'a, T>);
impl<'a, T> Clone for Keys<'a, T> {
fn clone(&self) -> Keys<'a, T> { Keys(self.0.clone()) }
}
impl<'a, T> Iterator for Keys<'a, T> {
type Item = usize;
fn next(&mut self) -> Option<usize> { self.0.next().map(|e| e.0) }
fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
}
impl<'a, T> ExactSizeIterator for Keys<'a, T> {}
pub struct Values<'a, T: 'a>(Iter<'a, T>);
impl<'a, T> Clone for Values<'a, T> {
fn clone(&self) -> Values<'a, T> { Values(self.0.clone()) }
}
impl<'a, T> Iterator for Values<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> { self.0.next().map(|e| e.1) }
fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
}
impl<'a, T> ExactSizeIterator for Values<'a, T> {}
macro_rules! item { ($i:item) => {$i}}
macro_rules! iterator_impl {
($name:ident,
iter = $iter:ident,
mutability = $($mut_:tt)*) => {
impl<'a, T> $name<'a, T> {
#[cfg(target_pointer_width="32")]
unsafe fn new() -> $name<'a, T> {
$name {
remaining: 0,
length: 0,
stack: [IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
]
}
}
#[cfg(target_pointer_width="64")]
unsafe fn new() -> $name<'a, T> {
$name {
remaining: 0,
length: 0,
stack: [IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
IntoIterator::into_iter((& $($mut_)*[])),
]
}
}
}
item!(impl<'a, T> Iterator for $name<'a, T> {
type Item = (usize, &'a $($mut_)* T);
fn next(&mut self) -> Option<(usize, &'a $($mut_)* T)> {
let start_ptr = self.stack.as_mut_ptr();
unsafe {
let mut write_ptr = start_ptr.offset(self.length as isize);
while write_ptr != start_ptr {
match (*write_ptr.offset(-1)).next() {
None => write_ptr = write_ptr.offset(-1),
Some(child) => {
addr!(match *child {
Internal(ref $($mut_)* node) => {
*write_ptr = node.children.$iter();
write_ptr = write_ptr.offset(1);
}
External(key, ref $($mut_)* value) => {
self.remaining -= 1;
self.length = (write_ptr as usize
- start_ptr as usize) /
mem::size_of_val(&*write_ptr);
return Some((key, value));
}
Nothing => {}
})
}
}
}
}
return None;
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
});
impl<'a, T> ExactSizeIterator for $name<'a, T> {
fn len(&self) -> usize { self.remaining }
}
}
}
iterator_impl! { Iter, iter = iter, mutability = }
iterator_impl! { IterMut, iter = iter_mut, mutability = mut }
pub struct Range<'a, T: 'a>(Iter<'a, T>);
impl<'a, T> Clone for Range<'a, T> {
fn clone(&self) -> Range<'a, T> { Range(self.0.clone()) }
}
impl<'a, T> Iterator for Range<'a, T> {
type Item = (usize, &'a T);
fn next(&mut self) -> Option<(usize, &'a T)> { self.0.next() }
fn size_hint(&self) -> (usize, Option<usize>) { (0, Some(self.0.remaining)) }
}
pub struct RangeMut<'a, T: 'a>(IterMut<'a, T>);
impl<'a, T> Iterator for RangeMut<'a, T> {
type Item = (usize, &'a mut T);
fn next(&mut self) -> Option<(usize, &'a mut T)> { self.0.next() }
fn size_hint(&self) -> (usize, Option<usize>) { (0, Some(self.0.remaining)) }
}
impl<'a, T> IntoIterator for &'a Map<T> {
type Item = (usize, &'a T);
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> { self.iter() }
}
impl<'a, T> IntoIterator for &'a mut Map<T> {
type Item = (usize, &'a mut T);
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> { self.iter_mut() }
}
#[cfg(test)]
mod test {
use std::usize;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
use super::{Map, InternalNode};
use super::Entry::*;
use super::TrieNode::*;
fn check_integrity<T>(trie: &InternalNode<T>) {
assert!(trie.count != 0);
let mut sum = 0;
for x in trie.children.iter() {
match *x {
Nothing => (),
Internal(ref y) => {
check_integrity(&**y);
sum += 1
}
External(_, _) => { sum += 1 }
}
}
assert_eq!(sum, trie.count);
}
#[test]
fn test_find_mut() {
let mut m = Map::new();
assert!(m.insert(1, 12).is_none());
assert!(m.insert(2, 8).is_none());
assert!(m.insert(5, 14).is_none());
let new = 100;
match m.get_mut(&5) {
None => panic!(), Some(x) => *x = new
}
assert_eq!(m.get(&5), Some(&new));
}
#[test]
fn test_find_mut_missing() {
let mut m = Map::new();
assert!(m.get_mut(&0).is_none());
assert!(m.insert(1, 12).is_none());
assert!(m.get_mut(&0).is_none());
assert!(m.insert(2, 8).is_none());
assert!(m.get_mut(&0).is_none());
}
#[test]
fn test_step() {
let mut trie = Map::new();
let n = 300;
for x in (1..n).step_by(2) {
assert!(trie.insert(x, x + 1).is_none());
assert!(trie.contains_key(&x));
check_integrity(&trie.root);
}
for x in (0..n).step_by(2) {
assert!(!trie.contains_key(&x));
assert!(trie.insert(x, x + 1).is_none());
check_integrity(&trie.root);
}
for x in 0..n {
assert!(trie.contains_key(&x));
assert!(!trie.insert(x, x + 1).is_none());
check_integrity(&trie.root);
}
for x in (1..n).step_by(2) {
assert!(trie.remove(&x).is_some());
assert!(!trie.contains_key(&x));
check_integrity(&trie.root);
}
for x in (0..n).step_by(2) {
assert!(trie.contains_key(&x));
assert!(!trie.insert(x, x + 1).is_none());
check_integrity(&trie.root);
}
}
#[test]
fn test_each_reverse() {
let mut m = Map::new();
assert!(m.insert(3, 6).is_none());
assert!(m.insert(0, 0).is_none());
assert!(m.insert(4, 8).is_none());
assert!(m.insert(2, 4).is_none());
assert!(m.insert(1, 2).is_none());
let mut n = 5;
let mut vec: Vec<&i32> = vec![];
m.each_reverse(|k, v| {
n -= 1;
assert_eq!(*k, n);
vec.push(v);
true
});
assert_eq!(vec, [&8, &6, &4, &2, &0]);
}
#[test]
fn test_each_reverse_break() {
let mut m = Map::new();
for x in (usize::MAX - 10000..usize::MAX).rev() {
m.insert(x, x / 2);
}
let mut n = usize::MAX - 1;
m.each_reverse(|k, v| {
if n == usize::MAX - 5000 { false } else {
assert!(n > usize::MAX - 5000);
assert_eq!(*k, n);
assert_eq!(*v, n / 2);
n -= 1;
true
}
});
}
#[test]
fn test_insert() {
let mut m = Map::new();
assert_eq!(m.insert(1, 2), None);
assert_eq!(m.insert(1, 3), Some(2));
assert_eq!(m.insert(1, 4), Some(3));
}
#[test]
fn test_remove() {
let mut m = Map::new();
m.insert(1, 2);
assert_eq!(m.remove(&1), Some(2));
assert_eq!(m.remove(&1), None);
}
#[test]
fn test_from_iter() {
let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
let map: Map<i32> = xs.iter().cloned().collect();
for &(k, v) in xs.iter() {
assert_eq!(map.get(&k), Some(&v));
}
}
#[test]
fn test_keys() {
let vec = [(1, 'a'), (2, 'b'), (3, 'c')];
let map: Map<_> = vec.iter().cloned().collect();
let keys: Vec<_> = map.keys().collect();
assert_eq!(keys.len(), 3);
assert!(keys.contains(&1));
assert!(keys.contains(&2));
assert!(keys.contains(&3));
}
#[test]
fn test_values() {
let vec = [(1, 'a'), (2, 'b'), (3, 'c')];
let map: Map<_> = vec.iter().cloned().collect();
let values: Vec<_> = map.values().cloned().collect();
assert_eq!(values.len(), 3);
assert!(values.contains(&'a'));
assert!(values.contains(&'b'));
assert!(values.contains(&'c'));
}
#[test]
fn test_iteration() {
let empty_map : Map<usize> = Map::new();
assert_eq!(empty_map.iter().next(), None);
let first = usize::MAX - 10000;
let last = usize::MAX;
let mut map = Map::new();
for x in (first..last).rev() {
map.insert(x, x / 2);
}
let mut i = 0;
for (k, &v) in map.iter() {
assert_eq!(k, first + i);
assert_eq!(v, k / 2);
i += 1;
}
assert_eq!(i, last - first);
}
#[test]
fn test_mut_iter() {
let mut empty_map : Map<usize> = Map::new();
assert!(empty_map.iter_mut().next().is_none());
let first = usize::MAX - 10000;
let last = usize::MAX;
let mut map = Map::new();
for x in (first..last).rev() {
map.insert(x, x / 2);
}
let mut i = 0;
for (k, v) in map.iter_mut() {
assert_eq!(k, first + i);
*v -= k / 2;
i += 1;
}
assert_eq!(i, last - first);
assert!(map.iter().all(|(_, &v)| v == 0));
}
#[test]
fn test_bound() {
let empty_map : Map<usize> = Map::new();
assert_eq!(empty_map.lower_bound(0).next(), None);
assert_eq!(empty_map.upper_bound(0).next(), None);
let last = 999;
let step = 3;
let value = 42;
let mut map : Map<usize> = Map::new();
for x in (0..last).step_by(step) {
assert!(x % step == 0);
map.insert(x, value);
}
for i in 0..last - step {
let mut lb = map.lower_bound(i);
let mut ub = map.upper_bound(i);
let next_key = i - i % step + step;
let next_pair = (next_key, &value);
if i % step == 0 {
assert_eq!(lb.next(), Some((i, &value)));
} else {
assert_eq!(lb.next(), Some(next_pair));
}
assert_eq!(ub.next(), Some(next_pair));
}
let mut lb = map.lower_bound(last - step);
assert_eq!(lb.next(), Some((last - step, &value)));
let mut ub = map.upper_bound(last - step);
assert_eq!(ub.next(), None);
for i in last - step + 1..last {
let mut lb = map.lower_bound(i);
assert_eq!(lb.next(), None);
let mut ub = map.upper_bound(i);
assert_eq!(ub.next(), None);
}
}
#[test]
fn test_mut_bound() {
let empty_map : Map<usize> = Map::new();
assert_eq!(empty_map.lower_bound(0).next(), None);
assert_eq!(empty_map.upper_bound(0).next(), None);
let mut m_lower = Map::new();
let mut m_upper = Map::new();
for i in 0..100 {
m_lower.insert(2 * i, 4 * i);
m_upper.insert(2 * i, 4 * i);
}
for i in 0..199 {
let mut lb_it = m_lower.lower_bound_mut(i);
let (k, v) = lb_it.next().unwrap();
let lb = i + i % 2;
assert_eq!(lb, k);
*v -= k;
}
for i in 0..198 {
let mut ub_it = m_upper.upper_bound_mut(i);
let (k, v) = ub_it.next().unwrap();
let ub = i + 2 - i % 2;
assert_eq!(ub, k);
*v -= k;
}
assert!(m_lower.lower_bound_mut(199).next().is_none());
assert!(m_upper.upper_bound_mut(198).next().is_none());
assert!(m_lower.iter().all(|(_, &x)| x == 0));
assert!(m_upper.iter().all(|(_, &x)| x == 0));
}
#[test]
fn test_clone() {
let mut a = Map::new();
a.insert(1, 'a');
a.insert(2, 'b');
a.insert(3, 'c');
assert!(a.clone() == a);
}
#[test]
fn test_eq() {
let mut a = Map::new();
let mut b = Map::new();
assert!(a == b);
assert!(a.insert(0, 5).is_none());
assert!(a != b);
assert!(b.insert(0, 4).is_none());
assert!(a != b);
assert!(a.insert(5, 19).is_none());
assert!(a != b);
assert!(!b.insert(0, 5).is_none());
assert!(a != b);
assert!(b.insert(5, 19).is_none());
assert!(a == b);
}
#[test]
fn test_lt() {
let mut a = Map::new();
let mut b = Map::new();
assert!(!(a < b) && !(b < a));
assert!(b.insert(2, 5).is_none());
assert!(a < b);
assert!(a.insert(2, 7).is_none());
assert!(!(a < b) && b < a);
assert!(b.insert(1, 0).is_none());
assert!(b < a);
assert!(a.insert(0, 6).is_none());
assert!(a < b);
assert!(a.insert(6, 2).is_none());
assert!(a < b && !(b < a));
}
#[test]
fn test_ord() {
let mut a = Map::new();
let mut b = Map::new();
assert!(a <= b && a >= b);
assert!(a.insert(1, 1).is_none());
assert!(a > b && a >= b);
assert!(b < a && b <= a);
assert!(b.insert(2, 2).is_none());
assert!(b > a && b >= a);
assert!(a < b && a <= b);
}
#[test]
fn test_hash() {
fn hash<T: Hash>(t: &T) -> u64 {
let mut s = DefaultHasher::new();
t.hash(&mut s);
s.finish()
}
let mut x = Map::new();
let mut y = Map::new();
assert!(hash(&x) == hash(&y));
x.insert(1, 'a');
x.insert(2, 'b');
x.insert(3, 'c');
y.insert(3, 'c');
y.insert(2, 'b');
y.insert(1, 'a');
assert!(hash(&x) == hash(&y));
}
#[test]
fn test_debug() {
let mut map = Map::new();
let empty: Map<char> = Map::new();
map.insert(1, 'a');
map.insert(2, 'b');
assert_eq!(format!("{:?}", map), "{1: 'a', 2: 'b'}");
assert_eq!(format!("{:?}", empty), "{}");
}
#[test]
fn test_index() {
let mut map = Map::new();
map.insert(1, 2);
map.insert(2, 1);
map.insert(3, 4);
assert_eq!(map[&2], 1);
}
#[test]
#[should_panic]
fn test_index_nonexistent() {
let mut map = Map::new();
map.insert(1, 2);
map.insert(2, 1);
map.insert(3, 4);
map[&4];
}
const SQUARES_UPPER_LIM: usize = 128;
fn squares_map() -> Map<usize> {
let mut map = Map::new();
for i in 0..SQUARES_UPPER_LIM {
map.insert(i, i * i);
}
map
}
#[test]
fn test_entry_get() {
let mut map = squares_map();
for i in 0..SQUARES_UPPER_LIM {
match map.entry(i) {
Occupied(slot) => assert_eq!(slot.get(), &(i * i)),
Vacant(_) => panic!("Key not found.")
}
}
check_integrity(&map.root);
}
#[test]
fn test_entry_get_mut() {
let mut map = squares_map();
for i in 0..SQUARES_UPPER_LIM {
match map.entry(i) {
Occupied(mut e) => {
*e.get_mut() = i * i * i;
}
Vacant(_) => panic!("Key not found.")
}
assert_eq!(map.get(&i).unwrap(), &(i * i * i));
}
check_integrity(&map.root);
}
#[test]
fn test_entry_into_mut() {
let mut map = Map::new();
map.insert(3, 6);
let value_ref = match map.entry(3) {
Occupied(e) => e.into_mut(),
Vacant(_) => panic!("Entry not found.")
};
assert_eq!(*value_ref, 6);
}
#[test]
fn test_entry_take() {
let mut map = squares_map();
assert_eq!(map.len(), SQUARES_UPPER_LIM);
for i in (1..SQUARES_UPPER_LIM).step_by(2) {
match map.entry(i) {
Occupied(e) => assert_eq!(e.remove(), i * i),
Vacant(_) => panic!("Key not found.")
}
}
check_integrity(&map.root);
for i in (0..SQUARES_UPPER_LIM).step_by(2) {
assert_eq!(map.get(&i).unwrap(), &(i * i));
}
assert_eq!(map.len(), SQUARES_UPPER_LIM / 2);
}
#[test]
fn test_occupied_entry_set() {
let mut map = squares_map();
for i in 0..SQUARES_UPPER_LIM {
match map.entry(i) {
Occupied(mut e) => assert_eq!(e.insert(i * i * i), i * i),
Vacant(_) => panic!("Key not found.")
}
assert_eq!(map.get(&i).unwrap(), &(i * i * i));
}
check_integrity(&map.root);
}
#[test]
fn test_vacant_entry_set() {
let mut map = Map::new();
for i in 0..SQUARES_UPPER_LIM {
match map.entry(i) {
Vacant(e) => {
let inserted_val = e.insert(i * i);
assert_eq!(*inserted_val, i * i);
*inserted_val = i * i * i;
},
_ => panic!("Non-existent key found.")
}
assert_eq!(map.get(&i).unwrap(), &(i * i * i));
}
check_integrity(&map.root);
assert_eq!(map.len(), SQUARES_UPPER_LIM);
}
#[test]
fn test_single_key() {
let mut map = Map::new();
map.insert(1, 2);
match map.entry(1) {
Occupied(e) => { e.remove(); },
_ => ()
}
}
}
#[cfg(test)]
mod bench {
use rand::{weak_rng, Rng};
use test::{Bencher, black_box};
use super::{Map, Occupied, Vacant};
const MAP_SIZE: usize = 1000;
map_insert_rand_bench!{insert_rand_100, 100, Map}
map_insert_rand_bench!{insert_rand_10_000, 10_000, Map}
map_insert_seq_bench!{insert_seq_100, 100, Map}
map_insert_seq_bench!{insert_seq_10_000, 10_000, Map}
map_find_rand_bench!{find_rand_100, 100, Map}
map_find_rand_bench!{find_rand_10_000, 10_000, Map}
map_find_seq_bench!{find_seq_100, 100, Map}
map_find_seq_bench!{find_seq_10_000, 10_000, Map}
fn random_map(size: usize) -> Map<usize> {
let mut map = Map::<usize>::new();
let mut rng = weak_rng();
for _ in 0..size {
map.insert(rng.gen(), rng.gen());
}
map
}
fn bench_iter(b: &mut Bencher, size: usize) {
let map = random_map(size);
b.iter(|| {
for entry in map.iter() {
black_box(entry);
}
});
}
#[bench]
pub fn iter_20(b: &mut Bencher) {
bench_iter(b, 20);
}
#[bench]
pub fn iter_1000(b: &mut Bencher) {
bench_iter(b, 1000);
}
#[bench]
pub fn iter_100000(b: &mut Bencher) {
bench_iter(b, 100000);
}
#[bench]
fn bench_lower_bound(b: &mut Bencher) {
let mut m = Map::<usize>::new();
let mut rng = weak_rng();
for _ in 0..MAP_SIZE {
m.insert(rng.gen(), rng.gen());
}
b.iter(|| {
for _ in 0..10 {
m.lower_bound(rng.gen());
}
});
}
#[bench]
fn bench_upper_bound(b: &mut Bencher) {
let mut m = Map::<usize>::new();
let mut rng = weak_rng();
for _ in 0..MAP_SIZE {
m.insert(rng.gen(), rng.gen());
}
b.iter(|| {
for _ in 0..10 {
m.upper_bound(rng.gen());
}
});
}
#[bench]
fn bench_insert_large(b: &mut Bencher) {
let mut m = Map::<[usize; 10]>::new();
let mut rng = weak_rng();
b.iter(|| {
for _ in 0..MAP_SIZE {
m.insert(rng.gen(), [1; 10]);
}
});
}
#[bench]
fn bench_insert_large_entry(b: &mut Bencher) {
let mut m = Map::<[usize; 10]>::new();
let mut rng = weak_rng();
b.iter(|| {
for _ in 0..MAP_SIZE {
match m.entry(rng.gen()) {
Occupied(mut e) => { e.insert([1; 10]); },
Vacant(e) => { e.insert([1; 10]); }
}
}
});
}
#[bench]
fn bench_insert_large_low_bits(b: &mut Bencher) {
let mut m = Map::<[usize; 10]>::new();
let mut rng = weak_rng();
b.iter(|| {
for _ in 0..MAP_SIZE {
m.insert(rng.gen::<usize>() & 0xff_ff, [1; 10]);
}
});
}
#[bench]
fn bench_insert_small(b: &mut Bencher) {
let mut m = Map::<()>::new();
let mut rng = weak_rng();
b.iter(|| {
for _ in 0..MAP_SIZE {
m.insert(rng.gen(), ());
}
});
}
#[bench]
fn bench_insert_small_low_bits(b: &mut Bencher) {
let mut m = Map::<()>::new();
let mut rng = weak_rng();
b.iter(|| {
for _ in 0..MAP_SIZE {
m.insert(rng.gen::<usize>() & 0xff_ff, ());
}
});
}
#[bench]
fn bench_get(b: &mut Bencher) {
let map = random_map(MAP_SIZE);
let keys: Vec<usize> = map.keys().collect();
b.iter(|| {
for key in keys.iter() {
black_box(map.get(key));
}
});
}
#[bench]
fn bench_get_entry(b: &mut Bencher) {
let mut map = random_map(MAP_SIZE);
let keys: Vec<usize> = map.keys().collect();
b.iter(|| {
for key in keys.iter() {
match map.entry(*key) {
Occupied(e) => { black_box(e.get()); },
_ => ()
}
}
});
}
#[bench]
fn bench_remove(b: &mut Bencher) {
b.iter(|| {
let mut map = random_map(MAP_SIZE);
let keys: Vec<usize> = map.keys().collect();
for key in keys.iter() {
black_box(map.remove(key));
}
});
}
#[bench]
fn bench_remove_entry(b: &mut Bencher) {
b.iter(|| {
let mut map = random_map(MAP_SIZE);
let keys: Vec<usize> = map.keys().collect();
for key in keys.iter() {
match map.entry(*key) {
Occupied(e) => { black_box(e.remove()); },
_ => ()
}
}
});
}
}