001: /*
002: * Copyright (c) 1998 - 2005 Versant Corporation
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Versant Corporation - initial API and implementation
010: */
011: package com.versant.core.common;
012:
013: /**
014: * Base class for containers that need to be able to sort themselves using
015: * the quicksort algorithm. Subclasses just need to implement compare
016: * and swap to make themselves sortable. The size field must be set to
017: * the number of entries in the container when sort is called.
018: *
019: * @see #compare
020: * @see #swap
021: * @see #sort
022: * @see #size
023: *
024: */
025: public abstract class SortableBase {
026:
027: /**
028: * The number of entries in the container.
029: */
030: protected int size;
031:
032: /**
033: * Sort the entries.
034: */
035: public void sort() {
036: quicksort(0, size - 1);
037: }
038:
039: public void sort(int min, int max) {
040: quicksort(min, max);
041: }
042:
043: /**
044: * Compare entries at and a and b. Return 0 if equal, less than 0
045: * if a is less than b or greater than 0 if a is greater than b.
046: */
047: protected abstract int compare(int a, int b);
048:
049: /**
050: * Swap entries.
051: */
052: protected abstract void swap(int index1, int index2);
053:
054: private final void quicksort(final int left, final int right) {
055: final int size = right - left + 1;
056: if (size <= 3) {
057: manualSort(left, right, size);
058: } else {
059: final int median = median(left, right);
060: final int partition = partition(left, right, median);
061: quicksort(left, partition - 1);
062: quicksort(partition + 1, right);
063: }
064: }
065:
066: /**
067: * This will sort up to 3 entries.
068: */
069: private final void manualSort(final int left, final int right,
070: final int size) {
071: if (size <= 1)
072: return;
073: if (size == 2) {
074: if (compare(left, right) > 0)
075: swap(left, right);
076: } else {
077: if (compare(left, right - 1) > 0)
078: swap(left, right - 1);
079: if (compare(left, right) > 0)
080: swap(left, right);
081: if (compare(left + 1, right) > 0)
082: swap(left + 1, right);
083: }
084:
085: }
086:
087: private final int median(final int left, final int right) {
088: final int center = (left + right) / 2;
089: if (compare(left, center) > 0)
090: swap(left, center);
091: if (compare(left, right) > 0)
092: swap(left, right);
093: if (compare(center, right) > 0)
094: swap(center, right);
095: swap(center, right - 1);
096: return right - 1;
097: }
098:
099: private final int partition(final int left, final int right,
100: final int pivotIndex) {
101: int leftIndex = left;
102: int rightIndex = right - 1;
103: while (true) {
104: while (compare(++leftIndex, pivotIndex) < 0)
105: ;
106: while (compare(--rightIndex, pivotIndex) > 0)
107: ;
108: if (leftIndex >= rightIndex) {
109: break; // pointers cross so partition done
110: } else {
111: swap(leftIndex, rightIndex);
112: }
113: }
114: swap(leftIndex, right - 1); // restore pivot
115: return leftIndex; // return pivot location
116: }
117:
118: }
|