MultiList: .NET Generic List with Multiple Sort Orders

// 
// MultiList library - Copyright 2008 by Michael Moorman / AsAbove.net
// This work is released to the public domain, and may be used for any purpose, without any conditions.
// 
// History:
// 01/20/2008 initial version
// 02/04/2008 add the IndexRange class for enumerating ranges, for use as a return value from
//		the FindIndexes methods.
//
using System;
using System.Collections.Generic;
using System.Text;
using AsAbove.Collections.Exception;

namespace AsAbove.Collections
{
	/// <summary>
	/// The MultiList class manages multiple sort orders on lists. It is best suited to object lists where 
	/// searching for objects is required on more than one criteria. It is also suited when searches must be done
	/// on complete objects as well as properties within objects. The class employs a binary search algorithm to
	/// find objects in lists, as well as to insert objects in sorted order within lists.
	/// </summary>
	/// <remarks>
	/// <B>Sort Criteria</B><para></para>
	/// When planning an implementation of this class, the first effort must be gaining an understanding of the
	/// different sorts to be performed on the object.
	/// Each unique sort criteria must be contained in a custom class that implements <i>at least</i> 
	/// the <see cref="System.Collections.Generic.IComparer&lt;T&gt;">IComparer&lt;T&gt;</see> interface. In addition to 
	/// the IComparer interface, which compares two instances of the complete object type, the custom class
	/// may also implement the <see cref="ITypeComparer&lt;T&gt;">ITypeComparer&lt;T&gt;</see> interface defined by
	/// this library. The ITypeComparer interface is used to sort by individual properties or sets of properties
	/// contained in the objects. <para></para>For instance, consider a Person class that contains properties for name, age, and profession. 
	/// To sort on the age property, a custom class called AgeComparer is written which implements both the IComparer and ITypeComparer interfaces.
	/// The IComparer interface compares the age property in two distinct Person objects, 
	/// to order them relative to each other. The ITypeComparer interface, on the other hand, compares the age property
	/// of a single Person object to an integer value given by the client in a search operation.
	/// <para></para>
	/// Here are some overview points about the MultiList class:
	/// <ul>
	/// <li>Any property that forms the basis of a sort must be immutable, but -</li>
	/// <li>If a sort property must be modified, the client code should take care to remove the object
	/// with the <see cref="Remove(T)">Remove</see> method before the modification, then reinsert it with the <see cref="Add(T)">Add</see> method after the modification</li>
	/// <li>The class employs a binary search algorithm for efficiency</li>
	/// <li>Object properties that are sort criteria are not required to be unique</li>
	/// <li>If a sort criteria contains duplicates in the list, a search will return the first in the series</li>
	/// <li>No direct access to the underlying lists is allowed, but lists may be enumerated with foreach</li>
	/// <li>The <see cref="ActiveList">ActiveList</see> property can be set before enumeration,
	/// to indicate which sort order to apply to subsequent enumerations</li>
	/// <li>The class also implements an indexer to allow array access to objects in the currently <see cref="ActiveList">active list</see></li>
	/// <li>A single call to the <see cref="Add(T)">Add</see> method adds the object to all mangaged lists</li>
	/// <li>A single call to the <see cref="Remove(T)">Remove</see> method removes the object from all mangaged lists</li>
	/// </ul>
	/// </remarks>
	/// <typeparam name="T">The type of object to store in the lists managed by this class</typeparam>
	public class MultiList<T> : IEnumerable<T>
	{
		#region members
		private List<T>[] _list;	// array of lists, one for each sort order
		private IComparer<T>[] _comparers;	// array of comparison classes which implement the IComparer interface
		private Type _enumeratorType;	// the enumerator type given in the constructor is held for later
		// validation on enumerators passed to all other methods.
		private int _activeListIndex = 0;	// current active sort order
		#endregion

		#region constants
		/// <summary>
		/// The NotFound constant is returned by Find methods to indicate that a record search is unsuccessful.
		/// </summary>
		public static int NotFound = -1;
		#endregion

		#region constructor
		/// <summary>
		/// The MultiList constructor initializes the object by preparing one list for each required sort order,
		/// and by storing a reference to an array of client-supplied class objects that implement the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;">IComparer&lt;T&gt;</see> interface. The constructor verifies
		/// that the type supplied in the <typeparamref name="sortOrderEnumerator">sortOrderEnumerator</typeparamref> argument is an enumerator type, and that the number
		/// of IComparer objects matches the number of constants in the enumerator.
		/// </summary>
		/// <remarks>
		/// <para>
		/// The use of an enumerator to define sort orders would not be strictly necessary to accomplish the 
		/// functionality of this class; it is done to assist in developing client code with clear intent.
		/// The developer should follow some guidelines in this regard:
		/// </para>
		/// <ul>
		/// <li>Do not override the values of the constants in the enumerator.</li>
		/// <li>For consistency, name the enumerator constants to match the names of the class objects in the IComparer array.</li>
		/// </ul>
		/// </remarks>
		/// <param name="sortOrderEnumerator">The Type for an enumerator that defines the sort orders to be managed by the class</param>
		/// <param name="comparers">An array of IComparer class objects, corresponding in order and number to the constants of the sortOrderEnumerator argument</param>
		/// Throws <exception cref="EnumeratorTypeExpectedException">EnumeratorTypeExpectedException</exception> if the sortOrderEnumerator
		/// argument is not an enumerator type<p></p>
		/// Throws <exception cref="InsufficientIComparerCountException">InsufficientIComparerCountException</exception> if the number of
		/// objects in the comparers array does not equal the number of constants in the sortOrderEnumerator enumerator type
		public MultiList (Type sortOrderEnumerator, params IComparer<T>[] comparers)
		{
			if (false == sortOrderEnumerator.IsEnum)
			{
				throw new EnumeratorTypeExpectedException ();
			}
			_enumeratorType = sortOrderEnumerator;

			int countOfEnums = System.Enum.GetValues (sortOrderEnumerator).Length;
			if (countOfEnums != comparers.Length)
			{
				throw new InsufficientIComparerCountException (countOfEnums);
			}
			_list = new List<T>[countOfEnums];
			_comparers = new IComparer<T>[countOfEnums];
			for (int i = 0; i < countOfEnums; i++)
			{
				_list[i] = new List<T> ();
				_comparers[i] = comparers[i];
			}
		}
		#endregion

		#region add objects to lists
		/// <summary>
		/// Add an object to each managed list, in sorted order.
		/// </summary>
		/// <param name="obj">object to add to the list</param>
		public void Add (T obj)
		{
			for (int i = 0; i < _list.Length; i++)
			{
				int position;
				if (true == BSearch (_list[i], _comparers[i], obj, out position))
				{
					_list[i].Insert (FindLastOf (_list[i], _comparers[i], position), obj);
				}
				else
				{
					_list[i].Insert (position, obj);
				}
			}
		}
		#endregion

		#region object access methods
		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <param name="obj">The object to match</param>
		/// <returns>The offset of the matching object in the managed list, or <see cref="NotFound">NotFound</see> if a
		/// match is not found</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// <para></para>
		/// This method locates the first matching object, if duplicate objects exist. 
		/// </remarks>
		public int FindIndex (T obj)
		{
			return FindIndex (_activeListIndex, obj);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists.
		/// </summary>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="obj">The object to match</param>
		/// <returns>The offset of the matching object in the managed list, or <see cref="NotFound">NotFound</see> if a
		/// match is not found</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// <para></para>
		/// This method locates the first matching object, if duplicate objects exist.
		/// </remarks>
		public int FindIndex (System.Enum e, T obj)
		{
			return FindIndex (ValidateEnumerator (e), obj);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method locates
		/// the last matching object, if duplicate objects exist. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <param name="obj">The object to match</param>
		/// <returns>The offset of the last matching object in the managed list, or <see cref="NotFound">NotFound</see> if no matching
		/// object is found</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// </remarks>
		public int FindLastIndex (T obj)
		{
			return FindLastIndex (_activeListIndex, obj);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method locates
		/// the last matching object, if duplicate objects exist.
		/// </summary>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="obj">The object to match</param>
		/// <returns>The offset of the last matching object in the managed list, or <see cref="NotFound">NotFound</see> if no matching
		/// object is found</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// </remarks>
		public int FindLastIndex (System.Enum e, T obj)
		{
			return FindLastIndex (ValidateEnumerator (e), obj);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The offset of the matching object in the managed list, or <see cref="NotFound">NotFound</see> if a
		/// match is not found</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.<para></para>
		/// This method locates the first matching object, if duplicate objects exist.
		/// </remarks>
		public int FindIndex<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindIndex<ComparisonType> (_activeListIndex, mlc, ct);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The offset of the matching object in the managed list, or <see cref="NotFound">NotFound</see> if a
		/// match is not found</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.<para></para>
		/// This method locates the first matching object, if duplicate objects exist.
		/// </remarks>
		public int FindIndex<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindIndex<ComparisonType> (ValidateEnumerator (e), mlc, ct);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method locates
		/// the last matching object, if duplicate objects exist. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The offset of the last matching object in the managed list, or <see cref="NotFound">NotFound</see> if no matching
		/// object is found</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.
		/// </remarks>
		public int FindLastIndex<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindLastIndex<ComparisonType> (_activeListIndex, mlc, ct);
		}

		/// <summary>
		/// Locate the offset of a matching object in one of the managed lists. This method locates
		/// the last matching object, if duplicate objects exist.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The offset of the last matching object in the managed list, or <see cref="NotFound">NotFound</see> if no matching
		/// object is found</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.
		/// </remarks>
		public int FindLastIndex<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindLastIndex<ComparisonType> (ValidateEnumerator (e), mlc, ct);
		}

		/// <summary>
		/// Locate a matching object in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The matching object</returns>
		/// Throws <exception cref="MultiListObjectNotFoundException">MultiListObjectNotFoundException</exception> if the search
		/// is unsuccessful.
		/// <remarks>
		/// This method locates the first matching object, if duplicate objects exist.
		/// </remarks>
		public T Find<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return Find<ComparisonType> (_activeListIndex, mlc, ct);
		}

		/// <summary>
		/// Locate a matching object in one of the managed lists.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>The matching object</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		///<p></p>
		/// Throws <exception cref="MultiListObjectNotFoundException">MultiListObjectNotFoundException</exception> if the search
		/// is unsuccessful.
		/// <remarks>
		/// This method locates the first matching object, if duplicate objects exist.
		/// </remarks>
		public T Find<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return Find<ComparisonType> (ValidateEnumerator (e), mlc, ct);
		}

		/// <summary>
		/// Locate a matching object in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <param name="obj">The argument which receives a reference to the matching object, if the object is found</param>
		/// <returns>The method returns true if a matching object is found, and false otherwise. If a matching
		/// object is found, it is returned in the obj argument.</returns>
		/// <remarks>
		/// If duplicate objects exist, the first match is returned.
		/// </remarks>
		public bool TryFind<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct, out T obj)
		{
			return TryFind<ComparisonType> (_activeListIndex, mlc, ct, out obj);
		}

		/// <summary>
		/// Locate a matching object in one of the managed lists.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <param name="obj">The argument which receives a reference to the matching object, if the object is found</param>
		/// <returns>The method returns true if a matching object is found, and false otherwise. If a matching
		/// object is found, it is returned in the obj argument.</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// If duplicate objects exist, the first match is returned.
		/// </remarks>
		public bool TryFind<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct, out T obj)
		{
			return TryFind<ComparisonType> (ValidateEnumerator (e), mlc, ct, out obj);
		}

		/// <summary>
		/// Return an object from a managed list at a given index position
		/// </summary>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="index">offset of the object to retrieve</param>
		/// <returns>The matching object</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <seealso cref="this[int]"/>
		public T GetObject (System.Enum e, int index)
		{
			return GetObject (ValidateEnumerator (e), index);
		}
		#endregion

		#region multiple object access methods
		/// <summary>
		/// Locate the starting and ending offsets of duplicate matching objects in one of the managed lists.
		/// This method uses the currently active list, corresponding to the state of the 
		/// <see cref="ActiveList">ActiveList</see> property. </summary>
		/// <param name="obj">The object to match</param>
		/// <returns>IndexRange object</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// </remarks> 
		public IndexRange FindIndexes (T obj)
		{
			return FindIndexes (_activeListIndex, obj);
		}// 02/04/2008

		/// <summary>
		/// Locate the starting and ending offsets of duplicate matching objects in one of the managed lists.
		/// </summary>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="obj">The object to match</param>
		/// <returns>IndexRange object</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="System.Collections.Generic.IComparer&lt;T&gt;.Compare(T,T)">IComparer&lt;T&gt;.Compare</see> 
		/// method of the corresponding class object that was given as an argument to the constructor.
		/// </remarks> // 02/04/2008
		public IndexRange FindIndexes (System.Enum e, T obj)
		{
			return FindIndexes (ValidateEnumerator (e), obj);
		}// 02/04/2008

		/// <summary>
		/// Locate the starting and ending offsets of duplicate matching objects in one of the managed lists.
		/// This method uses the currently active list, corresponding to the state of the 
		/// <see cref="ActiveList">ActiveList</see> property. </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>IndexRange object</returns>
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.
		/// </remarks>
		public IndexRange FindIndexes<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindIndexes<ComparisonType> (_activeListIndex, mlc, ct);
		}// 02/04/2008

		/// <summary>
		/// Locate the starting and ending offsets of duplicate matching objects in one of the managed lists.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>IndexRange object</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		/// <remarks>
		/// The search employs the 
		/// <see cref="ITypeComparer&lt;ComparisonType&gt;.Compare(T,ComparisonType)">ITypeComparer&lt;ComparisonType&gt;.Compare</see> 
		/// method of the class object given as an argument to the method.
		/// </remarks>
		public IndexRange FindIndexes<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return FindIndexes<ComparisonType> (ValidateEnumerator (e), mlc, ct);
		}// 02/04/2008

		/// <summary>
		/// Locate duplicate matching objects in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>If no matching objects exist, an empty object array is returned. Otherwise, an object array
		/// is returned with references to the matching objects.</returns>
		public T[] FindMultiple<ComparisonType> (ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			return GetObjects (_activeListIndex, FindIndexes (_activeListIndex, mlc, ct));
		}

		/// <summary>
		/// Locate duplicate matching objects in one of the managed lists.
		/// </summary>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="obj">The object to match</param>
		/// <returns>If no matching objects exist, an empty object array is returned. Otherwise, an object array
		/// is returned with references to the matching objects.</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		public T[] FindMultiple (System.Enum e, T obj)
		{
			return GetObjects (ValidateEnumerator (e), FindIndexes (obj));
		}

		/// <summary>
		/// Locate duplicate matching objects in one of the managed lists. This method uses the currently active
		/// list, corresponding to the state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <param name="obj">The object to match</param>
		/// <returns>If no matching objects exist, an empty object array is returned. Otherwise, an object array
		/// is returned with references to the matching objects.</returns>
		public T[] FindMultiple (T obj)
		{
			return GetObjects (_activeListIndex, FindIndexes (obj));
		}

		/// <summary>
		/// Locate duplicate matching objects in one of the managed lists.
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type
		/// of the comparison argument</typeparam>
		/// <param name="e">The enumerator that indicates which managed list to search</param>
		/// <param name="mlc">A class that implements the <see cref="ITypeComparer&lt;ComparisonType&gt;">ITypeComparer&lt;ComparisonType&gt;</see> interface</param>
		/// <param name="ct">The comparison argument to match</param>
		/// <returns>If no matching objects exist, an empty object array is returned. Otherwise, an object array
		/// is returned with references to the matching objects.</returns>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// <code>System.Enum</code> argument is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		public T[] FindMultiple<ComparisonType> (System.Enum e, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			int whichList = ValidateEnumerator (e);
			return GetObjects (whichList, FindIndexes (whichList, mlc, ct));
		}
		#endregion

		#region indexer
		/// <summary>
		/// Return an object from the active list, corresponding to the current
		/// state of the <see cref="ActiveList">ActiveList</see> property.
		/// </summary>
		/// <param name="index">offset of the object to retrieve from the active list</param>
		/// <returns>The matching object</returns>
		/// <seealso cref="GetObject (System.Enum, int)"/>
		public T this[int index]
		{
			get
			{
				return _list[_activeListIndex][index];
			}
		}
		#endregion

		#region remove objects and clear lists
		/// <summary>
		/// Remove an object from each managed list.
		/// </summary>
		/// <param name="obj">The object to match</param>
		public void Remove (T obj)
		{
			int count = _list.Length;
			while (count-- > 0)
			{
				_list[count].Remove (obj);
			}
		}

		/// <summary>
		/// Removes all elements from all lists
		/// </summary>
		public void Clear ()
		{
			for (int i = 0; i < _list.Length; i++)
			{
				_list[i].Clear ();
			}
		}
		#endregion

		#region public properties
		/// <summary>
		/// Gets or sets the total number of elements that each list can hold without resizing.
		/// </summary>
		public int Capacity
		{
			get
			{
				return _list[0].Capacity;
			}
			set
			{
				for (int i = 0; i < _list.Length; i++)
				{
					_list[i].Capacity = value;
				}
			}
		}

		/// <summary>
		/// Gets the number of elements contained in each list
		/// </summary>
		public int Count
		{
			get
			{
				return _list[0].Count;
			}
		}

		/// <summary>
		/// Set the property which indicates which list order will apply to subsequent
		/// enumeration.
		/// </summary>
		/// Throws <exception cref="InvalidEnumeratorException">InvalidEnumeratorException</exception> if the
		/// enumerator assigned to the property is not of the same type given in the constructor, or if the enumerator
		/// is out of range
		public System.Enum ActiveList
		{
			set
			{
				_activeListIndex = ValidateEnumerator (value);
			}
		}
		#endregion

		#region enumeration
		/// <summary>
		/// Get an enumerator for this object
		/// </summary>
		/// <returns>enumerator of object type</returns>
		public IEnumerator<T> GetEnumerator ()
		{
			foreach (T xi in _list[_activeListIndex])
			{
				yield return xi;
			}
		}
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () { return GetEnumerator (); }
		#endregion

		#region interface definition
		/// <summary>
		/// The ITypeComparer interface supports searches on objects of a managed list,
		/// on a publicly accessible property of the object. 
		/// </summary>
		/// <typeparam name="ComparisonType">The generic type argument indicates the data type of the property</typeparam>
		public interface ITypeComparer<ComparisonType>
		{
			/// <summary>
			/// Compare an object property with a comparison data type.
			/// </summary>
			/// <param name="t">object to compare</param>
			/// <param name="ct">data to compare</param>
			/// <returns>less than zero if the target property in t is less than ct, zero if the target
			/// property in t equals ct, and greater than zero if the target property in t is greater
			/// than ct</returns>
			int Compare (T t, ComparisonType ct);
		}
		#endregion

		#region private Binary search methods
		private bool BSearch (List<T> list, IComparer<T> c, T lt, out int position)
		{
			int low = 0, mid, high = list.Count - 1, compare = 0;

			while (low <= high)
			{
				mid = (low + high) / 2;
				compare = c.Compare (list[mid], lt);
				if (compare < 0)
				{
					low = mid + 1;
				}
				else if (compare > 0)
				{
					high = mid - 1;
				}
				else
				{
					position = mid;
					return true;
				}
			}
			position = low;
			return false;
		}

		private bool BSearch<ComparisonType> (List<T> list, ITypeComparer<ComparisonType> mlc, ComparisonType ct, out int position)
		{
			int low = 0, mid, high = list.Count - 1, compare = 0;

			while (low <= high) 
			{
				mid = (low + high) / 2;
				compare = mlc.Compare (list[mid], ct);
				if (compare < 0)
				{
					low = mid + 1;
				}
				else if (compare > 0)
				{
					high = mid - 1;
				}
				else
				{
					position = mid;
					return true;
				}
			}
			position = low;
			return false;
		}

		#endregion

		#region private Find methods

		// find the last index of an object that matches argument object T on the target list
		private int FindLastIndex (int whichList, T obj)
		{
			int index;
			if (true == BSearch (_list[whichList], _comparers[whichList], obj, out index))
			{
				return FindLastOf (_list[whichList], _comparers[whichList], index);
			}
			return NotFound;
		}

		// find the first index of an object that matches argument object T on the target list
		private int FindIndex (int whichList, T obj)
		{
			int index;
			if (true == BSearch (_list[whichList], _comparers[whichList], obj, out index))
			{
				return FindFirstOf (_list[whichList], _comparers[whichList], index);
			}
			return NotFound;
		}

		// find the range of indexes of objects that match argument object T on the target list
		private IndexRange FindIndexes (int whichList, T obj)
		{
			int index;
			if (true == BSearch (_list[whichList], _comparers[whichList], obj, out index))
			{
				return new IndexRange (
					FindFirstOf (_list[whichList], _comparers[whichList], index),
					FindLastOf (_list[whichList], _comparers[whichList], index));
			}
			return new IndexRange (NotFound, NotFound);
		}

		// find the first index of an object that matches argument comparison data type ct on the target list
		private int FindIndex<ComparisonType> (int whichList, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			int index;
			if (true == BSearch<ComparisonType> (_list[whichList], mlc, ct, out index))
			{
				return FindFirstOf (_list[whichList], mlc, ct, index);
			}
			return NotFound;
		}

		// find the range of indexes of objects that match argument comparison data type ct on the target list
		private IndexRange FindIndexes<ComparisonType> (int whichList, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			int index;
			if (true == BSearch<ComparisonType> (_list[whichList], mlc, ct, out index))
			{
				return new IndexRange (
					FindFirstOf (_list[whichList], mlc, ct, index),
					FindLastOf (_list[whichList], mlc, ct, index));
			}
			return new IndexRange (NotFound, NotFound);
		}

		// find the last index of an object that matches argument comparison data type ct on the target list
		private int FindLastIndex<ComparisonType> (int whichList, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			int index;
			if (true == BSearch<ComparisonType> (_list[whichList], mlc, ct, out index))
			{
				return FindLastOf<ComparisonType> (_list[whichList], mlc, ct, index);
			}
			return NotFound;
		}

		// try to find the first object that matches argument comparison data type ct on the target list
		// resulting in a true or false to indicate if the object exists
		private bool TryFind<ComparisonType> (int whichList, ITypeComparer<ComparisonType> mlc, ComparisonType ct, out T obj)
		{
			int index;
			if (true == BSearch<ComparisonType> (_list[whichList], mlc, ct, out index))
			{
				index = FindFirstOf (_list[whichList], mlc, ct, index);
				obj = _list[whichList][index];
				return true;
			}
			obj = default (T);
			return false;
		}

		// find the first object that matches argument comparison data type ct on the target list
		// resulting in an exception if the object does not exist
		private T Find<ComparisonType> (int whichList, ITypeComparer<ComparisonType> mlc, ComparisonType ct)
		{
			T match;
			if (true == TryFind<ComparisonType> (whichList, mlc, ct, out match))
			{
				return match;
			}
			throw new MultiListObjectNotFoundException ();
		}

		// get an array of objects from a given list. The indexes array contains two entries:
		// The first entry contains the index of the first offset, and the second
		// index contains the index of the last offset.
		private T[] GetObjects (int whichList, IndexRange range)
		{
			T[] t;
			if (range.Count > 0)
			{
				t = new T[range.Count];
				int count = 0;
				foreach (int index in range)
				{
					t[count++] = GetObject (whichList, index);
				}
			}
			else
			{
				t = new T[0];
			}
			return t;
		}

		// get a single object in a given list at a given index
		private T GetObject (int whichList, int index)
		{
			return _list[whichList][index];
		}

		// find the first object that matches using an IComparer interface on the target list 
		// and starting at a given index
		private int FindFirstOf (List<T> list, IComparer<T> c, int index)
		{
			while (index - 1 >= 0)
			{
				if (0 == c.Compare (list[index], list[index - 1]))
				{
					--index;
				}
				else
				{
					break;
				}
			}
			return index;
		}

		// find the first object that matches using an ITypeComparer interface on the target list 
		// and starting at a given index
		private int FindFirstOf<ComparisonType> (List<T> list, ITypeComparer<ComparisonType> mlc, ComparisonType ct, int index)
		{
			while (index - 1 >= 0)
			{
				if (0 == mlc.Compare (list[index - 1], ct))
				{
					--index;
				}
				else
				{
					break;
				}
			}
			return index;
		}

		// find the last object that matches using an IComparer interface on the target list 
		// and starting at a given index
		private int FindLastOf (List<T> list, IComparer<T> c, int index)
		{
			while (index + 1 < list.Count)
			{
				if (0 == c.Compare (list[index], list[index + 1]))
				{
					++index;
				}
				else
				{
					break;
				}
			}
			return index;
		}

		// find the last object that matches using an ITypeComparer interface on the target list 
		// and starting at a given index
		private int FindLastOf<ComparisonType> (List<T> list, ITypeComparer<ComparisonType> mlc, ComparisonType ct, int index)
		{
			while (index + 1 < list.Count)
			{
				if (0 == mlc.Compare (list[index + 1], ct))
				{
					++index;
				}
				else
				{
					break;
				}
			}
			return index;
		}
		#endregion

		#region Enumerator validation
		// verify that the given enumerator is of the same type passed to the constructor
		// as the first argument, and that the value of the enumerator falls within the
		// ordinal count of enumerators for that type
		private int ValidateEnumerator (System.Enum e)
		{
			if (e.GetType () != _enumeratorType)
			{
				throw new InvalidEnumeratorException ();
			}
			int i = Convert.ToInt32 (System.Enum.Parse (e.GetType (), e.ToString ()));
			if (i >= _list.Length)
			{
				throw new InvalidEnumeratorException ();
			}
			return i;
		}
		#endregion

	}

	// 02/04/2008
	/// <summary>
	/// The IndexRange class contains the starting and ending index range returned from a call to the four MultiList&lt;T&gt;.FindIndex methods: 
	/// <see cref="MultiList&lt;T&gt;.FindIndexes (T)">(1)</see>, 
	/// <see cref="MultiList&lt;T&gt;.FindIndexes (System.Enum, T)">(2)</see>, 
	/// <see cref="MultiList&lt;T&gt;.FindIndexes&lt;ComparisonType&gt; (MultiList&lt;T&gt;.ITypeComparer&lt;ComparisonType&gt;, ComparisonType)">(3)</see>, and
	/// <see cref="MultiList&lt;T&gt;.FindIndexes&lt;ComparisonType&gt; (System.Enum, MultiList&lt;T&gt;.ITypeComparer&lt;ComparisonType&gt;, ComparisonType)">(4)</see>
	/// The enumerator of this object returns each integer in the range beginning with the <see cref="Start">Start</see> property and ending with 
	/// the <see cref="End">End</see> property, inclusive.
	/// </summary>
	public class IndexRange : IEnumerable<int>
	{
		private int _start;
		private int _end;

		internal IndexRange (int start, int end)
		{
			_start = start;
			_end = end;
		}

		/// <summary>
		/// Return the start value in the range. If there are no values
		/// in the range, <see cref="MultiList&lt;T&gt;.NotFound">MultiList&lt;T&gt;.NotFound</see> is returned.
		/// </summary>
		public int Start
		{
			get { return _start; }
		}

		/// <summary>
		/// Return the end value in the range. If there are no values
		/// in the range, <see cref="MultiList&lt;T&gt;.NotFound">MultiList&lt;T&gt;.NotFound</see> is returned.
		/// </summary>
		public int End
		{
			get { return _end; }
		}

		/// <summary>
		/// Get the count of the number of values in the range. If there are no values
		/// in the range, zero is returned.
		/// </summary>
		public int Count
		{
			get { return (_start == MultiList<int>.NotFound ? 0 : (_end - _start + 1)); }
		}

		#region enumeration
		/// <summary>
		/// Get an enumerator for this object. The enumerator returns each integer in 
		/// the range between the <see cref="Start">Start</see> property and the <see cref="End">End</see> property, inclusive.
		/// </summary>
		/// <returns>IndexRange enumerator</returns>
		public IEnumerator<int> GetEnumerator ()
		{
			for (int index = _start; index <= _end; index++)
			{
				yield return index;
			}
		}
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () { return GetEnumerator (); }
		#endregion
	}
}