hara_native/lang/data/
queue.rs

1use crate::lang::data::{List, Vector};
2use crate::lang::hash::JavaHash;
3use crate::lang::protocol::{
4    HashType, IColl, IConj, ICount, IDisplay, IEmpty, IEquality, IHash, IMetadata, IMutable, INth,
5    IObjType, IPeekFirst, IPeekLast, IPersistent, IPopFirst, IPopLast, IPushFirst, IPushLast,
6    IToMutable, IToPersistent, ObjType,
7};
8use std::rc::Rc;
9
10pub const MAX_LENGTH: usize = 1024;
11
12#[derive(Debug, Clone)]
13pub struct Standard<E> {
14    metadata: Option<Rc<crate::lang::data::Metadata>>,
15    size: usize,
16    offset: usize,
17    head: Vector<E>,
18    tail: Vector<E>,
19    buffer: List<Vector<E>>,
20}
21
22impl<E: Clone> Default for Standard<E> {
23    fn default() -> Self {
24        Self {
25            metadata: None,
26            size: 0,
27            offset: 0,
28            head: Vector::new(),
29            tail: Vector::new(),
30            buffer: List::new(),
31        }
32    }
33}
34impl<E: Clone> Standard<E> {
35    pub fn new() -> Self {
36        Self::default()
37    }
38    pub fn len(&self) -> usize {
39        self.size
40    }
41    pub fn is_empty(&self) -> bool {
42        self.size == 0
43    }
44    pub fn peek_first(&self) -> Option<&E> {
45        if self.size == 0 {
46            None
47        } else {
48            self.head.get(self.offset)
49        }
50    }
51    pub fn peek_last(&self) -> Option<&E> {
52        if self.size == 0 {
53            None
54        } else if !self.tail.is_empty() {
55            self.tail.get(self.tail.len() - 1)
56        } else if !self.buffer.is_empty() {
57            self.buffer
58                .get(self.buffer.len() - 1)
59                .and_then(|v| v.get(v.len() - 1))
60        } else {
61            self.head.get(self.head.len() - 1)
62        }
63    }
64    pub fn get(&self, index: usize) -> Option<&E> {
65        if index >= self.size {
66            return None;
67        }
68        let head_remaining = self.head.len().saturating_sub(self.offset);
69        if index < head_remaining {
70            return self.head.get(self.offset + index);
71        }
72        let after = index - head_remaining;
73        let chunk = after / MAX_LENGTH;
74        let column = after % MAX_LENGTH;
75        if chunk < self.buffer.len() {
76            self.buffer.get(chunk).and_then(|v| v.get(column))
77        } else {
78            self.tail.get(column)
79        }
80    }
81    pub fn push_last(&self, value: E) -> Self {
82        let space = MAX_LENGTH - self.offset;
83        if self.size < space {
84            return Self {
85                size: self.size + 1,
86                head: self.head.push_last(value),
87                ..self.clone()
88            };
89        }
90        let tail = self.tail.push_last(value);
91        if tail.len() < MAX_LENGTH {
92            Self {
93                size: self.size + 1,
94                tail,
95                ..self.clone()
96            }
97        } else {
98            Self {
99                size: self.size + 1,
100                tail: Vector::new(),
101                buffer: self.buffer.push_last(tail),
102                ..self.clone()
103            }
104        }
105    }
106    pub fn push_first(&self, value: E) -> Self {
107        std::iter::once(value)
108            .chain(self.iter().cloned())
109            .collect::<Self>()
110            .with_meta(self.metadata.clone())
111    }
112    pub fn pop_first_value(&self) -> Self {
113        if self.size == 0 {
114            return self.clone();
115        }
116        let offset = self.offset + 1;
117        if offset < MAX_LENGTH {
118            return Self {
119                size: self.size - 1,
120                offset,
121                ..self.clone()
122            };
123        }
124        if self.buffer.is_empty() {
125            Self {
126                metadata: self.metadata.clone(),
127                size: self.size - 1,
128                offset: 0,
129                head: self.tail.clone(),
130                tail: Vector::new(),
131                buffer: self.buffer.clone(),
132            }
133        } else {
134            Self {
135                size: self.size - 1,
136                offset: 0,
137                head: self.buffer[0].clone(),
138                buffer: self.buffer.pop_first_value(),
139                ..self.clone()
140            }
141        }
142    }
143    pub fn pop_last_value(&self) -> Self {
144        if self.size == 0 {
145            return self.clone();
146        }
147        if !self.tail.is_empty() {
148            Self {
149                size: self.size - 1,
150                tail: self.tail.pop_last_value().expect("nonempty tail"),
151                ..self.clone()
152            }
153        } else if self.buffer.is_empty() {
154            Self {
155                size: self.size - 1,
156                head: self.head.pop_last_value().unwrap_or_else(Vector::new),
157                ..self.clone()
158            }
159        } else {
160            Self {
161                size: self.size - 1,
162                tail: self.buffer[self.buffer.len() - 1].clone(),
163                buffer: self.buffer.pop_last_value(),
164                ..self.clone()
165            }
166        }
167    }
168    pub fn iter(&self) -> impl Iterator<Item = &E> {
169        // Java Queue.Base.iterator (fixed): drop the first _offset head
170        // elements, then every buffer segment in order, then the tail.
171        self.head
172            .iter()
173            .skip(self.offset)
174            .chain(self.buffer.iter().flat_map(|segment| segment.iter()))
175            .chain(self.tail.iter())
176    }
177}
178impl<E: Clone> FromIterator<E> for Standard<E> {
179    fn from_iter<T: IntoIterator<Item = E>>(iter: T) -> Self {
180        iter.into_iter().fold(Self::new(), |q, v| q.push_last(v))
181    }
182}
183impl<E: Clone + PartialEq> PartialEq for Standard<E> {
184    fn eq(&self, other: &Self) -> bool {
185        self.size == other.size && self.iter().eq(other.iter())
186    }
187}
188impl<E: Clone> ICount for Standard<E> {
189    fn count(&self) -> usize {
190        self.size
191    }
192}
193impl<E: Clone> INth<E> for Standard<E> {
194    fn nth(&self, index: usize) -> Option<&E> {
195        self.get(index)
196    }
197}
198impl<E: Clone> IPeekFirst<E> for Standard<E> {
199    fn peek_first(&self) -> Option<E> {
200        Standard::peek_first(self).cloned()
201    }
202}
203impl<E: Clone> IPeekLast<E> for Standard<E> {
204    fn peek_last(&self) -> Option<E> {
205        Standard::peek_last(self).cloned()
206    }
207}
208impl<E: Clone> IPushLast<E> for Standard<E> {
209    type Output = Self;
210    fn push_last(&self, value: E) -> Self {
211        Standard::push_last(self, value)
212    }
213}
214impl<E: Clone> IPushFirst<E> for Standard<E> {
215    type Output = Self;
216    fn push_first(&self, value: E) -> Self {
217        Standard::push_first(self, value)
218    }
219}
220impl<E: Clone> IConj<E> for Standard<E> {
221    type Output = Self;
222    fn conj(&self, value: E) -> Self {
223        self.push_last(value)
224    }
225}
226impl<E: Clone> IPopFirst for Standard<E> {
227    type Output = Self;
228    fn pop_first(&self) -> Self {
229        self.pop_first_value()
230    }
231}
232impl<E: Clone> IPopLast for Standard<E> {
233    type Output = Self;
234    fn pop_last(&self) -> Self {
235        self.pop_last_value()
236    }
237}
238impl<E: Clone> IEmpty for Standard<E> {
239    type Output = Self;
240    fn empty(&self) -> Self {
241        Self::new().with_meta(self.metadata.clone())
242    }
243}
244impl<E: Clone> IMetadata for Standard<E> {
245    type Metadata = Rc<crate::lang::data::Metadata>;
246    fn meta(&self) -> Option<&Self::Metadata> {
247        self.metadata.as_ref()
248    }
249    fn with_meta(&self, metadata: Option<Self::Metadata>) -> Self {
250        Self {
251            metadata,
252            ..self.clone()
253        }
254    }
255}
256impl<E: Clone> IPersistent for Standard<E> {}
257
258impl<E: Clone> IntoIterator for Standard<E> {
259    type Item = E;
260    type IntoIter = std::vec::IntoIter<E>;
261    fn into_iter(self) -> Self::IntoIter {
262        self.iter().cloned().collect::<Vec<_>>().into_iter()
263    }
264}
265impl<E: Clone + PartialEq> IEquality for Standard<E> {
266    fn equality(&self, other: &Self) -> bool {
267        self == other
268    }
269}
270impl<E: Clone + std::fmt::Debug> IDisplay for Standard<E> {
271    fn display(&self) -> String {
272        format!(
273            "[{}]",
274            self.iter()
275                .map(|v| format!("{v:?}"))
276                .collect::<Vec<_>>()
277                .join(" ")
278        )
279    }
280}
281impl<E: Clone + std::hash::Hash + JavaHash> IHash for Standard<E> {
282    fn hash_calc(&self, hash_type: HashType) -> u64 {
283        // Java Queue extends ISequentialLookupType → ISequential:
284        // ordered composition, "::SEQUENTIAL" seed (see lang::hash).
285        crate::lang::hash::compose_ordered(
286            "SEQUENTIAL",
287            self.iter().map(|value| value.java_hash(hash_type)),
288        ) as u64
289    }
290}
291impl<E: Clone + std::fmt::Debug> IObjType for Standard<E> {
292    fn obj_type(&self) -> ObjType {
293        ObjType::Sequential
294    }
295}
296impl<E> IColl<E> for Standard<E>
297where
298    E: Clone + PartialEq + std::fmt::Debug + std::hash::Hash + JavaHash,
299{
300    fn start_string(&self) -> &'static str {
301        "["
302    }
303    fn end_string(&self) -> &'static str {
304        "]"
305    }
306}
307
308#[derive(Debug, Clone, Default, PartialEq)]
309pub struct Mutable<E: Clone> {
310    value: Standard<E>,
311}
312impl<E: Clone> Mutable<E> {
313    pub fn new() -> Self {
314        Self {
315            value: Standard::new(),
316        }
317    }
318    pub fn len(&self) -> usize {
319        self.value.len()
320    }
321    pub fn is_empty(&self) -> bool {
322        self.value.is_empty()
323    }
324    pub fn get(&self, index: usize) -> Option<&E> {
325        self.value.get(index)
326    }
327    pub fn peek_first(&self) -> Option<&E> {
328        self.value.peek_first()
329    }
330    pub fn peek_last(&self) -> Option<&E> {
331        self.value.peek_last()
332    }
333    pub fn push_last(&mut self, value: E) -> &mut Self {
334        self.value = self.value.push_last(value);
335        self
336    }
337    pub fn push_first(&mut self, value: E) -> &mut Self {
338        self.value = self.value.push_first(value);
339        self
340    }
341    pub fn pop_first(&mut self) -> &mut Self {
342        self.value = self.value.pop_first_value();
343        self
344    }
345    pub fn pop_last(&mut self) -> &mut Self {
346        self.value = self.value.pop_last_value();
347        self
348    }
349    pub fn empty(&mut self) -> &mut Self {
350        self.value = Standard::new();
351        self
352    }
353    pub fn iter(&self) -> impl Iterator<Item = &E> {
354        self.value.iter()
355    }
356}
357impl<E: Clone> FromIterator<E> for Mutable<E> {
358    fn from_iter<T: IntoIterator<Item = E>>(iter: T) -> Self {
359        Self {
360            value: iter.into_iter().collect(),
361        }
362    }
363}
364impl<E: Clone> IMutable for Mutable<E> {}
365impl<E: Clone> IToPersistent for Mutable<E> {
366    type Persistent = Standard<E>;
367    fn to_persistent(&mut self) -> Self::Persistent {
368        self.value.clone()
369    }
370}
371impl<E: Clone> IToMutable for Standard<E> {
372    type Mutable = Mutable<E>;
373    fn to_mutable(&self) -> Self::Mutable {
374        Mutable {
375            value: self.clone(),
376        }
377    }
378}
379
380#[cfg(test)]
381mod tests {
382    use super::{Standard, MAX_LENGTH};
383    #[test]
384    fn crosses_head_buffer_tail_boundaries() {
385        let q = (0..(MAX_LENGTH * 2 + 9)).collect::<Standard<_>>();
386        assert_eq!(q.get(0), Some(&0));
387        assert_eq!(q.get(MAX_LENGTH), Some(&MAX_LENGTH));
388        assert_eq!(q.peek_last(), Some(&(MAX_LENGTH * 2 + 8)));
389        let p = q.pop_first_value();
390        assert_eq!(p.peek_first(), Some(&1));
391        assert_eq!(q.peek_first(), Some(&0));
392    }
393    #[test]
394    fn pop_last_preserves_previous() {
395        let q = (0..1030).collect::<Standard<_>>();
396        let p = q.pop_last_value();
397        assert_eq!(q.peek_last(), Some(&1029));
398        assert_eq!(p.peek_last(), Some(&1028));
399    }
400    #[test]
401    fn push_first_preserves_order_and_previous_value() {
402        let queue = (1..=3).collect::<Standard<_>>();
403        let pushed = queue.push_first(0);
404        assert_eq!(queue.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
405        assert_eq!(pushed.iter().copied().collect::<Vec<_>>(), vec![0, 1, 2, 3]);
406    }
407    #[test]
408    fn persistent_operations_preserve_metadata() {
409        use crate::lang::protocol::{IEmpty, IMetadata};
410        let queue = Standard::from_iter(0..(MAX_LENGTH + 2))
411            .with_meta(Some(crate::lang::data::Metadata::document("doc")));
412        let values = [
413            queue.push_last(9999),
414            queue.pop_first_value(),
415            queue.pop_last_value(),
416            queue.empty(),
417        ];
418        assert!(values
419            .iter()
420            .all(|value| value.meta().map(|m| m.doc().unwrap()) == Some("doc")));
421    }
422
423    #[test]
424    fn mutable_round_trip_crosses_chunk_boundaries() {
425        use crate::lang::protocol::{IToMutable, IToPersistent};
426        let original = (0..(MAX_LENGTH + 3)).collect::<Standard<_>>();
427        let mut mutable = original.to_mutable();
428        mutable.pop_first().pop_last().push_last(9999);
429        assert_eq!(mutable.peek_first(), Some(&1));
430        assert_eq!(mutable.peek_last(), Some(&9999));
431        let persistent = mutable.to_persistent();
432        assert_eq!(persistent.peek_first(), Some(&1));
433        assert_eq!(persistent.peek_last(), Some(&9999));
434        assert_eq!(original.peek_first(), Some(&0));
435    }
436
437    #[test]
438    fn pop_first_promotes_tail_to_head_across_segment() {
439        // 1030 pushes: head fills to 1024, the remaining 6 go to the tail.
440        let queue = (0..1030).collect::<Standard<_>>();
441        assert_eq!(queue.head.len(), MAX_LENGTH);
442        assert_eq!(queue.tail.len(), 6);
443        // 1024 pops push offset to 1024: head is replaced by the former
444        // (short) tail and offset resets (Java popFirst, buffer empty).
445        let queue = (0..MAX_LENGTH).fold(queue, |q, _| q.pop_first_value());
446        assert_eq!(queue.offset, 0);
447        assert_eq!(queue.head.len(), 6);
448        assert!(queue.tail.is_empty());
449        assert_eq!(
450            queue.iter().copied().collect::<Vec<_>>(),
451            (1024..1030).collect::<Vec<_>>()
452        );
453        // iteration and nth respect the offset into the promoted short head
454        let queue = queue.pop_first_value();
455        assert_eq!(queue.offset, 1);
456        assert_eq!(
457            queue.iter().copied().collect::<Vec<_>>(),
458            vec![1025, 1026, 1027, 1028, 1029]
459        );
460        assert_eq!(queue.get(0), Some(&1025));
461        assert_eq!(queue.get(4), Some(&1029));
462        assert_eq!(queue.get(5), None);
463    }
464
465    #[test]
466    fn nth_probes_across_head_buffer_and_tail() {
467        // 2500 pushes, 100 pops: offset 100 into head, one buffer segment,
468        // 452-element tail (Java nth segment computation).
469        let queue = (0..2500).collect::<Standard<_>>();
470        let queue = (0..100).fold(queue, |q, _| q.pop_first_value());
471        assert_eq!(queue.offset, 100);
472        assert_eq!(queue.buffer.len(), 1);
473        assert_eq!(queue.len(), 2400);
474        for (index, value) in [
475            (0, 100),
476            (923, 1023),
477            (924, 1024),
478            (1947, 2047),
479            (1948, 2048),
480            (2399, 2499),
481        ] {
482            assert_eq!(queue.get(index), Some(&value));
483        }
484        assert_eq!(queue.iter().next(), Some(&100));
485        assert_eq!(queue.iter().last(), Some(&2499));
486        assert_eq!(queue.iter().count(), 2400);
487    }
488
489    #[test]
490    fn pop_last_promotes_last_buffer_segment_to_tail() {
491        // Java popLast quirk, pinned for parity: when the tail is empty and
492        // the buffer is not, the last buffer segment becomes the tail
493        // WITHOUT dropping an element — only _size decrements, so the
494        // segment iterator still yields the retained last element.
495        // Build the quirk state directly: head + 1 buffer segment + empty tail.
496        let queue = (0..(2 * MAX_LENGTH + 1)).collect::<Standard<_>>();
497        let queue = queue.pop_last_value(); // tail 1 -> empty
498        assert!(queue.tail.is_empty());
499        assert_eq!(queue.buffer.len(), 1);
500        let queue = queue.pop_last_value(); // promotes buffer segment, no drop
501        assert!(queue.buffer.is_empty());
502        assert_eq!(queue.tail.len(), MAX_LENGTH);
503        assert_eq!(queue.len(), 2 * MAX_LENGTH - 1);
504        assert_eq!(queue.peek_last(), Some(&(2 * MAX_LENGTH - 1)));
505        // segment iterator (Java parity) still sees the retained element
506        assert_eq!(queue.iter().count(), 2 * MAX_LENGTH);
507        assert_eq!(queue.iter().last(), Some(&(2 * MAX_LENGTH - 1)));
508    }
509}
hara_native/lang/data/queue.rs

hara_native/lang/data/
queue.rs
