israeli_queue_etc/
my_priority_queue.rs

1pub trait AbstractPriorityQueue<T, P: Ord> {
2    /// a version just like self
3    /// but without any actual items
4    #[must_use]
5    fn empty_copy(&self) -> Self;
6
7    /// what would `my_dequeue` give
8    fn my_peek(&self) -> Option<(&T, &P)>;
9
10    /// insert an item with specified priority
11    fn my_enqueue(&mut self, new_obj: T, new_obj_priority: P);
12
13    /// enqueueing many items all with the same priority, might have a faster implementation than
14    /// just doing them one by one
15    fn enqueue_batch(&mut self, new_batch: impl IntoIterator<Item = T>, new_batch_priority: P);
16
17    fn enqueue_many(&mut self, mut new_obj_and_priorities: impl Iterator<Item = (T, P)>) {
18        if let Some((first_item, first_item_priority)) = new_obj_and_priorities.next() {
19            let mut batch_to_send = Vec::new();
20            batch_to_send.push(first_item);
21            while let Some((next_item, next_item_priority)) = new_obj_and_priorities.next() {
22                if next_item_priority == first_item_priority {
23                    batch_to_send.push(next_item);
24                } else {
25                    if batch_to_send.len() == 1 {
26                        self.my_enqueue(
27                            batch_to_send.pop().expect("Already checked length"),
28                            first_item_priority,
29                        );
30                    } else if !batch_to_send.is_empty() {
31                        self.enqueue_batch(batch_to_send, first_item_priority);
32                    } else {
33                        unreachable!()
34                    }
35                    return self.enqueue_many(
36                        [(next_item, next_item_priority)]
37                            .into_iter()
38                            .chain(new_obj_and_priorities),
39                    );
40                }
41            }
42        }
43    }
44
45    /// if nonempty, one item comes out
46    /// the order is dependent on the specific implementation
47    /// and how it handles priorities
48    fn my_dequeue(&mut self) -> Option<(T, P)>;
49
50    /// if there are fewer than `around_how_many` gives all of the items in the queue
51    /// if there are more than that, give some number of items
52    ///     that is at least `around_how_many` but less than or equal to than the `hard limit`
53    ///     where how much more depends on the specific implementer and the specific items involved
54    fn dequeue_batch(&mut self, around_how_many: usize, hard_limit: usize) -> Vec<(T, P)>;
55
56    /// with no more items being enqueue'd
57    /// we can just dequeue them all and provide an iterator
58    /// over all the items ignoring their priorities
59    fn all_items_iter(mut self) -> impl Iterator<Item = T>
60    where
61        Self: Sized,
62    {
63        self.dequeue_batch(self.my_len(), self.my_len())
64            .into_iter()
65            .map(|z| z.0)
66    }
67
68    /// how many items are present
69    fn my_len(&self) -> usize;
70
71    /// is the queue empty
72    fn is_empty(&self) -> bool;
73
74    /// dequeue them all
75    /// but after the mutable reference issues resolved
76    /// more items can still be enqueue'd
77    /// unlike ``all_items_iter`` which closed this off
78    fn drain_all(&mut self) -> Vec<(T, P)> {
79        self.dequeue_batch(self.my_len(), self.my_len())
80    }
81}
israeli_queue_etc/my_priority_queue.rs

israeli_queue_etc/
my_priority_queue.rs
