sort.java

html 解析处理代码

// HTMLParser Library $Name: v1_6 $ - A java-based parser for HTML
// http://sourceforge.org/projects/htmlparser
// Copyright (C) 2004 Derrick Oswald
//
// Revision Control Information
//
// $Source: /cvsroot/htmlparser/htmlparser/src/org/htmlparser/util/sort/Sort.java,v $
// $Author: derrickoswald $
// $Date: 2004/01/14 02:53:47 $
// $Revision: 1.12 $
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 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 GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//

package org.htmlparser.util.sort;

import java.util.*;

/**
 * A quick sort algorithm to sort Vectors or arrays.
 * Provides sort and binary search capabilities.
 *<p>
 * This all goes away in JDK 1.2.
 * <p>
 * @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:
     * <pre>
     * QuickSort (v, 0, v.size () - 1);
     * </pre>
     * @param v A <code>Vector</code> of <code>Ordered</code> items.
     * @exception ClassCastException If the vector contains objects that
     * are not <code>Ordered</code>.
     */
    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.
     * <p>
     * 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 <code>Vector</code> of <code>Ordered</code> 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 <code>Ordered</code>.
     */
    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.
     * <p>
     * Equivalent to:
     * <pre>
     * QuickSort (a, 0, a.length - 1);
     * </pre>
     * @param a An array of <code>Ordered</code> 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.
     * <p>
     * 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 <code>Ordered</code> 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.
     * <p>
     * Equivalent to:
     * <pre>
     * QuickSort (a, 0, a.length - 1);
     * </pre>
     * @param a An array of <code>String</code> 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.
     * <p>
     * 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 <code>String</code> 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