lattices/ght/
test.rs

Help
1//! Tests for the GHT code
2#[cfg(test)]
3mod tests {
4    use std::collections::HashSet;
5
6    #[test]
7    fn basic_test() {
8        use variadics::var_expr;
9
10        use crate::GhtType;
11        use crate::ght::GeneralizedHashTrieNode;
12
13        // Example usage
14        type MyTrie1 = GhtType!(u32, u32 => &'static str: VariadicCountedHashSet);
15
16        fn ght_type<T: GeneralizedHashTrieNode>() {}
17        ght_type::<MyTrie1>();
18
19        let htrie1 = MyTrie1::new_from(vec![var_expr!(42, 314, "hello")]);
20        assert!(htrie1.contains(var_expr!(&42, &314, &"hello")));
21        assert_eq!(htrie1.recursive_iter().count(), 1);
22
23        type MyTrie2 = GhtType!(u32 => u32: VariadicCountedHashSet);
24        let htrie2 = MyTrie2::new_from(vec![var_expr!(42, 314)]);
25        assert!(htrie2.contains(var_expr!(&42, &314)));
26        assert_eq!(htrie1.recursive_iter().count(), 1);
27
28        type MyTrie3 = GhtType!(u32, u64, u16 => &'static str: VariadicCountedHashSet);
29        let htrie3 = MyTrie3::new_from(vec![
30            var_expr!(123, 2, 5, "hello"),
31            var_expr!(50, 1, 1, "hi"),
32            var_expr!(5, 1, 7, "hi"),
33            var_expr!(5, 1, 7, "bye"),
34        ]);
35        assert!(htrie3.contains(var_expr!(&50, &1, &1, &"hi")));
36        assert_eq!(htrie3.recursive_iter().count(), 4);
37    }
38    #[test]
39    fn test_ght_node_type_macro() {
40        use variadics::var_expr;
41
42        use crate::GhtType;
43        use crate::ght::GeneralizedHashTrieNode;
44
45        // 0 => 1
46        type LilTrie = GhtType!(() => u32: VariadicCountedHashSet);
47        let _j = LilTrie::default();
48        let _l = LilTrie::new_from(vec![var_expr!(1)]);
49
50        // 0 => >1
51        type LilTrie2 = GhtType!(() => u32, u64: VariadicCountedHashSet);
52        let _l = LilTrie2::default();
53        let _l = LilTrie2::new_from(vec![var_expr!(1, 1)]);
54
55        // 1 => 0
56        type KeyNoValTrie = GhtType!(u32 => (): VariadicCountedHashSet);
57        let l = KeyNoValTrie::new_from(vec![var_expr!(1)]);
58        let _: KeyNoValTrie = l;
59
60        // 1 => 1
61        type SmallTrie = GhtType!(u32 => &'static str: VariadicCountedHashSet);
62        type SmallKeyedTrie = GhtType!(u32 => &'static str: VariadicCountedHashSet);
63        let l = SmallTrie::new_from(vec![var_expr!(1, "hello")]);
64        let _: SmallKeyedTrie = l;
65
66        // 1 => >1
67        type SmallKeyLongValTrie = GhtType!(u32 => u64, u16, &'static str: VariadicCountedHashSet);
68        let _x = SmallKeyLongValTrie::new_from(vec![var_expr!(1, 999, 222, "hello")]);
69
70        // >1 => 0
71        type LongKeyNoValTrie = GhtType!(u32, u64 => (): VariadicCountedHashSet);
72        let l = LongKeyNoValTrie::new_from(vec![var_expr!(1, 999)]);
73        let _: LongKeyNoValTrie = l;
74
75        // >1 => 1
76        type LongKeySmallValTrie = GhtType!(u32, u16 => &'static str: VariadicCountedHashSet);
77        type LongKeySmallValKeyedTrie = GhtType!(u32, u16 => &'static str: VariadicCountedHashSet);
78        let x = LongKeySmallValTrie::new_from(vec![var_expr!(1, 314, "hello")]);
79        let _: LongKeySmallValKeyedTrie = x;
80        let _ = LongKeySmallValTrie::new_from(vec![var_expr!(1, 314, "hello")]);
81
82        // >1 => >1
83        type LongKeyLongValTrie = GhtType!(u32, u64 => u16, &'static str: VariadicCountedHashSet);
84        let _x = LongKeyLongValTrie::new_from(vec![var_expr!(1, 999, 222, "hello")]);
85    }
86
87    #[test]
88    fn test_insert() {
89        use variadics::var_expr;
90
91        use crate::GhtType;
92        use crate::ght::GeneralizedHashTrieNode;
93
94        type MyGht = GhtType!(u16, u32 => u64: VariadicCountedHashSet);
95        let mut htrie = MyGht::default();
96        htrie.insert(var_expr!(42, 314, 43770));
97        assert_eq!(htrie.recursive_iter().count(), 1);
98        assert_eq!(MyGht::HEIGHT, 2);
99        htrie.insert(var_expr!(42, 315, 43770));
100        assert_eq!(htrie.recursive_iter().count(), 2);
101        htrie.insert(var_expr!(42, 314, 30619));
102        assert_eq!(htrie.recursive_iter().count(), 3);
103        htrie.insert(var_expr!(43, 10, 600));
104        assert_eq!(htrie.recursive_iter().count(), 4);
105        assert!(htrie.contains(var_expr!(&42, &314, &30619)));
106        assert!(htrie.contains(var_expr!(&42, &315, &43770)));
107        assert!(htrie.contains(var_expr!(&43, &10, &600)));
108
109        type LongKeyLongValTrie = GhtType!(u32, u64 => u16, &'static str: VariadicCountedHashSet);
110        let mut htrie = LongKeyLongValTrie::new_from(vec![var_expr!(1, 999, 222, "hello")]);
111        htrie.insert(var_expr!(1, 999, 111, "bye"));
112        htrie.insert(var_expr!(1, 1000, 123, "cya"));
113        assert!(htrie.contains(var_expr!(&1, &999, &222, &"hello")));
114        assert!(htrie.contains(var_expr!(&1, &999, &111, &"bye")));
115        assert!(htrie.contains(var_expr!(&1, &1000, &123, &"cya")));
116    }
117
118    #[test]
119    fn test_scale() {
120        use variadics::var_expr;
121
122        use crate::GhtType;
123        use crate::ght::GeneralizedHashTrieNode;
124
125        type MyGht = GhtType!(bool, usize, &'static str => i32: VariadicCountedHashSet);
126        let mut htrie = MyGht::new_from(vec![var_expr!(true, 1, "hello", -5)]);
127        assert_eq!(htrie.recursive_iter().count(), 1);
128        for i in 1..1000000 {
129            htrie.insert(var_expr!(true, 1, "hello", i));
130        }
131        assert_eq!(htrie.recursive_iter().count(), 1000000);
132    }
133
134    #[test]
135    fn test_contains() {
136        use variadics::{VariadicExt, var_expr};
137
138        use crate::GhtType;
139        use crate::ght::GeneralizedHashTrieNode;
140
141        type MyGht = GhtType!(u16, u32 => u64: VariadicCountedHashSet);
142        let htrie = MyGht::new_from(vec![var_expr!(42_u16, 314_u32, 43770_u64)]);
143        let x = var_expr!(&42, &314, &43770);
144        assert!(htrie.contains(x));
145        assert!(htrie.contains(var_expr!(42, 314, 43770).as_ref_var()));
146        assert!(htrie.contains(var_expr!(&42, &314, &43770)));
147        assert!(!htrie.contains(var_expr!(42, 314, 30619).as_ref_var()));
148        assert!(!htrie.contains(var_expr!(&42, &315, &43770)));
149        assert!(!htrie.contains(var_expr!(&43, &314, &43770)));
150    }
151
152    #[test]
153    fn test_get() {
154        use variadics::{VariadicExt, var_expr};
155
156        use crate::GhtType;
157        use crate::ght::{GeneralizedHashTrieNode, GhtGet};
158
159        type MyGht = GhtType!(u32, u32 => u32: VariadicCountedHashSet);
160        let ht_root = MyGht::new_from(vec![var_expr!(42, 314, 43770)]);
161
162        let inner = ht_root.get(&42).unwrap();
163        let t = inner.recursive_iter().next().unwrap();
164        assert_eq!(t, var_expr!(&42, &314, &43770));
165
166        let leaf = inner.get(&314).unwrap();
167        let t = leaf.recursive_iter().next().unwrap();
168        assert_eq!(t, var_expr!(42, 314, 43770).as_ref_var());
169    }
170
171    #[test]
172    fn test_iter() {
173        use variadics::var_expr;
174
175        use crate::GhtType;
176        use crate::ght::{GeneralizedHashTrieNode, GhtGet};
177        type MyGht = GhtType!(u32, u32 => u32: VariadicCountedHashSet);
178        let ht_root = MyGht::new_from(vec![var_expr!(42, 314, 43770)]);
179        let inner_key = ht_root.iter().next().unwrap();
180        let inner = ht_root.get(&inner_key).unwrap();
181        let t = inner.recursive_iter().next().unwrap();
182        assert_eq!(t, var_expr!(&42, &314, &43770));
183
184        let leaf_key = inner.iter().next().unwrap();
185        let leaf = inner.get(&leaf_key).unwrap();
186        // iter() on leaf should return None
187        let t = leaf.iter().next();
188        assert!(t.is_none());
189    }
190
191    #[test]
192    fn test_recursive_iter() {
193        use variadics::{VariadicExt, var_expr, var_type};
194
195        use crate::GhtType;
196        use crate::ght::GeneralizedHashTrieNode;
197
198        type MyGht = GhtType!(u32, u32 => u32: VariadicCountedHashSet);
199        type InputType = var_type!(u32, u32, u32);
200        type ResultType<'a> = var_type!(&'a u32, &'a u32, &'a u32);
201        let input: HashSet<InputType> = HashSet::from_iter(
202            [
203                (42, 314, 30619),
204                (42, 314, 43770),
205                (42, 315, 43770),
206                (43, 10, 600),
207            ]
208            .iter()
209            .map(|&(a, b, c)| var_expr!(a, b, c)),
210        );
211        let htrie = MyGht::new_from(input.clone());
212        let result = input.iter().map(|v| v.as_ref_var()).collect();
213        let v: HashSet<ResultType> = htrie.recursive_iter().collect();
214        assert_eq!(v, result);
215    }
216
217    #[test]
218    fn test_prefix_iter_leaf() {
219        use variadics::variadic_collections::VariadicCountedHashSet;
220        use variadics::{var_expr, var_type};
221
222        use crate::ght::{GeneralizedHashTrieNode, GhtLeaf, GhtPrefixIter};
223
224        type InputType = var_type!(u8, u16, u32);
225        type ResultType<'a> = var_type!(&'a u8, &'a u16, &'a u32);
226
227        let input: HashSet<InputType> = HashSet::from_iter(
228            [
229                (42, 314, 30619),
230                (42, 314, 43770),
231                (42, 315, 43770),
232                (43, 10, 600),
233            ]
234            .iter()
235            .map(|&(a, b, c)| var_expr!(a, b, c)),
236        );
237        let leaf =
238            GhtLeaf::<InputType, var_type!(u16, u32), VariadicCountedHashSet<InputType>>::new_from(
239                input.clone(),
240            );
241        // let key = var_expr!(42u8).as_ref_var();
242        let key = (); // (var_expr!().as_ref_var();)
243        let v: HashSet<ResultType> = leaf.prefix_iter(key).collect();
244        let result = input
245            .iter()
246            // .filter(|t: &&InputType| t.0 == 42)
247            .map(|t: &InputType| var_expr!(&t.0, &t.1 .0, &t.1 .1 .0))
248            .collect();
249        assert_eq!(v, result);
250    }
251
252    #[test]
253    fn test_prefix_iter() {
254        use variadics::{VariadicExt, var_expr, var_type};
255
256        use crate::GhtType;
257        use crate::ght::{GeneralizedHashTrieNode, GhtPrefixIter};
258
259        type MyGht = GhtType!(u8, u16 => u32: VariadicCountedHashSet);
260        type InputType = var_type!(u8, u16, u32);
261        type ResultType<'a> = var_type!(&'a u8, &'a u16, &'a u32);
262        let input: HashSet<InputType> = HashSet::from_iter(
263            [
264                (42, 314, 30619),
265                (42, 314, 43770),
266                (42, 315, 43770),
267                (43, 10, 600),
268            ]
269            .iter()
270            .map(|&(a, b, c)| var_expr!(a, b, c)),
271        );
272        let htrie = MyGht::new_from(input.clone());
273
274        let v: HashSet<ResultType> = htrie.prefix_iter(var_expr!(42, 315).as_ref_var()).collect();
275        let result = HashSet::from_iter([var_expr!(&42, &315, &43770)].iter().copied());
276        assert_eq!(v, result);
277
278        let v: HashSet<ResultType> = htrie.prefix_iter(var_expr!(42u8).as_ref_var()).collect();
279        let result = input
280            .iter()
281            .filter(|t: &&InputType| t.0 == 42)
282            .map(|t: &InputType| var_expr!(&t.0, &t.1.0, &t.1.1.0))
283            .collect();
284        assert_eq!(v, result);
285
286        for row in htrie.prefix_iter(var_expr!(42, 315, 43770).as_ref_var()) {
287            assert_eq!(row, var_expr!(&42, &315, &43770));
288        }
289    }
290
291    #[test]
292    fn test_prefix_iter_complex() {
293        use variadics::{VariadicExt, var_expr, var_type};
294
295        use crate::GhtType;
296        use crate::ght::{GeneralizedHashTrieNode, GhtPrefixIter};
297
298        type MyGht = GhtType!(bool, u32, &'static str => i32: VariadicCountedHashSet);
299        type InputType = var_type!(bool, u32, &'static str, i32);
300        type ResultType<'a> = var_type!(&'a bool, &'a u32, &'a &'static str, &'a i32);
301        let input: HashSet<InputType> = HashSet::from_iter(
302            [
303                (true, 1, "hello", -5),
304                (true, 1, "hi", -2),
305                (true, 1, "hi", -3),
306                (true, 1, "hi", -4),
307                (true, 1, "hi", -5),
308                (true, 2, "hello", 1),
309                (false, 10, "bye", 5),
310            ]
311            .iter()
312            .map(|&(a, b, c, d)| var_expr!(a, b, c, d)),
313        );
314
315        let htrie = MyGht::new_from(input.clone());
316
317        let v: HashSet<ResultType> = htrie
318            .prefix_iter(var_expr!(true, 1, "hi").as_ref_var())
319            .collect();
320        let result = input
321            .iter()
322            .filter(|t: &&InputType| t.0 && t.1.0 == 1 && t.1.1.0 == "hi")
323            //.map(|t: &InputType| (&t.0, &t.1 .0, (&t.1 .1 .0, (&t.1 .1 .1 .0, ()))))
324            .map(|t| t.as_ref_var())
325            .collect();
326        assert_eq!(v, result);
327
328        let v: HashSet<ResultType> = htrie.prefix_iter(var_expr!(true).as_ref_var()).collect();
329        let result = input
330            .iter()
331            .filter(|t: &&InputType| t.0)
332            .map(|t: &InputType| t.as_ref_var())
333            .collect();
334        assert_eq!(v, result);
335    }
336
337    #[test]
338    fn test_merge() {
339        use variadics::{var_expr, var_type};
340
341        use crate::ght::GeneralizedHashTrieNode;
342        use crate::{GhtType, Merge};
343
344        type MyGht = GhtType!(u32, u64 => u16, &'static str: VariadicHashSet);
345
346        let mut test_ght1 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
347        let test_ght2 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
348
349        assert_eq!(
350            test_ght1
351                .recursive_iter()
352                .collect::<Vec<var_type!(&u32, &u64, &u16, &&'static str)>>()
353                .len(),
354            1
355        );
356        test_ght1.merge(test_ght2.clone());
357        // merge does not contain duplicate copy of the tuple
358        assert_eq!(
359            test_ght1
360                .recursive_iter()
361                .collect::<Vec<var_type!(&u32, &u64, &u16, &&'static str)>>()
362                .len(),
363            1
364        );
365        assert!(!test_ght1.merge(test_ght2.clone()));
366
367        let mut test_ght1 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
368        let mut test_ght2 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
369        test_ght1.merge(test_ght2.clone());
370
371        test_ght1.insert(var_expr!(42, 314, 20, "goodbye"));
372        test_ght2.insert(var_expr!(42, 314, 20, "again"));
373
374        // change on merge
375        assert!(test_ght1.merge(test_ght2.clone()));
376        for k in test_ght2.recursive_iter() {
377            assert!(test_ght1.contains(k))
378        }
379    }
380
381    #[test]
382    fn test_node_lattice() {
383        use variadics::var_expr;
384
385        use crate::ght::GeneralizedHashTrieNode;
386        use crate::{GhtType, NaiveLatticeOrd};
387
388        type MyGht = GhtType!(u32, u64 => u16, &'static str: VariadicHashSet);
389        type MyGhtNode = GhtType!(u32, u64 => u16, &'static str: VariadicHashSet);
390
391        let mut test_vec: Vec<MyGhtNode> = Vec::new();
392
393        let empty_ght = MyGht::new_from(vec![]);
394        let test_ght1 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
395        let mut test_ght2 = MyGht::new_from(vec![var_expr!(42, 314, 10, "hello")]);
396        test_ght2.insert(var_expr!(42, 314, 20, "again"));
397        let mut test_ght3 = test_ght2.clone();
398        test_ght3.insert(var_expr!(42, 400, 1, "level 2"));
399        let mut test_ght4 = test_ght3.clone();
400        test_ght4.insert(var_expr!(43, 1, 1, "level 1"));
401
402        let test_vec_wrap = [empty_ght, test_ght1, test_ght2, test_ght3, test_ght4];
403
404        for ght in test_vec_wrap.iter().cloned() {
405            ght.naive_cmp(&ght.clone());
406            test_vec.push(ght);
407        }
408        crate::test::check_all(&test_vec);
409        crate::test::check_all(&test_vec_wrap);
410    }
411
412    #[test]
413    fn test_cartesian_bimorphism() {
414        use variadics::var_expr;
415
416        use crate::ght::GeneralizedHashTrieNode;
417        use crate::ght::lattice::GhtCartesianProductBimorphism;
418        use crate::{GhtType, LatticeBimorphism};
419
420        type MyGhtA = GhtType!(u32, u64 => u16, &'static str: VariadicHashSet);
421        type MyGhtB = GhtType!(u32, u64, u16 => &'static str: VariadicHashSet);
422
423        let mut ght_a = MyGhtA::default();
424        let mut ght_b = MyGhtB::default();
425
426        ght_a.insert(var_expr!(123, 2, 5, "hello"));
427        ght_a.insert(var_expr!(50, 1, 1, "hi"));
428        ght_a.insert(var_expr!(5, 1, 7, "hi"));
429        ght_b.insert(var_expr!(5, 1, 8, "hi"));
430        ght_b.insert(var_expr!(10, 1, 2, "hi"));
431        ght_b.insert(var_expr!(12, 10, 98, "bye"));
432
433        type MyGhtAb = GhtType!(u32, u64, u16, &'static str, u32, u64 => u16, &'static str: VariadicCountedHashSet);
434
435        let mut bim = GhtCartesianProductBimorphism::<MyGhtAb>::default();
436        let ght_out = bim.call(&ght_a, &ght_b);
437        assert_eq!(
438            ght_out.recursive_iter().count(),
439            ght_a.recursive_iter().count() * ght_b.recursive_iter().count()
440        );
441    }
442
443    #[test]
444    fn test_join_bimorphism() {
445        use variadics::variadic_collections::{VariadicCountedHashSet, VariadicHashSet};
446        use variadics::{var_expr, var_type};
447
448        use crate::ght::lattice::{
449            DeepJoinLatticeBimorphism, GhtNodeKeyedBimorphism, GhtValTypeProductBimorphism,
450        };
451        use crate::ght::{GeneralizedHashTrieNode, GhtInner, GhtLeaf};
452        use crate::{GhtType, LatticeBimorphism};
453
454        type ResultSchemaType = var_type!(u32, u64, u16, &'static str, &'static str);
455        type ResultSchemaRefType<'a> = var_type!(
456            &'a u32,
457            &'a u64,
458            &'a u16,
459            &'a &'static str,
460            &'a &'static str
461        );
462        type MyGhtATrie = GhtType!(u32, u64, u16 => &'static str: VariadicHashSet);
463        type MyGhtBTrie = GhtType!(u32, u64, u16 => &'static str: VariadicHashSet);
464
465        let mut ght_a = MyGhtATrie::default();
466        let mut ght_b = MyGhtBTrie::default();
467
468        ght_a.insert(var_expr!(123, 2, 5, "hello"));
469        ght_a.insert(var_expr!(50, 1, 1, "hi"));
470        ght_a.insert(var_expr!(5, 1, 7, "hi"));
471
472        ght_b.insert(var_expr!(5, 1, 8, "hi"));
473        ght_b.insert(var_expr!(5, 1, 7, "world"));
474        ght_b.insert(var_expr!(10, 1, 2, "hi"));
475        ght_b.insert(var_expr!(12, 10, 98, "bye"));
476
477        let result: HashSet<ResultSchemaRefType> = [var_expr!(&5, &1, &7, &"hi", &"world")]
478            .iter()
479            .copied()
480            .collect();
481        {
482            // here we manually construct the proper bimorphism stack.
483            // note that the bottommost bimorphism is GhtValTypeProductBimorphism,
484            // which ensures that the Schema of the resulting output GhtLeaf and GhtInner
485            // nodes correctly includes the key columns, not just the cross-product of the values.
486            type MyGhtOut = GhtInner<
487                &'static str,
488                GhtLeaf<
489                    ResultSchemaType,
490                    var_type!(&'static str),
491                    VariadicCountedHashSet<ResultSchemaType>,
492                >,
493            >;
494            // let mut bim = GhtNodeKeyedBimorphism::new(GhtNodeKeyedBimorphism::new(
495            //     GhtNodeKeyedBimorphism::new(GhtValTypeProductBimorphism::<MyGhtOut>::default()),
496            // ));
497            let mut bim = GhtNodeKeyedBimorphism::new(GhtNodeKeyedBimorphism::new(
498                GhtNodeKeyedBimorphism::new(GhtValTypeProductBimorphism::<MyGhtOut>::default()),
499            ));
500            let out = bim.call(&ght_a, &ght_b);
501            let out: HashSet<ResultSchemaRefType> = out.recursive_iter().collect();
502            assert_eq!(out, result.iter().copied().collect());
503        }
504        {
505            // Here we use DeepJoinLatticeBimorphism as a more compact representation of the
506            // manual stack of bimorphisms above. This is the recommended approach.
507            type MyNodeBim<'a> = <(MyGhtATrie, MyGhtBTrie) as DeepJoinLatticeBimorphism<
508                VariadicHashSet<ResultSchemaType>,
509            >>::DeepJoinLatticeBimorphism;
510            let mut bim = <MyNodeBim as Default>::default();
511            let out = bim.call(&ght_a, &ght_b);
512            let out: HashSet<ResultSchemaRefType> = out.recursive_iter().collect();
513            assert_eq!(out, result.iter().copied().collect());
514        }
515    }
516
517    #[test]
518    fn test_ght_with_tuple_macro() {
519        use variadics::{VariadicExt, var_expr};
520        use variadics_macro::tuple;
521
522        use crate::GhtType;
523        use crate::ght::GeneralizedHashTrieNode;
524
525        type MyRoot = GhtType!(u16, u32 => u64: VariadicCountedHashSet);
526
527        let mut trie1 = MyRoot::default();
528        assert_eq!(3, <<MyRoot as GeneralizedHashTrieNode>::Schema>::LEN);
529        trie1.insert(var_expr!(1, 2, 3));
530        let t = trie1.recursive_iter().next().unwrap();
531        let tup = tuple!(t, 3);
532        assert_eq!(tup, (&1, &2, &3));
533    }
534
535    #[test]
536    fn test_triangle_generic_join() {
537        use std::hash::{BuildHasherDefault, DefaultHasher};
538
539        use variadics::var_expr;
540
541        use crate::GhtType;
542        use crate::ght::{GeneralizedHashTrieNode, GhtPrefixIter};
543
544        const MATCHES: u32 = 1000;
545        type MyGht = GhtType!(u32 => u32: VariadicCountedHashSet);
546
547        let r_iter = (0..MATCHES)
548            .map(|i| (0, i))
549            .chain((1..MATCHES).map(|i| (i, 0)));
550
551        let s_iter = (0..MATCHES)
552            .map(|i| (0, i))
553            .chain((1..MATCHES).map(|i| (i, 0)));
554
555        let t_iter = (0..MATCHES)
556            .map(|i| (0, i))
557            .chain((1..MATCHES).map(|i| (i, 0)));
558
559        let rx_ght = MyGht::new_from(r_iter.clone().map(|(x, y)| var_expr!(x, y)));
560        let sb_ght = MyGht::new_from(s_iter.clone().map(|(y, b)| var_expr!(b, y)));
561        let tx_ght = MyGht::new_from(t_iter.clone().map(|(z, x)| var_expr!(x, z)));
562
563        let r_x = r_iter
564            .clone()
565            .map(|(x, _y)| x)
566            .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
567        let t_x = s_iter
568            .clone()
569            .map(|(_z, x)| x)
570            .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
571        let x_inter = r_x.intersection(&t_x);
572        let len = x_inter.clone().count();
573        if len > 1 {
574            assert_eq!(1000, len);
575        }
576
577        let mut output: Vec<(u32, u32, u32)> = Vec::new();
578        let mut x_iters = 0usize;
579        let mut y_iters = 0usize;
580        let mut z_iters = 0usize;
581        for a in x_inter {
582            x_iters += 1;
583            let r = rx_ght
584                .prefix_iter(var_expr!(a))
585                .map(|(_x, (y, ()))| *y)
586                .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
587            let s_y = s_iter
588                .clone()
589                .map(|(y, _z)| y)
590                .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
591            let y_inter = r.intersection(&s_y);
592            let len = y_inter.clone().count();
593            if len > 1 {
594                assert_eq!(1000, len);
595            }
596            for b in y_inter {
597                y_iters += 1;
598                let s = sb_ght
599                    .prefix_iter(var_expr!(b))
600                    .map(|(_b, (z, ()))| *z)
601                    .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
602                let t = tx_ght
603                    .prefix_iter(var_expr!(a))
604                    .map(|(_x, (z, ()))| *z)
605                    .collect::<HashSet<_, BuildHasherDefault<DefaultHasher>>>();
606                let z_inter = s.intersection(&t);
607                let len = z_inter.clone().count();
608                if len > 1 {
609                    assert_eq!(1000, len);
610                }
611                for c in z_inter {
612                    z_iters += 1;
613                    output.push((*a, *b, *c));
614                }
615            }
616        }
617
618        assert_eq!(1000, x_iters);
619        assert_eq!(1999, y_iters);
620        assert_eq!(2998, z_iters);
621        assert_eq!(2998, output.len());
622    }
623
624    fn clover_setup(
625        matches: usize,
626    ) -> (
627        impl Iterator<Item = (u32, u32)>,
628        impl Iterator<Item = (u32, u32)>,
629        impl Iterator<Item = (u32, u32)>,
630    ) {
631        let r_iter = (1..matches)
632            .map(|i| (1u32, i as u32))
633            .chain((1..matches).map(|i| (2, i as u32)))
634            .chain([(0, 0)]);
635
636        let s_iter = (1..matches)
637            .map(|i| (2u32, i as u32))
638            .chain((1..matches).map(|i| (3, i as u32)))
639            .chain([(0, 0)]);
640
641        let t_iter = (1..matches)
642            .map(|i| (3u32, i as u32))
643            .chain((1..matches).map(|i| (1, i as u32)))
644            .chain([(0, 0)]);
645        (r_iter, s_iter, t_iter)
646    }
647
648    #[test]
649    fn clover_generic_join() {
650        use variadics::var_expr;
651
652        use crate::GhtType;
653        use crate::ght::{GeneralizedHashTrieNode, GhtGet};
654
655        const MATCHES: usize = 1000;
656        let (r_iter, s_iter, t_iter) = clover_setup(MATCHES);
657
658        type MyGht = GhtType!(u32 => u32: VariadicCountedHashSet);
659        let rx_ght = MyGht::new_from(r_iter.map(|(x, a)| var_expr!(x, a)));
660        let sx_ght = MyGht::new_from(s_iter.map(|(x, b)| var_expr!(x, b)));
661        let tx_ght = MyGht::new_from(t_iter.map(|(x, c)| var_expr!(x, c)));
662        for x in rx_ght.iter() {
663            if let (Some(r), Some(s), Some(t)) = (rx_ght.get(&x), sx_ght.get(&x), tx_ght.get(&x)) {
664                // All unwraps succeeded, use `r`, `s`, `t` here
665                for a in r.iter() {
666                    for b in s.iter() {
667                        for c in t.iter() {
668                            assert_eq!((x, a, b, c), (0, 0, 0, 0));
669                        }
670                    }
671                }
672            } else {
673                // If any unwrap fails, continue to the next iteration
674                continue;
675            }
676        }
677    }
678
679    #[test]
680    fn clover_factorized_join() {
681        use variadics::var_expr;
682
683        use crate::GhtType;
684        use crate::ght::{GeneralizedHashTrieNode, GhtGet};
685
686        const MATCHES: usize = 1000;
687        let (r_iter, s_iter, t_iter) = clover_setup(MATCHES);
688
689        type Ght1 = GhtType!(() => u32, u32: VariadicCountedHashSet);
690        type Ght2 = GhtType!(u32 => u32: VariadicCountedHashSet);
691        let rx_ght = Ght1::new_from(r_iter.map(|(x, a)| var_expr!(x, a)));
692        let sx_ght = Ght2::new_from(s_iter.map(|(x, b)| var_expr!(x, b)));
693        let tx_ght = Ght2::new_from(t_iter.map(|(x, c)| var_expr!(x, c)));
694
695        for t in rx_ght.recursive_iter() {
696            let (x, (a, ())): (&u32, (&u32, _)) = t;
697            if let (Some(s), Some(t)) = (sx_ght.get(x), tx_ght.get(x)) {
698                // All unwraps succeeded, use `s`, `t` here
699                for b in s.iter() {
700                    for c in t.iter() {
701                        assert_eq!((x, a, b, c), (&0, &0, 0, 0));
702                    }
703                }
704            } else {
705                // If any unwrap fails, continue to the next iteration
706                continue;
707            }
708        }
709    }
710
711    #[test]
712    fn test_force() {
713        use variadics::var_expr;
714
715        use crate::GhtType;
716        use crate::ght::GeneralizedHashTrieNode;
717        use crate::ght::colt::ColtForestNode;
718
719        type LeafType = GhtType!(() => u16, u32, u64: VariadicCountedHashSet);
720        let n = LeafType::new_from(vec![
721            var_expr!(1, 1, 1),
722            var_expr!(1, 2, 2),
723            var_expr!(1, 3, 3),
724            var_expr!(2, 4, 4),
725        ]);
726        let out = n.force().unwrap();
727        assert_eq!(out.height(), 1);
728    }
729
730    #[test]
731    fn test_forest_macro() {
732        use crate::ColtType;
733
734        type Forest4 = ColtType!(u8, u16, u32, u64);
735        let _f4 = Forest4::default();
736
737        type Forest3 = ColtType!(u8, u16, u32);
738        let _f3 = Forest3::default();
739
740        type Forest2 = ColtType!(u8, u16);
741        let _f2 = Forest2::default();
742
743        type Forest1 = ColtType!(u8);
744        let _f2 = Forest1::default();
745
746        type Forest01 = ColtType!(() => u16);
747        let _f01 = Forest01::default();
748
749        type Forest02 = ColtType!(() => u8, u16);
750        let _f02 = Forest02::default();
751
752        type Forest10 = ColtType!(u8 => ());
753        let _f10 = Forest10::default();
754
755        type Forest11 = ColtType!(u8 => u16);
756        let _f11 = Forest11::default();
757
758        type Forest12 = ColtType!(u8 => u16, u32);
759        let _f12 = Forest12::default();
760
761        type Forest20 = ColtType!(u8, u16 => ());
762        let _f20 = Forest20::default();
763
764        type Forest21 = ColtType!(u8, u16 => u32);
765        let _f21 = Forest21::default();
766
767        type Forest22 = ColtType!(u8, u16 => u32, u64);
768        let _f22 = Forest22::default();
769    }
770
771    #[test]
772    fn test_colt_little_get() {
773        use variadics::variadic_collections::VariadicCollection;
774        use variadics::{VariadicExt, var_expr};
775
776        use crate::ColtType;
777        use crate::ght::GeneralizedHashTrieNode;
778        use crate::ght::colt::ColtGet;
779
780        type MyForest = ColtType!(u8);
781
782        let mut forest = MyForest::default();
783
784        forest.0.insert(var_expr!(1));
785        forest.0.insert(var_expr!(2));
786        forest.0.insert(var_expr!(3));
787
788        assert_eq!(2, forest.len());
789        assert_eq!(3, forest.0.elements.len());
790
791        let result = ColtGet::get(forest.as_mut_var(), &3);
792        assert_eq!(1, result.len());
793        assert_eq!(0, forest.0.elements.len());
794        assert!(forest.0.forced);
795    }
796
797    #[test]
798    fn test_colt_get() {
799        use variadics::variadic_collections::VariadicCollection;
800        use variadics::{VariadicExt, var_expr};
801
802        use crate::ColtType;
803        use crate::ght::colt::ColtGet;
804        use crate::ght::{GeneralizedHashTrieNode, GhtGet};
805
806        type MyForest = ColtType!(u8, u16, u32, u64);
807        let mut forest = MyForest::default();
808        forest.0.insert(var_expr!(1, 1, 1, 1));
809        forest.0.insert(var_expr!(2, 2, 2, 2));
810        forest.0.insert(var_expr!(3, 3, 3, 3));
811
812        let len = forest.len();
813        assert_eq!(5, len);
814        {
815            let get_result = ColtGet::get(forest.as_mut_var(), &1);
816            assert_eq!(get_result.len(), len - 1);
817            assert_eq!(get_result.0.height(), 0);
818            let get_result2 = ColtGet::get(get_result, &1);
819            assert_eq!(get_result2.len(), len - 2);
820            let get_result3 = ColtGet::get(get_result2, &1);
821            assert_eq!(get_result3.len(), len - 3);
822            assert_eq!(
823                get_result3.0.elements.iter().next(),
824                Some(var_expr!(1, 1, 1, 1).as_ref_var())
825            );
826            assert_eq!(get_result3.1.0.children.len(), 0);
827        }
828        {
829            let get_result = ColtGet::get(forest.as_mut_var(), &3);
830            assert_eq!(get_result.len(), len - 1);
831            let get_result2 = ColtGet::get(get_result, &3);
832            assert_eq!(get_result2.len(), len - 2);
833            assert_eq!(
834                get_result2.0.elements.iter().next(),
835                Some(var_expr!(3, 3, 3, 3).as_ref_var())
836            );
837            assert_eq!(get_result2.1.0.children.len(), 0);
838        }
839        assert!(forest.0.forced);
840        assert_eq!(3, forest.1.0.children.len()); // keys 1, 2 and 3
841        assert_eq!(0, forest.1.0.get(&1).unwrap().elements.len());
842        assert_eq!(1, forest.1.0.get(&2).unwrap().elements.len());
843        assert_eq!(0, forest.1.0.get(&3).unwrap().elements.len());
844        assert_eq!(2, forest.1.1.0.children.len()); // keys 1 and 3
845        assert_eq!(
846            0,
847            forest
848                .1
849                .1
850                .0
851                .get(&1)
852                .unwrap()
853                .get(&1)
854                .unwrap()
855                .elements
856                .len()
857        );
858        assert!(forest.1.1.0.get(&2).is_none());
859        assert_eq!(
860            1,
861            forest
862                .1
863                .1
864                .0
865                .get(&3)
866                .unwrap()
867                .get(&3)
868                .unwrap()
869                .elements
870                .len()
871        );
872        assert_eq!(
873            1,
874            forest
875                .1
876                .1
877                .1
878                .0
879                .get(&1)
880                .unwrap()
881                .get(&1)
882                .unwrap()
883                .get(&1)
884                .unwrap()
885                .elements
886                .len()
887        );
888    }
889
890    #[test]
891    fn test_colt_scale() {
892        use variadics::variadic_collections::VariadicCollection;
893        use variadics::{VariadicExt, var_expr};
894
895        use crate::ght::colt::ColtGet;
896        use crate::ght::{GeneralizedHashTrieNode, GhtPrefixIter};
897
898        type MyColt = crate::ColtType!(i32, bool, usize, &'static str);
899        let mut forest = MyColt::default();
900        for i in 1..100000 {
901            forest.0.insert(var_expr!(i, true, 1, "hello"));
902        }
903        {
904            let result = forest.as_mut_var().get(&3);
905            assert_eq!(result.len(), 4);
906        }
907        // check: first Leaf trie is forced
908        assert!(forest.0.forced);
909        assert_eq!(forest.0.elements.len(), 0);
910        {
911            let result = forest.as_mut_var().get(&3);
912            let result2 = result.get(&true);
913            assert_eq!(result2.len(), 3);
914        }
915        {
916            // check: leaf below 3 in first non-empty trie is forced
917            let result = forest.as_mut_var().get(&3);
918            assert!(result.0.forced);
919            assert_eq!(result.0.elements.len(), 0);
920        }
921        // check: prefix (3, true) is now found in the third trie: forest.1.1.0
922        assert!(
923            forest
924                .1
925                .1
926                .0
927                .prefix_iter(var_expr!(3, true).as_ref_var())
928                .next()
929                .is_some()
930        );
931        {
932            let result = forest.as_mut_var().get(&3);
933            let result2 = result.get(&true);
934            assert_eq!(result2.len(), 3);
935            let result3 = result2.get(&1);
936            assert_eq!(result3.len(), 2);
937            let result4 = result3.get(&"hello");
938            assert_eq!(result4.0.elements.len(), 1);
939            assert_eq!(
940                result4.0.elements.iter().next(),
941                Some(var_expr!(3, true, 1, "hello").as_ref_var())
942            );
943        }
944    }
945}
lattices/ght/test.rs

lattices/ght/
test.rs
