// this code creates several objects of type Circ4 and Rect4, sorts them
// (according to the radius and the area, respectively, and searches for a
// specific Circ/Rect in this array by using the searchObj method of the
// class Search below.
// The findObj method of that class can handle any objects that implement
// the Comparable interface. 

public class SearchObj2
{
  public static void main(String[] args)
  {
     Circ4[] circs = {new Circ4(1, 1, 2), new Circ4(3, 8, 5),
        new Circ4(1, 1, 8), new Circ4(3, 8, 3), 
        new Circ4(1, 1, 4), new Circ4(3, 8, 9)};

     Rect4[] rects = {new Rect4(1, 1, 2, 6), new Rect4(3, 8, 5,6),
        new Rect4(1, 1, 8, 6), new Rect4(3, 8, 3, 6),
        new Rect4(1, 1, 4, 6), new Rect4(3, 8, 9, 6)};

     // sort the sircles and rects according to the diameter
     java.util.Arrays.sort(circs);
     java.util.Arrays.sort(rects);

   // Control output of sorted objects
     System.out.println("\nSorted Circles:");
     for (int i=0; i<circs.length; i++)
       System.out.println(circs[i]);

     System.out.println("\nSorted Rects:");
     for (int i=0; i<rects.length; i++)
       System.out.println(rects[i]);

     Circ4 qCirc = new Circ4(0, 0, 5);       // querry circle
     Rect4 qRect = new Rect4(0, 0, 5, 5);    // querry rectangle

     // search for the querry circle
     System.out.print("Circle: ");
     int i = Search.findObj(circs, 0, circs.length-1, qCirc);
     if (i >= 0)
       System.out.println("found at position " + i);
     else
       System.out.println("not found");

     // search for querry rectangle
     System.out.print("Rectangle: ");
     i = Search.findObj(rects, 0, rects.length-1, qRect);
     if (i >= 0)
       System.out.println("found at position " + i);
     else
       System.out.println("not found");
  }
}

class Search
{
  // binary search recursive method
  public static <T extends Comparable<T>> int findObj(T[] arr, int start, int stop, T qObj) 
  {
    if (start > stop) return(-1);
    int m = (start + stop) / 2;
    if (arr[m].compareTo(qObj) == 0) return(m);
    if (arr[m].compareTo(qObj) > 0)
      return findObj(arr, start, m-1, qObj);
    else
      return findObj(arr, m+1, stop, qObj);
  }
}