The Computer Machine Whisperer

One of the great new additions to .NET 3.5 is HashSet<T>. Unfortunately, you can’t run the 3.5 framework with Win2K, which is what my users are forced to use until we get a company-wide upgrade to XP or higher. We get to develop in VS 2008 on XP, and use some of the new C# 3.0 language features, but we still have to compile to 2.0, and because the users can’t run System.Core on Win2K, that means LINQ and HashSet<T> are out, for now.

Or so I thought, until I figured out a way to write it myself using a Dictionary<T, object> as the internal storage. Feel free to use it as you wish:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;

public class HashSet<T> : ICollection<T>, ISerializable, IDeserializationCallback
{
private readonly Dictionary<T, object> dict;

public HashSet()
{
dict = new Dictionary<T, object>();
}

public HashSet(IEnumerable<T> items) : this()
{
if (items == null)
{
return;
}

foreach (T item in items)
{
Add(item);
}
}

public HashSet<T> NullSet { get { return new HashSet<T>(); } }

#region ICollection<T> Members

public void Add(T item)
{
if (null == item)
{
throw new ArgumentNullException("item");
}

dict[item] = null;
}

public void Clear()
{
dict.Clear();
}

public bool Contains(T item)
{
return dict.ContainsKey(item);
}

public void CopyTo(T[] array, int arrayIndex)
{
if (array == null) throw new ArgumentNullException("array");
if (arrayIndex < 0 || arrayIndex >= array.Length || arrayIndex >= Count)
{
throw new ArgumentOutOfRangeException("arrayIndex");
}

dict.Keys.CopyTo(array, arrayIndex);
}

public bool Remove(T item)
{
return dict.Remove(item);
}

public int Count
{
get { return dict.Count; }
}

public bool IsReadOnly
{
get
{
return false;
}
}

#endregion

public HashSet<T> Union(HashSet<T> set)
{
HashSet<T> unionSet = new HashSet<T>(this);

if (null == set)
{
return unionSet;
}

foreach (T item in set)
{
if (unionSet.Contains(item))
{
continue;
}

unionSet.Add(item);
}

return unionSet;
}

public HashSet<T> Subtract(HashSet<T> set)
{
HashSet<T> subtractSet = new HashSet<T>(this);

if (null == set)
{
return subtractSet;
}

foreach (T item in set)
{
if (!subtractSet.Contains(item))
{
continue;
}

subtractSet.dict.Remove(item);
}

return subtractSet;
}

public bool IsSubsetOf(HashSet<T> set)
{
HashSet<T> setToCompare = set ?? NullSet;

foreach (T item in this)
{
if (!setToCompare.Contains(item))
{
return false;
}
}

return true;
}

public HashSet<T> Intersection(HashSet<T> set)
{
HashSet<T> intersectionSet = NullSet;

if (null == set)
{
return intersectionSet;
}

foreach (T item in this)
{
if (!set.Contains(item))
{
continue;
}

intersectionSet.Add(item);
}

foreach (T item in set)
{
if (!Contains(item) || intersectionSet.Contains(item))
{
continue;
}

intersectionSet.Add(item);
}

return intersectionSet;
}

public bool IsProperSubsetOf(HashSet<T> set)
{
HashSet<T> setToCompare = set ?? NullSet;

// A is a proper subset of a if the b is a subset of a and a != b
return (IsSubsetOf(setToCompare) && !setToCompare.IsSubsetOf(this));
}

public bool IsSupersetOf(HashSet<T> set)
{
HashSet<T> setToCompare = set ?? NullSet;

foreach (T item in setToCompare)
{
if (!Contains(item))
{
return false;
}
}

return true;
}

public bool IsProperSupersetOf(HashSet<T> set)
{
HashSet<T> setToCompare = set ?? NullSet;

// B is a proper superset of a if b is a superset of a and a != b
return (IsSupersetOf(setToCompare) && !setToCompare.IsSupersetOf(this));
}

public List<T> ToList()
{
return new List<T>(this);
}

#region Implementation of ISerializable

public void GetObjectData(SerializationInfo info, StreamingContext context)
{
if (info == null) throw new ArgumentNullException("info");
dict.GetObjectData(info, context);
}

#endregion

#region Implementation of IDeserializationCallback

public void OnDeserialization(object sender)
{
dict.OnDeserialization(sender);
}

#endregion

#region Implementation of IEnumerable

public IEnumerator<T> GetEnumerator()
{
return dict.Keys.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

#endregion
}