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 ...
Get C# Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.