//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  An arrays utility class

package schaums.dswj;

import java.util.Random;

public class Arrays
{ private static Random random = new Random();

  public static int load(int start, int range)
  { return random.nextInt(range) + start;
  }
  
  public static void load(int[] a, int start, int range)
  { int n=a.length;
    for (int i=0; i<n; i++)
      a[i] = random.nextInt(range) + start;
  }
  
  public static void print(int[] a)
  { for (int i=0; i<a.length; i++)
      System.out.print("  " + (i>9?"":" ") + i);
    System.out.print("\n{ " + a[0]);
    for (int i=1; i<a.length; i++)
      System.out.print(", " + a[i]);
    System.out.println(" }");
  }
  
  public static void load(double[] a, int start, int range)
  { int n=a.length;
    for (int i=0; i<n; i++)
      a[i] = random.nextInt(range) + start;
  }
  
  public static void print(double[] a)
  { for (int i=0; i<a.length; i++)
      System.out.print("  " + (i>9?"":" ") + i);
    System.out.print("\n{ " + a[0]);
    for (int i=1; i<a.length; i++)
      System.out.print(", " + a[i]);
    System.out.println(" }");
  }
  
  public static void load(Object[] a, int start, int range)
  { int n=a.length;
    for (int i=0; i<n; i++)
    { int m = random.nextInt(range) + start;
      if (i%3==0) a[i] = new Integer(m);
      else if (i%3==1) a[i] = new Double(m);
      else a[i] = "(" + m + ")";
    }
  }
  
  public static void print(Object[] a)
  { for (int i=0; i<a.length; i++)
      System.out.print("  " + (i>9?"":" ") + i);
    System.out.print("\n{ " + a[0]);
    for (int i=1; i<a.length; i++)
      System.out.print(", " + a[i]);
    System.out.println(" }");
  }
  
  public static void print(String label, Object[] a)
  { System.out.print(label + " = ");
    for (int i=0; i<a.length; i++)
      System.out.print("  " + (i>9?"":" ") + i);
    System.out.print("\n{ " + a[0]);
    for (int i=1; i<a.length; i++)
      System.out.print(", " + a[i]);
    System.out.println(" }");
  }
  
  public static void swap(int[] a, int i, int j)
  { int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
  
  public static void swap(Object[] a, int i, int j)
  { Object temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
  
  public static int sequentialSearch(int[] a, int x)
  { // POSTCONDITIONS: returns i; if i >= 0, then a[i] == x;
    //                 otherwise i == -1;
    for (int i=0; i<a.length; i++)                      // step 1
      // INVARIANT: if a[k]==x then i <= k < a.length;  // step 2
      // INVARIANT: a[k] != x, for 0 <= k < i;          // step 2
      if (a[i]==x) return i;                            // step 3
    return -1;                                          // step 4
  }

  public static int binarySearch(int[] a, int x)
  { // PRECONDITION:   a[0] <= a[1] <= ... <= a[a.length-1];
    // POSTCONDITIONS: returns i; if i >= 0, then a[i] == x;
    //                 otherwise i == -1;
    int lo=0, hi=a.length-1;
     while (lo <= hi)                                // step 1
    { // INVARIANT: if a[j]==x then lo <= j <= hi;  // step 3
       int i = (hi + lo)/2;                          // step 4
       if (a[i] == x) return i;                      // step 5
       else if (a[i] < x) lo = i+1;                  // step 6
       else hi = i-1;                                // step 7
     }
    return -1;                                      // step 2
  }
}