use std::fmt::Debug;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
use std::rc::Rc;
use std::cmp::min;
use crate::adapton::catalog::collections::{ListIntro, ListElim, list_fold};
use crate::adapton::catalog::bitstring::*;
use crate::adapton::engine::*;
use crate::macros::*;
#[derive(Debug,PartialEq,Eq,Clone)]
pub enum Trie<X> {
Nil(BS),
Leaf(BS, X),
Bin(BS, Box<Trie<X>>, Box<Trie<X>>),
Root(Meta, Box<Trie<X>>),
Name(Name, Box<Trie<X>>),
Art(Art<Trie<X>>),
}
pub const PLACEMENT_SEED: u64 = 42;
#[derive(Debug,PartialEq,Eq,Hash,Clone)]
pub struct Meta {
pub min_depth: i64,
}
pub trait MetaT {
fn hash_seeded(&self, _: u64);
}
impl MetaT for Meta {
fn hash_seeded(&self, seed: u64) {
let mut hasher = DefaultHasher::new();
seed.hash(&mut hasher);
"Adapton.Trie.Meta".hash(&mut hasher);
self.min_depth.hash(&mut hasher);
}
}
pub trait TrieIntro<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
fn nil(_: BS) -> Self;
fn leaf(_: BS, _: X) -> Self;
fn bin(_: BS, _: Self, _: Self) -> Self;
fn root(_: Meta, _: Self) -> Self;
fn name(_: Name, _: Self) -> Self;
fn art(_: Art<Self>) -> Self;
fn empty(_: Meta) -> Self;
fn singleton(_: Meta, _: Name, _: X) -> Self;
fn extend(_: Name, _: Self, _: X) -> Self;
}
pub trait TrieElim<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
fn find(_: &Self, _: &X, _: i64) -> Option<X>;
fn is_empty(_: &Self) -> bool;
fn split_atomic(_: Self) -> Self;
fn elim<Res, NilC, LeafC, BinC, RootC, NameC>(_: Self, _: NilC, _: LeafC, _: BinC, _: RootC, _: NameC) -> Res
where NilC: FnOnce(BS) -> Res,
LeafC: FnOnce(BS, X) -> Res,
BinC: FnOnce(BS, Self, Self) -> Res,
RootC: FnOnce(Meta, Self) -> Res,
NameC: FnOnce(Name, Self) -> Res;
fn elim_arg<Arg, Res, NilC, LeafC, BinC, RootC, NameC>(_: Self,
_: Arg,
_: NilC,
_: LeafC,
_: BinC,
_: RootC,
_: NameC)
-> Res
where NilC: FnOnce(BS, Arg) -> Res,
LeafC: FnOnce(BS, X, Arg) -> Res,
BinC: FnOnce(BS, Self, Self, Arg) -> Res,
RootC: FnOnce(Meta, Self, Arg) -> Res,
NameC: FnOnce(Name, Self, Arg) -> Res;
fn elim_ref<Res, NilC, LeafC, BinC, RootC, NameC>(_: &Self,
_: NilC,
_: LeafC,
_: BinC,
_: RootC,
_: NameC)
-> Res
where NilC: FnOnce(&BS) -> Res,
LeafC: FnOnce(&BS, &X) -> Res,
BinC: FnOnce(&BS, &Self, &Self) -> Res,
RootC: FnOnce(&Meta, &Self) -> Res,
NameC: FnOnce(&Name, &Self) -> Res;
}
impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieIntro<X> for Trie<X> {
fn nil(bs: BS) -> Self {
Trie::Nil(bs)
}
fn leaf(bs: BS, x: X) -> Self {
Trie::Leaf(bs, x)
}
fn bin(bs: BS, l: Self, r: Self) -> Self {
Trie::Bin(bs, Box::new(l), Box::new(r))
}
fn root(meta: Meta, trie: Self) -> Self {
Trie::Root(meta, Box::new(trie))
}
fn name(nm: Name, trie: Self) -> Self {
Trie::Name(nm, Box::new(trie))
}
fn art(art: Art<Self>) -> Self {
Trie::Art(art)
}
fn empty(meta: Meta) -> Self {
if meta.min_depth > BS::MAX_LEN {
println!("Cannot make Adapton.Trie with min_depth > {} (given {})",
BS::MAX_LEN,
meta.min_depth);
}
let min = min(meta.min_depth, BS::MAX_LEN);
let meta = Meta { min_depth: min };
let nm = name_of_str("empty");
let (nm1, nm2) = name_fork(nm);
let mtbs = BS {
length: 0,
value: 0,
};
let nil_art = thunk!(nm2.clone() =>> Self::nil, bs:mtbs);
let root_art = thunk!(nm1.clone() =>> Self::root, meta:meta,
trie:Self::name(nm2, Self::art(nil_art)));
Self::name(nm1.clone(), Self::art(root_art))
}
fn singleton(meta: Meta, nm: Name, elt: X) -> Self {
Self::extend(nm, TrieIntro::empty(meta), elt)
}
fn extend(nm: Name, trie: Self, elt: X) -> Self {
let (nm, nm_) = name_fork(nm);
let root_mfn_art = panic!("todo");
Self::name(nm, Self::art(root_mfn_art))
}
}
impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> Hash for Trie<X> {
fn hash<H: Hasher>(&self, state: &mut H) {
match *self {
Trie::Nil(bs) => bs.hash(state),
Trie::Leaf(bs, ref x) => {
x.hash(state);
bs.hash(state)
}
Trie::Bin(bs, ref left, ref right) => {
right.hash(state);
left.hash(state);
bs.hash(state)
}
Trie::Root(ref md, ref t) => {
t.hash(state);
md.hash_seeded(state.finish());
}
Trie::Name(ref nm, ref t) => {
t.hash(state);
nm.hash(state)
}
Trie::Art(ref art_t) => art_t.hash(state),
}
}
}
impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieElim<X> for Trie<X> {
fn find(trie: &Self, elt: &X, i: i64) -> Option<X> {
Self::elim_ref(trie,
|_| None,
|_, x| if *elt == *x { Some(x.clone()) } else { None },
|_, left, right| if i % 2 == 0 {
Self::find(left, elt, i >> 1)
} else {
Self::find(right, elt, i >> 1)
},
|_, t| Self::find(t, elt, i),
|_, t| Self::find(t, elt, i))
}
fn is_empty(trie: &Self) -> bool {
Self::elim_ref(trie,
|_| true,
|_, _| false,
|_, _, _| false,
|_, t| Self::is_empty(t),
|_, t| Self::is_empty(t))
}
fn split_atomic(trie: Self) -> Self {
fn suffix(bs: BS, k: i64) -> bool {
bs.value & k == bs.value
}
match trie {
t @ Trie::Nil(_) |
t @ Trie::Bin(_, _, _) => t,
Trie::Leaf(bs, e) => {
let bs0 = BS::prepend(0, bs);
let bs1 = BS::prepend(1, bs);
let mut hasher = DefaultHasher::new();
e.hash(&mut hasher);
if suffix(bs1, hasher.finish() as i64) {
Self::bin(bs, Self::nil(bs0), Self::leaf(bs1, e))
} else {
Self::bin(bs, Self::leaf(bs0, e), Self::nil(bs1))
}
}
_ => panic!("Bad split_atomic(t)"),
}
}
fn elim<Res, NilC, LeafC, BinC, RootC, NameC>(trie: Self,
nil: NilC,
leaf: LeafC,
bin: BinC,
root: RootC,
name: NameC)
-> Res
where NilC: FnOnce(BS) -> Res,
LeafC: FnOnce(BS, X) -> Res,
BinC: FnOnce(BS, Self, Self) -> Res,
RootC: FnOnce(Meta, Self) -> Res,
NameC: FnOnce(Name, Self) -> Res
{
match trie {
Trie::Nil(bs) => nil(bs),
Trie::Leaf(bs, x) => leaf(bs, x),
Trie::Bin(bs, l, r) => bin(bs, *l, *r),
Trie::Name(nm, t) => name(nm, *t),
Trie::Root(meta, t) => root(meta, *t),
Trie::Art(art) => {
let trie = force(&art);
Self::elim(trie, nil, leaf, bin, root, name)
}
}
}
fn elim_arg<Arg, Res, NilC, LeafC, BinC, RootC, NameC>(trie: Self,
arg: Arg,
nil: NilC,
leaf: LeafC,
bin: BinC,
root: RootC,
name: NameC)
-> Res
where NilC: FnOnce(BS, Arg) -> Res,
LeafC: FnOnce(BS, X, Arg) -> Res,
BinC: FnOnce(BS, Self, Self, Arg) -> Res,
RootC: FnOnce(Meta, Self, Arg) -> Res,
NameC: FnOnce(Name, Self, Arg) -> Res
{
match trie {
Trie::Nil(bs) => nil(bs, arg),
Trie::Leaf(bs, x) => leaf(bs, x, arg),
Trie::Bin(bs, l, r) => bin(bs, *l, *r, arg),
Trie::Name(nm, t) => name(nm, *t, arg),
Trie::Root(meta, t) => root(meta, *t, arg),
Trie::Art(art) => {
let trie = force(&art);
Self::elim_arg(trie, arg, nil, leaf, bin, root, name)
}
}
}
fn elim_ref<Res, NilC, LeafC, BinC, RootC, NameC>(trie: &Self,
nil: NilC,
leaf: LeafC,
bin: BinC,
root: RootC,
name: NameC)
-> Res
where NilC: FnOnce(&BS) -> Res,
LeafC: FnOnce(&BS, &X) -> Res,
BinC: FnOnce(&BS, &Self, &Self) -> Res,
RootC: FnOnce(&Meta, &Self) -> Res,
NameC: FnOnce(&Name, &Self) -> Res
{
match *trie {
Trie::Nil(ref bs) => nil(bs),
Trie::Leaf(ref bs, ref x) => leaf(bs, x),
Trie::Bin(ref bs, ref l, ref r) => bin(bs, &*l, &*r),
Trie::Name(ref nm, ref t) => name(nm, &*t),
Trie::Root(ref meta, ref t) => root(meta, &*t),
Trie::Art(ref art) => {
let trie = force(art);
Self::elim_ref(&trie, nil, leaf, bin, root, name)
}
}
}
}
pub trait SetIntro<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
fn empty() -> Self;
fn add(_: Self, e: X) -> Self;
}
pub trait SetElim<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
fn mem(_: &Self, _: &X) -> bool;
fn fold<Res, F>(_: Self, _: Res, _: Rc<F>) -> Res where F: Fn(X, Res) -> Res;
}
impl<X, Set: TrieIntro<X> + TrieElim<X>> SetIntro<X> for Set {
fn empty() -> Self {
let meta = Meta { min_depth: 1 };
Self::empty(meta)
}
fn add(set: Self, elt: X) -> Self {
Self::extend(name_unit(), set, elt)
}
}
impl<X: Hash, Set: TrieIntro<X> + TrieElim<X>> SetElim<X> for Set {
fn mem(set: &Self, elt: &X) -> bool {
let mut hasher = DefaultHasher::new();
elt.hash(&mut hasher);
match Set::find(set, elt, hasher.finish() as i64) {
Some(_) => true,
None => false,
}
}
fn fold<Res, F>(set: Self, res: Res, f: Rc<F>) -> Res
where F: Fn(X, Res) -> Res
{
Self::elim_arg(set,
res,
|_, arg| arg,
|_, x, arg| f(x, arg),
|_, left, right, arg| {
Self::fold(right, Self::fold(left, arg, f.clone()), f.clone())
},
|_, t, arg| Self::fold(t, arg, f.clone()),
|_, t, arg| Self::fold(t, arg, f.clone()))
}
}
pub type Set<X> = Trie<X>;
pub fn trie_fold
<X, T:TrieElim<X>, Res:Hash+Debug+Eq+Clone+'static, F:'static>
(t: T, res:Res, f: Rc<F>) -> Res
where F: Fn(X, Res) -> Res {
T::elim_arg(t,
(res, f),
|_, (arg, _)| arg,
|_, x, (arg, f)| f(x, arg),
|_, left, right, (arg, f)| trie_fold(right, trie_fold(left, arg, f.clone()), f),
|_, t, (arg, f)| trie_fold(t, arg, f),
|nm, t, (arg, f)| memo!(nm =>> trie_fold, t:t, res:arg ;; f:f))
}
pub fn trie_of_list<X: Hash + Clone + Debug + 'static,
T: TrieIntro<X> + 'static,
L: ListElim<X> + ListIntro<X> + 'static>
(list: L)
-> T {
list_fold(list,
T::empty(Meta { min_depth: 1 }),
Rc::new(|x, trie_acc| T::extend(name_unit(), trie_acc, x)))
}