package algs63; // section 6.3
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Manber.java
 *  Execution:    java Manber < text.txt
 *  Dependencies: In.java
 *
 *  Reads a text corpus from stdin and suffix sorts it in subquadratic
 *  time using a variant of XManber's algorithm.
 *
 *  NOTE: I THINK THIS IS CYCLIC SUFFIX SORTING
 *
 *************************************************************************/

public class XManber {
  private final int N;               // length of input string
  private final String text;         // input text
  private final int[] index;         // offset of ith string in order
  private final int[] rank;          // rank of ith string
  private final int[] newrank;       // rank of ith string (temporary)
  private int offset;

  public XManber(String s) {
    N    = s.length();
    text = s;
    index   = new int[N+1];
    rank    = new int[N+1];
    newrank = new int[N+1];

    // sentinels
    index[N] = N;
    rank[N] = -1;

    msd();
    doit();
  }

  // do one pass of msd sorting by rank at given offset
  private void doit() {
    for (offset = 1; offset < N; offset += offset) {
      StdOut.println("offset = " + offset);

      int count = 0;
      for (int i = 1; i <= N; i++) {
        if (rank[index[i]] == rank[index[i-1]]) count++;
        else if (count > 0) {
          // sort
          int left = i-1-count;
          int right = i-1;
          quicksort(left, right);

          // now fix up ranks
          int r = rank[index[left]];
          for (int j = left + 1; j <= right; j++) {
            if (less(index[j-1], index[j]))  {
              r = rank[index[left]] + j - left;
            }
            newrank[index[j]] = r;
          }

          // copy back - note can't update rank too eagerly
          for (int j = left + 1; j <= right; j++) {
            rank[index[j]] = newrank[index[j]];
          }

          count = 0;
        }
      }
    }
  }

  // sort by leading char, assumes extended ASCII (256 values)
  private void msd() {
    // calculate frequencies
    int[] freq = new int[256];
    for (int i = 0; i < N; i++)
      freq[text.charAt(i)]++;

    // calculate cumulative frequencies
    int[] cumm = new int[256];
    for (int i = 1; i < 256; i++)
      cumm[i] = cumm[i-1] + freq[i-1];

    // compute ranks
    for (int i = 0; i < N; i++)
      rank[i] = cumm[text.charAt(i)];

    // sort by first char
    for (int i = 0; i < N; i++)
      index[cumm[text.charAt(i)]++] = i;
  }


  // for debugging
  public void show() {
    String texttext = text + text;  // make cyclic
    StdOut.println("j, rank[index[j]], index[j]");
    for (int i = 0; i < N; i++) {
      String s = texttext.substring(index[i], index[i] +  Math.min(40, N));
      StdOut.println(s + " " + i + " " + rank[index[i]] + " " + index[i]);
    }
    StdOut.println();
  }


  // test client
  public static void main(String[] args) {
    String s = StdIn.readAll();
    XManber m = new XManber(s);
    m.show();
  }


  /* ********************************************************************
   *  Helper functions for comparing suffixes.
   **********************************************************************/

  /* ********************************************************************
   * Is the substring text[v..N] lexicographically less than the
   * substring text[w..N] ?
   **********************************************************************/
  private boolean less(int v, int w) {
    if (v + offset >= N) v -= N;
    if (w + offset >= N) w -= N;
    return rank[v + offset] < rank[w + offset];
  }



  /* ***********************************************************************
   *  Quicksort code from Sedgewick 7.1, 7.2.
   *************************************************************************/

  // swap pointer sort indices
  private void exch(int i, int j) {
    int swap = index[i];
    index[i] = index[j];
    index[j] = swap;
  }


  // SUGGEST REPLACING WITH 3-WAY QUICKSORT SINCE ELEMENTS ARE
  // RANKS AND THERE MAY BE DUPLICATES
  void quicksort(int l, int r) {
    if (r <= l) return;
    int i = partition(l, r);
    quicksort(l, i-1);
    quicksort(i+1, r);
  }

  int partition(int l, int r) {
    int i = l-1, j = r;
    int v = index[r];

    while (true) {

      // find item on left to swap
      while (less(index[++i], v))
        ;

      // find item on right to swap
      while (less(v, index[--j]))
        if (j == l) break;

      // check if pointers cross
      if (i >= j) break;

      exch(i, j);
    }

    // swap with partition element
    exch(i, r);

    return i;
  }
}