public final class EuclideanDistance {

  /**
   * Constructor.
   */
  public EuclideanDistance() {
    super();
  }

  /**
   * Calculates the Euclidean distance between two points.
   * 
   * @param p1 The first point.
   * @param p2 The second point.
   * @return The Euclidean distance.
   */
  public double distance(double p1, double p2) {
    double d = (p1 - p2) * (p1 - p2);
    return Math.sqrt(d);
  }

  /**
   * Calculates the Euclidean distance between two points.
   * 
   * @param point1 The first point.
   * @param point2 The second point.
   * @return The Euclidean distance.
   * @throws Exception In the case of error.
   */
  public double distance(double[] point1, double[] point2) throws Exception {
    return Math.sqrt(distance2(point1, point2));
  }

  /**
   * Calculates the Euclidean distance between two points.
   * 
   * @param point1 The first point.
   * @param point2 The second point.
   * @return The Euclidean distance.
   * @throws Exception In the case of error.
   */
  public double distance(int[] point1, int[] point2) throws Exception {
    return Math.sqrt(Long.valueOf(distance2(point1, point2)).doubleValue());
  }

  /**
   * Calculates the square of the Euclidean distance between two 1D points represented by real
   * values.
   * 
   * @param p1 The first point.
   * @param p2 The second point.
   * @return The Square of Euclidean distance.
   */
  public double distance2(double p1, double p2) {
    return (p1 - p2) * (p1 - p2);
  }

  /**
   * Calculates the square of the Euclidean distance between two multidimensional points represented
   * by the rational vectors.
   * 
   * @param point1 The first point.
   * @param point2 The second point.
   * @return The Euclidean distance.
   * @throws Exception In the case of error.
   */
  public double distance2(double[] point1, double[] point2) throws Exception {
    if (point1.length == point2.length) {
      Double sum = 0D;
      for (int i = 0; i < point1.length; i++) {
        double tmp = point2[i] - point1[i];
        sum = sum + tmp * tmp;
      }
      return sum;
    }
    else {
      throw new Exception("Exception in Euclidean distance: array lengths are not equal");
    }
  }

  /**
   * Calculates the square of the Euclidean distance between two multidimensional points represented
   * by integer vectors.
   * 
   * @param point1 The first point.
   * @param point2 The second point.
   * @return The Euclidean distance.
   * @throws Exception In the case of error.
   */
  public long distance2(int[] point1, int[] point2) throws Exception {
    if (point1.length == point2.length) {
      long sum = 0;
      for (int i = 0; i < point1.length; i++) {
        sum = sum + (point2[i] - point1[i]) * (point2[i] - point1[i]);
      }
      return sum;
    }
    else {
      throw new Exception("Exception in Euclidean distance: array lengths are not equal");
    }
  }

  /**
   * Calculates Euclidean distance between two multi-dimensional time-series of equal length.
   * 
   * @param series1 The first series.
   * @param series2 The second series.
   * @return The eclidean distance.
   * @throws Exception if error occures.
   */
  public double seriesDistance(double[][] series1, double[][] series2) throws Exception {
    if (series1.length == series2.length) {
      Double res = 0D;
      for (int i = 0; i < series1.length; i++) {
        res = res + distance2(series1[i], series2[i]);
      }
      return Math.sqrt(res);
    }
    else {
      throw new Exception("Exception in Euclidean distance: array lengths are not equal");
    }
  }

  /**
   * Calculates the Normalized Euclidean distance between two points.
   * 
   * @param point1 The first point.
   * @param point2 The second point.
   * @return The Euclidean distance.
   * @throws Exception In the case of error.
   */
  public double normalizedDistance(double[] point1, double[] point2) throws Exception {
    return Math.sqrt(distance2(point1, point2)) / point1.length;
  }

  /**
   * Implements Euclidean distance with early abandoning.
   * 
   * @param series1 the first series.
   * @param series2 the second series.
   * @param cutoff the cut-off threshold
   * @return the distance if it is less than cutoff or Double.NAN if it is above.
   * 
   * @throws Exception if error occurs.
   */
  public Double earlyAbandonedDistance(double[] series1, double[] series2, double cutoff)
      throws Exception {
    if (series1.length == series2.length) {
      double cutOff2 = cutoff;
      if (Double.MAX_VALUE != cutoff) {
        cutOff2 = cutoff * cutoff;
      }
      Double res = 0D;
      for (int i = 0; i < series1.length; i++) {
        res = res + distance2(series1[i], series2[i]);
        if (res > cutOff2) {
          return Double.NaN;
        }
      }
      return Math.sqrt(res);
    }
    else {
      throw new Exception("Exception in Euclidean distance: array lengths are not equal");
    }
  }

}
 public enum NumerosityReductionStrategy {

  /** No reduction at all - all the words going make it into collection. */
  NONE(0),

  /** Exact - the strategy based on the exact string match. */
  EXACT(1),

  /** Classic - the Lin's and Keogh's MINDIST based strategy. */
  MINDIST(2);

  private final int index;

  /**
   * Constructor.
   * 
   * @param index The strategy index.
   */
  NumerosityReductionStrategy(int index) {
    this.index = index;
  }

  /**
   * Gets the integer index of the instance.
   * 
   * @return integer key of the instance.
   */
  public int index() {
    return index;
  }

  /**
   * Makes a strategy out of integer. 0 stands for NONE, 1 for EXACT, and 3 for MINDIST.
   * 
   * @param value the key value.
   * @return the new Strategy instance.
   */
  public static NumerosityReductionStrategy fromValue(int value) {
    switch (value) {
    case 0:
      return NumerosityReductionStrategy.NONE;
    case 1:
      return NumerosityReductionStrategy.EXACT;
    case 2:
      return NumerosityReductionStrategy.MINDIST;
    default:
      throw new RuntimeException("Unknown index:" + value);
    }
  }

  /**
   * {@inheritDoc}
   */
  public String toString() {
    switch (this.index) {
    case 0:
      return "NONE";
    case 1:
      return "EXACT";
    case 2:
      return "MINDIST";
    default:
      throw new RuntimeException("Unknown index:" + this.index);
    }
  }

  /**
   * Parse the string value into an instance.
   * 
   * @param value the string value.
   * @return new instance.
   */
  public static NumerosityReductionStrategy fromString(String value) {
    if ("none".equalsIgnoreCase(value)) {
      return NumerosityReductionStrategy.NONE;
    }
    else if ("exact".equalsIgnoreCase(value)) {
      return NumerosityReductionStrategy.EXACT;
    }
    else if ("mindist".equalsIgnoreCase(value)) {
      return NumerosityReductionStrategy.MINDIST;
    }
    else {
      throw new RuntimeException("Unknown index:" + value);
    }
  }
} public final class SAXProcessor {

  private final TSProcessor tsProcessor;
  private final NormalAlphabet na;
  private EuclideanDistance ed;

  /**
   * Constructor.
   */
  public SAXProcessor() {
    super();
    this.tsProcessor = new TSProcessor();
    this.na = new NormalAlphabet();
    this.ed = new EuclideanDistance();
  }

  /**
   * Convert the timeseries into SAX string representation.
   * 
   * @param ts the timeseries.
   * @param paaSize the PAA size.
   * @param cuts the alphabet cuts.
   * @param nThreshold the normalization thresholds.
   * 
   * @return The SAX representation for timeseries.
   * @throws SAXException if error occurs.
   */
  public char[] ts2string(double[] ts, int paaSize, double[] cuts, double nThreshold)
      throws SAXException {

    if (paaSize == ts.length) {
      return tsProcessor.ts2String(tsProcessor.znorm(ts, nThreshold), cuts);
    }
    else {
      // perform PAA conversion
      double[] paa = tsProcessor.paa(tsProcessor.znorm(ts, nThreshold), paaSize);
      return tsProcessor.ts2String(paa, cuts);
    }
  }

  /**
   * Converts the input time series into a SAX data structure via chunking and Z normalization.
   * 
   * @param ts the input data.
   * @param paaSize the PAA size.
   * @param cuts the Alphabet cuts.
   * @param nThreshold the normalization threshold value.
   * 
   * @return SAX representation of the time series.
   * @throws SAXException if error occurs.
   */
  public SAXRecords ts2saxByChunking(double[] ts, int paaSize, double[] cuts, double nThreshold)
      throws SAXException {

    SAXRecords saxFrequencyData = new SAXRecords();

    // Z normalize it
    double[] normalizedTS = tsProcessor.znorm(ts, nThreshold);

    // perform PAA conversion if needed
    double[] paa = tsProcessor.paa(normalizedTS, paaSize);

    // Convert the PAA to a string.
    char[] currentString = tsProcessor.ts2String(paa, cuts);

    // create the datastructure
    for (int i = 0; i < currentString.length; i++) {
      char c = currentString[i];
      int pos = (int) Math.floor(i * ts.length / currentString.length);
      saxFrequencyData.add(String.valueOf(c).toCharArray(), pos);
    }

    return saxFrequencyData;

  }

  /**
   * Converts the input time series into a SAX data structure via sliding window and Z
   * normalization.
   * 
   * @param ts the input data.
   * @param windowSize the sliding window size.
   * @param paaSize the PAA size.
   * @param cuts the Alphabet cuts.
   * @param nThreshold the normalization threshold value.
   * @param strategy the NR strategy.
   * 
   * @return SAX representation of the time series.
   * @throws SAXException if error occurs.
   */
  public SAXRecords ts2saxViaWindow(double[] ts, int windowSize, int paaSize, double[] cuts,
      NumerosityReductionStrategy strategy, double nThreshold) throws SAXException {

    if (windowSize > ts.length) {
      throw new SAXException(
          "Unable to saxify via window, window size is greater than the timeseries length...");
    }

    // the resulting data structure init
    //
    SAXRecords saxFrequencyData = new SAXRecords();

    // scan across the time series extract sub sequences, and convert them to strings
    char[] previousString = null;

    for (int i = 0; i <= ts.length - windowSize; i++) {

      // fix the current subsection
      double[] subSection = Arrays.copyOfRange(ts, i, i + windowSize);

      // Z normalize it
      subSection = tsProcessor.znorm(subSection, nThreshold);

      // perform PAA conversion if needed
      double[] paa = tsProcessor.paa(subSection, paaSize);

      // Convert the PAA to a string.
      char[] currentString = tsProcessor.ts2String(paa, cuts);

      if (null != previousString) {

        if (NumerosityReductionStrategy.EXACT.equals(strategy)
            && Arrays.equals(previousString, currentString)) {
          // NumerosityReduction
          continue;
        }
        else if (NumerosityReductionStrategy.MINDIST.equals(strategy)
            && checkMinDistIsZero(previousString, currentString)) {
          continue;
        }

      }

      previousString = currentString;

      saxFrequencyData.add(currentString, i);
    }

    // ArrayList<Integer> keys = saxFrequencyData.getAllIndices();
    // for (int i : keys) {
    // System.out.println(i + "," + String.valueOf(saxFrequencyData.getByIndex(i).getPayload()));
    // }

    return saxFrequencyData;

  }

  /**
   * Converts the input time series into a SAX data structure via sliding window and Z
   * normalization. The difference between this function and ts2saxViaWindow is that in this
   * function, Z normalization occurs on entire range, rather than the sliding window.
   * 
   * @param ts the input data.
   * @param windowSize the sliding window size.
   * @param paaSize the PAA size.
   * @param cuts the Alphabet cuts.
   * @param nThreshold the normalization threshold value.
   * @param strategy the NR strategy.
   * 
   * @return SAX representation of the time series.
   * @throws SAXException if error occurs.
   */
  public SAXRecords ts2saxViaWindowGlobalZNorm(double[] ts, int windowSize, int paaSize,
      double[] cuts, NumerosityReductionStrategy strategy, double nThreshold) throws SAXException {

    // the resulting data structure init
    //
    SAXRecords saxFrequencyData = new SAXRecords();

    // scan across the time series extract sub sequences, and convert them to strings
    char[] previousString = null;

    // normalize the entire range
    double[] normalizedData = tsProcessor.znorm(ts, nThreshold);

    for (int i = 0; i <= ts.length - windowSize; i++) {

      // get the current subsection
      double[] subSection = Arrays.copyOfRange(normalizedData, i, i + windowSize);

      // perform PAA conversion if needed
      double[] paa = tsProcessor.paa(subSection, paaSize);

      // Convert the PAA to a string.
      char[] currentString = tsProcessor.ts2String(paa, cuts);

      if (null != previousString) {

        if (NumerosityReductionStrategy.EXACT.equals(strategy)
            && Arrays.equals(previousString, currentString)) {
          // NumerosityReduction
          continue;
        }
        else if (NumerosityReductionStrategy.MINDIST.equals(strategy)
            && checkMinDistIsZero(previousString, currentString)) {
          continue;
        }

      }

      previousString = currentString;

      saxFrequencyData.add(currentString, i);
    }

    return saxFrequencyData;

  }

  /**
   * Converts the input time series into a SAX data structure via sliding window and Z
   * normalization.
   * 
   * @param ts the input data.
   * @param windowSize the sliding window size.
   * @param paaSize the PAA size.
   * @param cuts the Alphabet cuts.
   * @param nThreshold the normalization threshold value.
   * @param strategy the NR strategy.
   * @param skips The list of points which shall be skipped during conversion; this feature is
   * particularly important when building a concatenated from pieces time series and junction shall
   * not make it into the grammar.
   * 
   * @return SAX representation of the time series.
   * @throws SAXException if error occurs.
   */
  public SAXRecords ts2saxViaWindowSkipping(double[] ts, int windowSize, int paaSize, double[] cuts,
      NumerosityReductionStrategy strategy, double nThreshold, ArrayList<Integer> skips)
      throws SAXException {

    // the resulting data structure init
    //
    SAXRecords saxFrequencyData = new SAXRecords();

    Collections.sort(skips);
    int cSkipIdx = 0;

    // scan across the time series extract sub sequences, and convert them to strings
    char[] previousString = null;
    boolean skipped = false;

    for (int i = 0; i < ts.length - (windowSize - 1); i++) {

      // skip what need to be skipped
      if (cSkipIdx < skips.size() && i == skips.get(cSkipIdx)) {
        cSkipIdx = cSkipIdx + 1;
        skipped = true;
        continue;
      }

      // fix the current subsection
      double[] subSection = Arrays.copyOfRange(ts, i, i + windowSize);

      // Z normalize it
      subSection = tsProcessor.znorm(subSection, nThreshold);

      // perform PAA conversion if needed
      double[] paa = tsProcessor.paa(subSection, paaSize);

      // Convert the PAA to a string.
      char[] currentString = tsProcessor.ts2String(paa, cuts);

      if (!(skipped) && null != previousString) {

        if (NumerosityReductionStrategy.EXACT.equals(strategy)
            && Arrays.equals(previousString, currentString)) {
          // NumerosityReduction
          continue;
        }
        else if (NumerosityReductionStrategy.MINDIST.equals(strategy)
            && checkMinDistIsZero(previousString, currentString)) {
          continue;
        }

      }

      previousString = currentString;
      if (skipped) {
        skipped = false;
      }

      saxFrequencyData.add(currentString, i);
    }

    return saxFrequencyData;
  }

  /**
   * Compute the distance between the two chars based on the ASCII symbol codes.
   * 
   * @param a The first char.
   * @param b The second char.
   * @return The distance.
   */
  public int charDistance(char a, char b) {
    return Math.abs(Character.getNumericValue(a) - Character.getNumericValue(b));
  }

  /**
   * Compute the distance between the two strings, this function use the numbers associated with
   * ASCII codes, i.e. distance between a and b would be 1.
   * 
   * @param a The first string.
   * @param b The second string.
   * @return The pairwise distance.
   * @throws SAXException if length are differ.
   */
  public int strDistance(char[] a, char[] b) throws SAXException {
    if (a.length == b.length) {
      int distance = 0;
      for (int i = 0; i < a.length; i++) {
        int tDist = Math.abs(Character.getNumericValue(a[i]) - Character.getNumericValue(b[i]));
        distance += tDist;
      }
      return distance;
    }
    else {
      throw new SAXException("Unable to compute SAX distance, string lengths are not equal");
    }
  }

  /**
   * This function implements SAX MINDIST function which uses alphabet based distance matrix.
   * 
   * @param a The SAX string.
   * @param b The SAX string.
   * @param distanceMatrix The distance matrix to use.
   * @param n the time series length (sliding window length).
   * @param w the number of PAA segments.
   * @return distance between strings.
   * @throws SAXException If error occurs.
   */
  public double saxMinDist(char[] a, char[] b, double[][] distanceMatrix, int n, int w)
      throws SAXException {
    if (a.length == b.length) {
      double dist = 0.0D;
      for (int i = 0; i < a.length; i++) {
        if (Character.isLetter(a[i]) && Character.isLetter(b[i])) {
          // ... forms have numeric values from 10 through 35
          int numA = Character.getNumericValue(a[i]) - 10;
          int numB = Character.getNumericValue(b[i]) - 10;
          int maxIdx = distanceMatrix[0].length;
          if (numA > (maxIdx - 1) || numA < 0 || numB > (maxIdx - 1) || numB < 0) {
            throw new SAXException(
                "The character index greater than " + maxIdx + " or less than 0!");
          }
          double localDist = distanceMatrix[numA][numB];
          dist = dist + localDist * localDist;
        }
        else {
          throw new SAXException("Non-literal character found!");
        }
      }
      return Math.sqrt((double) n / (double) w) * Math.sqrt(dist);
    }
    else {
      throw new SAXException("Data arrays lengths are not equal!");
    }
  }

  /**
   * Check for trivial mindist case.
   * 
   * @param a first string.
   * @param b second string.
   * @return true if mindist between strings is zero.
   */
  public boolean checkMinDistIsZero(char[] a, char[] b) {
    for (int i = 0; i < a.length; i++) {
      if (charDistance(a[i], b[i]) > 1) {
        return false;
      }
    }
    return true;
  }

  /**
   * Computes the distance between approximated values and the real TS.
   * 
   * @param ts the timeseries.
   * @param winSize SAX window size.
   * @param paaSize SAX PAA size.
   * @param normThreshold the normalization threshold.
   * @return the distance value.
   * @throws Exception if error occurs.
   */
  public double approximationDistancePAA(double[] ts, int winSize, int paaSize,
      double normThreshold) throws Exception {

    double resDistance = 0d;
    int windowCounter = 0;

    double pointsPerWindow = (double) winSize / (double) paaSize;

    for (int i = 0; i < ts.length - winSize + 1; i++) {

      double[] subseries = Arrays.copyOfRange(ts, i, i + winSize);

      if (tsProcessor.stDev(subseries) > normThreshold) {
        subseries = tsProcessor.znorm(subseries, normThreshold);
      }

      double[] paa = tsProcessor.paa(subseries, paaSize);

      windowCounter++;

      // essentially the distance here is the distance between the segment's
      // PAA value and the real TS value
      //
      double subsequenceDistance = 0.;
      for (int j = 0; j < subseries.length; j++) {

        int paaIdx = (int) Math.floor(((double) j + 0.5) / (double) pointsPerWindow);
        if (paaIdx < 0) {
          paaIdx = 0;
        }
        if (paaIdx > paa.length) {
          paaIdx = paa.length - 1;
        }

        subsequenceDistance = subsequenceDistance + ed.distance(paa[paaIdx], subseries[j]);
      }

      resDistance = resDistance + subsequenceDistance / subseries.length;
    }
    return resDistance / (double) windowCounter;
  }

  /**
   * Computes the distance between approximated values and the real TS.
   * 
   * @param ts the timeseries.
   * @param winSize SAX window size.
   * @param paaSize SAX PAA size.
   * @param alphabetSize SAX alphabet size.
   * @param normThreshold the normalization threshold.
   * @return the distance value.
   * @throws Exception if error occurs.
   */
  public double approximationDistanceAlphabet(double[] ts, int winSize, int paaSize,
      int alphabetSize, double normThreshold) throws Exception {

    double resDistance = 0d;
    int windowCounter = 0;

    double[] centralLines = na.getCentralCuts(alphabetSize);
    double[] cuts = na.getCuts(alphabetSize);

    for (int i = 0; i < ts.length - winSize + 1; i++) {

      double[] subseries = Arrays.copyOfRange(ts, i, i + winSize);
      double subsequenceDistance = 0.;

      if (tsProcessor.stDev(subseries) > normThreshold) {
        subseries = tsProcessor.znorm(subseries, normThreshold);
      }

      double[] paa = tsProcessor.paa(subseries, paaSize);
      int[] leterIndexes = tsProcessor.ts2Index(paa, cuts);

      windowCounter++;

      // essentially the distance here is the distance between the segment's
      // PAA value and the real TS value
      //
      for (int j = 0; j < paa.length; j++) {
        // compute the alphabet central cut line
        int letterIdx = leterIndexes[j];
        double cLine = centralLines[letterIdx];
        subsequenceDistance = subsequenceDistance + ed.distance(cLine, paa[j]);
      }

      resDistance = resDistance + subsequenceDistance / paa.length;
    }

    return resDistance / (double) windowCounter;
  }

  /**
   * Converts a single time-series into map of shingle frequencies.
   * 
   * @param series the time series.
   * @param windowSize the sliding window size.
   * @param paaSize the PAA segments number.
   * @param alphabetSize the alphabet size.
   * @param strategy the numerosity reduction strategy.
   * @param nrThreshold the SAX normalization threshold.
   * @param shingleSize the shingle size.
   * 
   * @return map of shingle frequencies.
   * @throws SAXException if error occurs.
   */
  public Map<String, Integer> ts2Shingles(double[] series, int windowSize, int paaSize,
      int alphabetSize, NumerosityReductionStrategy strategy, double nrThreshold, int shingleSize)
      throws SAXException {

    // build all shingles
    String[] alphabet = new String[alphabetSize];
    for (int i = 0; i < alphabetSize; i++) {
      alphabet[i] = String.valueOf(TSProcessor.ALPHABET[i]);
    }
    String[] allShingles = getAllPermutations(alphabet, shingleSize);

    // result
    HashMap<String, Integer> res = new HashMap<String, Integer>(allShingles.length);
    for (String s : allShingles) {
      res.put(s, 0);
    }

    // discretize
    SAXRecords saxData = ts2saxViaWindow(series, windowSize, paaSize, na.getCuts(alphabetSize),
        strategy, nrThreshold);

    // fill in the counts
    for (SAXRecord sr : saxData) {
      String word = String.valueOf(sr.getPayload());
      int frequency = sr.getIndexes().size();
      for (int i = 0; i <= word.length() - shingleSize; i++) {
        String shingle = word.substring(i, i + shingleSize);
        res.put(shingle, res.get(shingle) + frequency);
      }
    }

    return res;
  }

  /**
   * Get all permutations of the given alphabet of given length.
   * 
   * @param alphabet the alphabet to use.
   * @param wordLength the word length.
   * @return set of permutation.
   */
  public static String[] getAllPermutations(String[] alphabet, int wordLength) {

    // initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int) Math.pow(alphabet.length, wordLength)];

    // lists of length 1 are just the original elements
    if (wordLength == 1)
      return alphabet;
    else {
      // the recursion--get all lists of length 3, length 2, all the way up to 1
      String[] allSublists = getAllPermutations(alphabet, wordLength - 1);

      // append the sublists to each element
      int arrayIndex = 0;

      for (int i = 0; i < alphabet.length; i++) {
        for (int j = 0; j < allSublists.length; j++) {
          // add the newly appended combination to the list
          allLists[arrayIndex] = alphabet[i] + allSublists[j];
          arrayIndex++;
        }
      }

      return allLists;
    }
  }

  /**
   * Generic method to convert the milliseconds into the elapsed time string.
   * 
   * @param start Start timestamp.
   * @param finish End timestamp.
   * @return String representation of the elapsed time.
   */
  public static String timeToString(long start, long finish) {

    long millis = finish - start;

    if (millis < 0) {
      throw new IllegalArgumentException("Duration must be greater than zero!");
    }

    long days = TimeUnit.MILLISECONDS.toDays(millis);
    millis -= TimeUnit.DAYS.toMillis(days);
    long hours = TimeUnit.MILLISECONDS.toHours(millis);
    millis -= TimeUnit.HOURS.toMillis(hours);
    long minutes = TimeUnit.MILLISECONDS.toMinutes(millis);
    millis -= TimeUnit.MINUTES.toMillis(minutes);
    long seconds = TimeUnit.MILLISECONDS.toSeconds(millis);
    millis -= TimeUnit.SECONDS.toMillis(seconds);

    StringBuilder sb = new StringBuilder(64);
    sb.append(days);
    sb.append("d");
    sb.append(hours);
    sb.append("h");
    sb.append(minutes);
    sb.append("m");
    sb.append(seconds);
    sb.append("s");
    sb.append(millis);
    sb.append("ms");

    return sb.toString();

  }
}
 public class TSProcessor {

  private static final Charset DEFAULT_CHARSET = StandardCharsets.UTF_8;

  /** The latin alphabet, lower case letters a-z. */
  public static final char[] ALPHABET = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
      'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };

  // static block - we instantiate the logger
  //
  private static final Logger LOGGER = LoggerFactory.getLogger(TSProcessor.class);

  /**
   * Constructor.
   */
  public TSProcessor() {
    super();
  }

  /**
   * Reads timeseries from a file. Assumes that file has a single double value on every line.
   * Assigned timestamps are the line numbers.
   * 
   * @param filename The file to read from.
   * @param columnIdx The column index.
   * @param sizeLimit The number of lines to read, 0 == all.
   * @return data.
   * @throws IOException if error occurs.
   * @throws SAXException if error occurs.
   */
  public static double[] readFileColumn(String filename, int columnIdx, int sizeLimit)
      throws IOException, SAXException {

    // make sure the path exists
    Path path = Paths.get(filename);
    if (!(Files.exists(path))) {
      throw new SAXException("unable to load data - data source not found.");
    }

    BufferedReader br = new BufferedReader(
        new InputStreamReader(new FileInputStream(filename), "UTF-8"));

    return readTS(br, columnIdx, sizeLimit);
  }

  /**
   * Reads timeseries from a file. Assumes that file has a single double value on every line.
   * Assigned timestamps are the line numbers.
   * 
   * @param br The reader to use.
   * @param columnIdx The column index.
   * @param sizeLimit The number of lines to read, 0 == all.
   * @return data.
   * @throws IOException if error occurs.
   * @throws SAXException if error occurs.
   */
  public static double[] readTS(BufferedReader br, int columnIdx, int sizeLimit)
      throws IOException, SAXException {
    ArrayList<Double> preRes = new ArrayList<Double>();
    int lineCounter = 0;

    String line = null;
    while ((line = br.readLine()) != null) {
      String[] split = line.trim().split("\\s+");
      if (split.length < columnIdx) {
        String message = "Unable to read data from column " + columnIdx;
        br.close();
        throw new SAXException(message);
      }
      String str = split[columnIdx];
      double num = Double.NaN;
      try {
        num = Double.valueOf(str);
      }
      catch (NumberFormatException e) {
        LOGGER.info("Skipping the row " + lineCounter + " with value \"" + str + "\"");
        continue;
      }
      preRes.add(num);
      lineCounter++;
      if ((0 != sizeLimit) && (lineCounter >= sizeLimit)) {
        break;
      }
    }
    br.close();
    double[] res = new double[preRes.size()];
    for (int i = 0; i < preRes.size(); i++) {
      res[i] = preRes.get(i);
    }
    return res;

  }

  /**
   * Read at least N elements from the one-column file.
   * 
   * @param dataFileName the file name.
   * @param loadLimit the load limit.
   * @return the read data or empty array if nothing to load.
   * @throws SAXException if error occurs.
   * @throws IOException if error occurs.
   */
  public double[] readTS(String dataFileName, int loadLimit) throws SAXException, IOException {

    Path path = Paths.get(dataFileName);
    if (!(Files.exists(path))) {
      throw new SAXException("unable to load data - data source not found.");
    }

    BufferedReader reader = Files.newBufferedReader(path, DEFAULT_CHARSET);

    return readTS(reader, 0, loadLimit);

  }

  /**
   * Finds the maximal value in timeseries.
   * 
   * @param series The timeseries.
   * @return The max value.
   */
  public double max(double[] series) {
    double max = Double.MIN_VALUE;
    for (int i = 0; i < series.length; i++) {
      if (max < series[i]) {
        max = series[i];
      }
    }
    return max;
  }

  /**
   * Finds the minimal value in timeseries.
   * 
   * @param series The timeseries.
   * @return The min value.
   */
  public double min(double[] series) {
    double min = Double.MAX_VALUE;
    for (int i = 0; i < series.length; i++) {
      if (min > series[i]) {
        min = series[i];
      }
    }
    return min;
  }

  /**
   * Computes the mean value of timeseries.
   * 
   * @param series The timeseries.
   * @return The mean value.
   */
  public double mean(double[] series) {
    double res = 0D;
    int count = 0;
    for (double tp : series) {
      res += tp;
      count += 1;

    }
    if (count > 0) {
      return res / ((Integer) count).doubleValue();
    }
    return Double.NaN;
  }

  /**
   * Computes the mean value of timeseries.
   * 
   * @param series The timeseries.
   * @return The mean value.
   */
  public double mean(int[] series) {
    double res = 0D;
    int count = 0;
    for (int tp : series) {
      res += (double) tp;
      count += 1;

    }
    if (count > 0) {
      return res / ((Integer) count).doubleValue();
    }
    return Double.NaN;
  }

  /**
   * Computes the median value of timeseries.
   * 
   * @param series The timeseries.
   * @return The median value.
   */
  public double median(double[] series) {
    double[] clonedSeries = series.clone();
    Arrays.sort(clonedSeries);

    double median;
    if (clonedSeries.length % 2 == 0) {
      median = (clonedSeries[clonedSeries.length / 2]
          + (double) clonedSeries[clonedSeries.length / 2 - 1]) / 2;
    }
    else {
      median = clonedSeries[clonedSeries.length / 2];
    }
    return median;
  }

  /**
   * Compute the variance of timeseries.
   * 
   * @param series The timeseries.
   * @return The variance.
   */
  public double var(double[] series) {
    double res = 0D;
    double mean = mean(series);
    int count = 0;
    for (double tp : series) {
      res += (tp - mean) * (tp - mean);
      count += 1;
    }
    if (count > 0) {
      return res / ((Integer) (count - 1)).doubleValue();
    }
    return Double.NaN;
  }

  /**
   * Speed-optimized implementation.
   * 
   * @param series The timeseries.
   * @return the standard deviation.
   */
  public double stDev(double[] series) {
    double num0 = 0D;
    double sum = 0D;
    int count = 0;
    for (double tp : series) {
      num0 = num0 + tp * tp;
      sum = sum + tp;
      count += 1;
    }
    double len = ((Integer) count).doubleValue();
    return Math.sqrt((len * num0 - sum * sum) / (len * (len - 1)));
  }

  /**
   * Z-Normalize routine.
   * 
   * @param series the input timeseries.
   * @param normalizationThreshold the zNormalization threshold value.
   * @return Z-normalized time-series.
   */
  public double[] znorm(double[] series, double normalizationThreshold) {
    double[] res = new double[series.length];
    double sd = stDev(series);
    if (sd < normalizationThreshold) {
      // return series.clone();
      // return array of zeros
      return res;
    }
    double mean = mean(series);
    for (int i = 0; i < res.length; i++) {
      res[i] = (series[i] - mean) / sd;
    }
    return res;
  }

  /**
   * Approximate the timeseries using PAA. If the timeseries has some NaN's they are handled as
   * follows: 1) if all values of the piece are NaNs - the piece is approximated as NaN, 2) if there
   * are some (more or equal one) values happened to be in the piece - algorithm will handle it as
   * usual - getting the mean.
   * 
   * @param ts The timeseries to approximate.
   * @param paaSize The desired length of approximated timeseries.
   * @return PAA-approximated timeseries.
   * @throws SAXException if error occurs.
   * 
   */
  public double[] paa(double[] ts, int paaSize) throws SAXException {
    // fix the length
    int len = ts.length;
    if (len < paaSize) {
      throw new SAXException("PAA size can't be greater than the timeseries size.");
    }
    // check for the trivial case
    if (len == paaSize) {
      return Arrays.copyOf(ts, ts.length);
    }
    else {
      double[] paa = new double[paaSize];
      double pointsPerSegment = (double) len / (double) paaSize;
      double[] breaks = new double[paaSize + 1];
      for (int i = 0; i < paaSize + 1; i++) {
        breaks[i] = i * pointsPerSegment;
      }

      for (int i = 0; i < paaSize; i++) {
        double segStart = breaks[i];
        double segEnd = breaks[i + 1];

        double fractionStart = Math.ceil(segStart) - segStart;
        double fractionEnd = segEnd - Math.floor(segEnd);

        int fullStart = Double.valueOf(Math.floor(segStart)).intValue();
        int fullEnd = Double.valueOf(Math.ceil(segEnd)).intValue();

        double[] segment = Arrays.copyOfRange(ts, fullStart, fullEnd);

        if (fractionStart > 0) {
          segment[0] = segment[0] * fractionStart;
        }

        if (fractionEnd > 0) {
          segment[segment.length - 1] = segment[segment.length - 1] * fractionEnd;
        }

        double elementsSum = 0.0;
        for (double e : segment) {
          elementsSum = elementsSum + e;
        }

        paa[i] = elementsSum / pointsPerSegment;

      }
      return paa;
    }
  }

  /**
   * Converts the timeseries into string using given cuts intervals. Useful for not-normal
   * distribution cuts.
   * 
   * @param vals The timeseries.
   * @param cuts The cut intervals.
   * @return The timeseries SAX representation.
   */
  public char[] ts2String(double[] vals, double[] cuts) {
    char[] res = new char[vals.length];
    for (int i = 0; i < vals.length; i++) {
      res[i] = num2char(vals[i], cuts);
    }
    return res;
  }

  /**
   * Convert the timeseries into the index using SAX cuts.
   * 
   * @param series The timeseries to convert.
   * @param cuts The alphabet cuts.
   * @return SAX cuts indices.
   * @throws Exception if error occurs.
   */
  public int[] ts2Index(double[] series, double[] cuts) throws Exception {
    int[] res = new int[series.length];
    for (int i = 0; i < series.length; i++) {
      res[i] = num2index(series[i], cuts);
    }
    return res;
  }

  /**
   * Get mapping of a number to char.
   * 
   * @param value the value to map.
   * @param cuts the array of intervals.
   * @return character corresponding to numeric value.
   */
  public char num2char(double value, double[] cuts) {
    int idx = 0;
    if (value >= 0) {
      idx = cuts.length;
      while ((idx > 0) && (cuts[idx - 1] > value)) {
        idx--;
      }
    }
    else {
      while ((idx < cuts.length) && (cuts[idx] <= value)) {
        idx++;
      }
    }
    return ALPHABET[idx];
  }

  /**
   * Converts index into char.
   * 
   * @param idx The index value.
   * @return The char by index.
   */
  public char num2char(int idx) {
    return ALPHABET[idx];
  }

  /**
   * Get mapping of number to cut index.
   * 
   * @param value the value to map.
   * @param cuts the array of intervals.
   * @return character corresponding to numeric value.
   */
  public int num2index(double value, double[] cuts) {
    int count = 0;
    while ((count < cuts.length) && (cuts[count] <= value)) {
      count++;
    }
    return count;
  }

  /**
   * Extract subseries out of series.
   * 
   * @param series The series array.
   * @param start the fragment start.
   * @param end the fragment end.
   * @return The subseries.
   * @throws IndexOutOfBoundsException If error occurs.
   */
  public double[] subseriesByCopy(double[] series, int start, int end)
      throws IndexOutOfBoundsException {
    if ((start > end) || (start < 0) || (end > series.length)) {
      throw new IndexOutOfBoundsException("Unable to extract subseries, series length: "
          + series.length + ", start: " + start + ", end: " + String.valueOf(end - start));
    }
    return Arrays.copyOfRange(series, start, end);
  }

  /**
   * Prettyfies the timeseries for screen output.
   * 
   * @param series the data.
   * @param df the number format to use.
   * 
   * @return The timeseries formatted for screen output.
   */
  public String seriesToString(double[] series, NumberFormat df) {
    StringBuffer sb = new StringBuffer();
    sb.append('[');
    for (double d : series) {
      sb.append(df.format(d)).append(',');
    }
    sb.delete(sb.length() - 2, sb.length() - 1).append("]");
    return sb.toString();
  }

  /**
   * Normalizes data in interval 0-1.
   * 
   * @param data the dataset.
   * @return normalized dataset.
   */
  public double[] normOne(double[] data) {
    double[] res = new double[data.length];
    double max = max(data);
    for (int i = 0; i < data.length; i++) {
      res[i] = data[i] / max;
    }
    return res;
  }

}
 public final class NormalAlphabet extends Alphabet {

  /** The latin alphabet, lower case letters a-z. */
  public static final char[] ALPHABET = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
      'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };

  /** Maximal possible alphabet size. */
  private static final int MAX_SIZE = 20;

  // cut intervals
  //
  private static final double[] case2 = { 0 };
  private static final double[] case3 = { -0.4307273, 0.4307273 };
  private static final double[] case4 = { -0.6744898, 0, 0.6744898 };
  private static final double[] case5 = { -0.841621233572914, -0.2533471031358, 0.2533471031358,
      0.841621233572914 };
  private static final double[] case6 = { -0.967421566101701, -0.430727299295457, 0,
      0.430727299295457, 0.967421566101701 };
  private static final double[] case7 = { -1.06757052387814, -0.565948821932863, -0.180012369792705,
      0.180012369792705, 0.565948821932863, 1.06757052387814 };
  private static final double[] case8 = { -1.15034938037601, -0.674489750196082, -0.318639363964375,
      0, 0.318639363964375, 0.674489750196082, 1.15034938037601 };
  private static final double[] case9 = { -1.22064034884735, -0.764709673786387, -0.430727299295457,
      -0.139710298881862, 0.139710298881862, 0.430727299295457, 0.764709673786387,
      1.22064034884735 };
  private static final double[] case10 = { -1.2815515655446, -0.841621233572914, -0.524400512708041,
      -0.2533471031358, 0, 0.2533471031358, 0.524400512708041, 0.841621233572914, 1.2815515655446 };
  private static final double[] case11 = { -1.33517773611894, -0.908457868537385,
      -0.604585346583237, -0.348755695517045, -0.114185294321428, 0.114185294321428,
      0.348755695517045, 0.604585346583237, 0.908457868537385, 1.33517773611894 };
  private static final double[] case12 = { -1.38299412710064, -0.967421566101701,
      -0.674489750196082, -0.430727299295457, -0.210428394247925, 0, 0.210428394247925,
      0.430727299295457, 0.674489750196082, 0.967421566101701, 1.38299412710064 };
  private static final double[] case13 = { -1.42607687227285, -1.0200762327862, -0.736315917376129,
      -0.502402223373355, -0.293381232121193, -0.0965586152896391, 0.0965586152896394,
      0.293381232121194, 0.502402223373355, 0.73631591737613, 1.0200762327862, 1.42607687227285 };
  private static final double[] case14 = { -1.46523379268552, -1.06757052387814, -0.791638607743375,
      -0.565948821932863, -0.36610635680057, -0.180012369792705, 0, 0.180012369792705,
      0.36610635680057, 0.565948821932863, 0.791638607743375, 1.06757052387814, 1.46523379268552 };
  private static final double[] case15 = { -1.50108594604402, -1.11077161663679, -0.841621233572914,
      -0.622925723210088, -0.430727299295457, -0.2533471031358, -0.0836517339071291,
      0.0836517339071291, 0.2533471031358, 0.430727299295457, 0.622925723210088, 0.841621233572914,
      1.11077161663679, 1.50108594604402 };
  private static final double[] case16 = { -1.53412054435255, -1.15034938037601, -0.887146559018876,
      -0.674489750196082, -0.488776411114669, -0.318639363964375, -0.157310684610171, 0,
      0.157310684610171, 0.318639363964375, 0.488776411114669, 0.674489750196082, 0.887146559018876,
      1.15034938037601, 1.53412054435255 };
  private static final double[] case17 = { -1.5647264713618, -1.18683143275582, -0.928899491647271,
      -0.721522283982343, -0.541395085129088, -0.377391943828554, -0.223007830940367,
      -0.0737912738082727, 0.0737912738082727, 0.223007830940367, 0.377391943828554,
      0.541395085129088, 0.721522283982343, 0.928899491647271, 1.18683143275582, 1.5647264713618 };
  private static final double[] case18 = { -1.59321881802305, -1.22064034884735, -0.967421566101701,
      -0.764709673786387, -0.589455797849779, -0.430727299295457, -0.282216147062508,
      -0.139710298881862, 0, 0.139710298881862, 0.282216147062508, 0.430727299295457,
      0.589455797849779, 0.764709673786387, 0.967421566101701, 1.22064034884735, 1.59321881802305 };
  private static final double[] case19 = { -1.61985625863827, -1.25211952026522, -1.00314796766253,
      -0.8045963803603, -0.633640000779701, -0.47950565333095, -0.336038140371823,
      -0.199201324789267, -0.0660118123758407, 0.0660118123758406, 0.199201324789267,
      0.336038140371823, 0.47950565333095, 0.633640000779701, 0.8045963803603, 1.00314796766253,
      1.25211952026522, 1.61985625863827 };
  private static final double[] case20 = { -1.64485362695147, -1.2815515655446, -1.03643338949379,
      -0.841621233572914, -0.674489750196082, -0.524400512708041, -0.385320466407568,
      -0.2533471031358, -0.125661346855074, 0, 0.125661346855074, 0.2533471031358,
      0.385320466407568, 0.524400512708041, 0.674489750196082, 0.841621233572914, 1.03643338949379,
      1.2815515655446, 1.64485362695147 };

  private static final double[][] distance_case2 = { { 0.000000, 0.000000 },
      { 0.000000, 0.000000 } };

  private static final double[][] distance_case3 = { { 0.000000, 0.000000, 0.861455 },
      { 0.000000, 0.000000, 0.000000 }, { 0.861455, 0.000000, 0.000000 } };

  private static final double[][] distance_case4 =

      { { 0.000000, 0.000000, 0.674490, 1.348980 }, { 0.000000, 0.000000, 0.000000, 0.674490 },
          { 0.674490, 0.000000, 0.000000, 0.000000 }, { 1.348980, 0.674490, 0.000000, 0.000000 } };

  private static final double[][] distance_case5 = {
      { 0.000000, 0.000000, 0.588274, 1.094968, 1.683242 },
      { 0.000000, 0.000000, 0.000000, 0.506694, 1.094968 },
      { 0.588274, 0.000000, 0.000000, 0.000000, 0.588274 },
      { 1.094968, 0.506694, 0.000000, 0.000000, 0.000000 },
      { 1.683242, 1.094968, 0.588274, 0.000000, 0.000000 } };

  private static final double[][] distance_case6 = {
      { 0.000000, 0.000000, 0.536694, 0.967422, 1.398149, 1.934843 },
      { 0.000000, 0.000000, 0.000000, 0.430727, 0.861455, 1.398149 },
      { 0.536694, 0.000000, 0.000000, 0.000000, 0.430727, 0.967422 },
      { 0.967422, 0.430727, 0.000000, 0.000000, 0.000000, 0.536694 },
      { 1.398149, 0.861455, 0.430727, 0.000000, 0.000000, 0.000000 },
      { 1.934843, 1.398149, 0.967422, 0.536694, 0.000000, 0.000000 } };

  private static final double[][] distance_case7 = {
      { 0.000000, 0.000000, 0.501622, 0.887558, 1.247583, 1.633519, 2.135141 },
      { 0.000000, 0.000000, 0.000000, 0.385936, 0.745961, 1.131898, 1.633519 },
      { 0.501622, 0.000000, 0.000000, 0.000000, 0.360025, 0.745961, 1.247583 },
      { 0.887558, 0.385936, 0.000000, 0.000000, 0.000000, 0.385936, 0.887558 },
      { 1.247583, 0.745961, 0.360025, 0.000000, 0.000000, 0.000000, 0.501622 },
      { 1.633519, 1.131898, 0.745961, 0.385936, 0.000000, 0.000000, 0.000000 },
      { 2.135141, 1.633519, 1.247583, 0.887558, 0.501622, 0.000000, 0.000000 } };

  private static final double[][] distance_case8 = {
      { 0.000000, 0.000000, 0.475860, 0.831710, 1.150349, 1.468989, 1.824839, 2.300699 },
      { 0.000000, 0.000000, 0.000000, 0.355850, 0.674490, 0.993129, 1.348980, 1.824839 },
      { 0.475860, 0.000000, 0.000000, 0.000000, 0.318639, 0.637279, 0.993129, 1.468989 },
      { 0.831710, 0.355850, 0.000000, 0.000000, 0.000000, 0.318639, 0.674490, 1.150349 },
      { 1.150349, 0.674490, 0.318639, 0.000000, 0.000000, 0.000000, 0.355850, 0.831710 },
      { 1.468989, 0.993129, 0.637279, 0.318639, 0.000000, 0.000000, 0.000000, 0.475860 },
      { 1.824839, 1.348980, 0.993129, 0.674490, 0.355850, 0.000000, 0.000000, 0.000000 },
      { 2.300699, 1.824839, 1.468989, 1.150349, 0.831710, 0.475860, 0.000000, 0.000000 } };

  private static final double[][] distance_case9 = {
      { 0.000000, 0.000000, 0.455931, 0.789913, 1.080930, 1.360351, 1.651368, 1.985350, 2.441281 },
      { 0.000000, 0.000000, 0.000000, 0.333982, 0.624999, 0.904420, 1.195437, 1.529419, 1.985350 },
      { 0.455931, 0.000000, 0.000000, 0.000000, 0.291017, 0.570438, 0.861455, 1.195437, 1.651368 },
      { 0.789913, 0.333982, 0.000000, 0.000000, 0.000000, 0.279421, 0.570438, 0.904420, 1.360351 },
      { 1.080930, 0.624999, 0.291017, 0.000000, 0.000000, 0.000000, 0.291017, 0.624999, 1.080930 },
      { 1.360351, 0.904420, 0.570438, 0.279421, 0.000000, 0.000000, 0.000000, 0.333982, 0.789913 },
      { 1.651368, 1.195437, 0.861455, 0.570438, 0.291017, 0.000000, 0.000000, 0.000000, 0.455931 },
      { 1.985350, 1.529419, 1.195437, 0.904420, 0.624999, 0.333982, 0.000000, 0.000000, 0.000000 },
      { 2.441281, 1.985350, 1.651368, 1.360351, 1.080930, 0.789913, 0.455931, 0.000000,
          0.000000 } };

  private static final double[][] distance_case10 = {
      { 0.000000, 0.000000, 0.439930, 0.757151, 1.028204, 1.281552, 1.534899, 1.805952, 2.123173,
          2.563103 },
      { 0.000000, 0.000000, 0.000000, 0.317221, 0.588274, 0.841621, 1.094968, 1.366022, 1.683242,
          2.123173 },
      { 0.439930, 0.000000, 0.000000, 0.000000, 0.271053, 0.524401, 0.777748, 1.048801, 1.366022,
          1.805952 },
      { 0.757151, 0.317221, 0.000000, 0.000000, 0.000000, 0.253347, 0.506694, 0.777748, 1.094968,
          1.534899 },
      { 1.028204, 0.588274, 0.271053, 0.000000, 0.000000, 0.000000, 0.253347, 0.524401, 0.841621,
          1.281552 },
      { 1.281552, 0.841621, 0.524401, 0.253347, 0.000000, 0.000000, 0.000000, 0.271053, 0.588274,
          1.028204 },
      { 1.534899, 1.094968, 0.777748, 0.506694, 0.253347, 0.000000, 0.000000, 0.000000, 0.317221,
          0.757151 },
      { 1.805952, 1.366022, 1.048801, 0.777748, 0.524401, 0.271053, 0.000000, 0.000000, 0.000000,
          0.439930 },
      { 2.123173, 1.683242, 1.366022, 1.094968, 0.841621, 0.588274, 0.317221, 0.000000, 0.000000,
          0.000000 },
      { 2.563103, 2.123173, 1.805952, 1.534899, 1.281552, 1.028204, 0.757151, 0.439930, 0.000000,
          0.000000 } };

  private static final double[][] distance_case11 = {
      { 0.000000, 0.000000, 0.426720, 0.730592, 0.986422, 1.220992, 1.449363, 1.683933, 1.939763,
          2.243636, 2.670355 },
      { 0.000000, 0.000000, 0.000000, 0.303873, 0.559702, 0.794273, 1.022643, 1.257214, 1.513043,
          1.816916, 2.243636 },
      { 0.426720, 0.000000, 0.000000, 0.000000, 0.255830, 0.490400, 0.718771, 0.953341, 1.209171,
          1.513043, 1.939763 },
      { 0.730592, 0.303873, 0.000000, 0.000000, 0.000000, 0.234570, 0.462941, 0.697511, 0.953341,
          1.257214, 1.683933 },
      { 0.986422, 0.559702, 0.255830, 0.000000, 0.000000, 0.000000, 0.228371, 0.462941, 0.718771,
          1.022643, 1.449363 },
      { 1.220992, 0.794273, 0.490400, 0.234570, 0.000000, 0.000000, 0.000000, 0.234570, 0.490400,
          0.794273, 1.220992 },
      { 1.449363, 1.022643, 0.718771, 0.462941, 0.228371, 0.000000, 0.000000, 0.000000, 0.255830,
          0.559702, 0.986422 },
      { 1.683933, 1.257214, 0.953341, 0.697511, 0.462941, 0.234570, 0.000000, 0.000000, 0.000000,
          0.303873, 0.730592 },
      { 1.939763, 1.513043, 1.209171, 0.953341, 0.718771, 0.490400, 0.255830, 0.000000, 0.000000,
          0.000000, 0.426720 },
      { 2.243636, 1.816916, 1.513043, 1.257214, 1.022643, 0.794273, 0.559702, 0.303873, 0.000000,
          0.000000, 0.000000 },
      { 2.670355, 2.243636, 1.939763, 1.683933, 1.449363, 1.220992, 0.986422, 0.730592, 0.426720,
          0.000000, 0.000000 } };

  private static final double[][] distance_case12 = {
      { 0.000000, 0.000000, 0.415573, 0.708504, 0.952267, 1.172566, 1.382994, 1.593423, 1.813721,
          2.057484, 2.350416, 2.765988 },
      { 0.000000, 0.000000, 0.000000, 0.292932, 0.536694, 0.756993, 0.967422, 1.177850, 1.398149,
          1.641911, 1.934843, 2.350416 },
      { 0.415573, 0.000000, 0.000000, 0.000000, 0.243762, 0.464061, 0.674490, 0.884918, 1.105217,
          1.348980, 1.641911, 2.057484 },
      { 0.708504, 0.292932, 0.000000, 0.000000, 0.000000, 0.220299, 0.430727, 0.641156, 0.861455,
          1.105217, 1.398149, 1.813721 },
      { 0.952267, 0.536694, 0.243762, 0.000000, 0.000000, 0.000000, 0.210428, 0.420857, 0.641156,
          0.884918, 1.177850, 1.593423 },
      { 1.172566, 0.756993, 0.464061, 0.220299, 0.000000, 0.000000, 0.000000, 0.210428, 0.430727,
          0.674490, 0.967422, 1.382994 },
      { 1.382994, 0.967422, 0.674490, 0.430727, 0.210428, 0.000000, 0.000000, 0.000000, 0.220299,
          0.464061, 0.756993, 1.172566 },
      { 1.593423, 1.177850, 0.884918, 0.641156, 0.420857, 0.210428, 0.000000, 0.000000, 0.000000,
          0.243762, 0.536694, 0.952267 },
      { 1.813721, 1.398149, 1.105217, 0.861455, 0.641156, 0.430727, 0.220299, 0.000000, 0.000000,
          0.000000, 0.292932, 0.708504 },
      { 2.057484, 1.641911, 1.348980, 1.105217, 0.884918, 0.674490, 0.464061, 0.243762, 0.000000,
          0.000000, 0.000000, 0.415573 },
      { 2.350416, 1.934843, 1.641911, 1.398149, 1.177850, 0.967422, 0.756993, 0.536694, 0.292932,
          0.000000, 0.000000, 0.000000 },
      { 2.765988, 2.350416, 2.057484, 1.813721, 1.593423, 1.382994, 1.172566, 0.952267, 0.708504,
          0.415573, 0.000000, 0.000000 } };

  private static final double[][] distance_case13 = {
      { 0.000000, 0.000000, 0.406001, 0.689761, 0.923675, 1.132696, 1.329518, 1.522635, 1.719458,
          1.928479, 2.162393, 2.446153, 2.852154 },
      { 0.000000, 0.000000, 0.000000, 0.283760, 0.517674, 0.726695, 0.923518, 1.116635, 1.313457,
          1.522478, 1.756392, 2.040152, 2.446153 },
      { 0.406001, 0.000000, 0.000000, 0.000000, 0.233914, 0.442935, 0.639757, 0.832875, 1.029697,
          1.238718, 1.472632, 1.756392, 2.162393 },
      { 0.689761, 0.283760, 0.000000, 0.000000, 0.000000, 0.209021, 0.405844, 0.598961, 0.795783,
          1.004804, 1.238718, 1.522478, 1.928479 },
      { 0.923675, 0.517674, 0.233914, 0.000000, 0.000000, 0.000000, 0.196823, 0.389940, 0.586762,
          0.795783, 1.029697, 1.313457, 1.719458 },
      { 1.132696, 0.726695, 0.442935, 0.209021, 0.000000, 0.000000, 0.000000, 0.193117, 0.389940,
          0.598961, 0.832875, 1.116635, 1.522635 },
      { 1.329518, 0.923518, 0.639757, 0.405844, 0.196823, 0.000000, 0.000000, 0.000000, 0.196823,
          0.405844, 0.639757, 0.923518, 1.329518 },
      { 1.522635, 1.116635, 0.832875, 0.598961, 0.389940, 0.193117, 0.000000, 0.000000, 0.000000,
          0.209021, 0.442935, 0.726695, 1.132696 },
      { 1.719458, 1.313457, 1.029697, 0.795783, 0.586762, 0.389940, 0.196823, 0.000000, 0.000000,
          0.000000, 0.233914, 0.517674, 0.923675 },
      { 1.928479, 1.522478, 1.238718, 1.004804, 0.795783, 0.598961, 0.405844, 0.209021, 0.000000,
          0.000000, 0.000000, 0.283760, 0.689761 },
      { 2.162393, 1.756392, 1.472632, 1.238718, 1.029697, 0.832875, 0.639757, 0.442935, 0.233914,
          0.000000, 0.000000, 0.000000, 0.406001 },
      { 2.446153, 2.040152, 1.756392, 1.522478, 1.313457, 1.116635, 0.923518, 0.726695, 0.517674,
          0.283760, 0.000000, 0.000000, 0.000000 },
      { 2.852154, 2.446153, 2.162393, 1.928479, 1.719458, 1.522635, 1.329518, 1.132696, 0.923675,
          0.689761, 0.406001, 0.000000, 0.000000 } };

  private static final double[][] distance_case14 = {
      { 0.000000, 0.000000, 0.397663, 0.673595, 0.899285, 1.099127, 1.285221, 1.465234, 1.645246,
          1.831340, 2.031183, 2.256872, 2.532804, 2.930468 },
      { 0.000000, 0.000000, 0.000000, 0.275932, 0.501622, 0.701464, 0.887558, 1.067571, 1.247583,
          1.433677, 1.633519, 1.859209, 2.135141, 2.532804 },
      { 0.397663, 0.000000, 0.000000, 0.000000, 0.225690, 0.425532, 0.611626, 0.791639, 0.971651,
          1.157745, 1.357587, 1.583277, 1.859209, 2.256872 },
      { 0.673595, 0.275932, 0.000000, 0.000000, 0.000000, 0.199842, 0.385936, 0.565949, 0.745961,
          0.932055, 1.131898, 1.357587, 1.633519, 2.031183 },
      { 0.899285, 0.501622, 0.225690, 0.000000, 0.000000, 0.000000, 0.186094, 0.366106, 0.546119,
          0.732213, 0.932055, 1.157745, 1.433677, 1.831340 },
      { 1.099127, 0.701464, 0.425532, 0.199842, 0.000000, 0.000000, 0.000000, 0.180012, 0.360025,
          0.546119, 0.745961, 0.971651, 1.247583, 1.645246 },
      { 1.285221, 0.887558, 0.611626, 0.385936, 0.186094, 0.000000, 0.000000, 0.000000, 0.180012,
          0.366106, 0.565949, 0.791639, 1.067571, 1.465234 },
      { 1.465234, 1.067571, 0.791639, 0.565949, 0.366106, 0.180012, 0.000000, 0.000000, 0.000000,
          0.186094, 0.385936, 0.611626, 0.887558, 1.285221 },
      { 1.645246, 1.247583, 0.971651, 0.745961, 0.546119, 0.360025, 0.180012, 0.000000, 0.000000,
          0.000000, 0.199842, 0.425532, 0.701464, 1.099127 },
      { 1.831340, 1.433677, 1.157745, 0.932055, 0.732213, 0.546119, 0.366106, 0.186094, 0.000000,
          0.000000, 0.000000, 0.225690, 0.501622, 0.899285 },
      { 2.031183, 1.633519, 1.357587, 1.131898, 0.932055, 0.745961, 0.565949, 0.385936, 0.199842,
          0.000000, 0.000000, 0.000000, 0.275932, 0.673595 },
      { 2.256872, 1.859209, 1.583277, 1.357587, 1.157745, 0.971651, 0.791639, 0.611626, 0.425532,
          0.225690, 0.000000, 0.000000, 0.000000, 0.397663 },
      { 2.532804, 2.135141, 1.859209, 1.633519, 1.433677, 1.247583, 1.067571, 0.887558, 0.701464,
          0.501622, 0.275932, 0.000000, 0.000000, 0.000000 },
      { 2.930468, 2.532804, 2.256872, 2.031183, 1.831340, 1.645246, 1.465234, 1.285221, 1.099127,
          0.899285, 0.673595, 0.397663, 0.000000, 0.000000 } };

  private static final double[][] distance_case15 = {
      { 0.000000, 0.000000, 0.390314, 0.659465, 0.878160, 1.070359, 1.247739, 1.417434, 1.584738,
          1.754433, 1.931813, 2.124012, 2.342707, 2.611858, 3.002172 },
      { 0.000000, 0.000000, 0.000000, 0.269150, 0.487846, 0.680044, 0.857425, 1.027120, 1.194423,
          1.364119, 1.541499, 1.733697, 1.952393, 2.221543, 2.611858 },
      { 0.390314, 0.000000, 0.000000, 0.000000, 0.218696, 0.410894, 0.588274, 0.757969, 0.925273,
          1.094968, 1.272349, 1.464547, 1.683242, 1.952393, 2.342707 },
      { 0.659465, 0.269150, 0.000000, 0.000000, 0.000000, 0.192198, 0.369579, 0.539274, 0.706577,
          0.876273, 1.053653, 1.245851, 1.464547, 1.733697, 2.124012 },
      { 0.878160, 0.487846, 0.218696, 0.000000, 0.000000, 0.000000, 0.177380, 0.347076, 0.514379,
          0.684074, 0.861455, 1.053653, 1.272349, 1.541499, 1.931813 },
      { 1.070359, 0.680044, 0.410894, 0.192198, 0.000000, 0.000000, 0.000000, 0.169695, 0.336999,
          0.506694, 0.684074, 0.876273, 1.094968, 1.364119, 1.754433 },
      { 1.247739, 0.857425, 0.588274, 0.369579, 0.177380, 0.000000, 0.000000, 0.000000, 0.167303,
          0.336999, 0.514379, 0.706577, 0.925273, 1.194423, 1.584738 },
      { 1.417434, 1.027120, 0.757969, 0.539274, 0.347076, 0.169695, 0.000000, 0.000000, 0.000000,
          0.169695, 0.347076, 0.539274, 0.757969, 1.027120, 1.417434 },
      { 1.584738, 1.194423, 0.925273, 0.706577, 0.514379, 0.336999, 0.167303, 0.000000, 0.000000,
          0.000000, 0.177380, 0.369579, 0.588274, 0.857425, 1.247739 },
      { 1.754433, 1.364119, 1.094968, 0.876273, 0.684074, 0.506694, 0.336999, 0.169695, 0.000000,
          0.000000, 0.000000, 0.192198, 0.410894, 0.680044, 1.070359 },
      { 1.931813, 1.541499, 1.272349, 1.053653, 0.861455, 0.684074, 0.514379, 0.347076, 0.177380,
          0.000000, 0.000000, 0.000000, 0.218696, 0.487846, 0.878160 },
      { 2.124012, 1.733697, 1.464547, 1.245851, 1.053653, 0.876273, 0.706577, 0.539274, 0.369579,
          0.192198, 0.000000, 0.000000, 0.000000, 0.269150, 0.659465 },
      { 2.342707, 1.952393, 1.683242, 1.464547, 1.272349, 1.094968, 0.925273, 0.757969, 0.588274,
          0.410894, 0.218696, 0.000000, 0.000000, 0.000000, 0.390314 },
      { 2.611858, 2.221543, 1.952393, 1.733697, 1.541499, 1.364119, 1.194423, 1.027120, 0.857425,
          0.680044, 0.487846, 0.269150, 0.000000, 0.000000, 0.000000 },
      { 3.002172, 2.611858, 2.342707, 2.124012, 1.931813, 1.754433, 1.584738, 1.417434, 1.247739,
          1.070359, 0.878160, 0.659465, 0.390314, 0.000000, 0.000000 } };

  private static final double[][] distance_case16 = {
      { 0.000000, 0.000000, 0.383771, 0.646974, 0.859631, 1.045344, 1.215481, 1.376810, 1.534121,
          1.691431, 1.852760, 2.022897, 2.208610, 2.421267, 2.684470, 3.068241 },
      { 0.000000, 0.000000, 0.000000, 0.263203, 0.475860, 0.661573, 0.831710, 0.993039, 1.150349,
          1.307660, 1.468989, 1.639126, 1.824839, 2.037496, 2.300699, 2.684470 },
      { 0.383771, 0.000000, 0.000000, 0.000000, 0.212657, 0.398370, 0.568507, 0.729836, 0.887147,
          1.044457, 1.205786, 1.375923, 1.561636, 1.774293, 2.037496, 2.421267 },
      { 0.646974, 0.263203, 0.000000, 0.000000, 0.000000, 0.185713, 0.355850, 0.517179, 0.674490,
          0.831800, 0.993129, 1.163266, 1.348980, 1.561636, 1.824839, 2.208610 },
      { 0.859631, 0.475860, 0.212657, 0.000000, 0.000000, 0.000000, 0.170137, 0.331466, 0.488776,
          0.646087, 0.807416, 0.977553, 1.163266, 1.375923, 1.639126, 2.022897 },
      { 1.045344, 0.661573, 0.398370, 0.185713, 0.000000, 0.000000, 0.000000, 0.161329, 0.318639,
          0.475950, 0.637279, 0.807416, 0.993129, 1.205786, 1.468989, 1.852760 },
      { 1.215481, 0.831710, 0.568507, 0.355850, 0.170137, 0.000000, 0.000000, 0.000000, 0.157311,
          0.314621, 0.475950, 0.646087, 0.831800, 1.044457, 1.307660, 1.691431 },
      { 1.376810, 0.993039, 0.729836, 0.517179, 0.331466, 0.161329, 0.000000, 0.000000, 0.000000,
          0.157311, 0.318639, 0.488776, 0.674490, 0.887147, 1.150349, 1.534121 },
      { 1.534121, 1.150349, 0.887147, 0.674490, 0.488776, 0.318639, 0.157311, 0.000000, 0.000000,
          0.000000, 0.161329, 0.331466, 0.517179, 0.729836, 0.993039, 1.376810 },
      { 1.691431, 1.307660, 1.044457, 0.831800, 0.646087, 0.475950, 0.314621, 0.157311, 0.000000,
          0.000000, 0.000000, 0.170137, 0.355850, 0.568507, 0.831710, 1.215481 },
      { 1.852760, 1.468989, 1.205786, 0.993129, 0.807416, 0.637279, 0.475950, 0.318639, 0.161329,
          0.000000, 0.000000, 0.000000, 0.185713, 0.398370, 0.661573, 1.045344 },
      { 2.022897, 1.639126, 1.375923, 1.163266, 0.977553, 0.807416, 0.646087, 0.488776, 0.331466,
          0.170137, 0.000000, 0.000000, 0.000000, 0.212657, 0.475860, 0.859631 },
      { 2.208610, 1.824839, 1.561636, 1.348980, 1.163266, 0.993129, 0.831800, 0.674490, 0.517179,
          0.355850, 0.185713, 0.000000, 0.000000, 0.000000, 0.263203, 0.646974 },
      { 2.421267, 2.037496, 1.774293, 1.561636, 1.375923, 1.205786, 1.044457, 0.887147, 0.729836,
          0.568507, 0.398370, 0.212657, 0.000000, 0.000000, 0.000000, 0.383771 },
      { 2.684470, 2.300699, 2.037496, 1.824839, 1.639126, 1.468989, 1.307660, 1.150349, 0.993039,
          0.831710, 0.661573, 0.475860, 0.263203, 0.000000, 0.000000, 0.000000 },
      { 3.068241, 2.684470, 2.421267, 2.208610, 2.022897, 1.852760, 1.691431, 1.534121, 1.376810,
          1.215481, 1.045344, 0.859631, 0.646974, 0.383771, 0.000000, 0.000000 } };

  private static final double[][] distance_case17 = {
      { 0.000000, 0.000000, 0.377895, 0.635827, 0.843204, 1.023331, 1.187335, 1.341719, 1.490935,
          1.638518, 1.787734, 1.942118, 2.106122, 2.286249, 2.493626, 2.751558, 3.129453 },
      { 0.000000, 0.000000, 0.000000, 0.257932, 0.465309, 0.645436, 0.809439, 0.963824, 1.113040,
          1.260623, 1.409839, 1.564223, 1.728227, 1.908354, 2.115731, 2.373663, 2.751558 },
      { 0.377895, 0.000000, 0.000000, 0.000000, 0.207377, 0.387504, 0.551508, 0.705892, 0.855108,
          1.002691, 1.151907, 1.306291, 1.470295, 1.650422, 1.857799, 2.115731, 2.493626 },
      { 0.635827, 0.257932, 0.000000, 0.000000, 0.000000, 0.180127, 0.344130, 0.498514, 0.647731,
          0.795314, 0.944530, 1.098914, 1.262917, 1.443045, 1.650422, 1.908354, 2.286249 },
      { 0.843204, 0.465309, 0.207377, 0.000000, 0.000000, 0.000000, 0.164003, 0.318387, 0.467604,
          0.615186, 0.764403, 0.918787, 1.082790, 1.262917, 1.470295, 1.728227, 2.106122 },
      { 1.023331, 0.645436, 0.387504, 0.180127, 0.000000, 0.000000, 0.000000, 0.154384, 0.303601,
          0.451183, 0.600400, 0.754784, 0.918787, 1.098914, 1.306291, 1.564223, 1.942118 },
      { 1.187335, 0.809439, 0.551508, 0.344130, 0.164003, 0.000000, 0.000000, 0.000000, 0.149217,
          0.296799, 0.446016, 0.600400, 0.764403, 0.944530, 1.151907, 1.409839, 1.787734 },
      { 1.341719, 0.963824, 0.705892, 0.498514, 0.318387, 0.154384, 0.000000, 0.000000, 0.000000,
          0.147583, 0.296799, 0.451183, 0.615186, 0.795314, 1.002691, 1.260623, 1.638518 },
      { 1.490935, 1.113040, 0.855108, 0.647731, 0.467604, 0.303601, 0.149217, 0.000000, 0.000000,
          0.000000, 0.149217, 0.303601, 0.467604, 0.647731, 0.855108, 1.113040, 1.490935 },
      { 1.638518, 1.260623, 1.002691, 0.795314, 0.615186, 0.451183, 0.296799, 0.147583, 0.000000,
          0.000000, 0.000000, 0.154384, 0.318387, 0.498514, 0.705892, 0.963824, 1.341719 },
      { 1.787734, 1.409839, 1.151907, 0.944530, 0.764403, 0.600400, 0.446016, 0.296799, 0.149217,
          0.000000, 0.000000, 0.000000, 0.164003, 0.344130, 0.551508, 0.809439, 1.187335 },
      { 1.942118, 1.564223, 1.306291, 1.098914, 0.918787, 0.754784, 0.600400, 0.451183, 0.303601,
          0.154384, 0.000000, 0.000000, 0.000000, 0.180127, 0.387504, 0.645436, 1.023331 },
      { 2.106122, 1.728227, 1.470295, 1.262917, 1.082790, 0.918787, 0.764403, 0.615186, 0.467604,
          0.318387, 0.164003, 0.000000, 0.000000, 0.000000, 0.207377, 0.465309, 0.843204 },
      { 2.286249, 1.908354, 1.650422, 1.443045, 1.262917, 1.098914, 0.944530, 0.795314, 0.647731,
          0.498514, 0.344130, 0.180127, 0.000000, 0.000000, 0.000000, 0.257932, 0.635827 },
      { 2.493626, 2.115731, 1.857799, 1.650422, 1.470295, 1.306291, 1.151907, 1.002691, 0.855108,
          0.705892, 0.551508, 0.387504, 0.207377, 0.000000, 0.000000, 0.000000, 0.377895 },
      { 2.751558, 2.373663, 2.115731, 1.908354, 1.728227, 1.564223, 1.409839, 1.260623, 1.113040,
          0.963824, 0.809439, 0.645436, 0.465309, 0.257932, 0.000000, 0.000000, 0.000000 },
      { 3.129453, 2.751558, 2.493626, 2.286249, 2.106122, 1.942118, 1.787734, 1.638518, 1.490935,
          1.341719, 1.187335, 1.023331, 0.843204, 0.635827, 0.377895, 0.000000, 0.000000 } };

  private static final double[][] distance_case18 = {
      { 0.000000, 0.000000, 0.372578, 0.625797, 0.828509, 1.003763, 1.162492, 1.311003, 1.453509,
          1.593219, 1.732929, 1.875435, 2.023946, 2.182675, 2.357928, 2.560640, 2.813859,
          3.186438 },
      { 0.000000, 0.000000, 0.000000, 0.253219, 0.455931, 0.631185, 0.789913, 0.938424, 1.080930,
          1.220640, 1.360351, 1.502856, 1.651368, 1.810096, 1.985350, 2.188062, 2.441281,
          2.813859 },
      { 0.372578, 0.000000, 0.000000, 0.000000, 0.202712, 0.377966, 0.536694, 0.685205, 0.827711,
          0.967422, 1.107132, 1.249638, 1.398149, 1.556877, 1.732131, 1.934843, 2.188062,
          2.560640 },
      { 0.625797, 0.253219, 0.000000, 0.000000, 0.000000, 0.175254, 0.333982, 0.482494, 0.624999,
          0.764710, 0.904420, 1.046926, 1.195437, 1.354165, 1.529419, 1.732131, 1.985350,
          2.357928 },
      { 0.828509, 0.455931, 0.202712, 0.000000, 0.000000, 0.000000, 0.158728, 0.307240, 0.449745,
          0.589456, 0.729166, 0.871672, 1.020183, 1.178912, 1.354165, 1.556877, 1.810096,
          2.182675 },
      { 1.003763, 0.631185, 0.377966, 0.175254, 0.000000, 0.000000, 0.000000, 0.148511, 0.291017,
          0.430727, 0.570438, 0.712943, 0.861455, 1.020183, 1.195437, 1.398149, 1.651368,
          2.023946 },
      { 1.162492, 0.789913, 0.536694, 0.333982, 0.158728, 0.000000, 0.000000, 0.000000, 0.142506,
          0.282216, 0.421926, 0.564432, 0.712943, 0.871672, 1.046926, 1.249638, 1.502856,
          1.875435 },
      { 1.311003, 0.938424, 0.685205, 0.482494, 0.307240, 0.148511, 0.000000, 0.000000, 0.000000,
          0.139710, 0.279421, 0.421926, 0.570438, 0.729166, 0.904420, 1.107132, 1.360351,
          1.732929 },
      { 1.453509, 1.080930, 0.827711, 0.624999, 0.449745, 0.291017, 0.142506, 0.000000, 0.000000,
          0.000000, 0.139710, 0.282216, 0.430727, 0.589456, 0.764710, 0.967422, 1.220640,
          1.593219 },
      { 1.593219, 1.220640, 0.967422, 0.764710, 0.589456, 0.430727, 0.282216, 0.139710, 0.000000,
          0.000000, 0.000000, 0.142506, 0.291017, 0.449745, 0.624999, 0.827711, 1.080930,
          1.453509 },
      { 1.732929, 1.360351, 1.107132, 0.904420, 0.729166, 0.570438, 0.421926, 0.279421, 0.139710,
          0.000000, 0.000000, 0.000000, 0.148511, 0.307240, 0.482494, 0.685205, 0.938424,
          1.311003 },
      { 1.875435, 1.502856, 1.249638, 1.046926, 0.871672, 0.712943, 0.564432, 0.421926, 0.282216,
          0.142506, 0.000000, 0.000000, 0.000000, 0.158728, 0.333982, 0.536694, 0.789913,
          1.162492 },
      { 2.023946, 1.651368, 1.398149, 1.195437, 1.020183, 0.861455, 0.712943, 0.570438, 0.430727,
          0.291017, 0.148511, 0.000000, 0.000000, 0.000000, 0.175254, 0.377966, 0.631185,
          1.003763 },
      { 2.182675, 1.810096, 1.556877, 1.354165, 1.178912, 1.020183, 0.871672, 0.729166, 0.589456,
          0.449745, 0.307240, 0.158728, 0.000000, 0.000000, 0.000000, 0.202712, 0.455931,
          0.828509 },
      { 2.357928, 1.985350, 1.732131, 1.529419, 1.354165, 1.195437, 1.046926, 0.904420, 0.764710,
          0.624999, 0.482494, 0.333982, 0.175254, 0.000000, 0.000000, 0.000000, 0.253219,
          0.625797 },
      { 2.560640, 2.188062, 1.934843, 1.732131, 1.556877, 1.398149, 1.249638, 1.107132, 0.967422,
          0.827711, 0.685205, 0.536694, 0.377966, 0.202712, 0.000000, 0.000000, 0.000000,
          0.372578 },
      { 2.813859, 2.441281, 2.188062, 1.985350, 1.810096, 1.651368, 1.502856, 1.360351, 1.220640,
          1.080930, 0.938424, 0.789913, 0.631185, 0.455931, 0.253219, 0.000000, 0.000000,
          0.000000 },
      { 3.186438, 2.813859, 2.560640, 2.357928, 2.182675, 2.023946, 1.875435, 1.732929, 1.593219,
          1.453509, 1.311003, 1.162492, 1.003763, 0.828509, 0.625797, 0.372578, 0.000000,
          0.000000 } };

  private static final double[][] distance_case19 = {
      { 0.000000, 0.000000, 0.367737, 0.616708, 0.815260, 0.986216, 1.140351, 1.283818, 1.420655,
          1.553844, 1.685868, 1.819058, 1.955894, 2.099362, 2.253496, 2.424453, 2.623004, 2.871976,
          3.239713 },
      { 0.000000, 0.000000, 0.000000, 0.248972, 0.447523, 0.618480, 0.772614, 0.916081, 1.052918,
          1.186108, 1.318131, 1.451321, 1.588158, 1.731625, 1.885760, 2.056716, 2.255267, 2.504239,
          2.871976 },
      { 0.367737, 0.000000, 0.000000, 0.000000, 0.198552, 0.369508, 0.523642, 0.667110, 0.803947,
          0.937136, 1.069160, 1.202349, 1.339186, 1.482654, 1.636788, 1.807744, 2.006296, 2.255267,
          2.623004 },
      { 0.616708, 0.248972, 0.000000, 0.000000, 0.000000, 0.170956, 0.325091, 0.468558, 0.605395,
          0.738585, 0.870608, 1.003798, 1.140635, 1.284102, 1.438236, 1.609193, 1.807744, 2.056716,
          2.424453 },
      { 0.815260, 0.447523, 0.198552, 0.000000, 0.000000, 0.000000, 0.154134, 0.297602, 0.434439,
          0.567628, 0.699652, 0.832841, 0.969678, 1.113146, 1.267280, 1.438236, 1.636788, 1.885760,
          2.253496 },
      { 0.986216, 0.618480, 0.369508, 0.170956, 0.000000, 0.000000, 0.000000, 0.143468, 0.280304,
          0.413494, 0.545517, 0.678707, 0.815544, 0.959011, 1.113146, 1.284102, 1.482654, 1.731625,
          2.099362 },
      { 1.140351, 0.772614, 0.523642, 0.325091, 0.154134, 0.000000, 0.000000, 0.000000, 0.136837,
          0.270026, 0.402050, 0.535239, 0.672076, 0.815544, 0.969678, 1.140635, 1.339186, 1.588158,
          1.955894 },
      { 1.283818, 0.916081, 0.667110, 0.468558, 0.297602, 0.143468, 0.000000, 0.000000, 0.000000,
          0.133190, 0.265213, 0.398403, 0.535239, 0.678707, 0.832841, 1.003798, 1.202349, 1.451321,
          1.819058 },
      { 1.420655, 1.052918, 0.803947, 0.605395, 0.434439, 0.280304, 0.136837, 0.000000, 0.000000,
          0.000000, 0.132024, 0.265213, 0.402050, 0.545517, 0.699652, 0.870608, 1.069160, 1.318131,
          1.685868 },
      { 1.553844, 1.186108, 0.937136, 0.738585, 0.567628, 0.413494, 0.270026, 0.133190, 0.000000,
          0.000000, 0.000000, 0.133190, 0.270026, 0.413494, 0.567628, 0.738585, 0.937136, 1.186108,
          1.553844 },
      { 1.685868, 1.318131, 1.069160, 0.870608, 0.699652, 0.545517, 0.402050, 0.265213, 0.132024,
          0.000000, 0.000000, 0.000000, 0.136837, 0.280304, 0.434439, 0.605395, 0.803947, 1.052918,
          1.420655 },
      { 1.819058, 1.451321, 1.202349, 1.003798, 0.832841, 0.678707, 0.535239, 0.398403, 0.265213,
          0.133190, 0.000000, 0.000000, 0.000000, 0.143468, 0.297602, 0.468558, 0.667110, 0.916081,
          1.283818 },
      { 1.955894, 1.588158, 1.339186, 1.140635, 0.969678, 0.815544, 0.672076, 0.535239, 0.402050,
          0.270026, 0.136837, 0.000000, 0.000000, 0.000000, 0.154134, 0.325091, 0.523642, 0.772614,
          1.140351 },
      { 2.099362, 1.731625, 1.482654, 1.284102, 1.113146, 0.959011, 0.815544, 0.678707, 0.545517,
          0.413494, 0.280304, 0.143468, 0.000000, 0.000000, 0.000000, 0.170956, 0.369508, 0.618480,
          0.986216 },
      { 2.253496, 1.885760, 1.636788, 1.438236, 1.267280, 1.113146, 0.969678, 0.832841, 0.699652,
          0.567628, 0.434439, 0.297602, 0.154134, 0.000000, 0.000000, 0.000000, 0.198552, 0.447523,
          0.815260 },
      { 2.424453, 2.056716, 1.807744, 1.609193, 1.438236, 1.284102, 1.140635, 1.003798, 0.870608,
          0.738585, 0.605395, 0.468558, 0.325091, 0.170956, 0.000000, 0.000000, 0.000000, 0.248972,
          0.616708 },
      { 2.623004, 2.255267, 2.006296, 1.807744, 1.636788, 1.482654, 1.339186, 1.202349, 1.069160,
          0.937136, 0.803947, 0.667110, 0.523642, 0.369508, 0.198552, 0.000000, 0.000000, 0.000000,
          0.367737 },
      { 2.871976, 2.504239, 2.255267, 2.056716, 1.885760, 1.731625, 1.588158, 1.451321, 1.318131,
          1.186108, 1.052918, 0.916081, 0.772614, 0.618480, 0.447523, 0.248972, 0.000000, 0.000000,
          0.000000 },
      { 3.239713, 2.871976, 2.623004, 2.424453, 2.253496, 2.099362, 1.955894, 1.819058, 1.685868,
          1.553844, 1.420655, 1.283818, 1.140351, 0.986216, 0.815260, 0.616708, 0.367737, 0.000000,
          0.000000 } };

  private static final double[][] distance_case20 = {
      { 0.000000, 0.000000, 0.363302, 0.608420, 0.803232, 0.970364, 1.120453, 1.259533, 1.391507,
          1.519192, 1.644854, 1.770515, 1.898201, 2.030174, 2.169254, 2.319343, 2.486475, 2.681287,
          2.926405, 3.289707 },
      { 0.000000, 0.000000, 0.000000, 0.245118, 0.439930, 0.607062, 0.757151, 0.896231, 1.028204,
          1.155890, 1.281552, 1.407213, 1.534899, 1.666872, 1.805952, 1.956041, 2.123173, 2.317985,
          2.563103, 2.926405 },
      { 0.363302, 0.000000, 0.000000, 0.000000, 0.194812, 0.361944, 0.512033, 0.651113, 0.783086,
          0.910772, 1.036433, 1.162095, 1.289780, 1.421754, 1.560834, 1.710923, 1.878055, 2.072867,
          2.317985, 2.681287 },
      { 0.608420, 0.245118, 0.000000, 0.000000, 0.000000, 0.167131, 0.317221, 0.456301, 0.588274,
          0.715960, 0.841621, 0.967283, 1.094968, 1.226942, 1.366022, 1.516111, 1.683242, 1.878055,
          2.123173, 2.486475 },
      { 0.803232, 0.439930, 0.194812, 0.000000, 0.000000, 0.000000, 0.150089, 0.289169, 0.421143,
          0.548828, 0.674490, 0.800151, 0.927837, 1.059810, 1.198890, 1.348980, 1.516111, 1.710923,
          1.956041, 2.319343 },
      { 0.970364, 0.607062, 0.361944, 0.167131, 0.000000, 0.000000, 0.000000, 0.139080, 0.271053,
          0.398739, 0.524401, 0.650062, 0.777748, 0.909721, 1.048801, 1.198890, 1.366022, 1.560834,
          1.805952, 2.169254 },
      { 1.120453, 0.757151, 0.512033, 0.317221, 0.150089, 0.000000, 0.000000, 0.000000, 0.131973,
          0.259659, 0.385320, 0.510982, 0.638668, 0.770641, 0.909721, 1.059810, 1.226942, 1.421754,
          1.666872, 2.030174 },
      { 1.259533, 0.896231, 0.651113, 0.456301, 0.289169, 0.139080, 0.000000, 0.000000, 0.000000,
          0.127686, 0.253347, 0.379008, 0.506694, 0.638668, 0.777748, 0.927837, 1.094968, 1.289780,
          1.534899, 1.898201 },
      { 1.391507, 1.028204, 0.783086, 0.588274, 0.421143, 0.271053, 0.131973, 0.000000, 0.000000,
          0.000000, 0.125661, 0.251323, 0.379008, 0.510982, 0.650062, 0.800151, 0.967283, 1.162095,
          1.407213, 1.770515 },
      { 1.519192, 1.155890, 0.910772, 0.715960, 0.548828, 0.398739, 0.259659, 0.127686, 0.000000,
          0.000000, 0.000000, 0.125661, 0.253347, 0.385320, 0.524401, 0.674490, 0.841621, 1.036433,
          1.281552, 1.644854 },
      { 1.644854, 1.281552, 1.036433, 0.841621, 0.674490, 0.524401, 0.385320, 0.253347, 0.125661,
          0.000000, 0.000000, 0.000000, 0.127686, 0.259659, 0.398739, 0.548828, 0.715960, 0.910772,
          1.155890, 1.519192 },
      { 1.770515, 1.407213, 1.162095, 0.967283, 0.800151, 0.650062, 0.510982, 0.379008, 0.251323,
          0.125661, 0.000000, 0.000000, 0.000000, 0.131973, 0.271053, 0.421143, 0.588274, 0.783086,
          1.028204, 1.391507 },
      { 1.898201, 1.534899, 1.289780, 1.094968, 0.927837, 0.777748, 0.638668, 0.506694, 0.379008,
          0.253347, 0.127686, 0.000000, 0.000000, 0.000000, 0.139080, 0.289169, 0.456301, 0.651113,
          0.896231, 1.259533 },
      { 2.030174, 1.666872, 1.421754, 1.226942, 1.059810, 0.909721, 0.770641, 0.638668, 0.510982,
          0.385320, 0.259659, 0.131973, 0.000000, 0.000000, 0.000000, 0.150089, 0.317221, 0.512033,
          0.757151, 1.120453 },
      { 2.169254, 1.805952, 1.560834, 1.366022, 1.198890, 1.048801, 0.909721, 0.777748, 0.650062,
          0.524401, 0.398739, 0.271053, 0.139080, 0.000000, 0.000000, 0.000000, 0.167131, 0.361944,
          0.607062, 0.970364 },
      { 2.319343, 1.956041, 1.710923, 1.516111, 1.348980, 1.198890, 1.059810, 0.927837, 0.800151,
          0.674490, 0.548828, 0.421143, 0.289169, 0.150089, 0.000000, 0.000000, 0.000000, 0.194812,
          0.439930, 0.803232 },
      { 2.486475, 2.123173, 1.878055, 1.683242, 1.516111, 1.366022, 1.226942, 1.094968, 0.967283,
          0.841621, 0.715960, 0.588274, 0.456301, 0.317221, 0.167131, 0.000000, 0.000000, 0.000000,
          0.245118, 0.608420 },
      { 2.681287, 2.317985, 2.072867, 1.878055, 1.710923, 1.560834, 1.421754, 1.289780, 1.162095,
          1.036433, 0.910772, 0.783086, 0.651113, 0.512033, 0.361944, 0.194812, 0.000000, 0.000000,
          0.000000, 0.363302 },
      { 2.926405, 2.563103, 2.317985, 2.123173, 1.956041, 1.805952, 1.666872, 1.534899, 1.407213,
          1.281552, 1.155890, 1.028204, 0.896231, 0.757151, 0.607062, 0.439930, 0.245118, 0.000000,
          0.000000, 0.000000 },
      { 3.289707, 2.926405, 2.681287, 2.486475, 2.319343, 2.169254, 2.030174, 1.898201, 1.770515,
          1.644854, 1.519192, 1.391507, 1.259533, 1.120453, 0.970364, 0.803232, 0.608420, 0.363302,
          0.000000, 0.000000 } };

  //
  // central cuts
  //
  //
  private static final double[] center_case2 = { -0.674489750196082, 0.674489750196082 };
  private static final double[] center_case3 = { -0.967421566101701, 0, 0.967421566101701 };
  private static final double[] center_case4 = { -1.15034938037601, -0.318639363964375,
      0.318639363964375, 1.15034938037601 };
  private static final double[] center_case5 = { -1.2815515655446, -0.524400512708041,
      2.78291642467177e-16, 0.524400512708041, 1.2815515655446 };
  private static final double[] center_case6 = { -1.38299412710064, -0.674489750196082,
      -0.210428394247925, 0.210428394247925, 0.674489750196081, 1.38299412710064 };
  private static final double[] center_case7 = { -1.46523379268552, -0.791638607743375,
      -0.36610635680057, 0, 0.36610635680057, 0.791638607743375, 1.46523379268552 };
  private static final double[] center_case8 = { -1.53412054435255, -0.887146559018876,
      -0.488776411114669, -0.157310684610171, 0.157310684610171, 0.488776411114669,
      0.887146559018876, 1.53412054435255 };
  private static final double[] center_case9 = { -1.59321881802305, -0.967421566101701,
      -0.589455797849779, -0.282216147062508, 0, 0.282216147062508, 0.589455797849778,
      0.967421566101701, 1.59321881802305 };
  private static final double[] center_case10 = { -1.64485362695147, -1.03643338949379,
      -0.674489750196082, -0.385320466407568, -0.125661346855074, 0.125661346855074,
      0.385320466407568, 0.674489750196082, 1.03643338949379, 1.64485362695147 };
  private static final double[] center_case11 = { -1.6906216295849, -1.09680356209351,
      -0.747858594763302, -0.472789120992267, -0.229884117579232, -1.39145821233588e-16,
      0.229884117579232, 0.472789120992267, 0.747858594763303, 1.09680356209351, 1.6906216295849 };
  private static final double[] center_case12 = { -1.73166439612225, -1.15034938037601,
      -0.812217801499913, -0.548522282698098, -0.318639363964375, -0.104633455614075,
      0.104633455614075, 0.318639363964375, 0.548522282698098, 0.812217801499913, 1.15034938037601,
      1.73166439612225 };
  private static final double[] center_case13 = { -1.76882503851871, -1.19837970230692,
      -0.869423773288886, -0.615141104595973, -0.395725295814487, -0.194028142423926,
      2.78291642467177e-16, 0.194028142423926, 0.395725295814487, 0.615141104595974,
      0.869423773288887, 1.19837970230692, 1.76882503851871 };
  private static final double[] center_case14 = { -1.80274309073919, -1.24186679184332,
      -0.920822976368379, -0.674489750196082, -0.463707751457179, -0.271880005399261,
      -0.0896423510757625, 0.0896423510757625, 0.271880005399261, 0.463707751457179,
      0.674489750196082, 0.920822976368379, 1.24186679184332, 1.80274309073919 };
  private static final double[] center_case15 = { -1.83391463581591, -1.2815515655446,
      -0.967421566101701, -0.727913290881644, -0.524400512708041, -0.340694827087795,
      -0.167894004788105, 0, 0.167894004788105, 0.340694827087795, 0.524400512708041,
      0.727913290881644, 0.967421566101701, 1.2815515655446, 1.83391463581591 };
  private static final double[] center_case16 = { -1.86273186742165, -1.31801089730354,
      -1.00999016924958, -0.776421761147928, -0.579132162255556, -0.402250065321725,
      -0.237202109328788, -0.0784124127331122, 0.0784124127331122, 0.237202109328788,
      0.402250065321725, 0.579132162255556, 0.776421761147928, 1.00999016924958, 1.31801089730354,
      1.86273186742165 };
  private static final double[] center_case17 = { -1.88950996033343, -1.35170223993066,
      -1.04913139796397, -0.82079208833238, -0.62890421763219, -0.457851931012495,
      -0.299306910465667, -0.147987109725839, 0, 0.147987109725839, 0.299306910465667,
      0.457851931012495, 0.62890421763219, 0.82079208833238, 1.04913139796397, 1.35170223993066,
      1.88950996033343 };
  private static final double[] center_case18 = { -1.91450582505556, -1.38299412710064,
      -1.08532490807676, -0.861634120174172, -0.674489750196082, -0.508488059109357,
      -0.355490417839531, -0.210428394247925, -0.0696849203184557, 0.0696849203184557,
      0.210428394247925, 0.355490417839531, 0.508488059109357, 0.674489750196081, 0.861634120174172,
      1.08532490807676, 1.38299412710064, 1.91450582505556 };
  private static final double[] center_case19 = { -1.93793151085283, -1.41218757890616,
      -1.11895838106256, -0.899434907667234, -0.716497500177991, -0.554922942702654,
      -0.406724251871364, -0.266994125404953, -0.132312852276171, 0, 0.132312852276171,
      0.266994125404953, 0.406724251871363, 0.554922942702654, 0.716497500177991, 0.899434907667234,
      1.11895838106256, 1.41218757890616, 1.93793151085283 };
  private static final double[] center_case20 = { -1.95996398454005, -1.43953147093846,
      -1.15034938037601, -0.93458929107348, -0.755415026360469, -0.597760126042478,
      -0.453762190169879, -0.318639363964375, -0.189118426272792, -0.0627067779432138,
      0.0627067779432138, 0.189118426272793, 0.318639363964375, 0.45376219016988, 0.597760126042478,
      0.755415026360469, 0.93458929107348, 1.15034938037601, 1.43953147093846, 1.95996398454005 };

  /**
   * Constructor.
   */
  public NormalAlphabet() {
    super();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public double[] getCuts(Integer size) throws SAXException {
    switch (size) {
    case 2:
      return case2;
    case 3:
      return case3;
    case 4:
      return case4;
    case 5:
      return case5;
    case 6:
      return case6;
    case 7:
      return case7;
    case 8:
      return case8;
    case 9:
      return case9;
    case 10:
      return case10;
    case 11:
      return case11;
    case 12:
      return case12;
    case 13:
      return case13;
    case 14:
      return case14;
    case 15:
      return case15;
    case 16:
      return case16;
    case 17:
      return case17;
    case 18:
      return case18;
    case 19:
      return case19;
    case 20:
      return case20;
    default:
      throw new SAXException("Invalid alphabet size.");
    }
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public Integer getMaxSize() {
    return MAX_SIZE;
  }

  @Override
  public double[][] getDistanceMatrix(Integer size) throws SAXException {
    switch (size) {
    case 2:
      return distance_case2;
    case 3:
      return distance_case3;
    case 4:
      return distance_case4;
    case 5:
      return distance_case5;
    case 6:
      return distance_case6;
    case 7:
      return distance_case7;
    case 8:
      return distance_case8;
    case 9:
      return distance_case9;
    case 10:
      return distance_case10;
    case 11:
      return distance_case11;
    case 12:
      return distance_case12;
    case 13:
      return distance_case13;
    case 14:
      return distance_case14;
    case 15:
      return distance_case15;
    case 16:
      return distance_case16;
    case 17:
      return distance_case17;
    case 18:
      return distance_case18;
    case 19:
      return distance_case19;
    case 20:
      return distance_case20;
    default:
      throw new SAXException("Invalid alphabet size.");
    }
  }

  /**
   * Produces central cut intervals lines for the normal distribution.
   * 
   * @param size the Alphabet size [2 - 20].
   * @return an array of central lines for the specified alphabet size.
   * @throws SAXException if error occurs.
   */
  public double[] getCentralCuts(Integer size) throws SAXException {
    switch (size) {
    case 2:
      return center_case2;
    case 3:
      return center_case3;
    case 4:
      return center_case4;
    case 5:
      return center_case5;
    case 6:
      return center_case6;
    case 7:
      return center_case7;
    case 8:
      return center_case8;
    case 9:
      return center_case9;
    case 10:
      return center_case10;
    case 11:
      return center_case11;
    case 12:
      return center_case12;
    case 13:
      return center_case13;
    case 14:
      return center_case14;
    case 15:
      return center_case15;
    case 16:
      return center_case16;
    case 17:
      return center_case17;
    case 18:
      return center_case18;
    case 19:
      return center_case19;
    case 20:
      return center_case20;
    default:
      throw new SAXException("Invalid alphabet size.");
    }
  }

}
 public class FrequencyTableEntry implements Comparable<FrequencyTableEntry> {

  private int position;
  private char[] payload;
  private int frequency;

  /**
   * Constructor.
   * 
   * @param len the length of the string.
   * @param pos the occurrence position.
   */
  public FrequencyTableEntry(int len, int pos) {
    this.payload = new char[len];
    this.frequency = -1;
    this.position = pos;
  }

  /**
   * Constructor.
   * 
   * @param position the original entry position.
   * @param payload the payload string.
   * @param frequency the frequency.
   */
  public FrequencyTableEntry(Integer position, char[] payload, int frequency) {
    this.position = position;
    this.payload = payload;
    this.frequency = frequency;
  }

  /**
   * Get a string payload.
   * 
   * @return a string payload.
   */
  public char[] getStr() {
    char[] res = new char[this.payload.length];
    for (int i = 0; i < res.length; i++) {
      res[i] = this.payload[i];
    }
    return res;
  }

  /**
   * Set a string payload.
   * 
   * @param str the string payload.
   */
  public void setStr(char[] str) {
    this.payload = Arrays.copyOf(str, str.length);
  }

  /**
   * Get the observed frequency of the word.
   * 
   * @return the observed frequency of the word.
   */
  public int getFrequency() {
    return frequency;
  }

  /**
   * Set the observed frequency of the word.
   * 
   * @param frequency The frequency to set.
   */
  public void setFrequency(int frequency) {
    this.frequency = frequency;
  }

  /**
   * Get the position of the word.
   * 
   * @return the position of the word.
   */
  public int getPosition() {
    return position;
  }

  /**
   * Set the position of the word.
   * 
   * @param position The position to set.
   */
  public void setPosition(int position) {
    this.position = position;
  }

  /**
   * Check the complexity of the string.
   * 
   * @param complexity If 1 - single letter used, 2 - two or more letters, 3 - 3 or more etc..
   * 
   * @return Returns true if complexity conditions are met.
   */
  public boolean isTrivial(Integer complexity) {
    int len = payload.length;
    if ((null == complexity) || (len < 2)) {
      return true;
    }
    else if ((complexity.intValue() > 0) && (len > 2)) {
      Set<Character> seen = new TreeSet<Character>();
      for (int i = 0; i < len; i++) {
        Character c = Character.valueOf(this.payload[i]);
        if (seen.contains(c)) {
          continue;
        }
        else {
          seen.add(c);
        }
      }
      if (complexity.intValue() <= seen.size()) {
        return false;
      }
    }
    return true;
  }

  @Override
  public int compareTo(FrequencyTableEntry arg0) {
    if (null == arg0) {
      throw new NullPointerException("Unable to compare with a null object.");
    }
    if (this.frequency > arg0.getFrequency()) {
      return 1;
    }
    else if (this.frequency < arg0.getFrequency()) {
      return -1;
    }
    return 0;
  }

  /*
   * (non-Javadoc)
   * 
   * @see java.lang.Object#hashCode()
   */
  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + frequency;
    result = prime * result + Arrays.hashCode(payload);
    return result;
  }

  /*
   * (non-Javadoc)
   * 
   * @see java.lang.Object#equals(java.lang.Object)
   */
  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    FrequencyTableEntry other = (FrequencyTableEntry) obj;
    if (frequency != other.frequency) {
      return false;
    }
    if (!Arrays.equals(payload, other.payload)) {
      return false;
    }
    return true;
  }

  /**
   * {@inheritDoc}
   */
  public String toString() {
    return "payload: " + String.valueOf(this.payload) + ", frequency: " + this.frequency
        + ", location: " + this.position;
  }

  /**
   * Makes the instance copy.
   * 
   * @return the object copy (a "clone").
   */
  public FrequencyTableEntry copy() {
    FrequencyTableEntry res = new FrequencyTableEntry(this.position, this.payload, this.frequency);
    return res;
  }

} public class SAXRecord implements Comparable<SAXRecord> {

  /** The payload. */
  private char[] saxString;

  /** The index of occurrences in the raw sequence. */
  private HashSet<Integer> occurrences;

  /** Disable the constructor. */
  @SuppressWarnings("unused")
  private SAXRecord() {
    super();
  }

  /**
   * The allowed constructor.
   * 
   * @param str the payload value.
   * @param idx the occurrence index.
   */
  public SAXRecord(char[] str, int idx) {
    super();
    this.saxString = str.clone();
    this.occurrences = new HashSet<Integer>();
    this.addIndex(idx);
  }

  /**
   * Adds an index.
   * 
   * @param idx The index to add.
   */
  public void addIndex(int idx) {
    // if (!(this.occurrences.contains(idx))) {
    this.occurrences.add(idx);
    // }
  }

  /**
   * Removes a single index.
   * 
   * @param idx The index to remove.
   */
  public void removeIndex(Integer idx) {
    this.occurrences.remove(idx);
  }

  /**
   * Gets the payload of the structure.
   * 
   * @return The string.
   */
  public char[] getPayload() {
    return this.saxString;
  }

  /**
   * Get all indexes.
   * 
   * @return all indexes.
   */
  public Set<Integer> getIndexes() {
    return this.occurrences;
  }

  /**
   * This comparator compares entries by the length of the entries array - i.e. by the total
   * frequency of entry occurrence.
   * 
   * @param o an entry to compare with.
   * @return results of comparison.
   */
  @Override
  public int compareTo(SAXRecord o) {
    int a = this.occurrences.size();
    int b = o.getIndexes().size();
    if (a == b) {
      return 0;
    }
    else if (a > b) {
      return 1;
    }
    return -1;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public boolean equals(Object o) {
    if (o instanceof SAXRecord) {
      SAXRecord other = (SAXRecord) o;
      if (Arrays.equals(other.getPayload(), this.saxString)
          && (other.getIndexes().size() == this.occurrences.size())) {
        for (Integer e : this.occurrences) {
          if (!other.getIndexes().contains(e)) {
            return false;
          }
        }
        return true;
      }
    }
    return false;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public int hashCode() {
    int hash = 7;
    int num0 = 0;
    if (null == this.saxString || 0 == this.saxString.length) {
      num0 = 32;
    }
    else {
      for (int i = 0; i < this.saxString.length; i++) {
        num0 = num0 + Character.getNumericValue(this.saxString[i]);
      }
    }

    int num1 = 0;
    if (this.occurrences.isEmpty()) {
      num1 = 17;
    }
    else {
      for (Integer i : this.occurrences) {
        num1 = num1 + i;
      }
    }

    hash = num0 + hash * num1;
    return hash;
  }

  @Override
  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append(this.saxString).append(" -> ").append(occurrences.toString());
    return sb.toString();
  }

} public class SAXRecords implements Iterable<SAXRecord> {

  private static final Object CR = "\n";

  /** The id is used to identify the chunk. */
  private final long id;

  /** All the SAX records. */
  private final HashMap<String, SAXRecord> records;

  /** The index of occurrences, key is the position in the time series. */
  private final HashMap<Integer, SAXRecord> realTSindex;

  /** The mapping from SAX string positions to real time series positions. */
  private HashMap<Integer, Integer> stringPosToRealPos;

  /**
   * Constructor. The structure id will be set as System.currentTimeMillis().
   */
  public SAXRecords() {
    super();
    this.id = System.currentTimeMillis();
    this.records = new HashMap<String, SAXRecord>();
    this.realTSindex = new HashMap<Integer, SAXRecord>();
  }

  /**
   * The recommended constructor.
   * 
   * @param id The structure id.
   */
  public SAXRecords(long id) {
    super();
    this.id = id;
    this.records = new HashMap<String, SAXRecord>();
    this.realTSindex = new HashMap<Integer, SAXRecord>();
  }

  /**
   * Get the id.
   * 
   * @return the id.
   */
  public long getId() {
    return this.id;
  }

  /**
   * Returns an iterator which is backed by a hash map with no guarantee for ordering.
   * 
   * @return an iterator.
   */
  @Override
  public Iterator<SAXRecord> iterator() {
    return this.records.values().iterator();
  }

  /**
   * Gets an entry by the index.
   * 
   * @param idx The index.
   * @return The entry.
   */
  public SAXRecord getByIndex(int idx) {
    return realTSindex.get(idx);
  }

  /**
   * Get a SAX record by the string key.
   * 
   * @param str The query string.
   * @return the record if exists.
   */
  public SAXRecord getByWord(String str) {
    return records.get(str);
  }

  /**
   * Drops a single entry.
   * 
   * @param idx the index.
   */
  public void dropByIndex(int idx) {
    SAXRecord entry = realTSindex.get(idx);
    if (null != entry) {
      realTSindex.remove(idx);
      entry.removeIndex(idx);
      if (entry.getIndexes().isEmpty()) {
        records.remove(String.valueOf(entry.getPayload()));
      }
    }
  }

  /**
   * Adds a single string and index entry by creating a SAXRecord.
   * 
   * @param str The string.
   * @param idx The index.
   */
  public void add(char[] str, int idx) {
    SAXRecord rr = records.get(String.valueOf(str));
    if (null == rr) {
      rr = new SAXRecord(str, idx);
      this.records.put(String.valueOf(str), rr);
    }
    else {
      rr.addIndex(idx);
    }
    this.realTSindex.put(idx, rr);
  }

  /**
   * Adds all entries from the collection.
   * 
   * @param records The collection.
   */
  public void addAll(SAXRecords records) {
    for (SAXRecord record : records) {
      char[] payload = record.getPayload();
      for (Integer i : record.getIndexes()) {
        this.add(payload, i);
      }
    }
  }

  /**
   * This adds all to the internal store. Used by the parallel SAX conversion engine.
   * 
   * @param records the data to add.
   */
  public void addAll(HashMap<Integer, char[]> records) {
    for (Entry<Integer, char[]> e : records.entrySet()) {
      this.add(e.getValue(), e.getKey());
    }
  }

  /**
   * Finds the minimal index value.
   * 
   * @return the minimal index value.
   */
  public int getMinIndex() {
    return Collections.min(this.realTSindex.keySet());
  }

  /**
   * Finds the maximal index value.
   * 
   * @return the maximal index value.
   */
  public int getMaxIndex() {
    return Collections.max(this.realTSindex.keySet());
  }

  /**
   * Get the collection size in indexes.
   * 
   * @return the collection size in indexes.
   */
  public int size() {
    return this.realTSindex.size();
  }

  /**
   * Get all the indexes.
   * 
   * @return all the indexes.
   */
  public Set<Integer> getIndexes() {
    return this.realTSindex.keySet();
  }

  /**
   * Get the SAX string of this whole collection.
   * 
   * @param separatorToken The separator token to use for the string.
   * 
   * @return The whole data as a string.
   */
  public String getSAXString(String separatorToken) {
    StringBuffer sb = new StringBuffer();
    ArrayList<Integer> index = new ArrayList<Integer>();
    index.addAll(this.realTSindex.keySet());
    Collections.sort(index, new Comparator<Integer>() {
      public int compare(Integer int1, Integer int2) {
        return int1.compareTo(int2);
      }
    });
    for (int i : index) {
      sb.append(this.realTSindex.get(i).getPayload()).append(separatorToken);
    }
    return sb.toString();
  }

  /**
   * Get all indexes, sorted.
   * 
   * @return all the indexes.
   */
  public ArrayList<Integer> getAllIndices() {
    ArrayList<Integer> res = new ArrayList<Integer>(this.realTSindex.size());
    res.addAll(this.realTSindex.keySet());
    Collections.sort(res);
    return res;
  }

  /**
   * This builds an index that aids in mapping of a SAX word to the real timeseries index.
   */
  public void buildIndex() {
    this.stringPosToRealPos = new HashMap<Integer, Integer>();
    int counter = 0;
    for (Integer idx : getAllIndices()) {
      this.stringPosToRealPos.put(counter, idx);
      counter++;
    }
  }

  /**
   * This maps an index of the word in the output string to the real position in time-series.
   * 
   * @param idx the index to map.
   * @return the position in the time-series.
   */
  public Integer mapStringIndexToTSPosition(int idx) {
    return this.stringPosToRealPos.get(idx);
  }

  /**
   * Removes saxRecord occurrences that correspond to these positions.
   * 
   * @param positions The positions to clear.
   */
  public void excludePositions(ArrayList<Integer> positions) {
    for (Integer p : positions) {
      if (realTSindex.containsKey(p)) {
        SAXRecord rec = realTSindex.get(p);
        rec.removeIndex(p);
        if (rec.getIndexes().isEmpty()) {
          this.records.remove(String.valueOf(rec.getPayload()));
        }
        realTSindex.remove(p);
      }
    }
  }

  /**
   * Get motifs.
   * 
   * @param num how many motifs to report.
   * @return the array of motif SAXRecords.
   */
  public ArrayList<SAXRecord> getSimpleMotifs(int num) {
    ArrayList<SAXRecord> res = new ArrayList<SAXRecord>(num);
    DoublyLinkedSortedList<Entry<String, SAXRecord>> list = new DoublyLinkedSortedList<Entry<String, SAXRecord>>(
        num, new Comparator<Entry<String, SAXRecord>>() {
          @Override
          public int compare(Entry<String, SAXRecord> o1, Entry<String, SAXRecord> o2) {
            int f1 = o1.getValue().getIndexes().size();
            int f2 = o2.getValue().getIndexes().size();
            return Integer.compare(f1, f2);
          }
        });
    for (Entry<String, SAXRecord> e : this.records.entrySet()) {
      list.addElement(e);
    }
    Iterator<Entry<String, SAXRecord>> i = list.iterator();
    while (i.hasNext()) {
      res.add(i.next().getValue());
    }
    return res;
  }

  /**
   * Get access to records.
   * 
   * @return records.
   */
  public Collection<SAXRecord> getRecords() {
    return this.records.values();
  }

  @Override
  public String toString() {
    ArrayList<String> words = new ArrayList<String>(records.keySet().size());
    words.addAll(records.keySet());
    Collections.sort(words);
    StringBuffer sb = new StringBuffer(records.keySet().size() * 256);
    for (String w : words) {
      sb.append(records.get(w)).append(CR);
    }
    return sb.toString();
  }

} public class MagicArrayEntry implements Comparable<MagicArrayEntry> {

  protected String word;
  protected int freq;

  public MagicArrayEntry(String payload, int frequency) {
    this.word = payload;
    this.freq = frequency;
  }

  @Override
  public int compareTo(MagicArrayEntry arg0) {
    if (arg0 == null) {
      throw new NullPointerException("Unable to compare with a null object.");
    }
    if (this.freq > arg0.freq) {
      return 1;
    }
    else if (this.freq < arg0.freq) {
      return -1;
    }
    return 0;
  }

  public String getStr() {
    return this.word;
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + freq;
    result = prime * result + ((word == null) ? 0 : word.hashCode());
    return result;
  }

  @Override
  public boolean equals(Object obj) {
    if (this == obj)
      return true;
    if (obj == null)
      return false;
    if (getClass() != obj.getClass())
      return false;
    MagicArrayEntry other = (MagicArrayEntry) obj;
    if (freq != other.freq)
      return false;
    if (word == null) {
      if (other.word != null)
        return false;
    }
    else if (!word.equals(other.word))
      return false;
    return true;
  }

} public interface SlidingWindowMarkerAlgorithm {

  /**
   * Marks visited locations (of the magic array).
   * 
   * @param registry The magic array instance.
   * @param startPosition The position to start labeling from.
   * @param intervalLength The length of the interval to be labeled.
   */
  void markVisited(VisitRegistry registry, int startPosition, int intervalLength);

} public class VisitRegistry implements Cloneable {

  private static final byte ZERO = 0;
  private static final byte ONE = 1;

  protected byte[] registry; // 1 visited, 0 unvisited

  private int unvisitedCount; // unvisited counter

  private final Random randomizer = new Random(System.currentTimeMillis());

  /**
   * Constructor.
   * 
   * @param capacity The initial capacity.
   */
  public VisitRegistry(int capacity) {
    super();
    this.registry = new byte[capacity];
    this.unvisitedCount = capacity;
  }

  /**
   * Disabling the default constructor.
   */
  @SuppressWarnings("unused")
  private VisitRegistry() {
    super();
  }

  /**
   * Marks location visited. If it was unvisited, counter decremented.
   * 
   * @param loc The location to mark.
   */
  public void markVisited(int loc) {
    if (checkBounds(loc)) {
      if (ZERO == this.registry[loc]) {
        this.unvisitedCount--;
      }
      this.registry[loc] = ONE;
    }
    else {
      throw new RuntimeException(
          "The location " + loc + " out of bounds [0," + (this.registry.length - 1) + "]");
    }
  }

  /**
   * Marks as visited a range of locations.
   * 
   * @param from the start of labeling (inclusive).
   * @param upTo the end of labeling (exclusive).
   */
  public void markVisited(int from, int upTo) {
    if (checkBounds(from) && checkBounds(upTo - 1)) {
      for (int i = from; i < upTo; i++) {
        this.markVisited(i);
      }
    }
    else {
      throw new RuntimeException("The location " + from + "," + upTo + " out of bounds [0,"
          + (this.registry.length - 1) + "]");
    }
  }

  /**
   * Get the next random unvisited position.
   * 
   * @return The next unvisited position.
   */
  public int getNextRandomUnvisitedPosition() {

    // if all are visited, return -1
    //
    if (0 == this.unvisitedCount) {
      return -1;
    }

    // if there is space continue with random sampling
    //
    int i = this.randomizer.nextInt(this.registry.length);
    while (ONE == registry[i]) {
      i = this.randomizer.nextInt(this.registry.length);
    }
    return i;
  }

  /**
   * Check if position is not visited.
   * 
   * @param loc The index.
   * @return true if not visited.
   */
  public boolean isNotVisited(int loc) {
    if (checkBounds(loc)) {
      return (ZERO == this.registry[loc]);
    }
    else {
      throw new RuntimeException(
          "The location " + loc + " out of bounds [0," + (this.registry.length - 1) + "]");
    }
  }

  /**
   * Check if the interval and its boundaries were visited.
   * 
   * @param from The interval start (inclusive).
   * @param upTo The interval end (exclusive).
   * @return True if visited.
   */
  public boolean isVisited(int from, int upTo) {
    if (checkBounds(from) && checkBounds(upTo - 1)) {
      // perform the visit check
      //
      for (int i = from; i < upTo; i++) {
        if (ONE == this.registry[i]) {
          return true;
        }
      }
      return false;
    }
    else {
      throw new RuntimeException("The location " + from + "," + upTo + " out of bounds [0,"
          + (this.registry.length - 1) + "]");
    }
  }

  /**
   * Check if the location specified is visited.
   * 
   * @param loc the location.
   * @return true if visited
   */
  public boolean isVisited(int loc) {
    if (checkBounds(loc)) {
      return (ONE == this.registry[loc]);
    }
    else {
      throw new RuntimeException(
          "The location " + loc + " out of bounds [0," + (this.registry.length - 1) + "]");
    }

  }

  /**
   * Get the list of unvisited positions.
   * 
   * @return list of unvisited positions.
   */
  public ArrayList<Integer> getUnvisited() {
    if (0 == this.unvisitedCount) {
      return new ArrayList<Integer>();
    }
    ArrayList<Integer> res = new ArrayList<Integer>(this.unvisitedCount);
    for (int i = 0; i < this.registry.length; i++) {
      if (ZERO == this.registry[i]) {
        res.add(i);
      }
    }
    return res;
  }

  /**
   * Get the list of visited positions. Returns NULL if none are visited.
   * 
   * @return list of visited positions.
   */
  public ArrayList<Integer> getVisited() {
    if (0 == (this.registry.length - this.unvisitedCount)) {
      return new ArrayList<Integer>();
    }
    ArrayList<Integer> res = new ArrayList<Integer>(this.registry.length - this.unvisitedCount);
    for (int i = 0; i < this.registry.length; i++) {
      if (ONE == this.registry[i]) {
        res.add(i);
      }
    }
    return res;
  }

  /**
   * Transfers all visited entries from another registry to current.
   * 
   * @param discordRegistry The discords registry to copy from.
   */
  public void transferVisited(VisitRegistry discordRegistry) {
    for (int v : discordRegistry.getVisited()) {
      this.markVisited(v);
    }
  }

  /**
   * Creates the copy of a registry.
   * 
   * @return the complete copy.
   * @throws CloneNotSupportedException if error occurs.
   */
  public VisitRegistry clone() throws CloneNotSupportedException {
    VisitRegistry res = (VisitRegistry) super.clone();
    res.unvisitedCount = this.unvisitedCount;
    res.registry = Arrays.copyOfRange(this.registry, 0, this.registry.length);
    return res;
  }

  /**
   * The registry size.
   * 
   * @return the registry size.
   */
  public int size() {
    return this.registry.length;
  }

  /**
   * Check the bounds.
   * 
   * @param pos the pos to check.
   * @return true if within the bounds.
   */
  private boolean checkBounds(int pos) {
    if (pos < 0 || pos >= this.registry.length) {
      return false;
    }
    return true;
  }

  public int getUnvisitedCount() {
    return this.unvisitedCount;
  }

}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import org.slf4j.LoggerFactory;
import ch.qos.logback.classic.Level;
import ch.qos.logback.classic.Logger;
import net.seninp.jmotif.distance.EuclideanDistance;
import net.seninp.jmotif.sax.NumerosityReductionStrategy;
import net.seninp.jmotif.sax.SAXProcessor;
import net.seninp.jmotif.sax.TSProcessor;
import net.seninp.jmotif.sax.alphabet.NormalAlphabet;
import net.seninp.jmotif.sax.datastructure.FrequencyTableEntry;
import net.seninp.jmotif.sax.datastructure.SAXRecord;
import net.seninp.jmotif.sax.datastructure.SAXRecords;
import net.seninp.jmotif.sax.registry.MagicArrayEntry;
import net.seninp.jmotif.sax.registry.SlidingWindowMarkerAlgorithm;
import net.seninp.jmotif.sax.registry.VisitRegistry;
package net.seninp.jmotif.sax.discord;


/**
 * Implements HOTSAX discord discovery algorithm.
 *
 * @author psenin
 */
public class HOTSAXImplementation {

  private static TSProcessor tp = new TSProcessor();
  private static SAXProcessor sp = new SAXProcessor();
  private static EuclideanDistance ed = new EuclideanDistance();

  //logging stuff
  //
  private static final Logger LOGGER;
  private static final Level LOGGING_LEVEL = Level.INFO;

  static {
    LOGGER = (Logger) LoggerFactory.getLogger(HOTSAXImplementation.class);
    LOGGER.setLevel(LOGGING_LEVEL);
  }

  /**
   * Hash-table backed implementation (in contrast to trie). Time series is converted into a
   * SAXRecords data structure first, Hash-table backed magic array created second. HOTSAX applied
   * third. Nearest neighbors are searched only among the subsequences which were produced by SAX
   * with specified numerosity reduction. Thus, if the strategy is EXACT or MINDIST, discords do not
   * match those produced by BruteForce or NONE.
   *
   * @param series The timeseries.
   * @param discordsNumToReport The number of discords to report.
   * @param windowSize SAX sliding window size.
   * @param paaSize SAX PAA value.
   * @param alphabetSize SAX alphabet size.
   * @param strategy the numerosity reduction strategy.
   * @param nThreshold the normalization threshold value.
   * @return The set of discords found within the time series, it may return less than asked for --
   * in this case, there are no more discords.
   * @throws Exception if error occurs., currentPos + windowSize
   */
  public static DiscordRecords series2Discords(double[] series, int discordsNumToReport,
      int windowSize, int paaSize, int alphabetSize, NumerosityReductionStrategy strategy,