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