Recipe 3.6. Making a Type Searchable Problem You have a data type that will be stored as elements in an array or an ArrayList. You would like to use the Array.BinarySearch and ArrayList.BinarySearch methods to allow for custom searching of your data types in the array. Solution Use the IComparable and IComparer interfaces. The Square class, from Recipe 3.5, implements the IComparable interface in such a way that the Array, ArrayList, and SortedList objects can sort and search an array or collection of Square objects. Discussion By implementing the IComparable interface on your class (or structure), you can take advantage of the search routines of the Array, ArrayList, List<T>, and SortedList classes. The algorithms for searching are built into these classes; all you have to do is tell them how to search your classes via the code you implement in the IComparable.CompareTo method. To implement the CompareTo method, see Recipe 3.5. The Array, ArrayList, and List<T> classes provide a BinarySearch method to perform a search on the elements in that array. The elements are compared against an object passed to the BinarySearch method in the object parameter. The SortedList class does not have a BinarySearch method; instead, it has the Contains and ContainsKey methods, which perform a binary search on the key contained in the list. The ContainsValue method of the SortedList class performs a linear search when searching for values. This linear search uses the Equals method of the elements in the SortedList collection to do its work. The Compare and CompareTo methods do not have any effect on the operation of the linear search performed in the SortedList class, but they do have an effect on binary searches.  | To perform an accurate search using the BinarySearch methods of the Array and ArrayList classes, you must first sort the Array or ArrayList using its Sort method. In addition, if you pass an IComparer interface to the BinarySearch method, you must also pass the same interface to the Sort method. Otherwise, the BinarySearch method might not be able to find the object you are looking for. |
|
The TestSort method shown in Example 3-8 demonstrates how to use the Square and CompareHeight classes with the Array, ArrayList, and SortedList classes. Example 3-8. Making a type searchable public static void TestSort( ) { Square[] arrayOfSquares = new Square[4] {new Square(1,3), new Square(4,3), new Square(2,1), new Square(6,1)}; ArrayList arrayListOfSquares = new ArrayList( ); arrayListOfSquares.Add(new Square(1,3)); arrayListOfSquares.Add(new Square(4,3)); arrayListOfSquares.Add(new Square(2,1)); arrayListOfSquares.Add(new Square(6,1)); IComparer HeightCompare = new CompareHeight( ); // Test an ARRAY. Console.WriteLine("ARRAY"); Console.WriteLine("Original array"); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Sorted array using IComparer=HeightCompare"); Array.Sort(arrayOfSquares, HeightCompare); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparer=HeightCompare"); int found = Array.BinarySearch(arrayOfSquares, new Square(1,3), HeightCompare); Console.WriteLine("found (1,3): " + found); Console.WriteLine( ); Console.WriteLine("Sorted array using IComparable"); Array.Sort(arrayOfSquares); foreach (Square s in arrayOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine("Search using IComparable"); found = Array.BinarySearch(arrayOfSquares, new Square(6,1), null); // Use IComparable. Console.WriteLine("found (6,1): " + found); // Test an ARRAYLIST. Console.WriteLine( ); Console.WriteLine( ); Console.WriteLine("ARRAYLIST"); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Sorted ArrayList using IComparer=HeightCompare"); arrayListOfSquares.Sort(HeightCompare); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparer=HeightCompare"); found =arrayListOfSquares.BinarySearch(new Square(1,3), HeightCompare); Console.WriteLine("found (1,3): " + found); Console.WriteLine( ); Console.WriteLine("Sorted ArrayList using IComparable"); arrayListOfSquares.Sort( ); foreach (Square s in arrayListOfSquares) { Console.WriteLine(s.ToString( )); } Console.WriteLine( ); Console.WriteLine("Search using IComparable"); found = arrayListOfSquares.BinarySearch(new Square(6,1), null); Console.WriteLine("found (6,1): " + found); // Test a SORTEDLIST. SortedList SortedListOfSquares = new SortedList( ); SortedListOfSquares.Add(0, new Square(1,3)); SortedListOfSquares.Add(2, new Square(4,3)); SortedListOfSquares.Add(1, new Square(2,1)); SortedListOfSquares.Add(3, new Square(6,1)); Console.WriteLine( ); Console.WriteLine( ); Console.WriteLine("SORTEDLIST"); foreach (DictionaryEntry s in SortedListOfSquares) { Console.WriteLine(s.Key + " : " + ((Square)s.Value).ToString( )); } Console.WriteLine( ); bool foundBool = SortedListOfSquares.Contains(2); Console.WriteLine("SortedListOfSquares.Contains(2): " + foundBool); foundBool = SortedListOfSquares.ContainsKey(2); Console.WriteLine("SortedListOfSquares.ContainsKey(2): " + foundBool); // Does not use IComparer or IComparable // -- uses a linear search along with the Equals method, which has not been // overloaded; if the Square object were to be used as the key // rather than the value, a binary search would be performed when searching // for this Square object. Square value = new Square(6,1); foundBool = SortedListOfSquares.ContainsValue(value); Console.WriteLine ("SortedListOfSquares.ContainsValue(new Square(6,1)): " + foundBool); }
|
This code displays the following: ARRAY Original array Height:1 Width:3 Height:4 Width:3 Height:2 Width:1 Height:6 Width:1 Sorted array using IComparer=HeightCompare Height:1 Width:3 Height:2 Width:1 Height:4 Width:3 Height:6 Width:1 Search using IComparer=HeightCompare found (1,3): 0 Sorted array using IComparable Height:2 Width:1 Height:1 Width:3 Height:6 Width:1 Height:4 Width:3 Search using IComparable found (6,1): 2 ARRAYLIST Height:1 Width:3 Height:4 Width:3 Height:2 Width:1 Height:6 Width:1 Sorted ArrayList using IComparer=HeightCompare Height:1 Width:3 Height:2 Width:1 Height:4 Width:3 Height:6 Width:1 Search using IComparer=HeightCompare found (1,3): 0 Sorted ArrayList using IComparable Height:2 Width:1 Height:1 Width:3 Height:6 Width:1 Height:4 Width:3 Search using IComparable found (6,1): 2 SORTEDLIST 0 : Height:1 Width:3 1 : Height:2 Width:1 2 : Height:4 Width:3 3 : Height:6 Width:1 SortedListOfSquares.Contains(2): True SortedListOfSquares.ContainsKey(2): True SortedListOfSquares.ContainsValue(new Square(6,1)): False
See Also See Recipe 3.5; see the "IComparable Interface" and "IComparer Interface" topics in the MSDN documentation. |
