hara_native/lang/data/
deque.rs

1//! Persistent deque backed by a count-measured finger tree.
2
3use crate::lang::hash::JavaHash;
4use crate::lang::protocol::{
5    HashType, IAssoc, IColl, IConj, ICons, ICount, IDisplay, IEmpty, IEquality, IHash, ILookup,
6    IMetadata, INth, IObjType, IPeekFirst, IPeekLast, IPersistent, IPopFirst, IPopLast, IPushFirst,
7    IPushLast, MetaType, ObjType,
8};
9use std::rc::Rc;
10
11#[derive(Debug, Clone)]
12enum Item<E> {
13    Leaf(E),
14    Branch {
15        measure: usize,
16        children: Vec<Rc<Item<E>>>,
17    },
18}
19
20impl<E: Clone> Item<E> {
21    fn leaf(value: E) -> Rc<Self> {
22        Rc::new(Self::Leaf(value))
23    }
24    fn branch(children: Vec<Rc<Self>>) -> Rc<Self> {
25        debug_assert!((2..=3).contains(&children.len()));
26        Rc::new(Self::Branch {
27            measure: children.iter().map(|child| child.measure()).sum(),
28            children,
29        })
30    }
31    fn measure(&self) -> usize {
32        match self {
33            Self::Leaf(_) => 1,
34            Self::Branch { measure, .. } => *measure,
35        }
36    }
37    fn get(&self, mut index: usize) -> Option<&E> {
38        match self {
39            Self::Leaf(value) => (index == 0).then_some(value),
40            Self::Branch { children, .. } => {
41                for child in children {
42                    if index < child.measure() {
43                        return child.get(index);
44                    }
45                    index -= child.measure();
46                }
47                None
48            }
49        }
50    }
51    fn replace(&self, mut index: usize, value: E) -> Option<Rc<Self>> {
52        match self {
53            Self::Leaf(_) => (index == 0).then(|| Self::leaf(value)),
54            Self::Branch { children, .. } => {
55                for (position, child) in children.iter().enumerate() {
56                    if index < child.measure() {
57                        let mut replaced = children.clone();
58                        replaced[position] = child.replace(index, value)?;
59                        return Some(Self::branch(replaced));
60                    }
61                    index -= child.measure();
62                }
63                None
64            }
65        }
66    }
67    fn collect<'a>(&'a self, output: &mut Vec<&'a E>) {
68        match self {
69            Self::Leaf(value) => output.push(value),
70            Self::Branch { children, .. } => {
71                for child in children {
72                    child.collect(output);
73                }
74            }
75        }
76    }
77    fn children(&self) -> Vec<Rc<Self>> {
78        match self {
79            Self::Branch { children, .. } => children.clone(),
80            Self::Leaf(_) => unreachable!("finger-tree middle item must be a branch"),
81        }
82    }
83}
84
85#[derive(Debug, Clone, Default)]
86enum FingerTree<E> {
87    #[default]
88    Empty,
89    Single(Rc<Item<E>>),
90    Deep {
91        measure: usize,
92        prefix: Vec<Rc<Item<E>>>,
93        middle: Rc<FingerTree<E>>,
94        suffix: Vec<Rc<Item<E>>>,
95    },
96}
97
98impl<E: Clone> FingerTree<E> {
99    fn measure(&self) -> usize {
100        match self {
101            Self::Empty => 0,
102            Self::Single(item) => item.measure(),
103            Self::Deep { measure, .. } => *measure,
104        }
105    }
106    fn deep(prefix: Vec<Rc<Item<E>>>, middle: Rc<Self>, suffix: Vec<Rc<Item<E>>>) -> Self {
107        debug_assert!((1..=4).contains(&prefix.len()));
108        debug_assert!((1..=4).contains(&suffix.len()));
109        let measure = prefix.iter().map(|item| item.measure()).sum::<usize>()
110            + middle.measure()
111            + suffix.iter().map(|item| item.measure()).sum::<usize>();
112        Self::Deep {
113            measure,
114            prefix,
115            middle,
116            suffix,
117        }
118    }
119    fn push_first_item(&self, item: Rc<Item<E>>) -> Self {
120        match self {
121            Self::Empty => Self::Single(item),
122            Self::Single(existing) => {
123                Self::deep(vec![item], Rc::new(Self::Empty), vec![existing.clone()])
124            }
125            Self::Deep {
126                prefix,
127                middle,
128                suffix,
129                ..
130            } if prefix.len() < 4 => {
131                let mut next = Vec::with_capacity(prefix.len() + 1);
132                next.push(item);
133                next.extend(prefix.iter().cloned());
134                Self::deep(next, middle.clone(), suffix.clone())
135            }
136            Self::Deep {
137                prefix,
138                middle,
139                suffix,
140                ..
141            } => {
142                let node = Item::branch(prefix[1..].to_vec());
143                Self::deep(
144                    vec![item, prefix[0].clone()],
145                    Rc::new(middle.push_first_item(node)),
146                    suffix.clone(),
147                )
148            }
149        }
150    }
151    fn push_last_item(&self, item: Rc<Item<E>>) -> Self {
152        match self {
153            Self::Empty => Self::Single(item),
154            Self::Single(existing) => {
155                Self::deep(vec![existing.clone()], Rc::new(Self::Empty), vec![item])
156            }
157            Self::Deep {
158                prefix,
159                middle,
160                suffix,
161                ..
162            } if suffix.len() < 4 => {
163                let mut next = suffix.clone();
164                next.push(item);
165                Self::deep(prefix.clone(), middle.clone(), next)
166            }
167            Self::Deep {
168                prefix,
169                middle,
170                suffix,
171                ..
172            } => {
173                let node = Item::branch(suffix[..3].to_vec());
174                Self::deep(
175                    prefix.clone(),
176                    Rc::new(middle.push_last_item(node)),
177                    vec![suffix[3].clone(), item],
178                )
179            }
180        }
181    }
182    fn from_items(items: Vec<Rc<Item<E>>>) -> Self {
183        items
184            .into_iter()
185            .fold(Self::Empty, |tree, item| tree.push_last_item(item))
186    }
187    fn pop_first_item(&self) -> Option<(Rc<Item<E>>, Self)> {
188        match self {
189            Self::Empty => None,
190            Self::Single(item) => Some((item.clone(), Self::Empty)),
191            Self::Deep {
192                prefix,
193                middle,
194                suffix,
195                ..
196            } if prefix.len() > 1 => Some((
197                prefix[0].clone(),
198                Self::deep(prefix[1..].to_vec(), middle.clone(), suffix.clone()),
199            )),
200            Self::Deep {
201                prefix,
202                middle,
203                suffix,
204                ..
205            } => {
206                if let Some((node, next_middle)) = middle.pop_first_item() {
207                    Some((
208                        prefix[0].clone(),
209                        Self::deep(node.children(), Rc::new(next_middle), suffix.clone()),
210                    ))
211                } else {
212                    Some((prefix[0].clone(), Self::from_items(suffix.clone())))
213                }
214            }
215        }
216    }
217    fn pop_last_item(&self) -> Option<(Rc<Item<E>>, Self)> {
218        match self {
219            Self::Empty => None,
220            Self::Single(item) => Some((item.clone(), Self::Empty)),
221            Self::Deep {
222                prefix,
223                middle,
224                suffix,
225                ..
226            } if suffix.len() > 1 => {
227                let last = suffix.len() - 1;
228                Some((
229                    suffix[last].clone(),
230                    Self::deep(prefix.clone(), middle.clone(), suffix[..last].to_vec()),
231                ))
232            }
233            Self::Deep {
234                prefix,
235                middle,
236                suffix,
237                ..
238            } => {
239                if let Some((node, next_middle)) = middle.pop_last_item() {
240                    Some((
241                        suffix[0].clone(),
242                        Self::deep(prefix.clone(), Rc::new(next_middle), node.children()),
243                    ))
244                } else {
245                    Some((suffix[0].clone(), Self::from_items(prefix.clone())))
246                }
247            }
248        }
249    }
250    fn get(&self, mut index: usize) -> Option<&E> {
251        match self {
252            Self::Empty => None,
253            Self::Single(item) => item.get(index),
254            Self::Deep {
255                prefix,
256                middle,
257                suffix,
258                ..
259            } => {
260                for item in prefix {
261                    if index < item.measure() {
262                        return item.get(index);
263                    }
264                    index -= item.measure();
265                }
266                if index < middle.measure() {
267                    return middle.get(index);
268                }
269                index -= middle.measure();
270                for item in suffix {
271                    if index < item.measure() {
272                        return item.get(index);
273                    }
274                    index -= item.measure();
275                }
276                None
277            }
278        }
279    }
280    fn replace(&self, mut index: usize, value: E) -> Option<Self> {
281        match self {
282            Self::Empty => None,
283            Self::Single(item) => Some(Self::Single(item.replace(index, value)?)),
284            Self::Deep {
285                prefix,
286                middle,
287                suffix,
288                ..
289            } => {
290                for (position, item) in prefix.iter().enumerate() {
291                    if index < item.measure() {
292                        let mut next = prefix.clone();
293                        next[position] = item.replace(index, value)?;
294                        return Some(Self::deep(next, middle.clone(), suffix.clone()));
295                    }
296                    index -= item.measure();
297                }
298                if index < middle.measure() {
299                    return Some(Self::deep(
300                        prefix.clone(),
301                        Rc::new(middle.replace(index, value)?),
302                        suffix.clone(),
303                    ));
304                }
305                index -= middle.measure();
306                for (position, item) in suffix.iter().enumerate() {
307                    if index < item.measure() {
308                        let mut next = suffix.clone();
309                        next[position] = item.replace(index, value)?;
310                        return Some(Self::deep(prefix.clone(), middle.clone(), next));
311                    }
312                    index -= item.measure();
313                }
314                None
315            }
316        }
317    }
318    fn collect<'a>(&'a self, output: &mut Vec<&'a E>) {
319        match self {
320            Self::Empty => {}
321            Self::Single(item) => item.collect(output),
322            Self::Deep {
323                prefix,
324                middle,
325                suffix,
326                ..
327            } => {
328                for item in prefix {
329                    item.collect(output);
330                }
331                middle.collect(output);
332                for item in suffix {
333                    item.collect(output);
334                }
335            }
336        }
337    }
338}
339
340#[derive(Debug, Clone)]
341pub struct Standard<E> {
342    metadata: Option<Rc<crate::lang::data::Metadata>>,
343    tree: FingerTree<E>,
344}
345
346impl<E: Clone> Default for Standard<E> {
347    fn default() -> Self {
348        Self {
349            metadata: None,
350            tree: FingerTree::Empty,
351        }
352    }
353}
354impl<E: Clone> Standard<E> {
355    pub fn new() -> Self {
356        Self::default()
357    }
358    pub fn len(&self) -> usize {
359        self.tree.measure()
360    }
361    pub fn is_empty(&self) -> bool {
362        self.len() == 0
363    }
364    pub fn get(&self, index: usize) -> Option<&E> {
365        self.tree.get(index)
366    }
367    pub fn push_first(&self, value: E) -> Self {
368        Self {
369            metadata: self.metadata.clone(),
370            tree: self.tree.push_first_item(Item::leaf(value)),
371        }
372    }
373    pub fn push_last(&self, value: E) -> Self {
374        Self {
375            metadata: self.metadata.clone(),
376            tree: self.tree.push_last_item(Item::leaf(value)),
377        }
378    }
379    pub fn pop_first_value(&self) -> Self {
380        self.tree
381            .pop_first_item()
382            .map(|(_, tree)| Self {
383                metadata: self.metadata.clone(),
384                tree,
385            })
386            .unwrap_or_else(|| self.clone())
387    }
388    pub fn pop_last_value(&self) -> Self {
389        self.tree
390            .pop_last_item()
391            .map(|(_, tree)| Self {
392                metadata: self.metadata.clone(),
393                tree,
394            })
395            .unwrap_or_else(|| self.clone())
396    }
397    pub fn assoc_value(&self, index: usize, value: E) -> Option<Self> {
398        Some(Self {
399            metadata: self.metadata.clone(),
400            tree: self.tree.replace(index, value)?,
401        })
402    }
403    pub fn iter(&self) -> std::vec::IntoIter<&E> {
404        let mut values = Vec::with_capacity(self.len());
405        self.tree.collect(&mut values);
406        values.into_iter()
407    }
408}
409impl<E: Clone> FromIterator<E> for Standard<E> {
410    fn from_iter<T: IntoIterator<Item = E>>(it: T) -> Self {
411        it.into_iter().fold(Self::new(), |d, v| d.push_last(v))
412    }
413}
414impl<E: Clone> IntoIterator for Standard<E> {
415    type Item = E;
416    type IntoIter = std::vec::IntoIter<E>;
417    fn into_iter(self) -> Self::IntoIter {
418        self.iter().cloned().collect::<Vec<_>>().into_iter()
419    }
420}
421impl<E: Clone + PartialEq> PartialEq for Standard<E> {
422    fn eq(&self, other: &Self) -> bool {
423        self.len() == other.len() && self.iter().eq(other.iter())
424    }
425}
426impl<E: Clone> ICount for Standard<E> {
427    fn count(&self) -> usize {
428        self.len()
429    }
430}
431impl<E: Clone> INth<E> for Standard<E> {
432    fn nth(&self, index: usize) -> Option<&E> {
433        self.get(index)
434    }
435}
436impl<E: Clone> ILookup<usize, E> for Standard<E> {
437    type Keys = std::ops::Range<usize>;
438    type Values = std::vec::IntoIter<E>;
439    fn keys(&self) -> Self::Keys {
440        0..self.len()
441    }
442    fn vals(&self) -> Self::Values {
443        self.iter().cloned().collect::<Vec<_>>().into_iter()
444    }
445}
446impl<E: Clone> crate::lang::protocol::IFind<usize> for Standard<E> {
447    type Output = (usize, E);
448    fn find(&self, key: &usize) -> Option<Self::Output> {
449        self.get(*key).cloned().map(|v| (*key, v))
450    }
451}
452impl<E: Clone> IAssoc<usize, E> for Standard<E> {
453    type Output = Self;
454    fn assoc(&self, k: usize, v: E) -> Self {
455        self.assoc_value(k, v).unwrap_or_else(|| self.clone())
456    }
457}
458impl<E: Clone> IPeekFirst<E> for Standard<E> {
459    fn peek_first(&self) -> Option<E> {
460        self.get(0).cloned()
461    }
462}
463impl<E: Clone> IPeekLast<E> for Standard<E> {
464    fn peek_last(&self) -> Option<E> {
465        self.len().checked_sub(1).and_then(|i| self.get(i)).cloned()
466    }
467}
468impl<E: Clone> IPushFirst<E> for Standard<E> {
469    type Output = Self;
470    fn push_first(&self, v: E) -> Self {
471        Standard::push_first(self, v)
472    }
473}
474impl<E: Clone> IPushLast<E> for Standard<E> {
475    type Output = Self;
476    fn push_last(&self, v: E) -> Self {
477        Standard::push_last(self, v)
478    }
479}
480impl<E: Clone> IPopFirst for Standard<E> {
481    type Output = Self;
482    fn pop_first(&self) -> Self {
483        self.pop_first_value()
484    }
485}
486impl<E: Clone> IPopLast for Standard<E> {
487    type Output = Self;
488    fn pop_last(&self) -> Self {
489        self.pop_last_value()
490    }
491}
492impl<E: Clone> ICons<E> for Standard<E> {
493    type Output = Self;
494    fn cons(&self, v: E) -> Self {
495        self.push_first(v)
496    }
497}
498impl<E: Clone> IConj<E> for Standard<E> {
499    type Output = Self;
500    fn conj(&self, v: E) -> Self {
501        self.push_last(v)
502    }
503}
504impl<E: Clone> IEmpty for Standard<E> {
505    type Output = Self;
506    fn empty(&self) -> Self {
507        Self::new().with_meta(self.metadata.clone())
508    }
509}
510impl<E: Clone> IMetadata for Standard<E> {
511    type Metadata = Rc<crate::lang::data::Metadata>;
512    fn meta(&self) -> Option<&Self::Metadata> {
513        self.metadata.as_ref()
514    }
515    fn with_meta(&self, metadata: Option<Self::Metadata>) -> Self {
516        Self {
517            metadata,
518            tree: self.tree.clone(),
519        }
520    }
521    fn metatype(&self) -> MetaType {
522        MetaType::Object
523    }
524}
525impl<E: Clone> IPersistent for Standard<E> {}
526impl<E: Clone + PartialEq> IEquality for Standard<E> {
527    fn equality(&self, other: &Self) -> bool {
528        self == other
529    }
530}
531impl<E: Clone + std::fmt::Debug> IDisplay for Standard<E> {
532    fn display(&self) -> String {
533        format!(
534            "[{}]",
535            self.iter()
536                .map(|v| format!("{v:?}"))
537                .collect::<Vec<_>>()
538                .join(" ")
539        )
540    }
541}
542impl<E: Clone + std::hash::Hash + JavaHash> IHash for Standard<E> {
543    fn hash_calc(&self, t: HashType) -> u64 {
544        crate::lang::hash::compose_ordered("SEQUENTIAL", self.iter().map(|v| v.java_hash(t))) as u64
545    }
546}
547impl<E: Clone + std::fmt::Debug> IObjType for Standard<E> {
548    fn obj_type(&self) -> ObjType {
549        ObjType::Sequential
550    }
551}
552impl<E> IColl<E> for Standard<E>
553where
554    E: Clone + PartialEq + std::hash::Hash + JavaHash + std::fmt::Debug,
555{
556    fn start_string(&self) -> &'static str {
557        "["
558    }
559    fn end_string(&self) -> &'static str {
560        "]"
561    }
562}
563
564#[cfg(test)]
565mod tests {
566    use super::Standard;
567    #[test]
568    fn finger_tree_deque_matches_two_ended_model() {
569        let mut deque = Standard::new();
570        let mut model = std::collections::VecDeque::new();
571        for i in 0..2000 {
572            if i % 3 == 0 {
573                deque = deque.push_first(i);
574                model.push_front(i)
575            } else {
576                deque = deque.push_last(i);
577                model.push_back(i)
578            }
579        }
580        assert_eq!(
581            deque.iter().copied().collect::<Vec<_>>(),
582            model.iter().copied().collect::<Vec<_>>()
583        );
584        for i in 0..1500 {
585            if i % 2 == 0 {
586                deque = deque.pop_first_value();
587                model.pop_front();
588            } else {
589                deque = deque.pop_last_value();
590                model.pop_back();
591            }
592        }
593        assert_eq!(
594            deque.iter().copied().collect::<Vec<_>>(),
595            model.iter().copied().collect::<Vec<_>>()
596        );
597        assert_eq!(deque.len(), model.len());
598    }
599    #[test]
600    fn persistence_and_index_replacement_are_preserved() {
601        let original: Standard<_> = (0..100).collect();
602        let changed = original.assoc_value(50, 999).unwrap();
603        assert_eq!(original.get(50), Some(&50));
604        assert_eq!(changed.get(50), Some(&999));
605        assert_eq!(changed.get(99), Some(&99));
606    }
607}
hara_native/lang/data/deque.rs

hara_native/lang/data/
deque.rs
