/*************************************************************************
 *  Compilation:  javac LoadBalance.java
 *  Execution:    java LoadBalance N M S
 *  Dependencies: Queue.java RandomQueue.java StdOut.java
 *
 *  Simulates the process of assigning N items to a set of M servers. 
 *  Requests are put on the shortest of a sample of S queues
 *  chosen at random (with replacement).
 *
 *  % java LoadBalance 100 10 2
 *  min load = 8
 *  avg load = 10.0
 *  max load = 11
 *  (11):  3  8 16 27 39 45 61 65 76 97 99 
 *  ( 9):  2 40 41 44 49 57 69 78 81 
 *  (10): 23 26 28 33 35 52 56 59 82 98 
 *  ( 8):  4 12 15 25 37 51 62 88 
 *  (11):  0  9 19 29 55 63 66 72 90 92 93 
 *  (11):  6 17 21 24 46 50 67 73 83 84 96 
 *  (10): 13 32 38 42 48 53 60 74 94 95 
 *  (11):  7 11 14 31 34 36 54 70 86 87 89 
 *  (10): 10 18 20 22 58 64 68 75 80 85 
 *  ( 9):  1  5 30 43 47 71 77 79 91 
 *
 *  % java LoadBalance 1000 1000000 1
 *  min load = 889
 *  avg load = 1000.0
 *  max load = 1121
 *
 *  % java LoadBalance 1000 1000000 1
 *  min load = 909
 *  avg load = 1000.0
 *  max load = 1095
 *
 *  % java LoadBalance 1000 1000000 2
 *  min load = 995
 *  avg load = 1000.0
 *  max load = 1002
 *
 *  % java LoadBalance 1000 1000000 2
 *  min load = 995
 *  avg load = 1000.0
 *  max load = 1002
 *
 *************************************************************************/

public class LoadBalance { 
    public static void main(String[] args)  { 
        int M = Integer.parseInt(args[0]);     // # of servers 
        int N = Integer.parseInt(args[1]);     // # of items 
        int S = Integer.parseInt(args[2]);     // sample size 

        assert (N >= 0);
        assert (M >= 1);
        assert (S >= 1);

        // create M empty servers
        RandomQueue<Queue<Integer>> servers = new RandomQueue<Queue<Integer>>();
        for (int i = 0; i < M; i++) {
            servers.enqueue(new Queue<Integer>());
        }


        // assign N items
        for (int j = 0; j < N; j++) {

            // choose S servers at random and find least loaded one
            Queue<Integer> min = servers.sample();
            for (int k = 1; k < S; k++) {
                Queue<Integer> q = servers.sample();
                if (q.length() < min.length())
                    min = q;
            }

            // add item i to the least loaded server
            min.enqueue(j); 
        } 

        // compute statistics
        int maxLoad = 0;
        int minLoad = N;
        for (Queue<Integer> server : servers) {
            if (server.length() > maxLoad) maxLoad = server.length();
            if (server.length() < minLoad) minLoad = server.length();
        }

        // print statistics
        StdOut.println("min load = "  + minLoad);
        StdOut.println("avg load = "  + 1.0*N/M);
        StdOut.println("max load = "  + maxLoad);

        // print out contents of each server
        if (N <= 100) {
            for (Queue<Integer> server : servers) {
                StdOut.printf("(%2d): ", server.length());
                for (int item : server) {
                    StdOut.printf("%2d ", item);
                }
                StdOut.println();
            }
        }

    } 
}