1 package org.drools.reteoo.impl;
2
3 /*
4 $Id: PriorityQueue.java,v 1.1 2002/07/28 13:55:47 bob Exp $
5
6 Copyright 2002 (C) The Werken Company. All Rights Reserved.
7
8 Redistribution and use of this software and associated documentation
9 ("Software"), with or without modification, are permitted provided
10 that the following conditions are met:
11
12 1. Redistributions of source code must retain copyright
13 statements and notices. Redistributions must also contain a
14 copy of this document.
15
16 2. Redistributions in binary form must reproduce the
17 above copyright notice, this list of conditions and the
18 following disclaimer in the documentation and/or other
19 materials provided with the distribution.
20
21 3. The name "drools" must not be used to endorse or promote
22 products derived from this Software without prior written
23 permission of The Werken Company. For written permission,
24 please contact bob@werken.com.
25
26 4. Products derived from this Software may not be called "drools"
27 nor may "drools" appear in their names without prior written
28 permission of The Werken Company. "drools" is a registered
29 trademark of The Werken Company.
30
31 5. Due credit should be given to The Werken Company.
32 (http://drools.werken.com/).
33
34 THIS SOFTWARE IS PROVIDED BY THE WERKEN COMPANY AND CONTRIBUTORS
35 ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
36 NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
37 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
38 THE WERKEN COMPANY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
39 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
40 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
41 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
43 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
45 OF THE POSSIBILITY OF SUCH DAMAGE.
46
47 */
48
49 import java.util.LinkedList;
50 import java.util.ListIterator;
51 import java.util.NoSuchElementException;
52
53 /*** Queue that maintains the entries in sorted order.
54 *
55 * @author <a href="mailto:bob@eng.werken.com">bob mcwhirter</a>
56 */
57 public class PriorityQueue extends LinkedList
58 {
59 // ------------------------------------------------------------
60 // Constructors
61 // ------------------------------------------------------------
62
63 /*** Construct.
64 */
65 public PriorityQueue()
66 {
67 // intentionally left blank.
68 }
69
70 /*** Add an item to this queue.
71 *
72 * @param item The item to add.
73 * @param priority The priority of the item.
74 */
75 public void add(Object item,
76 int priority)
77 {
78 ListIterator entryIter = super.listIterator();
79 Entry eachEntry = null;
80
81 while ( entryIter.hasNext() )
82 {
83 eachEntry = (Entry) entryIter.next();
84
85 if ( eachEntry.getPriority() > priority )
86 {
87 entryIter.previous();
88 entryIter.add( new Entry( item,
89 priority ) );
90
91 return;
92 }
93 }
94
95 super.add( new Entry( item,
96 priority ) );
97 }
98
99 /*** Retrieve a bidrectional iterator of the
100 * members of this queue.
101 *
102 * @return The bidirectional list iterator.
103 */
104 public ListIterator listIterator()
105 {
106 return new ListIter( super.listIterator() );
107 }
108
109 /*** Remove the first element from this queue.
110 *
111 * @return The removed element.
112 *
113 * @throws NoSuchElementException If this queue is empty.
114 */
115 public Object removeFirst() throws NoSuchElementException
116 {
117 Entry entry = (Entry) super.removeFirst();
118
119 return entry.getItem();
120 }
121 }
122
123 /*** Bidirectional iterator implementation.
124 *
125 * @author <a href="mailto:bob@eng.werken.com">bob mcwhirter</a>
126 */
127 class ListIter implements ListIterator
128 {
129 // ------------------------------------------------------------
130 // Instance members
131 // ------------------------------------------------------------
132
133 /*** Internal iterator. */
134 private ListIterator iter;
135
136 // ------------------------------------------------------------
137 // Constructors
138 // ------------------------------------------------------------
139
140 /*** Construct.
141 *
142 * @param iter The internal iterator.
143 */
144 ListIter(ListIterator iter)
145 {
146 this.iter = iter;
147 }
148
149 // ------------------------------------------------------------
150 // Instance methods
151 // ------------------------------------------------------------
152
153 /*** Determine if this iterator has an element
154 * in the next position.
155 *
156 * @see #next
157 *
158 * @return <code>true</code> if this iterator contains
159 * an element in the next position,
160 * otherwise <code>false</code>.
161 */
162 public boolean hasNext()
163 {
164 return this.iter.hasNext();
165 }
166
167 /*** Determine if this iterator has an element
168 * in the previous position.
169 *
170 * @see #previous
171 *
172 * @return <code>true</code> if this iterator contains
173 * an element in the previous position,
174 * otherwise <code>false</code>.
175 */
176 public boolean hasPrevious()
177 {
178 return this.iter.hasPrevious();
179 }
180
181 /*** Retrieve the element in the next position and
182 * advance this iterator.
183 *
184 * @return The element at the next position.
185 *
186 * @throws NoSuchElementException If there is no
187 * element in the next position.
188 */
189 public Object next() throws NoSuchElementException
190 {
191 Entry entry = (Entry) this.iter.next();
192
193 return entry.getItem();
194 }
195
196 /*** Retrieve the element in the previous position and
197 * retreat this iterator.
198 *
199 * @return The element at the previous position.
200 *
201 * @throws NoSuchElementException If there is no
202 * element in the previous position.
203 */
204 public Object previous() throws NoSuchElementException
205 {
206 Entry entry = (Entry) this.iter.previous();
207
208 return entry.getItem();
209 }
210
211 /*** Remove the element currently pointed to.
212 *
213 * @throws IllegalStateException If this iterator
214 * does not currently point to any element.
215 */
216 public void remove() throws IllegalStateException
217 {
218 this.iter.remove();
219 }
220
221 /*** Add an element after the current point.
222 *
223 * @param item The item to add.
224 *
225 * @throws UnsupportedOperationException By default.
226 */
227 public void add(Object item) throws UnsupportedOperationException
228 {
229 throw new UnsupportedOperationException();
230 }
231
232 /*** Set the element at the current point.
233 *
234 * @param item The item to set.
235 *
236 * @throws UnsupportedOperationException By default.
237 */
238 public void set(Object item) throws UnsupportedOperationException
239 {
240 throw new UnsupportedOperationException();
241 }
242
243 /*** Retrieve the index of the next element position.
244 *
245 * @return the index.
246 */
247 public int nextIndex()
248 {
249 return this.iter.nextIndex();
250 }
251
252 /*** Retrieve the index of the previous element position.
253 *
254 * @return the index.
255 */
256 public int previousIndex()
257 {
258 return this.iter.previousIndex();
259 }
260 }
261
262 /*** Entry in the priority queue.
263 *
264 * @author <a href="mailto:bob@eng.werken.com">bob mcwhirter</a>
265 */
266 class Entry
267 {
268 // ------------------------------------------------------------
269 // Instance members
270 // ------------------------------------------------------------
271
272 /*** Priority. */
273 private int priority;
274
275 /*** Item, itself. */
276 private Object item;
277
278 // ------------------------------------------------------------
279 // Constructors
280 // ------------------------------------------------------------
281
282 /*** Construct.
283 *
284 * @param item The item.
285 * @param priority The priority.
286 */
287 Entry(Object item,
288 int priority)
289 {
290 this.item = item;
291 this.priority = priority;
292 }
293
294 // ------------------------------------------------------------
295 // Instance methods
296 // ------------------------------------------------------------
297
298 /*** Retrieve the priority.
299 *
300 * @return The priority.
301 */
302 public int getPriority()
303 {
304 return this.priority;
305 }
306
307 /*** Retrieve the item.
308 *
309 * @return The item.
310 */
311 public Object getItem()
312 {
313 return this.item;
314 }
315 }
This page was automatically generated by Maven