gistools/data_structures/
flat_queue.rs

1use alloc::vec::Vec;
2
3/// # FlatQueue
4///
5/// ## Description
6/// A priority queue implemented using a binary heap.
7///
8/// A port from the [flatqueue](https://github.com/mourner/flatqueue) code.
9///
10/// ## Usage
11///
12/// ```rust
13/// use gistools::data_structures::FlatQueue;
14///
15/// let mut q = FlatQueue::new();
16/// q.push(1, 1.0);
17/// q.push(3, 3.0);
18/// q.push(2, 2.0);
19/// assert_eq!(q.pop(), Some(1));
20/// assert_eq!(q.pop(), Some(2));
21/// assert_eq!(q.pop(), Some(3));
22/// assert_eq!(q.pop(), None);
23/// ```
24pub struct FlatQueue<T> {
25    ids: Vec<T>,
26    values: Vec<f64>, // priority
27    len: usize,
28}
29impl<T: Clone> Default for FlatQueue<T> {
30    fn default() -> Self {
31        Self::new()
32    }
33}
34impl<T: Clone> FlatQueue<T> {
35    /// Creates a new empty queue.
36    pub fn new() -> Self {
37        Self { ids: Vec::new(), values: Vec::new(), len: 0 }
38    }
39
40    /// Returns the number of items.
41    pub fn len(&self) -> usize {
42        self.len
43    }
44
45    /// Returns whether the queue is empty.
46    pub fn is_empty(&self) -> bool {
47        self.len == 0
48    }
49
50    /// Clears all items from the queue.
51    pub fn clear(&mut self) {
52        self.len = 0;
53    }
54
55    /// Adds `item` to the queue with the specified `priority`.
56    ///
57    /// `priority` must be a number. Items are sorted and returned from low to high priority. Multiple items
58    /// with the same priority value can be added to the queue, but there is no guaranteed order between these items.
59    ///
60    /// ## Parameters
61    /// - `item`: the item to add
62    /// - `priority`: the priority of the item
63    pub fn push(&mut self, item: T, priority: f64) {
64        let mut pos = self.len;
65        self.len += 1;
66
67        if self.ids.len() < self.len {
68            self.ids.resize(self.len, item.clone());
69            self.values.resize(self.len, priority);
70        }
71
72        while pos > 0 {
73            let parent = (pos - 1) >> 1;
74            let parent_value = self.values[parent];
75            if priority >= parent_value {
76                break;
77            }
78            self.ids[pos] = self.ids[parent].clone();
79            self.values[pos] = parent_value;
80            pos = parent;
81        }
82
83        self.ids[pos] = item;
84        self.values[pos] = priority;
85    }
86
87    /// Removes and returns the item from the head of this queue, which is one of
88    /// the items with the lowest priority. If this queue is empty, returns `undefined`.
89    ///
90    /// ## Returns
91    /// the item from the head of this queue
92    pub fn pop(&mut self) -> Option<T> {
93        if self.len == 0 {
94            return None;
95        }
96
97        let top = self.ids[0].clone();
98        self.len -= 1;
99
100        if self.len > 0 {
101            let id = self.ids[self.len].clone();
102            let value = self.values[self.len];
103            let mut pos = 0;
104            let half_len = self.len >> 1;
105
106            while pos < half_len {
107                let left = (pos << 1) + 1;
108                let right = left + 1;
109                let mut child = left;
110                if right < self.len && self.values[right] < self.values[left] {
111                    child = right;
112                }
113                if self.values[child] >= value {
114                    break;
115                }
116                self.ids[pos] = self.ids[child].clone();
117                self.values[pos] = self.values[child];
118                pos = child;
119            }
120
121            self.ids[pos] = id;
122            self.values[pos] = value;
123        }
124
125        Some(top)
126    }
127
128    /// Returns the item with the lowest priority without removing it.
129    pub fn peek(&self) -> Option<&T> {
130        if self.len > 0 { Some(&self.ids[0]) } else { None }
131    }
132
133    /// Returns the priority of the lowest-priority item.
134    pub fn peek_value(&self) -> Option<f64> {
135        if self.len > 0 { Some(self.values[0]) } else { None }
136    }
137
138    /// Shrinks underlying arrays to current length.
139    pub fn shrink(&mut self) {
140        self.ids.truncate(self.len);
141        self.values.truncate(self.len);
142    }
143}
gistools/data_structures/flat_queue.rs

gistools/data_structures/
flat_queue.rs
