/**
 * 
 */
package de.fhswf.in.inf.java1.aufgabe8;

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

/**
 * TODO Add comment here
 *
 * @author $Author: $
 * @version $Revision: $, $Date: $ UTC
 */
public final class FloydAndBentley
{

   private static Random rnd = new Random();

   /**
    * TODO Add constructor comment here
    *
    */
   private FloydAndBentley()
   {
      // TODO Auto-generated constructor stub
   }

   /**
    * A function which chooses a sample from a List with the Floyd and Bentley
    * algorithm.
    *
    *
    * @param <T>
    *           Type of the Lists.
    * @param s
    *           The set from which the sample is chosen.
    * @param k
    *           The number of items to be chosen.
    * @return Return the ordered sample.
    */
   public static <T> List<T> sample(List<T> s, int k)
   {
      if (s.isEmpty())
      {
         throw new IllegalArgumentException("Set is empty");
      }
      if (k > s.size())
      {
         throw new IllegalArgumentException("k is bigger than the Set");
      }

      List<T> ret = new ArrayList<>(k);
      sampleRec(s, k, ret);

      return ret;

   }

   /**
    * TODO Add method comment here
    *
    * @param <T>
    * @param s
    * @param k
    * @param ret
    */
   private static <T> void sampleRec(List<T> s, int k, List<T> ret)
   {
      if (ret.size() >= k)
      {
         return;
      }

      T val = s.get(rnd.nextInt(s.size() - ((k - ret.size()) - 1)));

      if (ret.contains(val))
      {
         val = s.get(s.size() - ((k - ret.size()) - 1));
      }

      ret.add(val);

      sampleRec(s, k, ret);

   }
}