1 /*
2 * %W% %E%
3 *
4 * Copyright 1997, 1998 Sun Microsystems, Inc. All Rights Reserved.
5 *
6 * Redistribution and use in source and binary forms, with or
7 * without modification, are permitted provided that the following
8 * conditions are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * - Redistribution in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials
16 * provided with the distribution.
17 *
18 * Neither the name of Sun Microsystems, Inc. or the names of
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
21 *
22 * This software is provided "AS IS," without a warranty of any
23 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
24 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
25 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
26 * EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY
27 * DAMAGES OR LIABILITIES SUFFERED BY LICENSEE AS A RESULT OF OR
28 * RELATING TO USE, MODIFICATION OR DISTRIBUTION OF THIS SOFTWARE OR
29 * ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE
30 * FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT,
31 * SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
32 * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF
33 * THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS
34 * BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
35 *
36 * You acknowledge that this software is not designed, licensed or
37 * intended for use in the design, construction, operation or
38 * maintenance of any nuclear facility.
39 */
40
41 package uk.ac.rdg.resc.jstyx.client.browser;
42
43 /***
44 * An implementation of MergeSort, needs to be subclassed to provide a
45 * comparator.
46 *
47 * @version %I% %G%
48 *
49 * @author Scott Violet
50 */
51 public abstract class MergeSort extends Object {
52 protected Object toSort[];
53 protected Object swapSpace[];
54
55 public void sort(Object array[]) {
56 if(array != null && array.length > 1)
57 {
58 int maxLength;
59
60 maxLength = array.length;
61 swapSpace = new Object[maxLength];
62 toSort = array;
63 this.mergeSort(0, maxLength - 1);
64 swapSpace = null;
65 toSort = null;
66 }
67 }
68
69 public abstract int compareElementsAt(int beginLoc, int endLoc);
70
71 protected void mergeSort(int begin, int end) {
72 if(begin != end)
73 {
74 int mid;
75
76 mid = (begin + end) / 2;
77 this.mergeSort(begin, mid);
78 this.mergeSort(mid + 1, end);
79 this.merge(begin, mid, end);
80 }
81 }
82
83 protected void merge(int begin, int middle, int end) {
84 int firstHalf, secondHalf, count;
85
86 firstHalf = count = begin;
87 secondHalf = middle + 1;
88 while((firstHalf <= middle) && (secondHalf <= end))
89 {
90 if(this.compareElementsAt(secondHalf, firstHalf) < 0)
91 swapSpace[count++] = toSort[secondHalf++];
92 else
93 swapSpace[count++] = toSort[firstHalf++];
94 }
95 if(firstHalf <= middle)
96 {
97 while(firstHalf <= middle)
98 swapSpace[count++] = toSort[firstHalf++];
99 }
100 else
101 {
102 while(secondHalf <= end)
103 swapSpace[count++] = toSort[secondHalf++];
104 }
105 for(count = begin;count <= end;count++)
106 toSort[count] = swapSpace[count];
107 }
108 }
109