hara_native/lang/data/
ordered_map.rs

1use std::cell::Cell;
2use std::hash::Hash;
3
4use crate::lang::data::{Map, Vector};
5use crate::lang::hash::JavaHash;
6use crate::lang::protocol::{
7    HashType, IAssoc, IColl, IConj, ICount, IDisplay, IDissoc, IEmpty, IEquality, IFind, IHash,
8    ILookup, IMetadata, IMutable, INth, IObjType, IPersistent, IToMutable, IToPersistent, MetaType,
9    ObjType,
10};
11
12const COMPACT_MINIMUM: usize = 32;
13
14#[derive(Debug, Clone)]
15pub struct Standard<K, V> {
16    lookup: Map<K, (usize, V)>,
17    order: Vector<Option<(K, V)>>,
18}
19
20impl<K: Clone + Eq + Hash, V: Clone> Default for Standard<K, V> {
21    fn default() -> Self {
22        Self {
23            lookup: Map::new(),
24            order: Vector::new(),
25        }
26    }
27}
28
29impl<K: Clone + Eq + Hash, V: Clone> Standard<K, V> {
30    pub fn new() -> Self {
31        Self::default()
32    }
33    pub fn len(&self) -> usize {
34        self.lookup.len()
35    }
36    pub fn is_empty(&self) -> bool {
37        self.lookup.is_empty()
38    }
39    pub fn get(&self, key: &K) -> Option<&V> {
40        self.lookup.get(key).map(|(_, value)| value)
41    }
42    pub fn find_entry(&self, key: &K) -> Option<(&K, &V)> {
43        self.lookup
44            .find_entry(key)
45            .map(|(stored, (_, value))| (stored, value))
46    }
47    pub fn iter(&self) -> impl Iterator<Item = &(K, V)> {
48        self.order.iter().filter_map(Option::as_ref)
49    }
50    pub fn assoc_value(&self, key: K, value: V) -> Self {
51        match self.lookup.get(&key) {
52            None => {
53                let index = self.order.len();
54                Self {
55                    lookup: self.lookup.assoc_value(key.clone(), (index, value.clone())),
56                    order: self.order.push_last(Some((key, value))),
57                }
58            }
59            Some((index, _)) => Self {
60                lookup: self
61                    .lookup
62                    .assoc_value(key.clone(), (*index, value.clone())),
63                order: self
64                    .order
65                    .assoc_value(*index, Some((key, value)))
66                    .expect("ordered-map index"),
67            },
68        }
69    }
70    /// Associates into a consumed ordered map, reusing the CHAMP lookup path
71    /// when it is uniquely owned while retaining persistent alias semantics.
72    pub fn assoc_value_owned(mut self, key: K, value: V) -> Self {
73        match self.lookup.get(&key).map(|(index, _)| *index) {
74            None => {
75                let index = self.order.len();
76                self.lookup = self
77                    .lookup
78                    .assoc_value_owned(key.clone(), (index, value.clone()));
79                self.order = self.order.push_last_owned(Some((key, value)));
80            }
81            Some(index) => {
82                self.lookup = self
83                    .lookup
84                    .assoc_value_owned(key.clone(), (index, value.clone()));
85                self.order = self
86                    .order
87                    .assoc_value_owned(index, Some((key, value)))
88                    .expect("ordered-map index");
89            }
90        }
91        self
92    }
93    pub fn dissoc_value(&self, key: &K) -> Self {
94        let Some((index, _)) = self.lookup.get(key) else {
95            return self.clone();
96        };
97        let map = Self {
98            lookup: self.lookup.dissoc_value(key),
99            order: self
100                .order
101                .assoc_value(*index, None)
102                .expect("ordered-map index"),
103        };
104        map.compact_if_sparse()
105    }
106    fn compact_if_sparse(self) -> Self {
107        if self.order.len() <= COMPACT_MINIMUM || self.order.len() <= 2 * self.lookup.len() {
108            return self;
109        }
110        self.iter()
111            .cloned()
112            .collect::<Self>()
113            .with_meta(self.lookup.meta().cloned())
114    }
115}
116
117impl<K: Clone + Eq + Hash, V: Clone> FromIterator<(K, V)> for Standard<K, V> {
118    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
119        iter.into_iter()
120            .fold(Self::new(), |map, (key, value)| map.assoc_value(key, value))
121    }
122}
123impl<K: Clone + Eq + Hash, V: Clone + PartialEq> PartialEq for Standard<K, V> {
124    fn eq(&self, other: &Self) -> bool {
125        self.len() == other.len()
126            && self
127                .iter()
128                .all(|(key, value)| other.get(key) == Some(value))
129    }
130}
131impl<K: Clone + Eq + Hash, V: Clone> ICount for Standard<K, V> {
132    fn count(&self) -> usize {
133        self.len()
134    }
135}
136impl<K: Clone + Eq + Hash, V: Clone> IFind<K> for Standard<K, V> {
137    type Output = (K, V);
138    fn find(&self, key: &K) -> Option<Self::Output> {
139        self.find_entry(key).map(|(k, v)| (k.clone(), v.clone()))
140    }
141}
142impl<K: Clone + Eq + Hash, V: Clone> ILookup<K, V> for Standard<K, V> {
143    type Keys = std::vec::IntoIter<K>;
144    type Values = std::vec::IntoIter<V>;
145    fn keys(&self) -> Self::Keys {
146        self.iter()
147            .map(|(key, _)| key.clone())
148            .collect::<Vec<_>>()
149            .into_iter()
150    }
151    fn vals(&self) -> Self::Values {
152        self.iter()
153            .map(|(_, value)| value.clone())
154            .collect::<Vec<_>>()
155            .into_iter()
156    }
157}
158impl<K: Clone + Eq + Hash, V: Clone> IAssoc<K, V> for Standard<K, V> {
159    type Output = Self;
160    fn assoc(&self, k: K, v: V) -> Self {
161        self.assoc_value(k, v)
162    }
163}
164impl<K: Clone + Eq + Hash, V: Clone> IDissoc<K> for Standard<K, V> {
165    type Output = Self;
166    fn dissoc(&self, k: &K) -> Self {
167        self.dissoc_value(k)
168    }
169}
170impl<K: Clone + Eq + Hash, V: Clone> INth<(K, V)> for Standard<K, V> {
171    fn nth(&self, i: usize) -> Option<&(K, V)> {
172        self.iter().nth(i)
173    }
174}
175impl<K: Clone + Eq + Hash, V: Clone> IEmpty for Standard<K, V> {
176    type Output = Self;
177    fn empty(&self) -> Self {
178        Self::new().with_meta(self.lookup.meta().cloned())
179    }
180}
181impl<K: Clone + Eq + Hash, V: Clone> IMetadata for Standard<K, V> {
182    type Metadata = std::rc::Rc<crate::lang::data::Metadata>;
183    fn meta(&self) -> Option<&Self::Metadata> {
184        self.lookup.meta()
185    }
186    fn with_meta(&self, metadata: Option<Self::Metadata>) -> Self {
187        Self {
188            lookup: self.lookup.with_meta(metadata.clone()),
189            order: self.order.with_meta(metadata),
190        }
191    }
192
193    fn metatype(&self) -> MetaType {
194        MetaType::Map
195    }
196}
197impl<K: Clone + Eq + Hash, V: Clone> IPersistent for Standard<K, V> {}
198impl<K: Clone + Eq + Hash, V: Clone> IntoIterator for Standard<K, V> {
199    type Item = (K, V);
200    type IntoIter = std::vec::IntoIter<(K, V)>;
201    fn into_iter(self) -> Self::IntoIter {
202        self.iter().cloned().collect::<Vec<_>>().into_iter()
203    }
204}
205impl<K: Clone + Eq + Hash, V: Clone> IConj<(K, V)> for Standard<K, V> {
206    type Output = Self;
207    fn conj(&self, (k, v): (K, V)) -> Self {
208        self.assoc_value(k, v)
209    }
210}
211impl<K: Clone + Eq + Hash, V: Clone + PartialEq> IEquality for Standard<K, V> {
212    fn equality(&self, other: &Self) -> bool {
213        self.len() == other.len() && self.iter().all(|(k, v)| other.get(k) == Some(v))
214    }
215}
216impl<K: Clone + Eq + Hash + std::fmt::Debug, V: Clone + std::fmt::Debug> IDisplay
217    for Standard<K, V>
218{
219    fn display(&self) -> String {
220        format!(
221            "{{{}}}",
222            self.iter()
223                .map(|(k, v)| format!("{k:?} {v:?}"))
224                .collect::<Vec<_>>()
225                .join(" ")
226        )
227    }
228}
229impl<K: Clone + Eq + Hash + JavaHash, V: Clone + Hash + JavaHash> IHash for Standard<K, V> {
230    fn hash_calc(&self, hash_type: HashType) -> u64 {
231        // Same composition as the hash map (Java IMapType → IUnOrderedType):
232        // "::MAP" seed, sum of ordered-entry hashes (see lang::hash).
233        crate::lang::hash::compose_unordered(
234            "MAP",
235            self.iter().map(|(k, v)| {
236                crate::lang::hash::compose_entry(k.java_hash(hash_type), v.java_hash(hash_type))
237            }),
238        ) as u64
239    }
240}
241impl<K: Clone + Eq + Hash + std::fmt::Debug, V: Clone + std::fmt::Debug> IObjType
242    for Standard<K, V>
243{
244    fn obj_type(&self) -> ObjType {
245        ObjType::Map
246    }
247}
248impl<K, V> IColl<(K, V)> for Standard<K, V>
249where
250    K: Clone + Eq + Hash + JavaHash + std::fmt::Debug,
251    V: Clone + PartialEq + Hash + JavaHash + std::fmt::Debug,
252{
253    fn start_string(&self) -> &'static str {
254        "{"
255    }
256    fn end_string(&self) -> &'static str {
257        "}"
258    }
259}
260impl<K: Clone + Eq + Hash, V: Clone> IToMutable for Standard<K, V> {
261    type Mutable = Mutable<K, V>;
262    fn to_mutable(&self) -> Self::Mutable {
263        Mutable {
264            editable: Cell::new(true),
265            map: self.clone(),
266        }
267    }
268}
269
270#[derive(Debug, Clone)]
271pub struct Mutable<K, V> {
272    editable: Cell<bool>,
273    map: Standard<K, V>,
274}
275impl<K: Clone + Eq + Hash, V: Clone> Mutable<K, V> {
276    fn check(&self) {
277        assert!(
278            self.editable.get(),
279            "mutable ordered map used after to_persistent"
280        );
281    }
282    pub fn assoc(&mut self, key: K, value: V) -> &mut Self {
283        self.check();
284        self.map = self.map.assoc_value(key, value);
285        self
286    }
287    pub fn dissoc(&mut self, key: &K) -> &mut Self {
288        self.check();
289        self.map = self.map.dissoc_value(key);
290        self
291    }
292}
293impl<K: Clone + Eq + Hash, V: Clone> std::ops::Deref for Mutable<K, V> {
294    type Target = Standard<K, V>;
295    fn deref(&self) -> &Self::Target {
296        self.check();
297        &self.map
298    }
299}
300impl<K, V> IMutable for Mutable<K, V> {}
301impl<K: Clone + Eq + Hash, V: Clone> IToPersistent for Mutable<K, V> {
302    type Persistent = Standard<K, V>;
303    fn to_persistent(&mut self) -> Self::Persistent {
304        self.check();
305        self.editable.set(false);
306        self.map.clone()
307    }
308}
309
310#[cfg(test)]
311mod tests {
312    use super::Standard;
313    #[test]
314    fn replacement_keeps_position_and_deletion_compacts() {
315        let map = Standard::new()
316            .assoc_value("a", 1)
317            .assoc_value("b", 2)
318            .assoc_value("a", 3);
319        assert_eq!(
320            map.iter().cloned().collect::<Vec<_>>(),
321            vec![("a", 3), ("b", 2)]
322        );
323        use crate::lang::protocol::IMetadata;
324        let original = (0..80)
325            .map(|n| (n, n))
326            .collect::<Standard<_, _>>()
327            .with_meta(Some(crate::lang::data::Metadata::document("doc")));
328        let reduced = (0..60).fold(original.clone(), |map, key| map.dissoc_value(&key));
329        assert_eq!(original.len(), 80);
330        assert_eq!(reduced.meta().map(|m| m.doc().unwrap()), Some("doc"));
331        assert_eq!(
332            reduced.iter().map(|(key, _)| *key).collect::<Vec<_>>(),
333            (60..80).collect::<Vec<_>>()
334        );
335    }
336
337    #[test]
338    fn compaction_triggers_at_java_threshold_and_renumbers() {
339        // Java: compact on dissoc when order.count() > 32 &&
340        // order.count() > 2 * lookup.count(), rebuilding both structures
341        // and renumbering lookup indices 0..count-1.
342        let mut map = (0..33).map(|n| (n, n)).collect::<Standard<_, _>>();
343        for key in 0..16 {
344            map = map.dissoc_value(&key);
345        }
346        // order 33, lookup 17: 33 > 32 but 33 <= 2 * 17, no compaction
347        assert_eq!(map.order.len(), 33);
348        map = map.dissoc_value(&16);
349        // order 33, lookup 16: 33 > 32 and 33 > 2 * 16, compact + renumber
350        assert_eq!(map.order.len(), 16);
351        assert_eq!(
352            map.iter().map(|(key, _)| *key).collect::<Vec<_>>(),
353            (17..33).collect::<Vec<_>>()
354        );
355        // renumbered: overwriting the first live key writes slot 0
356        let overwritten = map.assoc_value(17, 999);
357        assert_eq!(overwritten.iter().next(), Some(&(17, 999)));
358        // order at exactly 32 never compacts
359        let mut small = (0..32).map(|n| (n, n)).collect::<Standard<_, _>>();
360        for key in 0..31 {
361            small = small.dissoc_value(&key);
362        }
363        assert_eq!(small.order.len(), 32);
364        assert_eq!(small.len(), 1);
365    }
366
367    #[test]
368    fn dissoc_then_reassoc_appends_at_end() {
369        use crate::lang::protocol::{IFind, INth};
370        let map = Standard::new()
371            .assoc_value("a", 1)
372            .assoc_value("b", 2)
373            .assoc_value("c", 3)
374            .dissoc_value(&"b")
375            .assoc_value("b", 9);
376        assert_eq!(
377            map.iter().cloned().collect::<Vec<_>>(),
378            vec![("a", 1), ("c", 3), ("b", 9)]
379        );
380        assert_eq!(map.nth(1), Some(&("c", 3)));
381        assert_eq!(map.find(&"b"), Some(("b", 9)));
382        assert_eq!(map.find(&"zz"), None);
383    }
384}
hara_native/lang/data/ordered_map.rs

hara_native/lang/data/
ordered_map.rs
