Data structure for representing two queues in one

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 VecDeque but 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,
            };
        })
    }
}

(in the playground)

4 Likes
type Timestamp = u64;
pub struct Foo {
  foo: Deque<(Timestamp, Foo),
  var: Deque<(Timestamp, Bar)
}

Each of foo, and bar is always in sorted order (by Timestamp) right ?

so:

recv_foo() = pop from foo
recv_bar() = pop from bar
recv() = look at first element of each, pop one w earlier Timestamp

Does this work ?

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.