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}s with pairwise orderings between them. 37 * The {@code iterator} method provides the elements in 38 * topologically sorted order. Elements participating in a cycle 39 * are not returned. 40 * 41 * Unlike the {@code SortedSet} and {@code SortedMap} 42 * interfaces, which require their elements to implement the 43 * {@code Comparable} interface, this class receives ordering 44 * information via its {@code setOrdering} and 45 * {@code unsetPreference} 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<E> extends AbstractSet<E> { 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<E, DigraphNode<E>> poNodes = new HashMap<>(); 62 63 // The set of Objects 64 private Set<E> nodes = poNodes.keySet(); 65 66 /** 67 * Constructs a {@code PartiallyOrderedSet}. 68 */ PartiallyOrderedSet()69 public PartiallyOrderedSet() {} 70 size()71 public int size() { 72 return nodes.size(); 73 } 74 contains(Object o)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} method. 83 */ iterator()84 public Iterator<E> iterator() { 85 return new PartialOrderIterator<>(poNodes.values().iterator()); 86 } 87 88 /** 89 * Adds an {@code Object} to this 90 * {@code PartiallyOrderedSet}. 91 */ add(E o)92 public boolean add(E o) { 93 if (nodes.contains(o)) { 94 return false; 95 } 96 97 DigraphNode<E> node = new DigraphNode<>(o); 98 poNodes.put(o, node); 99 return true; 100 } 101 102 /** 103 * Removes an {@code Object} from this 104 * {@code PartiallyOrderedSet}. 105 */ remove(Object o)106 public boolean remove(Object o) { 107 DigraphNode<E> node = poNodes.get(o); 108 if (node == null) { 109 return false; 110 } 111 112 poNodes.remove(o); 113 node.dispose(); 114 return true; 115 } 116 clear()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} if no prior ordering existed 128 * between the nodes, {@code false} otherwise. 129 */ setOrdering(E first, E second)130 public boolean setOrdering(E first, E second) { 131 DigraphNode<E> firstPONode = poNodes.get(first); 132 DigraphNode<E> secondPONode = poNodes.get(second); 133 134 secondPONode.removeEdge(firstPONode); 135 return firstPONode.addEdge(secondPONode); 136 } 137 138 /** 139 * Removes any ordering between two nodes. 140 * 141 * @return true if a prior prefence existed between the nodes. 142 */ unsetOrdering(E first, E second)143 public boolean unsetOrdering(E first, E second) { 144 DigraphNode<E> firstPONode = poNodes.get(first); 145 DigraphNode<E> secondPONode = poNodes.get(second); 146 147 return firstPONode.removeEdge(secondPONode) || 148 secondPONode.removeEdge(firstPONode); 149 } 150 151 /** 152 * Returns {@code true} if an ordering exists between two 153 * nodes. 154 */ hasOrdering(E preferred, E other)155 public boolean hasOrdering(E preferred, E other) { 156 DigraphNode<E> preferredPONode = poNodes.get(preferred); 157 DigraphNode<E> otherPONode = poNodes.get(other); 158 159 return preferredPONode.hasEdge(otherPONode); 160 } 161 } 162 163 class PartialOrderIterator<E> implements Iterator<E> { 164 165 LinkedList<DigraphNode<E>> zeroList = new LinkedList<>(); 166 Map<DigraphNode<E>, Integer> inDegrees = new HashMap<>(); 167 PartialOrderIterator(Iterator<DigraphNode<E>> iter)168 public PartialOrderIterator(Iterator<DigraphNode<E>> iter) { 169 // Initialize scratch in-degree values, zero list 170 while (iter.hasNext()) { 171 DigraphNode<E> node = iter.next(); 172 int inDegree = node.getInDegree(); 173 inDegrees.put(node, inDegree); 174 175 // Add nodes with zero in-degree to the zero list 176 if (inDegree == 0) { 177 zeroList.add(node); 178 } 179 } 180 } 181 hasNext()182 public boolean hasNext() { 183 return !zeroList.isEmpty(); 184 } 185 next()186 public E next() { 187 DigraphNode<E> first = zeroList.removeFirst(); 188 189 // For each out node of the output node, decrement its in-degree 190 Iterator<DigraphNode<E>> outNodes = first.getOutNodes(); 191 while (outNodes.hasNext()) { 192 DigraphNode<E> node = outNodes.next(); 193 int inDegree = inDegrees.get(node).intValue() - 1; 194 inDegrees.put(node, inDegree); 195 196 // If the in-degree has fallen to 0, place the node on the list 197 if (inDegree == 0) { 198 zeroList.add(node); 199 } 200 } 201 202 return first.getData(); 203 } 204 remove()205 public void remove() { 206 throw new UnsupportedOperationException(); 207 } 208 } 209