/* Randomizer.java
   Copyright (c) 2009 Noa Resare <noa@voxbiblia.com>

   This piece of software is hereby put in the public domain and can be used
   and modified by anyone for any purpose.

 */


import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Selects a random small sublist of a large list in a somewhat efficient manner.
 */
public class Randomizer<T>
{
    private Random random;

    /**
     * Constructs a new Randomizer with a newly initalized instance of
     * java.util.Random as it's entropy source.
     */
    public Randomizer()
    {
        random = new Random();
    }

    /**
     * Construts a new Randomizer with a user supplied entropy source.
     *
     * @param random the instance of Random used to provide entropy
     */
    public Randomizer(Random random)
    {
        this.random = random;
    }

    /**
     * Creates and returns a list with count randomly selected unique
     * elements from the list source.
     *
     * @param source the list to pick elements from
     * @param count the number of unique elements in the resulting  list
     * @return a random sublist
     */
    public List<T> randomSublist(List<T> source, int count)
    {
        List<Integer> offsets = new ArrayList<Integer>(count);
        for (int i = 0; i < count; i++) {
            offsets.add(random.nextInt(source.size() - i));
        }
        while (count-- > 0) {

        }
        List<T> l = new ArrayList<T>();
        compensateOffsets(offsets);
        for (int offset : offsets) {
            l.add(source.get(offset));
        }
        return l;
    }

    static void compensateOffsets(List<Integer> offsets)
    {
        for (int i = 0; i < offsets.size(); i++) {
            int off = offsets.get(i);
            for (int j = 0; j <= off; j++) {
                for (int k = 0; k < i; k++) {
                    if (offsets.get(k) == j) {
                        off++;
                    }
                }
            }
            offsets.set(i, off);
        }
    }

}