KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > javax > imageio > spi > PartiallyOrderedSet


1 /*
2  * @(#)PartiallyOrderedSet.java 1.11 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package javax.imageio.spi;
9
10 import java.util.AbstractSet JavaDoc;
11 import java.util.HashMap JavaDoc;
12 import java.util.Iterator JavaDoc;
13 import java.util.LinkedList JavaDoc;
14 import java.util.Map JavaDoc;
15 import java.util.Set JavaDoc;
16
17 /**
18  * A set of <code>Object</code>s with pairwise orderings between them.
19  * The <code>iterator</code> method provides the elements in
20  * topologically sorted order. Elements participating in a cycle
21  * are not returned.
22  *
23  * Unlike the <code>SortedSet</code> and <code>SortedMap</code>
24  * interfaces, which require their elements to implement the
25  * <code>Comparable</code> interface, this class receives ordering
26  * information via its <code>setOrdering</code> and
27  * <code>unsetPreference</code> methods. This difference is due to
28  * the fact that the relevant ordering between elements is unlikely to
29  * be inherent in the elements themselves; rather, it is set
30  * dynamically accoring to application policy. For example, in a
31  * service provider registry situation, an application might allow the
32  * user to set a preference order for service provider objects
33  * supplied by a trusted vendor over those supplied by another.
34  *
35  * @version 0.5
36  */
37 class PartiallyOrderedSet extends AbstractSet JavaDoc {
38
39     // The topological sort (roughly) follows the algorithm described in
40 // Horowitz and Sahni, _Fundamentals of Data Structures_ (1976),
41 // p. 315.
42
43     // Maps Objects to DigraphNodes that contain them
44 private Map JavaDoc poNodes = new HashMap JavaDoc();
45
46     // The set of Objects
47 private Set JavaDoc nodes = poNodes.keySet();
48
49     /**
50      * Constructs a <code>PartiallyOrderedSet</code>.
51      */
52     public PartiallyOrderedSet() {}
53
54     public int size() {
55         return nodes.size();
56     }
57
58     public boolean contains(Object JavaDoc o) {
59         return nodes.contains(o);
60     }
61
62     /**
63      * Returns an iterator over the elements contained in this
64      * collection, with an ordering that respects the orderings set
65      * by the <code>setOrdering</code> method.
66      */
67     public Iterator JavaDoc iterator() {
68         return new PartialOrderIterator(poNodes.values().iterator());
69     }
70
71     /**
72      * Adds an <code>Object</code> to this
73      * <code>PartiallyOrderedSet</code>.
74      */
75     public boolean add(Object JavaDoc o) {
76         if (nodes.contains(o)) {
77             return false;
78         }
79         
80         DigraphNode JavaDoc node = new DigraphNode JavaDoc(o);
81         poNodes.put(o, node);
82         return true;
83     }
84
85     /**
86      * Removes an <code>Object</code> from this
87      * <code>PartiallyOrderedSet</code>.
88      */
89     public boolean remove(Object JavaDoc o) {
90         DigraphNode JavaDoc node = (DigraphNode JavaDoc)poNodes.get(o);
91         if (node == null) {
92             return false;
93         }
94
95         poNodes.remove(o);
96         node.dispose();
97         return true;
98     }
99
100     public void clear() {
101         poNodes.clear();
102     }
103
104     /**
105      * Sets an ordering between two nodes. When an iterator is
106      * requested, the first node will appear earlier in the
107      * sequence than the second node. If a prior ordering existed
108      * between the nodes in the opposite order, it is removed.
109      *
110      * @return <code>true</code> if no prior ordering existed
111      * between the nodes, <code>false</code>otherwise.
112      */
113     public boolean setOrdering(Object JavaDoc first, Object JavaDoc second) {
114         DigraphNode JavaDoc firstPONode =
115             (DigraphNode JavaDoc)poNodes.get(first);
116         DigraphNode JavaDoc secondPONode =
117             (DigraphNode JavaDoc)poNodes.get(second);
118         
119         secondPONode.removeEdge(firstPONode);
120         return firstPONode.addEdge(secondPONode);
121     }
122
123     /**
124      * Removes any ordering between two nodes.
125      *
126      * @return true if a prior prefence existed between the nodes.
127      */
128     public boolean unsetOrdering(Object JavaDoc first, Object JavaDoc second) {
129         DigraphNode JavaDoc firstPONode =
130             (DigraphNode JavaDoc)poNodes.get(first);
131         DigraphNode JavaDoc secondPONode =
132             (DigraphNode JavaDoc)poNodes.get(second);
133
134         return firstPONode.removeEdge(secondPONode) ||
135             secondPONode.removeEdge(firstPONode);
136     }
137
138     /**
139      * Returns <code>true</code> if an ordering exists between two
140      * nodes.
141      */
142     public boolean hasOrdering(Object JavaDoc preferred, Object JavaDoc other) {
143         DigraphNode JavaDoc preferredPONode =
144             (DigraphNode JavaDoc)poNodes.get(preferred);
145         DigraphNode JavaDoc otherPONode =
146             (DigraphNode JavaDoc)poNodes.get(other);
147
148         return preferredPONode.hasEdge(otherPONode);
149     }
150 }
151
152 class PartialOrderIterator implements Iterator JavaDoc {
153
154     LinkedList JavaDoc zeroList = new LinkedList JavaDoc();
155     Map JavaDoc inDegrees = new HashMap JavaDoc(); // DigraphNode -> Integer
156
157     public PartialOrderIterator(Iterator JavaDoc iter) {
158         // Initialize scratch in-degree values, zero list
159 while (iter.hasNext()) {
160             DigraphNode JavaDoc node = (DigraphNode JavaDoc)iter.next();
161             int inDegree = node.getInDegree();
162             inDegrees.put(node, new Integer JavaDoc(inDegree));
163
164             // Add nodes with zero in-degree to the zero list
165 if (inDegree == 0) {
166                 zeroList.add(node);
167             }
168         }
169     }
170
171     public boolean hasNext() {
172         return !zeroList.isEmpty();
173     }
174
175     public Object JavaDoc next() {
176         DigraphNode JavaDoc first = (DigraphNode JavaDoc)zeroList.removeFirst();
177
178         // For each out node of the output node, decrement its in-degree
179 Iterator JavaDoc outNodes = first.getOutNodes();
180         while (outNodes.hasNext()) {
181             DigraphNode JavaDoc node = (DigraphNode JavaDoc)outNodes.next();
182             int inDegree = ((Integer JavaDoc)inDegrees.get(node)).intValue() - 1;
183             inDegrees.put(node, new Integer JavaDoc(inDegree));
184
185             // If the in-degree has fallen to 0, place the node on the list
186 if (inDegree == 0) {
187                 zeroList.add(node);
188             }
189         }
190
191         return first.getData();
192     }
193     
194     public void remove() {
195         throw new UnsupportedOperationException JavaDoc();
196     }
197 }
198
Popular Tags