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.
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); } }
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.