Recipe 9.9 Keeping Your ArrayList Sorted

Problem

You will be using the BinarySearch method of the ArrayList to periodically search the ArrayList for specific elements. The addition, modification, and removal of elements will be interleaved with the searches. The BinarySearch method, however, presupposes a sorted array; if the ArrayList is not sorted, the BinarySearch method will possibly return incorrect results. You do not want to have to remember to always call the ArrayList.Sort method before calling the ArrayList.BinarySearch method, not to mention incurring all the overhead associated with this call. You need a way of keeping the ArrayList sorted without always having to call the ArrayList.Sort method.

Solution

The following class enhances the adding and modifying of elements within an ArrayList. These methods keep the array sorted when items are added to it and modified. Note that a DeleteSorted method is not required since this method would not disturb the sorting:

using System;
using System.Collections;

public class SortedArrayList : ArrayList
{
    public void AddSorted(object item)
    {
        int position = this.BinarySearch(item);
        if (position < 0)
        {
            position = ~position;
        }

        this.Insert(position, item);
    }

    public void ModifySorted(object item, int index)
    {
        this.RemoveAt(index);

        int position = this.BinarySearch(item);
        if (position < 0)
        {
            position = ~position;
        }

        this.Insert(position, item);
    }
}

Discussion

Instead of calling ArrayList.Add directly to add elements, use the AddSorted method to add elements while at the same time keeping the ArrayList sorted. The AddSorted method accepts an object (item) to add to source.

Likewise, instead of using the ArrayList indexer directly to modify elements, use the ModifySorted method to modify elements while at the same time keeping the ArrayList sorted. Call this method, passing in the object to replace the existing object (item), and the index of the object to modify (index).

The following code exercises the SortedArrayList class:

class CTest
{
   static void Main( )
   {
        // Create a SortedArrayList and populate it with 
        //    randomly choosen numbers
        SortedArrayList sortedAL = new SortedArrayList( );
        sortedAL.AddSorted(200);
        sortedAL.AddSorted(20);
        sortedAL.AddSorted(2);
        sortedAL.AddSorted(7);
        sortedAL.AddSorted(10);
        sortedAL.AddSorted(0);
        sortedAL.AddSorted(100);
        sortedAL.AddSorted(-20);
        sortedAL.AddSorted(56);
        sortedAL.AddSorted(55);
        sortedAL.AddSorted(57);
        sortedAL.AddSorted(200);
        sortedAL.AddSorted(-2);
        sortedAL.AddSorted(-20);
        sortedAL.AddSorted(55);
        sortedAL.AddSorted(55);

        // Display it
        foreach (int i in sortedAL)
        {
            Console.WriteLine(i);
        }

        // Now modify a value at a particular index
        sortedAL.ModifySorted(0, 5);
        sortedAL.ModifySorted(1, 10);
        sortedAL.ModifySorted(2, 11);
        sortedAL.ModifySorted(3, 7);
        sortedAL.ModifySorted(4, 2);
        sortedAL.ModifySorted(2, 4);
        sortedAL.ModifySorted(15, 0);
        sortedAL.ModifySorted(0, 15);
        sortedAL.ModifySorted(223, 15);

        // Display it
        Console.WriteLine( );
        foreach (int i in sortedAL)
        {
            Console.WriteLine(i);
        }
    }
}

This method automatically places the new item in the ArrayList while keeping its sort order; this is done without having to explicitly call ArrayList.Sort. The reason this works is because the AddSorted method first calls the BinarySearch method and passes it to the object to be added to the ArrayList. The BinarySearch method will either return the index where it found an identical item or a negative number that we can use to determine where the item that we are looking for should be located. If the BinarySearch method returns a positive number, we can use the ArrayList.Insert method to insert our new element at that location, keeping the sort order within the ArrayList. If the BinarySearch method returns a negative number, we can use the bitwise complement operator ~ to determine where the item should have been located, had it existed in the sorted list. Using this number, we can use the ArrayList.Insert method to add the item to the correct location in source while keeping the correct sort order.

You can remove an element from source without disturbing the sort order, but modifying an element's value in the ArrayList most likely will cause source to become unsorted. The ModifySorted method alleviates this problem. This method works similarly to the AddSorted method, except that it will initially remove the element from the ArrayList and then insert the new element into the correct location.

See Also

See the "ArrayList Class" topic in the MSDN documentation.