#![warn(
clippy::all,
clippy::pedantic,
clippy::nursery,
clippy::cargo,
missing_docs
)]
use crate::subset::Subset;
use crate::superset::SuperSet;
use crate::values::Values;
use std::iter::FromIterator;
mod entry;
mod subset;
mod superset;
mod values;
pub use entry::{CreatedEntry, Entry, EntryBuilder, ExistingEntry};
#[derive(Debug, Default, Eq, PartialEq)]
struct Node<K, T> {
children: Vec<(K, Node<K, T>)>,
leaves: Vec<T>,
}
impl<K, T> Node<K, T> {
pub const fn new() -> Self {
Self {
children: vec![],
leaves: vec![],
}
}
}
impl<K, T> Drop for Node<K, T> {
fn drop(&mut self) {
let mut stack = Vec::with_capacity(self.children.len());
while let Some((_, child)) = self.children.pop() {
stack.push(child);
while let Some(mut current) = stack.pop() {
while let Some((_, child)) = current.children.pop() {
stack.push(child)
}
}
}
}
}
impl<K, T> Node<K, T>
where
K: Ord,
{
fn has_descendant(&self, key: &K) -> bool {
println!("here");
if self.children.binary_search_by(|(k, _)| k.cmp(key)).is_ok() {
return true;
}
self.children
.iter()
.take_while(|(k, _)| k < key)
.any(|(_, n)| n.has_descendant(key))
}
fn between_inclusive(&self, from: &K, to: &K) -> &[(K, Self)] {
match (
self.children.binary_search_by(|(k, _)| k.cmp(from)),
self.children.binary_search_by(|(k, _)| k.cmp(to)),
) {
(Ok(from), Ok(to)) | (Err(from), Ok(to)) => &self.children[from..=to],
(Ok(from), Err(to)) | (Err(from), Err(to)) => &self.children[from..to],
}
}
}
#[derive(Debug, Default)]
pub struct SetTrie<K, T>(Node<K, T>);
impl<K, T> SetTrie<K, T> {
#[must_use]
pub const fn new() -> Self {
Self(Node::new())
}
}
impl<K, T> SetTrie<K, T>
where
K: Ord,
{
#[must_use]
pub fn entry<IK: IntoIterator<Item = K>>(
&mut self,
keys: IK,
) -> EntryBuilder<K, T, IK::IntoIter> {
EntryBuilder::new(self, keys.into_iter())
}
pub fn insert(&mut self, keys: impl IntoIterator<Item = K>, item: T) {
self.entry(keys.into_iter()).and_insert(item);
}
pub fn insert_many<IK: IntoIterator<Item = K>, IT: IntoIterator<Item = T>>(
&mut self,
keys: IK,
item: IT,
) {
self.entry(keys.into_iter()).and_extend(item);
}
#[must_use]
pub fn subsets<'a, 'b>(&'a self, keys: &'b [K]) -> Subset<'a, 'b, K, T> {
Subset::new(self, keys)
}
#[must_use]
pub fn values(&self) -> Values<K, T> {
Values::new(self)
}
#[must_use]
pub fn supersets<'a, 'b>(&'a self, keys: &'b [K]) -> SuperSet<'a, 'b, K, T> {
SuperSet::new(self, keys)
}
}
impl<I, K, T> Extend<(I, T)> for SetTrie<K, T>
where
I: IntoIterator<Item = K>,
K: Ord,
{
fn extend<F: IntoIterator<Item = (I, T)>>(&mut self, iter: F) {
for (k, t) in iter {
self.insert(k, t)
}
}
}
impl<I, K, T> FromIterator<(I, T)> for SetTrie<K, T>
where
I: IntoIterator<Item = K>,
K: Ord,
{
fn from_iter<F: IntoIterator<Item = (I, T)>>(iter: F) -> Self {
let mut trie = Self::new();
trie.extend(iter);
trie
}
}
#[cfg(test)]
mod tests {
use super::*;
mod doctests {
include!(concat!(env!("OUT_DIR"), "/skeptic-tests.rs"));
}
#[test]
fn insert() {
let mut trie = SetTrie::new();
trie.insert(&[1], "c");
trie.insert(&[1, 2], "c");
trie.insert(&[1, 2, 3], "a");
trie.insert(&[1, 2, 3], "b");
assert_eq!(trie.entry(&[1, 2, 3]).items(), Some(&vec!["a", "b"]))
}
#[test]
fn test_stack_overflow() {
let seed = 2000000;
let mut trie = SetTrie::new();
let mut current = trie.entry(0..1).or_insert(0);
for i in 1..seed {
current = current.entry(i - 1..i).or_insert(i)
}
}
}