You need to retrieve every object that
matches a search criteria contained in an
ArrayList
. The ArrayList
contains the
BinarySearch
method to find a single item—essentially, there is no
find all functionality. If you want to find all
items duplicated in an ArrayList
, you must write
your own routine.
The following class inherits from the ArrayList
class in order to extend its functionality. Two methods are added to
return an array of all the matching objects found in this sorted or
unsorted ArrayList
:
using System; using System.Collections; public class ArrayListEx : ArrayList { // The method to retrieve all matching objects in a // sorted or unsorted ArrayListEx public object[] GetAll(object searchValue) { ArrayList foundItem = new ArrayList( ); for (int index = 0; index < this.Count; index++) { if (this[index].Equals(searchValue)) { foundItem.Add(this[index]); } } return (foundItem.ToArray( )); } // The method to retrieve all matching objects in a sorted ArrayListEx public object[] BinarySearchAll(object searchValue) { // Sort ArrayList this.Sort( ); bool done = false; ArrayList RetObjs = new ArrayList( ); // Search for first item int center = this.BinarySearch(searchValue); int left = center - 1; int right = center + 1; int position = -1; if (center >= 0) { // Add first found RetObjs.Add(this[center]); // Search to the left do { if (left < 0) { done = true; } else { if (this[left].Equals(searchValue)) { position = left; } else { position = -1; } if (position < 0) { done = true; } else { // Add next found to left RetObjs.Add(this[left]); } } --left; }while (!done); // Reset done flag done = false; // Search to the right do { if (right >= (this.Count)) { done = true; } else { if (this[right].Equals(searchValue)) { position = right; } else { position = -1; } if (position < 0) { done = true; } else { // Add next found to right RetObjs.Add(this[right]); } } ++right; }while (!done); } return (RetObjs.ToArray( )); } }
These methods are very similar to the methods used in the previous
recipe. The main difference is that these methods return the actual
items found in an object
array instead of a count
of the number of times an item was found. The main thing to keep in
mind when choosing a method to use is whether you are going to be
searching an ArrayList
that is sorted. Choose the
GetAll
method to obtain an array of all found
items from an unsorted ArrayList
, and choose the
BinarySearchAll
method to get all items in a
sorted ArrayList
.
The following code exercises these two new methods of the
ArrayListEx
class:
class CTest { static void Main( ) { ArrayListEx arrayExt = new ArrayListEx( ); arrayExt.Add(-1); arrayExt.Add(-1); arrayExt.Add(1); arrayExt.Add(2); arrayExt.Add(2); arrayExt.Add(2); arrayExt.Add(2); arrayExt.Add(3); arrayExt.Add(100); arrayExt.Add(4); arrayExt.Add(5); Console.WriteLine("--GET All--"); object[] objects = arrayExt.GetAll(2); foreach (object o in objects) { Console.WriteLine("obj2: " + o); } Console.WriteLine( ); objects = arrayExt.GetAll(-2); foreach (object o in objects) { Console.WriteLine("obj-2: " + o); } Console.WriteLine( ); objects = arrayExt.GetAll(5); foreach (object o in objects) { Console.WriteLine("obj5: " + o); } Console.WriteLine(" --BINARY SEARCH GET ALL--"); objects = arrayExt.BinarySearchAll(-2); foreach (object o in objects) { Console.WriteLine("obj-2: " + o); } Console.WriteLine( ); objects = arrayExt.BinarySearchAll(2); foreach (object o in objects) { Console.WriteLine("obj2: " + o); } Console.WriteLine( ); objects = arrayExt.BinarySearchAll(5); foreach (object o in objects) { Console.WriteLine("obj5: " + o); } } }
This code outputs the following:
--GET All-- obj2: 2 obj2: 2 obj2: 2 obj2: 2 obj5: 5 --BINARY SEARCH GET ALL-- obj2: 2 obj2: 2 obj2: 2 obj2: 2 obj5: 5
The BinarySearchAll
method is faster than the
GetAll
method, especially if the array has already
been sorted. In the BinarySearchAll
method, we
have added a call to the Sort
method for the
current ArrayListEx
object; this is done to make
absolutely sure that the ArrayListEx
has been
sorted. You can remove this call if you are absolutely sure that the
ArrayListEx
will be sorted. If a
BinarySearch
is
used on an unsorted ArrayList
, it is highly likely
that the results returned by the search will be incorrect.
See Recipe 9.6; see the “ArrayList Class” topic in the MSDN documentation.