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

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

/**
 * Utility class for the Floyd and Bentley algorithm.
 *
 * @author $Author: $
 * @version $Revision: $, $Date: $ UTC
 */
public final class FloydAndBentley
{

   private static Random rnd = new Random();

   /**
    * Private constructor for utility class.
    *
    */
   private FloydAndBentley()
   {
   }

   /**
    * A function which chooses a sample from a List with the Floyd and Bentley
    * algorithm. (Recursive 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 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;

   }

   /**
    * The recursive implementation of 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.
    * @param ret
    *           Return the sample.
    */
   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())));

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

      ret.add(val);

      sampleRec(s, k, ret);

   }

   /**
    * A function which chooses a sample from a List with the Floyd and Bentley
    * algorithm. (Non recursive 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 sample.
    */
   public static <T> List<T> sample2(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);

      for (int i = 0; i < k; i++)
      {
         T val = s.get(rnd.nextInt(s.size() - (k - ret.size())));

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

         ret.add(val);
      }

      return ret;
   }
}