Does a C# "circular collection" exist?

Question

I want to implement a round-robin-based scheduling for a producer/consumer situation, where the consumers may change during runtime.

In the beginning I used a Queue which contained all the consumers, dequeued one and immediately enqueued it again to have a circular collection, worked perfectly. Whenever a new consumer registered I just enqueued it to the queue -> done.

However, the problem of removing consumers at runtime (when they send an unsubscribe message) is challenging. Queue does not offer a Remove() method, however, I need to remove them completely from the queue - independently of the consumer's current position within the queue. Obviously the Queue "interface" is not exactly what I need.

Is there some kind of "circular collection" in C# I haven't heard of?

It is called Dequeue, not Remove. The only thing special about a circular buffer is that it has a fixed size. Queue doesn't, it works better. — Hans Passant, Sep 08 '13 at 16:29
Maybe there is a circular iterator which I can use for List? — D.R., Sep 08 '13 at 16:29
Dequeue just takes the next element out of the queue, it does not remove a consumer completely from the queue - independently from its position. — D.R., Sep 08 '13 at 16:30
I rephrased the question. It means: the consumer sends an unsubscribe message and I need to remove them completely from the underlying collection - regardless of their current position within the collection. — D.R., Sep 08 '13 at 16:33
Like people waiting in line for a sandwich when suddenly someone around the middle leaves because there's no turkey sandwich left? — Jeroen Vannevel, Sep 08 '13 at 16:35
Yeah, like that. Although each guy receiving a sandwhich at the front of the queue immediately goes back to the end of the line and waits again for a new sandwhich :-) — D.R., Sep 08 '13 at 16:36
You need two queues, one for sandwhiches and another for guys. — Hans Passant, Sep 08 '13 at 16:40
http://stackoverflow.com/questions/9346526/what-is-the-equivalent-of-linkedhashset-java-in-c achitaka-san's answer might be interesting for you. "It uses the Dictionary to look up items and the LinkedList to preserve order." — Jeroen Vannevel, Sep 08 '13 at 16:42
There is a LimitList here that may be of help: http://stackoverflow.com/questions/14702654/rolling-list-in-net — Simon Mourier, Sep 08 '13 at 16:46
How about just marking the task as cancelled, and then when it reaches the head and gets dequeued, check the cancelled flag and discard it without processing? — Ben Voigt, Sep 08 '13 at 16:46
Marking it "canceled" is also a good approach, however, dropping the `Queue` and using a `LinkedList` seems to be easier. See answer. — D.R., Sep 08 '13 at 16:55

score 2 · Answer 1 · answered Sep 08 '13 at 16:41

Removing things from the middle of the queue is a mess: you would end up iterating all items, and re-queueing only the ones that you do not want to erase. Something like this may work:

int count = q.Count;
for (int i = 0 ; i != count ; i++) {
    var item = q.Dequeue();
    if (!toRemove.Equals(item)) {
        q.Enqueue(item);
    }
}

However, this requires going through the entire queue, so it's O(n). A better approach may be keeping a HashSet<T> toRemove of the removed items, and wrap the dequeue method in such a way that removing items requires a quick toRemove.Add(removedItem), enqueueing requires removal of the item from toRemove in addition to the actual enqueueing, and dequeueing requires an additional check of the item for presence in toRemove.

Of course you can always implement your own circular buffer, which would let you remove items from the middle simply by walking the buffer back to front, copying the items that you wish to keep onto itself, and adjusting the 'head' pointer when you are done.

This would change the order, however, I used a similar approach now. Going to answer the question myself. Upvoting you, because you guided me into the right direction! — D.R., Sep 08 '13 at 16:51
@D.R. Why would it change the order? You read `Count` items, and enqueue `Count - erased` items in the same exact order. Doing the same thing with a linked list does not change a thing. — Sergey Kalinichenko, Sep 08 '13 at 16:54
Sorry. You're right. I thought you were just enqueueing/dequeuing until you find the correct item. My `LinkedList` solution seems to be a bit more performant then. — D.R., Sep 08 '13 at 16:56

score 0 · Accepted Answer · answered Sep 08 '13 at 16:54

After reading dasblinkenlight's answer, I'm now using a LinkedList-based approach.

AddConsumer -> linkedList.AddLast
RemoveConsumer -> linkedList.Remove
GetNextConsumer

var next = linkedList.First.Value; linkedList.RemoveFirst(); linkedList.AddLast(next); return next;

This does the trick, RemoveConsumer is O(N), however, that's not too bad, as remove is a rare occurrence.

Does a C# "circular collection" exist?

2 Answers2