Say I have an input queue, which can receive two different types of commands, each with its own payload. For simplicity, let's call the command types Foo and Bar. The data structure I want is a VecDequebut there's an annoying twist: The application can choose to receive next node based on command type; i.e. "receive next foo or next bar command":
recv() - gets the next command in the queue and returns an enum; either a Command::Foo(foodata) , or a Command::Bar(bardata).
recv_foo() - gets the next foo data buffer from the queue.
recv_bar() - gets the next bar data buffer from the queue.
I'm concerned about the performance of removing nodes in the VecDeque which aren't in the beginning or the end of the list. (This issue wouldn't apply to the recv() method, but I suspect applications will use the two other ones more often).
One obvious way to work around this is to have two separate queues, but then the recv() becomes more complicated; it's not obvious which of the queues to prioritize, and I don't want to timestamp each node just to be able to determine which of them to pull next. ... or maybe I do want to do that. Hm..
In the good ol' days this is a case where I'd use a double linked list (because it's fast at removing nodes mid-list, but I'm wondering if there's a obvious data structure that I'm missing.
Does it have to be a double-ended queue? I’m assuming not. You can have an extra “front” queue that stores only items of one type. (Well, you’ll need two of them in general if you want to keep your allocations.)
Here’s some sample code
use either::Either::{self, Left, Right};
use std::collections::VecDeque;
#[derive(Debug)]
pub struct EitherQueue<L, R> {
// always one of front_lefts, front_rights is empty
front_lefts: VecDeque<L>,
front_rights: VecDeque<R>,
back: VecDeque<Either<L, R>>,
}
impl<L, R> Default for EitherQueue<L, R> {
fn default() -> Self {
Self {
front_lefts: <_>::default(),
front_rights: <_>::default(),
back: <_>::default(),
}
}
}
impl<L, R> EitherQueue<L, R> {
pub fn new() -> Self {
<_>::default()
}
pub fn push(&mut self, item: Either<L, R>) {
self.back.push_back(item)
}
pub fn push_left(&mut self, item: L) {
self.push(Left(item))
}
pub fn push_right(&mut self, item: R) {
self.push(Right(item))
}
#[rustfmt::skip]
pub fn pop(&mut self) -> Option<Either<L, R>> {
// one of front_lefts, front_rights is empty, so we can try them in any order
self.front_lefts.pop_front().map(Left) .or_else(||
self.front_rights.pop_front().map(Right) .or_else(||
self.back.pop_front() ))
}
pub fn pop_left(&mut self) -> Option<L> {
self.front_lefts.pop_front().or_else(|| loop {
break match self.back.pop_front() {
Some(Right(i)) => {
// filling front_rights and front_lefts was empty
self.front_rights.push_back(i);
continue;
}
Some(Left(i)) => Some(i),
None => None,
};
})
}
pub fn pop_right(&mut self) -> Option<R> {
self.front_rights.pop_front().or_else(|| loop {
break match self.back.pop_front() {
Some(Left(i)) => {
// filling front_lefts and front_rights was empty
self.front_lefts.push_back(i);
continue;
}
Some(Right(i)) => Some(i),
None => None,
};
})
}
}