//
// 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<T>">IComparer<T></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<T>">ITypeComparer<T></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<T>">IComparer<T></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<T>.Compare(T,T)">IComparer<T>.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<T>.Compare(T,T)">IComparer<T>.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<T>.Compare(T,T)">IComparer<T>.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<T>.Compare(T,T)">IComparer<T>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>">ITypeComparer<ComparisonType></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<T>.Compare(T,T)">IComparer<T>.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<T>.Compare(T,T)">IComparer<T>.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<ComparisonType>">ITypeComparer<ComparisonType></see> interface</param>
/// <param name="ct">The comparison argument to match</param>
/// <returns>IndexRange object</returns>
/// <remarks>
/// The search employs the
/// <see cref="ITypeComparer<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>.Compare(T,ComparisonType)">ITypeComparer<ComparisonType>.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<ComparisonType>">ITypeComparer<ComparisonType></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<ComparisonType>">ITypeComparer<ComparisonType></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<T>.FindIndex methods:
/// <see cref="MultiList<T>.FindIndexes (T)">(1)</see>,
/// <see cref="MultiList<T>.FindIndexes (System.Enum, T)">(2)</see>,
/// <see cref="MultiList<T>.FindIndexes<ComparisonType> (MultiList<T>.ITypeComparer<ComparisonType>, ComparisonType)">(3)</see>, and
/// <see cref="MultiList<T>.FindIndexes<ComparisonType> (System.Enum, MultiList<T>.ITypeComparer<ComparisonType>, 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<T>.NotFound">MultiList<T>.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<T>.NotFound">MultiList<T>.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
}
}