lattices/ght/
lattice.rs

Help
1//! Lattice traits for GHT
2
3use core::cmp::Ordering::{Equal, Greater, Less};
4use std::cmp::Ordering;
5use std::collections::HashMap;
6use std::hash::Hash;
7
8use variadics::variadic_collections::VariadicSet;
9use variadics::{CloneVariadic, PartialEqVariadic, SplitBySuffix, VariadicExt, var_expr, var_type};
10
11use crate::ght::{GeneralizedHashTrieNode, GhtGet, GhtInner, GhtLeaf};
12use crate::{IsBot, IsTop, LatticeBimorphism, LatticeOrd, Merge};
13
14impl<Head, Node> Merge<GhtInner<Head, Node>> for GhtInner<Head, Node>
15where
16    Node: GeneralizedHashTrieNode + Merge<Node>,
17    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
18    Self: GeneralizedHashTrieNode,
19    Head: Hash + Eq + Clone,
20{
21    fn merge(&mut self, other: GhtInner<Head, Node>) -> bool {
22        let mut changed = false;
23
24        for (k, v) in other.children {
25            match self.children.entry(k) {
26                std::collections::hash_map::Entry::Occupied(mut occupied) => {
27                    changed |= occupied.get_mut().merge_node(v);
28                }
29                std::collections::hash_map::Entry::Vacant(vacant) => {
30                    vacant.insert(v);
31                    changed = true;
32                }
33            }
34        }
35        changed
36    }
37}
38
39impl<Schema, ValType, Storage> Merge<GhtLeaf<Schema, ValType, Storage>>
40    for GhtLeaf<Schema, ValType, Storage>
41where
42    Schema: Eq + Hash,
43    Storage: VariadicSet<Schema = Schema> + Extend<Schema> + IntoIterator<Item = Schema>,
44{
45    fn merge(&mut self, other: GhtLeaf<Schema, ValType, Storage>) -> bool {
46        let old_len = self.elements.len();
47        self.elements.extend(other.elements);
48        self.elements.len() > old_len
49    }
50}
51
52impl<Head, Node> PartialEq<GhtInner<Head, Node>> for GhtInner<Head, Node>
53where
54    Head: Hash + Eq + 'static + Clone,
55    Node: GeneralizedHashTrieNode + 'static + PartialEq,
56    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
57    Node::Schema: SplitBySuffix<var_type!(Head, ...Node::SuffixSchema)>,
58    GhtInner<Head, Node>: GhtGet,
59    <GhtInner<Head, Node> as GhtGet>::Get: PartialEq,
60{
61    fn eq(&self, other: &GhtInner<Head, Node>) -> bool {
62        if self.children.len() != other.children.len() {
63            return false;
64        }
65
66        for head in self.iter() {
67            let other_node = other.get(&head);
68            if other_node.is_none() {
69                return false;
70            }
71            let this_node = self.get(&head);
72            if this_node.is_none() {
73                return false;
74            }
75            if this_node.unwrap() != other_node.unwrap() {
76                return false;
77            }
78        }
79        true
80    }
81}
82
83impl<Head, Node> PartialOrd<GhtInner<Head, Node>> for GhtInner<Head, Node>
84where
85    Head: Hash + Eq + 'static + Clone,
86    Node: 'static + GeneralizedHashTrieNode + PartialEq + PartialOrd,
87    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
88    Node::Schema: SplitBySuffix<var_type!(Head, ...Node::SuffixSchema)>,
89{
90    fn partial_cmp(&self, other: &GhtInner<Head, Node>) -> Option<Ordering> {
91        let mut self_any_greater = false;
92        let mut other_any_greater = false;
93        if self.children.is_empty() && other.children.is_empty() {
94            Some(Equal)
95        } else {
96            for k in self.children.keys().chain(other.children.keys()) {
97                match (self.children.get(k), other.children.get(k)) {
98                    (Some(self_value), Some(other_value)) => {
99                        match self_value.partial_cmp(other_value)? {
100                            Greater => {
101                                self_any_greater = true;
102                            }
103                            Less => {
104                                other_any_greater = true;
105                            }
106                            Equal => {}
107                        }
108                    }
109                    (Some(_), None) => {
110                        self_any_greater = true;
111                    }
112                    (None, Some(_)) => {
113                        other_any_greater = true;
114                    }
115                    (None, None) => unreachable!(),
116                }
117            }
118            match (self_any_greater, other_any_greater) {
119                (true, false) => Some(Greater),
120                (false, true) => Some(Less),
121                (false, false) => Some(Equal),
122                (true, true) => unreachable!(),
123            }
124        }
125    }
126}
127
128impl<Schema, SuffixSchema, Storage> PartialOrd<GhtLeaf<Schema, SuffixSchema, Storage>>
129    for GhtLeaf<Schema, SuffixSchema, Storage>
130where
131    Schema: Eq + Hash + PartialEqVariadic,
132    SuffixSchema: Eq + Hash,
133    Storage: VariadicSet<Schema = Schema> + PartialEq,
134{
135    fn partial_cmp(&self, other: &GhtLeaf<Schema, SuffixSchema, Storage>) -> Option<Ordering> {
136        match self.elements.len().cmp(&other.elements.len()) {
137            Greater => {
138                if other.elements.iter().all(|tup| self.elements.contains(tup)) {
139                    Some(Greater)
140                } else {
141                    None
142                }
143            }
144            Equal => {
145                if self
146                    .elements
147                    .iter()
148                    .all(|head| other.elements.contains(head))
149                {
150                    Some(Equal)
151                } else {
152                    None
153                }
154            }
155            Less => {
156                if self
157                    .elements
158                    .iter()
159                    .all(|head| other.elements.contains(head))
160                {
161                    Some(Less)
162                } else {
163                    None
164                }
165            }
166        }
167    }
168}
169
170impl<Head, Node> LatticeOrd<GhtInner<Head, Node>> for GhtInner<Head, Node>
171where
172    Self: PartialOrd<GhtInner<Head, Node>>,
173    Head: Clone,
174    Node: GeneralizedHashTrieNode,
175    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
176{
177}
178impl<Schema, SuffixSchema, Storage> LatticeOrd<GhtLeaf<Schema, SuffixSchema, Storage>>
179    for GhtLeaf<Schema, SuffixSchema, Storage>
180where
181    Schema: Eq + Hash + PartialEqVariadic,
182    SuffixSchema: Eq + Hash,
183    Storage: VariadicSet<Schema = Schema> + PartialEq,
184{
185}
186
187impl<Head, Node> IsBot for GhtInner<Head, Node>
188where
189    Head: Clone,
190    Node: GeneralizedHashTrieNode + IsBot,
191{
192    fn is_bot(&self) -> bool {
193        self.children.iter().all(|(_, v)| v.is_bot())
194    }
195}
196
197impl<Schema, SuffixSchema, Storage> IsBot for GhtLeaf<Schema, SuffixSchema, Storage>
198where
199    Schema: Eq + Hash,
200    SuffixSchema: Eq + Hash,
201    Storage: VariadicSet<Schema = Schema>,
202{
203    fn is_bot(&self) -> bool {
204        self.elements.is_empty()
205    }
206}
207
208impl<Head, Node> IsTop for GhtInner<Head, Node>
209where
210    Head: Clone,
211    Node: GeneralizedHashTrieNode,
212    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
213{
214    fn is_top(&self) -> bool {
215        false
216    }
217}
218
219impl<Schema, SuffixSchema, Storage> IsTop for GhtLeaf<Schema, SuffixSchema, Storage>
220where
221    Schema: Eq + Hash,
222    SuffixSchema: Eq + Hash,
223    Storage: VariadicSet<Schema = Schema>,
224{
225    fn is_top(&self) -> bool {
226        false
227    }
228}
229
230//////////////////////////
231// BiMorphisms for GHT
232//
233
234/// Bimorphism for the cartesian product of two GHT *subtries*.
235///
236/// Output is a set of all possible pairs of
237/// *suffixes* from the two subtries. If you use this at the root of a GHT, it's a full cross-product.
238/// If you use this at an internal node, it provides a 'factorized' representation with only the suffix
239/// cross-products expanded.
240pub struct GhtCartesianProductBimorphism<GhtOut> {
241    _phantom: std::marker::PhantomData<fn() -> GhtOut>,
242}
243impl<GhtOut> Default for GhtCartesianProductBimorphism<GhtOut> {
244    fn default() -> Self {
245        Self {
246            _phantom: Default::default(),
247        }
248    }
249}
250impl<'a, 'b, GhtA, GhtB, GhtOut> LatticeBimorphism<&'a GhtA, &'b GhtB>
251    for GhtCartesianProductBimorphism<GhtOut>
252where
253    GhtA: GeneralizedHashTrieNode,
254    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
255    GhtB: GeneralizedHashTrieNode,
256    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
257    GhtOut: FromIterator<var_type!(...GhtA::SuffixSchema, ...GhtB::SuffixSchema)>,
258    GhtA::SuffixSchema: CloneVariadic,
259    GhtB::SuffixSchema: CloneVariadic,
260{
261    type Output = GhtOut;
262
263    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
264        ght_a.recursive_iter().flat_map(|a| {
265            let (_a_prefix, a_suffix) = <GhtA::Schema as SplitBySuffix<GhtA::SuffixSchema>>::split_by_suffix_ref(a);
266            ght_b
267                .recursive_iter()
268                .map(move |b| {
269                    let (_b_prefix, b_suffix) = <GhtB::Schema as SplitBySuffix<GhtB::SuffixSchema>>::split_by_suffix_ref(b);
270                    var_expr!(...<GhtA::SuffixSchema as CloneVariadic>::clone_ref_var(a_suffix), ...<GhtB::SuffixSchema as CloneVariadic>::clone_ref_var(b_suffix))
271                })
272        }).collect()
273    }
274}
275
276/// Forms the cartesian product of the ValTypes only
277/// Used on GhtLeaf nodes to implement DeepJoinLatticeBimorphism
278pub struct GhtValTypeProductBimorphism<GhtOut> {
279    _phantom: std::marker::PhantomData<fn() -> GhtOut>,
280}
281impl<GhtOut> Default for GhtValTypeProductBimorphism<GhtOut> {
282    fn default() -> Self {
283        Self {
284            _phantom: Default::default(),
285        }
286    }
287}
288impl<'a, 'b, GhtA, GhtB, GhtOut> LatticeBimorphism<&'a GhtA, &'b GhtB>
289    for GhtValTypeProductBimorphism<GhtOut>
290where
291    GhtA: GeneralizedHashTrieNode,
292    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
293    GhtB: GeneralizedHashTrieNode,
294    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
295    GhtOut: FromIterator<var_type!(...GhtA::Schema, ...GhtB::ValType)>,
296    GhtA::Schema: Eq + Hash + CloneVariadic,
297    GhtB::Schema: Eq + Hash + SplitBySuffix<GhtB::ValType>,
298    GhtB::ValType: CloneVariadic,
299{
300    type Output = GhtOut;
301
302    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
303        ght_a.recursive_iter().flat_map(|a| {
304            ght_b
305                .recursive_iter()
306                .map(move |b| {
307                    let (_prefix_b, suffix_b)
308                        = <GhtB::Schema as SplitBySuffix<GhtB::ValType>>::split_by_suffix_ref(b);
309                    var_expr!(...<GhtA::Schema as CloneVariadic>::clone_ref_var(a), ...<GhtB::ValType as CloneVariadic>::clone_ref_var(suffix_b))
310                }
311            )
312        }).collect()
313    }
314}
315
316/// Composable bimorphism, wraps an existing morphism by partitioning it per key.
317///
318/// For example, `GhtKeyedBimorphism<..., GhtCartesianProduct<...>>` is a join.
319#[derive(Default)]
320pub struct GhtBimorphism<Bimorphism> {
321    bimorphism: Bimorphism,
322    // _phantom: std::marker::PhantomData<fn() -> MapOut>,
323}
324impl<Bimorphism> GhtBimorphism<Bimorphism> {
325    /// Create a `KeyedBimorphism` using `bimorphism` for handling values.
326    pub fn new(bimorphism: Bimorphism) -> Self {
327        Self {
328            bimorphism,
329            // _phantom: std::marker::PhantomData,
330        }
331    }
332}
333
334impl<GhtA, GhtB, ValFunc, GhtOut> LatticeBimorphism<GhtA, GhtB> for GhtBimorphism<ValFunc>
335where
336    GhtA: GeneralizedHashTrieNode,
337    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
338    GhtB: GeneralizedHashTrieNode,
339    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
340    GhtOut: GeneralizedHashTrieNode, // FromIterator<var_type!(...GhtA::Schema, ...GhtB::ValType)>,
341    for<'a, 'b> ValFunc: LatticeBimorphism<&'a GhtA, &'b GhtB, Output = GhtOut>,
342{
343    type Output = GhtOut;
344
345    fn call(&mut self, ght_a: GhtA, ght_b: GhtB) -> Self::Output {
346        let node_bim = &mut self.bimorphism; // GhtNodeKeyedBimorphism::<ValFunc>::new(self.bimorphism);
347        node_bim.call(&ght_a, &ght_b)
348    }
349}
350
351#[derive(Default)]
352/// bimorphism trait for equijoining Ght Nodes
353pub struct GhtNodeKeyedBimorphism<Bimorphism> {
354    bimorphism: Bimorphism,
355}
356/// bimorphism implementation for equijoining Ght Nodes
357impl<Bimorphism> GhtNodeKeyedBimorphism<Bimorphism> {
358    /// initialize bimorphism
359    pub fn new(bimorphism: Bimorphism) -> Self {
360        Self { bimorphism }
361    }
362}
363/// bimorphism implementation for equijoining Ght Nodes
364impl<'a, 'b, Head, GhtA, GhtB, ValFunc> LatticeBimorphism<&'a GhtA, &'b GhtB>
365    for GhtNodeKeyedBimorphism<ValFunc>
366where
367    Head: Clone + Hash + Eq,
368    ValFunc: LatticeBimorphism<&'a GhtA::Get, &'b GhtB::Get>,
369    ValFunc::Output: GeneralizedHashTrieNode,
370    GhtA: GeneralizedHashTrieNode<Head = Head> + GhtGet,
371    GhtB: GeneralizedHashTrieNode<Head = Head, Schema = GhtA::Schema> + GhtGet,
372    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
373    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
374    <GhtA::SuffixSchema as VariadicExt>::AsRefVar<'a>: CloneVariadic,
375    <GhtB::SuffixSchema as VariadicExt>::AsRefVar<'b>: CloneVariadic,
376{
377    type Output = GhtInner<Head, ValFunc::Output>; // HashMap<Head, ValFunc::Output>; // GhtOut;
378
379    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
380        let mut children = HashMap::<Head, ValFunc::Output>::new();
381        // for head in ght_b.iter_keys() {
382        for head in ght_b.iter() {
383            if let Some(get_a) = ght_a.get(&head) {
384                let get_b = ght_b.get(&head).unwrap();
385                let val = self.bimorphism.call(get_a, get_b);
386                children.insert(head.clone(), val);
387            }
388        }
389        GhtInner { children }
390    }
391}
392
393/// bimorphism trait for equijoin on full tuple (keys in all GhtInner nodes)
394pub trait DeepJoinLatticeBimorphism<Storage> {
395    /// bimorphism type for equijoin on full tuple (keys in all GhtInner nodes)
396    type DeepJoinLatticeBimorphism;
397}
398/// bimorphism implementation for equijoin on full tuple (keys in all GhtInner nodes)
399impl<Head, NodeA, NodeB, Storage> DeepJoinLatticeBimorphism<Storage>
400    for (GhtInner<Head, NodeA>, GhtInner<Head, NodeB>)
401where
402    Head: 'static + Hash + Eq + Clone,
403    NodeA: 'static + GeneralizedHashTrieNode,
404    NodeB: 'static + GeneralizedHashTrieNode,
405    NodeA::Storage: VariadicSet<Schema = NodeA::Schema>, // multiset is not a lattice!
406    NodeB::Storage: VariadicSet<Schema = NodeB::Schema>, // multiset is not a lattice!
407    (NodeA, NodeB): DeepJoinLatticeBimorphism<Storage>,
408    Storage: VariadicSet<Schema = var_type!(...NodeA::Schema, ...NodeB::ValType)>,
409{
410    type DeepJoinLatticeBimorphism = GhtNodeKeyedBimorphism<
411        <(NodeA, NodeB) as DeepJoinLatticeBimorphism<Storage>>::DeepJoinLatticeBimorphism,
412    >;
413}
414impl<SchemaA, ValTypeA, StorageA, SchemaB, ValTypeB, StorageB, StorageOut>
415    DeepJoinLatticeBimorphism<StorageOut>
416    for (
417        GhtLeaf<SchemaA, ValTypeA, StorageA>,
418        GhtLeaf<SchemaB, ValTypeB, StorageB>,
419    )
420where
421    SchemaA: 'static + VariadicExt + Eq + Hash + SplitBySuffix<ValTypeA>, /* + AsRefVariadicPartialEq */
422    ValTypeA: 'static + VariadicExt + Eq + Hash, // + AsRefVariadicPartialEq
423    SchemaB: 'static + VariadicExt + Eq + Hash + SplitBySuffix<ValTypeB>, /* + AsRefVariadicPartialEq */
424    ValTypeB: 'static + VariadicExt + Eq + Hash, // + AsRefVariadicPartialEq
425    StorageA: VariadicSet<Schema = SchemaA>,
426    StorageB: VariadicSet<Schema = SchemaB>,
427    StorageOut: VariadicSet<Schema = var_type!(...SchemaA, ...ValTypeB)>,
428    for<'x> SchemaA::AsRefVar<'x>: CloneVariadic,
429    for<'x> SchemaB::AsRefVar<'x>: CloneVariadic,
430    var_type!(...SchemaA, ...ValTypeB): Eq + Hash,
431{
432    type DeepJoinLatticeBimorphism = GhtValTypeProductBimorphism<
433        GhtLeaf<
434            var_type!(...SchemaA, ...ValTypeB),
435            var_type!(...ValTypeA, ...ValTypeB),
436            StorageOut,
437        >,
438    >;
439}
lattices/ght/lattice.rs

lattices/ght/
lattice.rs
