# JAL Computing

|  | # Chapter 15 "Using IComparer" Here again are four uses of abstract classes from Chapter 2:
| Defer the Final Implementation to Another More Knowledgeable Class
| Formally Hide or Encapsulate the Implementation for Flexibility
| Allow Runtime Variation in Implementation (Polymorphism)
| Mark Thyself
In Chapter 13, I demonstrated the use of encapsulation and polymorphism to load a plug-in at runtime. In this chapter, I am going to demonstrate how to use the IComparer interface to reuse the generic sort and binary search algorithm provided by the ArrayList class. The ArrayList class defers the final implementation of the sort and binary search algorithm to a more knowledgeable class. The more knowledgeable class must provide a useful concrete implementation of the IComparer interface. Properly done, the implementer of the IComparer interface can reuse the complex sort and binary search algorithm in the ArrayList class. For instance, the user may want to do a case insensitive sort of an ArrayList of strings and then perform an exact match binary search of the list of sorted strings. In this chapter I demonstrate an algorithm for finding the rows in the sorted list that are a partial match to a search key. This algorithm uses the binary search algorithm in the ArrayList class by passing an instance of a _different_ class that implements the IComparer interface! This type of algorithm might be useful in searching through listings in an Address Book application. Note: In a age long long past, I took issue to a challenge that Java could not be used in a real world application. I responded by programming a Java Address Book program and posting it on CompuServe. To do this, I had to write my own quick sort and binary search routines! Thankfully, both Java and C# now provide sort and binary search algorithms. ### Sample Code
    using System;
    using System.Collections;
    namespace TestBinarySearch
    {
    	/// <summary>
    	/// Demonstrates the use of IComparer for
    	/// case insensitive string compare.
    	/// Sample code to find rows in a sorted list
    	/// that are a partial match to a search key
    	/// </summary>
    	// ASSERT x, y are strings && not null
    	class MyCaseInsensitiveCompare : IComparer
    	{
    		// Case insensitive
    		public int Compare(object x, object y)
    		{
    			return String.Compare((string)x,(string)y,true);
    		}
    	}
    	class MyPartialMatchCompare : IComparer
    	{
    		// ASSERT x, y are strings && not null
    		// Case insensitive sort and compare
    		// y is the search key
    		public int Compare(object x, object y)
    		{
    			int length= ((string)y).Length;
    			if (((string)x).Length < length) return -1;
    			return String.Compare((string)x,0,(string)y,0,length,true);
    		}
    	}
    	class PartialMatch
    	{
    		private ArrayList al= null;
    		//ASSERT al not null
    		//ASSERT al contains non null strings
    		// Class Constructor
    		public PartialMatch(ArrayList al)
    		{
    			// shallow copy is safe since strings are immutable
    			this.al= (ArrayList)al.Clone();
    			// since our copy is safe, we can sort here once
    			this.al.Sort(new MyCaseInsensitiveCompare());
    		}
    		// ASSERT key not null
    		public void FindIt(string key)
    		{
    			// Do BINARY_SEARCH to find any partial match
    			int index= al.BinarySearch(key, new MyPartialMatchCompare());
    			System.Console.WriteLine("Input");
    			foreach (string s in al)
    			{
    				System.Console.WriteLine(s);
    			}
    			System.Console.WriteLine("Find: "+key);
    			if (index < 0) System.Console.WriteLine("No Match.");
    			else
    			//got at least one match for criteria find&
    			{
    				System.Console.WriteLine("Output");
    				// now do LINEAR_SEARCH for other matches
    				int firstIndex= index;
    				int lastIndex= index;
    				MyPartialMatchCompare mc= new MyPartialMatchCompare();
    				for (int i=index-1; i>=0 && (mc.Compare(al[i],key)==0) ; i--)
    				{
    					firstIndex= i;
    				}
    				for (int i=index+1; (i<al.Count) && (mc.Compare(al[i],key)==0); i++)
    				{
    					lastIndex= i;
    				}
    				for (int i=firstIndex;i<=lastIndex;i++)
    				{
    					System.Console.WriteLine(al[i]);
    				}
    			}
    		}

    		/// <summary>
    		/// The main entry point for the application.
    		/// </summary>
    		[STAThread]
    		static void Main(string[] args)
    		{
    			//
    			// TODO: Add code to start application here
    			//
    			ArrayList al= new ArrayList();
    			al.Add("Louie,Jeff");
    			al.Add("Smith,Ann");
    			al.Add("Smith,J");
    			al.Add("Smith,Dick,");
    			al.Add("Smith,Peter,");
    			al.Add("Smith,Jan");
    			al.Add("Smith,Tom");
    			al.Add("Smith,Harry");
    			al.Add("Smith,Joe");
    			al.Add("Smith,Joe");
    			al.Add("Smith,John");
    			PartialMatch pm= new PartialMatch(al);
    			pm.FindIt("SMITH,JO");
    			System.Console.ReadLine();
    			// OUTPUT
    			// Smith, Joe
    			// Smith, Joe
    			// Smith, John
    		}
    	}
    }
Now that was a lot easier than writing my own quick sort and binary search routines!

##### Send mail to jeff_louie@yahoo.com with questions or comments about this web site. Copyright © 2001, 2002, 2003, 2004, 2005, 2006, 2007 © Last modified: 11/22/07