1 /* 2 * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package javax.imageio.spi; 27 28 import java.util.AbstractSet; 29 import java.util.HashMap; 30 import java.util.Iterator; 31 import java.util.LinkedList; 32 import java.util.Map; 33 import java.util.Set; 34 35 /** 36 * A set of <code>Object</code>s with pairwise orderings between them. 37 * The <code>iterator</code> method provides the elements in 38 * topologically sorted order. Elements participating in a cycle 39 * are not returned. 40 * 41 * Unlike the <code>SortedSet</code> and <code>SortedMap</code> 42 * interfaces, which require their elements to implement the 43 * <code>Comparable</code> interface, this class receives ordering 44 * information via its <code>setOrdering</code> and 45 * <code>unsetPreference</code> methods. This difference is due to 46 * the fact that the relevant ordering between elements is unlikely to 47 * be inherent in the elements themselves; rather, it is set 48 * dynamically accoring to application policy. For example, in a 49 * service provider registry situation, an application might allow the 50 * user to set a preference order for service provider objects 51 * supplied by a trusted vendor over those supplied by another. 52 * 53 */ 54 class PartiallyOrderedSet extends AbstractSet { 55 56 // The topological sort (roughly) follows the algorithm described in 57 // Horowitz and Sahni, _Fundamentals of Data Structures_ (1976), 58 // p. 315. 59 60 // Maps Objects to DigraphNodes that contain them 61 private Map poNodes = new HashMap(); 62 63 // The set of Objects 64 private Set nodes = poNodes.keySet(); 65 66 /** 67 * Constructs a <code>PartiallyOrderedSet</code>. 68 */ 69 public PartiallyOrderedSet() {} 70 71 public int size() { 72 return nodes.size(); 73 } 74 75 public boolean contains(Object o) { 76 return nodes.contains(o); 77 } 78 79 /** 80 * Returns an iterator over the elements contained in this 81 * collection, with an ordering that respects the orderings set 82 * by the <code>setOrdering</code> method. 83 */ 84 public Iterator iterator() { 85 return new PartialOrderIterator(poNodes.values().iterator()); 86 } 87 88 /** 89 * Adds an <code>Object</code> to this 90 * <code>PartiallyOrderedSet</code>. 91 */ 92 public boolean add(Object o) { 93 if (nodes.contains(o)) { 94 return false; 95 } 96 97 DigraphNode node = new DigraphNode(o); 98 poNodes.put(o, node); 99 return true; 100 } 101 102 /** 103 * Removes an <code>Object</code> from this 104 * <code>PartiallyOrderedSet</code>. 105 */ 106 public boolean remove(Object o) { 107 DigraphNode node = (DigraphNode)poNodes.get(o); 108 if (node == null) { 109 return false; 110 } 111 112 poNodes.remove(o); 113 node.dispose(); 114 return true; 115 } 116 117 public void clear() { 118 poNodes.clear(); 119 } 120 121 /** 122 * Sets an ordering between two nodes. When an iterator is 123 * requested, the first node will appear earlier in the 124 * sequence than the second node. If a prior ordering existed 125 * between the nodes in the opposite order, it is removed. 126 * 127 * @return <code>true</code> if no prior ordering existed 128 * between the nodes, <code>false</code>otherwise. 129 */ 130 public boolean setOrdering(Object first, Object second) { 131 DigraphNode firstPONode = 132 (DigraphNode)poNodes.get(first); 133 DigraphNode secondPONode = 134 (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 = 147 (DigraphNode)poNodes.get(first); 148 DigraphNode secondPONode = 149 (DigraphNode)poNodes.get(second); 150 151 return firstPONode.removeEdge(secondPONode) || 152 secondPONode.removeEdge(firstPONode); 153 } 154 155 /** 156 * Returns <code>true</code> if an ordering exists between two 157 * nodes. 158 */ 159 public boolean hasOrdering(Object preferred, Object other) { 160 DigraphNode preferredPONode = 161 (DigraphNode)poNodes.get(preferred); 162 DigraphNode otherPONode = 163 (DigraphNode)poNodes.get(other); 164 165 return preferredPONode.hasEdge(otherPONode); 166 } 167 } 168 169 class PartialOrderIterator implements Iterator { 170 171 LinkedList zeroList = new LinkedList(); 172 Map inDegrees = new HashMap(); // DigraphNode -> Integer 173 174 public PartialOrderIterator(Iterator iter) { 175 // Initialize scratch in-degree values, zero list 176 while (iter.hasNext()) { 177 DigraphNode node = (DigraphNode)iter.next(); 178 int inDegree = node.getInDegree(); 179 inDegrees.put(node, new Integer(inDegree)); 180 181 // Add nodes with zero in-degree to the zero list 182 if (inDegree == 0) { 183 zeroList.add(node); 184 } 185 } 186 } 187 188 public boolean hasNext() { 189 return !zeroList.isEmpty(); 190 } 191 192 public Object next() { 193 DigraphNode first = (DigraphNode)zeroList.removeFirst(); 194 195 // For each out node of the output node, decrement its in-degree 196 Iterator outNodes = first.getOutNodes(); 197 while (outNodes.hasNext()) { 198 DigraphNode node = (DigraphNode)outNodes.next(); 199 int inDegree = ((Integer)inDegrees.get(node)).intValue() - 1; 200 inDegrees.put(node, new Integer(inDegree)); 201 202 // If the in-degree has fallen to 0, place the node on the list 203 if (inDegree == 0) { 204 zeroList.add(node); 205 } 206 } 207 208 return first.getData(); 209 } 210 211 public void remove() { 212 throw new UnsupportedOperationException(); 213 } 214 }