PrioritizedList


1   /*
2    * Copyright 2002 by
3    * <a HREF="http://www.coridan.com">Coridan</a>
4    * <a HREF="mailto: support@coridan.com ">support@coridan.com</a>
5    *
6    * The contents of this file are subject to the Mozilla Public License Version
7    * 1.1 (the "License"); you may not use this file except in compliance with the
8    * License.  You may obtain a copy of the License at
9    * http://www.mozilla.org/MPL/
10   *
11   * Software distributed under the License is distributed on an "AS IS" basis,
12   * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13   * for the specific language governing rights and limitations under the
14   * License.
15   *
16   * The Original Code is "MantaRay" (TM).
17   *
18   * The Initial Developer of the Original Code is Amir Shevat.
19   * Portions created by the Initial Developer are Copyright (C) 2006
20   * Coridan Inc.  All Rights Reserved.
21   *
22   * Contributor(s): all the names of the contributors are added in the source
23   * code where applicable.
24   *
25   * Alternatively, the contents of this file may be used under the terms of the
26   * LGPL license (the "GNU LESSER GENERAL PUBLIC LICENSE"), in which case the
27   * provisions of LGPL are applicable instead of those above.  If you wish to
28   * allow use of your version of this file only under the terms of the LGPL
29   * License and not to allow others to use your version of this file under
30   * the MPL, indicate your decision by deleting the provisions above and
31   * replace them with the notice and other provisions required by the LGPL.
32   * If you do not delete the provisions above, a recipient may use your version
33   * of this file under either the MPL or the GNU LESSER GENERAL PUBLIC LICENSE.
34   
35   *
36   * This library is free software; you can redistribute it and/or modify it
37   * under the terms of the MPL as stated above or under the terms of the GNU
38   * Lesser General Public License as published by the Free Software Foundation;
39   * either version 2.1 of the License, or any later version.
40   *
41   * This library is distributed in the hope that it will be useful, but WITHOUT
42   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
43   * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
44   * License for more details.
45   */
46  package org.mr.core.util;
47  
48  import java.util.ArrayList  ;
49  import java.util.Collection  ;
50  import java.util.Iterator  ;
51  import java.util.LinkedList  ;
52  import java.util.List  ;
53  import java.util.ListIterator  ;
54  import java.util.NoSuchElementException  ;
55  import java.util.Random  ;
56  //import java.util.Random;
57  
58  /**
59  * Good class if you know the number of the Priorities you want to sort a collection
60   * keeps the list sorted primarily by priority and secondly sorted by time of insert
61   * @author Amir Shevat
62   *
63   */
64  public class PrioritizedList implements List   {
65      
66      
67      int numberOfPriorities;
68      List  [] lists ;
69      
70      public PrioritizedList(int numberOfPriorities){
71          this.numberOfPriorities = numberOfPriorities;
72          lists = new List  [numberOfPriorities];
73          for (int i = 0; i < lists.length; i++) {
74              lists[i]= new LinkedList  ();
75          }
76      }
77      
78      public int size() {
79          int result = 0;
80          for (int i = 0; i < lists.length; i++) {
81              result += lists[i].size() ;
82          }
83          return result;
84          
85      }
86  
87      public void clear() {
88          for (int i = 0; i < lists.length; i++) {
89              lists[i].clear();
90          }
91      }
92  
93      public boolean isEmpty() {
94          return size() == 0;
95      }
96  
97      public Object  [] toArray() {
98          //  not best solution but will do 
99          return makeListFromLists().toArray();
100     }
101     
102     private List   makeListFromLists() {
103         ArrayList   result = new ArrayList  ();
104         for (int i = 0; i < lists.length; i++) {
105             result.addAll(lists[i]) ;
106         }
107         return result;
108     }
109     
110     public Object   get(int index) {
111         for (int i = 0; i < lists.length; i++) {
112             if (index < lists[i].size())
113                 return lists[i].get(index);
114             index -= lists[i].size() ;
115         }
116         return null;
117     }
118 
119     public Object   remove(int index) {
120         int temp = index;
121         for (int i = 0; i < lists.length; i++) {
122             if (temp < lists[i].size())
123                 return lists[i].remove(temp);
124             temp -= lists[i].size() ;
125         }
126         return null;
127     }
128 
129     public void add(int index, Object   element) {
130         throw new UnsupportedOperationException  ();
131     }
132 
133     public int indexOf(Object   o) {
134         Prioritizeable p = (Prioritizeable) o;
135         int priorityIndex = (numberOfPriorities-1)-p.getPriority();
136         int index = lists[priorityIndex].indexOf(o);
137         if (index < 0)
138             return -1;
139         for (int i=0; i<priorityIndex ; i++) {
140             index+=lists[i].size();
141         }
142         return index;
143     }
144 
145     public int lastIndexOf(Object   o) {
146         Prioritizeable p = (Prioritizeable) o;
147         int priorityIndex = (numberOfPriorities-1)-p.getPriority();
148         int index = lists[priorityIndex].lastIndexOf(o);
149         if (index < 0)
150             return -1;
151         for (int i=0; i<priorityIndex ; i++) {
152             index+=lists[i].size();
153         }
154         return index;
155     }
156 
157     public boolean add(Object   o) {
158         Prioritizeable p = (Prioritizeable) o;
159         return lists[(numberOfPriorities-1)-p.getPriority()].add(o);
160     }
161 
162     public boolean contains(Object   o) {
163         Prioritizeable p = (Prioritizeable) o;
164         return lists[(numberOfPriorities-1)-p.getPriority()].contains(o);
165     }
166 
167     public boolean remove(Object   o) {
168         Prioritizeable p = (Prioritizeable) o;
169         return lists[(numberOfPriorities-1)-p.getPriority()].remove(o);
170     }
171 
172     public boolean addAll(int index, Collection   c) {
173         throw new UnsupportedOperationException  ();
174     }
175 
176     // returns true is the list has changes
177     public boolean addAll(Collection   c) {
178         boolean result = false;
179         Object   o;
180         boolean temp;
181         Iterator   ci = c.iterator();
182         while (ci.hasNext()) {
183             o = ci.next();
184             temp = add(o);
185             result = result || temp;
186         }
187         return result;
188     }
189     
190     public void addAllToHead(Collection   c) {
191         Iterator   ci = c.iterator();
192         Prioritizeable p;
193         int minPriorityIndex = numberOfPriorities-1; 
194         while (ci.hasNext()) {
195             p = (Prioritizeable) ci.next();
196             lists[minPriorityIndex-p.getPriority()].add(0,p);
197         }
198     }
199     
200     public void addToHead(Object   element){
201         Prioritizeable p = (Prioritizeable) element;
202         lists[(numberOfPriorities-1)-p.getPriority()].add(0,p);
203     }
204 
205     public boolean containsAll(Collection   c) {
206         Iterator   ci = c.iterator();
207         Object   o;
208         while(ci.hasNext()) {
209             o = ci.next();
210             if (!contains(o))
211                 return false;
212         }
213         return true;
214     }
215 
216     // returns true if the list has changed
217     public boolean removeAll(Collection   c) {
218         boolean result = false;
219         Iterator   ci = c.iterator();
220         Prioritizeable p;
221         int minPriorityIndex = numberOfPriorities-1;
222         while (ci.hasNext()) {
223             p = (Prioritizeable) ci.next();
224             if (lists[minPriorityIndex-p.getPriority()].remove(p))
225                 result = true;
226         }
227         return result;
228     }
229 
230     public boolean retainAll(Collection   c) {
231         clear();
232         return addAll(c);
233     }
234 
235     public Iterator   iterator() {
236         return new PriorityIterator();
237     }
238 
239     public List   subList(int fromIndex, int toIndex) {
240         // not best solution but will do 
241         return makeListFromLists().subList(fromIndex, toIndex);
242     }
243 
244     public ListIterator   listIterator() {
245         // not best solution but will do 
246         return makeListFromLists().listIterator();
247     }
248 
249     public ListIterator   listIterator(int index) {
250         // not best solution but will do 
251         return makeListFromLists().listIterator(index);
252     }
253 
254     public Object   set(int index, Object   element) {
255         throw new UnsupportedOperationException  ();
256     }
257 
258     public Object  [] toArray(Object  [] a) {
259         // not best solution but will do 
260         return makeListFromLists().toArray(a);
261     }
262     
263     // Iterator implementation over the PrioritizedList
264     class PriorityIterator implements Iterator   {
265         
266         // the current list index
267         int currentList;
268         boolean nextCalled;
269         
270         // the current element index in the current list
271         int currentElement;
272         
273         PriorityIterator () {
274             currentList = -1;
275             currentElement = -1;
276             nextCalled = false;
277         }
278         
279         public void remove() {
280             if (nextCalled) {
281                 lists[currentList].remove(currentElement);
282                 currentElement--;
283                 nextCalled = false;
284             }
285             else {
286                 throw new IllegalStateException  ();
287             }
288         }
289 
290         public boolean hasNext() {
291             if (currentList >= 0) {
292                 // we already started iterating the lists
293                 if (currentElement >= 0) {
294                     // we already iterating one of the lists 
295                     if (currentElement < lists[currentList].size()-1) {
296                         // we are still not in the end of the list
297                         return true;
298                     }
299                     else {
300                         // its the last element in the list.
301                         // start searching from the next list.
302                         for (int i=currentList+1 ; i<lists.length ; i++) {
303                             if (!lists[i].isEmpty()) {
304                                 return true;
305                             }
306                         }
307                         return false;
308                     }
309                 }
310                 else {
311                     // we haven't started iterating this list 
312                     for (int i=currentList ; i<lists.length ; i++) {
313                         if (!lists[i].isEmpty()) {
314                             return true;
315                         }
316                     }
317                     return false;
318                 }
319             }
320             else {
321                 // we haven't started to iterate at all.
322                 // start searching from the first list
323                 for (int i=0 ; i<lists.length ; i++) {
324                     if (!lists[i].isEmpty()) {
325                         return true;
326                     }
327                 }
328                 return false;
329             }           
330         } // hasNext()
331 
332         public Object   next() {
333             if (currentList >= 0) {
334                 // we already started iterating the lists
335                 if (currentElement >= 0) {
336                     // we already iterating one of the lists 
337                     if (currentElement < lists[currentList].size()-1) {
338                         // we are still not in the end of the list
339                         currentElement++;
340                         nextCalled = true;
341                         return lists[currentList].get(currentElement);
342                     }
343                     else {
344                         // its the last element in the list.
345                         // start searching from the next list.
346                         for (int i=currentList+1 ; i<lists.length ; i++) {
347                             if (!lists[i].isEmpty()) {
348                                 currentList = i;
349                                 currentElement = 0;
350                                 nextCalled = true;
351                                 return lists[currentList].get(currentElement);
352                             }
353                         }
354                         throw new NoSuchElementException  ("No more elements exist in the collection");
355                     }
356                 }
357                 else {
358                     // we haven't started iterating this list 
359                     for (int i=currentList ; i<lists.length ; i++) {
360                         if (!lists[i].isEmpty()) {
361                             currentList = i;
362                             currentElement = 0;
363                             nextCalled = true;
364                             return lists[currentList].get(currentElement);
365                         }
366                     }
367                     throw new NoSuchElementException  ("No more elements exist in the collection");
368                 }
369             }
370             else {
371                 // we haven't started to iterate at all.
372                 // start searching from the first list
373                 for (int i=0 ; i<lists.length ; i++) {
374                     if (!lists[i].isEmpty()) {
375                         currentList = i;
376                         currentElement = 0;
377                         nextCalled = true;
378                         return lists[currentList].get(currentElement);
379                     }
380                 }
381                 throw new NoSuchElementException  ("No more elements exist in the collection");
382             }           
383         } // next()
384     } // PriorityIterator
385 
386     /*class PriorityObject implements Prioritizeable {
387         
388         private byte priority;
389         
390         public PriorityObject(byte prio) {
391             priority = prio;
392         }
393         
394         public byte getPriority() {
395             return priority;
396         }
397         
398         public String toString() {
399             return "my priority is "+priority;
400         }
401     }
402     
403     public static void main(String[] args) {
404         PrioritizedList list = new PrioritizedList(10);
405         
406         Random r = new Random(System.currentTimeMillis());
407         
408         Collection c = new ArrayList();
409         for (int i=0 ; i<10 ; i++) {
410             //int n = Math.abs(r.nextInt());
411             byte b = (byte)(i);
412             System.out.println("Created object with priority: "+b);
413             list.add(list.new PriorityObject(b));
414         }
415         System.out.println("Iterate right");
416         
417         Iterator it3 = list.iterator();
418         while (it3.hasNext()) {
419             try {
420                 Thread.sleep(100);
421             } catch (InterruptedException e) {
422                 // TODO Auto-generated catch block
423                 e.printStackTrace();
424             }
425             Object x = it3.next();
426             System.out.println(x.toString());
427         }
428         System.out.println("Iterate wrong");
429         Iterator it = list.iterator();
430         int i = 0;
431         if (it.hasNext()) {
432             Object x = it.next();
433             System.out.println(x.toString());
434             it.remove();
435         }
436         if (it.hasNext()) {
437             Object x = it.next();
438             System.out.println(x.toString());
439             it.remove();
440         }
441         if (it.hasNext()) {
442             it.remove();
443         }
444 
445 //      System.out.println("Again");
446 //      Iterator it2 = list.iterator();
447 //      while (it2.hasNext()) {
448 //          Object x = it2.next();
449 //          System.out.println(x.toString());
450 //      }
451         
452     }*/
453     
454 }
455
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags