001: package org.drools.util;
002:
003: /*
004: * Copyright 2005 JBoss Inc
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: */
018:
019: import java.io.Serializable;
020: import java.util.Comparator;
021: import java.util.NoSuchElementException;
022:
023: public class BinaryHeapQueue implements Queue, Serializable {
024: /** The default capacity for a binary heap. */
025: private final static int DEFAULT_CAPACITY = 13;
026:
027: /** The comparator used to order the elements */
028: private final Comparator comparator;
029:
030: /** The number of elements currently in this heap. */
031: private int size;
032:
033: /** The elements in this heap. */
034: private Queueable[] elements;
035:
036: /**
037: * Constructs a new <code>BinaryHeap</code> that will use the given
038: * comparator to order its elements.
039: *
040: * @param comparator the comparator used to order the elements, null
041: * means use natural order
042: */
043: public BinaryHeapQueue(final Comparator comparator) {
044: this (comparator, BinaryHeapQueue.DEFAULT_CAPACITY);
045: }
046:
047: /**
048: * Constructs a new <code>BinaryHeap</code>.
049: *
050: * @param comparator the comparator used to order the elements, null
051: * means use natural order
052: * @param capacity the initial capacity for the heap
053: * @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code>
054: */
055: public BinaryHeapQueue(final Comparator comparator,
056: final int capacity) {
057: if (capacity <= 0) {
058: throw new IllegalArgumentException("invalid capacity");
059: }
060:
061: //+1 as 0 is noop
062: this .elements = new Queueable[capacity + 1];
063: this .comparator = comparator;
064: }
065:
066: //-----------------------------------------------------------------------
067:
068: /**
069: * Clears all elements from queue.
070: */
071: public void clear() {
072: this .elements = new Queueable[this .elements.length]; // for gc
073: this .size = 0;
074: }
075:
076: /**
077: * Tests if queue is empty.
078: *
079: * @return <code>true</code> if queue is empty; <code>false</code>
080: * otherwise.
081: */
082: public boolean isEmpty() {
083: return this .size == 0;
084: }
085:
086: /**
087: * Tests if queue is full.
088: *
089: * @return <code>true</code> if queue is full; <code>false</code>
090: * otherwise.
091: */
092: public boolean isFull() {
093: //+1 as Queueable 0 is noop
094: return this .elements.length == this .size + 1;
095: }
096:
097: /**
098: * Returns the number of elements in this heap.
099: *
100: * @return the number of elements in this heap
101: */
102: public int size() {
103: return this .size;
104: }
105:
106: /**
107: * Inserts an Queueable into queue.
108: *
109: * @param element the Queueable to be inserted
110: */
111: public void enqueue(final Queueable element) {
112: if (isFull()) {
113: grow();
114: }
115:
116: percolateUpMinHeap(element);
117: }
118:
119: /**
120: * Returns the Queueable on top of heap and remove it.
121: *
122: * @return the Queueable at top of heap
123: * @throws NoSuchElementException if <code>isEmpty() == true</code>
124: */
125: public Queueable dequeue() throws NoSuchElementException {
126: if (isEmpty()) {
127: return null;
128: }
129:
130: final Queueable result = this .elements[1];
131: result.dequeue();
132:
133: // Code bellow was removed because it is already executed
134: // inside result.dequeue()
135: //
136: // setElement(1, this.elements[this.size--]);
137: // this.elements[this.size + 1] = null;
138: //
139: // if (this.size != 0) {
140: // percolateDownMinHeap(1);
141: // }
142:
143: return result;
144: }
145:
146: /**
147: *
148: * @param index
149: */
150: public Queueable dequeue(final int index) {
151: if (index < 1 || index > this .size) {
152: //throw new NoSuchElementException();
153: return null;
154: }
155:
156: final Queueable result = this .elements[index];
157: setElement(index, this .elements[this .size]);
158: this .elements[this .size] = null;
159: this .size--;
160: if (this .size != 0 && index <= this .size) {
161: int compareToParent = 0;
162: if (index > 1) {
163: compareToParent = compare(this .elements[index],
164: this .elements[index / 2]);
165: }
166: if (index > 1 && compareToParent < 0) {
167: percolateUpMinHeap(index);
168: } else {
169: percolateDownMinHeap(index);
170: }
171: }
172:
173: return result;
174: }
175:
176: /**
177: * Percolates Queueable down heap from the position given by the index.
178: * <p/>
179: * Assumes it is a minimum heap.
180: *
181: * @param index the index for the Queueable
182: */
183: private void percolateDownMinHeap(final int index) {
184: final Queueable element = this .elements[index];
185: int hole = index;
186:
187: while ((hole * 2) <= this .size) {
188: int child = hole * 2;
189:
190: // if we have a right child and that child can not be percolated
191: // up then move onto other child
192: if (child != this .size
193: && compare(this .elements[child + 1],
194: this .elements[child]) < 0) {
195: child++;
196: }
197:
198: // if we found resting place of bubble then terminate search
199: if (compare(this .elements[child], element) >= 0) {
200: break;
201: }
202:
203: setElement(hole, this .elements[child]);
204: hole = child;
205: }
206:
207: setElement(hole, element);
208: }
209:
210: /**
211: * Percolates Queueable up heap from the position given by the index.
212: * <p/>
213: * Assumes it is a minimum heap.
214: *
215: * @param index the index of the Queueable to be percolated up
216: */
217: private void percolateUpMinHeap(final int index) {
218: int hole = index;
219: final Queueable element = this .elements[hole];
220: while (hole > 1
221: && compare(element, this .elements[hole / 2]) < 0) {
222: // save Queueable that is being pushed down
223: // as the Queueable "bubble" is percolated up
224: final int next = hole / 2;
225: setElement(hole, this .elements[next]);
226: hole = next;
227: }
228: setElement(hole, element);
229: }
230:
231: /**
232: * Percolates a new Queueable up heap from the bottom.
233: * <p/>
234: * Assumes it is a minimum heap.
235: *
236: * @param element the Queueable
237: */
238: private void percolateUpMinHeap(final Queueable element) {
239: setElement(++this .size, element);
240: percolateUpMinHeap(this .size);
241: }
242:
243: /**
244: * Compares two objects using the comparator if specified, or the
245: * natural order otherwise.
246: *
247: * @param a the first object
248: * @param b the second object
249: * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
250: */
251: private int compare(final Queueable a, final Queueable b) {
252: return this .comparator.compare(a, b);
253: }
254:
255: /**
256: * Increases the size of the heap to support additional elements
257: */
258: private void grow() {
259: final Queueable[] elements = new Queueable[this .elements.length * 2];
260: System.arraycopy(this .elements, 0, elements, 0,
261: this .elements.length);
262: this .elements = elements;
263: }
264:
265: /**
266: *
267: * @param index
268: * @param element
269: */
270: private void setElement(final int index, final Queueable element) {
271: this .elements[index] = element;
272: element.enqueued(this , index);
273: }
274:
275: public Queueable[] getQueueable() {
276: return this .elements;
277: }
278:
279: public Object[] toArray() {
280: final Object[] result = new Object[this .size];
281: System.arraycopy(this .elements, 1, result, 0, this .size);
282: return result;
283: }
284:
285: public Object[] toArray(Object a[]) {
286: if (a.length < this .size) {
287: a = (Object[]) java.lang.reflect.Array.newInstance(a
288: .getClass().getComponentType(), this .size);
289: }
290:
291: System.arraycopy(this .elements, 1, a, 0, this.size);
292:
293: if (a.length > this.size) {
294: a[this.size] = null;
295: }
296:
297: return a;
298: }
299: }
|