"Sack" data structure in C#

Question

The idea is to have a data structure that holds any number of objects of any type. Objects can be retrieved, or removed permanently, at random. Also, it can be cleared (or emptied).

This class just provides the ability to select a random object from a collection, with the option of removing it.

public class Sack
{
    private List<object> objects;

    public Sack()
    {
        objects = new List<object>();
    }

    public void Add<T>(T obj)
    {
        objects.Add(obj);
    }

    public object Retrieve()
    {
        int numberObjects = objects.Count;

        Random rand = new Random();
        int selectedIndex = rand.Next(0, numberObjects);

        return objects[selectedIndex];
    }

    public object Remove()
    {
        int numberObjects = objects.Count;

        Random rand = new Random();
        int selectedIndex = rand.Next(0, numberObjects);

        object selectedObject = objects[selectedIndex];
        objects.RemoveAt(selectedIndex);

        return selectedObject;
    }

    public void Empty()
    {
        objects.Clear();
    }
}

Answer 1

I would go and encourage you to use Generics instead of object. When you use object you're adding a casting operations in the back-scene, which means you might have a chance of getting casting exceptions at run-time. So, using generics would avoid that, and it would perform faster.

Also, in your code, you're using List, which is fine, but why you don't benefit from the existed interfaces such as ICollection, IList ..etc. These would give you many advantages, for instance, use ICollection such as Sack<T> : ICollection<T> you'll be able to use foreach loop (because it implements IEnumerable interfaces). So, make use of .NET existing interfaces, and don't take the long road.

Also, You can create an interface say ISack<T> : ICollection<T> add the additional methods that you want, then do Sack<T> : ISack<T>

for your random index, you can declare the Random and SelectedIndex at the class level, and then create a method that returns a random index.

example :

public class Sack<T>
{

    private readonly IList<T> objects = new List<T>();

    private readonly Random rand = new Random();

    private int SelectedIndex = -1;


    public T Retrieve()
    {
        RandomIndex();
        return objects[SelectedIndex];
    }

    public T Remove()
    {
        RandomIndex();
        var removedObject = objects[SelectedIndex];
        objects.Remove(removedObject);
        return removedObject;

    }

    private void RandomIndex()
    {
        // keep creating a new random index until you get a non-null object. 
        // [ToDo] : what if object.Count == 0 ? how should you handle it ? 
        while (true)
        {
            if ((SelectedIndex == -1 || objects[SelectedIndex] == null))
            {
                SelectedIndex = rand.Next(0, objects.Count);
            }
            else
            {
                break;
            }
        }
    }

}

I have added ICollection<T> to the class, which would give you more options and customization

 public class Sack<T> : ICollection<T>
    {
        private readonly IList<T> objects = new List<T>();

        private readonly Random rand = new Random();

        private int SelectedIndex = -1;

        public T this[int index]
        {
            get => this[index];
            set => this[index] = value;

        }
        public int Count => objects.Count;

        public bool IsReadOnly => objects.IsReadOnly;

        public void Add(T item)
        {
            objects.Add(item);
        }

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

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

        public void CopyTo(T[] array, int index) => objects.CopyTo(array, index);

        public IEnumerator<T> GetEnumerator() => objects.GetEnumerator();

        public int IndexOf(T item) => objects.IndexOf(item);

        public void Insert(int index, T item) => objects.Insert(index, item);

        public bool Remove(T item) => objects.Remove(item);

        public void RemoveAt(int index) => objects.RemoveAt(index);

        IEnumerator IEnumerable.GetEnumerator() => objects.GetEnumerator();

        public T Retrieve()
        {
            RandomIndex();
            return objects[SelectedIndex];
        }

        public T Remove()
        {
            RandomIndex();
            var removedObject = objects[SelectedIndex];
            objects.Remove(removedObject);
            return removedObject;

        }

        private void RandomIndex()
        {
            while (true)
            {
                if ((SelectedIndex == -1 || objects[SelectedIndex] == null))
                {
                    SelectedIndex = rand.Next(0, objects.Count);
                }
                else
                {
                    break;
                }

            }

        }

    }
}

Answer 2

• You don't use any method which is specific to List<T>. You should always code against interfaces if possible, meaning you should use IList<T> instead of List<T>.
• If Retrieved is called very often in a short time it is likely that you get the same object each time. This is because Random when instantiated will use the system clock to provide a seed value. You should have one Random object as a class-level field which should be instantiated in the constructor or directly.
• The genericness of the method Add<T> doesn't buy you anything. A simple Add(object) would be enough and does the exact same.
• objects should be made readonly because you don't change it.
• For Retrieve and Remove I wouldn't introduce the numberObjects variable but if you want to keep it you should rename it to e.g numberOfObjects.

Implementing the mentioned points would look like this:

public class Sack
{
    private readonly IList<object> objects = new List<object>();
    private readonly Random rand = new Random();

    public void Add(object obj)
    {
        objects.Add(obj);
    }

    public object Retrieve()
    {
        int selectedIndex = rand.Next(0, objects.Count);

        return objects[selectedIndex];
    }

    public object Remove()
    {
        int selectedIndex = rand.Next(0, objects.Count);

        object selectedObject = objects[selectedIndex];
        objects.RemoveAt(selectedIndex);

        return selectedObject;
    }

    public void Empty()
    {
        objects.Clear();
    }
}

Answer 3

Testing your code

To make your code testable, you should allow the code that uses this Sack to supply a custom random number generator.

In your unit test for the Sack class, you should create a custom TestingRandom class that derives from Random and overrides the Next(int, int) method. In your TestingRandom class you should ensure that the amount of requested randomness is exactly what you expect.

Given a set of 5 things, when you take them all out of the Sack, your random number generator must have generated randomness 5 * 4 * 3 * 2 * 1. Not more, not less. This ensures that the distribution of objects returned by the Sack can be fair. It doesn't guarantee that, but it detects mistakes quickly.

Performance

Do you use this class to manage millions of objects? Because if you do, the RemoveAt call will make it very slow as that method needs to copy half of the array on average.

To improve performance, you can change the code so that it always removes the element at the end:

var index = RandomIndex();
var obj = objects[index];
objects[index] = objects[objects.Count - 1];
objects.RemoveAt(objects.Count - 1);
return obj;

Answer 4

Since the Retrieve and the Remove methods share much of the same code, and since Remove also retrieves, I would suggest merging the 2. Adding a default argument and a conditional, to the Retrieve method, would do the trick:

public object Retrieve(bool remove = false)
{
    int selectedIndex = rand.Next(0, objects.Count);
    object selectedObject = objects[selectedIndex];
    if(remove)
    {
        objects.RemoveAt(selectedIndex);
    {
    return selectedObject;
}

Answer 5

I'd inherit from List to avoid proxying functions like Clear() with no value-add, or write an extension method over List for the randomized retrieval.

public static class RandomRemover
{
    private static readonly Random rand = new Random();

    public static object Retrieve(this List<object> target)
    {
        int selectedIndex = rand.Next(0, target.Count);
        return target[selectedIndex];
    }
}

cf. open/closed principle

Answer 6

Retrieve and Remove both share this piece of code:

int numberObjects = objects.Count;

Random rand = new Random();
int selectedIndex = rand.Next(0, numberObjects);

I would recommend refactoring it into a private helper:

int GetRandomIndex()
{
    int numberObjects = objects.Count;

    Random rand = new Random();
    int selectedIndex = rand.Next(0, numberObjects);
}

And then just call it like this:

public object Retrieve()
{
    int selectedIndex = GetRandomIndex();

    return objects[selectedIndex];
}