stochastic_queue/
queue.rs

1use rand::thread_rng;
2use rand::RngCore;
3use std::cmp::Ordering;
4use std::collections::BinaryHeap;
5
6struct Entry<T> {
7  pos: u64,
8  val: T,
9}
10
11impl<T> PartialEq for Entry<T> {
12  fn eq(&self, other: &Self) -> bool {
13    self.pos == other.pos
14  }
15}
16
17impl<T> Eq for Entry<T> {}
18
19impl<T> PartialOrd for Entry<T> {
20  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
21    self.pos.partial_cmp(&other.pos)
22  }
23}
24
25impl<T> Ord for Entry<T> {
26  fn cmp(&self, other: &Self) -> Ordering {
27    self.partial_cmp(other).unwrap()
28  }
29}
30
31/// A queue which pops items at random uniformly. It cannot be iterated or peeked.
32pub struct StochasticQueue<T> {
33  entries: BinaryHeap<Entry<T>>,
34}
35
36impl<T> StochasticQueue<T> {
37  /// Create a queue with an initial capacity.
38  pub fn with_capacity(cap: usize) -> Self {
39    Self {
40      entries: BinaryHeap::with_capacity(cap),
41    }
42  }
43
44  /// Create a queue.
45  pub fn new() -> Self {
46    Self::with_capacity(0)
47  }
48
49  /// Get the amount of items in the queue. These items can be popped.
50  pub fn len(&self) -> usize {
51    self.entries.len()
52  }
53
54  /// Checks whether or not the queue has no items.
55  pub fn is_empty(&self) -> bool {
56    self.entries.is_empty()
57  }
58
59  /// Returns an iterator over all items in the queue without popping them. The order is arbitrary.
60  pub fn peek_iter(&self) -> impl Iterator<Item = &T> {
61    self.entries.iter().map(|e| &e.val)
62  }
63
64  /// Adds an item to the queue. When it will be chosen to be popped is nondeterministic.
65  pub fn push(&mut self, val: T) {
66    let pos = thread_rng().next_u64();
67    self.entries.push(Entry { pos, val });
68  }
69
70  /// Removes an item from the queue, or returns None if the queue is empty. Which item will be popped is nondeterministic, but all items have an equal chance of being popped. If there is at least one item present, an item will definitely be popped.
71  pub fn pop(&mut self) -> Option<T> {
72    self.entries.pop().map(|e| e.val)
73  }
74
75  /// Removes all items from the queue.
76  pub fn clear(&mut self) {
77    self.entries.clear();
78  }
79}
stochastic_queue/queue.rs

stochastic_queue/
queue.rs
