#[cfg(not(feature = "btreemap"))]
use std::hash::Hash;
#[cfg(not(feature = "btreemap"))]
use std::collections::hash_map::{self, HashMap};
#[cfg(feature = "btreemap")]
use std::collections::{btree_map, BTreeMap};
use std::hash::BuildHasher;
use std::collections::hash_map::RandomState;
use std::iter::IntoIterator;
use std::default::Default;
use std::borrow::{Borrow, ToOwned};
use std::mem;
use std::marker::PhantomData;
#[cfg(feature = "serde")]
use serde::{Serialize, Deserialize};
#[cfg(feature = "serde")]
#[macro_use]
extern crate serde;
#[cfg(test)]
mod tests;
#[cfg(all(test, feature = "serde"))]
mod serde_tests;
#[derive(Debug, Clone)]
#[cfg(not(feature = "btreemap"))]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(bound(serialize = "K: Serialize, V: Serialize")))]
#[cfg_attr(feature = "serde",
serde(bound(deserialize = "K: Deserialize<'de>, V: Deserialize<'de>")))]
pub struct SequenceTrie<K, V, S = RandomState>
where K: TrieKey,
S: BuildHasher + Default,
{
value: Option<V>,
children: HashMap<K, SequenceTrie<K, V, S>, S>,
}
#[derive(Debug, Clone)]
#[cfg(feature = "btreemap")]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "serde", serde(bound(serialize = "K: Serialize, V: Serialize")))]
#[cfg_attr(feature = "serde",
serde(bound(deserialize = "K: Deserialize<'de>, V: Deserialize<'de>")))]
pub struct SequenceTrie<K, V, S = RandomState>
where K: TrieKey,
S: BuildHasher + Default,
{
value: Option<V>,
children: BTreeMap<K, SequenceTrie<K, V, S>>,
#[cfg_attr(feature = "serde", serde(skip))]
_phantom: PhantomData<S>,
}
#[cfg(not(feature = "btreemap"))]
pub trait TrieKey: Eq + Hash {}
#[cfg(not(feature = "btreemap"))]
impl<K> TrieKey for K where K: Eq + Hash + ?Sized {}
#[cfg(feature = "btreemap")]
pub trait TrieKey: Ord {}
#[cfg(feature = "btreemap")]
impl<K> TrieKey for K where K: Ord + ?Sized {}
#[cfg(not(feature = "btreemap"))]
impl<K, V> SequenceTrie<K, V>
where K: TrieKey,
{
pub fn new() -> SequenceTrie<K, V> {
SequenceTrie::with_hasher(RandomState::new())
}
}
#[cfg(not(feature = "btreemap"))]
impl<K, V, S> SequenceTrie<K, V, S>
where K: TrieKey,
S: BuildHasher + Default + Clone,
{
pub fn with_hasher(hash_builder: S) -> SequenceTrie<K, V, S> {
SequenceTrie {
value: None,
children: HashMap::with_hasher(hash_builder),
}
}
}
#[cfg(feature = "btreemap")]
impl<K, V> SequenceTrie<K, V>
where K: TrieKey,
{
pub fn new() -> SequenceTrie<K, V> {
Self::new_generic()
}
}
#[cfg(feature = "btreemap")]
impl<K, V, S> SequenceTrie<K, V, S>
where K: TrieKey,
S: BuildHasher + Default + Clone,
{
pub fn new_generic() -> SequenceTrie<K, V, S> {
SequenceTrie {
value: None,
children: BTreeMap::new(),
_phantom: PhantomData,
}
}
}
impl<K, V, S> SequenceTrie<K, V, S>
where K: TrieKey,
S: BuildHasher + Default + Clone,
{
pub fn value(&self) -> Option<&V> {
self.value.as_ref()
}
pub fn value_mut(&mut self) -> Option<&mut V> {
self.value.as_mut()
}
pub fn is_empty(&self) -> bool {
self.is_leaf() && self.value.is_none()
}
pub fn is_leaf(&self) -> bool {
self.children.is_empty()
}
pub fn insert<'key, I, Q: 'key + ?Sized>(&mut self, key: I, value: V) -> Option<V>
where I: IntoIterator<Item = &'key Q>,
Q: ToOwned<Owned = K>,
K: Borrow<Q>
{
self.insert_owned(key.into_iter().map(ToOwned::to_owned), value)
}
#[cfg(not(feature = "btreemap"))]
pub fn insert_owned<I>(&mut self, key: I, value: V) -> Option<V>
where I: IntoIterator<Item = K>
{
let key_node = key.into_iter().fold(self, |current_node, fragment| {
let hash_builder = current_node.children.hasher().clone();
current_node.children
.entry(fragment)
.or_insert_with(|| Self::with_hasher(hash_builder))
});
mem::replace(&mut key_node.value, Some(value))
}
#[cfg(feature = "btreemap")]
pub fn insert_owned<I>(&mut self, key: I, value: V) -> Option<V>
where I: IntoIterator<Item = K>
{
let key_node = key.into_iter().fold(self, |current_node, fragment| {
current_node.children
.entry(fragment)
.or_insert_with(Self::new_generic)
});
mem::replace(&mut key_node.value, Some(value))
}
pub fn get<'key, I, Q: ?Sized>(&self, key: I) -> Option<&V>
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.get_node(key).and_then(|node| node.value.as_ref())
}
pub fn get_node<'key, I, Q: ?Sized>(&self, key: I) -> Option<&SequenceTrie<K, V, S>>
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
let mut current_node = self;
for fragment in key {
match current_node.children.get(fragment) {
Some(node) => current_node = node,
None => return None,
}
}
Some(current_node)
}
pub fn get_mut<'key, I, Q: ?Sized>(&mut self, key: I) -> Option<&mut V>
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.get_node_mut(key).and_then(|node| node.value.as_mut())
}
pub fn get_node_mut<'key, I, Q: ?Sized>(&mut self, key: I) -> Option<&mut SequenceTrie<K, V, S>>
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
let mut current_node = Some(self);
for fragment in key {
match current_node.and_then(|node| node.children.get_mut(fragment)) {
Some(node) => current_node = Some(node),
None => return None,
}
}
current_node
}
pub fn get_prefix_nodes<'key, I, Q: ?Sized>(&self, key: I) -> Vec<&SequenceTrie<K, V, S>>
where I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.prefix_iter(key).collect()
}
pub fn get_ancestor<'key, I, Q: ?Sized>(&self, key: I) -> Option<&V>
where I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.get_ancestor_node(key).and_then(|node| node.value.as_ref())
}
pub fn get_ancestor_node<'key, I, Q: ?Sized>(&self, key: I) -> Option<&SequenceTrie<K, V, S>>
where I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.prefix_iter(key)
.filter(|node| node.value.is_some())
.last()
}
pub fn remove<'key, I, Q: ?Sized>(&mut self, key: I)
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
self.remove_recursive(key);
}
fn remove_recursive<'key, I, Q: ?Sized>(&mut self, key: I) -> bool
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
let mut fragments = key.into_iter();
match fragments.next() {
None => {
self.value = None;
}
Some(fragment) => {
let delete_child = match self.children.get_mut(fragment) {
Some(child) => child.remove_recursive(fragments),
None => false,
};
if delete_child {
self.children.remove(fragment);
}
}
}
self.is_empty()
}
pub fn map<F>(&mut self, f: F) where F: Fn(&Self) -> Option<V> {
self.map_rec(&f)
}
fn map_rec<F>(&mut self, f: &F) where F: Fn(&Self) -> Option<V> {
for child in self.children.values_mut() {
child.map_rec(f);
}
if let Some(v) = f(&*self) {
self.value = Some(v);
}
}
pub fn iter(&self) -> Iter<K, V, S> {
Iter {
root: self,
root_visited: false,
key: vec![],
stack: vec![],
}
}
pub fn keys(&self) -> Keys<K, V, S> {
Keys { inner: self.iter() }
}
pub fn values(&self) -> Values<K, V, S> {
Values { inner: self.iter() }
}
pub fn prefix_iter<'trie, 'key, I, Q: ?Sized>(&'trie self,
key: I)
-> PrefixIter<'trie, 'key, K, V, Q, I::IntoIter, S>
where I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key
{
PrefixIter {
next_node: Some(self),
fragments: key.into_iter(),
_phantom: PhantomData,
}
}
pub fn children(&self) -> Vec<&Self> {
self.children.values().collect()
}
pub fn children_with_keys<'a>(&'a self) -> Vec<(&'a K, &'a Self)> {
self.children.iter().collect()
}
}
pub struct Iter<'a, K: 'a, V: 'a, S: 'a = RandomState>
where K: TrieKey,
S: BuildHasher + Default
{
root: &'a SequenceTrie<K, V, S>,
root_visited: bool,
key: Vec<&'a K>,
stack: Vec<StackItem<'a, K, V, S>>,
}
pub type KeyValuePair<'a, K, V> = (Vec<&'a K>, &'a V);
pub struct Keys<'a, K: 'a, V: 'a, S: 'a = RandomState>
where K: TrieKey,
S: BuildHasher + Default
{
inner: Iter<'a, K, V, S>,
}
pub struct Values<'a, K: 'a, V: 'a, S: 'a = RandomState>
where K: TrieKey,
S: BuildHasher + Default
{
inner: Iter<'a, K, V, S>,
}
struct StackItem<'a, K: 'a, V: 'a, S: 'a = RandomState>
where K: TrieKey,
S: BuildHasher + Default
{
#[cfg(not(feature = "btreemap"))]
child_iter: hash_map::Iter<'a, K, SequenceTrie<K, V, S>>,
#[cfg(feature = "btreemap")]
child_iter: btree_map::Iter<'a, K, SequenceTrie<K, V, S>>,
}
enum IterAction<'a, K: 'a, V: 'a, S: 'a>
where K: TrieKey,
S: BuildHasher + Default
{
Push(&'a K, &'a SequenceTrie<K, V, S>),
Pop,
}
impl<'a, K, V, S> Iterator for Iter<'a, K, V, S>
where K: TrieKey,
S: BuildHasher + Default
{
type Item = KeyValuePair<'a, K, V>;
fn next(&mut self) -> Option<KeyValuePair<'a, K, V>> {
use IterAction::*;
if !self.root_visited {
self.root_visited = true;
self.stack.push(StackItem { child_iter: self.root.children.iter() });
if let Some(ref root_val) = self.root.value {
return Some((vec![], root_val));
}
}
loop {
let action = match self.stack.last_mut() {
Some(stack_top) => {
match stack_top.child_iter.next() {
Some((fragment, child_node)) => Push(fragment, child_node),
None => Pop,
}
}
None => return None,
};
match action {
Push(fragment, node) => {
self.stack.push(StackItem { child_iter: node.children.iter() });
self.key.push(fragment);
if let Some(ref value) = node.value {
return Some((self.key.clone(), value));
}
}
Pop => {
self.key.pop();
self.stack.pop();
}
}
}
}
}
impl<'a, K, V, S> Iterator for Keys<'a, K, V, S>
where K: TrieKey,
S: BuildHasher + Default,
{
type Item = Vec<&'a K>;
fn next(&mut self) -> Option<Vec<&'a K>> {
self.inner.next().map(|(k, _)| k)
}
}
impl<'a, K, V, S> Iterator for Values<'a, K, V, S>
where K: TrieKey,
S: BuildHasher + Default
{
type Item = &'a V;
fn next(&mut self) -> Option<&'a V> {
self.inner.next().map(|(_, v)| v)
}
}
impl<K, V, S> PartialEq for SequenceTrie<K, V, S>
where K: TrieKey,
V: PartialEq,
S: BuildHasher + Default
{
fn eq(&self, other: &Self) -> bool {
self.value == other.value && self.children == other.children
}
}
impl<K, V, S> Eq for SequenceTrie<K, V, S>
where K: TrieKey,
V: Eq,
S: BuildHasher + Default
{}
impl<K, V, S> Default for SequenceTrie<K, V, S>
where K: TrieKey,
S: BuildHasher + Default + Clone
{
fn default() -> Self {
#[cfg(not(feature = "btreemap"))]
{ SequenceTrie::with_hasher(S::default()) }
#[cfg(feature = "btreemap")]
{ SequenceTrie::new_generic() }
}
}
pub struct PrefixIter<'trie, 'key, K, V, Q: ?Sized, I, S = RandomState>
where K: 'trie + TrieKey,
V: 'trie,
I: 'key + Iterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key,
S: 'trie + BuildHasher + Default
{
next_node: Option<&'trie SequenceTrie<K, V, S>>,
fragments: I,
_phantom: PhantomData<&'key I>,
}
impl<'trie, 'key, K, V, Q: ?Sized, I, S> Iterator for PrefixIter<'trie, 'key, K, V, Q, I, S>
where K: 'trie + TrieKey,
V: 'trie,
I: 'key + Iterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key,
S: BuildHasher + Default
{
type Item = &'trie SequenceTrie<K, V, S>;
fn next(&mut self) -> Option<Self::Item> {
if let Some(current_node) = self.next_node.take() {
if let Some(fragment) = self.fragments.next() {
self.next_node = current_node.children.get(fragment)
}
return Some(current_node);
}
None
}
fn size_hint(&self) -> (usize, Option<usize>) {
let lower = if self.next_node.is_some() {
1
} else {
0
};
(lower, self.fragments.size_hint().1)
}
}