KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > mr > core > util > 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 JavaDoc;
49 import java.util.Collection JavaDoc;
50 import java.util.Iterator JavaDoc;
51 import java.util.LinkedList JavaDoc;
52 import java.util.List JavaDoc;
53 import java.util.ListIterator JavaDoc;
54 import java.util.NoSuchElementException JavaDoc;
55 import java.util.Random JavaDoc;
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 JavaDoc {
65     
66     
67     int numberOfPriorities;
68     List JavaDoc[] lists ;
69     
70     public PrioritizedList(int numberOfPriorities){
71         this.numberOfPriorities = numberOfPriorities;
72         lists = new List JavaDoc[numberOfPriorities];
73         for (int i = 0; i < lists.length; i++) {
74             lists[i]= new LinkedList JavaDoc();
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 JavaDoc[] toArray() {
98         // not best solution but will do
99
return makeListFromLists().toArray();
100     }
101     
102     private List JavaDoc makeListFromLists() {
103         ArrayList JavaDoc result = new ArrayList JavaDoc();
104         for (int i = 0; i < lists.length; i++) {
105             result.addAll(lists[i]) ;
106         }
107         return result;
108     }
109     
110     public Object JavaDoc 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 JavaDoc 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 JavaDoc element) {
130         throw new UnsupportedOperationException JavaDoc();
131     }
132
133     public int indexOf(Object JavaDoc 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 JavaDoc 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 JavaDoc o) {
158         Prioritizeable p = (Prioritizeable) o;
159         return lists[(numberOfPriorities-1)-p.getPriority()].add(o);
160     }
161
162     public boolean contains(Object JavaDoc o) {
163         Prioritizeable p = (Prioritizeable) o;
164         return lists[(numberOfPriorities-1)-p.getPriority()].contains(o);
165     }
166
167     public boolean remove(Object JavaDoc o) {
168         Prioritizeable p = (Prioritizeable) o;
169         return lists[(numberOfPriorities-1)-p.getPriority()].remove(o);
170     }
171
172     public boolean addAll(int index, Collection JavaDoc c) {
173         throw new UnsupportedOperationException JavaDoc();
174     }
175
176     // returns true is the list has changes
177
public boolean addAll(Collection JavaDoc c) {
178         boolean result = false;
179         Object JavaDoc o;
180         boolean temp;
181         Iterator JavaDoc 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 JavaDoc c) {
191         Iterator JavaDoc 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 JavaDoc element){
201         Prioritizeable p = (Prioritizeable) element;
202         lists[(numberOfPriorities-1)-p.getPriority()].add(0,p);
203     }
204
205     public boolean containsAll(Collection JavaDoc c) {
206         Iterator JavaDoc ci = c.iterator();
207         Object JavaDoc 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 JavaDoc c) {
218         boolean result = false;
219         Iterator JavaDoc 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 JavaDoc c) {
231         clear();
232         return addAll(c);
233     }
234
235     public Iterator JavaDoc iterator() {
236         return new PriorityIterator();
237     }
238
239     public List JavaDoc subList(int fromIndex, int toIndex) {
240         // not best solution but will do
241
return makeListFromLists().subList(fromIndex, toIndex);
242     }
243
244     public ListIterator JavaDoc listIterator() {
245         // not best solution but will do
246
return makeListFromLists().listIterator();
247     }
248
249     public ListIterator JavaDoc listIterator(int index) {
250         // not best solution but will do
251
return makeListFromLists().listIterator(index);
252     }
253
254     public Object JavaDoc set(int index, Object JavaDoc element) {
255         throw new UnsupportedOperationException JavaDoc();
256     }
257
258     public Object JavaDoc[] toArray(Object JavaDoc[] 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 JavaDoc {
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 JavaDoc();
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 JavaDoc 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 JavaDoc("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 JavaDoc("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 JavaDoc("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
Popular Tags