<html>
<head>
<title>MultiList Code Examples</title>
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type=text/css href="http://www.codeproject.com/styles/global.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<h2>Introduction</h2>
<p>
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.
<P>
This code sample demonstrates the declaration of a Person class, and the instantiation
of a MultiList class to manage lists by three sort orders on the Person class. This
documentation does not extensively demonstrate how to perform searches, additions, or deletions to the
MultiList object; the reader should refer to the unit test code for this project for
those examples.
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 <code>Remove</code> method before the modification, then reinsert it with the <code>Add</code> method after the modification</li>
<li>The class employs a binary search algorithm for efficiency, both for sorting and inserting objects into lists</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 <code>foreach</code></li>
<li>The <code>ActiveList</code> property can be set before enumeration, to indicate which sort order to apply to subsequent enumerations</li>
<li>A single call to the <code>Add</code> method adds an object to all mangaged lists</li>
<li>A single call to the <code>Remove</code> method removes an object from all mangaged lists</li>
</ul>
<h2>Background</h2>
The idea for this library came about as I was working on an unrelated project that manages a list on
two different sort orders. Initially I used a list that was sorted on the most important sort order, and a clumsy property
and filter which allowed iteration on the second sort order. I knew it was a total <a href="http://en.wikipedia.org/wiki/Kludge">kludge</a>, but it worked.
Before beginning this library, I searched for this type of functionality in publicly available code, with no luck. It seems like
a fairly common problem, easily encounted in routine scenarios:
<ul>
<li>I have an ordered list of customer names, and I would also like it sorted on city and state</li>
<li>I have an ordered list of files names, and I also want to sort in on extension, size, and date</li>
</ul>
The <a href="http://msdn2.microsoft.com/en-us/6sh2ey19.aspx">List<T></a> class in the System.Collections.Generic namespace provides all of the functionality to search and sort lists, but it comes up short in some ways:
<ul>
<li>Although it offers the ability to sort, and to insert at a specified position, there is no mechanism to insert in sorted order
without explicitly giving the index.</li>
<li>The <a href="http://msdn2.microsoft.com/en-us/3f90y839.aspx">BinarySearch</a> method returns the first match found when duplicates are present, but not necessarily the first in a series of duplicates.</li>
<li>Although a list may be in sorted order, the methods
<a href="http://msdn2.microsoft.com/en-us/x0b5b5bc.aspx">Find</a>, <a href="http://msdn2.microsoft.com/en-us/0k601hd9.aspx">FindIndex</a>, <a href="http://msdn2.microsoft.com/en-us/5kthb929.aspx">FindLast</a>, and <a href="http://msdn2.microsoft.com/en-us/0zxbszh4.aspx">FindLastIndex</a> perform linear searches to locate a match. On a sorted list,
a binary search would be faster, followed by a linear search to the last duplicate for the FindLast and FindLastIndex methods.
</ul>
The MultiList library addresses all these issues.
<h2>Using the code</h2>
This code example demonstrates the declaration of a Person class, and the instantiation
of a MultiList class to manage lists by three sort orders on the Person class. This
documentation does not extensively demonstrate how to perform searches, additions, or deletions to the
MultiList object; the reader should refer to the unit test code for this project for
those examples.
<p>
The Person class is defined as follows:
<pre>
public class Person : System.IEquatable<Person>
{
public enum Profession
{
Teacher,
Nurse,
Barber,
Welder,
Carpenter,
Lawyer
};
private string _name;
private int _age;
private Profession _career;
private static int _static_sequence = 0;
private int _sequence;
public Person (string name, int age, Profession career)
{
_name = name;
_age = age;
_career = career;
lock (typeof (Person))
{
_sequence = ++_static_sequence;
}
}
public string Name { get { return _name; } }
public int Age { get { return _age; } }
public Profession Career { get { return _career; } }
public int Sequence { get { return _sequence; } }
public bool Equals (Person p)
{
return Sequence == p.Sequence;
}
}
</pre>
Note the following points about the Person class:
<ul>
<li>The class implements the <a href="http://msdn2.microsoft.com/en-us/ms131187.aspx">IEquatable<T></a> interface. The purpose of this is to define a standard of equality for the class, without relying on the
<a href="http://msdn2.microsoft.com/en-us/system.object.gethashcode.aspx">GetHashCode</a> method,
which is the default measure of equality. This is important because you may not want to give a direct reference to your object
to a client; you may want to give the client a cloned copy, which would have a different hash code. </li>
<li>The class employs a static sequence member and a sequence member at the object level to generate a unique ID. This ID
is used to determine equality.</li>
</ul>
The next step is to define an enumerator and three custom classes which are to be used as arguments to the MultiList constructor.
<p>
<pre>
// declare the enumerator which defines the sort orders that we want on the Person class
private enum PersonSortCriteria
{
Name,
Age,
Career
};
public class NameComparer : MultiList<<code>Person</code>>.ITypeComparer<<code>string</code>>, IComparer<<code>Person</code>>
{
public int Compare (Person p1, Person p2)
{
return p1.Name.CompareTo (p2.Name);
}
public int Compare (Person p, string name)
{
return p.Name.CompareTo (name);
}
}
public class AgeComparer : MultiList<<code>Person</code>>.ITypeComparer<<code>int</code>>, IComparer<<code>Person</code>>
{
public int Compare (Person p1, Person p2)
{
return p1.Age - p2.Age;
}
public int Compare (Person p, int age)
{
return p.Age - age;
}
}
public class CareerComparer : MultiList<<code>Person</code>>.ITypeComparer<<code>Person.Profession</code>>, IComparer<<code>Person</code>>
{
public int Compare (Person p1, Person p2)
{
return p1.Career.CompareTo (p2.Career);
}
public int Compare (Person p, Person.Profession career)
{
return p.Career.CompareTo (career);
}
}
</pre>
<p>
The last step is to instantiate the three comparer objects and the MultiList class object. Note that the
comparer object argument order matches the order of the PersonSortCriteria enumerator constants in the
constructor.
<pre>
NameComparer nameComparer = new NameComparer ();
AgeComparer ageComparer = new AgeComparer ();
CareerComparer careerComparer = new CareerComparer ();
MultiList<<code>Person</code>> ml = new MultiList<<code>Person</code>> (typeof (PersonSortCriteria), nameComparer, ageComparer, careerComparer);
</pre>
<p>
After this, adding objects to the list is straightforward.
<pre>
// add four Person objects to the MultiList
Person Jim = new Person ("Jim", 42, Person.Profession.Teacher);
ml.Add (Jim);
ml.Add (new Person ("Susan", 29, Person.Profession.Lawyer));
ml.Add (new Person ("Arthur", 22, Person.Profession.Barber));
ml.Add (new Person ("Ellen", 29, Person.Profession.Teacher));
</pre>
A list can be searched for an index or for the actual object. It might be preferable to
search for an index if you're not sure if a match will be found. If a match is not
found, index searches return <code>MultiList.NotFound</code>. When a match is found,
an index is returned that corresponds to the sort order of the search.
<p>
The following examples demonstrate the use of the index methods.<p>
<B>Searching for list indexes</B><p>
There are two types of searches that can be done on a MultiList object. The first
type searches for an object with an existing Person object.
<pre>
// return the index of Jim in the name sort list
int index = ml.FindIndex (PersonSortCriteria.Name, Jim);
// return the index of Jim in the age sort list
index = ml.FindIndex (PersonSortCriteria.Age, Jim);
</pre>
<p>
The second type of search uses a data type that corresponds to a particular sort order.
<pre>
// return the index of Susan in the name sort list
int index = ml.FindIndex<<code>string</code>> (PersonSortCriteria.Name, nameComparer, "Susan");
// return the index of the first Person with an age of 29
index = ml.FindIndex<<code>int</code>> (PersonSortCriteria.Age, ageComparer, 29);
// return the index of the first Person with a career of Barber
index = ml.FindIndex<<code>Person.Profession</code>> (PersonSortCriteria.Career, careerComparer, Person.Profession.Barber);
</pre>
<p>
The <code>ActiveList</code> property may be used to specify a particular sort order, which will apply to
all subsequent methods which do not specify a sort order.
<pre>
ml.ActiveList = PersonSortCriteria.Age;
// return the index of the first Person with an age of 29
int index = ml.FindIndex<<code>int</code>> (ageComparer, 29);
</pre>
<p>
When an index is obtained, the object can be accessed in a couple of ways. In
the previous code example, the <code>ActiveList</code> property was set to <code>PersonSortCriteria.Age</code>. If the Item indexer is used, it will
return objects from the Age list.
<pre>
// note that we first check to see that a valid index was returned,
// before accessing the list element.
if (index != MultiList.NotFound)
{
Person match = ml[index];
}
</pre>
<p>
You may also access any of the lists using the <code>GetObject</code> method.
<pre>
int index = ml.FindIndex<<code>string</code>> (PersonSortCriteria.Name, nameComparer, "Susan");
if (index != MultiList.NotFound)
{
Person match = ml.GetObject (PersonSortCriteria.Name, index);
}
</pre>
<B>Searching for actual objects</B>
<p>
The <code>Find</code> methods return a reference to the object stored in the list.
When you use one of the <code>Find</code> methods that return an actual object, you will have to do so
in a try/catch block, or else use the <code>TryFind</code> methods.
<pre>
Person match;
try
{
match = ml.Find<<code>string</code>> (PersonSortCriteria.Name, nameComparer, "Susan");
}
catch (MultiListObjectNotFoundException)
{
// not found
}
// set the active list to age, and use the TryFind method to search
ml.ActiveList = PersonSortCriteria.Age;
if (true == TryFind<<code>string</code>> (ageComparer, 29, <code>out</code> match))
{
// a match was found
}
</pre>
<B>Searching for multiple objects</B>
<p>
Several methods are available that return multiple objects or indexes when duplicates exist.
<pre>
<code>IndexRange</code> range = ml.FindIndexes<<code>int</code>> (PersonSortCriteria.Age, ageComparer, 29);
if (range.Count > 0)
{
// one or more matches was found
foreach (int index in range)
{
// iterate indexes
}
}
Person[] matches = ml.FindMultiple<<code>int</code>> (PersonSortCriteria.Age, ageComparer, 29);
if (matches.Length > 0)
{
// one or more matches was found
}
</pre>
<h2>Points of Interest</h2>
The unit test code for this project requires NUnit 2.4.3.
<h2>History</h2>
<p>Initial release - January 20, 2008
<p>Enhanced - February 5, 2008: Added IndexRange object and iteration. This object simplifies
the handling of multiple indexes returned from Find methods.
</body>
</html>
Submit an article or tip