CircularSuffixArray.java

/*
Aggregate score: 98.77%
Correctness:  73/73 tests passed
Memory:       10/10 tests passed
Timing:       153/163 tests passed
*/


import edu.princeton.cs.algs4.In;
import java.util.Arrays;

public class CircularSuffixArray {

    private final int n;
    private final CircularSuffix[] cs;

    // circular suffix array of s
    public CircularSuffixArray(String s) {
        if (null == s) throw new IllegalArgumentException();
        this.n = s.length();
        this.cs = new CircularSuffix[n];

        for (int i = 0; i < n; i++) { // Creation of the suffixes
            cs[i] = new CircularSuffix(s, i);
        }
        sortCsa(); // sort the suffixes
    }

    // length of s
    public int length() {
        return n;
    }

    // returns index of ith sorted suffix
    public int index(int i) {
        if (i < 0 || i >= n) throw new IllegalArgumentException(); // i within bounds?
        return cs[i].getFirstPos();
    }

    private void sortCsa() {
        Arrays.sort(cs);
    }

    /////////////// NESTED CLASS //////////////////
    private class CircularSuffix implements Comparable<CircularSuffix> {
        private String s;
        private final int firstPos;
        private final int n;

        public CircularSuffix(String txt, int pos) {
            this.s = txt;
            this.n = txt.length();
            this.firstPos = pos;
        }

        public char charAt(int u) {
            return this.s.charAt(u);
        }

        public int getFirstPos() {
            return firstPos;
        }

        @Override
        public int compareTo(CircularSuffix circularSuffix) {
            CircularSuffix that = circularSuffix;
            char c1 = charAt(this.firstPos);
            char c2 = charAt(that.firstPos);
            int c = 0; // a counter

            while (c1 == c2 && c < n) { // we compare the char of each suffixes at their respective first positions
                c1 = charAt((this.firstPos + c) % n); // we continue searching further down the string
                c2 = charAt((that.firstPos + c) % n);
                c++;
            }
            if (c == n)
                return 0; // we have reached the end of the compares without a difference so same suffixes
            else return c1 < c2 ? -1 : 1;
        }
    }

    // unit testing (required)
    public static void main(String[] args) {
        In in = new In(args[0]);
        String s = in.readAll();
        CircularSuffixArray csa = new CircularSuffixArray(s);
    }
}