CODEWITHSUNDEEP
c#collections
D.R.
D.R.

Reputation: 21194

Does a C# "circular collection" exist?

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?

Upvotes: 0

Views: 2294

Answers (2)

D.R.
D.R.

Reputation: 21194

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.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726609

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.

Upvotes: 2

Related Questions