001: /**
002: * The XMOJO Project 5
003: * Copyright © 2003 XMOJO.org. All rights reserved.
004:
005: * NO WARRANTY
006:
007: * BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR
008: * THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
009: * OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
010: * PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
011: * OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
012: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
013: * TO THE QUALITY AND PERFORMANCE OF THE LIBRARY IS WITH YOU. SHOULD THE
014: * LIBRARY PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
015: * REPAIR OR CORRECTION.
016:
017: * IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL
018: * ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE
019: * THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY
020: * GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
021: * USE OR INABILITY TO USE THE LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF
022: * DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD
023: * PARTIES OR A FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE),
024: * EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
025: * SUCH DAMAGES.
026: **/package com.adventnet.jmx.utils;
027:
028: /**
029: * This is a utility class which sorts a objectID array using
030: * quick sort mechanism .By default the compareTo method compares
031: * two strings str1 & str2 considering it to be a OID string. API
032: * users may override this method inorder to have their own compareTo
033: * method incase of different type of string.
034: * <p>
035: * Usage is :
036: * <li>sorter = new Sorter();
037: * <li>toSort = new String[2]{".1.3.6.1.3.2", ".1.3.6.1.3.12",};
038: * <li>sorter.sort(toSort, null);
039: */
040: public class Sorter implements java.io.Serializable {
041:
042: /** This is a generic version of C.A.R Hoare's Quick Sort
043: * algorithm. This will handle arrays that are already
044: * sorted, and arrays with duplicate keys.<BR>
045: *
046: * If you think of a one dimensional array as going from
047: * the lowest index on the left to the highest index on the right
048: * then the parameters to this function are lowest index or
049: * left and highest index or right. The first time you call
050: * this function it will be with the parameters 0, a.length - 1.
051: *
052: * @param a an integer array
053: * @param lo0 left boundary of array partition
054: * @param hi0 right boundary of array partition
055: */
056: public void QuickSort(String a[], int lo0, int hi0)
057: throws Exception {
058: int lo = lo0;
059: int hi = hi0;
060: String mid;
061:
062: if (hi0 > lo0) {
063:
064: /* Arbitrarily establishing partition element as the midpoint of
065: * the array.
066: */
067: mid = a[(lo0 + hi0) / 2];
068:
069: // loop through the array until indices cross
070: while (lo <= hi) {
071: /* find the first element that is greater than or equal to
072: * the partition element starting from the left Index.
073: */
074: while ((lo < hi0) && (compareTo(a[lo], mid) < 0))
075: ++lo;
076:
077: /* find an element that is smaller than or equal to
078: * the partition element starting from the right Index.
079: */
080: while ((hi > lo0) && (compareTo(a[hi], mid) > 0))
081: --hi;
082:
083: // if the indexes have not crossed, swap
084: if (lo <= hi) {
085: swap(a, lo, hi);
086: ++lo;
087: --hi;
088: }
089: }
090:
091: /* If the right index has not reached the left side of array
092: * must now sort the left partition.
093: */
094: if (lo0 < hi)
095: QuickSort(a, lo0, hi);
096:
097: /* If the left index has not reached the right side of array
098: * must now sort the right partition.
099: */
100: if (lo < hi0)
101: QuickSort(a, lo, hi0);
102:
103: }
104: }
105:
106: /**
107: * This method compares two string considering it be
108: * OID string. API users may override this method incase
109: * if they want to have different compareTo method.
110: */
111:
112: private int compareTo(String str1, String str2) {
113: int ret = str1.compareTo(str2);
114:
115: if (ret > 0)
116: return 1;
117: if (ret < 0)
118: return -1;
119: return 0;
120: }
121:
122: private void swap(String a[], int i, int j) {
123: Object T;
124: T = a[i];
125: a[i] = a[j];
126: a[j] = (String) T;
127:
128: if (obj != null) {
129:
130: int max = obj.length;
131:
132: for (int pos = 0; pos < max; pos++) {
133: Object[] b = obj[pos];
134: T = b[i];
135: b[i] = b[j];
136: b[j] = T;
137: }
138: }
139:
140: }
141:
142: Object[][] obj = null;
143:
144: /**
145: * This method sorts the OID string array in ascending order.
146: * Also it sorts multi array objects in "obj" according to the key
147: * OID string array "a".
148: * @param a the key string array to be sorted.
149: * @param obj the multiarray objects which are sorted according to the
150: * key oid.
151: */
152: public void sort(String a[], Object[][] obj) throws Exception {
153: this .obj = obj;
154: QuickSort(a, 0, a.length - 1);
155: }
156:
157: /** This is a generic version of C.A.R Hoare's Quick Sort
158: * algorithm. This will handle arrays that are already
159: * sorted, and arrays with duplicate keys.<BR>
160: *
161: * If you think of a one dimensional array as going from
162: * the lowest index on the left to the highest index on the right
163: * then the parameters to this function are lowest index or
164: * left and highest index or right. The first time you call
165: * this function it will be with the parameters 0, a.length - 1.
166: *
167: * @param a an integer array
168: * @param lo0 left boundary of array partition
169: * @param hi0 right boundary of array partition
170: */
171: public void QuickSort(int a[], int lo0, int hi0) throws Exception {
172: int lo = lo0;
173: int hi = hi0;
174: int mid;
175:
176: if (hi0 > lo0) {
177:
178: /* Arbitrarily establishing partition element as the midpoint of
179: * the array.
180: */
181: mid = a[(lo0 + hi0) / 2];
182:
183: // loop through the array until indices cross
184: while (lo <= hi) {
185: /* find the first element that is greater than or equal to
186: * the partition element starting from the left Index.
187: */
188: while ((lo < hi0) && (a[lo] < mid))
189: ++lo;
190:
191: /* find an element that is smaller than or equal to
192: * the partition element starting from the right Index.
193: */
194: while ((hi > lo0) && (a[hi] > mid))
195: --hi;
196:
197: // if the indexes have not crossed, swap
198: if (lo <= hi) {
199: swap(a, lo, hi);
200: ++lo;
201: --hi;
202: }
203: }
204:
205: /* If the right index has not reached the left side of array
206: * must now sort the left partition.
207: */
208: if (lo0 < hi)
209: QuickSort(a, lo0, hi);
210:
211: /* If the left index has not reached the right side of array
212: * must now sort the right partition.
213: */
214: if (lo < hi0)
215: QuickSort(a, lo, hi0);
216:
217: }
218: }
219:
220: private void swap(int a[], int i, int j) {
221: int T;
222: T = a[i];
223: a[i] = a[j];
224: a[j] = T;
225:
226: }
227:
228: public void sort(int a[]) throws Exception {
229: QuickSort(a, 0, a.length - 1);
230: }
231: }
|