Keeping Your List&ltT&gt Sorted






Keeping Your List<T> Sorted

Problem

You will be using the BinarySearch method of the List<T> to periodically search the List<T> 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 List<T> is not sorted, the BinarySearch method will possibly return incorrect results. You do not want to have to remember to always call the List<T>.Sort method before calling the List<T>.BinarySearch method, not to mention incurring all the overhead associated with this call. You need a way of keeping the List<T> sorted without always having to call the List<T>.Sort method.

Solution

The following SortedList generic class enhances the adding and modifying of elements within a List<T>. These methods keep the array sorted when items are added to it and modified. Note that a DeleteSorted method is not required since deleting an item does not disturb the sorted order of the remaining items:

	using System;
	using System.Collections;
	using System.Collections.Generic;

	public class SortedList<T> : List<T>
	{
	    public void AddSorted(T item)
	    {
	        int position = this.BinarySearch(item);
	        if (position < 0)
	        {
	            // This bit of code will be described in detail later.
	            position = ~position;
	        }

	        this.Insert(position, item);
	    }

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

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

	        this.Insert(position, item);
	    }
	}

Discussion

Instead of calling List<T>.Add directly to add elements, use the AddSorted method to add elements while at the same time keeping the List<T> sorted. The AddSorted method accepts a generic type (T) to add to the sorted list.

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

The following code exercises the SortedList<T> class:

	class CTest
	{
	    static void Main( )
	    {
	        // Create a SortedList and populate it with
	        // randomly chosen numbers.
	        SortedList<int> sortedAL = new SortedList<int>( );
	        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 List<T> while keeping its sort order; this is done without having to explicitly call List<T>.Sort. The reason this works is because the AddSorted method first calls the BinarySearch method and passes it 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 you can use to determine where the item that you are looking for should be located. If the BinarySearch method returns a positive number, you can use the List<T>. Insert method to insert the new element at that location, keeping the sort order within the List<T>. If the BinarySearch method returns a negative number, you 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, you can use the List<T>.Insert method to add the item to the correct location in the sorted list while keeping the correct sort order.

You can remove an element from the sorted list without disturbing the sort order, but modifying an element's value in the List<T> most likely will cause the sorted list 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 List<T> and then insert the new element into the correct location.

See Also

See the "List<T> Class" topic in the MSDN documentation.



 Python   SQL   Java   php   Perl 
 game development   web development   internet   *nix   graphics   hardware 
 telecommunications   C++ 
 Flash   Active Directory   Windows