pageindex.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/lexer/PageIndex.java,v $
// $Author: derrickoswald $
// $Date: 2005/05/15 11:49:04 $
// $Revision: 1.18 $
//
// 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.lexer;

import java.io.Serializable;
import org.htmlparser.util.sort.Ordered;
import org.htmlparser.util.sort.Sort;
import org.htmlparser.util.sort.Sortable;

/**
 * A sorted array of integers, the positions of the first characters of each line.
 * To facilitate processing the first element should be maintained at position 0.
 * Facilities to add, remove, search and determine row and column are provided.
 * This class provides similar functionality to a Vector but
 * does not incur the overhead of an <code>Integer</code> object per element.
 */
public class PageIndex
    implements
        Serializable,
        Sortable
{
    /**
     * Starting increment for allocations.
     */
    protected static final int mStartIncrement = 100;

    /**
     * Increment for allocations.
     */
    protected int mIncrement;

    /**
     * The number of valid elements.
     */
    protected int mCount;

    /**
     * The elements.
     */
    protected int[] mIndices;

    /**
     * The page associated with this index.
     */
    protected Page mPage;

    /**
     * Create an empty index.
     * @param page The page associated with this index.
     */
    public PageIndex (Page page)
    {
        mPage = page;
        mIndices = new int[mIncrement];
        mCount = 0;
        mIncrement = mStartIncrement * 2;
    }

    /**
     * Create an index with the one element given.
     * @param page The page associated with this index.
     * @param cursor The single element for the new index.
     */
    public PageIndex (Page page, int cursor)
    {
        this (page);
        mIndices[0] = cursor;
        mCount = 1;
    }

    /**
     * Create an index with the elements given.
     * @param page The page associated with this index.
     * @param cursors The initial elements of the index.
     * NOTE: The list must be sorted in ascending order.
     */
    public PageIndex (Page page, int[] cursors)
    {
        mPage = page;
        mIndices = cursors;
        mCount = cursors.length;
    }

    /**
     * Get this index's page.
     * @return The page associated with this index.
     */
    public Page getPage ()
    {
        return (mPage);
    }

    /**
     * Get the count of elements.
     * @return The number of valid elements.
     */
    public int size ()
    {
        return (mCount);
    }

    /**
     * Get the capacity for elements without reallocation.
     * @return The number of spaces for elements.
     */
    public int capacity ()
    {
        return (mIndices.length);
    }

    /**
     * Add an element to the list
     * @param cursor The element to add.
     * @return The position at which the element was inserted or
     * the index of the existing element if it is a duplicate.
     */
    public int add (Cursor cursor)
    {
        int position;
        int last;
        int ret;

        position = cursor.getPosition ();
        if (0 == mCount)
        {
            ret = 0;
            insertElementAt (position, ret);
        }
        else
        {
            last = mIndices[mCount - 1];
            if (position == last)
                ret = mCount - 1;
            else
                if (position > last)
                {
                    ret = mCount;
                    insertElementAt (position, ret);
                }
                else
                {
        	        // find where it goes
        	        ret = Sort.bsearch (this, cursor);

	                // insert, but not twice
	                if (!((ret < size ()) && (position == mIndices[ret])))
	                    insertElementAt (position, ret);
                }
        }

        return (ret);
    }

    /**
     * Add an element to the list
     * @param cursor The element to add.
     * @return The position at which the element was inserted or
     * the index of the existing element if it is a duplicate.
     */
    public int add (int cursor)
    {
        return (add (new Cursor (getPage (), cursor)));
    }

    /**
     * Remove an element from the list
     * @param cursor The element to remove.
     */
    public void remove (Cursor cursor)
    {
        int i;

        // find it
        i = Sort.bsearch (this, cursor);

        // remove
        if ((i < size ()) && (cursor.getPosition () == mIndices[i]))
            removeElementAt (i);
    }

    /**
     * Remove an element from the list
     * @param cursor The element to remove.
     */
    public void remove (int cursor)
    {
        remove (new Cursor (getPage (), cursor));
    }

    /**
     * Get an element from the list.
     * @param index The index of the element to get.
     * @return The element.
     */
    public int elementAt (int index)
    {
        if (index >= mCount) // negative index is handled by array.. below
            throw new IndexOutOfBoundsException ("index " + index + " beyond current limit");
        else
            return (mIndices[index]);
    }

    /**
     * Get the line number for a cursor.
     * @param cursor The character offset into the page.
     * @return The line number the character is in.
     */
    public int row (Cursor cursor)
    {
        int ret;

        ret = Sort.bsearch (this, cursor);
        // handle line transition, the search returns the index if it matches
        // exactly one of the line end positions, so we advance one line if
        // it's equal to the offset at the row index, since that position is
        // actually the beginning of the next line
        if ((ret < mCount) && (cursor.getPosition () == mIndices[ret]))
            ret++;

        return (ret);
    }

    /**
     * Get the line number for a position.
     * @param cursor The character offset into the page.
     * @return The line number the character is in.
     */
    public int row (int cursor)
    {
        return (row (new Cursor (getPage (), cursor)));
    }

    /**
     * Get the column number for a cursor.
     * @param cursor The character offset into the page.
     * @return The character offset into the line this cursor is on.
     */
    public int column (Cursor cursor)
    {
        int row;
        int previous;

        row = row (cursor);
        if (0 != row)
            previous = this.elementAt (row - 1);
        else
            previous = 0;

        return (cursor.getPosition () - previous);
    }

    /**
     * Get the column number for a position.
     * @param cursor The character offset into the page.
     * @return The character offset into the line this cursor is on.
     */
    public int column (int cursor)
    {
        return (column (new Cursor (getPage (), cursor)));
    }

    /**
     * Get the elements as an array of int.
     * @return A new array containing the elements,
     * i.e. a snapshot of the index.
     */
    public int[] get ()
    {
        int[] ret = new int[size ()];
        System.arraycopy (mIndices, 0, ret, 0, size ());

        return (ret);
    }

    /**
     * Binary search for the element.
     * @param cursor The element to search for.
     * @return The index at which the element was found or is to be inserted.
     */
    protected int bsearch (int cursor)
    {
        return (Sort.bsearch (this, new Cursor (getPage (), cursor)));
    }

    /**
     * Binary search for the element.
     * @param cursor The element to search for.
     * @param first The index to start at.
     * @param last The index to stop at.
     * @return The index at which the element was found or is to be inserted.
     */
    protected int bsearch (int cursor, int first, int last)
    {
        return (Sort.bsearch (this, new Cursor (getPage (), cursor), first, last));
    }

    /**
     * Inserts an element into the list.
     * The index must be a value greater than or equal to 0 and less than
     * or equal to the current size of the array.
     * @param cursor The element to insert.
     * @param index The index in the list to insert it at.
     */
    protected void insertElementAt (int cursor, int index)
    {
        if ((index >= capacity ()) || (size () == capacity ()))
        {   // allocate more space
            int[] new_values = new int[Math.max (capacity () + mIncrement, index + 1)];
            mIncrement *= 2;
            if (index < capacity ())
            {
                // copy and shift up in two pieces
                System.arraycopy (mIndices, 0, new_values, 0, index);
                System.arraycopy (mIndices, index, new_values, index + 1, capacity () - index);
            }
            else
                System.arraycopy (mIndices, 0, new_values, 0, capacity ());
            mIndices = new_values;
        }
        else if (index < size ())
            // shift up
            System.arraycopy (mIndices, index, mIndices, index + 1, capacity () - (index + 1));
        mIndices[index] = cursor;
        mCount++;
    }

    /**
     * Remove an element from the list.
     * @param index The index of the item to remove.
     */
    protected void removeElementAt (int index)
    {
        // shift
        System.arraycopy (mIndices, index + 1, mIndices, index, capacity () - (index + 1));
        mIndices[capacity() - 1] = 0;
        mCount--;
    }

    //
    // Sortable interface
    //

    /**
     * Returns the first index of the Sortable.
     * @return The index of the first element.
     */
    public int first ()
    {
        return (0);
    }

    /**
     * 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).
     * For an empty index this will return -1.
     */
    public int last ()
    {
        return (mCount - 1);
    }

    /**
     * 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)
    {
        Cursor ret;

        if (null != reuse)
        {
            ret = (Cursor)reuse;
            ret.mPosition = mIndices[index];
            ret.mPage = getPage (); // redundant
        }
        else
            ret = new Cursor (getPage (), mIndices[index]);

        return (ret);
    }

    /**
     * Swaps the elements at the given indicies.
     * @param i One index.
     * @param j The other index.
     */
    public void swap (int i, int j)
    {
        int temp = mIndices[i];
        mIndices[i] = mIndices[j];
        mIndices[j] = temp;
    }
}