001: /**
002: * com.mckoi.util.SortUtil 29 Mar 1998
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.util;
024:
025: import java.util.Arrays;
026:
027: /**
028: * Provides various sort utilities for a list of objects that implement
029: * Comparable. It also provide some methods that can be used on a sorted
030: * list of objects, such as a fast search method.
031: * <p>
032: * All the methods in this class are static.
033: * <p>
034: * @author Tobias Downer
035: */
036:
037: public final class SortUtil {
038:
039: /**
040: * Performs a quick sort on the given array of Comparable objects between
041: * the min and maximum range. It changes the array to the new sorted order.
042: */
043: public static void quickSort(Comparable[] list, int min, int max) {
044: Arrays.sort(list, min, max + 1);
045:
046: // int left = min;
047: // int right = max;
048: //
049: // if (max > min) {
050: // Comparable mid = list[(min + max) / 2];
051: // while (left < right) {
052: // while (left < max && list[left].compareTo(mid) < 0) {
053: // ++left;
054: // }
055: // while (right > min && list[right].compareTo(mid) > 0) {
056: // --right;
057: // }
058: // if (left <= right) {
059: // if (left != right) {
060: // Comparable t = list[left];
061: // list[left] = list[right];
062: // list[right] = t;
063: // }
064: //
065: // ++left;
066: // --right;
067: // }
068: //
069: // }
070: //
071: // if (min < right) {
072: // quickSort(list, min, right);
073: // }
074: // if (left < max) {
075: // quickSort(list, left, max);
076: // }
077: //
078: // }
079: }
080:
081: /**
082: * Performs a quick sort on the given array of Comparable objects.
083: * It changes the array to the new sorted order.
084: */
085: public static void quickSort(Comparable[] obs) {
086: quickSort(obs, 0, obs.length - 1);
087: }
088:
089: /**
090: * Quickly finds the index of the given object in the list. If the object
091: * can not be found, it returns the point where the element should be
092: * added.
093: */
094: public static int sortedIndexOf(Comparable[] list, Comparable val,
095: int lower, int higher) {
096:
097: if (lower >= higher) {
098: if (val.compareTo(list[lower]) > 0) {
099: return lower + 1;
100: } else {
101: return lower;
102: }
103: }
104:
105: int mid = (lower + higher) / 2;
106: Comparable mid_val = list[mid];
107:
108: if (val.equals(mid_val)) {
109: return mid;
110: } else if (val.compareTo(mid_val) < 0) {
111: return sortedIndexOf(list, val, lower, mid - 1);
112: } else {
113: return sortedIndexOf(list, val, mid + 1, higher);
114: }
115:
116: }
117:
118: /**
119: * Quickly finds the given element in the array of objects. It assumes
120: * the object given is of the same type as the array. It returns null if
121: * the given object is not in the array. If the object is in the array, it
122: * returns a SearchResults object that contains information about the index
123: * of the found object, and the number of objects like this in the array.
124: * Not that it takes a 'SearchResults' object to store the results in. This
125: * is for reuse of an old SearchResults object that is no longer needed.
126: * This prevents gc and overhead of having to allocate a new SearchResults
127: * object.
128: * This method works by dividing the search space in half and iterating in
129: * the half with the given object in.
130: */
131: public static SearchResults sortedQuickFind(Comparable[] list,
132: Comparable val, SearchResults results) {
133: if (list.length == 0) {
134: return null;
135: }
136:
137: int size = list.length - 1;
138: int count = 0;
139:
140: int i = sortedIndexOf(list, val, 0, size);
141: if (i > size) {
142: return null;
143: }
144: int temp_i = i;
145:
146: while (temp_i >= 0 && list[temp_i].equals(val)) {
147: ++count;
148: --temp_i;
149: }
150: int start_index = temp_i + 1;
151: temp_i = i + 1;
152: while (temp_i <= size && list[temp_i].equals(val)) {
153: ++count;
154: ++temp_i;
155: }
156:
157: if (count == 0) {
158: return null;
159: } else {
160: if (results == null) {
161: results = new SearchResults();
162: }
163: results.found_index = start_index;
164: results.found_count = count;
165: }
166:
167: return results;
168: }
169:
170: }
|