There is a great (always busy) sandwich shop in Boston called Darwin's that I used to go to a lot that worked that way. When a customer placed an order they would call down the long line, "anyone else for an X?", then make make the sandwiches with the inner loop over sandwich and the outer loop over ingredient.

I took much delight in the efficiency as well as the incentive structure: If you are not picky and you can help us increase throughput then we'll reduce your latency :)

Reminds me a little bit of a "delta queue" used in efficient discrete time based scheduling, for example, in an OS scheduler. Imagine you want to implement a scheduler that accepts jobs and runs them at some point in the future. Instead of keeping a list and scanning through the list at each clock tick, implement a linked list with (time delta, job) at each node. Now, handling a tick() simply requires decrementing the head node and popping items until you see a non-zero delta. Inserting is done like a normal list, except as you iterate through the list, you decrement the desired time interval as you see deltas in the list. It goes like this:

insert(job1, 1) # (job1, 1) -> null insert(job2, 1) # (job1, 1) -> (job2, 0) -> null insert(job3, 2) # (job1, 1) -> (job2, 0) -> (job3, 1) -> null tick() -> job1, job2 # (job3, 0) -> null tick -> job3 # -> null

Sounds similar to the behavior of Guava's LoadingCache. If you try to fetch a key that's not in the cache, the supplied callback is used to fetch it. While the value is being loaded, other threads can access the cache concurrently, but if a second thread asks for the same key, it will wait for the first load to complete instead of redundantly fetching the same value.

Sounds like a priority queue with a sidecar hashmap or some kind of notify mechanism for when "order's up!"

How do you implement it? Do you do a scan with every insert or do you hash or use a tree for indexing?

Sounds like a priority queue

Not really. In a priority queue, an item with higher priority gets pulled out before one with lower priority, so you can have items that skip parts of the queue (or all of it) even if there are no items of the same priority in there already.

This structure seems to behave differently, in that an item may skip ahead in the queue if and only if another item with some matching characteristic is already contained. This makes it so you can never skip the whole structure, for example, assuming you get put after your "friend".

Is it the same thing? I'm trying to imagine how this would work with a priority queue.

I think you need an flexible number of priorities that is equal to the queue length, and the priority values come from an infinite counter that only goes up. Higher values = lower priority.

When a unique item comes into the queue you increment the counter and give it that value as a priority. This puts it on the end of the queue.

But if the new item is a duplicate of an existing item then you give it the priority of the existing item.