You need the number of occurrences of one
type of object contained in an ArrayList
. The
ArrayList
contains methods, such as
Contains
and
BinarySearch
to
find a single item. Unfortunately, these methods cannot find all
duplicated items at one time—essentially, there is no
count all functionality. If you want to find
multiple items, you need to implement your own routine.
The following class inherits from the ArrayList
class in order to extend its functionality. Two methods are added to
return the number of times a particular object appears in a sorted
and an unsorted
ArrayList
:
using System; using System.Collections; public class ArrayListEx : ArrayList { // Count the number of times an item appears in this // unsorted or sorted ArrayList public int CountAll(object searchValue) { int foundCounter = 0; for (int index = 0; index < this.Count; index++) { if (this[index].Equals(searchValue)) { foundCounter++; } } return (foundCounter); } // Count the number of times an item appears in this sorted ArrayList public int BinarySearchCountAll(object searchValue) { // Sort ArrayList this.Sort( ); bool done = false; int count = 0; // Search for first item int center = this.BinarySearch(searchValue); int left = center - 1; int right = center + 1; int position = -1; if (center >= 0) { // Increment counter for found item ++count; // 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 { // Increment counter for found item ++count; } } --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 { // Increment counter for found item ++count; } } ++right; }while (!done); } return (count); } }
The CountAll
method accepts a search value
(searchValue
) of type object. This method then
proceeds to count the number of times the search value appears in the
ArrayListEx
class. This method may be used when
the ArrayListEx
is sorted or unsorted. If the
ArrayListEx
is sorted (an
ArrayListEx
is sorted by calling the
Sort
method), the
BinarySearchCountAll
method can be used to
increase the efficiency of the searching. This is done by making use
of the BinarySearch
method on the
ArrayListEx
class, which is much faster than
iterating through the entire ArrayListEx
. This is
especially true as the ArrayListEx
grows in size.
The following code exercises these two new methods of the
ArrayListEx
class:
class CTest { static void Main( ) { ArrayListEx arrayExt = new ArrayListEx( ); arrayExt.Add(-2); arrayExt.Add(-2); 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("--CONTAINS TOTAL--"); int count = arrayExt.CountAll(2); Console.WriteLine("Count2: " + count); count = arrayExt.CountAll(3); Console.WriteLine("Count3: " + count); count = arrayExt.CountAll(1); Console.WriteLine("Count1: " + count); Console.WriteLine(" --BINARY SEARCH COUNT ALL--"); count = arrayExt.BinarySearchCountAll(2); Console.WriteLine("Count2: " + count); count = arrayExt.BinarySearchCountAll(3); Console.WriteLine("Count3: " + count); count = arrayExt.BinarySearchCountAll(1); Console.WriteLine("Count1: " + count); } }
This code outputs the following:
--CONTAINS TOTAL-- Count2: 4 Count3: 1 Count1: 1 --BINARY SEARCH COUNT ALL-- Count2: 4 Count3: 1 Count1: 1
The CountAll
method uses a sequential search that
is performed in a for
loop. A linear search must
be used since the ArrayList
is not sorted. The
if
statement determines whether each element in
the ArrayList
is equal to the search criteria
(searchValue
). If the element is found to be a
match, the counter (foundCounter
) is incremented
by one. This counter is returned by this method to indicate the
number of items matching the search criteria in the
ArrayList
.
The BinarySearchCountAll
method is somewhat more
complex. This method implements a binary search to locate the first
item matching the search criteria (searchValue
) in
the ArrayList
. If one is found, the
count
variable is incremented by one and the
algorithm proceeds to search to the left and right of the first found
element. This first found item is used as a pivot point to locate all
other matching items that exist around it. First, it searches to the
left of the initially found item. Once it encounters the start of the
ArrayList
or an item that does not match
searchValue
, the searching to the left stops and
searching to the right of the initially found item starts. Searching
to the right continues until the end of the
ArrayList
is reached or an item is found that does
not match searchValue
. Every time an element is
found to the right or left of the initially found item, the
count
variable is incremented by one; the value of
this variable is then returned to the caller.
Recipe 9.7 contains a variation of this recipe that returns the actual items found, rather than a count.
See Recipe 9.7; see the “ArrayList Class” topic in the MSDN documentation.