tikhomirov@307: /*
tikhomirov@307:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@307:  *  
tikhomirov@307:  * This program is free software; you can redistribute it and/or modify
tikhomirov@307:  * it under the terms of the GNU General Public License as published by
tikhomirov@307:  * the Free Software Foundation; version 2 of the License.
tikhomirov@307:  *
tikhomirov@307:  * This program is distributed in the hope that it will be useful,
tikhomirov@307:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@307:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@307:  * GNU General Public License for more details.
tikhomirov@307:  *
tikhomirov@307:  * For information on how to redistribute this software under
tikhomirov@307:  * the terms of a license other than GNU General Public License
tikhomirov@307:  * contact TMate Software at support@hg4j.com
tikhomirov@307:  */
tikhomirov@307: package org.tmatesoft.hg.internal;
tikhomirov@307: 
tikhomirov@657: import java.util.Arrays;
tikhomirov@657: 
tikhomirov@307: /**
tikhomirov@311:  * Internal alternative to Arrays.sort to build reversed index along with sorting
tikhomirov@657:  * and to perform lookup (binary search) without sorted array, using reversed index.
tikhomirov@307:  * 
tikhomirov@307:  * @author Artem Tikhomirov
tikhomirov@307:  * @author TMate Software Ltd.
tikhomirov@307:  */
tikhomirov@657: public final class ArrayHelper<T extends Comparable<T>> {
tikhomirov@657: 	private int[] reverse; // aka sorted2natural
tikhomirov@657: 	private final T[] data;
tikhomirov@657: 	private T[] sorted;
tikhomirov@657: 	
tikhomirov@657: 	public ArrayHelper(T[] _data) {
tikhomirov@657: 		assert _data != null;
tikhomirov@657: 		data = _data;
tikhomirov@657: 	}
tikhomirov@307: 
tikhomirov@657: 	/**
tikhomirov@657: 	 * Sort data this helper wraps, possibly using supplied array (optional)
tikhomirov@657: 	 * to keep sorted elements
tikhomirov@657: 	 * @param sortDest array to keep sorted values at, or <code>null</code>
tikhomirov@657: 	 * @param sortDestIsEmpty <code>false</code> when sortDest already contains copy of data to be sorted
tikhomirov@657: 	 * @param keepSorted <code>true</code> to save sorted array for future use (e.g. in
tikhomirov@657: 	 */
tikhomirov@657: 	public void sort(T[] sortDest, boolean sortDestIsEmpty, boolean keepSorted) {
tikhomirov@657: 		if (sortDest != null) {
tikhomirov@657: 			assert sortDest.length >= data.length;
tikhomirov@657: 			if (sortDestIsEmpty) {
tikhomirov@657: 				System.arraycopy(data, 0, sortDest, 0, data.length);
tikhomirov@657: 			}
tikhomirov@657: 			sorted = sortDest;
tikhomirov@657: 		} else {
tikhomirov@657: 			sorted = data.clone();
tikhomirov@657: 		}
tikhomirov@657: 		reverse = new int[data.length];
tikhomirov@310: 		for (int i = 0; i < reverse.length; i++) {
tikhomirov@657: 			// initial reverse indexes, so that elements that do
tikhomirov@657: 			// not move during sort got correct indexes
tikhomirov@657: 			reverse[i] = i;
tikhomirov@310: 		}
tikhomirov@657: 		sort1(0, data.length);
tikhomirov@657: 		if (!keepSorted) {
tikhomirov@657: 			sorted = null;
tikhomirov@657: 		}
tikhomirov@657: 	}
tikhomirov@657: 
tikhomirov@657: 	/**
tikhomirov@657: 	 * @return all reverse indexes
tikhomirov@657: 	 */
tikhomirov@657: 	public int[] getReverseIndexes() {
tikhomirov@657: 		return reverse;
tikhomirov@657: 	}
tikhomirov@657: 	
tikhomirov@657: 	public int getReverseIndex(int sortedIndex) {
tikhomirov@657: 		return reverse[sortedIndex];
tikhomirov@657: 	}
tikhomirov@657: 	
tikhomirov@657: 	public T get(int index) {
tikhomirov@657: 		return data[index];
tikhomirov@657: 	}
tikhomirov@657: 	
tikhomirov@657: 	public T[] getData() {
tikhomirov@657: 		return data;
tikhomirov@657: 	}
tikhomirov@657: 
tikhomirov@657: 	/**
tikhomirov@657: 	 * Look up sorted index of the value, using sort information 
tikhomirov@657: 	 * @return same value as {@link Arrays#binarySearch(Object[], Object)} does
tikhomirov@657: 	 */
tikhomirov@657: 	public int binarySearchSorted(T value) {
tikhomirov@657: 		if (sorted != null) {
tikhomirov@657: 			return Arrays.binarySearch(sorted, 0, data.length, value);
tikhomirov@657: 		}
tikhomirov@657: 		return binarySearchWithReverse(0, data.length, value);
tikhomirov@657: 	}
tikhomirov@657: 
tikhomirov@657: 	/**
tikhomirov@657: 	 * Look up index of the value in the original array.
tikhomirov@657: 	 * @return index in original data, or <code>defaultValue</code> if value not found
tikhomirov@657: 	 */
tikhomirov@657: 	public int binarySearch(T value, int defaultValue) {
tikhomirov@657: 		int x = binarySearchSorted(value);
tikhomirov@657: 		if (x < 0) {
tikhomirov@657: 			return defaultValue;
tikhomirov@657: 		}
tikhomirov@657: 		return reverse[x];
tikhomirov@307: 	}
tikhomirov@311: 
tikhomirov@311: 	/**
tikhomirov@311: 	 * Slightly modified version of Arrays.sort1(int[], int, int) quicksort alg (just to deal with Object[])
tikhomirov@311: 	 */
tikhomirov@657:     private void sort1(int off, int len) {
tikhomirov@658: 		Comparable<Object>[] x = comparableSorted();
tikhomirov@307:     	// Insertion sort on smallest arrays
tikhomirov@307:     	if (len < 7) {
tikhomirov@307:     	    for (int i=off; i<len+off; i++)
tikhomirov@307:     			for (int j=i; j>off && x[j-1].compareTo(x[j]) > 0; j--)
tikhomirov@657:     			    swap(j, j-1);
tikhomirov@307:     	    return;
tikhomirov@307:     	}
tikhomirov@307: 
tikhomirov@307:     	// Choose a partition element, v
tikhomirov@307:     	int m = off + (len >> 1);       // Small arrays, middle element
tikhomirov@307:     	if (len > 7) {
tikhomirov@307:     	    int l = off;
tikhomirov@307:     	    int n = off + len - 1;
tikhomirov@307:     	    if (len > 40) {        // Big arrays, pseudomedian of 9
tikhomirov@307:     			int s = len/8;
tikhomirov@657: 	    		l = med3(l,     l+s, l+2*s);
tikhomirov@657: 	    		m = med3(m-s,   m,   m+s);
tikhomirov@657: 	    		n = med3(n-2*s, n-s, n);
tikhomirov@307:     	    }
tikhomirov@657:     	    m = med3(l, m, n); // Mid-size, med of 3
tikhomirov@307:     	}
tikhomirov@307:     	Comparable<Object> v = x[m];
tikhomirov@307: 
tikhomirov@307:     	// Establish Invariant: v* (<v)* (>v)* v*
tikhomirov@307:     	int a = off, b = a, c = off + len - 1, d = c;
tikhomirov@307:     	while(true) {
tikhomirov@307:     	    while (b <= c && x[b].compareTo(v) <= 0) {
tikhomirov@307:     			if (x[b] == v)
tikhomirov@657:     			    swap(a++, b);
tikhomirov@307:     			b++;
tikhomirov@307:     	    }
tikhomirov@307:     	    while (c >= b && x[c].compareTo(v) >= 0) {
tikhomirov@307:     			if (x[c] == v)
tikhomirov@657:     			    swap(c, d--);
tikhomirov@307:     			c--;
tikhomirov@307:     	    }
tikhomirov@307:     	    if (b > c)
tikhomirov@307:     			break;
tikhomirov@657:     	    swap(b++, c--);
tikhomirov@307:     	}
tikhomirov@307: 
tikhomirov@307:     	// Swap partition elements back to middle
tikhomirov@307:     	int s, n = off + len;
tikhomirov@657:     	s = Math.min(a-off, b-a  );  vecswap(off, b-s, s);
tikhomirov@657:     	s = Math.min(d-c,   n-d-1);  vecswap(b,   n-s, s);
tikhomirov@307: 
tikhomirov@307:     	// Recursively sort non-partition-elements
tikhomirov@307:     	if ((s = b-a) > 1)
tikhomirov@657:     	    sort1(off, s);
tikhomirov@307:     	if ((s = d-c) > 1)
tikhomirov@657:     	    sort1(n-s, s);
tikhomirov@307:     }
tikhomirov@307: 
tikhomirov@307:     /**
tikhomirov@307:      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
tikhomirov@307:      */
tikhomirov@657:     private void vecswap(int a, int b, int n) {
tikhomirov@307: 		for (int i=0; i<n; i++, a++, b++) {
tikhomirov@657: 		    swap(a, b);
tikhomirov@307: 		}
tikhomirov@307:     }
tikhomirov@307: 
tikhomirov@307:     /**
tikhomirov@307:      * Returns the index of the median of the three indexed integers.
tikhomirov@307:      */
tikhomirov@657:     private int med3(int a, int b, int c) {
tikhomirov@658: 		Comparable<Object>[] x = comparableSorted();
tikhomirov@657: 		return (x[a].compareTo(x[b]) < 0 ?
tikhomirov@657: 			(x[b].compareTo(x[c]) < 0 ? b : x[a].compareTo(x[c]) < 0 ? c : a) :
tikhomirov@657: 			(x[b].compareTo(x[c]) > 0 ? b : x[a].compareTo(x[c]) > 0 ? c : a));
tikhomirov@307:     }
tikhomirov@658:     
tikhomirov@658:     private Comparable<Object>[] comparableSorted() {
tikhomirov@658:     	// Comparable<Object>[] x = (Comparable<Object>[]) sorted
tikhomirov@658: 		// eclipse compiler is ok with the line above, while javac doesn't understand it:
tikhomirov@658: 		// inconvertible types found : T[] required: java.lang.Comparable<java.lang.Object>[]
tikhomirov@658:     	// so need to add another step
tikhomirov@658:     	Comparable<?>[] oo = sorted;
tikhomirov@658: 		@SuppressWarnings("unchecked")
tikhomirov@658: 		Comparable<Object>[] x = (Comparable<Object>[]) oo;
tikhomirov@658: 		return x;
tikhomirov@658:     }
tikhomirov@307: 
tikhomirov@657:     /**
tikhomirov@307: 	 * Swaps x[a] with x[b].
tikhomirov@307: 	 */
tikhomirov@657: 	private void swap(int a, int b) {
tikhomirov@657: 		Object[] x = sorted;
tikhomirov@307: 		Object t = x[a];
tikhomirov@307: 		x[a] = x[b];
tikhomirov@307: 		x[b] = t;
tikhomirov@657: 		int z1 = reverse[a];
tikhomirov@657: 		int z2 = reverse[b];
tikhomirov@307: 		reverse[b] = z1;
tikhomirov@307: 		reverse[a] = z2;
tikhomirov@307: 	}
tikhomirov@657: 
tikhomirov@657: 	// copied from Arrays.binarySearch0, update to be instance method and to use reverse indexes
tikhomirov@657: 	private int binarySearchWithReverse(int fromIndex, int toIndex, T key) {
tikhomirov@657: 		int low = fromIndex;
tikhomirov@657: 		int high = toIndex - 1;
tikhomirov@657: 
tikhomirov@657: 		while (low <= high) {
tikhomirov@657: 			int mid = (low + high) >>> 1;
tikhomirov@657: 			// data[reverse[x]] gives sorted value at index x
tikhomirov@657: 			T midVal = data[reverse[mid]];
tikhomirov@657: 			int cmp = midVal.compareTo(key);
tikhomirov@657: 
tikhomirov@657: 			if (cmp < 0)
tikhomirov@657: 				low = mid + 1;
tikhomirov@657: 			else if (cmp > 0)
tikhomirov@657: 				high = mid - 1;
tikhomirov@657: 			else
tikhomirov@657: 				return mid; // key found
tikhomirov@657: 		}
tikhomirov@657: 		return -(low + 1);  // key not found.
tikhomirov@657: 	}
tikhomirov@657: 
tikhomirov@307: }