Collections Data Structure Java

// HTMLParser Library - A java-based parser for HTML
// http://htmlparser.org
// Copyright (C) 2006 Derrick Oswald
//
// Revision Control Information
//
// $URL: https://svn.sourceforge.net/svnroot/htmlparser/trunk/lexer/src/main/java/org/htmlparser/util/sort/Sort.java $
// $Author: derrickoswald $
// $Date: 2006-09-16 10:44:17 -0400 (Sat, 16 Sep 2006) $
// $Revision: 4 $
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the Common Public License; either
// version 1.0 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// Common Public License for more details.
//
// You should have received a copy of the Common Public License
// along with this library; if not, the license is available from
// the Open Source Initiative (OSI) website:
//   http://opensource.org/licenses/cpl1.0.php
//package org.htmlparser.util.sort;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;
/**
 * A quick sort algorithm to sort Vectors or arrays. Provides sort and binary
 * search capabilities.
 * 


 * This all goes away in JDK 1.2.
 * 


 * 
 * @author James Gosling
 * @author Kevin A. Smith
 * @author Derrick Oswald
 * @version 1.4, 11 June, 1997
 */
public class Sort {
  /**
   * No object of this class need ever be instantiated. All methods are
   * static.
   */
  private Sort() {
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle vectors that are already sorted, and vectors with duplicate
   * keys. Equivalent to:
   * 
   * 


   * QuickSort(v, 0, v.size() - 1);
   * 

   * 
   * @param v
   *            A Vector of Ordered items.
   * @exception ClassCastException
   *                If the vector contains objects that are not
   *                Ordered.
   */
  public static void QuickSort(Vector v) throws ClassCastException {
    QuickSort(v, 0, v.size() - 1);
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle vectors that are already sorted, and vectors with duplicate
   * keys.
   * 


   * If you think of a one dimensional vector as going from the lowest index
   * on the left to the highest index on the right then the parameters to this
   * function are lowest index or left and highest index or right.
   * 
   * @param v
   *            A Vector of Ordered items.
   * @param lo0
   *            Left boundary of vector partition.
   * @param hi0
   *            Right boundary of vector partition.
   * @exception ClassCastException
   *                If the vector contains objects that are not
   *                Ordered.
   */
  public static void QuickSort(Vector v, int lo0, int hi0)
      throws ClassCastException {
    int lo = lo0;
    int hi = hi0;
    Ordered mid;
    if (hi0 > lo0) { // arbitrarily establish partition element as the
              // midpoint of the vector
      mid = (Ordered) v.elementAt((lo0 + hi0) / 2);
      // loop through the vector until indices cross
      while (lo <= hi) {
        // find the first element that is greater than or equal to
        // the partition element starting from the left index
        while ((lo < hi0)
            && (0 > ((Ordered) v.elementAt(lo)).compare(mid)))
          ++lo;
        // find an element that is smaller than or equal to
        // the partition element starting from the right index
        while ((hi > lo0)
            && (0 < ((Ordered) v.elementAt(hi)).compare(mid)))
          --hi;
        // if the indexes have not crossed, swap
        if (lo <= hi)
          swap(v, lo++, hi--);
      }
      // if the right index has not reached the left side of array
      // must now sort the left partition
      if (lo0 < hi)
        QuickSort(v, lo0, hi);
      // if the left index has not reached the right side of array
      // must now sort the right partition
      if (lo < hi0)
        QuickSort(v, lo, hi0);
    }
  }
  private static void swap(Vector v, int i, int j) {
    Object o;
    o = v.elementAt(i);
    v.setElementAt(v.elementAt(j), i);
    v.setElementAt(o, j);
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle arrays that are already sorted, and arrays with duplicate
   * keys.
   * 


   * Equivalent to:
   * 
   * 


   * QuickSort(a, 0, a.length - 1);
   * 

   * 
   * @param a
   *            An array of Ordered items.
   */
  public static void QuickSort(Ordered[] a) {
    QuickSort(a, 0, a.length - 1);
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle arrays that are already sorted, and arrays with duplicate
   * keys.
   * 


   * If you think of a one dimensional array as going from the lowest index on
   * the left to the highest index on the right then the parameters to this
   * function are lowest index or left and highest index or right.
   * 
   * @param a
   *            An array of Ordered items.
   * @param lo0
   *            Left boundary of array partition.
   * @param hi0
   *            Right boundary of array partition.
   */
  public static void QuickSort(Ordered[] a, int lo0, int hi0) {
    int lo = lo0;
    int hi = hi0;
    Ordered mid;
    if (hi0 > lo0) {
      // arbitrarily establish partition element as the midpoint of the
      // array
      mid = a[(lo0 + hi0) / 2];
      // loop through the vector until indices cross
      while (lo <= hi) {
        // find the first element that is greater than or equal to
        // the partition element starting from the left index
        while ((lo < hi0) && (0 > a[lo].compare(mid)))
          ++lo;
        // find an element that is smaller than or equal to
        // the partition element starting from the right Index.
        while ((hi > lo0) && (0 < a[hi].compare(mid)))
          --hi;
        // if the indexes have not crossed, swap
        if (lo <= hi)
          swap(a, lo++, hi--);
      }
      // if the right index has not reached the left side of array
      // must now sort the left partition
      if (lo0 < hi)
        QuickSort(a, lo0, hi);
      // if the left index has not reached the right side of array
      // must now sort the right partition
      if (lo < hi0)
        QuickSort(a, lo, hi0);
    }
  }
  /**
   * Swaps two elements of an array.
   * 
   * @param a
   *            The array of elements.
   * @param i
   *            The index of one item to swap.
   * @param j
   *            The index of the other item to swap.
   */
  private static void swap(Object[] a, int i, int j) {
    Object o;
    o = a[i];
    a[i] = a[j];
    a[j] = o;
  }
  /**
   * This is a string version of C.A.R Hoare's Quick Sort algorithm. This will
   * handle arrays that are already sorted, and arrays with duplicate keys.
   * 


   * Equivalent to:
   * 
   * 


   * QuickSort(a, 0, a.length - 1);
   * 

   * 
   * @param a
   *            An array of String items.
   */
  public static void QuickSort(String[] a) {
    QuickSort(a, 0, a.length - 1);
  }
  /**
   * This is a string version of C.A.R Hoare's Quick Sort algorithm. This will
   * handle arrays that are already sorted, and arrays with duplicate keys.
   * 


   * If you think of a one dimensional array as going from the lowest index on
   * the left to the highest index on the right then the parameters to this
   * function are lowest index or left and highest index or right.
   * 
   * @param a
   *            An array of String items.
   * @param lo0
   *            Left boundary of array partition.
   * @param hi0
   *            Right boundary of array partition.
   */
  public static void QuickSort(String[] a, int lo0, int hi0) {
    int lo = lo0;
    int hi = hi0;
    String mid;
    if (hi0 > lo0) {
      // arbitrarily establish partition element as the midpoint of the
      // array
      mid = a[(lo0 + hi0) / 2];
      // loop through the vector until indices cross
      while (lo <= hi) {
        // find the first element that is greater than or equal to
        // the partition element starting from the left index
        while ((lo < hi0) && (0 > a[lo].compareTo(mid)))
          ++lo;
        // find an element that is smaller than or equal to
        // the partition element starting from the right Index.
        while ((hi > lo0) && (0 < a[hi].compareTo(mid)))
          --hi;
        // if the indexes have not crossed, swap
        if (lo <= hi)
          swap(a, lo++, hi--);
      }
      // if the right index has not reached the left side of array
      // must now sort the left partition
      if (lo0 < hi)
        QuickSort(a, lo0, hi);
      // if the left index has not reached the right side of array
      // must now sort the right partition
      if (lo < hi0)
        QuickSort(a, lo, hi0);
    }
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle Sortable objects that are already sorted, and Sortable
   * objects with duplicate keys.
   * 


   * 
   * @param sortable
   *            A Sortable object.
   * @param lo0
   *            Left boundary of partition.
   * @param hi0
   *            Right boundary of partition.
   */
  public static void QuickSort(Sortable sortable, int lo0, int hi0) {
    int lo = lo0;
    int hi = hi0;
    Ordered mid;
    Ordered test;
    if (hi0 > lo0) { // arbitrarily establish partition element as the
              // midpoint of the vector
      mid = sortable.fetch((lo0 + hi0) / 2, null);
      test = null;
      // loop through the vector until indices cross
      while (lo <= hi) {
        // find the first element that is greater than or equal to
        // the partition element starting from the left index
        while ((lo < hi0)
            && (0 > (test = sortable.fetch(lo, test)).compare(mid)))
          ++lo;
        // find an element that is smaller than or equal to
        // the partition element starting from the right index
        while ((hi > lo0)
            && (0 < (test = sortable.fetch(hi, test)).compare(mid)))
          --hi;
        // if the indexes have not crossed, swap
        if (lo <= hi)
          sortable.swap(lo++, hi--);
      }
      // if the right index has not reached the left side of array
      // must now sort the left partition
      if (lo0 < hi)
        QuickSort(sortable, lo0, hi);
      // if the left index has not reached the right side of array
      // must now sort the right partition
      if (lo < hi0)
        QuickSort(sortable, lo, hi0);
    }
  }
  /**
   * This is a generic version of C.A.R Hoare's Quick Sort algorithm. This
   * will handle Sortable objects that are already sorted, and Sortable
   * objects with duplicate keys.
   * 


   * Equivalent to:
   * 
   * 


   * QuickSort(sortable, sortable.first(), sortable.last());
   * 

   * 
   * @param sortable
   *            A Sortable object.
   */
  public static void QuickSort(Sortable sortable) {
    QuickSort(sortable, sortable.first(), sortable.last());
  }
  /**
   * Sort a Hashtable.
   * 
   * @param h
   *            A Hashtable with String or Ordered keys.
   * @return A sorted array of the keys.
   * @exception ClassCastException
   *                If the keys of the hashtable are not Ordered.
   */
  public static Object[] QuickSort(Hashtable h) throws ClassCastException {
    Enumeration e;
    boolean are_strings;
    Object[] ret;
    // make the array
    ret = new Ordered[h.size()];
    e = h.keys();
    are_strings = true; // until proven otherwise
    for (int i = 0; i < ret.length; i++) {
      ret[i] = e.nextElement();
      if (are_strings && !(ret[i] instanceof String))
        are_strings = false;
    }
    // sort it
    if (are_strings)
      QuickSort((String[]) ret);
    else
      QuickSort((Ordered[]) ret);
    return (ret);
  }
  /**
   * Binary search for an object
   * 
   * @param set
   *            The collection of Ordered objects.
   * @param ref
   *            The name to search for.
   * @param lo
   *            The lower index within which to look.
   * @param hi
   *            The upper index within which to look.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Sortable set, Ordered ref, int lo, int hi) {
    int num;
    int mid;
    Ordered ordered;
    int half;
    int result;
    int ret;
    ret = -1;
    num = (hi - lo) + 1;
    ordered = null;
    while ((-1 == ret) && (lo <= hi)) {
      half = num / 2;
      mid = lo + ((0 != (num & 1)) ? half : half - 1);
      ordered = set.fetch(mid, ordered);
      result = ref.compare(ordered);
      if (0 == result)
        ret = mid;
      else if (0 > result) {
        hi = mid - 1;
        num = ((0 != (num & 1)) ? half : half - 1);
      } else {
        lo = mid + 1;
        num = half;
      }
    }
    if (-1 == ret)
      ret = lo;
    return (ret);
  }
  /**
   * Binary search for an object
   * 
   * @param set
   *            The collection of Ordered objects.
   * @param ref
   *            The name to search for.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Sortable set, Ordered ref) {
    return (bsearch(set, ref, set.first(), set.last()));
  }
  /**
   * Binary search for an object
   * 
   * @param vector
   *            The vector of Ordered objects.
   * @param ref
   *            The name to search for.
   * @param lo
   *            The lower index within which to look.
   * @param hi
   *            The upper index within which to look.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Vector vector, Ordered ref, int lo, int hi) {
    int num;
    int mid;
    int half;
    int result;
    int ret;
    ret = -1;
    num = (hi - lo) + 1;
    while ((-1 == ret) && (lo <= hi)) {
      half = num / 2;
      mid = lo + ((0 != (num & 1)) ? half : half - 1);
      result = ref.compare(vector.elementAt(mid));
      if (0 == result)
        ret = mid;
      else if (0 > result) {
        hi = mid - 1;
        num = ((0 != (num & 1)) ? half : half - 1);
      } else {
        lo = mid + 1;
        num = half;
      }
    }
    if (-1 == ret)
      ret = lo;
    return (ret);
  }
  /**
   * Binary search for an object
   * 
   * @param vector
   *            The vector of Ordered objects.
   * @param ref
   *            The name to search for.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Vector vector, Ordered ref) {
    return (bsearch(vector, ref, 0, vector.size() - 1));
  }
  /**
   * Binary search for an object
   * 
   * @param array
   *            The array of Ordered objects.
   * @param ref
   *            The name to search for.
   * @param lo
   *            The lower index within which to look.
   * @param hi
   *            The upper index within which to look.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Ordered[] array, Ordered ref, int lo, int hi) {
    int num;
    int mid;
    int half;
    int result;
    int ret;
    ret = -1;
    num = (hi - lo) + 1;
    while ((-1 == ret) && (lo <= hi)) {
      half = num / 2;
      mid = lo + ((0 != (num & 1)) ? half : half - 1);
      result = ref.compare(array[mid]);
      if (0 == result)
        ret = mid;
      else if (0 > result) {
        hi = mid - 1;
        num = ((0 != (num & 1)) ? half : half - 1);
      } else {
        lo = mid + 1;
        num = half;
      }
    }
    if (-1 == ret)
      ret = lo;
    return (ret);
  }
  /**
   * Binary search for an object
   * 
   * @param array
   *            The array of Ordered objects.
   * @param ref
   *            The name to search for.
   * @return The index at which reference was found or is to be inserted.
   */
  public static int bsearch(Ordered[] array, Ordered ref) {
    return (bsearch(array, ref, 0, array.length - 1));
  }
}
// HTMLParser Library - A java-based parser for HTML
// http://htmlparser.org
// Copyright (C) 2006 Derrick Oswald
//
// Revision Control Information
//
// $URL:
// https://svn.sourceforge.net/svnroot/htmlparser/trunk/lexer/src/main/java/org/htmlparser/util/sort/Ordered.java
// $
// $Author: derrickoswald $
// $Date: 2006-09-16 10:44:17 -0400 (Sat, 16 Sep 2006) $
// $Revision: 4 $
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the Common Public License; either
// version 1.0 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// Common Public License for more details.
//
// You should have received a copy of the Common Public License
// along with this library; if not, the license is available from
// the Open Source Initiative (OSI) website:
// http://opensource.org/licenses/cpl1.0.php
/**
 * Describes an object that knows about ordering. Implementors must have a
 * comparison function, which imposes a partial ordering on some collection of
 * objects. Ordered objects can be passed to a sort method (such as
 * org.htmlparser.util.sort.Sort) to allow precise control over the sort order.
 * 


 * An set of elements S is partially ordered if and only if
 * e1.compare(e2)==0 implies that e1.equals(e2) for
 * every e1 and e2 in S.
 * 


 * This all goes away in JDK 1.2.
 * 


 * For use with java.lang.Comparable from JDK 1.2:
 * 
 * 


 * public int compare(Object o1, Object o2) {
 *   return (((Ordered) o1).compare(o2));
 * }
 * 

 * 
 * @see Sort
 */
interface Ordered {
  /**
   * Compares this object with another for order. Returns a negative integer,
   * zero, or a positive integer as this object is less than, equal to, or
   * greater than the second.
   * 


   * The implementor must ensure that
   * sgn(x.compare(y)) == -sgn(y.compare(x)) for all x and y.
   * (This implies that x.compare(y) must throw an exception if
   * and only if y.compare(x) throws an exception.)
   * 


   * The implementor must also ensure that the relation is transitive:
   * ((x.compare(y)>0) && (y.compare(z)>0)) implies
   * x.compare(z)>0.
   * 


   * Finally, the implementer must ensure that x.compare(y)==0
   * implies that sgn(x.compare(z))==sgn(y.compare(z)) for all z.
   * 
   * @param that
   *            The object to compare this object against.
   * @return A negative integer, zero, or a positive integer as this object is
   *         less than, equal to, or greater than the second.
   * @exception ClassCastException
   *                The arguments type prevents it from being compared by this
   *                Ordered.
   */
  public int compare(Object that);
}
// HTMLParser Library - A java-based parser for HTML
// http://htmlparser.org
// Copyright (C) 2006 Derrick Oswald
//
// Revision Control Information
//
// $URL:
// https://svn.sourceforge.net/svnroot/htmlparser/trunk/lexer/src/main/java/org/htmlparser/util/sort/Sortable.java
// $
// $Author: derrickoswald $
// $Date: 2006-09-16 10:44:17 -0400 (Sat, 16 Sep 2006) $
// $Revision: 4 $
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the Common Public License; either
// version 1.0 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// Common Public License for more details.
//
// You should have received a copy of the Common Public License
// along with this library; if not, the license is available from
// the Open Source Initiative (OSI) website:
// http://opensource.org/licenses/cpl1.0.php
/**
 * Provides a mechanism to abstract the sort process. Classes implementing this
 * interface are collections of Ordered objects that are to be sorted by the
 * Sort class and are not necessarily Vectors or Arrays of Ordered objects.
 * 
 * @see Sort
 */
interface Sortable {
  /**
   * Returns the first index of the Sortable.
   * 
   * @return The index of the first element.
   */
  public int first();
  /**
   * Returns the last index of the Sortable.
   * 
   * @return The index of the last element. If this were an array object this
   *         would be (object.length - 1).
   */
  public int last();
  /**
   * Fetch the object at the given index.
   * 
   * @param index
   *            The item number to get.
   * @param reuse
   *            If this argument is not null, it is an object acquired from a
   *            previous fetch that is no longer needed and may be returned as
   *            the result if it makes mores sense to alter and return it than
   *            to fetch or create a new element. That is, the reuse object is
   *            garbage and may be used to avoid allocating a new object if
   *            that would normally be the strategy.
   * @return The Ordered object at that index.
   */
  public Ordered fetch(int index, Ordered reuse);
  /**
   * Swaps the elements at the given indicies.
   * 
   * @param i
   *            One index.
   * @param j
   *            The other index.
   */
  public void swap(int i, int j);
}