import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Set;

public class Sequence {
  private static final float MIN_STRAIGHT_LENGTH = 0.5f;
  private static final float MAX_STRAIGHT_LENGTH = 0.8f;
  private static final float MIN_JUNK_VALUES = 0.1f;
  private static final float MAX_JUNK_VALUES = 0.3f;

  private static final int DIE_SIDES = 3;

  private static final int FACTOR = 5;
  private Integer[] map;
  private HashSet<Integer> keySet;
  private boolean cyclic;

  public Sequence() {
    keySet = new HashSet<Integer>();
    generateSimpleSequence();
  }

  public Sequence(int size, boolean hasCycle) {
    keySet = new HashSet<Integer>();
    generateRandomSequence(size, hasCycle);
  }

  public void generateSimpleSequence() {
    map = new Integer[10];

    map[0] = 9;
    map[1] = 6;
    map[2] = 5;
    map[3] = 1;
    map[4] = 3;
    map[5] = 10;
    map[6] = 9;
    map[7] = 9;
    map[8] = -10;
    map[9] = 4;
  }

  private LinkedList<Integer> generateValidValues(int size) {
    LinkedList<Integer> list = new LinkedList<Integer>();
    for (int i = 1; i < size; i++) {
      list.add(i);
    }
    return list;
  }

  private LinkedList<Integer> generateInvalidValues(int size) {
    LinkedList<Integer> list = new LinkedList<Integer>();
    for (int i = size; i < size * 2; i++) {
      list.add(i);
    }
    return list;
  }

  public int generateRandomSequence(int size, boolean hasCycle) {
    map = new Integer[size];
    Random rand = new Random();
    int cycleMinIndex = 0;
    int numJunkVals = -1;
    if (hasCycle) {
      int max = (int) (MAX_JUNK_VALUES * size);
      int min = (int) (MIN_JUNK_VALUES * size);
      numJunkVals = min + rand.nextInt(max - min);
    } else {
      numJunkVals = 0;
    }

    LinkedList<Integer> valid = generateValidValues(size);
    LinkedList<Integer> invalid = generateInvalidValues(size);

    LinkedList<Integer> seq = new LinkedList<Integer>();
    seq.add(0);
    for (int i = 1; i < size - numJunkVals; i++) {
      int nextVal = valid.remove(rand.nextInt(valid.size()));
      seq.add(nextVal);
    }
    int toReturn = -1;
    if (hasCycle) {
      int max = (int) (MAX_STRAIGHT_LENGTH * seq.size());
      int min = (int) (MIN_STRAIGHT_LENGTH * seq.size());
      cycleMinIndex = min + rand.nextInt(max - min);

      seq.add(seq.get(cycleMinIndex));
      toReturn = seq.get(cycleMinIndex);
    } else {
      seq.add(invalid.get(rand.nextInt(invalid.size())));
    }

    while (seq.size() > 1) {
      map[seq.remove(0)] = seq.get(0);
    }

    for (int i = 0; i < map.length; i++) {
      if (map[i] == null) {
        map[i] = invalid.get(rand.nextInt(invalid.size()));
      }
    }
    return toReturn;
  }

  public int successor(int element) {
    return map[element];
  }

  public int maxVal() {
    return map.length - 1;
  }

  public static void main(String[] args) {
    Sequence seq = new Sequence(200, true);
  }
}