import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class BinSearch
   {

   /**
    * Comparator for reverse alphabetic sorting
    */
   private static final Comparator<String> order = new ReverseAlphabetically();

   /**
    * test binary search
    *
    * @param args not used
    */
   public static void main ( String[] args )
      {

      // create a Collection of antelope species
      ArrayList<String> antelopes = new ArrayList<String>(10);
      antelopes.add( "kudu" );
      antelopes.add( "gazelle" );
      antelopes.add( "springbok" );
      antelopes.add( "impala" );
      antelopes.add( "duiker" );

      // sort in reverse order
      Collections.sort( antelopes, order );

      // display Collection
      // springbok
      // kudu
      // impala
      // gazelle
      // duiker
      for ( String antelope : antelopes )
         {
         System.out.println( antelope );
         }

      // Binary search
      // negative wherefound means where to insert, positive means where found.
      int whereFound = Collections.binarySearch( antelopes, "gnu", order );

      System.out.println( whereFound );
      // Result is -4. Thus the insert point is +3.
      // "gnu" would be sitting at index 3 after insertion,
      // between impala and gazelle.
      // gazelle and duiker would slide up.
      // gnu would sit where gazelle used to.
      }

   }  // end class BinSearch

/**
 * top level default scope Comparator to sort in reverse order.
 */
class ReverseAlphabetically implements Comparator<String>
   {
   /**
     * Compare two Strings in reverse order
     * Callback for sort.
     * effectively returns -(a-b);
     * @return -1, a>b, 0 a=b, +1 a<b, case insenstive
     */
   public final int compare( String a, String b )
      {
      // swap usual roles of a and b.
      return b.compareToIgnoreCase( a );
      } // end compare

   } // end class ReverseAlphabetically