import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
interface Counter { int count(); }
interface CountingSorter<E>
{
void sort(List<E> list);
int exchangeCount();
int comparisonCount();
}
interface Subsorter<E> { void sort(List<E> list, int lower, int upper); }
interface InjectableSorter<E> { void sort(List<E> list, Comparator<E> cmp); }
final class ListFactory<E>
{
public final List<E> produce()
{
return new ArrayList<E>(); // or, new LinkedList<E>();
}
}
class ListCopier<E>
{
private final ListFactory<E> listFactory = new ListFactory<E>();
public final List<E> copy(List<E> list)
{
List<E> copy = listFactory.produce();
copy.addAll(list);
return copy;
}
}
final class ListPermuter<E>
{
private final ListFactory<E> listFactory = new ListFactory<E>();
private final ListCopier<E> listCopier = new ListCopier<E>();
private final ListFactory<List<E>> listOfListsFactory = new ListFactory<List<E>>();
public List<List<E>> allPermutationsOf(List<E> original)
{
List<E> list = listCopier.copy(original);
List<List<E>> allPermutations = listOfListsFactory.produce();
final int n = list.size();
if (n <= 1)
{
List<E> singlePermutation = listCopier.copy(list);
allPermutations.add(singlePermutation);
return allPermutations;
}
for (int i = 0; i < n; i++)
{
E element = list.get(i);
List<E> oneLess = listFactory.produce();
for (int j = 0; j < n; j++)
if (i != j)
oneLess.add(list.get(j));
for (List<E> permutation : allPermutationsOf(oneLess))
{
List<E> nextPermutation = listFactory.produce();
nextPermutation.add(element);
nextPermutation.addAll(permutation);
allPermutations.add(nextPermutation);
}
}
return allPermutations;
}
}
final class Multitool<E>
{
private final ListFactory<E> listFactory = new ListFactory<E>();
private final ListCopier<E> listCopier = new ListCopier<E>();
private final ListPermuter<E> listPermuter = new ListPermuter();
private Long startTime = System.nanoTime();
public final List<E> produce()
{
return listFactory.produce();
}
public final List<E> copy(List<E> list)
{
return listCopier.copy(list);
}
public final List<List<E>> allPermutationsOf(List<E> list)
{
return listPermuter.allPermutationsOf(list);
}
public final void startTimer()
{
startTime = System.nanoTime();
}
public final long stopTimer()
{
return System.nanoTime() - startTime;
}
}
class CountingExchanger<E> implements Counter
{
private int n = 0;
public void exchange(List<E> list, int i, int j)
{
n++;
E tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
}
public int count() { return n; }
}
class CountingComparator<E> implements Comparator<E>, Counter
{
private int n = 0;
private Comparator<E> comparator;
public CountingComparator(Comparator<E> cmp)
{
this.comparator = cmp;
}
public int compare(E e1, E e2)
{
n++;
return comparator.compare(e1, e2);
}
public int count() { return n; }
}
class Pivoter<E>
{
private final CountingExchanger<E> exchanger;
private final CountingComparator<E> comparator;
public Pivoter(Comparator<E> cmp)
{
this(new CountingExchanger<E>(), new CountingComparator<E>(cmp));
}
public Pivoter(CountingExchanger<E> exch, CountingComparator<E> cmp)
{
this.exchanger = exch;
this.comparator = cmp;
}
public final int exchangeCount()
{
return exchanger.count();
}
public final int comparisonCount()
{
return comparator.count();
}
final public int pivotDown(List<E> list, int lower, int upper)
{
if (upper - lower <= 1) return -1;
int pivot = upper - 1;
final E pivotValue = list.get(pivot);
int j = pivot - 1;
for (int i = j; i >= lower; i--)
{
final int compareResult = comparator.compare(list.get(i), pivotValue);
if (compareResult >= 0)
{
if (i < j) exchanger.exchange(list, i, j);
if (compareResult > 0) exchanger.exchange(list, pivot, j);
pivot = j--;
}
}
return pivot;
}
public final int pivotUp(List<E> list, int lower, int upper)
{
if (upper - lower <= 1) return -1;
int pivot = lower;
final E pivotValue = list.get(pivot);
int j = pivot + 1;
for (int i = j; i < upper; i++)
{
final int compareResult = comparator.compare(list.get(i), pivotValue);
if (compareResult <= 0)
{
if (i > j) exchanger.exchange(list, i, j);
if (compareResult < 0) exchanger.exchange(list, pivot, j);
pivot = j++;
}
}
return pivot;
}
public final int pivotIn(List<E> list, int lower, int upper)
{
final int n = upper - lower - 1;
if (n < 1) return -1;
final E pivotValue = list.get((int)(Math.random() * n));
int i = lower, j = upper - 1;
int left = -1, right = -1;
while (i < j)
{
if (left < 0)
{
if (comparator.compare(list.get(i), pivotValue) > 0)
left = i;
else
i++;
}
if (right < 0)
{
if (comparator.compare(list.get(j), pivotValue) < 0)
right = j;
else
j--;
}
if (left >= 0 && right >=0)
{
exchanger.exchange(list, left, right);
left = right = -1;
}
}
System.out.println("pivot index: " + i);
if (left >= 0)
{
if (left < i - 1)
exchanger.exchange(list, left, i - 1);
exchanger.exchange(list, i - 1, i);
}
else if (right >= 0)
{
if (right > i + 1)
exchanger.exchange(list, i + 1, right);
exchanger.exchange(list, i, i + 1);
}
return i;
}
}
abstract class AbstractQuicksorter<E> extends Pivoter<E> implements CountingSorter<E>
{
protected AbstractQuicksorter(Comparator<E> cmp)
{
super(cmp);
}
public void sort(List<E> list)
{
introspectiveSort(list, 0, list.size());
}
public void pivotInSort(List<E> list)
{
pivotInSort(list, 0, list.size());
}
public void pivotDownSort(List<E> list)
{
pivotDownSort(list, 0, list.size());
}
public void pivotUpSort(List<E> list)
{
pivotUpSort(list, 0, list.size());
}
public void pivotUpDownSort(List<E> list)
{
pivotUpDownSort(list, 0, list.size());
}
public void pivotDownUpSort(List<E> list)
{
pivotDownUpSort(list, 0, list.size());
}
public abstract void introspectiveSort(List<E> list, int lower, int upper);
public abstract void pivotDownSort(List<E> list, int lower, int upper);
public abstract void pivotUpSort(List<E> list, int lower, int upper);
public abstract void pivotInSort(List<E> list, int lower, int upper);
public abstract void pivotDownUpSort(List<E> list, int lower, int upper);
public abstract void pivotUpDownSort(List<E> list, int lower, int upper);
}
final class Quicksorter<E> extends AbstractQuicksorter<E>
{
private final int TIP; // the too-tiny / not-too-tiny tipping point
private final Subsorter<E> TOO_TINY;
private final Subsorter<E> NOT_TOO_TINY;
public Quicksorter(Comparator<E> cmp)
{
super(cmp);
this.TIP = 4;
this.TOO_TINY = (lst, low, high) -> pivotUpDownSort(lst, low, high);
this.NOT_TOO_TINY = (lst, low, high) -> introspectiveSort(lst, low, high);
}
public Quicksorter(Comparator<E> cmp, int tip, Subsorter<E> tooTiny, Subsorter<E> notTooTiny)
{
super(cmp);
this.TIP = tip;
this.TOO_TINY = tooTiny;
this.NOT_TOO_TINY = notTooTiny;
}
public final Subsorter<E> getSubsorter(int listSize)
{
return (listSize < this.TIP) ? this.TOO_TINY : this.NOT_TOO_TINY;
}
public final void introspectiveSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotIn(list, lower, upper);
if (pivot < 0) return;
final int bottomSize = pivot - lower - 1;
final int topSize = upper - pivot;
int firstSize, secondSize, firstLower, firstUpper, secondLower, secondUpper;
Subsorter<E> firstSubsorter, secondSubsorter;
if (bottomSize < topSize)
{
firstSize = bottomSize;
secondSize = topSize;
firstLower = lower;
firstUpper = pivot;
secondLower = pivot + 1;
secondUpper = upper;
}
else
{
firstSize = topSize;
secondSize = bottomSize;
firstLower = pivot + 1;
firstUpper = upper;
secondLower = lower;
secondUpper = pivot;
}
firstSubsorter = getSubsorter(firstSize);
secondSubsorter = getSubsorter(secondSize);
firstSubsorter.sort(list, firstLower, firstUpper);
secondSubsorter.sort(list, secondLower, secondUpper);
}
public final void pivotInSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotIn(list, lower, upper);
if (pivot < 0) return;
pivotInSort(list, lower, pivot);
pivotInSort(list, pivot + 1, upper);
}
public final void pivotDownUpSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotDown(list, lower, upper);
if (pivot < 0) return;
pivotUpDownSort(list, lower, pivot);
pivotUpDownSort(list, pivot + 1, upper);
}
public final void pivotUpDownSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotUp(list, lower, upper);
if (pivot < 0) return;
pivotDownUpSort(list, lower, pivot);
pivotDownUpSort(list, pivot + 1, upper);
}
public final void pivotDownSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotDown(list, lower, upper);
if (pivot < 0) return;
pivotDownSort(list, lower, pivot);
pivotDownSort(list, pivot + 1, upper);
}
public final void pivotUpSort(List<E> list, int lower, int upper)
{
int pivot = super.pivotUp(list, lower, upper);
if (pivot < 0) return;
pivotUpSort(list, lower, pivot);
pivotUpSort(list, pivot + 1, upper);
}
}
/** Go, Sorter. Go!
*
* Is it pretty? Is it quick? Is it pretty quick?
*
* Do you like thisPrettyQuickSorter?
*/
public class PrettyQuickSorters {
private static final Multitool<String> tool = new Multitool<String>();
private static final CountingSorter<String> thisPrettyQuickSorter =
new Quicksorter<String>(String.CASE_INSENSITIVE_ORDER);
private static final InjectableSorter<String> thatPrettyQuickSorter =
(list, cmp) -> Collections.sort(list, cmp);
private static final CountingComparator<String> comparator =
new CountingComparator<String>(String.CASE_INSENSITIVE_ORDER);
public static void main(String[] args)
{
Long nanoSec1 = 0L, nanoSec2 = 0L;
List<String> original = Arrays.asList(args);
List<List<String>> permutations = tool.allPermutationsOf(original);
for (List<String> permutation : permutations)
{
List<String> copy1 = tool.copy(permutation);
tool.startTimer();
thisPrettyQuickSorter.sort(copy1);
nanoSec1 += tool.stopTimer();
List<String> copy2 = tool.copy(permutation);
tool.startTimer();
thatPrettyQuickSorter.sort(copy2, comparator);
nanoSec2 += tool.stopTimer();
}
System.out.println("Sorted " + permutations.size() + " permutations of " + original);
System.out.println("This comparisons, exchanges, seconds: " +
thisPrettyQuickSorter.comparisonCount() + ", " +
thisPrettyQuickSorter.exchangeCount() + ", " +
nanoSec1 / 1e9);
System.out.println("That comparisons, exchanges, seconds: " +
comparator.count() + ", ?, " + nanoSec2 / 1e9);
}
}
