Recipe5.7.Retrieving All Instances of a Specific Item in a ListT

Recipe 5.7. Retrieving All Instances of a Specific Item in a List<T>

Problem

You need to retrieve every object contained in a List<T> that matches a search criterion. The List<T> contains the BinarySearch method to find a single itemessentially, there is no find all functionality. If you want to find all items duplicated in a List<T>, you must write your own routine.

Solution

Use the ListEx<T> class shown in Example 5-3, which inherits from the List<T> class in order to extend its functionality. Two methodsGetAll and BinarySearchGetAllare added to return an array of all the matching objects found in this sorted or unsorted List<T>.

Example 5-3. Retrieving all instances of a specific item in a List<T>

 using System; using System.Collections; using System.Collections.Generic; public class ListEx<T> : List<T> {     // The method to retrieve all matching objects in a     // sorted or unsorted ListEx<T>     public T[] GetAll(T searchValue)     {         List<T> foundItem = new List<T>( );         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 ListEx<T>     public T[] BinarySearchGetAll(T searchValue)     {         bool done = false;         List<T> RetObjs = new List<T>();         // Search for first item.         int center = this.BinarySearch(searchValue);         if (center > 0)         {             RetObjs.Add(this[center]);             int left = center;             while (left > 0 && this[left - 1].Equals(searchValue))             {                 left -= 1;                 RetObjs.Add(this[left]);             }             int right = center;             while (right < (this.Count - 1) &&                 this[right + 1].Equals(searchValue))             {                 right += 1;                 RetObjs.Add(this[right]);             }         }         return (RetObjs.ToArray());     } }

Discussion

The GetAll and BinarySearchGetAll methods used in this recipe are very similar to those used in Recipe 5.6. 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 is whether you are going to be searching a List<T> that is sorted. Choose the GetAll method to obtain an array of all found items from an unsorted List<T>, and choose the BinarySearchGetAll method to get all items in a sorted List<T>.

The following code exercises these two new methods of the ListEx<T> class:

 class Test {     static void Main( )     {         ListEx<int> arrayExt = new ListEx<int>( );         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--");         int[] 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--");         arrayExt.Sort( );         objects = arrayExt.BinarySearchGetAll(-2);         foreach (object o in objects)         {             Console.WriteLine("obj-2: " + o);         }         Console.WriteLine( );         objects = arrayExt.BinarySearchGetAll(2);         foreach (object o in objects)         {             Console.WriteLine("obj2: " + o);         }         Console.WriteLine( );         objects = arrayExt.BinarySearchGetAll(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 BinarySearchGetAll method is faster than the GetAll method, especially if the array has already been sorted. If a BinarySearch is used on an unsorted List<T>, it is highly likely that the results returned by the search will be incorrect.