/**Demo March 17 */
public class D {
    
    /** = index of first occurrence of c in s.
          Precondition: c is in s. */
    public static int first(char c, String s) {
        int k= 0;
        // Store in k index of the first occ. of c in s
        
        // inv: s[0..k-1] does not contain c
        while (s.charAt(k) != c) {
            k= k+1;
        }
        
        // k = index of the first occ. of c in s
        
        return k;
    }
    
    
    /** = index of first occurrence of c in b.
          Precondition: c is in b. */
    public static int first(char c, char[] b) {
        int k= 0;
        // Store in k index of the first occ. of c in b
        
        // inv: b[0..k-1] does not contain c
        while (b[k] != c) {
            k= k+1;
        }
        
        
        // k = index of the first occ. of c in b

        return k;
    }
    
    /** For a call swap(b,c), this does NOT swap the
        values in variables b and c. Execute the call
        by hand ot see why. */
    public static void swap(int x, int y) {
        int temp= x;
        x= y;
        y= temp;
    }
    
    
    /** Swap b[h] and b[k] */ 
    public static void swap (int[] b, int h, int k) { 
        int temp= b[h];
        b[h]= b[k];
        b[k]= temp;
    } 
    
    private static String[] words= new String[]
           {"zero", "one", "two", "three", "four", "five"};
        
    
    /** = word for n. Precondition 0 < n < 5 */
    public static String word(int n) {
        return words[n];
    }
    
    /* Below, we write the algorithm to roll a die, where the 
       probabilities of the faces being up are given by an array p:
       p[i] is the probability that face i will be up.
       
       Checking this out may be difficult because it involves random
       numbers. Below the method, we write another method that calls 
       rollDie a number of times and prints out how many times each face
       was up after a roll. We can use that to help see whether rollDie
       it OK. For example, try these:
       
          D.testRollDie(new double[]{.25, .25, .25, .25}, 10000000);
          D.testRollDie(new double[]{.1, .1, .1, .1, .1, .5}, 10000000);
    */
    
    
    /** p contains a list of probabilities that add up to 1.
        For example, p = {.1, .1, .1, .1, .1, .5} could be
        probabilities for rolling an unfair die that yields 1, 2, 3,
        4, and 5 with equal probability but 6 with probability 5 times
        that of the other faces.
        
        So, we view p as representing an unfair die with p.length faces,
        numbered 0, 1, 2, ..., p.length-1, with each p[k] giving the
        probability that face k is up when the die is rolled.
        
        Roll the die and return the face that is up. */
    public static int rollDie(double[] p) {
        double r= Math.random(); // r in [0,1)
        int n= p.length-1;
        /** Consider these segments of [0..1):
            0: 0         to (but no including) p[0]
            1: p[0]      to (but no including) p[0]+p[1]
            2: p[0]+p[1] to (but no including) p[0]+p[1]+p[2]
            ...
            n: p[0]+...+p[n-1] to (but no including) p[0]+...+p[n]
            
            r lies in one of these segments; we have to find which one
            and return that segment numbers. This is a linear search,
            starting from the beginning, with a variable endk to
            indicate the end of the segment to be searched next.
            */
        
        int k= 0;
        double endk= p[0];
        /** invariant: r is not in segments 0..k-1 and
                       endk is the right boundary of segment k */
        while (r >= endk) {
            endk= endk + p[k+1];
            k= k+1;
        }
                    
        // r is not in segments 0..k-1 and r < rendk, 
        // i.e. r is in segment k
        return k;
    }
    
    /** Roll a die with face probabilities given by p n times
        and print the number of times each face came up. */
    public static void testRollDie(double[] p, int n) {
        int[] times=  new int[p.length];
        
        //inv: The die has been rolled k-1 times and each
        //     times[f] is the number of times face f was on top.
        for (int k= 1; k <= n; k= k+1) {
            int f= rollDie(p);
            times[f]= times[f] + 1;
        }
       
        //inv: times[0..f-1] has been printed
        for (int f= 0; f < p.length; f= f+1) {
            System.out.println("face " + f + ": " + times[f] + " times.");
        }
    }
    
        
}