01: /*
02: * The contents of this file are subject to the Mozilla Public License
03: * Version 1.1 (the "License"); you may not use this file except in
04: * compliance with the License. You may obtain a copy of the License at
05: * http://www.mozilla.org/MPL/
06: *
07: * Software distributed under the License is distributed on an "AS IS"
08: * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
09: * License for the specific language governing rights and limitations
10: * under the License.
11: *
12: * The Original Code is iSQL-Viewer, A Mutli-Platform Database Tool.
13: *
14: * The Initial Developer of the Original Code is iSQL-Viewer, A Mutli-Platform Database Tool.
15: * Portions created by Mark A. Kobold are Copyright (C) 2000-2007. All Rights Reserved.
16: *
17: * Contributor(s):
18: * Mark A. Kobold [mkobold <at> isqlviewer <dot> com].
19: *
20: * If you didn't download this code from the following link, you should check
21: * if you aren't using an obsolete version: http://www.isqlviewer.com
22: */
23: package org.isqlviewer.swing.outline;
24:
25: /**
26: * An implementation of MergeSort, needs to be subclassed to compare the terms.
27: * <p>
28: *
29: * @author Scott Violet
30: */
31: public abstract class MergeSort extends Object {
32:
33: protected Object toSort[];
34: protected Object swapSpace[];
35:
36: public void sort(Object array[]) {
37:
38: if (array != null && array.length > 1) {
39: int maxLength;
40:
41: maxLength = array.length;
42: swapSpace = new Object[maxLength];
43: toSort = array;
44: this .mergeSort(0, maxLength - 1);
45: swapSpace = null;
46: toSort = null;
47: }
48: }
49:
50: public abstract int compareElementsAt(int beginLoc, int endLoc);
51:
52: protected void mergeSort(int begin, int end) {
53:
54: if (begin != end) {
55: int mid;
56:
57: mid = (begin + end) / 2;
58: this .mergeSort(begin, mid);
59: this .mergeSort(mid + 1, end);
60: this .merge(begin, mid, end);
61: }
62: }
63:
64: protected void merge(int begin, int middle, int end) {
65:
66: int firstHalf, secondHalf, count;
67:
68: firstHalf = count = begin;
69: secondHalf = middle + 1;
70: while ((firstHalf <= middle) && (secondHalf <= end)) {
71: if (this .compareElementsAt(secondHalf, firstHalf) < 0)
72: swapSpace[count++] = toSort[secondHalf++];
73: else
74: swapSpace[count++] = toSort[firstHalf++];
75: }
76: if (firstHalf <= middle) {
77: while (firstHalf <= middle)
78: swapSpace[count++] = toSort[firstHalf++];
79: } else {
80: while (secondHalf <= end)
81: swapSpace[count++] = toSort[secondHalf++];
82: }
83: for (count = begin; count <= end; count++)
84: toSort[count] = swapSpace[count];
85: }
86: }
|