KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > thoughtworks > xstream > core > util > PrioritizedList


1 package com.thoughtworks.xstream.core.util;
2
3 import com.thoughtworks.xstream.converters.Converter;
4
5 import java.util.Iterator JavaDoc;
6
7 /**
8  * List that allows items to be added with a priority that will affect the order in which they are later iterated over.
9  *
10  * Objects with a high priority will appear before objects with a low priority in the list. If two objects of the same
11  * priority are added to the list, the most recently added one will be iterated over first.
12  *
13  * @author Joe Walnes
14  */
15 public class PrioritizedList {
16
17     /**
18      * Start of forward only linked list. Each item contains a value, priority and pointer to next item.
19      * The first item does not contain a value, rather just a pointer to the next real item. This makes
20      * the add() algorithm easier as there is no special case for adding to the beginning of the list.
21      */
22     private final LinkedItem pointerToFirst = new LinkedItem(null, 0, null);
23
24     private int lowestPriority = Integer.MAX_VALUE;
25
26     /**
27      * Add an item with a default priority of zero.
28      */
29     public void add(Object JavaDoc item) {
30         add(item, 0);
31     }
32
33     public void add(Object JavaDoc item, int priority) {
34         // Note: this is quite efficient if the client tends to add low priority items before high priority items
35 // as it will not have to iterate over much of the list. However for the other way round, maybe some
36 // optimizations can be made? -joe
37 LinkedItem current = pointerToFirst;
38         while(current.next != null && priority < current.next.priority) {
39             current = current.next;
40         }
41         current.next = new LinkedItem(item, priority, current.next);
42         if (priority < lowestPriority) {
43             lowestPriority = priority;
44         }
45     }
46
47     public Iterator JavaDoc iterator() {
48         return new LinkedItemIterator(pointerToFirst.next);
49     }
50
51     public Object JavaDoc firstOfLowestPriority() {
52         for(LinkedItem current = pointerToFirst.next; current != null; current = current.next) {
53             if (current.priority == lowestPriority) {
54                 return current.value;
55             }
56         }
57         return null;
58     }
59
60     private static class LinkedItem {
61
62         final Object JavaDoc value;
63         final int priority;
64
65         LinkedItem next;
66
67         public LinkedItem(Object JavaDoc value, int priority, LinkedItem next) {
68             this.value = value;
69             this.priority = priority;
70             this.next = next;
71         }
72
73     }
74
75     private static class LinkedItemIterator implements Iterator JavaDoc {
76
77         private LinkedItem current;
78
79         public LinkedItemIterator(LinkedItem current) {
80             this.current = current;
81         }
82
83         public void remove() {
84             throw new UnsupportedOperationException JavaDoc();
85         }
86
87         public boolean hasNext() {
88             return current != null;
89         }
90
91         public Object JavaDoc next() {
92             Object JavaDoc result = current.value;
93             current = current.next;
94             return result;
95         }
96
97     }
98
99 }
100
Popular Tags