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.