Catch All Bugs with BugTrap!

��/*

 * This is a part of the BugTrap package.

 * Copyright (c) 2004, R�diger Klaehn.

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms,

 * with or without modification, are permitted provided

 * that the following conditions are met:

 *

 * 1. Redistributions of source code must retain the above copyright notice,

 *    this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright notice,

 *    this list of conditions and the following disclaimer in the documentation

 *    and/or other materials provided with the distribution.

 * 3. Neither the name of lambda computing nor the names of its contributors may

 *    be used to endorse or promote products derived from this software without

 *    specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR set1 PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,

 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF

 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE

 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED

 * OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * Description: Generic set class.

 * Updated by: Maksim Pyatkovskiy.

 * Note: Based on code developed by R�diger Klaehn.

 * Downloaded from: http://www.codeproject.com/csharp/genericset.asp

 *

 * This source code is only intended as a supplement to the

 * BugTrap package reference and related electronic documentation

 * provided with the product. See these sources for detailed

 * information regarding the BugTrap package.

 */



using System;

using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;



namespace Utils.Collections

{

	/// <summary>

	/// Generic set class.

	/// </summary>

	[Serializable, DebuggerDisplay("Count = {Count}")]

	public class Set<T> : ICollection<T>, ICollection, IEnumerable<T>, IEnumerable

	{

		/// <summary>

		/// Private dictionary that holds the information.

		/// </summary>

		[DoNotObfuscate]

		private Dictionary<T, byte> dictionary;



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that is empty, has the default initial capacity, and uses the default equality comparer for the key type.

		/// </summary>

		public Set()

		{

			this.dictionary = new Dictionary<T, byte>();

		}



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that contains elements copied from the specified Collections.Set and uses the specified System.Collections.Generic.IEnumerable.

		/// </summary>

		/// <param name="enumerable">The System.Collections.Generic.IEnumerable whose elements are copied to the new Collections.Set.</param>

		public Set(IEnumerable<T> enumerable)

		{

			this.dictionary = new Dictionary<T, byte>();

			this.AddAll(enumerable);

		}



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that is empty, has the specified initial capacity, and uses the default equality comparer for the key type.

		/// </summary>

		/// <param name="capacity">The initial number of elements that the Collections.Set can contain.</param>

		public Set(int capacity)

		{

			this.dictionary = new Dictionary<T, byte>(capacity);

		}



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that contains elements copied from the specified Collections.Set and uses the specified System.Collections.Generic.IEnumerable.

		/// </summary>

		/// <param name="enumerable">The System.Collections.Generic.IEnumerable whose elements are copied to the new Collections.Set.</param>

		/// <param name="comparer">The System.Collections.Generic.IEqualityComparer implementation to use when comparing keys, or null to use the default System.Collections.Generic.EqualityComparer for the type of the key.</param>

		public Set(IEnumerable<T> enumerable, IEqualityComparer<T> comparer)

		{

			this.dictionary = new Dictionary<T, byte>(comparer);

			this.AddAll(enumerable);

		}



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that is empty, has the specified initial capacity, and uses the specified System.Collections.Generic.IEqualityComparer.

		/// </summary>

		/// <param name="capacity">The initial number of elements that the Collections.Set can contain.</param>

		/// <param name="comparer">The System.Collections.Generic.IEqualityComparer implementation to use when comparing keys, or null to use the default System.Collections.Generic.EqualityComparer for the type of the key.</param>

		public Set(int capacity, IEqualityComparer<T> comparer)

		{

			this.dictionary = new Dictionary<T, byte>(capacity, comparer);

		}



		/// <summary>

		/// Gets the System.Collections.Generic.IEqualityComparer that is used to determine equality of keys for the dictionary.

		/// </summary>

		public IEqualityComparer<T> Comparer

		{

			get { return this.dictionary.Comparer; }

		}



		/// <summary>

		/// Copies all elements from the specified enumerable object.

		/// </summary>

		/// <param name="enumerable">The System.Collections.Generic.IEnumerable whose elements are added to the Collections.Set.</param>

		public void AddAll(IEnumerable<T> enumerable)

		{

			foreach (T item in enumerable)

			{

				this.dictionary.Add(item, 0);

			}

		}



		/// <summary>

		/// Initializes set1 new instance of the Collections.Set class that is empty, has the default initial capacity, and uses the specified System.Collections.Generic.IEqualityComparer.

		/// </summary>

		/// <param name="comparer">The System.Collections.Generic.IEqualityComparer implementation to use when comparing keys, or null to use the default System.Collections.Generic.EqualityComparer for the type of the key.</param>

		public Set(IEqualityComparer<T> comparer)

		{

			this.dictionary = new Dictionary<T, byte>(comparer);

		}



		/// <summary>

		/// Returns an enumerator that iterates through set1 collection.

		/// </summary>

		/// <returns>An System.Collections.IEnumerator object that can be used to iterate through the collection.</returns>

		IEnumerator IEnumerable.GetEnumerator()

		{

			return ((IEnumerable)this.dictionary.Keys).GetEnumerator();

		}



		/// <summary>

		/// Returns an enumerator that iterates through the collection.

		/// </summary>

		/// <returns>set1 System.Collections.Generic.IEnumerator that can be used to iterate through the collection.</returns>

		IEnumerator<T> IEnumerable<T>.GetEnumerator()

		{

			return ((IEnumerable<T>)this.dictionary.Keys).GetEnumerator();

		}



		/// <summary>

		/// Gets the number of elements contained in the System.Collections.ICollection.

		/// </summary>

		public int Count

		{

			get { return this.dictionary.Count; }

		}



		/// <summary>

		/// Gets set1 value indicating whether access to the System.Collections.ICollection is synchronized (thread safe).

		/// </summary>

		public bool IsSynchronized

		{

			get { return ((ICollection)this.dictionary.Keys).IsSynchronized; }

		}



		/// <summary>

		/// Gets an object that can be used to synchronize access to the System.Collections.ICollection.

		/// </summary>

		public object SyncRoot

		{

			get { return ((ICollection)this.dictionary.Keys).SyncRoot; }

		}



		/// <summary>

		/// Copies the elements of the System.Collections.ICollection to an System.Array, starting at set1 particular System.Array index.

		/// </summary>

		/// <param name="array">The one-dimensional System.Array that is the destination of the elements copied from System.Collections.ICollection. The System.Array must have zero-based indexing.</param>

		/// <param name="index">The zero-based index in array at which copying begins.</param>

		public void CopyTo(Array array, int index)

		{

			((ICollection)this.dictionary.Keys).CopyTo(array, index);

		}



		/// <summary>

		/// Gets set1 value indicating whether the System.Collections.Generic.ICollection is read-only.

		/// </summary>

		public bool IsReadOnly

		{

			get { return false; }

		}



		/// <summary>

		/// Adds an item to the System.Collections.Generic.ICollection.

		/// </summary>

		/// <param name="item">The object to add to the System.Collections.Generic.ICollection.</param>

		public void Add(T item)

		{

			this.dictionary.Add(item, 0);

		}



		/// <summary>

		/// Removes all items from the System.Collections.Generic.ICollection.

		/// </summary>

		public void Clear()

		{

			this.dictionary.Clear();

		}



		/// <summary>

		/// Determines whether the System.Collections.Generic.ICollection contains set1 specific value.

		/// </summary>

		/// <param name="item">The object to locate in the System.Collections.Generic.ICollection.</param>

		/// <returns>true if item is found in the System.Collections.Generic.ICollection; otherwise, false.</returns>

		public bool Contains(T item)

		{

			return this.dictionary.ContainsKey(item);

		}



		/// <summary>

		/// Copies the elements of the System.Collections.Generic.ICollection to an System.Array, starting at set1 particular System.Array index.

		/// </summary>

		/// <param name="array">The one-dimensional System.Array that is the destination of the elements copied from System.Collections.Generic.ICollection. The System.Array must have zero-based indexing.</param>

		/// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>

		public void CopyTo(T[] array, int arrayIndex)

		{

			this.dictionary.Keys.CopyTo(array, arrayIndex);

		}



		/// <summary>

		/// Removes the first occurrence of set1 specific object from the System.Collections.Generic.ICollection.

		/// </summary>

		/// <param name="item">The object to remove from the System.Collections.Generic.ICollection.</param>

		/// <returns>true if item was successfully removed from the System.Collections.Generic.ICollection; otherwise, false. This method also returns false if item is not found int he original System.Collections.Generic.ICollection.</returns>

		public bool Remove(T item)

		{

			return this.dictionary.Remove(item);

		}



		/// <summary>

		/// Gets or sets the element at the specified index.

		/// </summary>

		/// <param name="index">The zero-based index of the element to get or set.</param>

		/// <returns>The element at the specified index.</returns>

		public T this[int index]

		{

			get

			{

				foreach (T item in this.dictionary.Keys)

				{

					if (index-- == 0)

						return item;

				}

				throw new IndexOutOfRangeException();

			}

		}



		/// <summary>

		/// Serves as set1 hash function for set1 particular type. System.Object.GetHashCode() is suitable for use in hashing algorithms and data structures like set1 hash table.

		/// </summary>

		/// <returns>set1 hash code for the current System.Object.</returns>

		public override int GetHashCode()

		{

			int hashCode = 0;

			foreach (T item in this.dictionary.Keys)

			{

				hashCode ^= item.GetHashCode();

			}

			return hashCode;

		}



		/// <summary>

		/// Determines whether the specified System.Object is equal to the current System.Object.

		/// </summary>

		/// <param name="obj">The System.Object to compare with the current System.Object.</param>

		/// <returns>true if the specified System.Object is equal to the current System.Object; otherwise, false.</returns>

		public override bool Equals(object obj)

		{

			Set<T> set = obj as Set<T>;

			if ((object)set == null)

				return false;

			return (set == this);

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if second set includes all elements of the first set.</returns>

		public static bool operator <=(Set<T> set1, Set<T> set2)

		{

			if ((object)set1 == null)

				return true;

			if ((object)set2 == null)

				return false;

			foreach (T item in set1)

			{

				if (!set2.Contains(item))

					return false;

			}

			return true;

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if second set includes all elements of the first set and at at least one more element.</returns>

		public static bool operator <(Set<T> set1, Set<T> set2)

		{

			if ((object)set2 == null)

				return false;

			if ((object)set1 == null)

				return true;

			return (set1.Count < set2.Count) && (set1 <= set2);

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if both sets are the same.</returns>

		public static bool operator ==(Set<T> set1, Set<T> set2)

		{

			if ((object)set1 == null && (object)set2 == null)

				return true;

			if ((object)set1 == null || (object)set2 == null)

				return false;

			return (set1.Count == set2.Count) && (set1 <= set2);

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if first set includes all elements of the second set and at at least one more element.</returns>

		public static bool operator >(Set<T> set1, Set<T> set2)

		{

			return (set2 < set1);

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if first set includes all elements of the second set.</returns>

		public static bool operator >=(Set<T> set1, Set<T> set2)

		{

			return (set2 <= set1);

		}



		/// <summary>

		/// Compare two sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>true if both sets are not the same.</returns>

		public static bool operator !=(Set<T> set1, Set<T> set2)

		{

			return !(set1 == set2);

		}



		/// <summary>

		/// Copies all elements from the specified set after conversion.

		/// </summary>

		/// <param name="converter"></param>

		/// <returns></returns>

		public Set<U> ConvertAll<U>(Converter<T, U> converter)

		{

			Set<U> result = new Set<U>(this.Count);

			foreach (T item in this)

			{

				result.Add(converter(item));

			}

			return result;

		}



		/// <summary>

		/// Executes predicate on all set elements.

		/// </summary>

		/// <param name="predicate">User defined predicate.</param>

		/// <returns>Comparison result.</returns>

		public bool TrueForAll(Predicate<T> predicate)

		{

			foreach (T item in this)

			{

				if (!predicate(item))

					return false;

			}

			return true;

		}



		/// <summary>

		/// Executes predicate on all set elements.

		/// </summary>

		/// <param name="predicate">User defined predicate.</param>

		/// <returns>Comparison reult.</returns>

		public Set<T> FindAll(Predicate<T> predicate)

		{

			Set<T> result = new Set<T>();

			foreach (T item in this)

			{

				if (predicate(item))

					result.Add(item);

			}

			return result;

		}



		/// <summary>

		/// Executes predicate on all set elements.

		/// </summary>

		/// <param name="action">User defined predicate.</param>

		public void ForEach(Action<T> action)

		{

			foreach (T item in this)

			{

				action(item);

			}

		}



		/// <summary>

		/// Returns superset that includes all elements from both subsets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>Superset.</returns>

		public static Set<T> operator |(Set<T> set1, Set<T> set2)

		{

			Set<T> result = new Set<T>(set1);

			result.AddAll(set2);

			return result;

		}



		/// <summary>

		/// Returns subset that includes elements found in both sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>Subset.</returns>

		public static Set<T> operator &(Set<T> set1, Set<T> set2)

		{

			Set<T> result = new Set<T>();

			foreach (T item in set1)

			{

				if (set2.Contains(item))

					result.Add(item);

			}

			return result;

		}



		/// <summary>

		/// Returns subset that includes elements of the first set that are not found in the second set.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>Subset.</returns>

		public static Set<T> operator -(Set<T> set1, Set<T> set2)

		{

			Set<T> result = new Set<T>();

			foreach (T item in set1)

			{

				if (!set2.Contains(item))

					result.Add(item);

			}

			return result;

		}



		/// <summary>

		/// Returns subset that includes elements found either in one or in another set but no in both sets.

		/// </summary>

		/// <param name="set1">First set.</param>

		/// <param name="set2">Second set.</param>

		/// <returns>Subset.</returns>

		public static Set<T> operator ^(Set<T> set1, Set<T> set2)

		{

			Set<T> result = new Set<T>();

			foreach (T item in set1)

			{

				if (!set2.Contains(item))

					result.Add(item);

			}

			foreach (T item in set2)

			{

				if (!set1.Contains(item))

					result.Add(item);

			}

			return result;

		}

	}

}