Recipe 9.6 Determining the Number of Times an Item Appears in an ArrayList

Problem

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.

Solution

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

Discussion

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("\r\n--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 Also

See Recipe 9.7; see the "ArrayList Class" topic in the MSDN documentation.