001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 IBM Corporation and others.
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: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.ui.dialogs;
011:
012: import java.util.Comparator;
013:
014: import org.eclipse.core.runtime.Assert;
015:
016: /**
017: * Quick sort to sort key-value pairs. The keys and arrays are specified
018: * in separate arrays.
019: *
020: * @since 2.0
021: */
022: /* package */class TwoArrayQuickSorter {
023:
024: private Comparator fComparator;
025:
026: /**
027: * Default comparator.
028: */
029: public static final class StringComparator implements Comparator {
030: private boolean fIgnoreCase;
031:
032: StringComparator(boolean ignoreCase) {
033: fIgnoreCase = ignoreCase;
034: }
035:
036: public int compare(Object left, Object right) {
037: return fIgnoreCase ? ((String) left)
038: .compareToIgnoreCase((String) right)
039: : ((String) left).compareTo((String) right);
040: }
041: }
042:
043: /**
044: * Creates a sorter with default string comparator.
045: * The keys are assumed to be strings.
046: * @param ignoreCase specifies whether sorting is case sensitive or not.
047: */
048: public TwoArrayQuickSorter(boolean ignoreCase) {
049: fComparator = new StringComparator(ignoreCase);
050: }
051:
052: /**
053: * Creates a sorter with a comparator.
054: * @param comparator the comparator to order the elements. The comparator must not be <code>null</code>.
055: */
056: public TwoArrayQuickSorter(Comparator comparator) {
057: fComparator = comparator;
058: }
059:
060: /**
061: * Sorts keys and values in parallel.
062: * @param keys the keys to use for sorting.
063: * @param values the values associated with the keys.
064: */
065: public void sort(Object[] keys, Object[] values) {
066: if ((keys == null) || (values == null)) {
067: Assert.isTrue(false, "Either keys or values in null"); //$NON-NLS-1$
068: return;
069: }
070:
071: if (keys.length <= 1) {
072: return;
073: }
074:
075: internalSort(keys, values, 0, keys.length - 1);
076: }
077:
078: private void internalSort(Object[] keys, Object[] values, int left,
079: int right) {
080: int original_left = left;
081: int original_right = right;
082:
083: Object mid = keys[(left + right) / 2];
084: do {
085: while (fComparator.compare(keys[left], mid) < 0) {
086: left++;
087: }
088:
089: while (fComparator.compare(mid, keys[right]) < 0) {
090: right--;
091: }
092:
093: if (left <= right) {
094: swap(keys, left, right);
095: swap(values, left, right);
096: left++;
097: right--;
098: }
099: } while (left <= right);
100:
101: if (original_left < right) {
102: internalSort(keys, values, original_left, right);
103: }
104:
105: if (left < original_right) {
106: internalSort(keys, values, left, original_right);
107: }
108: }
109:
110: /*
111: * Swaps x[a] with x[b].
112: */
113: private static final void swap(Object x[], int a, int b) {
114: Object t = x[a];
115: x[a] = x[b];
116: x[b] = t;
117: }
118:
119: }
|