Empty Collections

I was reading one of my favourite Java programming books this morning and came across a simple coding pattern that I've been practicing in C# since I first read this book. I feel it's a useful thing to share here. For those of you that are interested, the book is "Effective Java" by Joshua Bloch. It contains a series of bite sized chunks of tips/recommendations that Java developers can use. Although the book focuses on the Java programming language, I feel there are lots of things it discusses that are transferrable to any programming language. One of these tips is the topic of this post.

Joshua mentions that it's better to return empty collections rather than null when writing methods. The reason being that any code calling your method then doesn't need to explicitly handle a special null case. Returning an empty collection makes the null check redundant and results in much cleaner method calling code. In C#, the System.Linq.Enumerable class has a useful generic method called Empty. When called with a type parameter, this method returns an empty instance of IEnumerable<T> (where T is your type parameter).

An example use:

public class House
{
    public IEnumerable<Person> CurrentOccupants { get; set; }
        
    public House()
    {
        CurrentOccupants = Enumerable.Empty<Person>();
    }
}

I also find that this method of instantiating (or returning) a collection states my intent more clearly than something like:

CurrentOccupants = new List<Person();

The MSDN documentation for Enumerable.Empty states that it caches the returned empty sequence of type TResult - so using this consistently for the same types can give (probably negligible) performance or memory usage advantages.

This pattern also reduces the chances of null reference errors from being raised in calling code. As mentioned above, the calling code then doesn't need to go through the usual boiler-plate null check code on the returned collection. Naturally, this leads to cleaner code as the calling code can process the collection the same way if it has items or doesn't have items within it.

C# Set Implementation (pre-.NET 3.5)

I was recently working on a .NET 3.0 project and found that this version of the framework didn't have any support for a mathematical Set collection. As of .NET 3.5 there is the System.Collections.Generic.HashSet implementation, however, I was working on a WinForms project and updating the framework on the client machines was out of scope for this piece of work.

I had some spare time available and thought it would be a good exercise to write a custom generic Set collection. The first step was to define an interface:

using System.Collections.Generic;

...

public interface ISet<T> : ICollection<T>
{
    void UnionWith(ISet<T> set);
    void IntersectWith(ISet<T> set);
}

By inheriting from ICollection, we get all of the generally useful collection-based methods included in the ISet interface (e.g. Add, Clear, Contains etc.). I just had two methods to add to those, these were the set union and set intersection operations.

The next step was the implementation of the set. To keep things simple, I opted for a list-based implementation. I used the adapter pattern to map the ISet interface to a list interface. Therefore, the internal representation of the Set was actually an instance of System.Collections.Generic.List. By using this approach, I could delegate a lot of the method logic to use the list method implementations (i.e. Clear, Contains, CopyTo and Remove). The only custom logic I needed to write was the Add method (to avoid adding items already within the set), UnionWith method, IntersectWith method, ToString method and the readonly indexer. The implementation is below:

/// <summary>
/// A list-based implementation of a mathematical set.
/// </summary>
public sealed class ListBasedSet<T> : ISet<T>
{
    private IList<T> _thisSet = new List<T>();

    /// <summary>
    /// Gets the number of elements contained in this set.
    /// </summary>
    public int Count { get { return _thisSet.Count; } }

    /// <summary>
    /// Gets a value indicating whether this set is readonly.
    /// </summary>
    public bool IsReadOnly { get { return false; } }

    /// <summary>
    /// Gets the item at the specified index in the set.
    /// </summary>
    /// <param name="i">
    /// Index of the item to retrieve from the set.
    /// </param>
    /// <returns>Item at the specified index</returns>
    public T this[int i] { get { return _thisSet[i]; } }

    /// <summary>
    /// Adds item into the set if this set does not already
    /// contain the item.
    /// </summary>
    /// <param name="item">Item to add to the set.</param>
    public void Add(T item)
    {
        if (!Contains(item))
            _thisSet.Add(item);
    }

    /// <summary>
    /// Clears the items from the set resulting in an empty set.
    /// </summary>
    public void Clear()
    {
        _thisSet.Clear();
    }

    /// <summary>
    /// Determines if the specified item is within the set.
    /// </summary>
    /// <param name="item">
    /// The object to locate in the set.
    /// </param>
    /// <returns>
    /// true if item is found in the set; false otherwise.
    /// </returns>
    public bool Contains(T item)
    {
        return _thisSet.Contains(item);
    }

    /// <summary>
    /// Copies the entire set to a one-dimensional array, 
    /// starting at the specified target index of the target 
    /// array.
    /// </summary>
    /// <param name="array">
    /// The one-dimensional array to copy to.
    /// </param>
    /// <param name="arrayIndex">
    /// The zero-based index in array at which copying begins.
    /// </param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        _thisSet.CopyTo(array, arrayIndex);
    }

    /// <summary>
    /// Removes the specified item from the set.
    /// </summary>
    /// <param name="item">Item to remove.</param>
    /// <returns>
    /// true if item is successfully removed; otherwise, false. 
    /// This method also returns false if item was not found 
    /// in the set.
    /// </returns>
    public bool Remove(T item)
    {
        return _thisSet.Remove(item);
    }

    /// <summary>
    /// Returns an enumerator that iterates through the set.
    /// </summary>
    /// <returns>
    /// An IEnumerator object that can be used to iterate 
    /// through the set.
    /// </returns>
    public IEnumerator<T> GetEnumerator()
    {
        return _thisSet.GetEnumerator();
    }

    /// <summary>
    /// Returns an enumerator that iterates through the set.
    /// </summary>
    /// <returns>
    /// An IEnumerator object that can be used to iterate 
    /// through the set.
    /// </returns>
    System.Collections.IEnumerator 
        System.Collections.IEnumerable.GetEnumerator()
    {
        return _thisSet.GetEnumerator();
    }

    /// <summary>
    /// Modifies this set to contain all elements that are 
    /// present in itself, the specified collection, or both.
    /// </summary>
    /// <param name="otherSet">The set to union with.</param>
    public void UnionWith(ISet<T> otherSet)
    {
        foreach (var item in otherSet)
            Add(item);
    }

    /// <summary>
    /// Modifies this set to contain only the elements that are 
    /// present in it and in the specified collection.
    /// </summary>
    /// <param name="otherSet">The set to intersect with.</param>
    public void IntersectWith(ISet<T> otherSet)
    {
        var itemsToRemove = new List<T>();

        for (int i  = 0; i < Count; i++)
        {
            T item = this[i];

            if (!otherSet.Contains(item))
                itemsToRemove.Add(item);
        }

        foreach (var itemToRemove in itemsToRemove)
            Remove(itemToRemove);
    }

    /// <summary>
    /// Returns a string representation of this set
    /// </summary>
    /// <returns>A string representation of this set</returns>
    public override string ToString()
    {
        var setStringBuilder = new StringBuilder();
        setStringBuilder.Append("{");

        foreach (var item in _thisSet)
            setStringBuilder.Append(
                string.Format(" {0},", item));
            
        return string.Format("{0} }}", 
            setStringBuilder.ToString().TrimEnd(','));
    }
}

Example usage:

ISet<string> set = new ListBasedSet<string> 
    { "Mars", "Earth", "Pluto" };
ISet<string> otherSet = new ListBasedSet<string> 
    { "Jupiter", "Earth", "Pluto", "Venus" };
ISet<string> earthSet = new ListBasedSet<string> 
    { "Earth" };
ISet<string> emptySet = new ListBasedSet<string>();

set.UnionWith(otherSet);
Console.WriteLine("set UNION otherset = {0}", set);

Console.WriteLine("|set| (cardinality of set) = {0}", set.Count);

set.IntersectWith(earthSet);
Console.WriteLine("set INTERSECTION earthSet = {0}", set);

set.UnionWith(emptySet);
Console.WriteLine("set UNION emptySet = {0}", set);

set.IntersectWith(emptySet);
Console.WriteLine("set INTERSECTION emptySet = {0}", set);

You can download the source files for the ISet interface and the ListBasedSet class from here.