hara_native/lang/data/
ordered_set.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, IColl, IConj, ICount, IDisplay, IDissoc, IEmpty, IEquality, IFind, IHash, IMetadata,
8    IMutable, INth, IObjType, IPersistent, IToMutable, IToPersistent, ObjType,
9};
10
11const COMPACT_MINIMUM: usize = 32;
12
13#[derive(Debug, Clone)]
14pub struct Standard<E> {
15    lookup: Map<E, usize>,
16    order: Vector<Option<E>>,
17}
18impl<E: Clone + Eq + Hash> Default for Standard<E> {
19    fn default() -> Self {
20        Self {
21            lookup: Map::new(),
22            order: Vector::new(),
23        }
24    }
25}
26impl<E: Clone + Eq + Hash> Standard<E> {
27    pub fn new() -> Self {
28        Self::default()
29    }
30    pub fn len(&self) -> usize {
31        self.lookup.len()
32    }
33    pub fn is_empty(&self) -> bool {
34        self.lookup.is_empty()
35    }
36    pub fn get(&self, value: &E) -> Option<&E> {
37        self.lookup.find_entry(value).map(|(stored, _)| stored)
38    }
39    pub fn contains(&self, value: &E) -> bool {
40        self.get(value).is_some()
41    }
42    pub fn iter(&self) -> impl Iterator<Item = &E> {
43        self.order.iter().filter_map(Option::as_ref)
44    }
45    pub fn conj_value(&self, value: E) -> Self {
46        if self.lookup.get(&value).is_some() {
47            return self.clone();
48        }
49        let index = self.order.len();
50        Self {
51            lookup: self.lookup.assoc_value(value.clone(), index),
52            order: self.order.push_last(Some(value)),
53        }
54    }
55    pub fn dissoc_value(&self, value: &E) -> Self {
56        let Some(index) = self.lookup.get(value) else {
57            return self.clone();
58        };
59        let set = Self {
60            lookup: self.lookup.dissoc_value(value),
61            order: self
62                .order
63                .assoc_value(*index, None)
64                .expect("ordered-set index"),
65        };
66        set.compact_if_sparse()
67    }
68    fn compact_if_sparse(self) -> Self {
69        if self.order.len() <= COMPACT_MINIMUM || self.order.len() <= 2 * self.lookup.len() {
70            return self;
71        }
72        self.iter()
73            .cloned()
74            .collect::<Self>()
75            .with_meta(self.lookup.meta().cloned())
76    }
77}
78impl<E: Clone + Eq + Hash> FromIterator<E> for Standard<E> {
79    fn from_iter<T: IntoIterator<Item = E>>(iter: T) -> Self {
80        iter.into_iter()
81            .fold(Self::new(), |set, value| set.conj_value(value))
82    }
83}
84impl<E: Clone + Eq + Hash> From<Vec<E>> for Standard<E> {
85    fn from(values: Vec<E>) -> Self {
86        values.into_iter().collect()
87    }
88}
89impl<E: Clone + Eq + Hash> PartialEq for Standard<E> {
90    fn eq(&self, other: &Self) -> bool {
91        self.len() == other.len() && self.iter().all(|v| other.contains(v))
92    }
93}
94impl<E: Clone + Eq + Hash> ICount for Standard<E> {
95    fn count(&self) -> usize {
96        self.len()
97    }
98}
99impl<E: Clone + Eq + Hash> IFind<E> for Standard<E> {
100    type Output = E;
101    fn find(&self, key: &E) -> Option<E> {
102        self.get(key).cloned()
103    }
104}
105impl<E: Clone + Eq + Hash> IConj<E> for Standard<E> {
106    type Output = Self;
107    fn conj(&self, value: E) -> Self {
108        self.conj_value(value)
109    }
110}
111impl<E: Clone + Eq + Hash> IDissoc<E> for Standard<E> {
112    type Output = Self;
113    fn dissoc(&self, key: &E) -> Self {
114        self.dissoc_value(key)
115    }
116}
117impl<E: Clone + Eq + Hash> INth<E> for Standard<E> {
118    fn nth(&self, index: usize) -> Option<&E> {
119        self.iter().nth(index)
120    }
121}
122impl<E: Clone + Eq + Hash> IEmpty for Standard<E> {
123    type Output = Self;
124    fn empty(&self) -> Self {
125        Self::new().with_meta(self.lookup.meta().cloned())
126    }
127}
128impl<E: Clone + Eq + Hash> IMetadata for Standard<E> {
129    type Metadata = std::rc::Rc<crate::lang::data::Metadata>;
130    fn meta(&self) -> Option<&Self::Metadata> {
131        self.lookup.meta()
132    }
133    fn with_meta(&self, metadata: Option<Self::Metadata>) -> Self {
134        Self {
135            lookup: self.lookup.with_meta(metadata.clone()),
136            order: self.order.with_meta(metadata),
137        }
138    }
139}
140impl<E: Clone + Eq + Hash> IPersistent for Standard<E> {}
141impl<E: Clone + Eq + Hash> IntoIterator for Standard<E> {
142    type Item = E;
143    type IntoIter = std::vec::IntoIter<E>;
144    fn into_iter(self) -> Self::IntoIter {
145        self.iter().cloned().collect::<Vec<_>>().into_iter()
146    }
147}
148impl<E: Clone + Eq + Hash> IEquality for Standard<E> {
149    fn equality(&self, other: &Self) -> bool {
150        self.len() == other.len() && self.iter().all(|v| other.get(v).is_some())
151    }
152}
153impl<E: Clone + Eq + Hash + std::fmt::Debug> IDisplay for Standard<E> {
154    fn display(&self) -> String {
155        format!(
156            "#{{{}}}",
157            self.iter()
158                .map(|v| format!("{v:?}"))
159                .collect::<Vec<_>>()
160                .join(" ")
161        )
162    }
163}
164impl<E: Clone + Eq + Hash + JavaHash> IHash for Standard<E> {
165    fn hash_calc(&self, hash_type: HashType) -> u64 {
166        // Java ISetType → IUnOrderedType: order-insensitive sum,
167        // "::SET" seed (see lang::hash).
168        crate::lang::hash::compose_unordered("SET", self.iter().map(|v| v.java_hash(hash_type)))
169            as u64
170    }
171}
172impl<E: Clone + Eq + Hash + std::fmt::Debug> IObjType for Standard<E> {
173    fn obj_type(&self) -> ObjType {
174        ObjType::Set
175    }
176}
177impl<E> IColl<E> for Standard<E>
178where
179    E: Clone + Eq + Hash + JavaHash + std::fmt::Debug,
180{
181    fn start_string(&self) -> &'static str {
182        "#{"
183    }
184    fn end_string(&self) -> &'static str {
185        "}"
186    }
187}
188impl<E: Clone + Eq + Hash> IToMutable for Standard<E> {
189    type Mutable = Mutable<E>;
190    fn to_mutable(&self) -> Self::Mutable {
191        Mutable {
192            editable: Cell::new(true),
193            set: self.clone(),
194        }
195    }
196}
197
198#[derive(Debug, Clone)]
199pub struct Mutable<E> {
200    editable: Cell<bool>,
201    set: Standard<E>,
202}
203impl<E: Clone + Eq + Hash> Mutable<E> {
204    fn check(&self) {
205        assert!(
206            self.editable.get(),
207            "mutable ordered set used after to_persistent"
208        );
209    }
210    pub fn conj(&mut self, value: E) -> &mut Self {
211        self.check();
212        self.set = self.set.conj_value(value);
213        self
214    }
215    pub fn dissoc(&mut self, value: &E) -> &mut Self {
216        self.check();
217        self.set = self.set.dissoc_value(value);
218        self
219    }
220}
221impl<E: Clone + Eq + Hash> std::ops::Deref for Mutable<E> {
222    type Target = Standard<E>;
223    fn deref(&self) -> &Self::Target {
224        self.check();
225        &self.set
226    }
227}
228impl<E> IMutable for Mutable<E> {}
229impl<E: Clone + Eq + Hash> IToPersistent for Mutable<E> {
230    type Persistent = Standard<E>;
231    fn to_persistent(&mut self) -> Self::Persistent {
232        self.check();
233        self.editable.set(false);
234        self.set.clone()
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    use super::Standard;
241    #[test]
242    fn compaction_and_empty_preserve_metadata() {
243        use crate::lang::protocol::{IEmpty, IMetadata};
244        let original = (0..80)
245            .collect::<Standard<_>>()
246            .with_meta(Some(crate::lang::data::Metadata::document("doc")));
247        let reduced = (0..60).fold(original, |set, value| set.dissoc_value(&value));
248        assert_eq!(reduced.meta().map(|m| m.doc().unwrap()), Some("doc"));
249        assert_eq!(
250            reduced.empty().meta().map(|m| m.doc().unwrap()),
251            Some("doc")
252        );
253    }
254
255    #[test]
256    fn is_unique_ordered_and_persistent() {
257        let original = [3, 1, 3, 2].into_iter().collect::<Standard<_>>();
258        let reduced = original.dissoc_value(&1);
259        assert_eq!(original.iter().copied().collect::<Vec<_>>(), vec![3, 1, 2]);
260        assert_eq!(reduced.iter().copied().collect::<Vec<_>>(), vec![3, 2]);
261    }
262
263    #[test]
264    fn compaction_triggers_at_java_threshold_and_renumbers() {
265        // Java: compact on dissoc when order.count() > 32 &&
266        // order.count() > 2 * lookup.count(), rebuilding both structures
267        // and renumbering lookup indices 0..count-1.
268        let mut set = (0..33).collect::<Standard<_>>();
269        for value in 0..16 {
270            set = set.dissoc_value(&value);
271        }
272        // order 33, lookup 17: 33 > 32 but 33 <= 2 * 17, no compaction
273        assert_eq!(set.order.len(), 33);
274        set = set.dissoc_value(&16);
275        // order 33, lookup 16: 33 > 32 and 33 > 2 * 16, compact + renumber
276        assert_eq!(set.order.len(), 16);
277        assert_eq!(
278            set.iter().copied().collect::<Vec<_>>(),
279            (17..33).collect::<Vec<_>>()
280        );
281        // order at exactly 32 never compacts
282        let mut small = (0..32).collect::<Standard<_>>();
283        for value in 0..31 {
284            small = small.dissoc_value(&value);
285        }
286        assert_eq!(small.order.len(), 32);
287        assert_eq!(small.len(), 1);
288    }
289
290    #[test]
291    fn dissoc_then_reconj_appends_at_end() {
292        use crate::lang::protocol::{IFind, INth};
293        let set = [1, 2, 3]
294            .into_iter()
295            .collect::<Standard<_>>()
296            .dissoc_value(&2)
297            .conj_value(2);
298        assert_eq!(set.iter().copied().collect::<Vec<_>>(), vec![1, 3, 2]);
299        assert_eq!(set.nth(1), Some(&3));
300        assert_eq!(set.find(&2), Some(2));
301        assert_eq!(set.find(&9), None);
302        // duplicate conj keeps original position
303        let dup = set.conj_value(1);
304        assert_eq!(dup.iter().copied().collect::<Vec<_>>(), vec![1, 3, 2]);
305    }
306}
hara_native/lang/data/ordered_set.rs

hara_native/lang/data/
ordered_set.rs
