adapton/catalog/
trie.rs

1use std::fmt::Debug;
2use std::hash::{Hash, Hasher};
3use std::collections::hash_map::DefaultHasher;
4use std::rc::Rc;
5use std::cmp::min;
6
7use crate::adapton::catalog::collections::{ListIntro, ListElim, list_fold};
8use crate::adapton::catalog::bitstring::*;
9use crate::adapton::engine::*;
10use crate::macros::*;
11
12/// Probablistically Balanced Trie
13/// Rough implementation of probabilistic tries from OOPSLA 2015 paper.
14///
15/// See also: [Tries in OCaml](http://github.com/plum-umd/adapton.ocaml)
16#[derive(Debug,PartialEq,Eq,Clone)]
17pub enum Trie<X> {
18    Nil(BS),
19    Leaf(BS, X),
20    Bin(BS, Box<Trie<X>>, Box<Trie<X>>),
21    Root(Meta, Box<Trie<X>>),
22    Name(Name, Box<Trie<X>>),
23    Art(Art<Trie<X>>),
24}
25
26pub const PLACEMENT_SEED: u64 = 42;
27
28/// Metadata held by the root node.
29#[derive(Debug,PartialEq,Eq,Hash,Clone)]
30pub struct Meta {
31    pub min_depth: i64,
32}
33
34pub trait MetaT {
35    fn hash_seeded(&self, _: u64);
36}
37
38impl MetaT for Meta {
39    fn hash_seeded(&self, seed: u64) {
40        let mut hasher = DefaultHasher::new();
41        seed.hash(&mut hasher);
42        "Adapton.Trie.Meta".hash(&mut hasher);
43        self.min_depth.hash(&mut hasher);
44    }
45}
46
47// impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> PartialEq for Trie<X> {
48//     fn eq(&self, other: &Trie<X>) -> bool {
49//         match (self, other) {
50//             (&Trie::Nil(ref bs_self), &Trie::Nil(ref bs_other)) => bs_self == bs_other,
51//             (&Trie::Leaf(ref bs_self, ref e_self), &Trie::Leaf(ref bs_other, ref e_other)) => {
52//                 let bs_equal = bs_self == bs_other;
53//                 let b = bs_equal && e_self == e_other;
54//                 // println!("{:?}\n{}\n{:?}", self, b, other);
55//                 b
56//             }
57//             (&Trie::Bin(ref bs, ref left, ref right),
58//              &Trie::Bin(ref bs_other, ref left_other, ref right_other)) => {
59//                 let b = bs == bs_other && left == left_other && right == right_other;
60//                 // println!("{:?}\n{}\n{:?}", self, b, other);
61//                 b
62//             }
63//             (&Trie::Root(ref md, ref t), &Trie::Root(ref md_other, ref t_other)) => {
64//                 let b = md == md_other && t == t_other;
65//                 // println!("{:?}\n{}\n{:?}", t, b, t_other);
66//                 b
67//             }
68//             (&Trie::Name(ref nm, ref t), &Trie::Name(ref nm_other, ref t_other)) => {
69//                 let b = nm == nm_other && t == t_other;
70//                 // println!("{:?}\n{}\n{:?}", t, b, t_other);
71//                 b
72//             }
73//             (&Trie::Art(ref a), &Trie::Art(ref a_other)) => {
74//                 let b = a == a_other;
75//                 // println!("{:?}\n{}\n{:?}", a, b, a_other);
76//                 b
77//             }
78//             (t, t_other) => {
79//                 // println!("{:?}\n!=\n{:?}", t, t_other);
80//                 false
81//             }
82//         }
83//     }
84// }
85
86// impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> Eq for Trie<X> {}
87
88pub trait TrieIntro<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
89    fn nil(_: BS) -> Self;
90    fn leaf(_: BS, _: X) -> Self;
91    fn bin(_: BS, _: Self, _: Self) -> Self;
92    fn root(_: Meta, _: Self) -> Self;
93
94    // requisite "adaptonic" constructors: `name` and `art`:
95    fn name(_: Name, _: Self) -> Self;
96    fn art(_: Art<Self>) -> Self;
97
98    fn empty(_: Meta) -> Self;
99    fn singleton(_: Meta, _: Name, _: X) -> Self;
100    fn extend(_: Name, _: Self, _: X) -> Self;
101}
102
103pub trait TrieElim<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
104    fn find(_: &Self, _: &X, _: i64) -> Option<X>;
105    fn is_empty(_: &Self) -> bool;
106    fn split_atomic(_: Self) -> Self;
107
108    fn elim<Res, NilC, LeafC, BinC, RootC, NameC>(_: Self, _: NilC, _: LeafC, _: BinC, _: RootC, _: NameC) -> Res
109        where NilC: FnOnce(BS) -> Res,
110              LeafC: FnOnce(BS, X) -> Res,
111              BinC: FnOnce(BS, Self, Self) -> Res,
112              RootC: FnOnce(Meta, Self) -> Res,
113              NameC: FnOnce(Name, Self) -> Res;
114
115    fn elim_arg<Arg, Res, NilC, LeafC, BinC, RootC, NameC>(_: Self,
116                                                           _: Arg,
117                                                           _: NilC,
118                                                           _: LeafC,
119                                                           _: BinC,
120                                                           _: RootC,
121                                                           _: NameC)
122                                                           -> Res
123        where NilC: FnOnce(BS, Arg) -> Res,
124              LeafC: FnOnce(BS, X, Arg) -> Res,
125              BinC: FnOnce(BS, Self, Self, Arg) -> Res,
126              RootC: FnOnce(Meta, Self, Arg) -> Res,
127              NameC: FnOnce(Name, Self, Arg) -> Res;
128
129    fn elim_ref<Res, NilC, LeafC, BinC, RootC, NameC>(_: &Self,
130                                                      _: NilC,
131                                                      _: LeafC,
132                                                      _: BinC,
133                                                      _: RootC,
134                                                      _: NameC)
135                                                      -> Res
136        where NilC: FnOnce(&BS) -> Res,
137              LeafC: FnOnce(&BS, &X) -> Res,
138              BinC: FnOnce(&BS, &Self, &Self) -> Res,
139              RootC: FnOnce(&Meta, &Self) -> Res,
140              NameC: FnOnce(&Name, &Self) -> Res;
141}
142
143/*
14420121221-- requires box_syntax feature
145
146impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> Trie<X> {
147    fn mfn(nm: Name, meta: Meta, trie: Self, bs: BS, elt: X, hash: u64) -> Self {
148        match trie {
149            Trie::Nil(_) if BS::length(bs) < meta.min_depth => {
150                let h_ = hash >> 1;
151                let bs0 = BS::prepend(0, bs);
152                let bs1 = BS::prepend(1, bs);
153                let mt0 = Self::nil(bs0);
154                let mt1 = Self::nil(bs1);
155                if hash % 2 == 0 {
156                    Self::bin(bs, Self::mfn(nm, meta, mt0, bs0, elt, h_), mt1)
157                } else {
158                    Self::bin(bs, mt0, Self::mfn(nm, meta, mt1, bs1, elt, h_))
159                }
160            }
161            Trie::Nil(_) => Trie::Leaf(bs, elt),
162            Trie::Leaf(_, e) => {
163                let depth = BS::length(bs);
164                if depth >= BS::MAX_LEN || e == elt {
165                    Self::leaf(bs, e)
166                } else if depth < BS::MAX_LEN {
167                    Self::mfn(nm,
168                              meta,
169                              Self::split_atomic(Self::leaf(bs, e)),
170                              bs,
171                              elt,
172                              hash)
173                } else {
174                    panic!("Bad value found in nadd:\nLeaf(bs, e)\n{:?}",
175                           Self::leaf(bs, e));
176                }
177            }
178            Trie::Bin(bs, left, right) => {
179                let h_ = hash >> 1;
180                if hash % 2 == 0 {
181                    let l = Self::mfn(nm, meta, *left, BS::prepend(0, bs), elt, h_);
182                    Self::bin(bs, l, *right)
183                } else {
184                    let r = Self::mfn(nm, meta, *right, BS::prepend(1, bs), elt, h_);
185                    Self::bin(bs, *left, r)
186                }
187            }
188            Trie::Name(_, box Trie::Art(a)) => Self::mfn(nm, meta, force(&a), bs, elt, hash),
189            t => panic!("Bad value found in nadd:\n{:?}\n", t),
190        }
191    }
192
193    fn root_mfn(_: Name, nm: Name, trie: Self, elt: X) -> Self {
194        match trie {
195            Trie::Name(_, box Trie::Art(a)) => {
196                match force(&a) {
197                    Trie::Root(meta, t) => {
198                        let (nm, nm_) = name_fork(nm);
199                        let mut hasher = DefaultHasher::new();
200                        elt.hash(&mut hasher);
201                        let a = Self::mfn(nm_,
202                                          meta.clone(),
203                                          *t,
204                                          BS {
205                                              length: 0,
206                                              value: 0,
207                                          },
208                                          elt,
209                                          hasher.finish());
210                        Self::root(meta, Self::name(nm, Self::art(put(a))))
211                    }
212                    t @ Trie::Name(_, box Trie::Art(_)) => Self::root_mfn(nm.clone(), nm, t, elt),
213                    t => panic!("Non-root node entry to `Trie.extend': {:?}", t),
214                }
215            }
216            _ => panic!("None-name node at entry to `Trie.extend'"),
217        }
218    }
219}
220*/
221
222impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieIntro<X> for Trie<X> {
223    fn nil(bs: BS) -> Self {
224        Trie::Nil(bs)
225    }
226    fn leaf(bs: BS, x: X) -> Self {
227        Trie::Leaf(bs, x)
228    }
229    fn bin(bs: BS, l: Self, r: Self) -> Self {
230        Trie::Bin(bs, Box::new(l), Box::new(r))
231    }
232    fn root(meta: Meta, trie: Self) -> Self {
233        Trie::Root(meta, Box::new(trie))
234    }
235    fn name(nm: Name, trie: Self) -> Self {
236        Trie::Name(nm, Box::new(trie))
237    }
238    fn art(art: Art<Self>) -> Self {
239        Trie::Art(art)
240    }
241
242    fn empty(meta: Meta) -> Self {
243        if meta.min_depth > BS::MAX_LEN {
244            println!("Cannot make Adapton.Trie with min_depth > {} (given {})",
245                     BS::MAX_LEN,
246                     meta.min_depth);
247        }
248        let min = min(meta.min_depth, BS::MAX_LEN);
249        let meta = Meta { min_depth: min };
250        let nm = name_of_str("empty");
251        let (nm1, nm2) = name_fork(nm);
252        let mtbs = BS {
253            length: 0,
254            value: 0,
255        };
256        let nil_art = thunk!(nm2.clone() =>> Self::nil, bs:mtbs);
257        let root_art = thunk!(nm1.clone() =>> Self::root, meta:meta,
258                              trie:Self::name(nm2, Self::art(nil_art)));
259        Self::name(nm1.clone(), Self::art(root_art))
260    }
261
262    fn singleton(meta: Meta, nm: Name, elt: X) -> Self {
263        Self::extend(nm, TrieIntro::empty(meta), elt)
264    }
265
266    fn extend(nm: Name, trie: Self, elt: X) -> Self {
267        let (nm, nm_) = name_fork(nm);
268        // let a = Self::root_mfn(nm.clone(), nm_, trie, elt);
269        let root_mfn_art = panic!("todo"); //put(Self::root_mfn(nm.clone(), nm_, trie, elt));
270        Self::name(nm, Self::art(root_mfn_art))
271    }
272}
273
274impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> Hash for Trie<X> {
275    fn hash<H: Hasher>(&self, state: &mut H) {
276        match *self {
277            Trie::Nil(bs) => bs.hash(state),
278            Trie::Leaf(bs, ref x) => {
279                x.hash(state);
280                bs.hash(state)
281            }
282            Trie::Bin(bs, ref left, ref right) => {
283                right.hash(state);
284                left.hash(state);
285                bs.hash(state)
286            }
287            Trie::Root(ref md, ref t) => {
288                t.hash(state);
289                md.hash_seeded(state.finish());
290            }
291            Trie::Name(ref nm, ref t) => {
292                t.hash(state);
293                nm.hash(state)
294            }
295            Trie::Art(ref art_t) => art_t.hash(state),
296        }
297    }
298}
299
300impl<X: Debug + Hash + PartialEq + Eq + Clone + 'static> TrieElim<X> for Trie<X> {
301    fn find(trie: &Self, elt: &X, i: i64) -> Option<X> {
302        Self::elim_ref(trie,
303                       |_| None,
304                       |_, x| if *elt == *x { Some(x.clone()) } else { None },
305                       |_, left, right| if i % 2 == 0 {
306                           Self::find(left, elt, i >> 1)
307                       } else {
308                           Self::find(right, elt, i >> 1)
309                       },
310                       |_, t| Self::find(t, elt, i),
311                       |_, t| Self::find(t, elt, i))
312    }
313
314    fn is_empty(trie: &Self) -> bool {
315        Self::elim_ref(trie,
316                       |_| true,
317                       |_, _| false,
318                       |_, _, _| false,
319                       |_, t| Self::is_empty(t),
320                       |_, t| Self::is_empty(t))
321    }
322
323    fn split_atomic(trie: Self) -> Self {
324        fn suffix(bs: BS, k: i64) -> bool {
325            bs.value & k == bs.value
326        }
327        match trie {
328            t @ Trie::Nil(_) |
329            t @ Trie::Bin(_, _, _) => t,
330            Trie::Leaf(bs, e) => {
331                let bs0 = BS::prepend(0, bs);
332                let bs1 = BS::prepend(1, bs);
333                let mut hasher = DefaultHasher::new();
334                e.hash(&mut hasher);
335                if suffix(bs1, hasher.finish() as i64) {
336                    Self::bin(bs, Self::nil(bs0), Self::leaf(bs1, e))
337                } else {
338                    Self::bin(bs, Self::leaf(bs0, e), Self::nil(bs1))
339                }
340            }
341            _ => panic!("Bad split_atomic(t)"),
342        }
343    }
344
345    fn elim<Res, NilC, LeafC, BinC, RootC, NameC>(trie: Self,
346                                                  nil: NilC,
347                                                  leaf: LeafC,
348                                                  bin: BinC,
349                                                  root: RootC,
350                                                  name: NameC)
351                                                  -> Res
352        where NilC: FnOnce(BS) -> Res,
353              LeafC: FnOnce(BS, X) -> Res,
354              BinC: FnOnce(BS, Self, Self) -> Res,
355              RootC: FnOnce(Meta, Self) -> Res,
356              NameC: FnOnce(Name, Self) -> Res
357    {
358        match trie {
359            Trie::Nil(bs) => nil(bs),
360            Trie::Leaf(bs, x) => leaf(bs, x),
361            Trie::Bin(bs, l, r) => bin(bs, *l, *r),
362            Trie::Name(nm, t) => name(nm, *t),
363            Trie::Root(meta, t) => root(meta, *t),
364            Trie::Art(art) => {
365                let trie = force(&art);
366                Self::elim(trie, nil, leaf, bin, root, name)
367            }
368        }
369    }
370
371    fn elim_arg<Arg, Res, NilC, LeafC, BinC, RootC, NameC>(trie: Self,
372                                                           arg: Arg,
373                                                           nil: NilC,
374                                                           leaf: LeafC,
375                                                           bin: BinC,
376                                                           root: RootC,
377                                                           name: NameC)
378                                                           -> Res
379        where NilC: FnOnce(BS, Arg) -> Res,
380              LeafC: FnOnce(BS, X, Arg) -> Res,
381              BinC: FnOnce(BS, Self, Self, Arg) -> Res,
382              RootC: FnOnce(Meta, Self, Arg) -> Res,
383              NameC: FnOnce(Name, Self, Arg) -> Res
384    {
385        match trie {
386            Trie::Nil(bs) => nil(bs, arg),
387            Trie::Leaf(bs, x) => leaf(bs, x, arg),
388            Trie::Bin(bs, l, r) => bin(bs, *l, *r, arg),
389            Trie::Name(nm, t) => name(nm, *t, arg),
390            Trie::Root(meta, t) => root(meta, *t, arg),
391            Trie::Art(art) => {
392                let trie = force(&art);
393                Self::elim_arg(trie, arg, nil, leaf, bin, root, name)
394            }
395        }
396    }
397
398    fn elim_ref<Res, NilC, LeafC, BinC, RootC, NameC>(trie: &Self,
399                                                      nil: NilC,
400                                                      leaf: LeafC,
401                                                      bin: BinC,
402                                                      root: RootC,
403                                                      name: NameC)
404                                                      -> Res
405        where NilC: FnOnce(&BS) -> Res,
406              LeafC: FnOnce(&BS, &X) -> Res,
407              BinC: FnOnce(&BS, &Self, &Self) -> Res,
408              RootC: FnOnce(&Meta, &Self) -> Res,
409              NameC: FnOnce(&Name, &Self) -> Res
410    {
411        match *trie {
412            Trie::Nil(ref bs) => nil(bs),
413            Trie::Leaf(ref bs, ref x) => leaf(bs, x),
414            Trie::Bin(ref bs, ref l, ref r) => bin(bs, &*l, &*r),
415            Trie::Name(ref nm, ref t) => name(nm, &*t),
416            Trie::Root(ref meta, ref t) => root(meta, &*t),
417            Trie::Art(ref art) => {
418                let trie = force(art);
419                Self::elim_ref(&trie, nil, leaf, bin, root, name)
420            }
421        }
422    }
423}
424
425pub trait SetIntro<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
426    fn empty() -> Self;
427    fn add(_: Self, e: X) -> Self;
428    // fn remove(Self, e: &X) -> Self;
429    // fn union(Self, Self) -> Self;
430    // fn inter(Self, Self) -> Self;
431    // fn diff(Self, Self) -> Self;
432}
433
434pub trait SetElim<X>: Debug + Hash + PartialEq + Eq + Clone + 'static {
435    fn mem(_: &Self, _: &X) -> bool;
436    fn fold<Res, F>(_: Self, _: Res, _: Rc<F>) -> Res where F: Fn(X, Res) -> Res;
437}
438
439impl<X, Set: TrieIntro<X> + TrieElim<X>> SetIntro<X> for Set {
440    fn empty() -> Self {
441        let meta = Meta { min_depth: 1 };
442        Self::empty(meta)
443    }
444
445    fn add(set: Self, elt: X) -> Self {
446        Self::extend(name_unit(), set, elt)
447    }
448}
449
450impl<X: Hash, Set: TrieIntro<X> + TrieElim<X>> SetElim<X> for Set {
451    fn mem(set: &Self, elt: &X) -> bool {
452        let mut hasher = DefaultHasher::new();
453        elt.hash(&mut hasher);
454        match Set::find(set, elt, hasher.finish() as i64) {
455            Some(_) => true,
456            None => false,
457        }
458    }
459
460    fn fold<Res, F>(set: Self, res: Res, f: Rc<F>) -> Res
461        where F: Fn(X, Res) -> Res
462    {
463        Self::elim_arg(set,
464                       res,
465                       |_, arg| arg,
466                       |_, x, arg| f(x, arg),
467                       |_, left, right, arg| {
468                           Self::fold(right, Self::fold(left, arg, f.clone()), f.clone())
469                       },
470                       |_, t, arg| Self::fold(t, arg, f.clone()),
471                       |_, t, arg| Self::fold(t, arg, f.clone()))
472    }
473}
474
475pub type Set<X> = Trie<X>;
476pub fn trie_fold
477    <X, T:TrieElim<X>, Res:Hash+Debug+Eq+Clone+'static, F:'static>
478    (t: T, res:Res, f: Rc<F>) -> Res
479    where F: Fn(X, Res) -> Res {
480    T::elim_arg(t,
481                (res, f),
482                |_, (arg, _)| arg,
483                |_, x, (arg, f)| f(x, arg),
484                |_, left, right, (arg, f)| trie_fold(right, trie_fold(left, arg, f.clone()), f),
485                |_, t, (arg, f)| trie_fold(t, arg, f),
486                |nm, t, (arg, f)| memo!(nm =>> trie_fold, t:t, res:arg ;; f:f))
487}
488
489pub fn trie_of_list<X: Hash + Clone + Debug + 'static,
490                    T: TrieIntro<X> + 'static,
491                    L: ListElim<X> + ListIntro<X> + 'static>
492    (list: L)
493     -> T {
494    list_fold(list,
495              T::empty(Meta { min_depth: 1 }),
496              Rc::new(|x, trie_acc| T::extend(name_unit(), trie_acc, x)))
497}
adapton/catalog/trie.rs

adapton/catalog/
trie.rs
