Sort.java
1 // HTMLParser Library $Name: v1_6_20060319 $ - A java-based parser for HTML 2 // http://sourceforge.org/projects/htmlparser 3 // Copyright (C) 2004 Derrick Oswald 4 // 5 // Revision Control Information 6 // 7 // $Source: /cvsroot/htmlparser/htmlparser/src/org/htmlparser/util/sort/Sort.java,v $ 8 // $Author: derrickoswald $ 9 // $Date: 2004/01/14 02:53:47 $ 10 // $Revision: 1.12 $ 11 // 12 // This library is free software; you can redistribute it and/or 13 // modify it under the terms of the GNU Lesser General Public 14 // License as published by the Free Software Foundation; either 15 // version 2.1 of the License, or (at your option) any later version. 16 // 17 // This library is distributed in the hope that it will be useful, 18 // but WITHOUT ANY WARRANTY; without even the implied warranty of 19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 20 // Lesser General Public License for more details. 21 // 22 // You should have received a copy of the GNU Lesser General Public 23 // License along with this library; if not, write to the Free Software 24 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 25 // 26 27 package org.htmlparser.util.sort; 28 29 import java.util.*; 30 31 /** 32 * A quick sort algorithm to sort Vectors or arrays. 33 * Provides sort and binary search capabilities. 34 *<p> 35 * This all goes away in JDK 1.2. 36 * <p> 37 * @author James Gosling 38 * @author Kevin A. Smith 39 * @author Derrick Oswald 40 * @version 1.4, 11 June, 1997 41 */ 42 public class Sort 43 { 44 /** 45 * No object of this class need ever be instantiated. 46 * All methods are static. 47 */ 48 private Sort () 49 { 50 } 51 52 /** 53 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 54 * This will handle vectors that are already 55 * sorted, and vectors with duplicate keys. 56 * Equivalent to: 57 * <pre> 58 * QuickSort (v, 0, v.size () - 1); 59 * </pre> 60 * @param v A <code>Vector</code> of <code>Ordered</code> items. 61 * @exception ClassCastException If the vector contains objects that 62 * are not <code>Ordered</code>. 63 */ 64 public static void QuickSort (Vector v) throws ClassCastException 65 { 66 QuickSort (v, 0, v.size () - 1); 67 } 68 69 /** 70 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 71 * This will handle vectors that are already 72 * sorted, and vectors with duplicate keys. 73 * <p> 74 * If you think of a one dimensional vector as going from 75 * the lowest index on the left to the highest index on the right 76 * then the parameters to this function are lowest index or 77 * left and highest index or right. 78 * @param v A <code>Vector</code> of <code>Ordered</code> items. 79 * @param lo0 Left boundary of vector partition. 80 * @param hi0 Right boundary of vector partition. 81 * @exception ClassCastException If the vector contains objects that 82 * are not <code>Ordered</code>. 83 */ 84 public static void QuickSort (Vector v, int lo0, int hi0) throws ClassCastException 85 { 86 int lo = lo0; 87 int hi = hi0; 88 Ordered mid; 89 90 if ( hi0 > lo0) 91 { // arbitrarily establish partition element as the midpoint of the vector 92 mid = (Ordered)v.elementAt((lo0 + hi0) / 2); 93 94 // loop through the vector until indices cross 95 while (lo <= hi) 96 { 97 // find the first element that is greater than or equal to 98 // the partition element starting from the left index 99 while ((lo < hi0) && (0 > ((Ordered)v.elementAt (lo)).compare (mid))) 100 ++lo; 101 102 // find an element that is smaller than or equal to 103 // the partition element starting from the right index 104 while ((hi > lo0) && (0 < ((Ordered)v.elementAt (hi)).compare (mid))) 105 --hi; 106 107 // if the indexes have not crossed, swap 108 if (lo <= hi) 109 swap (v, lo++, hi--); 110 } 111 112 // if the right index has not reached the left side of array 113 // must now sort the left partition 114 if (lo0 < hi) 115 QuickSort (v, lo0, hi); 116 117 // if the left index has not reached the right side of array 118 // must now sort the right partition 119 if (lo < hi0) 120 QuickSort (v, lo, hi0); 121 } 122 } 123 124 private static void swap (Vector v, int i, int j) 125 { 126 Object o; 127 128 o = v.elementAt (i); 129 v.setElementAt (v.elementAt (j), i); 130 v.setElementAt (o, j); 131 } 132 133 /** 134 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 135 * This will handle arrays that are already sorted, 136 * and arrays with duplicate keys. 137 * <p> 138 * Equivalent to: 139 * <pre> 140 * QuickSort (a, 0, a.length - 1); 141 * </pre> 142 * @param a An array of <code>Ordered</code> items. 143 */ 144 public static void QuickSort (Ordered[] a) 145 { 146 QuickSort (a, 0, a.length - 1); 147 } 148 149 /** 150 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 151 * This will handle arrays that are already sorted, 152 * and arrays with duplicate keys. 153 * <p> 154 * If you think of a one dimensional array as going from 155 * the lowest index on the left to the highest index on the right 156 * then the parameters to this function are lowest index or 157 * left and highest index or right. 158 * @param a An array of <code>Ordered</code> items. 159 * @param lo0 Left boundary of array partition. 160 * @param hi0 Right boundary of array partition. 161 */ 162 public static void QuickSort (Ordered[] a, int lo0, int hi0) 163 { 164 int lo = lo0; 165 int hi = hi0; 166 Ordered mid; 167 168 if ( hi0 > lo0) 169 { 170 // arbitrarily establish partition element as the midpoint of the array 171 mid = a[(lo0 + hi0) / 2]; 172 173 // loop through the vector until indices cross 174 while (lo <= hi) 175 { 176 // find the first element that is greater than or equal to 177 // the partition element starting from the left index 178 while ((lo < hi0) && (0 > a[lo].compare (mid))) 179 ++lo; 180 181 // find an element that is smaller than or equal to 182 // the partition element starting from the right Index. 183 while ((hi > lo0) && (0 < a[hi].compare (mid))) 184 --hi; 185 186 // if the indexes have not crossed, swap 187 if (lo <= hi) 188 swap (a, lo++, hi--); 189 } 190 191 // if the right index has not reached the left side of array 192 // must now sort the left partition 193 if (lo0 < hi) 194 QuickSort (a, lo0, hi); 195 196 // if the left index has not reached the right side of array 197 // must now sort the right partition 198 if (lo < hi0) 199 QuickSort (a, lo, hi0); 200 } 201 } 202 203 /** 204 * Swaps two elements of an array. 205 * @param a The array of elements. 206 * @param i The index of one item to swap. 207 * @param j The index of the other item to swap. 208 */ 209 private static void swap (Object[] a, int i, int j) 210 { 211 Object o; 212 o = a[i]; 213 a[i] = a[j]; 214 a[j] = o; 215 } 216 217 /** 218 * This is a string version of C.A.R Hoare's Quick Sort algorithm. 219 * This will handle arrays that are already sorted, 220 * and arrays with duplicate keys. 221 * <p> 222 * Equivalent to: 223 * <pre> 224 * QuickSort (a, 0, a.length - 1); 225 * </pre> 226 * @param a An array of <code>String</code> items. 227 */ 228 public static void QuickSort (String[] a) 229 { 230 QuickSort (a, 0, a.length - 1); 231 } 232 233 /** 234 * This is a string version of C.A.R Hoare's Quick Sort algorithm. 235 * This will handle arrays that are already sorted, 236 * and arrays with duplicate keys. 237 * <p> 238 * If you think of a one dimensional array as going from 239 * the lowest index on the left to the highest index on the right 240 * then the parameters to this function are lowest index or 241 * left and highest index or right. 242 * @param a An array of <code>String</code> items. 243 * @param lo0 Left boundary of array partition. 244 * @param hi0 Right boundary of array partition. 245 */ 246 public static void QuickSort (String[] a, int lo0, int hi0) 247 { 248 int lo = lo0; 249 int hi = hi0; 250 String mid; 251 252 if ( hi0 > lo0) 253 { 254 // arbitrarily establish partition element as the midpoint of the array 255 mid = a[(lo0 + hi0) / 2]; 256 257 // loop through the vector until indices cross 258 while (lo <= hi) 259 { 260 // find the first element that is greater than or equal to 261 // the partition element starting from the left index 262 while ((lo < hi0) && (0 > a[lo].compareTo (mid))) 263 ++lo; 264 265 // find an element that is smaller than or equal to 266 // the partition element starting from the right Index. 267 while ((hi > lo0) && (0 < a[hi].compareTo (mid))) 268 --hi; 269 270 // if the indexes have not crossed, swap 271 if (lo <= hi) 272 swap (a, lo++, hi--); 273 } 274 275 // if the right index has not reached the left side of array 276 // must now sort the left partition 277 if (lo0 < hi) 278 QuickSort (a, lo0, hi); 279 280 // if the left index has not reached the right side of array 281 // must now sort the right partition 282 if (lo < hi0) 283 QuickSort (a, lo, hi0); 284 } 285 } 286 287 /** 288 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 289 * This will handle Sortable objects that are already 290 * sorted, and Sortable objects with duplicate keys. 291 * <p> 292 * @param sortable A <code>Sortable</code> object. 293 * @param lo0 Left boundary of partition. 294 * @param hi0 Right boundary of partition. 295 */ 296 public static void QuickSort (Sortable sortable, int lo0, int hi0) 297 { 298 int lo = lo0; 299 int hi = hi0; 300 Ordered mid; 301 Ordered test; 302 303 if ( hi0 > lo0) 304 { // arbitrarily establish partition element as the midpoint of the vector 305 mid = sortable.fetch ((lo0 + hi0) / 2, null); 306 test = null; 307 308 // loop through the vector until indices cross 309 while (lo <= hi) 310 { 311 // find the first element that is greater than or equal to 312 // the partition element starting from the left index 313 while ((lo < hi0) && (0 > (test = sortable.fetch (lo, test)).compare (mid))) 314 ++lo; 315 316 // find an element that is smaller than or equal to 317 // the partition element starting from the right index 318 while ((hi > lo0) && (0 < (test = sortable.fetch (hi, test)).compare (mid))) 319 --hi; 320 321 // if the indexes have not crossed, swap 322 if (lo <= hi) 323 sortable.swap (lo++, hi--); 324 } 325 326 // if the right index has not reached the left side of array 327 // must now sort the left partition 328 if (lo0 < hi) 329 QuickSort (sortable, lo0, hi); 330 331 // if the left index has not reached the right side of array 332 // must now sort the right partition 333 if (lo < hi0) 334 QuickSort (sortable, lo, hi0); 335 } 336 } 337 338 /** 339 * This is a generic version of C.A.R Hoare's Quick Sort algorithm. 340 * This will handle Sortable objects that are already 341 * sorted, and Sortable objects with duplicate keys. 342 * <p> 343 * Equivalent to: 344 * <pre> 345 * QuickSort (sortable, sortable.first (), sortable.last ()); 346 * </pre> 347 * @param sortable A <code>Sortable</code> object. 348 */ 349 public static void QuickSort (Sortable sortable) 350 { 351 QuickSort (sortable, sortable.first (), sortable.last ()); 352 } 353 354 /** 355 * Sort a Hashtable. 356 * @param h A Hashtable with String or Ordered keys. 357 * @return A sorted array of the keys. 358 * @exception ClassCastException If the keys of the hashtable 359 * are not <code>Ordered</code>. 360 */ 361 public static Object[] QuickSort (Hashtable h) throws ClassCastException 362 { 363 Enumeration e; 364 boolean are_strings; 365 Object[] ret; 366 367 // make the array 368 ret = new Ordered[h.size ()]; 369 e = h.keys (); 370 are_strings = true; // until proven otherwise 371 for (int i = 0; i < ret.length; i++) 372 { 373 ret[i] = e.nextElement (); 374 if (are_strings && !(ret[i] instanceof String)) 375 are_strings = false; 376 } 377 378 // sort it 379 if (are_strings) 380 QuickSort ((String[])ret); 381 else 382 QuickSort ((Ordered[])ret); 383 384 return (ret); 385 } 386 387 /** 388 * Binary search for an object 389 * @param set The collection of <code>Ordered</code> objects. 390 * @param ref The name to search for. 391 * @param lo The lower index within which to look. 392 * @param hi The upper index within which to look. 393 * @return The index at which reference was found or is to be inserted. 394 */ 395 public static int bsearch (Sortable set, Ordered ref, int lo, int hi) 396 { int num; 397 int mid; 398 Ordered ordered; 399 int half; 400 int result; 401 int ret; 402 403 ret = -1; 404 405 num = (hi - lo) + 1; 406 ordered = null; 407 while ((-1 == ret) && (lo <= hi)) 408 { 409 half = num / 2; 410 mid = lo + ((0 != (num & 1)) ? half : half - 1); 411 ordered = set.fetch (mid, ordered); 412 result = ref.compare (ordered); 413 if (0 == result) 414 ret = mid; 415 else if (0 > result) 416 { 417 hi = mid - 1; 418 num = ((0 != (num & 1)) ? half : half - 1); 419 } 420 else 421 { 422 lo = mid + 1; 423 num = half; 424 } 425 } 426 if (-1 == ret) 427 ret = lo; 428 429 return (ret); 430 } 431 432 /** 433 * Binary search for an object 434 * @param set The collection of <code>Ordered</code> objects. 435 * @param ref The name to search for. 436 * @return The index at which reference was found or is to be inserted. 437 */ 438 public static int bsearch (Sortable set, Ordered ref) 439 { 440 return (bsearch (set, ref, set.first (), set.last ())); 441 } 442 443 /** 444 * Binary search for an object 445 * @param vector The vector of <code>Ordered</code> objects. 446 * @param ref The name to search for. 447 * @param lo The lower index within which to look. 448 * @param hi The upper index within which to look. 449 * @return The index at which reference was found or is to be inserted. 450 */ 451 public static int bsearch (Vector vector, Ordered ref, int lo, int hi) 452 { int num; 453 int mid; 454 int half; 455 int result; 456 int ret; 457 458 ret = -1; 459 460 num = (hi - lo) + 1; 461 while ((-1 == ret) && (lo <= hi)) 462 { 463 half = num / 2; 464 mid = lo + ((0 != (num & 1)) ? half : half - 1); 465 result = ref.compare (vector.elementAt (mid)); 466 if (0 == result) 467 ret = mid; 468 else if (0 > result) 469 { 470 hi = mid - 1; 471 num = ((0 != (num & 1)) ? half : half - 1); 472 } 473 else 474 { 475 lo = mid + 1; 476 num = half; 477 } 478 } 479 if (-1 == ret) 480 ret = lo; 481 482 return (ret); 483 } 484 485 /** 486 * Binary search for an object 487 * @param vector The vector of <code>Ordered</code> objects. 488 * @param ref The name to search for. 489 * @return The index at which reference was found or is to be inserted. 490 */ 491 public static int bsearch (Vector vector, Ordered ref) 492 { 493 return (bsearch (vector, ref, 0, vector.size () - 1)); 494 } 495 496 /** 497 * Binary search for an object 498 * @param array The array of <code>Ordered</code> objects. 499 * @param ref The name to search for. 500 * @param lo The lower index within which to look. 501 * @param hi The upper index within which to look. 502 * @return The index at which reference was found or is to be inserted. 503 */ 504 public static int bsearch (Ordered[] array, Ordered ref, int lo, int hi) 505 { int num; 506 int mid; 507 int half; 508 int result; 509 int ret; 510 511 ret = -1; 512 513 num = (hi - lo) + 1; 514 while ((-1 == ret) && (lo <= hi)) 515 { 516 half = num / 2; 517 mid = lo + ((0 != (num & 1)) ? half : half - 1); 518 result = ref.compare (array[mid]); 519 if (0 == result) 520 ret = mid; 521 else if (0 > result) 522 { 523 hi = mid - 1; 524 num = ((0 != (num & 1)) ? half : half - 1); 525 } 526 else 527 { 528 lo = mid + 1; 529 num = half; 530 } 531 } 532 if (-1 == ret) 533 ret = lo; 534 535 return (ret); 536 } 537 538 /** 539 * Binary search for an object 540 * @param array The array of <code>Ordered</code> objects. 541 * @param ref The name to search for. 542 * @return The index at which reference was found or is to be inserted. 543 */ 544 public static int bsearch (Ordered[] array, Ordered ref) 545 { 546 return (bsearch (array, ref, 0, array.length - 1)); 547 } 548 } 549