Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

MultiList: .NET Generic List with Multiple Sort Orders

, 1 Feb 2008
The MultiList class extends the functionality of the generic list. The MultiList class manages multiple sort orders on lists. It is best suited to object lists where searching is required on more than one criteria.
multilist.zip
AsAbove
Collections
MultiList
MultiList
bin
Release
AsAbove.Collections.MultiList.dll
Documentation
Help
MultiList.chm
Properties
Source
AsAbove
Collections
Test
bin
Release
AsAbove.Collections.MultiList.dll
Test.dll
Properties
// 
// 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
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

gogglin

United States United States
No Biography provided

| Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 2 Feb 2008
Article Copyright 2008 by gogglin
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid