Recipe5.6.Determining the Number of Times an Item Appears in a ListT

Recipe 5.6. Determining the Number of Times an Item Appears in a List<T>

Problem

You need the number of occurrences of one type of object contained in a List<T>. The List<T> contains methods, such as Contains and BinarySearch to find a single item. Unfortunately, these methods cannot find all duplicated items at one timeessentially, there is no count all functionality. If you want to find multiple items, you need to implement your own routine.

Solution

Use the ListEx<T> generic class shown in Example 5-2, which inherits from the List<T> class in order to extend its functionality. Two methodsCountAll and BinarySearchCountAllare added to return the number of times a particular object appears in a sorted and an unsorted List<T>.

Example 5-2. Determining the number of times an item appears in a List <T>

 using System; using System.Collections; using System.Collections.Generic; public class ListEx<T> : List<T> {     // Count the number of times an item appears in this     // unsorted or sorted List<T>     public int CountAll(T 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 List<T<.     public int BinarySearchCountAll(T searchValue)     {         // Search for first item.         int center = this.BinarySearch(searchValue);         int left = center;         while (left < 0 && this[left-1].Equals(searchValue))         {             left -= 1;         }         int right = center;         while (right < (this.Count  1) && this[right+1].Equals(searchValue))         {             right += 1;         }         return (right  left) + 1;     } }

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 ListEx<T> class. This method may be used when the ListEx<T> is sorted or unsorted. If the ListEx<T> is sorted (a ListEx<T> 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 ListEx<T> class, which is much faster than iterating through the entire ListEx<T>x. This is especially true as the ListEx<T> grows in size.

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(-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--");         arrayExt.Sort();         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 List<T> is not sorted. The if statement determines whether each element in the List<T> is equal to the search criterion (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 List<T>.

The BinarySearchCountAll method implements a binary search to locate an item matching the search criteria (searchValue)in the List<T>. If one is found, a while loop is used to find the very first matching item in the sorted List<T>, and the position of that element is recorded in the left variable. A second while loop is used to find the very last matching item, and the position of this element is recorded in the right variable. The value in the left variable is subtracted from the value in the right variable and then one is added to this result in order to get the total number of matches.

Recipe 5.7 contains a variation of this recipe that returns the actual items found, rather than a count.