rudac/queue/
circular.rs

1/// A circular buffer, circular queue, ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.
2/// This structure lends itself easily to buffering data streams.
3///
4/// # Examples
5/// ```
6/// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
7///
8/// circular_buffer.enqueue(1);
9///
10/// match circular_buffer.dequeue() {
11///     Some(data) => assert_eq!(*data, 1),
12///     None => panic!("Data must not be empty")
13/// }
14/// ```
15///
16#[derive(Debug)]
17pub struct Circular<T> {
18    front_index: usize,
19    rear_index: usize,
20    size: usize,
21    internal_vec: Vec<T>,
22    capacity: usize,
23    push_enabled: bool,
24}
25
26impl<T> Circular<T> {
27    /// Creates a new instance of circular queue
28    ///
29    /// # Arguments
30    /// * `capacity` - capacity of the queue. note that the real capacity is equal to capacity determined by the argument + 1
31    ///
32    /// # Examples
33    /// ```
34    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
35    /// ```
36    pub fn new(capacity: usize) -> Circular<T> {
37        Circular {
38            front_index: 0,
39            rear_index: 0,
40            internal_vec: Vec::with_capacity(std::cmp::max(capacity + 1, 1)),
41            size: 0,
42            push_enabled: true,
43            capacity: std::cmp::max(capacity + 1, 1),
44        }
45    }
46
47    /// Returns number of items in the queue
48    ///
49    /// # Examples
50    /// ```
51    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
52    /// assert_eq!(circular_buffer.size(), 0);
53    ///
54    /// circular_buffer.enqueue(1);
55    /// assert_eq!(circular_buffer.size(), 1);
56    /// ```
57    pub fn size(&self) -> usize {
58        return self.size;
59    }
60
61    /// Returns wether queue is empty or not. this implies wether size is equal to 0 or not.
62    /// capacity will stay the same.
63    ///
64    /// # Examples
65    /// ```
66    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
67    /// assert_eq!(circular_buffer.empty(), true);
68    ///
69    /// circular_buffer.enqueue(1);
70    /// assert_eq!(circular_buffer.empty(), false);
71    /// ```
72    pub fn empty(&self) -> bool {
73        return self.size == 0;
74    }
75
76    /// Returns true if there are no more room for inserting new items.
77    ///
78    /// # Examples
79    /// ```
80    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
81    /// assert_eq!(circular_buffer.full(), false);
82    ///
83    /// circular_buffer.enqueue(1);
84    /// assert_eq!(circular_buffer.full(), true);
85    /// ```
86    pub fn full(&self) -> bool {
87        return (self.rear_index + 1) % self.capacity == self.front_index;
88    }
89
90    /// If queue is not full it will insert an element at the end of the queue.
91    /// If queue is full, oldest item will be discarded and new item will be inserted at the end of the queue.
92    ///
93    /// # Arguments
94    /// * `element`: item to be inserted in the queue
95    ///
96    /// # Examples
97    /// ```
98    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
99    ///
100    /// circular_buffer.enqueue(1);
101    /// ```
102    pub fn enqueue(&mut self, element: T) {
103        // enqueue is only possible on queue with capacity > 1
104        // if capacity of queue is not enough then do nothing
105        if self.capacity <= 1 {
106            return;
107        }
108
109        // check if queue is full
110        if self.full() {
111            self.front_index = (self.front_index + 1) % self.capacity;
112
113            self.size -= 1;
114        }
115
116        if self.push_enabled {
117            self.internal_vec.push(element);
118        } else {
119            self.internal_vec[self.rear_index] = element;
120        }
121
122        self.push_enabled = !(self.rear_index + 1 == self.capacity) & self.push_enabled;
123
124        self.rear_index = (self.rear_index + 1) % self.capacity;
125
126        self.size += 1;
127    }
128
129    /// Returns and discards the item at the front of the queue.
130    /// Returns None if there are no items in the queue.
131    ///
132    /// # Examples
133    /// ```
134    /// let mut circular_buffer: rudac::queue::Circular<usize> = rudac::queue::Circular::new(1);
135    ///
136    /// circular_buffer.enqueue(1);
137    ///
138    /// match circular_buffer.dequeue() {
139    ///     Some(data) => assert_eq!(*data, 1),
140    ///     None => panic!("Data must not be empty")
141    /// }
142    /// ```
143    pub fn dequeue(&mut self) -> Option<&T> {
144        if self.empty() {
145            return None;
146        }
147
148        let element: &T = &self.internal_vec[self.front_index];
149
150        self.front_index = (self.front_index + 1) % self.capacity;
151
152        self.size -= 1;
153
154        return Some(element);
155    }
156
157    /// Transforms each element in the queue using the transform function provided
158    ///
159    /// # Arguments
160    /// * `transform`: function that transforms each element of the queue and returns that transformed element
161    ///
162    /// # Examples
163    /// ```
164    /// fn all_caps(text: &String) -> String {
165    ///     return text.to_uppercase();
166    /// }
167    ///
168    /// let mut circular_buffer: rudac::queue::Circular<String> = rudac::queue::Circular::new(1);
169    ///
170    /// circular_buffer.enqueue(String::from("element"));
171    ///
172    /// circular_buffer.map(all_caps);
173    ///
174    /// match circular_buffer.dequeue() {
175    ///     Some(data) => assert_eq!(*data, String::from("ELEMENT")),
176    ///     None => panic!("Data must not be None")
177    /// }
178    /// ```
179    pub fn map(&mut self, transform: fn(&T) -> T) {
180        for i in 0..self.size() {
181            self[i] = transform(&self[i]);
182        }
183    }
184
185    /// Transforms each element in the queue using the transform closure provided
186    ///
187    /// # Arguments
188    /// * `transform`: closure that transforms each element of the queue and returns that transformed element
189    ///
190    /// # Examples
191    /// ```
192    /// let mut circular_buffer: rudac::queue::Circular<String> = rudac::queue::Circular::new(1);
193    ///
194    /// circular_buffer.enqueue(String::from("element"));
195    ///
196    /// circular_buffer.map_closure(|text: &String| -> String{text.to_uppercase()});
197    ///
198    /// match circular_buffer.dequeue() {
199    ///     Some(data) => assert_eq!(*data, String::from("ELEMENT")),
200    ///     None => panic!("Data must not be None")
201    /// }
202    /// ```
203    pub fn map_closure<F>(&mut self, transform: F)
204    where
205        F: Fn(&T) -> T,
206    {
207        for i in 0..self.size() {
208            self[i] = transform(&self[i]);
209        }
210    }
211
212    /// Clears the queue and resets internal flags
213    pub fn clear(&mut self) {
214        self.internal_vec.clear();
215
216        self.rear_index = 0;
217        self.front_index = 0;
218        self.size = 0;
219        self.push_enabled = true;
220    }
221}
222
223impl<T> std::ops::Index<usize> for Circular<T> {
224    type Output = T;
225
226    fn index(&self, index: usize) -> &Self::Output {
227        if index >= self.size() {
228            panic!("index out of bounds");
229        }
230        let new_index = (self.front_index + index) % self.capacity;
231
232        return &self.internal_vec[new_index];
233    }
234}
235
236impl<T> std::ops::IndexMut<usize> for Circular<T> {
237    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
238        if index >= self.size() {
239            panic!("index out of bounds");
240        }
241        let new_index = (self.front_index + index) % self.capacity;
242
243        return &mut self.internal_vec[new_index];
244    }
245}
246
247pub struct CircularIterator<'a, T> {
248    vec_circular: &'a Circular<T>,
249    index: usize,
250}
251
252impl<'a, T> std::iter::IntoIterator for &'a Circular<T> {
253    type Item = &'a T;
254    type IntoIter = CircularIterator<'a, T>;
255
256    fn into_iter(self) -> Self::IntoIter {
257        CircularIterator {
258            vec_circular: &self,
259            index: self.front_index,
260        }
261    }
262}
263
264impl<'a, T> std::iter::Iterator for CircularIterator<'a, T> {
265    type Item = &'a T;
266    fn next(&mut self) -> Option<&'a T> {
267        if self.index == self.vec_circular.rear_index || self.vec_circular.empty() {
268            return None;
269        } else {
270            let item = &self.vec_circular[self.index];
271            self.index = (self.index + 1) % self.vec_circular.capacity;
272            return Some(item);
273        }
274    }
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280
281    #[test]
282    fn create_circular_queue_1() {
283        let vc: Circular<String> = Circular::new(0);
284
285        assert_eq!(vc.capacity, 1);
286        assert_eq!(vc.push_enabled, true);
287        assert_eq!(vc.front_index, 0);
288        assert_eq!(vc.rear_index, 0);
289        assert_eq!(vc.size, 0);
290    }
291
292    #[test]
293    fn create_circular_queue_2() {
294        let vc: Circular<String> = Circular::new(1);
295
296        assert_eq!(vc.capacity, 2);
297        assert_eq!(vc.push_enabled, true);
298        assert_eq!(vc.front_index, 0);
299        assert_eq!(vc.rear_index, 0);
300        assert_eq!(vc.size, 0);
301    }
302
303    #[test]
304    fn enqueue_on_capacity_zero() {
305        let mut vc: Circular<String> = Circular::new(0);
306
307        vc.enqueue(String::from("element1"));
308
309        assert_eq!(vc.push_enabled, true);
310        assert_eq!(vc.front_index, 0);
311        assert_eq!(vc.rear_index, 0);
312        assert_eq!(vc.size, 0);
313    }
314
315    #[test]
316    fn enqueue_on_capacity_big() {
317        let mut vc: Circular<String> = Circular::new(10);
318
319        vc.enqueue(String::from("element1"));
320        assert_eq!(vc.push_enabled, true);
321        assert_eq!(vc.front_index, 0);
322        assert_eq!(vc.rear_index, 1);
323        assert_eq!(vc.size, 1);
324
325        vc.enqueue(String::from("element2"));
326        assert_eq!(vc.push_enabled, true);
327        assert_eq!(vc.front_index, 0);
328        assert_eq!(vc.rear_index, 2);
329        assert_eq!(vc.size, 2);
330
331        vc.enqueue(String::from("element3"));
332        assert_eq!(vc.push_enabled, true);
333        assert_eq!(vc.front_index, 0);
334        assert_eq!(vc.rear_index, 3);
335        assert_eq!(vc.size, 3);
336    }
337
338    #[test]
339    fn enqueue_on_full_queue() {
340        let mut vc: Circular<String> = Circular::new(3);
341
342        vc.enqueue(String::from("element1"));
343
344        assert_eq!(vc.push_enabled, true);
345        assert_eq!(vc.front_index, 0);
346        assert_eq!(vc.rear_index, 1);
347        assert_eq!(vc.size, 1);
348
349        vc.enqueue(String::from("element2"));
350        assert_eq!(vc.push_enabled, true);
351        assert_eq!(vc.front_index, 0);
352        assert_eq!(vc.rear_index, 2);
353        assert_eq!(vc.size, 2);
354
355        vc.enqueue(String::from("element3"));
356        assert_eq!(vc.push_enabled, true);
357        assert_eq!(vc.front_index, 0);
358        assert_eq!(vc.rear_index, 3);
359        assert_eq!(vc.size, 3);
360
361        // now queue is full
362        vc.enqueue(String::from("element4"));
363        assert_eq!(vc.push_enabled, false);
364        assert_eq!(vc.front_index, 1);
365        assert_eq!(vc.rear_index, 0);
366        assert_eq!(vc.size, 3);
367
368        vc.enqueue(String::from("element5"));
369        assert_eq!(vc.push_enabled, false);
370        assert_eq!(vc.front_index, 2);
371        assert_eq!(vc.rear_index, 1);
372        assert_eq!(vc.size, 3);
373
374        vc.enqueue(String::from("element6"));
375        assert_eq!(vc.push_enabled, false);
376        assert_eq!(vc.front_index, 3);
377        assert_eq!(vc.rear_index, 2);
378        assert_eq!(vc.size, 3);
379
380        vc.enqueue(String::from("element7"));
381        assert_eq!(vc.push_enabled, false);
382        assert_eq!(vc.front_index, 0);
383        assert_eq!(vc.rear_index, 3);
384        assert_eq!(vc.size, 3);
385    }
386
387    #[test]
388    fn dequeue_on_queue_capacity_zero() {
389        let mut vc: Circular<String> = Circular::new(0);
390
391        assert_eq!(None, vc.dequeue());
392    }
393
394    #[test]
395    fn dequeue_one_element() {
396        let mut vc: Circular<String> = Circular::new(1);
397
398        vc.enqueue(String::from("element1"));
399
400        match vc.dequeue() {
401            Some(elem) => assert_eq!(*elem, String::from("element1")),
402            None => panic!("Element should not be None!"),
403        }
404
405        assert_eq!(vc.push_enabled, true);
406        assert_eq!(vc.front_index, 1);
407        assert_eq!(vc.rear_index, 1);
408        assert_eq!(vc.size, 0);
409    }
410
411    #[test]
412    fn dequeue_multiple_elements() {
413        let mut vc: Circular<String> = Circular::new(5);
414
415        vc.enqueue(String::from("element1"));
416        vc.enqueue(String::from("element2"));
417        vc.enqueue(String::from("element3"));
418        vc.enqueue(String::from("element4"));
419        vc.enqueue(String::from("element5"));
420
421        match vc.dequeue() {
422            Some(elem) => assert_eq!(*elem, String::from("element1")),
423            None => panic!("Element should not be None!"),
424        }
425        assert_eq!(vc.push_enabled, true);
426        assert_eq!(vc.front_index, 1);
427        assert_eq!(vc.rear_index, 5);
428        assert_eq!(vc.size, 4);
429
430        match vc.dequeue() {
431            Some(elem) => assert_eq!(*elem, String::from("element2")),
432            None => panic!("Element should not be None!"),
433        }
434        assert_eq!(vc.push_enabled, true);
435        assert_eq!(vc.front_index, 2);
436        assert_eq!(vc.rear_index, 5);
437        assert_eq!(vc.size, 3);
438
439        match vc.dequeue() {
440            Some(elem) => assert_eq!(*elem, String::from("element3")),
441            None => panic!("Element should not be None!"),
442        }
443        assert_eq!(vc.push_enabled, true);
444        assert_eq!(vc.front_index, 3);
445        assert_eq!(vc.rear_index, 5);
446        assert_eq!(vc.size, 2);
447
448        match vc.dequeue() {
449            Some(elem) => assert_eq!(*elem, String::from("element4")),
450            None => panic!("Element should not be None!"),
451        }
452        assert_eq!(vc.push_enabled, true);
453        assert_eq!(vc.front_index, 4);
454        assert_eq!(vc.rear_index, 5);
455        assert_eq!(vc.size, 1);
456
457        match vc.dequeue() {
458            Some(elem) => assert_eq!(*elem, String::from("element5")),
459            None => panic!("Element should not be None!"),
460        }
461        assert_eq!(vc.push_enabled, true);
462        assert_eq!(vc.front_index, 5);
463        assert_eq!(vc.rear_index, 5);
464        assert_eq!(vc.size, 0);
465    }
466
467    #[test]
468    fn dequeue_when_rear_smaller_than_front_index() {
469        let mut vc: Circular<String> = Circular::new(2);
470
471        vc.enqueue(String::from("element1"));
472        vc.enqueue(String::from("element2"));
473        vc.enqueue(String::from("element3"));
474        vc.enqueue(String::from("element4"));
475
476        match vc.dequeue() {
477            Some(elem) => assert_eq!(*elem, String::from("element3")),
478            None => panic!("Element should not be None!"),
479        }
480        assert_eq!(vc.push_enabled, false);
481        assert_eq!(vc.front_index, 0);
482        assert_eq!(vc.rear_index, 1);
483        assert_eq!(vc.size, 1);
484
485        match vc.dequeue() {
486            Some(elem) => assert_eq!(*elem, String::from("element4")),
487            None => panic!("Element should not be None!"),
488        }
489        assert_eq!(vc.push_enabled, false);
490        assert_eq!(vc.front_index, 1);
491        assert_eq!(vc.rear_index, 1);
492        assert_eq!(vc.size, 0);
493    }
494
495    #[test]
496    fn enqueue_dequeue_of_primitive_data() {
497        let mut vc: Circular<i32> = Circular::new(2);
498
499        vc.enqueue(1);
500        vc.enqueue(2);
501
502        match vc.dequeue() {
503            Some(elem) => assert_eq!(*elem, 1),
504            None => panic!("Element should not be None!"),
505        }
506
507        match vc.dequeue() {
508            Some(elem) => assert_eq!(*elem, 2),
509            None => panic!("Element should not be None!"),
510        }
511    }
512
513    #[test]
514    fn clear_circular_queue() {
515        let mut vc: Circular<String> = Circular::new(5);
516
517        vc.clear();
518        assert_eq!(vc.capacity, 6);
519        assert_eq!(vc.push_enabled, true);
520        assert_eq!(vc.front_index, 0);
521        assert_eq!(vc.rear_index, 0);
522        assert_eq!(vc.size, 0);
523    }
524
525    #[test]
526    fn clear_queue_with_capacity_zero() {
527        let mut vc: Circular<String> = Circular::new(0);
528
529        vc.clear();
530        assert_eq!(vc.capacity, 1);
531        assert_eq!(vc.push_enabled, true);
532        assert_eq!(vc.front_index, 0);
533        assert_eq!(vc.rear_index, 0);
534        assert_eq!(vc.size, 0);
535    }
536
537    #[test]
538    fn index_trait() {
539        let mut vc: Circular<String> = Circular::new(2);
540
541        vc.enqueue(String::from("element1"));
542        vc.enqueue(String::from("element2"));
543
544        assert_eq!(*vc[0], String::from("element1"));
545        assert_eq!(*vc[1], String::from("element2"));
546    }
547
548    #[test]
549    fn index_trait_rear_before_front() {
550        let mut vc: Circular<String> = Circular::new(2);
551
552        vc.enqueue(String::from("element1"));
553        vc.enqueue(String::from("element2"));
554        vc.enqueue(String::from("element3"));
555        vc.enqueue(String::from("element4"));
556
557        assert_eq!(*vc[0], String::from("element3"));
558        assert_eq!(*vc[1], String::from("element4"));
559    }
560
561    #[test]
562    #[should_panic(expected = "index out of bounds")]
563    fn index_trait_out_of_bounds() {
564        let vc: Circular<String> = Circular::new(0);
565
566        &vc[0];
567    }
568
569    #[test]
570    #[should_panic(expected = "index out of bounds")]
571    fn index_trait_out_of_bounds_1() {
572        let vc: Circular<String> = Circular::new(1);
573
574        &vc[0];
575    }
576
577    #[test]
578    #[should_panic(expected = "index out of bounds")]
579    fn index_trait_out_of_bounds_2() {
580        let mut vc: Circular<String> = Circular::new(1);
581
582        vc.enqueue(String::from("element1"));
583
584        &vc[1];
585    }
586
587    #[test]
588    #[should_panic(expected = "index out of bounds")]
589    fn index_trait_out_of_bounds_3() {
590        let mut vc: Circular<String> = Circular::new(3);
591
592        vc.enqueue(String::from("element1"));
593        vc.enqueue(String::from("element2"));
594        vc.enqueue(String::from("element3"));
595
596        &vc[3];
597    }
598
599    #[test]
600    #[should_panic(expected = "index out of bounds")]
601    fn index_trait_out_of_bounds_rear_before_front_index() {
602        let mut vc: Circular<String> = Circular::new(2);
603
604        vc.enqueue(String::from("element1"));
605        vc.enqueue(String::from("element2"));
606        vc.enqueue(String::from("element3"));
607        vc.enqueue(String::from("element4"));
608
609        &vc[3];
610    }
611
612    #[test]
613    fn mut_index_trait() {
614        let mut vc: Circular<String> = Circular::new(2);
615
616        vc.enqueue(String::from("element1"));
617        vc.enqueue(String::from("element2"));
618
619        vc[0] = String::from("element3");
620        vc[1] = String::from("element4");
621
622        assert_eq!(*vc[0], String::from("element3"));
623        assert_eq!(*vc[1], String::from("element4"));
624    }
625
626    #[test]
627    fn mut_index_trait_dequeue() {
628        let mut vc: Circular<String> = Circular::new(2);
629
630        vc.enqueue(String::from("element1"));
631        vc.enqueue(String::from("element2"));
632
633        vc[0] = String::from("element3");
634        vc[1] = String::from("element4");
635
636        match vc.dequeue() {
637            Some(elem) => assert_eq!(*elem, String::from("element3")),
638            None => panic!("Element should not be None!"),
639        }
640
641        match vc.dequeue() {
642            Some(elem) => assert_eq!(*elem, String::from("element4")),
643            None => panic!("Element should not be None!"),
644        }
645    }
646
647    #[test]
648    fn iterator_trait() {
649        let mut vc: Circular<String> = Circular::new(2);
650
651        let template = vec!["element1", "element2"];
652        let mut index = 0;
653
654        vc.enqueue(String::from("element1"));
655        vc.enqueue(String::from("element2"));
656
657        for item in &vc {
658            assert_eq!(item, template[index]);
659            index += 1;
660        }
661    }
662
663    #[test]
664    fn iterator_trait_on_empty_queue() {
665        let vc: Circular<String> = Circular::new(2);
666
667        for _ in &vc {
668            panic!("Loop should not get executed");
669        }
670    }
671
672    fn all_caps(text: &String) -> String {
673        return text.to_uppercase();
674    }
675
676    #[test]
677    fn apply_map() {
678        let mut vc: Circular<String> = Circular::new(2);
679
680        vc.enqueue(String::from("element1"));
681        vc.enqueue(String::from("element2"));
682
683        vc.map(all_caps);
684
685        match vc.dequeue() {
686            Some(data) => assert_eq!(*data, String::from("ELEMENT1")),
687            None => panic!("Data must not be None"),
688        }
689
690        match vc.dequeue() {
691            Some(data) => assert_eq!(*data, String::from("ELEMENT2")),
692            None => panic!("Data must not be None"),
693        }
694    }
695
696    fn plus_one(num: &usize) -> usize {
697        return *num + 1;
698    }
699
700    #[test]
701    fn apply_map_primitive_data() {
702        let mut vc: Circular<usize> = Circular::new(2);
703        vc.enqueue(1);
704        vc.enqueue(2);
705
706        vc.map(plus_one);
707
708        match vc.dequeue() {
709            Some(data) => assert_eq!(*data, 2),
710            None => panic!("Data must not be None"),
711        }
712
713        match vc.dequeue() {
714            Some(data) => assert_eq!(*data, 3),
715            None => panic!("Data must not be None"),
716        }
717    }
718
719    #[test]
720    fn apply_map_closure() {
721        let mut vc: Circular<String> = Circular::new(2);
722
723        vc.enqueue(String::from("element1"));
724        vc.enqueue(String::from("element2"));
725
726        vc.map_closure(|text: &String| -> String { text.to_uppercase() });
727
728        match vc.dequeue() {
729            Some(data) => assert_eq!(*data, String::from("ELEMENT1")),
730            None => panic!("Data must not be None"),
731        }
732
733        match vc.dequeue() {
734            Some(data) => assert_eq!(*data, String::from("ELEMENT2")),
735            None => panic!("Data must not be None"),
736        }
737    }
738
739    #[test]
740    fn apply_map_closure_primitive_data() {
741        let mut vc: Circular<usize> = Circular::new(2);
742        vc.enqueue(1);
743        vc.enqueue(2);
744
745        vc.map_closure(|num: &usize| -> usize { num + 1 });
746
747        match vc.dequeue() {
748            Some(data) => assert_eq!(*data, 2),
749            None => panic!("Data must not be None"),
750        }
751
752        match vc.dequeue() {
753            Some(data) => assert_eq!(*data, 3),
754            None => panic!("Data must not be None"),
755        }
756    }
757}
rudac/queue/circular.rs

rudac/queue/
circular.rs
