001 /*
002 * Copyright 2000 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package javax.imageio.spi;
027
028 import java.util.AbstractSet;
029 import java.util.HashMap;
030 import java.util.Iterator;
031 import java.util.LinkedList;
032 import java.util.Map;
033 import java.util.Set;
034
035 /**
036 * A set of <code>Object</code>s with pairwise orderings between them.
037 * The <code>iterator</code> method provides the elements in
038 * topologically sorted order. Elements participating in a cycle
039 * are not returned.
040 *
041 * Unlike the <code>SortedSet</code> and <code>SortedMap</code>
042 * interfaces, which require their elements to implement the
043 * <code>Comparable</code> interface, this class receives ordering
044 * information via its <code>setOrdering</code> and
045 * <code>unsetPreference</code> methods. This difference is due to
046 * the fact that the relevant ordering between elements is unlikely to
047 * be inherent in the elements themselves; rather, it is set
048 * dynamically accoring to application policy. For example, in a
049 * service provider registry situation, an application might allow the
050 * user to set a preference order for service provider objects
051 * supplied by a trusted vendor over those supplied by another.
052 *
053 * @version 0.5
054 */
055 class PartiallyOrderedSet extends AbstractSet {
056
057 // The topological sort (roughly) follows the algorithm described in
058 // Horowitz and Sahni, _Fundamentals of Data Structures_ (1976),
059 // p. 315.
060
061 // Maps Objects to DigraphNodes that contain them
062 private Map poNodes = new HashMap();
063
064 // The set of Objects
065 private Set nodes = poNodes.keySet();
066
067 /**
068 * Constructs a <code>PartiallyOrderedSet</code>.
069 */
070 public PartiallyOrderedSet() {
071 }
072
073 public int size() {
074 return nodes.size();
075 }
076
077 public boolean contains(Object o) {
078 return nodes.contains(o);
079 }
080
081 /**
082 * Returns an iterator over the elements contained in this
083 * collection, with an ordering that respects the orderings set
084 * by the <code>setOrdering</code> method.
085 */
086 public Iterator iterator() {
087 return new PartialOrderIterator(poNodes.values().iterator());
088 }
089
090 /**
091 * Adds an <code>Object</code> to this
092 * <code>PartiallyOrderedSet</code>.
093 */
094 public boolean add(Object o) {
095 if (nodes.contains(o)) {
096 return false;
097 }
098
099 DigraphNode node = new DigraphNode(o);
100 poNodes.put(o, node);
101 return true;
102 }
103
104 /**
105 * Removes an <code>Object</code> from this
106 * <code>PartiallyOrderedSet</code>.
107 */
108 public boolean remove(Object o) {
109 DigraphNode node = (DigraphNode) poNodes.get(o);
110 if (node == null) {
111 return false;
112 }
113
114 poNodes.remove(o);
115 node.dispose();
116 return true;
117 }
118
119 public void clear() {
120 poNodes.clear();
121 }
122
123 /**
124 * Sets an ordering between two nodes. When an iterator is
125 * requested, the first node will appear earlier in the
126 * sequence than the second node. If a prior ordering existed
127 * between the nodes in the opposite order, it is removed.
128 *
129 * @return <code>true</code> if no prior ordering existed
130 * between the nodes, <code>false</code>otherwise.
131 */
132 public boolean setOrdering(Object first, Object second) {
133 DigraphNode firstPONode = (DigraphNode) poNodes.get(first);
134 DigraphNode secondPONode = (DigraphNode) poNodes.get(second);
135
136 secondPONode.removeEdge(firstPONode);
137 return firstPONode.addEdge(secondPONode);
138 }
139
140 /**
141 * Removes any ordering between two nodes.
142 *
143 * @return true if a prior prefence existed between the nodes.
144 */
145 public boolean unsetOrdering(Object first, Object second) {
146 DigraphNode firstPONode = (DigraphNode) poNodes.get(first);
147 DigraphNode secondPONode = (DigraphNode) poNodes.get(second);
148
149 return firstPONode.removeEdge(secondPONode)
150 || secondPONode.removeEdge(firstPONode);
151 }
152
153 /**
154 * Returns <code>true</code> if an ordering exists between two
155 * nodes.
156 */
157 public boolean hasOrdering(Object preferred, Object other) {
158 DigraphNode preferredPONode = (DigraphNode) poNodes
159 .get(preferred);
160 DigraphNode otherPONode = (DigraphNode) poNodes.get(other);
161
162 return preferredPONode.hasEdge(otherPONode);
163 }
164 }
165
166 class PartialOrderIterator implements Iterator {
167
168 LinkedList zeroList = new LinkedList();
169 Map inDegrees = new HashMap(); // DigraphNode -> Integer
170
171 public PartialOrderIterator(Iterator iter) {
172 // Initialize scratch in-degree values, zero list
173 while (iter.hasNext()) {
174 DigraphNode node = (DigraphNode) iter.next();
175 int inDegree = node.getInDegree();
176 inDegrees.put(node, new Integer(inDegree));
177
178 // Add nodes with zero in-degree to the zero list
179 if (inDegree == 0) {
180 zeroList.add(node);
181 }
182 }
183 }
184
185 public boolean hasNext() {
186 return !zeroList.isEmpty();
187 }
188
189 public Object next() {
190 DigraphNode first = (DigraphNode) zeroList.removeFirst();
191
192 // For each out node of the output node, decrement its in-degree
193 Iterator outNodes = first.getOutNodes();
194 while (outNodes.hasNext()) {
195 DigraphNode node = (DigraphNode) outNodes.next();
196 int inDegree = ((Integer) inDegrees.get(node)).intValue() - 1;
197 inDegrees.put(node, new Integer(inDegree));
198
199 // If the in-degree has fallen to 0, place the node on the list
200 if (inDegree == 0) {
201 zeroList.add(node);
202 }
203 }
204
205 return first.getData();
206 }
207
208 public void remove() {
209 throw new UnsupportedOperationException();
210 }
211 }
|