Automatic sorted list

• Download source & test files - 5.33 Kb

Introduction

Basically, I wanted a dynamic array in which all elements would always stay sorted no matter one would do and especially when a new element is added. Then, given the fact that the list knows if it is in the sorted state, it is able to perform operations more efficiently. For instance, looking for an element can be optimized by using a transparent binary search.

Such a collection also must be accessible by index like any other list, and it has to provide the same services as the ArrayList class.

Of course, the .NET framework offers the SortedList class in the System.Collections component. Nevertheless this one did not satisfy me. Indeed, it is a collection of key-and-value pairs that are sorted by the keys. Hence, it internally maintains two arrays: one for the values and one for the keys. So this turns out to be a bit heavy and not so convenient to use for common requirements. After all, in most cases you want the elements to be sorted using either their own IComparable implementation or a specified IComparer. That makes sense.

• bool IsSorted {get}--> Says whether the list is sorted or not.
• bool KeepSorted {get/set}--> If true, next elements to add, will be placed so as to keep the list sorted. If false, they will simply be appended and the list will behave just like an unsorted array. You cannot set this property to true if the list is not sorted, otherwise an exception is thrown. Note that KeepSorted==true implies IsSorted==true.
• bool AddDuplicates {get/set}--> Accept or reject duplicate elements. If false, an object will not be added when its value is already in the list.

Using the code

By default KeepSorted is set to true and the list will remain permanently ordered depending on:

• either an IComparer interface if one has been provided with the appropriate constructor.
• or the IComparable implementation of the contained objects (by default).

If you decide to set KeepSorted to false and make some disordering operations in this mode, then the list will not become sorted again unless you apply the method: void Sort().

By default AddDuplicates is set to true. But when it is false, the list guarantees that an object will not actually be added as long as its value is already in the list. Naturally, equality is recognized according to the Object.Equals(object O) method. In addition, two functions are provided in order to retrieve all duplicates from the list, or even to keep a precise number of elements consisting of a specified value. These are:

• public void LimitNbOccurrences(object Value, int NbValuesToKeep) --> Limits the number of occurrences of a specified value.
• public void RemoveDuplicates() --> Scans the list in order to keep only one representative object for each value. Multiples are suppressed.

Note that SortableList overrides Object.ToString() so as to display itself as a string. To do that, the same function is called on each element of the list.

Example with string type objects:

public class TestSortableList
{
    public static void Main()
    {
        Console.WriteLine("You create a new SortableList." );
        SortableList SL = new SortableList();

        Console.Write(@"You set KeepSorted property 
           to false add the strings X, B, A and D: " );
        SL.KeepSorted = false;
        SL.Add("X");
        SL.Add("B");
        SL.Add("A");
        SL.Add("D");
        Console.WriteLine(SL);

        Console.Write(@"You can insert or set elements where you want 
           since KeepSorted==false.\nLet's set 'C' instead of 'D': ");
        SL[3] = "C";
        Console.WriteLine(SL);

        Console.Write("You decide to sort the list: ");
        SL.Sort();
        Console.WriteLine(SL);

        Console.Write(@"You now set the KeepSorted property to true 
           and add some new strings:\n");
        SL.KeepSorted = true;
        SL.Add("J");
        SL.Add("E");
        SL.Add("E");
        SL.Add("B");
        SL.Add("X");
        SL.Add("E");
        SL.Add("E");
        Console.WriteLine(SL);

        Console.WriteLine("'E' is found at index " + 
                             SL.IndexOf("E").ToString());
        Console.WriteLine("Does the list contain 'X' ?: " + 
                             SL.Contains("X").ToString());
        Console.WriteLine("Does the list contain 'M' ?: " + 
                             SL.Contains("M").ToString());

        Console.Write("You limit the number 
                           of occurrences of 'E' to 2: ");
        SL.LimitNbOccurrences("E", 2);
        Console.WriteLine(SL);

        Console.Write("After all you do not 
                                  want any duplicates: ");
        SL.RemoveDuplicates();
        Console.WriteLine(SL);

        Console.Write(@"You set AddDuplicates to false 
                         and try to add J and E again.\n
                         They are not actually added: ");
        SL.AddDuplicates = false;
        SL.Add("J");
        SL.Add("E");
        Console.WriteLine(SL);

        Console.Write(@"Now you create another SortableList 
                        but this time you give 
                        it an IComparer \nclass which is 
                        the anti-alphabetical order.");
        SL = new SortableList( new AntiAlphabeticalComparer() );

        Console.Write(@"You fill the list by adding a 
                        range of vowels in alphabetical order. 
                        But the resulting list is: " );
        string[] Vowels = new string[] {"A", "E", "I", "O", "U"};
        SL.AddRange( Vowels );
        Console.WriteLine(SL);
        Console.ReadLine();
    }
    
    class AntiAlphabeticalComparer: IComparer
    {
        public int Compare(object O1, object O2)
        {
            string S1 = O1.ToString();
            string S2 = O2.ToString();
            return -String.Compare(S1, S2);
        }
    }
}

Output:

You create a new SortableList.
You set the KeepSorted property to false and 
       add the strings X, B, A, D: {X; B; A; D}
You can insert or set elements where you want since KeepSorted==false.
Let's set 'C' to index 4: {X; B; A; C}
You decide to sort the list: {A; B; C; X}
You now set the KeepSorted property to true and add some new strings:
{A; B; B; C; E; E; E; E; J; X; X}
'E' is found at index 4
Does the list contain 'X' ?: True
Does the list contain 'M' ?: False
You limit the number of occurrences of 'E' to 2: {A; B; B; C; E; E; J; X; X}
After all you do not want any duplicates: {A; B; C; E; J; X}
You set the AddDuplicates property to false and try to add J and E again.
They are not actually added: {A; B; C; E; J; X}
Now you create another SortableList but this time you give it an IComparer
class which is the anti-alphabetical order.
You fill the list by adding a range of vowels in alphabetic order.
But the resulting list is: {U; O; I; E; A}

Points of interest

First, when designing the class I was faced with a conflict of love and obligation. Indeed, here is the alternative:

1. Make the SortableList derived from the ArrayList. On one hand, the advantage is that many methods are already defined in ArrayList and you do not have to re-write them. But on the other hand, some other methods of the base class are not appropriate for a sorted list. Therefore they must be privately overridden to prevent the user from employing them. It is not really easy to control the way the user will actuate the list. For example, what if he casts a SortableList instance in ArrayList? Then the list will not be able to know if it is sorted.
2. Make the SortableList incorporating the ArrayList as a class member. This is the choice I have made over time. The advantage is that you can control all the actions the user does on the list, since it is exactly the one you implement. The only vexatious matter is that you have to define many methods that are simply calling the same ones on the ArrayList member. Never mind.

Then, SortableList should implement all the methods needed for the following interfaces : IList (consequently ICollection and IEnumerable) and ICloneable. Regarding new and specific functions, I advise you to have a look at the source code. You will see that for performance reasons, RemoveDuplicates - unlike IndexOf among other methods - proceeds differently when the list is sorted and when it is not. And here the logic lays down that IComparer.Compare(Obj1,Obj2)==0 (or IComparable.CompareTo(Obj2)==0) must be equivalent to Obj1.Equals(Obj2):

public int IndexOf(object O)
{
    int Result = -1;
    if ( _IsSorted )
    {
        Result = _ArrayList.BinarySearch(O, _Comparer);
        while ( Result>0 && _ArrayList[Result-1].Equals(O) )
          Result--; // Move backward to point at the FIRST occurence

    }
    else Result = _ArrayList.IndexOf(O);
    return Result;
}

Finally I had to control the forbidden actions. Typically you cannot do the things listed below. And all of them trigger an InvalidOperationException or an ArgumentException:

• Set the KeepSorted property to true whereas IsSorted equals false.
• Use one of the Insert methods or the set operation ([]=). When KeepSorted equals true, only the Add method is allowed to place a new element into the list.
• The list has not been provided with an IComparer interface at construction plus the user adds (Add, Insert, []=,...) an object which does not implement IComparable.

History

• 18th April 2003 - Initial version. Merci beaucoup � Lauren K.
• 22nd April 2003 - New functions added:
  • public int IndexOfMin();
  • public int IndexOfMax();
  • public int IndexOf(object O, EqualityDelegate AreEqual);