queued_rust/queues/
sorted.rs

1use super::QueueError;
2
3/// A sorted queue implementation.
4#[derive(Clone, Debug)]
5pub struct SortedQueue<T>
6where
7    T: Ord,
8{
9    items: Vec<T>,
10    max_size: Option<usize>,
11    reverse: bool,
12}
13
14impl<T> SortedQueue<T>
15where
16    T: Ord,
17{
18    /// Creates a new `SortedQueue` with no maximum size.
19    pub fn new(reverse: bool) -> Self {
20        Self { items: vec![], max_size: None, reverse }
21    }
22    /// Creates a new `SortedQueue` with a specified maximum size.
23    pub fn new_sized(size: usize, reverse: bool) -> Self {
24        Self { items: vec![], max_size: Some(size), reverse }
25    }
26
27    /// Removes all elements from the queue.
28    pub fn clear(&mut self) {
29        self.items = vec![];
30    }
31    /// Returns the length of the queue.
32    pub fn len(&self) -> usize {
33        self.items.len()
34    }
35    /// Checks if the queue is full.
36    pub fn is_full(&self) -> bool {
37        if let Some(max_size) = self.max_size {
38            return self.len() >= max_size;
39        }
40        false
41    }
42    /// Returns queue reversed state
43    pub fn is_reversed(&self) -> bool {
44        self.reverse
45    }
46
47    /// Adds an item to the sorted queue.
48    ///
49    /// Items are inserted such that the queue remains sorted in ascending order.
50    pub fn add(&mut self, item: T) {
51        let mut low = 0;
52        let mut high = self.len();
53
54        while low < high {
55            let mid = (low + high) / 2;
56
57
58            if (self.items[mid] > item)^self.reverse { // Flip to switch order
59                low = mid + 1;
60            } else {
61                high = mid;
62            }
63        }
64
65        self.items.insert(low, item);
66    }
67
68    /// Attempts to add an item to the queue.
69    ///
70    /// If the queue is full, returns an error.
71    pub fn try_add(&mut self, item: T) -> Result<(), QueueError> {
72        if self.is_full() {
73            Err(QueueError::Full)
74        } else {
75            self.add(item);
76            Ok(())
77        }
78    }
79
80    /// Removes and returns an item from the queue.
81    pub fn pop(&mut self) -> Option<T> {
82        self.items.pop()
83    }
84
85    /// Returns a reference to the first item in the queue.
86    pub fn first(&self) -> Option<&T> {
87        self.items.last()
88    }
89}
90
91impl<T> Iterator for SortedQueue<T> where T: Ord {
92    type Item = T;
93
94    fn next(&mut self) -> Option<Self::Item> {
95        self.pop()
96    }
97}
queued_rust/queues/sorted.rs

queued_rust/queues/
sorted.rs
