KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > mckoi > util > SortUtil


1 /**
2  * com.mckoi.util.SortUtil 29 Mar 1998
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.util;
26
27 import java.util.Arrays JavaDoc;
28
29 /**
30  * Provides various sort utilities for a list of objects that implement
31  * Comparable. It also provide some methods that can be used on a sorted
32  * list of objects, such as a fast search method.
33  * <p>
34  * All the methods in this class are static.
35  * <p>
36  * @author Tobias Downer
37  */
38
39 public final class SortUtil {
40
41   /**
42    * Performs a quick sort on the given array of Comparable objects between
43    * the min and maximum range. It changes the array to the new sorted order.
44    */
45   public static void quickSort(Comparable JavaDoc[] list, int min, int max) {
46     Arrays.sort(list, min, max + 1);
47
48 // int left = min;
49 // int right = max;
50 //
51 // if (max > min) {
52 // Comparable mid = list[(min + max) / 2];
53 // while (left < right) {
54 // while (left < max && list[left].compareTo(mid) < 0) {
55 // ++left;
56 // }
57 // while (right > min && list[right].compareTo(mid) > 0) {
58 // --right;
59 // }
60 // if (left <= right) {
61 // if (left != right) {
62 // Comparable t = list[left];
63 // list[left] = list[right];
64 // list[right] = t;
65 // }
66 //
67 // ++left;
68 // --right;
69 // }
70 //
71 // }
72 //
73 // if (min < right) {
74 // quickSort(list, min, right);
75 // }
76 // if (left < max) {
77 // quickSort(list, left, max);
78 // }
79 //
80 // }
81 }
82
83   /**
84    * Performs a quick sort on the given array of Comparable objects.
85    * It changes the array to the new sorted order.
86    */
87   public static void quickSort(Comparable JavaDoc[] obs) {
88     quickSort(obs, 0, obs.length - 1);
89   }
90
91
92   /**
93    * Quickly finds the index of the given object in the list. If the object
94    * can not be found, it returns the point where the element should be
95    * added.
96    */
97   public static int sortedIndexOf(Comparable JavaDoc[] list, Comparable JavaDoc val, int lower, int higher) {
98
99     if (lower >= higher) {
100       if (val.compareTo(list[lower]) > 0) {
101         return lower + 1;
102       }
103       else {
104         return lower;
105       }
106     }
107
108     int mid = (lower + higher) / 2;
109     Comparable JavaDoc mid_val = list[mid];
110
111     if (val.equals(mid_val)) {
112       return mid;
113     }
114     else if (val.compareTo(mid_val) < 0) {
115       return sortedIndexOf(list, val, lower, mid - 1);
116     }
117     else {
118       return sortedIndexOf(list, val, mid + 1, higher);
119     }
120
121   }
122
123   /**
124    * Quickly finds the given element in the array of objects. It assumes
125    * the object given is of the same type as the array. It returns null if
126    * the given object is not in the array. If the object is in the array, it
127    * returns a SearchResults object that contains information about the index
128    * of the found object, and the number of objects like this in the array.
129    * Not that it takes a 'SearchResults' object to store the results in. This
130    * is for reuse of an old SearchResults object that is no longer needed.
131    * This prevents gc and overhead of having to allocate a new SearchResults
132    * object.
133    * This method works by dividing the search space in half and iterating in
134    * the half with the given object in.
135    */
136   public static SearchResults sortedQuickFind(Comparable JavaDoc[] list, Comparable JavaDoc val, SearchResults results) {
137     if (list.length == 0) {
138       return null;
139     }
140
141     int size = list.length - 1;
142     int count = 0;
143
144     int i = sortedIndexOf(list, val, 0, size);
145     if (i > size) {
146       return null;
147     }
148     int temp_i = i;
149
150     while (temp_i >= 0 && list[temp_i].equals(val)) {
151       ++count;
152       --temp_i;
153     }
154     int start_index = temp_i + 1;
155     temp_i = i + 1;
156     while (temp_i <= size && list[temp_i].equals(val)) {
157       ++count;
158       ++temp_i;
159     }
160
161     if (count == 0) {
162       return null;
163     }
164     else {
165       if (results == null) {
166         results = new SearchResults();
167       }
168       results.found_index = start_index;
169       results.found_count = count;
170     }
171
172     return results;
173   }
174
175 }
176
Popular Tags