kanata_parser/
subset.rs

1//! Collection where keys are slices of a type, and supports a get operation to check if the key
2//! exists, is a subset of any existing key, or is neither of the aforementioned cases.
3//!
4//! In the underlying structure the value is cloned for each participating member of slice key, so
5//! you should ensure values are cheaply clonable. If the value is not, consider putting it inside
6//! `Rc` or `Arc`.
7
8use rustc_hash::FxHashMap;
9use std::hash::Hash;
10
11#[derive(Debug, Clone)]
12pub struct SubsetMap<K, V> {
13    map: FxHashMap<K, Vec<SsmKeyValue<K, V>>>,
14}
15
16#[derive(Debug, Clone)]
17struct SsmKeyValue<K, V> {
18    key: Box<[K]>,
19    value: V,
20}
21
22impl<K, V> SsmKeyValue<K, V>
23where
24    K: Clone,
25{
26    fn ssmkv_new(key: impl AsRef<[K]>, value: V) -> Self {
27        Self {
28            key: key.as_ref().to_vec().into_boxed_slice(),
29            value,
30        }
31    }
32}
33
34#[derive(Debug, Copy, Clone, PartialEq, Eq)]
35pub enum GetOrIsSubsetOfKnownKey<T> {
36    HasValue(T),
37    IsSubset,
38    Neither,
39}
40
41#[derive(Debug, Copy, Clone, PartialEq, Eq)]
42pub enum SsmKeyExistedBeforeInsert {
43    Existed,
44    NotThere,
45}
46
47use GetOrIsSubsetOfKnownKey::*;
48
49impl<K, V> Default for SubsetMap<K, V>
50where
51    K: Clone + PartialEq + Ord + Hash,
52    V: Clone,
53{
54    fn default() -> Self {
55        Self::ssm_new()
56    }
57}
58
59impl<K, V> SubsetMap<K, V>
60where
61    K: Clone + PartialEq + Ord + Hash,
62    V: Clone,
63{
64    pub fn ssm_new() -> Self {
65        Self {
66            map: FxHashMap::default(),
67        }
68    }
69
70    /// Inserts a potentially unsorted key. Sorts the key and then calls ssm_insert_ksorted.
71    pub fn ssm_insert(&mut self, mut key: impl AsMut<[K]>, val: V) -> SsmKeyExistedBeforeInsert {
72        key.as_mut().sort();
73        self.ssm_insert_ksorted(key.as_mut(), val)
74    }
75
76    /// Inserts a sorted key. Failure to enforce that the key is sorted results in defined but
77    /// unspecified behaviour.
78    pub fn ssm_insert_ksorted(
79        &mut self,
80        key: impl AsRef<[K]>,
81        val: V,
82    ) -> SsmKeyExistedBeforeInsert {
83        let mut key_existed = SsmKeyExistedBeforeInsert::NotThere;
84        for k in key.as_ref().iter().cloned() {
85            let keyvals_for_key_item = self.map.entry(k).or_default();
86            match keyvals_for_key_item
87                .binary_search_by(|probe| probe.key.as_ref().cmp(key.as_ref()))
88            {
89                Ok(pos) => {
90                    key_existed = SsmKeyExistedBeforeInsert::Existed;
91                    keyvals_for_key_item[pos] = SsmKeyValue::ssmkv_new(key.as_ref(), val.clone());
92                }
93                Err(pos) => {
94                    keyvals_for_key_item
95                        .insert(pos, SsmKeyValue::ssmkv_new(key.as_ref(), val.clone()));
96                }
97            }
98        }
99        key_existed
100    }
101
102    /// Gets using a potentially unsorted key. Sorts the key then calls
103    /// ssm_get_or_is_subset_ksorted.
104    pub fn ssm_get_or_is_subset(&self, mut key: impl AsMut<[K]>) -> GetOrIsSubsetOfKnownKey<V> {
105        key.as_mut().sort();
106        self.ssm_get_or_is_subset_ksorted(key.as_mut())
107    }
108
109    /// Gets using a sorted key. Failure to enforce a sorted key results in defined but unspecified
110    /// behaviour.
111    pub fn ssm_get_or_is_subset_ksorted(
112        &self,
113        get_key: impl AsRef<[K]>,
114    ) -> GetOrIsSubsetOfKnownKey<V> {
115        let get_key = get_key.as_ref();
116        if get_key.is_empty() {
117            return match self.is_empty() {
118                true => Neither,
119                false => IsSubset,
120            };
121        }
122        match self.map.get(&get_key[0]) {
123            None => Neither,
124            Some(keyvals_for_key_item) => {
125                match keyvals_for_key_item
126                    .binary_search_by(|probe| probe.key.as_ref().cmp(get_key.as_ref()))
127                {
128                    Ok(pos) => HasValue(keyvals_for_key_item[pos].value.clone()),
129                    Err(_) => {
130                        for kv in keyvals_for_key_item.iter() {
131                            if get_key.iter().all(|kitem| kv.key.contains(kitem)) {
132                                return IsSubset;
133                            }
134                        }
135                        Neither
136                    }
137                }
138            }
139        }
140    }
141
142    pub fn is_empty(&self) -> bool {
143        self.map.is_empty()
144    }
145}
kanata_parser/subset.rs

kanata_parser/
subset.rs
