PriorityQueue - JBoss RULES 3.0.6 API 英文版文档

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

org.drools.util
Class PriorityQueue

java.lang.Object
  java.util.AbstractCollection
      org.drools.util.PriorityQueue

All Implemented Interfaces:: java.io.Serializable, java.lang.Iterable, java.util.Collection

public class PriorityQueue
extends java.util.AbstractCollection
implements java.io.Serializable
extends java.util.AbstractCollection
implements java.io.Serializable

Binary heap implementation of Buffer that provides for removal based on Comparator ordering.

The removal order of a binary heap is based on either the natural sort order of its elements or a specified . The remove()method always returns the first element as determined by the sort order. (The ascendingOrder flag in the constructors can be used to reverse the sort order, in which case will always remove the last element.) The removal order is not the same as the order of iteration; elements are returned by the iterator in no particular order.

The add(Object)and remove()operations perform in logarithmic time. The get()operation performs in constant time. All other operations perform in linear time or worse.

Note that this implementation is not synchronized.

See Also:: Serialized Form

Field Summary

protected boolean ascendingOrder
          If true, the first element as determined by the sort order will be returned.

protected java.util.Comparator comparator
          The comparator used to order the elements

protected java.lang.Object[] elements
          The elements in this buffer.

protected int size
          The number of elements currently in this buffer.

Constructor Summary

PriorityQueue()
          Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.

PriorityQueue(boolean ascendingOrder)
          Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.

PriorityQueue(boolean ascendingOrder, java.util.Comparator comparator)
          Constructs a new empty buffer specifying the sort order and comparator.

PriorityQueue(java.util.Comparator comparator)
          Constructs a new empty buffer that sorts in ascending order using the specified comparator.

PriorityQueue(int capacity)
          Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added, specifying an initial capacity.

PriorityQueue(int capacity, boolean ascendingOrder)
          Constructs a new empty buffer that specifying initial capacity and sort order, using the natural order of the objects added.

PriorityQueue(int capacity, boolean ascendingOrder, java.util.Comparator comparator)
          Constructs a new empty buffer that specifying initial capacity, sort order and comparator.

PriorityQueue(int capacity, java.util.Comparator comparator)
          Constructs a new empty buffer that sorts in ascending order using the specified comparator and initial capacity.

Method Summary

boolean add(java.lang.Object element)
          Adds an element to the buffer.

void clear()
          Clears all elements from the buffer.

java.util.Comparator comparator()
          Gets the comparator being used for this buffer, null is natural order.

protected int compare(java.lang.Object a, java.lang.Object b)
          Compares two objects using the comparator if specified, or the natural order otherwise.

java.lang.Object get()
          Gets the next element to be removed without actually removing it (peek).

protected void grow()
          Increases the size of the heap to support additional elements

boolean isAscendingOrder()
          Checks whether the heap is ascending or descending order.

protected boolean isAtCapacity()
          Tests if the buffer is at capacity.

java.util.Iterator iterator()
          Returns an iterator over this heap's elements.

protected void percolateDownMaxHeap(int index)
          Percolates element down heap from the position given by the index.

protected void percolateDownMinHeap(int index)
          Percolates element down heap from the position given by the index.

protected void percolateUpMaxHeap(int index)
          Percolates element up heap from from the position given by the index.

protected void percolateUpMaxHeap(java.lang.Object element)
          Percolates a new element up heap from the bottom.

protected void percolateUpMinHeap(int index)
          Percolates element up heap from the position given by the index.

protected void percolateUpMinHeap(java.lang.Object element)
          Percolates a new element up heap from the bottom.

java.lang.Object remove()
          Gets and removes the next element (pop).

int size()
          Returns the number of elements in this buffer.

java.lang.String toString()
          Returns a string representation of this heap.

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Field Summary
`protected boolean`	`ascendingOrder` If true, the first element as determined by the sort order will be returned.
`protected java.util.Comparator`	`comparator` The comparator used to order the elements
`protected java.lang.Object[]`	`elements` The elements in this buffer.
`protected int`	`size` The number of elements currently in this buffer.

Constructor Summary
`PriorityQueue()` Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.
`PriorityQueue(boolean ascendingOrder)` Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.
`PriorityQueue(boolean ascendingOrder, java.util.Comparator comparator)` Constructs a new empty buffer specifying the sort order and comparator.
`PriorityQueue(java.util.Comparator comparator)` Constructs a new empty buffer that sorts in ascending order using the specified comparator.
`PriorityQueue(int capacity)` Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added, specifying an initial capacity.
`PriorityQueue(int capacity, boolean ascendingOrder)` Constructs a new empty buffer that specifying initial capacity and sort order, using the natural order of the objects added.
`PriorityQueue(int capacity, boolean ascendingOrder, java.util.Comparator comparator)` Constructs a new empty buffer that specifying initial capacity, sort order and comparator.
`PriorityQueue(int capacity, java.util.Comparator comparator)` Constructs a new empty buffer that sorts in ascending order using the specified comparator and initial capacity.

Method Summary
`boolean`	`add(java.lang.Object element)` Adds an element to the buffer.
`void`	`clear()` Clears all elements from the buffer.
`java.util.Comparator`	`comparator()` Gets the comparator being used for this buffer, null is natural order.
`protected int`	`compare(java.lang.Object a, java.lang.Object b)` Compares two objects using the comparator if specified, or the natural order otherwise.
`java.lang.Object`	`get()` Gets the next element to be removed without actually removing it (peek).
`protected void`	`grow()` Increases the size of the heap to support additional elements
`boolean`	`isAscendingOrder()` Checks whether the heap is ascending or descending order.
`protected boolean`	`isAtCapacity()` Tests if the buffer is at capacity.
`java.util.Iterator`	`iterator()` Returns an iterator over this heap's elements.
`protected void`	`percolateDownMaxHeap(int index)` Percolates element down heap from the position given by the index.
`protected void`	`percolateDownMinHeap(int index)` Percolates element down heap from the position given by the index.
`protected void`	`percolateUpMaxHeap(int index)` Percolates element up heap from from the position given by the index.
`protected void`	`percolateUpMaxHeap(java.lang.Object element)` Percolates a new element up heap from the bottom.
`protected void`	`percolateUpMinHeap(int index)` Percolates element up heap from the position given by the index.
`protected void`	`percolateUpMinHeap(java.lang.Object element)` Percolates a new element up heap from the bottom.
`java.lang.Object`	`remove()` Gets and removes the next element (pop).
`int`	`size()` Returns the number of elements in this buffer.
`java.lang.String`	`toString()` Returns a string representation of this heap.

Methods inherited from class java.util.AbstractCollection
`addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

Methods inherited from interface java.util.Collection
`equals, hashCode`

Field Detail

elements

protected java.lang.Object[] elements

The elements in this buffer.

size

protected int size

The number of elements currently in this buffer.

ascendingOrder

protected boolean ascendingOrder

If true, the first element as determined by the sort order will be returned. If false, the last element as determined by the sort order will be returned.

comparator

protected java.util.Comparator comparator

The comparator used to order the elements

Constructor Detail

PriorityQueue

public PriorityQueue()

Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added.

PriorityQueue

public PriorityQueue(java.util.Comparator comparator)

Constructs a new empty buffer that sorts in ascending order using the specified comparator.

Parameters:: comparator - the comparator used to order the elements, null means use natural order

PriorityQueue

public PriorityQueue(boolean ascendingOrder)

Constructs a new empty buffer specifying the sort order and using the natural order of the objects added.

Parameters:: ascendingOrder - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap

PriorityQueue

public PriorityQueue(boolean ascendingOrder,
                     java.util.Comparator comparator)

Constructs a new empty buffer specifying the sort order and comparator.

Parameters:: ascendingOrder - true to use the order imposed by the given comparator; false to reverse that order; comparator - the comparator used to order the elements, null means use natural order

PriorityQueue

public PriorityQueue(int capacity)

Constructs a new empty buffer that sorts in ascending order by the natural order of the objects added, specifying an initial capacity.

Parameters:: capacity - the initial capacity for the buffer, greater than zero
Throws:: java.lang.IllegalArgumentException - if capacity is <= 0

PriorityQueue

public PriorityQueue(int capacity,
                     java.util.Comparator comparator)

Constructs a new empty buffer that sorts in ascending order using the specified comparator and initial capacity.

Parameters:: capacity - the initial capacity for the buffer, greater than zero; comparator - the comparator used to order the elements, null means use natural order
Throws:: java.lang.IllegalArgumentException - if capacity is <= 0

PriorityQueue

public PriorityQueue(int capacity,
                     boolean ascendingOrder)

Constructs a new empty buffer that specifying initial capacity and sort order, using the natural order of the objects added.

Parameters:: capacity - the initial capacity for the buffer, greater than zero; ascendingOrder - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap.
Throws:: java.lang.IllegalArgumentException - if capacity is <= 0

PriorityQueue

public PriorityQueue(int capacity,
                     boolean ascendingOrder,
                     java.util.Comparator comparator)

Constructs a new empty buffer that specifying initial capacity, sort order and comparator.

Parameters:: capacity - the initial capacity for the buffer, greater than zero; ascendingOrder - true to use the order imposed by the given comparator; false to reverse that order; comparator - the comparator used to order the elements, null means use natural order
Throws:: java.lang.IllegalArgumentException - if capacity is <= 0

Method Detail

isAscendingOrder

public boolean isAscendingOrder()

Checks whether the heap is ascending or descending order.

Returns:: true if ascending order (a min heap)

comparator

public java.util.Comparator comparator()

Gets the comparator being used for this buffer, null is natural order.

Returns:: the comparator in use, null is natural order

size

public int size()

Returns the number of elements in this buffer.

Specified by:: size in interface java.util.Collection
Specified by:: size in class java.util.AbstractCollection

Returns:: the number of elements in this buffer

clear

public void clear()

Clears all elements from the buffer.

Specified by:: clear in interface java.util.Collection
Overrides:: clear in class java.util.AbstractCollection

add

public boolean add(java.lang.Object element)

Adds an element to the buffer.

The element added will be sorted according to the comparator in use.

Specified by:: add in interface java.util.Collection
Overrides:: add in class java.util.AbstractCollection

Parameters:: element - the element to be added
Returns:: true always

get

public java.lang.Object get()

Gets the next element to be removed without actually removing it (peek).

Returns:: the next element
Throws:: java.util.NoSuchElementException - if the buffer is empty

remove

public java.lang.Object remove()

Gets and removes the next element (pop).

Returns:: the next element
Throws:: java.util.NoSuchElementException - if the buffer is empty

isAtCapacity

protected boolean isAtCapacity()

Tests if the buffer is at capacity.

Returns:: true if buffer is full; false otherwise.

percolateDownMinHeap

protected void percolateDownMinHeap(int index)

Percolates element down heap from the position given by the index.

Assumes it is a minimum heap.

Parameters:: index - the index for the element

percolateDownMaxHeap

protected void percolateDownMaxHeap(int index)

Percolates element down heap from the position given by the index.

Assumes it is a maximum heap.

Parameters:: index - the index of the element

percolateUpMinHeap

protected void percolateUpMinHeap(int index)

Percolates element up heap from the position given by the index.

Assumes it is a minimum heap.

Parameters:: index - the index of the element to be percolated up

percolateUpMinHeap

protected void percolateUpMinHeap(java.lang.Object element)

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

Parameters:: element - the element

percolateUpMaxHeap

protected void percolateUpMaxHeap(int index)

Percolates element up heap from from the position given by the index.

Assume it is a maximum heap.

Parameters:: index - the index of the element to be percolated up

percolateUpMaxHeap

protected void percolateUpMaxHeap(java.lang.Object element)

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

Parameters:: element - the element

compare

protected int compare(java.lang.Object a,
                      java.lang.Object b)

Compares two objects using the comparator if specified, or the natural order otherwise.

Parameters:: a - the first object; b - the second object
Returns:: -ve if a less than b, 0 if they are equal, +ve if a greater than b

grow

protected void grow()

Increases the size of the heap to support additional elements

iterator

public java.util.Iterator iterator()

Returns an iterator over this heap's elements.

Specified by:: iterator in interface java.lang.Iterable
Specified by:: iterator in interface java.util.Collection
Specified by:: iterator in class java.util.AbstractCollection

Returns:: an iterator over this heap's elements

toString

public java.lang.String toString()

Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.

Overrides:: toString in class java.util.AbstractCollection

Returns:: a string representation of this heap

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

PriorityQueue - JBoss RULES 3.0.6 API 英文版文档

org.drools.util Class PriorityQueue

elements

size

ascendingOrder

comparator

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

isAscendingOrder

comparator

size

clear

add

get

remove

isAtCapacity

percolateDownMinHeap

percolateDownMaxHeap

percolateUpMinHeap

percolateUpMinHeap

percolateUpMaxHeap

percolateUpMaxHeap

compare

grow

iterator

toString

org.drools.util
Class PriorityQueue