public class RandomIteratorTest {
   
   interface CreateRandomIteratorInstance
   {
      public RandomIterator createRandomIteratorInstance(long seed);
   }
   /**
    * @param args
    */
   public static void main(String[] args) {
      final int listSize = 1 << 20;
      final int iterations = 100;
      final List<Integer> list = new ArrayList<Integer>(listSize);
      for (int i = 0; i < listSize; i++) {
         list.add(i);
      }
      
      collisionCheck(list,iterations);
      speedTest(list.size(),iterations);

   }
   
   static private void collisionCheck(final List<Integer> list,final int iterations)
   {
      
      HashSet<Integer> seenSet = new HashSet<Integer>(list.size());
      
      // primeStep
      
      runCollisionTest(iterations,seenSet,list, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorPrimeStep(list, new Random(seed),seed);
         }
      });
      
      // BucketRiven
      
      runCollisionTest(iterations,seenSet,list, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorBucketRiven(list, 333,new Random(seed),seed);
         }
      });
      
   }
   
   static private void speedTest(final int listSize,final int iterations)
   {
      
      // primeStep
      
      runIndexOnlyTest(iterations,listSize, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorPrimeStep(listSize, new Random(seed),seed);
         }
      });
      
      // BucketRiven
      
      runIndexOnlyTest(iterations,listSize, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorBucketRiven(listSize, 333,new Random(seed),seed);
         }
      });
      

   }
   
   static private void runCollisionTest(final int iterations,final HashSet<Integer> seenSet, final List<Integer> list, CreateRandomIteratorInstance createRandomIteratorInstance)
   {
      RandomIterator randomIterator = null;
      for (int j = 0; j < iterations; j++) {
         seenSet.clear();
         randomIterator = createRandomIteratorInstance.createRandomIteratorInstance(j);

         for (int i = 0; i < list.size(); i++) {
            Integer obj = randomIterator.getNext();
            if (seenSet.contains(obj)) {
               System.out.println(randomIterator.getName()+" collision. "+randomIterator.getStatus());
               System.exit(1);
            }
            seenSet.add(obj);
         }
      }
      System.out.println(randomIterator.getName()+" no collisions.");
   }
   
   static private void runIndexOnlyTest(final int iterations, final int listSize, CreateRandomIteratorInstance createRandomIteratorInstance)
   {
      RandomIterator randomIterator = null;
      long startTime = System.currentTimeMillis();
      for (int j = 0; j < iterations; j++) {

         randomIterator = createRandomIteratorInstance.createRandomIteratorInstance(j);


         for (int i = 0; i < listSize; i++) {
            int index = randomIterator.getNextIndex();
         }
      }
      System.out.println(randomIterator.getName()+" time taken = "+(System.currentTimeMillis()-startTime));
   }
}

class SemiRandomIteratorBucketRiven implements RandomIterator {

   final Integer[] bucket;
   int currentBucket = 0;
   final int bucketSize;
   final List<Integer> remainder = new ArrayList<Integer>();
   final int bucketCount;
   final long seed;
   final List<Integer> list;
   int subBucketIndex = 0;
   final Random random;

   SemiRandomIteratorBucketRiven(List<Integer> list, int bucketCount,
         Random random, long seed) {

      this.bucketCount = bucketCount;
      this.list = list;
      this.seed = seed;
      this.random = random;
      bucketSize = list.size() / bucketCount;

      bucket = (Integer[]) new Integer[bucketSize];
   }
   
   SemiRandomIteratorBucketRiven(int collectionSize, int bucketCount,
         Random random, long seed) {

      list = new ArrayList<Integer>(collectionSize);
      for (int i = 0; i < collectionSize; i++) {
         list.add(i);
      }
      
      this.bucketCount = bucketCount;
      this.seed = seed;
      this.random = random;
      bucketSize = list.size() / bucketCount;

      bucket = (Integer[]) new Integer[bucketSize];
   }
   


   @Override
   public Integer getNext() {

      if (currentBucket == bucketCount) {
         if (subBucketIndex == 0) {
            if (list.size() % bucketCount != 0) {

               if (bucket.length == 0) {
                  remainder.addAll(list);
               } else {
                  for (int k = 0; k < bucketCount; k++) {
                     for (int i = k + bucket.length * bucketCount; i < list
                           .size(); i += bucketCount) {
                        remainder.add(list.get(i));
                     }
                  }
               }

               Collections.shuffle(remainder);
            }
         }
         return remainder.get(subBucketIndex++);
      } else {
         if (subBucketIndex == bucketSize) {
            subBucketIndex = 0;
            currentBucket++;
            return getNext();
         } else if (subBucketIndex == 0) {
            for (int i = 0, p = currentBucket; i < bucket.length; i++, p += bucketCount) {
               bucket[i] = list.get(p);
            }
            ;
         }

         int p = subBucketIndex
               + random.nextInt(bucketSize - subBucketIndex);
         Integer returnInteger = bucket[p];
         bucket[p] = bucket[subBucketIndex];
         subBucketIndex++;
         return returnInteger;

      }

   }

   @Override
   public String getStatus() {
      return "subBucketIndex: " + subBucketIndex + " currentBucket: "
            + currentBucket + " seed: " + seed;
   }

   @Override
   public int getNextIndex() {
      return getNext();
   }
   
   public String getName()
   {
      return "Bucket Riven";
   }
}


class SemiRandomIteratorPrimeStep extends IntervalRandomIterator {


   public SemiRandomIteratorPrimeStep(List<Integer> collection, Random random,long seed) {
      super(collection,createInterval(collection.size(),random),random,seed);

   }
   
   public SemiRandomIteratorPrimeStep(int collectionSize, Random random,long seed) {
      super(collectionSize,createInterval(collectionSize,random),random,seed);

   }
   
   private static int createInterval(int collectionSize, Random random)
   {

      final int bitLength = 24;

      return BigInteger.probablePrime(bitLength, random).intValue();

   }
   
   public String getName()
   {
      return "Prime Step";
   }
}


public interface RandomIterator {

   public Integer getNext();
   
   public int getNextIndex();
   
   public String getStatus();
   
   public String getName();

}

abstract class IntervalRandomIterator implements RandomIterator {

   public int getStartIndex() {
      return startIndex;
   }

   public int getInterval() {
      return interval;
   }

   public int getCurrIndex() {
      return currIndex;
   }

   private final int startIndex;
   private final int interval;
   private final List<Integer> collection;
   private final int collectionSize;
   private int currIndex;
   private final long seed;

   public IntervalRandomIterator(List<Integer> collection, int interval,Random random,long seed) {
      this.collection = collection;
      collectionSize = collection.size();
      this.interval=interval;
      startIndex = random.nextInt(collectionSize);
      currIndex = startIndex;
      this.seed=seed;
   }
   
   public IntervalRandomIterator(int collectionSize, int interval,Random random,long seed) {
      this.collection = null;
      this.collectionSize=collectionSize;
      this.interval=interval;
      startIndex = random.nextInt(collectionSize);
      currIndex = startIndex;
      this.seed=seed;
   }

   public Integer getNext() {
      Integer o = collection.get(currIndex);

      currIndex = (interval - (collectionSize - currIndex)) % collectionSize;

      return o;
   }
   
   public int getNextIndex() {
      int returnIndex = currIndex;

      currIndex = (interval - (collectionSize - currIndex)) % collectionSize;

      return returnIndex;
   }

   public String getStatus()
   {
      return "Index: "
            + getCurrIndex() + " interval: "
            + getInterval()
            + " startIndex: "
            + getStartIndex() + " seed: "
            + seed;
   }
}