Recipe 9.7 Retrieving All Instances of a Specific Itemin an ArrayList

Problem

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.

Solution

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

Discussion

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

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