View Javadoc
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