BZip2DivSufSort.java

/*
 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
 * Copyright (c) 2011 Matthew Francis
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

package org.itadaki.bzip2;


/**
 * DivSufSort suffix array generator
 * Based on libdivsufsort 1.2.3 patched to support BZip2
 * 
 * This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX"
 * comments within the class). Documentation within the class is largely absent.
 */
public class BZip2DivSufSort {

	/**
	 */
	private static final int STACK_SIZE = 64;

	/**
	 */
	private static final int BUCKET_A_SIZE = 256;

	/**
	 */
	private static final int BUCKET_B_SIZE = 65536;

	/**
	 */
	private static final int SS_BLOCKSIZE = 1024;

	/**
	 */
	private static final int INSERTIONSORT_THRESHOLD = 8;

	/**
	 */
	private static final int log2table[]= {
		-1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
		5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
	};

	/**
	 */
	private final int[] SA;

	/**
	 */
	private final byte[] T;

	/**
	 */
	private final int n;


	/**
	 * @param array1 
	 * @param index1 
	 * @param array2 
	 * @param index2 
	 */
	private static final void swapElements (final int[] array1, final int index1, final int[] array2, final int index2) {

		final int temp = array1[index1];
		array1[index1] = array2[index2];
		array2[index2] = temp; 

	}


	/**
	 * @param p1 
	 * @param p2 
	 * @param depth 
	 * @return
	 */
	private int ssCompare (final int p1, final int p2, final int depth) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		final int U1n, U2n; // pointers within T
		int U1, U2;

		for (
				U1 = depth + SA[p1], U2 = depth + SA[p2], U1n = SA[p1 + 1] + 2, U2n = SA[p2 + 1] + 2;
				(U1 < U1n) && (U2 < U2n) && (T[U1] == T[U2]);
				++U1, ++U2
		    );

		return U1 < U1n ?
				  (U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1)
				: (U2 < U2n ? -1 : 0);

	}


	/**
	 * @param PA
	 * @param p1
	 * @param p2
	 * @param depth
	 * @param size
	 * @return
	 */
	private int ssCompareLast (int PA, int p1, int p2, int depth, int size) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		int U1, U2, U1n, U2n;

		for (
				U1 = depth + SA[p1], U2 = depth + SA[p2], U1n = size, U2n = SA[(p2 + 1)] + 2;
				(U1 < U1n) && (U2 < U2n) && (T[U1] == T[U2]);
				++U1, ++U2
		    );

		if (U1 < U1n) {
			return (U2 < U2n) ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1;
		} else if (U2 == U2n) {
			return 1;
		}

		for (
				U1 = U1 % size, U1n = SA[PA] + 2;
				(U1 < U1n) && (U2 < U2n) && (T[U1] == T[U2]);
				++U1, ++U2
		    );

		return U1 < U1n ?
				  (U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1)
				: (U2 < U2n ? -1 : 0);

	}


	/**
	 * @param PA 
	 * @param first 
	 * @param last 
	 * @param depth
	 */
	private void ssInsertionSort (int PA, int first, int last, int depth) {

		final int[] SA = this.SA;

		int i, j; // pointer within SA
		int t;
		int r;

		for (i = last - 2; first <= i; --i) {
			for (t = SA[i], j = i + 1; 0 < (r = ssCompare (PA + t, PA + SA[j], depth));) {
				do {
					SA[j - 1] = SA[j];
				} while ((++j < last) && (SA[j] < 0));
				if (last <= j) {
					break;
				}
			}
			if (r == 0) {
				SA[j] = ~SA[j];
			}
			SA[j - 1] = t;
		}

	}


	/**
	 * @param Td
	 * @param PA
	 * @param sa
	 * @param i
	 * @param size
	 */
	private void ssFixdown (int Td, int PA, int sa, int i, int size) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		int j, k;
		int v;
		int c, d, e;

		for (v = SA[sa + i], c = (T[Td + SA[PA + v]]) & 0xff; (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
			d = T[Td + SA[PA + SA[sa + (k = j++)]]] & 0xff;
			if (d < (e = T[Td + SA[PA + SA[sa + j]]] & 0xff)) {
				k = j;
				d = e;
			}
			if (d <= c) break;
		}
		SA[sa + i] = v;

	}

	/**
	 * @param Td
	 * @param PA
	 * @param sa
	 * @param size
	 */
	private void ssHeapSort (int Td, int PA, int sa, int size) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		int i, m;
		int t;

		m = size;
		if ((size % 2) == 0) {
			m--;
			if ((T[Td + SA[PA + SA[sa + (m / 2)]]] & 0xff) < (T[Td + SA[PA + SA[sa + m]]] & 0xff)) {
				swapElements (SA, sa + m, SA, sa + (m / 2));
			}
		}

		for (i = m / 2 - 1; 0 <= i; --i) {
			ssFixdown (Td, PA, sa, i, m);
		}

		if ((size % 2) == 0) {
			swapElements (SA, sa, SA, sa + m);
			ssFixdown (Td, PA, sa, 0, m);
		}

		for (i = m - 1; 0 < i; --i) {
			t = SA[sa];
			SA[sa] = SA[sa + i];
			ssFixdown (Td, PA, sa, 0, i);
			SA[sa + i] = t;
		}

	}


	/**
	 * @param Td
	 * @param PA
	 * @param v1
	 * @param v2
	 * @param v3
	 * @return
	 */
	private int ssMedian3 (final int Td, final int PA, int v1, int v2, int v3) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		int T_v1 = T[Td + SA[PA + SA[v1]]] & 0xff;
		int T_v2 = T[Td + SA[PA + SA[v2]]] & 0xff;
		int T_v3 = T[Td + SA[PA + SA[v3]]] & 0xff;

		if (T_v1 > T_v2) {
			final int temp = v1;
			v1 = v2;
			v2 = temp;
			final int T_vtemp = T_v1;
			T_v1 = T_v2;
			T_v2 = T_vtemp;
		}
		if (T_v2 > T_v3) {
			if (T_v1 > T_v3) {
				return v1;
			}
			return v3;
		}
		return v2;

	}


	/**
	 * @param Td
	 * @param PA
	 * @param v1
	 * @param v2
	 * @param v3
	 * @param v4
	 * @param v5
	 * @return
	 */
	private int ssMedian5 (final int Td, final int PA, int v1, int v2, int v3, int v4, int v5) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		int T_v1 = T[Td + SA[PA + SA[v1]]] & 0xff;
		int T_v2 = T[Td + SA[PA + SA[v2]]] & 0xff;
		int T_v3 = T[Td + SA[PA + SA[v3]]] & 0xff;
		int T_v4 = T[Td + SA[PA + SA[v4]]] & 0xff;
		int T_v5 = T[Td + SA[PA + SA[v5]]] & 0xff;
		int temp;
		int T_vtemp;

		if (T_v2 > T_v3) {
			temp = v2;
			v2 = v3;
			v3 = temp;
			T_vtemp = T_v2;
			T_v2 = T_v3;
			T_v3 = T_vtemp;
		}
		if (T_v4 > T_v5) {
			temp = v4;
			v4 = v5;
			v5 = temp;
			T_vtemp = T_v4;
			T_v4 = T_v5;
			T_v5 = T_vtemp;
		}
		if (T_v2 > T_v4) {
			temp = v2;
			v2 = v4;
			v4 = temp;
			T_vtemp = T_v2;
			T_v2 = T_v4;
			T_v4 = T_vtemp;
			temp = v3;
			v3 = v5;
			v5 = temp;
			T_vtemp = T_v3;
			T_v3 = T_v5;
			T_v5 = T_vtemp;
		}
		if (T_v1 > T_v3) {
			temp = v1;
			v1 = v3;
			v3 = temp;
			T_vtemp = T_v1;
			T_v1 = T_v3;
			T_v3 = T_vtemp;
		}
		if (T_v1 > T_v4) {
			temp = v1;
			v1 = v4;
			v4 = temp;
			T_vtemp = T_v1;
			T_v1 = T_v4;
			T_v4 = T_vtemp;
			temp = v3;
			v3 = v5;
			v5 = temp;
			T_vtemp = T_v3;
			T_v3 = T_v5;
			T_v5 = T_vtemp;
		}
		if (T_v3 > T_v4) {
			return v4;
		}
		return v3;

	}


	/**
	 * @param Td
	 * @param PA
	 * @param first
	 * @param last
	 * @return
	 */
	private int ssPivot (final int Td, final int PA, final int first, final int last) {

		int middle;
		int t;

		t = last - first;
		middle = first + t / 2;

		if (t <= 512) {
			if (t <= 32) {
				return ssMedian3 (Td, PA, first, middle, last - 1);
			}
			t >>= 2;
			return ssMedian5 (Td, PA, first, first + t, middle, last - 1 - t, last - 1);
		}
		t >>= 3;
		return ssMedian3 (
				Td, PA,
				ssMedian3 (Td, PA, first, first + t, first + (t << 1)),
				ssMedian3 (Td, PA, middle - t, middle, middle + t),
				ssMedian3 (Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1)
		);

	}


	/**
	 * @param n
	 * @return
	 */
	private int ssLog (final int n) {

		return ((n & 0xff00) != 0) ?
				  8 + log2table[(n >> 8) & 0xff]
				: log2table[n & 0xff];

	}


	/**
	 * @param PA
	 * @param first
	 * @param last
	 * @param depth
	 * @return
	 */
	private int ssSubstringPartition (final int PA, final int first, final int last, final int depth) {

		final int[] SA = this.SA;

		int a, b;
		int t;

		for (a = first - 1, b = last;;) {
			for (; (++a < b) && ((SA[PA + SA[a]] + depth) >= (SA[PA + SA[a] + 1] + 1));) {
				SA[a] = ~SA[a];
			}
			for (; (a < --b) && ((SA[PA + SA[b]] + depth) <  (SA[PA + SA[b] + 1] + 1)););
			if (b <= a) {
				break;
			}
			t = ~SA[b];
			SA[b] = SA[a];
			SA[a] = t;
		}
		if (first < a) {
			SA[first] = ~SA[first];
		}

		return a;

	}


	/**
	 */
	private static class StackEntry {

		/**
		 */
		final int a;
		/**
		 */
		final int b;
		/**
		 */
		final int c;
		/**
		 */
		final int d;

		/**
		 * @param a
		 * @param b
		 * @param c
		 * @param d
		 */
		public StackEntry (final int a, final int b, final int c, final int d) {

			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;

		}

	}


	/**
	 * @param PA
	 * @param first
	 * @param last
	 * @param depth
	 */
	private void ssMultiKeyIntroSort (final int PA, int first, int last, int depth) {

		final int[] SA = this.SA;
		final byte[] T = this.T;

		final StackEntry[] stack = new StackEntry[STACK_SIZE];

		int Td = 0;
		int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
		int s = 0, t = 0;
		int ssize;
		int limit;
		int v = 0, x = 0;

		for (ssize = 0, limit = ssLog (last - first);;) {
			if ((last - first) <= INSERTIONSORT_THRESHOLD) {
				if (1 < (last - first)) {
					ssInsertionSort (PA, first, last, depth);
				}
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				last = entry.b;
				depth = entry.c;
				limit = entry.d;
				continue;
			}

			Td = depth;
			if (limit-- == 0) {
				ssHeapSort (Td, PA, first, last - first);
			}
			if (limit < 0) {
				for (a = first + 1, v = T[Td + SA[PA + SA[first]]] & 0xff; a < last; ++a) {
					if ((x = (T[Td + SA[PA + SA[a]]] & 0xff)) != v) {
						if (1 < (a - first)) { break; }
						v = x;
						first = a;
					}
				}
				if ((T[Td + SA[PA + SA[first]] - 1] & 0xff) < v) {
					first = ssSubstringPartition (PA, first, a, depth);
				}
				if ((a - first) <= (last - a)) {
					if (1 < (a - first)) {
						stack[ssize++] = new StackEntry (a, last, depth, -1);
						last = a;
						depth += 1;
						limit = ssLog (a - first);
					} else {
						first = a;
						limit = -1;
					}
				} else {
					if (1 < (last - a)) {
						stack[ssize++] = new StackEntry (first, a, depth + 1, ssLog (a - first));
						first = a;
						limit = -1;
					} else {
						last = a;
						depth += 1;
						limit = ssLog (a - first);
					}
				}
				continue;
			}

			a = ssPivot (Td, PA, first, last);
			v = T[Td + SA[PA + SA[a]]] & 0xff;
			swapElements (SA, first, SA, a);

			for (b = first; (++b < last) && ((x = (T[Td + SA[PA + SA[b]]] & 0xff)) == v););
			if (((a = b) < last) && (x < v)) {
				for (; (++b < last) && ((x = (T[Td + SA[PA + SA[b]]] & 0xff)) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a);
						++a;
					}
				}
			}
			for (c = last; (b < --c) && ((x = (T[Td + SA[PA + SA[c]]] & 0xff)) == v););
			if ((b < (d = c)) && (x > v)) {
				for (; (b < --c) && ((x = (T[Td + SA[PA + SA[c]]] & 0xff)) >= v);) {
					if (x == v) {
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}
			for (; b < c;) {
				swapElements (SA, b, SA, c);
				for (; (++b < c) && ((x = (T[Td + SA[PA + SA[b]]] & 0xff)) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a);
						++a;
					}
				}
				for (; (b < --c) && ((x = (T[Td + SA[PA + SA[c]]] & 0xff)) >= v);) {
					if (x == v) { 
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}

			if (a <= d) {
				c = b - 1;

				if ((s = a - first) > (t = b - a)) {
					s = t;
				}
				for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}
				if ((s = d - c) > (t = last - d - 1)) {
					s = t;
				}
				for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}

				a = first + (b - a);
				c = last - (d - c);
				b = (v <= (T[Td + SA[PA + SA[a]] - 1] & 0xff)) ? a : ssSubstringPartition (PA, a, c, depth);

				if ((a - first) <= (last - c)) {
					if ((last - c) <= (c - b)) {
						stack[ssize++] = new StackEntry (b, c, depth + 1, ssLog (c - b));
						stack[ssize++] = new StackEntry (c, last, depth, limit);
						last = a;
					} else if ((a - first) <= (c - b)) {
						stack[ssize++] = new StackEntry (c, last, depth, limit);
						stack[ssize++] = new StackEntry (b, c, depth + 1, ssLog (c - b));
						last = a;
					} else {
						stack[ssize++] = new StackEntry (c, last, depth, limit);
						stack[ssize++] = new StackEntry (first, a, depth, limit);
						first = b;
						last = c;
						depth += 1;
						limit = ssLog (c - b);
					}
				} else {
					if ((a - first) <= (c - b)) {
						stack[ssize++] = new StackEntry (b, c, depth + 1, ssLog (c - b));
						stack[ssize++] = new StackEntry (first, a, depth, limit);
						first = c;
					} else if ((last - c) <= (c - b)) {
						stack[ssize++] = new StackEntry (first, a, depth, limit);
						stack[ssize++] = new StackEntry (b, c, depth + 1, ssLog (c - b));
						first = c;
					} else {
						stack[ssize++] = new StackEntry (first, a, depth, limit);
						stack[ssize++] = new StackEntry (c, last, depth, limit);
						first = b;
						last = c;
						depth += 1;
						limit = ssLog (c - b);
					}
				}
			} else {
				limit += 1;
				if ((T[Td + SA[PA + SA[first]] - 1] & 0xff) < v) {
					first = ssSubstringPartition (PA, first, last, depth);
					limit = ssLog (last - first);
				}
				depth += 1;
			}
		}
	}


	/**
	 * @param array1 
	 * @param first1
	 * @param array2 
	 * @param first2
	 * @param size
	 */
	private void ssBlockSwap (final int[] array1, final int first1, final int[] array2, final int first2, final int size) {

		int a, b;
		int i;
		for (i = size, a = first1, b = first2; 0 < i; --i, ++a, ++b) {
			swapElements (array1, a, array2, b);
		}

	}


	/**
	 * @param PA
	 * @param buf 
	 * @param bufoffset
	 * @param first
	 * @param middle
	 * @param last
	 * @param depth
	 */
	private void ssMergeForward (final int PA, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth) {

		final int[] SA = this.SA;

		int bufend;
		int i, j, k;
		int t;
		int r;

		bufend = bufoffset + (middle - first) - 1;
		ssBlockSwap (buf, bufoffset, SA, first, middle - first);

		for (t = SA[first], i = first, j = bufoffset, k = middle;;) {
			r = ssCompare (PA + buf[j], PA + SA[k], depth);
			if (r < 0) {
				do {
					SA[i++] = buf[j];
					if (bufend <= j) {
						buf[j] = t;
						return;
					}
					buf[j++] = SA[i];
				} while (buf[j] < 0);
			} else if (r > 0) {
				do {
					SA[i++] = SA[k];
					SA[k++] = SA[i];
					if (last <= k) {
						while (j < bufend) { SA[i++] = buf[j]; buf[j++] = SA[i]; }
						SA[i] = buf[j]; buf[j] = t;
						return;
					}
				} while (SA[k] < 0);
			} else {
				SA[k] = ~SA[k];
				do {
					SA[i++] = buf[j];
					if (bufend <= j) {
						buf[j] = t;
						return;
					}
					buf[j++] = SA[i];
				} while (buf[j] < 0);

				do {
					SA[i++] = SA[k];
					SA[k++] = SA[i];
					if (last <= k) {
						while (j < bufend) {
							SA[i++] = buf[j];
							buf[j++] = SA[i];
						}
						SA[i] = buf[j]; buf[j] = t;
						return;
					}
				} while (SA[k] < 0);
			}
		}

	}


	/**
	 * @param PA
	 * @param buf 
	 * @param buf
	 * @param bufoffset 
	 * @param first
	 * @param middle
	 * @param last
	 * @param depth
	 */
	private void ssMergeBackward (final int PA, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth) {

		final int[] SA = this.SA;

		int p1, p2;
		int bufend;
		int i, j, k;
		int t;
		int r;
		int x;

		bufend = bufoffset + (last - middle);
		ssBlockSwap (buf, bufoffset, SA, middle, last - middle);

		x = 0;
		if (buf[bufend - 1] < 0) {
			x |=  1;
			p1 = PA + ~buf[bufend - 1];
		} else {
			p1 = PA +  buf[bufend - 1];
		}
		if (SA[middle - 1] < 0) {
			x |=  2;
			p2 = PA + ~SA[middle - 1];
		} else {
			p2 = PA +  SA[middle - 1];
		}
		for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {

			r = ssCompare (p1, p2, depth);
			if (r > 0) {
				if ((x & 1) != 0) {
					do {
						SA[i--] = buf[j];
						buf[j--] = SA[i];
					} while (buf[j] < 0);
					x ^= 1;
				}
				SA[i--] = buf[j];
				if (j <= bufoffset) {
					buf[j] = t;
					return;
				}
				buf[j--] = SA[i];

				if (buf[j] < 0) {
					x |=  1;
					p1 = PA + ~buf[j];
				} else {
					p1 = PA +  buf[j];
				}
			} else if (r < 0) {
				if ((x & 2) != 0) {
					do {
						SA[i--] = SA[k];
						SA[k--] = SA[i];
					} while (SA[k] < 0);
					x ^= 2;
				}
				SA[i--] = SA[k];
				SA[k--] = SA[i];
				if (k < first) {
					while (bufoffset < j) {
						SA[i--] = buf[j];
						buf[j--] = SA[i];
					}
					SA[i] = buf[j];
					buf[j] = t;
					return;
				}

				if (SA[k] < 0) {
					x |=  2;
					p2 = PA + ~SA[k];
				} else {
					p2 = PA +  SA[k];
				}
			} else {
				if ((x & 1) != 0) {
					do {
						SA[i--] = buf[j];
						buf[j--] = SA[i];
					} while (buf[j] < 0);
					x ^= 1;
				}
				SA[i--] = ~buf[j];
				if (j <= bufoffset) {
					buf[j] = t;
					return;
				}
				buf[j--] = SA[i];

				if ((x & 2) != 0) {
					do {
						SA[i--] = SA[k];
						SA[k--] = SA[i];
					} while (SA[k] < 0);
					x ^= 2;
				}
				SA[i--] = SA[k];
				SA[k--] = SA[i];
				if (k < first) {
					while (bufoffset < j) {
						SA[i--] = buf[j];
						buf[j--] = SA[i];
					}
					SA[i] = buf[j];
					buf[j] = t;
					return;
				}

				if (buf[j] < 0) {
					x |=  1;
					p1 = PA + ~buf[j];
				} else {
					p1 = PA +  buf[j];
				}
				if (SA[k] < 0) {
					x |=  2;
					p2 = PA + ~SA[k];
				} else {
					p2 = PA +  SA[k];
				}
			}
		}
	}


	/**
	 * @param a
	 * @return
	 */
	private final static int getIDX (final int a) {

		return (0 <= a) ? a : ~a;

	}


	/**
	 * @param PA
	 * @param depth
	 * @param a
	 */
	private void ssMergeCheckEqual (final int PA, final int depth, final int a) {

		final int[] SA = this.SA;

		if (
				   (0 <= SA[a])
				&& (ssCompare (PA + getIDX (SA[a - 1]), PA + SA[a], depth) == 0)
		   )
		{
			SA[a] = ~SA[a];
		}

	}


	/**
	 * @param PA
	 * @param first
	 * @param middle
	 * @param last
	 * @param buf 
	 * @param bufoffset 
	 * @param bufsize
	 * @param depth
	 */
	private void ssMerge (final int PA, int first, int middle, int last, int[] buf, final int bufoffset, final int bufsize, final int depth) {

		final int[] SA = this.SA;

		final StackEntry[] stack = new StackEntry[STACK_SIZE];

		int i, j;
		int m, len, half;
		int ssize;
		int check, next;

		for (check = 0, ssize = 0;;) {

			if ((last - middle) <= bufsize) {
				if ((first < middle) && (middle < last)) {
					ssMergeBackward (PA, buf, bufoffset, first, middle, last, depth);
				}

				if ((check & 1) != 0) {
					ssMergeCheckEqual (PA, depth, first);
				}
				if ((check & 2) != 0) {
					ssMergeCheckEqual (PA, depth, last);
				}
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				middle = entry.b;
				last = entry.c;
				check = entry.d;
				continue;
			}

			if ((middle - first) <= bufsize) {
				if (first < middle) {
					ssMergeForward ( PA, buf, bufoffset, first, middle, last, depth);
				}
				if ((check & 1) != 0) {
					ssMergeCheckEqual (PA, depth, first);
				}
				if ((check & 2) != 0) {
					ssMergeCheckEqual (PA, depth, last);
				}
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				middle = entry.b;
				last = entry.c;
				check = entry.d;
				continue;
			}

			for (
					m = 0, len = Math.min (middle - first, last - middle), half = len >> 1;
					0 < len;
					len = half, half >>= 1
			    )
			{
				if (ssCompare (PA + getIDX (SA[middle + m + half]),
						PA + getIDX (SA[middle - m - half - 1]), depth) < 0) {
					m += half + 1;
					half -= (len & 1) ^ 1;
				}
			}

			if (0 < m) {
				ssBlockSwap (SA, middle - m, SA, middle, m);
				i = j = middle;
				next = 0;
				if ((middle + m) < last) {
					if (SA[middle + m] < 0) {
						for (; SA[i - 1] < 0; --i);
						SA[middle + m] = ~SA[middle + m];
					}
					for (j = middle; SA[j] < 0; ++j);
					next = 1;
				}
				if ((i - first) <= (last - j)) {
					stack[ssize++] = new StackEntry (j, middle + m, last, (check &  2) | (next & 1));
					middle -= m;
					last = i;
					check = (check & 1);
				} else {
					if ((i == middle) && (middle == j)) {
						next <<= 1;
					}
					stack[ssize++] = new StackEntry (first, middle - m, i, (check & 1) | (next & 2));
					first = j;
					middle += m;
					check = (check & 2) | (next & 1);
				}
			} else {
				if ((check & 1) != 0) {
					ssMergeCheckEqual (PA, depth, first);
				}
				ssMergeCheckEqual (PA, depth, middle);
				if ((check & 2) != 0) {
					ssMergeCheckEqual (PA, depth, last);
				}
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				middle = entry.b;
				last = entry.c;
				check = entry.d;
			}

		}

	}


	/**
	 * @param PA
	 * @param first
	 * @param last
	 * @param buf 
	 * @param bufoffset
	 * @param bufsize
	 * @param depth
	 * @param lastsuffix
	 * @param size
	 */
	private void subStringSort (final int PA, int first, final int last, final int[] buf, final int bufoffset, final int bufsize, final int depth, final boolean lastsuffix, final int size) {

		final int[] SA = this.SA;

		int a, b;
		int[] curbuf;
		int curbufoffset;
		int i, j, k;
		int curbufsize;

		if (lastsuffix) {
			++first;
		}
		for (a = first, i = 0; (a + SS_BLOCKSIZE) < last; a += SS_BLOCKSIZE, ++i) {
			ssMultiKeyIntroSort (PA, a, a + SS_BLOCKSIZE, depth);
			curbuf = SA;
			curbufoffset = a + SS_BLOCKSIZE;
			curbufsize = last - (a + SS_BLOCKSIZE);
			if (curbufsize <= bufsize) {
				curbufsize = bufsize;
				curbuf = buf;
				curbufoffset = bufoffset;
			}
			for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
				ssMerge (PA, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
			}
		}

		ssMultiKeyIntroSort (PA, a, last, depth);

		for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
			if ((i & 1) != 0) {
				ssMerge (PA, a - k, a, last, buf, bufoffset, bufsize, depth);
				a -= k;
			}
		}

		if (lastsuffix) {
			int r;
			for (
					a = first, i = SA[first - 1], r = 1;
					(a < last) && ((SA[a] < 0) || (0 < (r = ssCompareLast (PA, PA + i, PA + SA[a], depth, size))));
					++a
			    )
			{
				SA[a - 1] = SA[a];
			}
			if (r == 0) {
				SA[a] = ~SA[a];
			}
			SA[a - 1] = i;
		}

	}


	/*----------------------------------------------------------------------------*/

	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param p
	 * @return
	 */
	private int trGetC (final int ISA, final int ISAd, final int ISAn, final int p) {

		return (((ISAd + p) < ISAn) ? this.SA[ISAd + p] : this.SA[ISA + ((ISAd - ISA + p) % (ISAn - ISA))]);

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param sa
	 * @param i
	 * @param size
	 */
	private void trFixdown (final int ISA, final int ISAd, final int ISAn, final int sa, int i, final int size) {

		final int[] SA = this.SA;

		int j, k;
		int v;
		int c, d, e;

		for (v = SA[sa +i], c = trGetC (ISA, ISAd, ISAn, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
			k = j++;
			d = trGetC (ISA, ISAd, ISAn, SA[sa + k]);
			if (d < (e = trGetC (ISA, ISAd, ISAn, SA[sa + j]))) {
				k = j;
				d = e;
			}
			if (d <= c) {
				break;
			}
		}
		SA[sa + i] = v;

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param sa
	 * @param size
	 */
	private void trHeapSort (final int ISA, final int ISAd, final int ISAn, final int sa, final int size) {

		final int[] SA = this.SA;

		int i, m;
		int t;

		m = size;
		if ((size % 2) == 0) {
			m--;
			if (trGetC (ISA, ISAd, ISAn, SA[sa + (m / 2)]) < trGetC (ISA, ISAd, ISAn, SA[sa + m])) {
				swapElements (SA, sa + m, SA, sa + (m / 2));
			}
		}

		for (i = m / 2 - 1; 0 <= i; --i) {
			trFixdown (ISA, ISAd, ISAn, sa, i, m);
		}

		if ((size % 2) == 0) {
			swapElements (SA, sa + 0, SA, sa + m);
			trFixdown (ISA, ISAd, ISAn, sa, 0, m);
		}

		for (i = m - 1; 0 < i; --i) {
			t = SA[sa + 0];
			SA[sa + 0] = SA[sa + i];
			trFixdown (ISA, ISAd, ISAn, sa, 0, i);
			SA[sa + i] = t;
		}

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param first
	 * @param last
	 */
	private void trInsertionSort (final int ISA, final int ISAd, final int ISAn, int first, int last) {

		final int[] SA = this.SA;

		int a, b;
		int t, r;

		for (a = first + 1; a < last; ++a) {
			for (t = SA[a], b = a - 1; 0 > (r = trGetC (ISA, ISAd, ISAn, t) - trGetC (ISA, ISAd, ISAn, SA[b]));) {
				do {
					SA[b + 1] = SA[b];
				} while ((first <= --b) && (SA[b] < 0));
				if (b < first) {
					break;
				}
			}
			if (r == 0) {
				SA[b] = ~SA[b];
			}
			SA[b + 1]= t;
		}

	}


	/**
	 * @param n
	 * @return
	 */
	private int trLog (int n) {

		return ((n & 0xffff0000) != 0) ?
				  (((n & 0xff000000) != 0) ? 24 + log2table[(n >> 24) & 0xff] : 16 + log2table[(n >> 16) & 0xff])
				: (((n & 0x0000ff00) != 0) ? 8 + log2table[(n >>  8) & 0xff] : 0 + log2table[(n >>  0) & 0xff]);

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param v1
	 * @param v2
	 * @param v3
	 * @return
	 */
	private int trMedian3 (final int ISA, final int ISAd, final int ISAn, int v1, int v2, int v3) {

		final int[] SA = this.SA;

		int SA_v1 = trGetC (ISA, ISAd, ISAn, SA[v1]);
		int SA_v2 = trGetC (ISA, ISAd, ISAn, SA[v2]);
		int SA_v3 = trGetC (ISA, ISAd, ISAn, SA[v3]);

		if (SA_v1 > SA_v2) {
			final int temp = v1;
			v1 = v2;
			v2 = temp;
			final int SA_vtemp = SA_v1;
			SA_v1 = SA_v2;
			SA_v2 = SA_vtemp;
		}
		if (SA_v2 > SA_v3) {
			if (SA_v1 > SA_v3) {
				return v1;
			}
			return v3;
		}

		return v2;

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param v1
	 * @param v2
	 * @param v3
	 * @param v4
	 * @param v5
	 * @return
	 */
	private int trMedian5 (final int ISA, final int ISAd, final int ISAn, int v1, int v2, int v3, int v4, int v5) {

		final int[] SA = this.SA;

		int SA_v1 = trGetC (ISA, ISAd, ISAn, SA[v1]);
		int SA_v2 = trGetC (ISA, ISAd, ISAn, SA[v2]);
		int SA_v3 = trGetC (ISA, ISAd, ISAn, SA[v3]);
		int SA_v4 = trGetC (ISA, ISAd, ISAn, SA[v4]);
		int SA_v5 = trGetC (ISA, ISAd, ISAn, SA[v5]);
		int temp;
		int SA_vtemp;

		if (SA_v2 > SA_v3) {
			temp = v2;
			v2 = v3;
			v3 = temp;
			SA_vtemp = SA_v2;
			SA_v2 = SA_v3;
			SA_v3 = SA_vtemp;
		}
		if (SA_v4 > SA_v5) {
			temp = v4;
			v4 = v5;
			v5 = temp;
			SA_vtemp = SA_v4;
			SA_v4 = SA_v5;
			SA_v5 = SA_vtemp;
		}
		if (SA_v2 > SA_v4) {
			temp = v2;
			v2 = v4;
			v4 = temp;
			SA_vtemp = SA_v2;
			SA_v2 = SA_v4;
			SA_v4 = SA_vtemp;
			temp = v3;
			v3 = v5;
			v5 = temp;
			SA_vtemp = SA_v3;
			SA_v3 = SA_v5;
			SA_v5 = SA_vtemp;
		}
		if (SA_v1 > SA_v3) {
			temp = v1;
			v1 = v3;
			v3 = temp;
			SA_vtemp = SA_v1;
			SA_v1 = SA_v3;
			SA_v3 = SA_vtemp;
		}
		if (SA_v1 > SA_v4) {
			temp = v1;
			v1 = v4;
			v4 = temp;
			SA_vtemp = SA_v1;
			SA_v1 = SA_v4;
			SA_v4 = SA_vtemp;
			temp = v3;
			v3 = v5;
			v5 = temp;
			SA_vtemp = SA_v3;
			SA_v3 = SA_v5;
			SA_v5 = SA_vtemp;
		}
		if (SA_v3 > SA_v4) {
			return v4;
		}
		return v3;

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param first
	 * @param last
	 * @return
	 */
	private int trPivot (final int ISA, final int ISAd, final int ISAn, final int first, final int last) {

		final int middle;
		int t;

		t = last - first;
		middle = first + t / 2;

		if (t <= 512) {
			if (t <= 32) {
				return trMedian3 (ISA, ISAd, ISAn, first, middle, last - 1);
			}
			t >>= 2;
			return trMedian5 (
					ISA, ISAd, ISAn,
					first, first + t,
					middle,
					last - 1 - t, last - 1
			);
		}
		t >>= 3;
		return trMedian3 (
				ISA, ISAd, ISAn,
				trMedian3 (ISA, ISAd, ISAn, first, first + t, first + (t << 1)),
				trMedian3 (ISA, ISAd, ISAn, middle - t, middle, middle + t),
				trMedian3 (ISA, ISAd, ISAn, last - 1 - (t << 1), last - 1 - t, last - 1)
		);

	}


	/*---------------------------------------------------------------------------*/

	/**
	 * @param ISA
	 * @param sa
	 * @param first
	 * @param last
	 */
	private void lsUpdateGroup (final int ISA, final int first, final int last) {

		final int[] SA = this.SA;

		int a, b;
		int t;

		for (a = first; a < last; ++a) {
			if (0 <= SA[a]) {
				b = a;
				do {
					SA[ISA + SA[a]] = a;
				} while ((++a < last) && (0 <= SA[a]));
				SA[b] = b - a;
				if (last <= a) {
					break;
				}
			}
			b = a;
			do {
				SA[a] = ~SA[a];
			} while (SA[++a] < 0);
			t = a;
			do {
				SA[ISA + SA[b]] = t;
			} while (++b <= a);
		}

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param sa
	 * @param first
	 * @param last
	 */
	private void lsIntroSort (final int ISA, final int ISAd, final int ISAn, int first, int last) {

		final int[] SA = this.SA;

		final StackEntry[] stack = new StackEntry[STACK_SIZE];

		int a, b, c, d, e, f;
		int s, t;
		int limit;
		int v, x = 0;
		int ssize;

		for (ssize = 0, limit = trLog (last - first);;) {

			if ((last - first) <= INSERTIONSORT_THRESHOLD) {
				if (1 < (last - first)) {
					trInsertionSort (ISA, ISAd, ISAn, first, last);
					lsUpdateGroup (ISA, first, last);
				} else if ((last - first) == 1) {
					SA[first] = -1;
				}
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				last = entry.b;
				limit = entry.c;
				continue;
			}

			if (limit-- == 0) {
				trHeapSort (ISA, ISAd, ISAn, first, last - first);
				for (a = last - 1; first < a; a = b) {
					for (
							x = trGetC (ISA, ISAd, ISAn, SA[a]), b = a - 1;
							(first <= b) && (trGetC (ISA, ISAd, ISAn, SA[b]) == x);
							--b
					    )
					{
						SA[b] = ~SA[b];
					}
				}
				lsUpdateGroup (ISA, first, last);
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				last = entry.b;
				limit = entry.c;
				continue;
			}

			a = trPivot (ISA, ISAd, ISAn, first, last);
			swapElements (SA, first, SA, a);
			v = trGetC (ISA, ISAd, ISAn, SA[first]);

			for (b = first; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) == v););
			if (((a = b) < last) && (x < v)) {
				for (; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a);
						++a;
					}
				}
			}
			for (c = last; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) == v););
			if ((b < (d = c)) && (x > v)) {
				for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
					if (x == v) {
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}
			for (; b < c;) {
				swapElements (SA, b, SA, c);
				for (; (++b < c) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a);
						++a;
					}
				}
				for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
					if (x == v) {
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}

			if (a <= d) {
				c = b - 1;

				if ((s = a - first) > (t = b - a)) {
					s = t;
				}
				for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}
				if ((s = d - c) > (t = last - d - 1)) {
					s = t;
				}
				for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}

				a = first + (b - a);
				b = last - (d - c);

				for (c = first, v = a - 1; c < a; ++c) {
					SA[ISA + SA[c]] = v;
				}
				if (b < last) {
					for (c = a, v = b - 1; c < b; ++c) {
						SA[ISA + SA[c]] = v;
					}
				}
				if ((b - a) == 1) {
					SA[a] = - 1;
				}

				if ((a - first) <= (last - b)) {
					if (first < a) {
						stack[ssize++] = new StackEntry (b, last, limit, 0);
						last = a;
					} else {
						first = b;
					}
				} else {
					if (b < last) {
						stack[ssize++] = new StackEntry (first, a, limit, 0);
						first = b;
					} else {
						last = a;
					}
				}
			} else {
				if (ssize == 0) return;
				StackEntry entry = stack[--ssize];
				first = entry.a;
				last = entry.b;
				limit = entry.c;
			}
		}
	}


	/**
	 * @param ISA
	 * @param n
	 * @param depth
	 */
	private void lsSort (final int ISA, final int n, final int depth) {

		final int[] SA = this.SA;

		int ISAd;
		int first, last, i;
		int t, skip;

		for (ISAd = ISA + depth; -n < SA[0]; ISAd += (ISAd - ISA)) {
			first = 0;
			skip = 0;
			do {
				if ((t = SA[first]) < 0) {
					first -= t;
					skip += t;
				} else {
					if (skip != 0) {
						SA[first + skip] = skip;
						skip = 0;
					}
					last = SA[ISA + t] + 1;
					lsIntroSort (ISA, ISAd, ISA + n, first, last);
					first = last;
				}
			} while (first < n);
			if (skip != 0) {
				SA[first + skip] = skip;
			}
			if (n < (ISAd - ISA)) {
				first = 0;
				do {
					if ((t = SA[first]) < 0) {
						first -= t;
					}
					else {
						last = SA[ISA + t] + 1;
						for (i = first; i < last; ++i) {
							SA[ISA + SA[i]] = i;
						}
						first = last;
					}
				} while (first < n);
				break;
			}
		}

	}


	/*---------------------------------------------------------------------------*/

	/**
	 */
	private final class PartitionResult {

		/**
		 */
		final int first;

		/**
		 */
		final int last;

		/**
		 * @param first
		 * @param last
		 */
		public PartitionResult (final int first, final int last) {
			this.first = first;
			this.last = last;
		}

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param first
	 * @param last
	 * @param v
	 * @return
	 */
	private PartitionResult trPartition (final int ISA, final int ISAd, final int ISAn, int first, int last, final int v) {

		final int[] SA = this.SA;

		int a, b, c, d, e, f;
		int t, s;
		int x = 0;

		for (b = first - 1; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) == v););
		if (((a = b) < last) && (x < v)) {
			for (; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
				if (x == v) {
					swapElements (SA, b, SA, a); ++a;
				}
			}
		}
		for (c = last; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) == v););
		if ((b < (d = c)) && (x > v)) {
			for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
				if (x == v) {
					swapElements (SA, c, SA, d); --d;
				}
			}
		}
		for (; b < c;) {
			swapElements (SA, b, SA, c);
			for (; (++b < c) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
				if (x == v) {
					swapElements (SA, b, SA, a); ++a;
				}
			}
			for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
				if (x == v) {
					swapElements (SA, c, SA, d); --d;
				}
			}
		}

		if (a <= d) {
			c = b - 1;
			if ((s = a - first) > (t = b - a)) {
				s = t;
			}
			for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
				swapElements (SA, e, SA, f);
			}
			if ((s = d - c) > (t = last - d - 1)) {
				s = t;
			}
			for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
				swapElements (SA, e, SA, f);
			}
			first += (b - a);
			last -= (d - c);
		}

		return new PartitionResult (first, last);

	}


	/**
	 * @param ISA
	 * @param ISAn
	 * @param first
	 * @param a
	 * @param b
	 * @param last
	 * @param depth
	 */
	private void trCopy (final int ISA, final int ISAn, final int first, final int a, final int b, final int last, final int depth) {

		final int[] SA = this.SA;

		int c, d, e;
		int s, v;

		v = b - 1;

		for (c = first, d = a - 1; c <= d; ++c) {
			if ((s = SA[c] - depth) < 0) {
				s += ISAn - ISA;
			}
			if (SA[ISA +s] == v) {
				SA[++d] = s;
				SA[ISA +s] = d;
			}
		}
		for (c = last - 1, e = d + 1, d = b; e < d; --c) {
			if ((s = SA[c] - depth) < 0) {
				s += ISAn - ISA;
			}
			if (SA[ISA +s] == v) {
				SA[--d] = s;
				SA[ISA + s] = d;
			}
		}

	}


	/**
	 * @param ISA
	 * @param ISAd
	 * @param ISAn
	 * @param first
	 * @param last
	 * @param budget
	 * @param size
	 */
	private void trIntroSort (final int ISA, int ISAd, int ISAn, int first, int last, final TRBudget budget, final int size) {

		final int[] SA = this.SA;

		final StackEntry[] stack = new StackEntry[STACK_SIZE];

		int a, b, c, d, e, f;
		int s, t;
		int v, x = 0;
		int limit, next;
		int ssize;

		for (ssize = 0, limit = trLog (last - first);;) {
			if (limit < 0) {
				if (limit == -1) {
					if (!budget.update (size, last - first)) break; 
					PartitionResult result = trPartition (ISA, ISAd - 1, ISAn, first, last, last - 1);
					a = result.first;
					b = result.last;
					if ((first < a) || (b < last)) {
						if (a < last) {
							for (c = first, v = a - 1; c < a; ++c) {
								SA[ISA + SA[c]] = v;
							}
						}
						if (b < last) {
							for (c = a, v = b - 1; c < b; ++c) {
								SA[ISA + SA[c]] = v;
							}
						}

						stack[ssize++] = new StackEntry (0, a, b, 0);
						stack[ssize++] = new StackEntry (ISAd - 1, first, last, -2);
						if ((a - first) <= (last - b)) {
							if (1 < (a - first)) {
								stack[ssize++] = new StackEntry (ISAd, b, last, trLog (last - b));
								last = a; limit = trLog (a - first);
							} else if (1 < (last - b)) {
								first = b; limit = trLog (last - b);
							} else {
								if (ssize == 0) return;
								StackEntry entry = stack[--ssize];
								ISAd = entry.a;
								first = entry.b;
								last = entry.c;
								limit = entry.d;
							}
						} else {
							if (1 < (last - b)) {
								stack[ssize++] = new StackEntry (ISAd, first, a, trLog (a - first));
								first = b;
								limit = trLog (last - b);
							} else if (1 < (a - first)) {
								last = a;
								limit = trLog (a - first);
							} else {
								if (ssize == 0) return;
								StackEntry entry = stack[--ssize];
								ISAd = entry.a;
								first = entry.b;
								last = entry.c;
								limit = entry.d;
							}
						}
					} else {
						for (c = first; c < last; ++c) {
							SA[ISA + SA[c]] = c;
						}
						if (ssize == 0) return;
						StackEntry entry = stack[--ssize];
						ISAd = entry.a;
						first = entry.b;
						last = entry.c;
						limit = entry.d;
					}
				} else if (limit == -2) {
					a = stack[--ssize].b;
					b = stack[ssize].c;
					trCopy (ISA, ISAn, first, a, b, last, ISAd - ISA);
					if (ssize == 0) return;
					StackEntry entry = stack[--ssize];
					ISAd = entry.a;
					first = entry.b;
					last = entry.c;
					limit = entry.d;
				} else {
					if (0 <= SA[first]) {
						a = first;
						do {
							SA[ISA + SA[a]] = a;
						} while ((++a < last) && (0 <= SA[a]));
						first = a;
					}
					if (first < last) {
						a = first;
						do {
							SA[a] = ~SA[a];
						} while (SA[++a] < 0);
						next = (SA[ISA + SA[a]] != SA[ISAd + SA[a]]) ? trLog (a - first + 1) : -1;
						if (++a < last) {
							for (b = first, v = a - 1; b < a; ++b) {
								SA[ISA + SA[b]] = v;
							}
						}

						if ((a - first) <= (last - a)) {
							stack[ssize++] = new StackEntry (ISAd, a, last, -3);
							ISAd += 1; last = a; limit = next;
						} else {
							if (1 < (last - a)) {
								stack[ssize++] = new StackEntry (ISAd + 1, first, a, next);
								first = a; limit = -3;
							} else {
								ISAd += 1; last = a; limit = next;
							}
						}
					} else {
						if (ssize == 0) return;
						StackEntry entry = stack[--ssize];
						ISAd = entry.a;
						first = entry.b;
						last = entry.c;
						limit = entry.d;
					}
				}
				continue;
			}

			if ((last - first) <= INSERTIONSORT_THRESHOLD) {
				if (!budget.update (size, last - first)) break;
				trInsertionSort (ISA, ISAd, ISAn, first, last);
				limit = -3;
				continue;
			}

			if (limit-- == 0) {
				if (!budget.update (size, last - first)) break;
				trHeapSort (ISA, ISAd, ISAn, first, last - first);
				for (a = last - 1; first < a; a = b) {
					for (
							x = trGetC (ISA, ISAd, ISAn, SA[a]), b = a - 1;
							(first <= b) && (trGetC (ISA, ISAd, ISAn, SA[b]) == x);
							--b
					    )
					{
						SA[b] = ~SA[b];
					}
				}
				limit = -3;
				continue;
			}

			a = trPivot (ISA, ISAd, ISAn, first, last);

			swapElements (SA, first, SA, a);
			v = trGetC (ISA, ISAd, ISAn, SA[first]);
			for (b = first; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) == v););
			if (((a = b) < last) && (x < v)) {
				for (; (++b < last) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a); ++a;
					}
				}
			}
			for (c = last; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) == v););
			if ((b < (d = c)) && (x > v)) {
				for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
					if (x == v) {
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}
			for (; b < c;) {
				swapElements (SA, b, SA, c);
				for (; (++b < c) && ((x = trGetC (ISA, ISAd, ISAn, SA[b])) <= v);) {
					if (x == v) {
						swapElements (SA, b, SA, a);
						++a;
					}
				}
				for (; (b < --c) && ((x = trGetC (ISA, ISAd, ISAn, SA[c])) >= v);) {
					if (x == v) {
						swapElements (SA, c, SA, d);
						--d;
					}
				}
			}

			if (a <= d) {
				c = b - 1;

				if ((s = a - first) > (t = b - a)) {
					s = t;
				}
				for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}
				if ((s = d - c) > (t = last - d - 1)) {
					s = t;
				}
				for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
					swapElements (SA, e, SA, f);
				}

				a = first + (b - a);
				b = last - (d - c);
				next = (SA[ISA + SA[a]] != v) ? trLog (b - a) : -1;

				for (c = first, v = a - 1; c < a; ++c) {
					SA[ISA + SA[c]] = v;
				}
				if (b < last) {
					for (c = a, v = b - 1; c < b; ++c) {
						SA[ISA + SA[c]] = v; }
				}

				if ((a - first) <= (last - b)) {
					if ((last - b) <= (b - a)) {
						if (1 < (a - first)) {
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							last = a;
						} else if (1 < (last - b)) {
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							first = b;
						} else if (1 < (b - a)) {
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							if (ssize == 0) return;
							StackEntry entry = stack[--ssize];
							ISAd = entry.a;
							first = entry.b;
							last = entry.c;
							limit = entry.d;
						}
					} else if ((a - first) <= (b - a)) {
						if (1 < (a - first)) {
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							last = a;
						} else if (1 < (b - a)) {
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							first = b;
						}
					} else {
						if (1 < (b - a)) {
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							last = a;
						}
					}
				} else {
					if ((a - first) <= (b - a)) {
						if (1 < (last - b)) {
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							first = b;
						} else if (1 < (a - first)) {
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							last = a;
						} else if (1 < (b - a)) {
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							stack[ssize++] = new StackEntry (ISAd, first, last, limit);
						}
					} else if ((last - b) <= (b - a)) {
						if (1 < (last - b)) {
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							stack[ssize++] = new StackEntry (ISAd + 1, a, b, next);
							first = b;
						} else if (1 < (b - a)) {
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							last = a;
						}
					} else {
						if (1 < (b - a)) {
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							stack[ssize++] = new StackEntry (ISAd, b, last, limit);
							ISAd += 1;
							first = a;
							last = b;
							limit = next;
						} else {
							stack[ssize++] = new StackEntry (ISAd, first, a, limit);
							first = b;
						}
					}
				}
			} else {
				if (!budget.update (size, last - first)) break; // BUGFIX : Added to prevent an infinite loop in the original code
				limit += 1; ISAd += 1;
			}
		}

		for (s = 0; s < ssize; ++s) {
			if (stack[s].d == -3) {
				lsUpdateGroup (ISA, stack[s].b, stack[s].c);
			}
		}

	}


	/**
	 */
	private static class TRBudget {

		/**
		 */
		int budget;

		/**
		 */
		int chance;

		/**
		 * @param size
		 * @param n
		 * @return something
		 */
		public boolean update (final int size, final int n) {

			this.budget -= n;
			if (this.budget <= 0) {
				if (--this.chance == 0) {
					return false;
				}
				this.budget += size;
			}

			return true;

		}

		/**
		 * @param budget
		 * @param chance
		 */
		public TRBudget (final int budget, final int chance) {

			this.budget = budget;
			this.chance = chance;

		}

	}


	/**
	 * @param ISA
	 * @param n
	 * @param depth
	 */
	private void trSort (final int ISA, final int n, final int depth) {

		final int[] SA = this.SA;

		int first = 0, last;
		int t;

		if (-n < SA[0]) {
			TRBudget budget = new TRBudget (n, trLog (n) * 2 / 3 + 1);
			do {
				if ((t = SA[first]) < 0) {
					first -= t;
				}
				else {
					last = SA[ISA + t] + 1;
					if (1 < (last - first)) {
						trIntroSort (ISA, ISA + depth, ISA + n, first, last, budget, n);
						if (budget.chance == 0) {
							/* Switch to Larsson-Sadakane sorting algorithm. */
							if (0 < first) {
								SA[0] = -first;
							}
							lsSort (ISA, n, depth);
							break;
						}
					}
					first = last;

				}
			} while (first < n);
		}

	}


	/*---------------------------------------------------------------------------*/

	/**
	 * @param bucketB
	 * @param c0
	 * @param c1
	 * @return
	 */
	private static final int BUCKET_B (final int c0, final int c1) {

		return (c1 << 8) | c0;

	}


	/**
	 * @param bucketB
	 * @param c0
	 * @param c1
	 * @return
	 */
	private static final int BUCKET_BSTAR (final int c0, final int c1) {

		return (c0 << 8) | c1;

	}


	/**
	 * @param bucketA
	 * @param bucketB
	 * @return
	 */
	private int sortTypeBstar (final int[] bucketA, final int[] bucketB) {

		final byte[] T = this.T;
		final int[] SA = this.SA;
		final int n = this.n;
		final int[] tempbuf = new int[256];

		int[] buf;
		int PAb, ISAb, bufoffset;
		int i, j, k, t, m, bufsize;
		int c0, c1;
		int flag;

		for (i = 1, flag = 1; i < n; ++i) {
			if (T[i - 1] != T[i]) {
				if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
					flag = 0;
				}
				break;
			}
		}
		i = n - 1;
		m = n;

		int ti,ti1, t0;
		if (((ti = (T[i] & 0xff)) < (t0 = (T[0] & 0xff))) || ((T[i] == T[0]) && (flag != 0))) {
			if (flag == 0) {
				++bucketB[BUCKET_BSTAR (ti, t0)];
				SA[--m] = i;
			} else {
				++bucketB[BUCKET_B (ti, t0)];
			}
			for (--i; (0 <= i) && ((ti = (T[i] & 0xff)) <= (ti1 = (T[i + 1] & 0xff))); --i) {
				++bucketB[BUCKET_B (ti, ti1)];
			}
		}

		for (; 0 <= i;) {
			do {
				++bucketA[T[i] & 0xff];
			} while ((0 <= --i) && ((T[i] & 0xff) >= (T[i + 1] & 0xff)));
			if (0 <= i) {
				++bucketB[BUCKET_BSTAR (T[i] & 0xff, T[i + 1] & 0xff)];
				SA[--m] = i;
				for (--i; (0 <= i) && ((ti = (T[i] & 0xff)) <= (ti1 = (T[i + 1] & 0xff))); --i) {
					++bucketB[BUCKET_B (ti, ti1)];
				}
			}
		}
		m = n - m;
		if (m == 0) {
			for (i = 0; i < n; ++i) {
				SA[i] = i;
			}
			return 0;
		}

		for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
			t = i + bucketA[c0];
			bucketA[c0] = i + j;
			i = t + bucketB[BUCKET_B (c0, c0)];
			for (c1 = c0 + 1; c1 < 256; ++c1) {
				j += bucketB[BUCKET_BSTAR (c0, c1)];
				bucketB[(c0 << 8) | c1] = j;
				i += bucketB[BUCKET_B (c0, c1)];
			}
		}

		PAb = n - m;
		ISAb = m;
		for (i = m - 2; 0 <= i; --i) {
			t = SA[PAb + i];
			c0 = T[t] & 0xff;
			c1 = T[t + 1] & 0xff;
			SA[--bucketB[BUCKET_BSTAR (c0, c1)]] = i;
		}
		t = SA[PAb + m - 1];
		c0 = T[t] & 0xff;
		c1 = T[t + 1] & 0xff;
		SA[--bucketB[BUCKET_BSTAR (c0, c1)]] = m - 1;

		buf = SA;
		bufoffset = m;
		bufsize = n - (2 * m);
		if (bufsize <= 256) {
			buf = tempbuf;
			bufoffset = 0;
			bufsize = 256;
		}

		for (c0 = 255, j = m; 0 < j; --c0) {
			for (c1 = 255; c0 < c1; j = i, --c1) {
				i = bucketB[BUCKET_BSTAR (c0, c1)];
				if (1 < (j - i)) {
					subStringSort (PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == (m - 1), n);
				}
			}
		}

		for (i = m - 1; 0 <= i; --i) {
			if (0 <= SA[i]) {
				j = i;
				do {
					SA[ISAb + SA[i]] = i;
				} while ((0 <= --i) && (0 <= SA[i]));
				SA[i + 1] = i - j;
				if (i <= 0) {
					break;
				}
			}
			j = i;
			do {
				SA[ISAb + (SA[i] = ~SA[i])] = j;
			} while (SA[--i] < 0);
			SA[ISAb + SA[i]] = j;
		}

		trSort (ISAb, m, 1);

		i = n - 1; j = m;
		if (((T[i] & 0xff) < (T[0] & 0xff)) || ((T[i] == T[0]) && (flag != 0))) {
			if (flag == 0) {
				SA[SA[ISAb + --j]] = i;
			}
			for (--i; (0 <= i) && ((T[i] & 0xff) <= (T[i + 1] & 0xff)); --i);
		}
		for (; 0 <= i;) {
			for (--i; (0 <= i) && ((T[i] & 0xff) >= (T[i + 1] & 0xff)); --i);
			if (0 <= i) {
				SA[SA[ISAb + --j]] = i;
				for (--i; (0 <= i) && ((T[i] & 0xff) <= (T[i + 1] & 0xff)); --i);
			}
		}

		for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
			for (c1 = 255; c0 < c1; --c1) {
				t = i - bucketB[BUCKET_B (c0, c1)];
				bucketB[BUCKET_B (c0, c1)] = i + 1;

				for (i = t, j = bucketB[BUCKET_BSTAR (c0, c1)]; j <= k; --i, --k) {
					SA[i] = SA[k];
				}
			}
			t = i - bucketB[BUCKET_B (c0, c0)];
			bucketB[BUCKET_B (c0, c0)] = i + 1;
			if (c0 < 255) {
				bucketB[BUCKET_BSTAR (c0, c0 + 1)] = t + 1;
			}
			i = bucketA[c0];
		}

		return m;

	}


	/**
	 * @param bucketA
	 * @param bucketB
	 * @return
	 */
	private int constructBWT (final int[] bucketA, final int[] bucketB) {

		final byte[] T = this.T;
		final int[] SA = this.SA;
		final int n = this.n;

		int i, j, t = 0;
		int s, s1;
		int c0 = 0, c1, c2 = 0;
		int orig = -1;

		for (c1 = 254; 0 <= c1; --c1) {
			for (
					i = bucketB[BUCKET_BSTAR (c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
					i <= j;
					--j
			    )
			{
				if (0 <= (s1 = s = SA[j])) {
					if (--s < 0) {
						s = n - 1;
					}
					if ((c0 = (T[s] & 0xff)) <= c1) {
						SA[j] = ~s1;
						if ((0 < s) && ((T[s - 1] & 0xff) > c0)) {
							s = ~s;
						}
						if (c2 == c0) {
							SA[--t] = s;
						} else {
							if (0 <= c2) {
								bucketB[BUCKET_B (c2, c1)] = t;
							}
							SA[t = bucketB[BUCKET_B (c2 = c0, c1)] - 1] = s;
						}
					}
				} else {
					SA[j] = ~s;
				}
			}
		}

		for (i = 0; i < n; ++i) {
			if (0 <= (s1 = s = SA[i])) {
				if (--s < 0) {
					s = n - 1;
				}
				if ((c0 = (T[s] & 0xff)) >= (T[s + 1] & 0xff)) {
					if ((0 < s) && ((T[s - 1] & 0xff) < c0)) {
						s = ~s;
					}
					if (c0 == c2) {
						SA[++t] = s;
					} else {
						if (c2 != -1) // BUGFIX: Original code can write to bucketA[-1]
							bucketA[c2] = t;
						SA[t = bucketA[c2 = c0] + 1] = s;
					}
				}

			} else {
				s1 = ~s1;
			}

			if (s1 == 0) {
				SA[i] = T[n - 1];
				orig = i;
			} else {
				SA[i] = T[s1 - 1];
			}
		}

		return orig;

	}


	/**
	 * Performs a Burrows Wheeler Transform on the input array
	 * @return the index of the first character of the input array within the output array
	 */
	public int bwt() {

		final int[] SA = this.SA;
		final byte[] T = this.T;
		final int n = this.n;

		final int[] bucketA = new int[BZip2DivSufSort.BUCKET_A_SIZE];
		final int[] bucketB = new int[BZip2DivSufSort.BUCKET_B_SIZE];

		if (n == 0) {
			return 0;
		} else if (n == 1) {
			SA[0] = T[0];
			return 0;
		}

		int m = sortTypeBstar (bucketA, bucketB);
		if (0 < m) {
			return constructBWT (bucketA, bucketB);
		}

		return 0;

	}


	/**
	 * @param T The input array
	 * @param SA The output array
	 * @param n The length of the input data
	 */
	public BZip2DivSufSort (final byte[] T, final int[] SA, final int n) {

		this.T = T;
		this.SA = SA;
		this.n = n;

	}

}