priorityqueue.java

jboss规则引擎

    /**
     * Gets and removes the next element (pop).
     * 
     * @return the next element
     * @throws NoSuchElementException
     *             if the buffer is empty
     */
    public Object remove() {
        final Object result = get();
        this.elements[1] = this.elements[this.size--];

        // set the unused element to 'null' so that the garbage collector
        // can free the object if not used anywhere else.(remove reference)
        this.elements[this.size + 1] = null;

        if ( this.size != 0 ) {
            // percolate top element to it's place in tree
            if ( this.ascendingOrder ) {
                percolateDownMinHeap( 1 );
            } else {
                percolateDownMaxHeap( 1 );
            }
        }

        return result;
    }

    // -----------------------------------------------------------------------
    /**
     * Tests if the buffer is at capacity.
     * 
     * @return <code>true</code> if buffer is full; <code>false</code>
     *         otherwise.
     */
    protected boolean isAtCapacity() {
        // +1 as element 0 is noop
        return this.elements.length == this.size + 1;
    }

    /**
     * Percolates element down heap from the position given by the index. <p/>
     * Assumes it is a minimum heap.
     * 
     * @param index
     *            the index for the element
     */
    protected void percolateDownMinHeap(final int index) {
        final Object element = this.elements[index];
        int hole = index;

        while ( (hole * 2) <= this.size ) {
            int child = hole * 2;

            // if we have a right child and that child can not be percolated
            // up then move onto other child
            if ( child != this.size && compare( this.elements[child + 1],
                                                this.elements[child] ) < 0 ) {
                child++;
            }

            // if we found resting place of bubble then terminate search
            if ( compare( this.elements[child],
                          element ) >= 0 ) {
                break;
            }

            this.elements[hole] = this.elements[child];
            hole = child;
        }

        this.elements[hole] = element;
    }

    /**
     * Percolates element down heap from the position given by the index. <p/>
     * Assumes it is a maximum heap.
     * 
     * @param index
     *            the index of the element
     */
    protected void percolateDownMaxHeap(final int index) {
        final Object element = this.elements[index];
        int hole = index;

        while ( (hole * 2) <= this.size ) {
            int child = hole * 2;

            // if we have a right child and that child can not be percolated
            // up then move onto other child
            if ( child != this.size && compare( this.elements[child + 1],
                                                this.elements[child] ) > 0 ) {
                child++;
            }

            // if we found resting place of bubble then terminate search
            if ( compare( this.elements[child],
                          element ) <= 0 ) {
                break;
            }

            this.elements[hole] = this.elements[child];
            hole = child;
        }

        this.elements[hole] = element;
    }

    /**
     * Percolates element up heap from the position given by the index. <p/>
     * Assumes it is a minimum heap.
     * 
     * @param index
     *            the index of the element to be percolated up
     */
    protected void percolateUpMinHeap(final int index) {
        int hole = index;
        final Object element = this.elements[hole];
        while ( hole > 1 && compare( element,
                                     this.elements[hole / 2] ) < 0 ) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            this.elements[hole] = this.elements[next];
            hole = next;
        }
        this.elements[hole] = element;
    }

    /**
     * Percolates a new element up heap from the bottom. <p/>Assumes it is a
     * minimum heap.
     * 
     * @param element
     *            the element
     */
    protected void percolateUpMinHeap(final Object element) {
        this.elements[++this.size] = element;
        percolateUpMinHeap( this.size );
    }

    /**
     * Percolates element up heap from from the position given by the index.
     * <p/>Assume it is a maximum heap.
     * 
     * @param index
     *            the index of the element to be percolated up
     */
    protected void percolateUpMaxHeap(final int index) {
        int hole = index;
        final Object element = this.elements[hole];

        while ( hole > 1 && compare( element,
                                     this.elements[hole / 2] ) > 0 ) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            this.elements[hole] = this.elements[next];
            hole = next;
        }

        this.elements[hole] = element;
    }

    /**
     * Percolates a new element up heap from the bottom. <p/>Assume it is a
     * maximum heap.
     * 
     * @param element
     *            the element
     */
    protected void percolateUpMaxHeap(final Object element) {
        this.elements[++this.size] = element;
        percolateUpMaxHeap( this.size );
    }

    /**
     * Compares two objects using the comparator if specified, or the natural
     * order otherwise.
     * 
     * @param a
     *            the first object
     * @param b
     *            the second object
     * @return -ve if a less than b, 0 if they are equal, +ve if a greater than
     *         b
     */
    protected int compare(final Object a,
                          final Object b) {
        if ( this.comparator != null ) {
            return this.comparator.compare( a,
                                            b );
        } else {
            return ((Comparable) a).compareTo( b );
        }
    }

    /**
     * Increases the size of the heap to support additional elements
     */
    protected void grow() {
        final Object[] array = new Object[this.elements.length * 2];
        System.arraycopy( this.elements,
                          0,
                          array,
                          0,
                          this.elements.length );
        this.elements = array;
    }

    // -----------------------------------------------------------------------
    /**
     * Returns an iterator over this heap's elements.
     * 
     * @return an iterator over this heap's elements
     */
    public Iterator iterator() {
        return new Iterator() {

            private int index             = 1;

            private int lastReturnedIndex = -1;

            public boolean hasNext() {
                return this.index <= PriorityQueue.this.size;
            }

            public Object next() {
                if ( !hasNext() ) {
                    throw new NoSuchElementException();
                }
                this.lastReturnedIndex = this.index;
                this.index++;
                return PriorityQueue.this.elements[this.lastReturnedIndex];
            }

            public void remove() {
                if ( this.lastReturnedIndex == -1 ) {
                    throw new IllegalStateException();
                }
                PriorityQueue.this.elements[this.lastReturnedIndex] = PriorityQueue.this.elements[PriorityQueue.this.size];
                PriorityQueue.this.elements[PriorityQueue.this.size] = null;
                PriorityQueue.this.size--;
                if ( PriorityQueue.this.size != 0 && this.lastReturnedIndex <= PriorityQueue.this.size ) {
                    int compareToParent = 0;
                    if ( this.lastReturnedIndex > 1 ) {
                        compareToParent = compare( PriorityQueue.this.elements[this.lastReturnedIndex],
                                                   PriorityQueue.this.elements[this.lastReturnedIndex / 2] );
                    }
                    if ( PriorityQueue.this.ascendingOrder ) {
                        if ( this.lastReturnedIndex > 1 && compareToParent < 0 ) {
                            percolateUpMinHeap( this.lastReturnedIndex );
                        } else {
                            percolateDownMinHeap( this.lastReturnedIndex );
                        }
                    } else { // max heap
                        if ( this.lastReturnedIndex > 1 && compareToParent > 0 ) {
                            percolateUpMaxHeap( this.lastReturnedIndex );
                        } else {
                            percolateDownMaxHeap( this.lastReturnedIndex );
                        }
                    }
                }
                this.index--;
                this.lastReturnedIndex = -1;
            }

        };
    }

    /**
     * Returns a string representation of this heap. The returned string is
     * similar to those produced by standard JDK collections.
     * 
     * @return a string representation of this heap
     */
    public String toString() {
        final StringBuffer sb = new StringBuffer();

        sb.append( "[ " );

        for ( int i = 1; i < this.size + 1; i++ ) {
            if ( i != 1 ) {
                sb.append( ", " );
            }
            sb.append( this.elements[i] );
        }

        sb.append( " ]" );

        return sb.toString();
    }

}