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);
         }
      });
      
      // POT Roquen
      
      runCollisionTest(iterations,seenSet,list, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorPOTRoquen(list, new Random(seed),seed);
         }
      });
      
//      // Directional UprightPath
//      
//      runCollisionTest(iterations,seenSet,list, new CreateRandomIteratorInstance() {
//         
//         @Override
//         public RandomIterator createRandomIteratorInstance(long seed) {
//            return new SemiRandomIteratorDirectionalUprightPath(list, 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);
         }
      });
      
      // POT Roquen
      
      runIndexOnlyTest(iterations,listSize, new CreateRandomIteratorInstance() {
         
         @Override
         public RandomIterator createRandomIteratorInstance(long seed) {
            return new SemiRandomIteratorPOTRoquen(listSize, new Random(seed),seed);
         }
      });
      
//      // Directional UprightPath
//      
//      runIndexOnlyTest(iterations,listSize, new CreateRandomIteratorInstance() {
//         
//         @Override
//         public RandomIterator createRandomIteratorInstance(long seed) {
//            return new SemiRandomIteratorDirectionalUprightPath(listSize, 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;
   }
}

public class SemiRandomIteratorDirectionalUprightPath implements RandomIterator {

   private int startIndex;
   private int rangeStart;
   private int rangeEnd;
   private int currIndex;
   private int currLoopIndex;
   private int step;
   private boolean up;
   private boolean move;
   private final List<Integer> collection;
   private final Random random;
   private final long seed;
   private final int collectionSize;

   public SemiRandomIteratorDirectionalUprightPath(List<Integer> collection,
          Random random, long seed) {
      this.collection = collection;
      this.random = random;
      this.seed = seed;
      this.collectionSize = collection.size();
      this.rangeStart = random.nextInt(collectionSize);
      
      int range;
      if (collectionSize%2==1)
      {
         range=collectionSize+1;
      }
      else
      {
         range=collectionSize;
      }
      
      
      this.rangeEnd = this.rangeStart + range;
      this.startIndex = this.rangeStart + random.nextInt(range);
      this.currIndex = startIndex;
      this.currLoopIndex = this.currIndex;
      this.step = range/2;
      this.up = random.nextBoolean();
      this.move = random.nextBoolean();
   }
   
   public SemiRandomIteratorDirectionalUprightPath(int collectionSize,
          Random random, long seed) {
      this.collection = null;
      this.random = random;
      this.seed = seed;
      this.collectionSize = collection.size();
      this.rangeStart = random.nextInt(collectionSize);
      
      int range;
      if (collectionSize%2==1)
      {
         range=collectionSize+1;
      }
      else
      {
         range=collectionSize;
      }
      
      
      this.rangeEnd = this.rangeStart + range;
      this.startIndex = this.rangeStart + random.nextInt(range);
      this.currIndex = startIndex;
      this.currLoopIndex = this.currIndex;
      this.step = range/2;
      this.up = random.nextBoolean();
      this.move = random.nextBoolean();
   }

   public Integer getNext() {
      if (currIndex >= collectionSize) {
         calculateNextIndex();
         return getNext();
      }

      Integer o = collection.get(currIndex);
      calculateNextIndex();
      return o;
   }

   private void calculateNextIndex() {
      if (up) {
         currIndex += step;
         if (currIndex >= rangeEnd) {
            currIndex = rangeStart + (currIndex - rangeEnd);
         }
      } else {
         currIndex -= step;
         if (currIndex < rangeStart) {
            currIndex = rangeEnd - (rangeStart - currIndex);
         }
      }
      if (currLoopIndex == currIndex) {
         currIndex += move ? 1 : -1;
         if (currIndex >= rangeEnd) {
            currIndex = rangeStart + (currIndex - rangeEnd);
         } else if (currIndex < rangeStart) {
            currIndex = rangeEnd - (rangeStart - currIndex);
         }
         currLoopIndex = currIndex;
      }

   }

   @Override
   public int getNextIndex() {

      if (currIndex >= collectionSize) {
         calculateNextIndex();
         return getNextIndex();
      }

      int returnIndex = currIndex;
      calculateNextIndex();
      return returnIndex;
   }

   @Override
   public String getStatus() {
      return "no status";
   }

   @Override
   public String getName() {
      return "Directional by UprightPath";
   }
}


public class SemiRandomIteratorPOTRoquen implements RandomIterator {

   private final List<Integer> collection;
   private final Random random;
   private final long seed;
   private final int collectionSize;
   private final int length;
   private int m;
   private int a;
   private int mask;
   private int v;


   public SemiRandomIteratorPOTRoquen(List<Integer> collection,Random random, long seed)
     {
      this.random=random;
      this.collection=collection;
      this.collectionSize=collection.size();
      this.seed=seed;
      length = 1<< ((int) Math.ceil(Math.log(collectionSize)/Math.log(2)));
       setLength(length);
     }
   
   public SemiRandomIteratorPOTRoquen(int collectionSize,Random random, long seed)
     {
      this.random=random;
      this.collection=null;
      this.collectionSize=collectionSize;
      this.seed=seed;
      length = 1<< ((int) Math.ceil(Math.log(collectionSize)/Math.log(2)));
       setLength(length);
     }

     /** Set the length of the sequence.  Must be a power-of-two.  */
     public void setLength(int length)
     {
       mask = length-1;
       reset();
     }

     /** Create a new permutation of the current length. */
     public void reset()
     {
       // this is all overkill
       m = (random.nextInt()<<3)|5;   // anything such that (m & 7)==5 
       a = (random.nextInt()<<1)|1;   // any odd value
       v = (random.nextInt());        // basically sets the offset that zero will appear
     }



   public Integer getNext() {
      Integer o = collection.get(getNextIndex());
      return o;
   }

   @Override
   public int getNextIndex() {

      do
      {   
          v = (m*v + a) & mask;
//          System.out.println(v);
      } while (v>=collectionSize);


       return v;
   }

   @Override
   public String getStatus() {
      return "index: "+v+" length: "+length+" seed: "+seed;
   }

   @Override
   public String getName() {
      return "Power of Two Perturbed Sequence by Roquen";
   }
}