eitherq/
lib.rs

1//! `EitherQueue` is queue that supports two different queues as one.
2
3use std::collections::VecDeque;
4use std::time::Instant;
5
6/// Representation of two queues in one.
7pub struct EitherQueue<L, R> {
8  left: VecDeque<(Instant, L)>,
9  right: VecDeque<(Instant, R)>
10}
11
12
13pub enum Either<L, R> {
14  Left(L),
15  Right(R)
16}
17
18impl<L, R> EitherQueue<L, R> {
19  /// Allocate and return a new, empty, `EitherQueue` object.
20  #[inline(always)]
21  pub fn new() -> Self {
22    Self::default()
23  }
24
25
26  /// Returns the number of nodes in both left and right queues combined.
27  ///
28  /// ```
29  /// let mut q = eitherq::EitherQueue::<&str, u32>::new();
30  /// q.push_left("elena");
31  /// q.push_left("chloe");
32  /// q.push_right(42);
33  /// assert_eq!(q.len(), 3);
34  /// ```
35  #[inline(always)]
36  pub fn len(&self) -> usize {
37    self.left.len() + self.right.len()
38  }
39
40
41  #[inline(always)]
42  pub fn left_len(&self) -> usize {
43    self.left.len()
44  }
45
46
47  #[inline(always)]
48  pub fn right_len(&self) -> usize {
49    self.right.len()
50  }
51
52
53  /// Returns `true` if both internal queues are empty.
54  ///
55  /// ```
56  /// let mut q = eitherq::EitherQueue::<&str, u32>::new();
57  /// assert_eq!(q.is_empty(), true);
58  /// q.push_left("charlie");
59  /// assert_eq!(q.is_empty(), false);
60  /// q.clear();
61  /// q.push_right(17);
62  /// assert_eq!(q.is_empty(), false);
63  /// ```
64  #[inline(always)]
65  pub fn is_empty(&self) -> bool {
66    self.left.is_empty() && self.right.is_empty()
67  }
68
69
70  /// Returns `true` if the left queue is empty.  Returns `false` otherwise.
71  #[inline(always)]
72  pub fn is_left_empty(&self) -> bool {
73    self.left.is_empty()
74  }
75
76
77  /// Returns `true` if the right queue is empty.  Returns `false` otherwise.
78  #[inline(always)]
79  pub fn is_right_empty(&self) -> bool {
80    self.right.is_empty()
81  }
82
83
84  /// Clears all elements from both queues.
85  ///
86  /// ```
87  /// let mut q = eitherq::EitherQueue::<&str, u32>::new();
88  /// q.push_left("sully");
89  /// q.push_right(11);
90  /// q.clear();
91  /// assert_eq!(q.len(), 0);
92  /// ```
93  #[inline(always)]
94  pub fn clear(&mut self) {
95    self.left.clear();
96    self.right.clear();
97  }
98
99
100  #[inline(always)]
101  pub fn push(&mut self, n: Either<L, R>) {
102    match n {
103      Either::Left(n) => self.push_left(n),
104      Either::Right(n) => self.push_right(n)
105    }
106  }
107
108
109  #[inline(always)]
110  pub fn push_left(&mut self, n: L) {
111    self.left.push_back((Instant::now(), n));
112  }
113
114
115  #[inline(always)]
116  pub fn push_right(&mut self, n: R) {
117    self.right.push_back((Instant::now(), n));
118  }
119
120
121  /// Take the "oldest" node off the queue.
122  pub fn pop(&mut self) -> Option<Either<L, R>> {
123    if self.left.is_empty() {
124      // The "left" queue is empty, so try the "right" one
125      if let Some((_, n)) = self.right.pop_front() {
126        Some(Either::Right(n))
127      } else {
128        // Both queues are empty
129        None
130      }
131    } else if self.right.is_empty() {
132      // The "left" has nodes, but the "right" does not
133      if let Some((_, n)) = self.left.pop_front() {
134        Some(Either::Left(n))
135      } else {
136        // Should never happen
137        unreachable!("Could not get node that is known to exist");
138      }
139    } else {
140      // There are nodes in both queues.
141      // Find out which of the queues has the oldest node.
142      // If they are equal, the left queue will take predence.
143      let next_left = {
144        let (li, _) = self
145          .left
146          .front()
147          .expect("Unable to get reference to expected front left node");
148        let (ri, _) = self
149          .right
150          .front()
151          .expect("Unable to get reference to expected front right node");
152        li <= ri
153      };
154
155      if next_left {
156        let (_, n) = self
157          .left
158          .pop_front()
159          .expect("Unexpectededly unable to get next left node");
160        Some(Either::Left(n))
161      } else {
162        let (_, n) = self
163          .right
164          .pop_front()
165          .expect("Unexpectededly unable to get next put node");
166        Some(Either::Right(n))
167      }
168    }
169  }
170
171
172  /// Take the oldest node off the left queue.
173  #[inline(always)]
174  pub fn pop_left(&mut self) -> Option<L> {
175    if let Some((_, n)) = self.left.pop_front() {
176      Some(n)
177    } else {
178      None
179    }
180  }
181
182
183  /// Take the oldest node off the right queue.
184  #[inline(always)]
185  pub fn pop_right(&mut self) -> Option<R> {
186    if let Some((_, n)) = self.right.pop_front() {
187      Some(n)
188    } else {
189      None
190    }
191  }
192}
193
194impl<L, R> Default for EitherQueue<L, R> {
195  fn default() -> Self {
196    Self {
197      left: VecDeque::new(),
198      right: VecDeque::new()
199    }
200  }
201}
202
203// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :
eitherq/lib.rs

eitherq/
lib.rs
