/*Copyright 2002 by Insight Enterprise Systems, Inc., and Jason Smith*/
using System;
using System.Collections;
using System.Collections.Specialized;
namespace Iesi.Collections
{
/// <summary>
/// Contains a collection of static methods for creating sets and for
/// arithmetic operations on sets.
/// </summary>
public class Sets
{
private Sets(){}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>Hashtable</c>.
/// </summary>
/// <returns>An empty <c>GenericSet</c>.</returns>
public static GenericSet NewHashSet()
{
return new GenericSet(new Hashtable());
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>SortedList</c>.
/// </summary>
/// <returns>An empty <c>GenericSet</c>.</returns>
public static GenericSet NewSortedSet()
{
return new GenericSet(new SortedList());
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>HybridDictionary</c>.
/// </summary>
/// <returns>An empty <c>GenericSet</c>.</returns>
public static GenericSet NewHybridSet()
{
return new GenericSet(new HybridDictionary());
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>ListDictionary</c>.
/// </summary>
/// <returns>An empty <c>GenericSet</c>.</returns>
public static GenericSet NewListSet()
{
return new GenericSet(new ListDictionary());
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>Hashtable</c>.
/// </summary>
/// <returns>An initialized <c>GenericSet</c>.</returns>
public static GenericSet NewHashSet(ICollection initialValues)
{
return new GenericSet(new Hashtable(), initialValues);
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>SortedList</c>.
/// </summary>
/// <returns>An initialized <c>GenericSet</c>.</returns>
public static GenericSet NewSortedSet(ICollection initialValues)
{
return new GenericSet(new SortedList(), initialValues);
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>HybridDictionary</c>.
/// </summary>
/// <returns>An initialized <c>GenericSet</c>.</returns>
public static GenericSet NewHybridSet(ICollection initialValues)
{
return new GenericSet(new HybridDictionary(), initialValues);
}
/// <summary>
/// Create a new <c>GenericSet</c> based on a <c>ListDictionary</c>. Note that
/// this type of set should only be used if you know you will never have more than
/// 10 elements, or thereabouts. Some of the set operations can exceed O(n^2)
/// running time.
/// </summary>
/// <returns>An initialized <c>GenericSet</c>.</returns>
public static GenericSet NewListSet(ICollection initialValues)
{
return new GenericSet(new ListDictionary(), initialValues);
}
/// <summary>
/// Returns a set containing all the elements from both sets.
/// </summary>
/// <param name="a">A set of elements.</param>
/// <param name="b">A set of elements.</param>
/// <returns>A set containing the union of the input sets.</returns>
public static ISet Union(ISet a, ISet b)
{
ISet result = NewHybridSet(a);
result.AddAll(b);
return result;
}
/// <summary>
/// Returns a set containing all the elements common to both sets.
/// </summary>
/// <param name="a">A set of elements.</param>
/// <param name="b">A set of elements.</param>
/// <returns>The intersection of the two input sets.</returns>
public static ISet Intersect(ISet a, ISet b)
{
ISet result = NewHybridSet(a);
result.RetainAll(b);
return result;
}
/// <summary>
/// Returns a set containing all the elements from <c>A</c> with all the elements from
/// <c>B</c> removed.
/// </summary>
/// <param name="a">A set of elements.</param>
/// <param name="b">A set of elements.</param>
/// <returns>A set containing <c>A - B</c> elements.</returns>
public static ISet Minus(ISet a, ISet b)
{
ISet result = NewHybridSet(a);
result.RemoveAll(b);
return result;
}
}
/// <summary>
/// <p><c>GenericSet</c> is an implementation of <c>ISet</c> which uses an <c>IDictionary</c> object
/// to implement set functionality.</p>
///
/// <p>You can use any object that implements the <c>IDictionary</c> interface to hold set data.
/// You can define your own, or you can use one of the objects provided in the Framework. There are
/// a number of static methods on the <c>Sets</c> <see cref="Iesi.Collections.Sets"/> object that will create a new <c>GenericSet</c> based on
/// the <c>IDictionary</c> of your choice. There are a number of things you need to take into consideration
/// when choosing an implementation:</p>
/// <list type="bullet">
/// <item>
/// <description><c>Hashtable</c>: Good (very fast) for large sets where enumeration order is not important.</description>
/// </item>
/// <item>
/// <description><c>SortedList</c>: Good for large sets. Enumerates in sort order. A little slower
/// than <c>Hashtable</c> for very large datasets, but this effect is usually not noticable.</description>
/// </item>
/// <item>
/// <description><c>ListDictionary</c>: Good if you have lots of very small sets, since this
/// type of <c>IDictionary</c> does not incur as much overhead. Watch out though! If the sets
/// get beyond about 10 items each, running time on some set functions will increase by
/// O(n^2).</description>
/// </item>
/// <item>
/// <description><c>HybridDictionary</c>: If you have lots of small sets, but are unsure about the
/// maximum size you need, use this instead of <c>ListDictionary</c>. If the set is small, it will
/// use a <c>ListDictionary</c>, but if the set grows too large it will use a <c>Hashtable</c>
/// instead.</description>
/// </item>
/// </list>
/// <p>This object overrides both the <c>Equals()</c> and <c>GetHashCode()</c> object methods, so it
/// is safe to use as a key value in a dictionary that does not rely on keys, as long as all the elements
/// contained in the set implement <c>Equals()</c> and <c>GetHashCode()</c> as well.</p>
/// </summary>
public class GenericSet : ISet
{
//I'm using XOR to implement the hashcode. XOR when you add, XOR when you remove.
//As long as the hashcodes of all included objects are value based, it works.
private int _hashcode = unchecked((int)0xDEADBEEF);
private IDictionary _set;
private static object _object = new object();
/// <summary>
/// Creates a new <c>GenericSet</c> based on a <c>HybridDictionary</c>.
/// </summary>
public GenericSet() : this(new HybridDictionary())
{}
/// <summary>
/// Creates a new <c>GenericSet</c> based on the <c>IDictionary</c> of your choice.
/// </summary>
/// <param name="baseDictionary">An object that implements <c>IDictionary</c> which will contain the set data.</param>
public GenericSet(IDictionary baseDictionary)
{
_set = baseDictionary;
}
/// <summary>
/// Creates a new <c>GenericSet</c> based on the <c>IDictionary</c> of your choice, and
/// initializes it based on a collection of elements.
/// </summary>
/// <param name="baseDictionary">An object that implements <c>IDictionary</c> which will contain the set data.</param>
/// <param name="initialValues">A collection of elements that defines the initial set contents.</param>
public GenericSet(IDictionary baseDictionary, ICollection initialValues) : this(baseDictionary)
{
this.AddAll(initialValues);
}
/// <summary>
/// Adds the specified element to this set if it is not already present.
/// </summary>
/// <param name="o">The object to add to the set.</param>
/// <returns><c>true</c> is the object was added, <c>false</c> if it was already present.</returns>
public bool Add(object o)
{
if(_set[o] != null)
return false;
else
{
//The object we are adding is just a placeholder. The thing we are
//really concerned with is 'o', the key.
_set.Add(o, _object);
_hashcode ^= o.GetHashCode();
return true;
}
}
/// <summary>
/// Adds all the elements in the specified collection to the set if they are not already present.
/// </summary>
/// <param name="c">A collection of objects to add to the set.</param>
/// <returns><c>true</c> is the set changed as a result of this operation, <c>false</c> if not.</returns>
public bool AddAll(ICollection c)
{
bool changed = false;
foreach(object o in c)
changed |= this.Add(o);
return changed;
}
/// <summary>
/// Removes all objects from the set.
/// </summary>
public void Clear()
{
_set.Clear();
_hashcode = unchecked((int)0xDEADBEEF);
}
/// <summary>
/// Returns <c>true</c> if this set contains the specified element.
/// </summary>
/// <param name="o">The element to look for.</param>
/// <returns><c>true</c> if this set contains the specified element, <c>false</c> otherwise.</returns>
public bool Contains(object o)
{
return _set[o] != null;
}
/// <summary>
/// Returns <c>true</c> if the set contains all the elements in the specified collection.
/// </summary>
/// <param name="c">A collection of objects.</param>
/// <returns><c>true</c> if the set contains all the elements in the specified collection, <c>false</c> otherwise.</returns>
public bool ContainsAll(ICollection c)
{
foreach(object o in c)
{
if(!this.Contains(o))
return false;
}
return true;
}
/// <summary>
/// Returns <c>true</c> if this set contains no elements.
/// </summary>
public bool IsEmpty
{
get{return _set.Count == 0;}
}
/// <summary>
/// Removes the specified element from the set.
/// </summary>
/// <param name="o">The element to be removed.</param>
/// <returns><c>true</c> if the set contained the specified element, <c>false</c> otherwise.</returns>
public bool Remove(object o)
{
bool contained = this.Contains(o);
if(contained)
{
_hashcode ^= o.GetHashCode();
_set.Remove(o);
}
return contained;
}
/// <summary>
/// Remove all the specified elements from this set, if they exist in this set.
/// </summary>
/// <param name="c">A collection of elements to remove.</param>
/// <returns><c>true</c> if the set was modified as a result of this operation.</returns>
public bool RemoveAll(ICollection c)
{
bool changed = false;
foreach(object o in c)
changed |= this.Remove(o);
return changed;
}
/// <summary>
/// Retains only the elements in this set that are contained in the specified collection.
/// </summary>
/// <param name="c">Collection that defines the set of elements to be retained.</param>
/// <returns><c>true</c> if this set changed as a result of this operation.</returns>
public bool RetainAll(ICollection c)
{
//Put data from C into a set so we can use the Contains() method.
ISet cSet = Sets.NewHashSet(c);
//We are going to build a set of elements to remove.
ISet removeSet = Sets.NewHashSet();
foreach(object o in this)
{
//If C does not contain O, then we need to remove O from our
//set. We can't do this while iterating through our set, so
//we put it into RemoveSet for later.
if(!cSet.Contains(o))
removeSet.Add(o);
}
return this.RemoveAll(removeSet);
}
public void CopyTo(Array array, int index)
{
_set.Keys.CopyTo(array, index);
}
public int Count
{
get{return _set.Count;}
}
public bool IsSynchronized
{
get{return false;}
}
public object SyncRoot
{
get{return null;}
}
public IEnumerator GetEnumerator()
{
return _set.Keys.GetEnumerator();
}
public override bool Equals(object o)
{
if(o == null || !(o is ISet) || ((ISet)o).Count != this.Count)
return false;
else
{
foreach(object elt in ((ISet)o))
{
if(!this.Contains(elt))
return false;
}
return true;
}
}
public override int GetHashCode()
{
return _hashcode;
}
}
/// <summary>
/// A collection that contains no duplicate elements. This interface models the mathematical
/// <c>Set</c> abstraction.
/// </summary>
public interface ISet : ICollection
{
/// <summary>
/// Adds the specified element to this set if it is not already present.
/// </summary>
/// <param name="o">The object to add to the set.</param>
/// <returns><c>true</c> is the object was added, <c>false</c> if it was already present.</returns>
bool Add(object o);
/// <summary>
/// Adds all the elements in the specified collection to the set if they are not already present.
/// </summary>
/// <param name="c">A collection of objects to add to the set.</param>
/// <returns><c>true</c> is the set changed as a result of this operation, <c>false</c> if not.</returns>
bool AddAll(ICollection c);
/// <summary>
/// Removes all objects from the set.
/// </summary>
void Clear();
/// <summary>
/// Returns <c>true</c> if this set contains the specified element.
/// </summary>
/// <param name="o">The element to look for.</param>
/// <returns><c>true</c> if this set contains the specified element, <c>false</c> otherwise.</returns>
bool Contains(object o);
/// <summary>
/// Returns <c>true</c> if the set contains all the elements in the specified collection.
/// </summary>
/// <param name="c">A collection of objects.</param>
/// <returns><c>true</c> if the set contains all the elements in the specified collection, <c>false</c> otherwise.</returns>
bool ContainsAll(ICollection c);
/// <summary>
/// Returns <c>true</c> if this set contains no elements.
/// </summary>
bool IsEmpty {get;}
/// <summary>
/// Removes the specified element from the set.
/// </summary>
/// <param name="o">The element to be removed.</param>
/// <returns><c>true</c> if the set contained the specified element, <c>false</c> otherwise.</returns>
bool Remove(object o);
/// <summary>
/// Remove all the specified elements from this set, if they exist in this set.
/// </summary>
/// <param name="c">A collection of elements to remove.</param>
/// <returns><c>true</c> if the set was modified as a result of this operation.</returns>
bool RemoveAll(ICollection c);
/// <summary>
/// Retains only the elements in this set that are contained in the specified collection.
/// </summary>
/// <param name="c">Collection that defines the set of elements to be retained.</param>
/// <returns><c>true</c> if this set changed as a result of this operation.</returns>
bool RetainAll(ICollection c);
}
}
Submit an article or tip