1use collection::{Collection, Disposable};
2
3use crate::error::StackError;
4use crate::traits::{CircularStackLike, StackLike};
5
6#[derive(Debug)]
7pub struct CircularStack<T> {
8 elements: Vec<Option<T>>,
9 capacity: usize,
10 size: usize,
11 start: usize,
12 end: usize,
13 disposed: bool,
14}
15
16impl<T> CircularStack<T> {
17 pub fn new(capacity: usize) -> Result<Self, StackError> {
18 if capacity == 0 {
19 return Err(StackError::InvalidCapacity { capacity });
20 }
21
22 Ok(Self {
23 elements: empty_buffer(capacity),
24 capacity,
25 size: 0,
26 start: 0,
27 end: 0,
28 disposed: false,
29 })
30 }
31
32 pub fn fork(&self) -> Self
33 where
34 T: Clone,
35 {
36 self.clone()
37 }
38
39 fn fork_snapshot(&self) -> Self
40 where
41 T: Clone,
42 {
43 let mut elements = empty_buffer(self.capacity);
44 for offset in 0..self.size {
45 let src = self.physical_index(offset);
46 let item = self.elements[src]
47 .as_ref()
48 .expect("stack item must exist")
49 .clone();
50 elements[offset] = Some(item);
51 }
52
53 Self {
54 elements,
55 capacity: self.capacity,
56 size: self.size,
57 start: 0,
58 end: if self.size == 0 { 0 } else { self.size - 1 },
59 disposed: self.disposed,
60 }
61 }
62
63 fn do_push(&mut self, element: T) {
64 if self.size == 0 {
65 self.elements[0] = Some(element);
66 self.size = 1;
67 self.start = 0;
68 self.end = 0;
69 return;
70 }
71
72 self.end = self.next_index(self.end);
73 self.elements[self.end] = Some(element);
74
75 if self.size < self.capacity {
76 self.size += 1;
77 } else {
78 self.start = self.next_index(self.start);
79 }
80 }
81
82 fn do_pop(&mut self) -> Option<T> {
83 if self.size == 0 {
84 return None;
85 }
86
87 let removed = self.elements[self.end].take();
88 debug_assert!(removed.is_some());
89
90 if self.size == 1 {
91 self.size = 0;
92 self.start = 0;
93 self.end = 0;
94 return removed;
95 }
96
97 self.size -= 1;
98 self.end = self.prev_index(self.end);
99 removed
100 }
101
102 fn do_replace_top(&mut self, new_top: T) -> Option<T> {
103 if self.size == 0 {
104 self.elements[0] = Some(new_top);
105 self.size = 1;
106 self.start = 0;
107 self.end = 0;
108 return None;
109 }
110
111 let removed = self.elements[self.end].replace(new_top);
112 debug_assert!(removed.is_some());
113 removed
114 }
115
116 fn clear_internal(&mut self) {
117 for offset in 0..self.size {
118 let idx = self.physical_index(offset);
119 self.elements[idx].take();
120 }
121 self.size = 0;
122 self.start = 0;
123 self.end = 0;
124 }
125
126 fn shrink_keep_latest(&mut self, new_capacity: usize) {
127 if self.size <= new_capacity {
128 return;
129 }
130
131 let previous_size = self.size;
132 let drop_count = previous_size - new_capacity;
133
134 for i in 0..new_capacity {
135 self.elements[i] = self.elements[drop_count + i].take();
136 }
137 for i in new_capacity..previous_size {
138 self.elements[i] = None;
139 }
140
141 self.size = new_capacity;
142 }
143
144 fn rearrange_impl(&mut self) {
145 if self.size == 0 {
146 self.start = 0;
147 self.end = 0;
148 return;
149 }
150 if self.start == 0 {
151 return;
152 }
153
154 let capacity = self.capacity;
155 let size = self.size;
156 let start = self.start;
157 let end = self.end;
158
159 let is_dense = (size as u128) * 4 >= (capacity as u128) * 3;
163 if is_dense {
164 self.elements.rotate_left(start);
165 self.start = 0;
166 self.end = size - 1;
167 return;
168 }
169
170 if start <= end {
171 for i in 0..size {
172 let src = start + i;
173 self.elements[i] = self.elements[src].take();
174 }
175 } else {
176 let first_len = capacity - start;
177
178 let mut tail = Vec::with_capacity(end + 1);
179 for i in 0..=end {
180 tail.push(self.elements[i].take());
181 }
182
183 for i in 0..first_len {
184 let src = start + i;
185 self.elements[i] = self.elements[src].take();
186 }
187
188 for (i, value) in tail.into_iter().enumerate() {
189 self.elements[first_len + i] = value;
190 }
191 }
192
193 self.start = 0;
194 self.end = size - 1;
195 }
196
197 fn physical_index(&self, offset: usize) -> usize {
198 (self.start + offset) % self.capacity
199 }
200
201 fn physical_index_from_top(&self, offset: usize) -> usize {
202 let off = offset % self.capacity;
203 if self.end >= off {
204 self.end - off
205 } else {
206 self.capacity + self.end - off
207 }
208 }
209
210 fn next_index(&self, index: usize) -> usize {
211 let next = index + 1;
212 if next == self.capacity { 0 } else { next }
213 }
214
215 fn prev_index(&self, index: usize) -> usize {
216 if index == 0 {
217 self.capacity - 1
218 } else {
219 index - 1
220 }
221 }
222}
223
224impl<T> Clone for CircularStack<T>
225where
226 T: Clone,
227{
228 fn clone(&self) -> Self {
229 self.fork_snapshot()
230 }
231}
232
233impl<T> StackLike<T> for CircularStack<T> {
234 fn top(&self) -> Option<&T> {
235 if self.size == 0 {
236 return None;
237 }
238 self.elements[self.end].as_ref()
239 }
240
241 fn push(&mut self, element: T) {
242 self.do_push(element);
243 }
244
245 fn pop(&mut self) -> Option<T> {
246 self.do_pop()
247 }
248
249 fn pushes<I>(&mut self, elements: I)
250 where
251 I: IntoIterator<Item = T>,
252 {
253 let capacity = self.capacity;
254 let mut size = self.size;
255 let mut start = self.start;
256 let mut end = if size == 0 { capacity - 1 } else { self.end };
257
258 let mut inserted = 0usize;
259 for element in elements {
260 inserted += 1;
261 size += 1;
262 end = if end + 1 == capacity { 0 } else { end + 1 };
263 self.elements[end] = Some(element);
264 }
265
266 if inserted == 0 {
267 return;
268 }
269
270 if size > capacity {
271 let shift = size - capacity;
272 size = capacity;
273 start = (start + shift) % capacity;
274 }
275
276 self.size = size;
277 self.start = start;
278 self.end = end;
279 }
280
281 fn replace_top(&mut self, new_top: T) -> Option<T> {
282 self.do_replace_top(new_top)
283 }
284}
285
286impl<T> CircularStackLike<T> for CircularStack<T> {
287 type Error = StackError;
288
289 fn capacity(&self) -> usize {
290 self.capacity
291 }
292
293 fn at(&self, index: isize) -> Option<&T> {
294 if index < 0 || index as usize >= self.size {
295 return None;
296 }
297
298 let idx = self.physical_index(index as usize);
299 self.elements[idx].as_ref()
300 }
301
302 fn update(&mut self, index: isize, element: T) -> bool {
303 if index < 0 || index as usize >= self.size {
304 return false;
305 }
306
307 let idx = self.physical_index(index as usize);
308 self.elements[idx] = Some(element);
309 true
310 }
311
312 fn resize(&mut self, new_capacity: usize) -> Result<(), Self::Error> {
313 if new_capacity == 0 {
314 return Err(StackError::InvalidCapacity {
315 capacity: new_capacity,
316 });
317 }
318
319 if new_capacity == self.capacity {
320 return Ok(());
321 }
322
323 if new_capacity > self.capacity {
324 let is_wrapped = self.size > 0 && self.start > self.end;
325 if is_wrapped {
326 self.rearrange_impl();
327 self.start = 0;
328 self.end = if self.size == 0 { 0 } else { self.size - 1 };
329 }
330
331 self.elements.resize_with(new_capacity, || None);
332 self.capacity = new_capacity;
333 return Ok(());
334 }
335
336 if self.start != 0 {
337 self.rearrange_impl();
338 }
339 self.shrink_keep_latest(new_capacity);
340
341 self.elements.truncate(new_capacity);
342
343 self.capacity = new_capacity;
344 self.start = 0;
345 self.end = if self.size == 0 { 0 } else { self.size - 1 };
346 Ok(())
347 }
348
349 fn rearrange(&mut self) {
350 self.rearrange_impl();
351 }
352}
353
354impl<T> Collection for CircularStack<T> {
355 type Item = T;
356 type Iter<'a>
357 = Iter<'a, T>
358 where
359 Self: 'a;
360
361 fn iter(&self) -> Self::Iter<'_> {
362 Iter {
363 stack: self,
364 offset: 0,
365 }
366 }
367
368 fn size(&self) -> usize {
369 self.size
370 }
371
372 fn clear(&mut self) {
373 self.clear_internal();
374 }
375
376 fn retain<F>(&mut self, mut f: F) -> usize
377 where
378 F: FnMut(&Self::Item) -> bool,
379 {
380 let original_size = self.size;
381 if original_size == 0 {
382 return 0;
383 }
384
385 self.rearrange_impl();
386
387 let mut kept_size = 0usize;
388 for read_idx in 0..original_size {
389 let item = self.elements[read_idx]
390 .take()
391 .expect("stack item must exist");
392 if f(&item) {
393 self.elements[kept_size] = Some(item);
394 kept_size += 1;
395 }
396 }
397
398 self.size = kept_size;
399 self.start = 0;
400 self.end = if kept_size == 0 { 0 } else { kept_size - 1 };
401
402 original_size - kept_size
403 }
404}
405
406impl<T> Disposable for CircularStack<T> {
407 fn dispose(&mut self) {
408 self.disposed = true;
409 self.clear_internal();
410 }
411
412 fn is_disposed(&self) -> bool {
413 self.disposed
414 }
415}
416
417pub struct Iter<'a, T> {
418 stack: &'a CircularStack<T>,
419 offset: usize,
420}
421
422impl<'a, T> Iterator for Iter<'a, T> {
423 type Item = &'a T;
424
425 fn next(&mut self) -> Option<Self::Item> {
426 if self.offset >= self.stack.size {
427 return None;
428 }
429
430 let idx = self.stack.physical_index_from_top(self.offset);
431 self.offset += 1;
432 self.stack.elements[idx].as_ref()
433 }
434
435 fn size_hint(&self) -> (usize, Option<usize>) {
436 let remain = self.stack.size - self.offset;
437 (remain, Some(remain))
438 }
439}
440
441impl<T> ExactSizeIterator for Iter<'_, T> {}
442
443impl<'a, T> IntoIterator for &'a CircularStack<T> {
444 type Item = &'a T;
445 type IntoIter = Iter<'a, T>;
446
447 fn into_iter(self) -> Self::IntoIter {
448 self.iter()
449 }
450}
451
452fn empty_buffer<T>(capacity: usize) -> Vec<Option<T>> {
453 std::iter::repeat_with(|| None).take(capacity).collect()
454}
455
456#[cfg(test)]
457mod tests {
458 use collection::{Collection, Disposable};
459
460 use crate::traits::{CircularStackLike, StackLike};
461
462 use super::CircularStack;
463 use crate::error::StackError;
464
465 fn as_vec_top<T: Clone>(q: &CircularStack<T>) -> Vec<T> {
466 Collection::collect(q)
467 }
468
469 #[test]
470 fn constructor_should_validate_capacity() {
471 assert!(matches!(
472 CircularStack::<i32>::new(0),
473 Err(StackError::InvalidCapacity { capacity: 0 })
474 ));
475 assert!(CircularStack::<i32>::new(1).is_ok());
476 }
477
478 #[test]
479 fn stack_like_ops_should_work() {
480 let mut s = CircularStack::new(4).expect("new should work");
481
482 assert_eq!(s.top(), None);
483 assert_eq!(s.pop(), None);
484
485 s.pushes([1, 2, 3, 4]);
486 assert_eq!(as_vec_top(&s), vec![4, 3, 2, 1]);
487 assert_eq!(s.top(), Some(&4));
488
489 s.push(5);
490 assert_eq!(as_vec_top(&s), vec![5, 4, 3, 2]);
491 assert_eq!(s.at(0), Some(&2));
492 assert_eq!(s.at(3), Some(&5));
493
494 assert_eq!(s.replace_top(8), Some(5));
495 assert_eq!(as_vec_top(&s), vec![8, 4, 3, 2]);
496
497 assert_eq!(s.pop(), Some(8));
498 assert_eq!(as_vec_top(&s), vec![4, 3, 2]);
499 }
500
501 #[test]
502 fn push_pop_and_replace_top_should_handle_single_and_empty_states() {
503 let mut s = CircularStack::new(3).expect("new should work");
504
505 assert_eq!(s.replace_top(10), None);
506 assert_eq!(as_vec_top(&s), vec![10]);
507
508 assert_eq!(s.pop(), Some(10));
509 assert!(s.is_empty());
510
511 s.push(20);
512 assert_eq!(s.top(), Some(&20));
513 assert_eq!(as_vec_top(&s), vec![20]);
514 }
515
516 #[test]
517 fn pushes_should_support_empty_input_without_side_effects() {
518 let mut s = CircularStack::new(4).expect("new should work");
519
520 s.pushes(std::iter::empty());
521 assert!(s.is_empty());
522
523 s.pushes([1, 2]);
524 s.pushes(std::iter::empty());
525 assert_eq!(as_vec_top(&s), vec![2, 1]);
526 }
527
528 #[test]
529 fn at_and_update_should_work() {
530 let mut s = CircularStack::new(4).expect("new should work");
531
532 s.pushes([1, 2, 3, 4, 5]);
533 assert_eq!(as_vec_top(&s), vec![5, 4, 3, 2]);
534 assert_eq!(s.at(-1), None);
535 assert_eq!(s.at(0), Some(&2));
536 assert_eq!(s.at(1), Some(&3));
537 assert_eq!(s.at(2), Some(&4));
538 assert_eq!(s.at(3), Some(&5));
539 assert_eq!(s.at(4), None);
540
541 assert!(s.update(1, -3));
542 assert_eq!(s.at(1), Some(&-3));
543 assert_eq!(as_vec_top(&s), vec![5, 4, -3, 2]);
544
545 assert!(!s.update(-1, 9));
546 assert!(!s.update(4, 9));
547 assert_eq!(as_vec_top(&s), vec![5, 4, -3, 2]);
548 }
549
550 #[test]
551 fn resize_should_keep_latest_on_shrink_and_support_growth() {
552 let mut s = CircularStack::new(4).expect("new should work");
553
554 s.pushes([1, 2, 3, 4]);
555 s.resize(3).expect("resize should work");
556 assert_eq!(s.capacity(), 3);
557 assert_eq!(as_vec_top(&s), vec![4, 3, 2]);
558
559 s.push(5);
560 assert_eq!(as_vec_top(&s), vec![5, 4, 3]);
561
562 s.resize(5).expect("resize should work");
563 s.push(6);
564 assert_eq!(s.capacity(), 5);
565 assert_eq!(as_vec_top(&s), vec![6, 5, 4, 3]);
566
567 s.resize(2).expect("resize should work");
568 assert_eq!(s.capacity(), 2);
569 assert_eq!(as_vec_top(&s), vec![6, 5]);
570 }
571
572 #[test]
573 fn resize_grow_should_preserve_order_for_shifted_non_wrapped_state() {
574 let mut s = CircularStack::new(5).expect("new should work");
575 s.pushes([1, 2, 3, 4, 5, 6, 7]);
576
577 assert_eq!(s.pop(), Some(7));
578 assert_eq!(s.pop(), Some(6));
579 assert_eq!(as_vec_top(&s), vec![5, 4, 3]);
580
581 s.resize(8).expect("resize should work");
582 assert_eq!(s.capacity(), 8);
583 assert_eq!(as_vec_top(&s), vec![5, 4, 3]);
584 assert_eq!(s.at(0), Some(&3));
585 assert_eq!(s.at(2), Some(&5));
586
587 s.push(8);
588 assert_eq!(as_vec_top(&s), vec![8, 5, 4, 3]);
589
590 s.resize(8).expect("resize should work");
591 assert_eq!(as_vec_top(&s), vec![8, 5, 4, 3]);
592 }
593
594 #[test]
595 fn resize_should_reject_zero_capacity() {
596 let mut s = CircularStack::<i32>::new(5).expect("new should work");
597
598 assert_eq!(
599 s.resize(0),
600 Err(StackError::InvalidCapacity { capacity: 0 })
601 );
602 }
603
604 #[test]
605 fn rearrange_should_preserve_order_for_dense_wrapped_state() {
606 let mut s = CircularStack::new(8).expect("new should work");
607 s.pushes(1..=10);
608
609 let before = as_vec_top(&s);
610 s.rearrange();
611 assert_eq!(as_vec_top(&s), before);
612
613 s.push(11);
614 assert_eq!(as_vec_top(&s), vec![11, 10, 9, 8, 7, 6, 5, 4]);
615 }
616
617 #[test]
618 fn rearrange_should_handle_empty_and_sparse_shifted_non_wrapped_state() {
619 let mut s = CircularStack::new(10).expect("new should work");
620
621 s.rearrange();
622 assert!(s.is_empty());
623
624 s.pushes(1..=12);
625 for _ in 0..3 {
626 assert!(s.pop().is_some());
627 }
628
629 let before = as_vec_top(&s);
630 s.rearrange();
631 assert_eq!(as_vec_top(&s), before);
632
633 s.push(13);
634 assert_eq!(as_vec_top(&s), vec![13, 9, 8, 7, 6, 5, 4, 3]);
635 }
636
637 #[test]
638 fn rearrange_should_preserve_order_for_sparse_wrapped_state() {
639 let mut s = CircularStack::new(16).expect("new should work");
640 s.pushes(1..=30);
641 for _ in 0..12 {
642 assert!(s.pop().is_some());
643 }
644
645 let before = as_vec_top(&s);
646 s.rearrange();
647 assert_eq!(as_vec_top(&s), before);
648
649 s.pushes([31, 32]);
650 assert_eq!(as_vec_top(&s), vec![32, 31, 18, 17, 16, 15]);
651 }
652
653 #[test]
654 fn retain_should_filter_and_preserve_order() {
655 let mut s = CircularStack::new(6).expect("new should work");
656 s.pushes([1, 2, 3, 4, 5, 6, 7, 8]);
657
658 let removed = s.retain(|x| *x % 2 == 0);
659 assert_eq!(removed, 3);
660 assert_eq!(as_vec_top(&s), vec![8, 6, 4]);
661
662 let removed_none = s.retain(|_| true);
663 assert_eq!(removed_none, 0);
664 assert_eq!(as_vec_top(&s), vec![8, 6, 4]);
665
666 let removed_all = s.retain(|_| false);
667 assert_eq!(removed_all, 3);
668 assert!(s.is_empty());
669 }
670
671 #[test]
672 fn retain_should_return_zero_on_empty_stack() {
673 let mut s = CircularStack::<i32>::new(4).expect("new should work");
674
675 let removed = s.retain(|_| true);
676 assert_eq!(removed, 0);
677 assert!(s.is_empty());
678 }
679
680 #[test]
681 fn iter_and_into_iter_should_report_exact_size_hint() {
682 let mut s = CircularStack::new(4).expect("new should work");
683 s.pushes([1, 2, 3]);
684
685 let mut it = s.iter();
686 assert_eq!(it.size_hint(), (3, Some(3)));
687 assert_eq!(it.next(), Some(&3));
688 assert_eq!(it.size_hint(), (2, Some(2)));
689 assert_eq!(it.next(), Some(&2));
690 assert_eq!(it.next(), Some(&1));
691 assert_eq!(it.size_hint(), (0, Some(0)));
692 assert_eq!(it.next(), None);
693
694 let from_into_iter: Vec<i32> = (&s).into_iter().copied().collect();
695 assert_eq!(from_into_iter, vec![3, 2, 1]);
696 }
697
698 #[test]
699 fn collection_and_dispose_contract_should_work() {
700 let mut s = CircularStack::new(6).expect("new should work");
701 s.pushes([1, 2, 3, 4, 5, 6]);
702
703 assert_eq!(Collection::size(&s), 6);
704 assert_eq!(Collection::count(&s, |x| *x % 2 == 0), 3);
705 assert_eq!(Collection::collect(&s), vec![6, 5, 4, 3, 2, 1]);
706
707 let removed = Collection::retain(&mut s, |x| *x % 2 == 1);
708 assert_eq!(removed, 3);
709 assert_eq!(Collection::collect(&s), vec![5, 3, 1]);
710
711 Collection::clear(&mut s);
712 assert!(Collection::is_empty(&s));
713
714 assert!(!s.is_disposed());
715 s.pushes([7, 8]);
716 s.dispose();
717 assert!(s.is_disposed());
718 assert!(s.is_empty());
719 }
720
721 #[test]
722 fn circular_stack_like_ops_should_work() {
723 let mut s = CircularStack::new(5).expect("new should work");
724
725 s.pushes([1, 2, 3, 4, 5, 6]);
726 assert_eq!(s.capacity(), 5);
727 assert_eq!(as_vec_top(&s), vec![6, 5, 4, 3, 2]);
728
729 assert_eq!(s.at(0), Some(&2));
730 assert_eq!(s.at(4), Some(&6));
731 assert_eq!(s.at(5), None);
732
733 assert!(s.update(2, 40));
734 assert_eq!(as_vec_top(&s), vec![6, 5, 40, 3, 2]);
735
736 s.rearrange();
737 assert_eq!(as_vec_top(&s), vec![6, 5, 40, 3, 2]);
738
739 s.resize(3).expect("resize should work");
740 assert_eq!(as_vec_top(&s), vec![6, 5, 40]);
741 }
742
743 #[test]
744 fn fork_should_create_independent_snapshot() {
745 let mut s = CircularStack::new(5).expect("new should work");
746 s.pushes([1, 2, 3, 4, 5, 6, 7]);
747
748 let mut forked = StackLike::fork(&s);
749 assert_eq!(as_vec_top(&s), as_vec_top(&forked));
750 assert_eq!(s.capacity(), forked.capacity());
751
752 s.push(8);
753 assert_eq!(as_vec_top(&s), vec![8, 7, 6, 5, 4]);
754 assert_eq!(as_vec_top(&forked), vec![7, 6, 5, 4, 3]);
755
756 forked.push(9);
757 assert_eq!(as_vec_top(&forked), vec![9, 7, 6, 5, 4]);
758 assert_eq!(as_vec_top(&s), vec![8, 7, 6, 5, 4]);
759 }
760
761 #[test]
762 fn fork_should_preserve_wrapped_layout_observable_behavior() {
763 let mut s = CircularStack::new(8).expect("new should work");
764 s.pushes(1..=12);
765 for _ in 0..3 {
766 assert!(s.pop().is_some());
767 }
768 s.pushes([13, 14]);
769
770 let forked = s.fork();
771 assert_eq!(as_vec_top(&forked), as_vec_top(&s));
772 assert_eq!(forked.capacity(), s.capacity());
773
774 for i in 0..s.size() {
775 assert_eq!(forked.at(i as isize), s.at(i as isize));
776 }
777 }
778}