C# Cookbook

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 ...