Simple Question About Adding-Removing From List

Hi everyone.

This is a really straightforward and easy question and I’m sure has been asked a lot, but I haven’t been able to find an answer online.

Here’s the deal, I want to create a script that keeps a list of instantiated objects (say, “ObjA”, for example), and have a max. amount of ObjA’s allowed at once.
So if the max. amount is set to 20 ObjA’s, and a new ObjA is instantiated, the script should find and destroy the oldest ObjA in the list, move the other ObjA’s up in the list, and add the instantiated ObjA in slot 20.

Any ideas or suggestions would help me greatly. Thanks for your help in advance!

What you need is called Queue

Research a little about two concepts called FIFO (Queue) and LIFO (Stack)

1 Like

Thank you! I’ll look into it!

Here’s one possible approach.

using System;
using System.Collections.Generic;

public class LimitedQueue<T> {

  Queue<T> _q;
  public int Limit { get; private set; }

  public LimitedQueue(int limit) {
    if(limit <= 0) throw new ArgumentException(nameof(limit));
    Limit = limit;
    _q = new(capacity: Limit);
  }
  
  public int Count => _q.Count;

  // returns true if something was dropped
  public bool Enqueue(T item) {
    var res = false;
    if(Count == Limit) { _q.Dequeue(); res = true; }
    _q.Enqueue(item);
    return res;
  }

  public T Dequeue() => _q.Dequeue;

  public void Clear() => _q.Clear();

  public bool Contains(T item) => _q.Contains();

  public IEnumerable<T> Items { get {
    foreach(var item in _q) yield return item;
  } }

}

To use it

void myQueue = new LimitedQueue<string>(limit: 20);
for(int i = 0; i < 24; i++) myQueue.Enqueue($"item_{i}");
foreach(var item in myQueue.Items) Debug.Log(item);

Now this could be made to fully implement ICollection<T> interface, to properly support enumerator functionality, and aggregate all of the Queue methods etc. This is just a sloppy example.

1 Like

Thanks! I’ve been trying to implement a way of using this approach, I’ll try it out!

A classic Queue is a pure first in first out structure. You usually don’t get random access like a classical List. Also a Queue does grow as necessary just like a List. That’s why I wrote my own RingBuffer class (download).

This class works similar to a Queue by using an internal buffer and a read and write pointer to push and dequeue elements without the need to move the remaining elements around. It actually has a random access property / indexer which automatically calculates the proper wrapped around index. The class has a fix capacity that is set when the class is created, but it can be resized if necessary but that should be avoided to avoid garbage allocation. The class implements IList and therefore works almost like an ordinary list. It does support arbitrary removing of elements but currently does not support arbitrary inserting.

It’s or course mainly meant as a classical ring buffer. So when the buffer is filled and you add elements at the end, the oldest element would be overwritten / removed.

I was just thinking about implementing proper push and pop methods for both ends. So it’s essentially a universal continuous data container where you can add and remove elements on both ends in O(1). The RemoveAt method already shifts the elements into the most efficient direction. So removing the second element would only shift the first one over while removing the second last element would just shift the last element over. In theory the “fixed size” could be optional so it could act like a normal List or Queue. Though I don’t want to over complicate things :slight_smile:

1 Like

No problem.
Another way would to build a so called ring buffer.

You add elements one by one until you reach the maximum, for example 4.

first, second, third, fourth

But when you introduce the fifth, you actually wrap around the buffer and overwrite the first one (which is simultaneously the oldest entry).

fifth, second, third, fourth

And similarly the sixth

fifth, sixth, third, fourth

This way the actual buffer stays in place, but the “header pointer” moves around in a circle.
This means that if you’d ask for the oldest entry (at index 0), you’d correctly receive “third” as the answer.

Here’s how to implement this.

using System;
using System.Collections.Generic;

public class RingBuffer<T> {

  T[] _buffer;
  int _head = 0;
  int _tail = 0;

  public RingBuffer(int maxSize) {
    if(maxSize < 0) throw new ArgumentException(nameof(maxSize));
    _buffer = new T[maxSize];
  }

  public int MaxSize => _buffer.Length;
  public int Count => _tail;

  // returns true when something was dropped
  public bool Enqueue(T item) {
    if(MaxSize == 0) return false;
    _buffer[windex(_head + _tail)] = item;
    _tail++;
    if(_tail <= MaxSize) return false;
    _head = windex(_head + 1);
    _tail = MaxSize;
    return true;
  }

  // removes the first (oldest) element and returns it
  // will return default(T) when there are no elements
  public T Dequeue() {
    if(MaxSize == 0 || _tail == 0) return default;
    int w = windex(_head);
    T result = _buffer[w];
    _buffer[w] = default;
    _head = windex(_head + 1);
    _tail--;
    return result;
  }

  // Same as enqueue, but in the context of a stack
  public bool Push(T item) => Enqueue(item);

  // removes the last (youngest) element and returns it
  // will return default(T) when there are no elements
  public T Pop() {
    if(MaxSize == 0 || _tail == 0) return default;
    int w = windex(_head + _tail - 1);
    T result = _buffer[w];
    _buffer[w] = default;
    _tail--;
    return result;
  }

  // Same as dequeue but doesn't remove anything
  public T Peek() => this[0];

  public void Clear() {
    _head = 0;
    _tail = 0;
  }

  // a custom indexer allows for random access
  public T this[int index] {
    get {
      if(MaxSize == 0 || index < 0 || index > _tail) throw new ArgumentOutOfRangeException();
      return _buffer[windex(_head + index)];
    }
    set {
      if(MaxSize == 0 || index < 0 || index > _tail) throw new ArgumentOutOfRangeException();
      _buffer[windex(_head + index)] = value;
    }
  }

  public IEnumerable<T> Items { get {
    for(int i = 0; i < MaxSize; i++) {
      yield return _buffer[windex(_head + i)];
    }
  } }

  // utility for wrapping the index around the ring via "clock arithmetic"
  int windex(int index) => index % MaxSize;

  // a general purpose solution which got optimized away for this particular implementation
  // this is because index and MaxSize are guaranteed to be >= 0
  // int windex(int index) => mod(index, MaxSize);
  // static int mod(int n, int m) => m <= 0? 0 : (n %= m) < 0? n + m : n;
 
}

Test

var buf = new RingBuffer<string>(5); // 5 is the maximum capacity

for(int i = 0; i < 8; i++) {
  buf.Enqueue($"string_{i}");
  Debug.Log($"Count: {buf.Count}"); // 1,2,3,4,5,5,5,5
}

buf.Dequeue();
Debug.Log(buf.Dequeue()); // "string_4"
Debug.Log($"Count: {buf.Count}"); // 3

buf.Enqueue("test1");
buf.Dequeue();
Debug.Log($"Count: {buf.Count}"); // 3

buf.Enqueue("string_8");
Debug.Log(buf.Pop()); // "string_8"
Debug.Log($"Count: {buf.Count}"); // 3

buf.Enqueue("string_9");
buf.Enqueue("test2");
Debug.Log($"Count: {buf.Count}"); // 5

(buf[0], buf[1]) = (buf[1], buf[0]); // swaps the first two elements
buf.Enqueue("string_12");
Console.WriteLine($"Count: {buf.Count}"); // 5

foreach(var x in buf.Items) {
  Debug.Log(x);
}

// string_6
// test1
// string_9
// test2
// string_12

Edit:
Bunny was faster :smiley:

Edit2:
Added Peek, Push, indexer setter and a test.

Edit3:
Peek had a typo, return yield → yield return, also Count was incorrect, added swap (and counting) to the test.

1 Like

:slight_smile: Great minds think alike. Or how we say in german “two idiots, one thought” :wink:

1 Like