package com.codemitts.chapter8;

import com.codemitts.ArrayUtils;
import org.junit.Assert;
import org.junit.Test;

import java.util.Random;

/**
 * Created by Sarika on 5/1/2015.
 *
 * 8-4 Water jugs
 * Suppose that you are given n red and n blue water jugs, all of different shapes and
 * sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover,
 * for every red jug, there is a blue jug that holds the same amount of water, and vice
 * versa.
 * Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold
 * the same amount of water. To do so, you may perform the following operation: pick
 * a pair of jugs in which one is red and one is blue, fill the red jug with water, and
 * then pour the water into the blue jug. This operation will tell you whether the red
 * or the blue jug can hold more water, or that they have the same volume. Assume
 * that such a comparison takes one time unit. Your goal is to find an algorithm that
 * makes a minimum number of comparisons to determine the grouping. Remember
 * that you may not directly compare two red jugs or two blue jugs.
 */

enum Color {
    Red,
    Blue
}

class Jug {
    private Color color;
    private int amt;

    public Jug(Color color, int amt) {
        this.color = color;
        this.amt = amt;
    }

    public static int compare(Jug j1, Jug j2) throws Exception {
        if (j1.color == j2.color) {
            throw new Exception("Cannot compare same color jugs");
        }

        if (j1.amt == j2.amt) {
            return 0;
        } else if (j1.amt > j2.amt) {
            return 1;
        } else {
            return -1;
        }
    }

    public static boolean isGoodPair(Jug j1, Jug j2) {
        return  (j1.amt == j2.amt);
    }

    public String getString() {
        return Integer.toString(amt)+"\t";
    }
}

public class WaterJugs {
    @Test
    public void testPairUp1() throws Exception {
        int len = 10;
        Jug[] blueJugs = new Jug[len];
        Jug[] redJugs = new Jug[len];
        fillJugs(blueJugs, redJugs, len);
        randomize(blueJugs, len, 10);
        randomize(redJugs, len, 10);
        pairUp(blueJugs, redJugs, len);
        System.out.print("Blue:   "); print(blueJugs);
        System.out.print("Red:    "); print(redJugs);
        Assert.assertTrue(testPairUp(blueJugs, redJugs, len));
    }

    @Test
    public void testPairUpFast1() throws Exception {
        int len = 10;
        Jug[] blueJugs = new Jug[len];
        Jug[] redJugs = new Jug[len];
        fillJugs(blueJugs, redJugs, len);
        randomize(blueJugs, len, 10);
        randomize(redJugs, len, 10);
        pairUpFast(blueJugs, redJugs, len);
        System.out.print("Blue:   "); print(blueJugs);
        System.out.print("Red:    "); print(redJugs);
        Assert.assertTrue(testPairUp(blueJugs, redJugs, len));
    }


    @Test
    public void testPairUp2() throws Exception {
        int len = 100000;
        Jug[] blueJugs = new Jug[len];
        Jug[] redJugs = new Jug[len];
        fillJugs(blueJugs, redJugs, len);
        randomize(blueJugs, len, len);
        randomize(redJugs, len, len);
        long t1 = System.currentTimeMillis();
        pairUp(blueJugs, redJugs, len);
        long t2 = System.currentTimeMillis();
        System.out.println(t2-t1);
        Assert.assertTrue(testPairUp(blueJugs, redJugs, len));
    }

    @Test
    public void testPairUpFast2() throws Exception {
        int len = 100000;
        Jug[] blueJugs = new Jug[len];
        Jug[] redJugs = new Jug[len];
        fillJugs(blueJugs, redJugs, len);
        randomize(blueJugs, len, len);
        randomize(redJugs, len, len);
        long t1 = System.currentTimeMillis();
        pairUpFast(blueJugs, redJugs, len);
        long t2 = System.currentTimeMillis();
        System.out.println(t2-t1);
        Assert.assertTrue(testPairUp(blueJugs, redJugs, len));
    }

    private void print(Jug[] jugs) {
        for (int i = 0; i < jugs.length; i++) {
            System.out.print(jugs[i].getString());
        }
    }

    private boolean testPairUp(Jug[] blueJugs, Jug[] redJugs, int len) {
        for (int i=0; i<len; i++) {
            if (!Jug.isGoodPair(blueJugs[i], redJugs[i])) {
                return false;
            }
        }
        return true;
    }

    private void randomize(Jug[] jugs, int len, int times) {
        Random r = new Random(System.currentTimeMillis());
        int x,y;
        Jug temp;
        for (int i=0; i<times; i++) {
            x = r.nextInt(len);
            y = r.nextInt(len);
            temp = jugs[x];
            jugs[x] = jugs[y];
            jugs[y] = temp;
        }
    }

    private void fillJugs(Jug[] blueJugs, Jug[] redJugs, int len) {
        int[] amts = ArrayUtils.getRandom(len);
        for (int i=0; i<len; i++) {
            blueJugs[i] = new Jug(Color.Blue, amts[i]);
            redJugs[i] = new Jug(Color.Red, amts[i]);
        }
    }

    /**
     * Deterministic algorithm that uses O(n^2) comparisons to group the jugs into pairs
     * @param blueJugs
     * @param redJugs
     * @param len
     * @throws Exception
     */
    public void pairUp(Jug[] blueJugs, Jug[] redJugs, int len) throws Exception {
        for (int i = 0; i < len; i++) {
            // find the right blue jug
            int j;
            for (j = i; j < len; j++) {
                if (Jug.compare(blueJugs[j],redJugs[i]) == 0) {
                    break;
                }
            }

            if (j >= len) {
                throw new IllegalArgumentException("Cannot find 2 jugs of same amount of water. Inconsistent input.");
            }

            // swap
            if (j != i) {
                Jug temp = blueJugs[j];
                blueJugs[j] = blueJugs[i];
                blueJugs[i] = temp;
            }
        }
    }

    /**
     * Randomized algorithm whose expected number of comparisons is O(n log n)
     * @param blueJugs
     * @param redJugs
     * @param len
     * @throws Exception
     */
    public void pairUpFast(Jug[] blueJugs, Jug[] redJugs, int len) throws Exception {
        pairUpFast(blueJugs, redJugs, 0, len-1);
    }

    private void pairUpFast(Jug[] blueJugs, Jug[] redJugs, int start, int end) throws Exception {
        if (start >= end) {
            return;
        }

        // parse red jugs
        Jug pivot = blueJugs[end];
        int i,mid,cmp,same=-1;
        for (i=start,mid=start; i<=end; i++) {
            cmp = Jug.compare(redJugs[i], pivot);
            if (cmp == 0) {
                same = mid;
            }
            if (cmp <= 0) {
                // swap mid and i
                Jug temp = redJugs[i];
                redJugs[i] = redJugs[mid];
                redJugs[mid] = temp;
                mid++;
            }
        }

        mid--;
        if (same < 0) {
            throw new IllegalArgumentException("Cannot find 2 jugs of same amount of water. Inconsistent input.");
        }

        // swap same and mid
        Jug temp = redJugs[mid];
        redJugs[mid] = redJugs[same];
        redJugs[same] = temp;


        // parse blue jugs
        pivot = redJugs[mid];
        same = -1;
        for (i=start,mid=start; i<=end; i++) {
            cmp = Jug.compare(blueJugs[i], pivot);
            if (cmp == 0) {
                same = mid;
            }
            if (cmp <= 0) {
                // swap mid and i
                temp = blueJugs[i];
                blueJugs[i] = blueJugs[mid];
                blueJugs[mid] = temp;
                mid++;
            }
        }
        mid--;
        if (same < 0) {
            throw new IllegalArgumentException("Cannot find 2 jugs of same amount of water. Inconsistent input.");
        }

        // swap same and mid
        temp = blueJugs[mid];
        blueJugs[mid] = blueJugs[same];
        blueJugs[same] = temp;


        // call pair up on sub arrays
        pairUpFast(blueJugs, redJugs, start, mid-1);
        pairUpFast(blueJugs, redJugs, mid+1, end);
    }
}
