/*
 * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package javax.imageio.spi;

import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

A set of Objects with pairwise orderings between them. The iterator method provides the elements in topologically sorted order. Elements participating in a cycle are not returned. Unlike the SortedSet and SortedMap interfaces, which require their elements to implement the Comparable interface, this class receives ordering information via its setOrdering and unsetPreference methods. This difference is due to the fact that the relevant ordering between elements is unlikely to be inherent in the elements themselves; rather, it is set dynamically accoring to application policy. For example, in a service provider registry situation, an application might allow the user to set a preference order for service provider objects supplied by a trusted vendor over those supplied by another.
/** * A set of <code>Object</code>s with pairwise orderings between them. * The <code>iterator</code> method provides the elements in * topologically sorted order. Elements participating in a cycle * are not returned. * * Unlike the <code>SortedSet</code> and <code>SortedMap</code> * interfaces, which require their elements to implement the * <code>Comparable</code> interface, this class receives ordering * information via its <code>setOrdering</code> and * <code>unsetPreference</code> methods. This difference is due to * the fact that the relevant ordering between elements is unlikely to * be inherent in the elements themselves; rather, it is set * dynamically accoring to application policy. For example, in a * service provider registry situation, an application might allow the * user to set a preference order for service provider objects * supplied by a trusted vendor over those supplied by another. * */
class PartiallyOrderedSet extends AbstractSet { // The topological sort (roughly) follows the algorithm described in // Horowitz and Sahni, _Fundamentals of Data Structures_ (1976), // p. 315. // Maps Objects to DigraphNodes that contain them private Map poNodes = new HashMap(); // The set of Objects private Set nodes = poNodes.keySet();
Constructs a PartiallyOrderedSet.
/** * Constructs a <code>PartiallyOrderedSet</code>. */
public PartiallyOrderedSet() {} public int size() { return nodes.size(); } public boolean contains(Object o) { return nodes.contains(o); }
Returns an iterator over the elements contained in this collection, with an ordering that respects the orderings set by the setOrdering method.
/** * Returns an iterator over the elements contained in this * collection, with an ordering that respects the orderings set * by the <code>setOrdering</code> method. */
public Iterator iterator() { return new PartialOrderIterator(poNodes.values().iterator()); }
Adds an Object to this PartiallyOrderedSet.
/** * Adds an <code>Object</code> to this * <code>PartiallyOrderedSet</code>. */
public boolean add(Object o) { if (nodes.contains(o)) { return false; } DigraphNode node = new DigraphNode(o); poNodes.put(o, node); return true; }
Removes an Object from this PartiallyOrderedSet.
/** * Removes an <code>Object</code> from this * <code>PartiallyOrderedSet</code>. */
public boolean remove(Object o) { DigraphNode node = (DigraphNode)poNodes.get(o); if (node == null) { return false; } poNodes.remove(o); node.dispose(); return true; } public void clear() { poNodes.clear(); }
Sets an ordering between two nodes. When an iterator is requested, the first node will appear earlier in the sequence than the second node. If a prior ordering existed between the nodes in the opposite order, it is removed.
Returns:true if no prior ordering existed between the nodes, falseotherwise.
/** * Sets an ordering between two nodes. When an iterator is * requested, the first node will appear earlier in the * sequence than the second node. If a prior ordering existed * between the nodes in the opposite order, it is removed. * * @return <code>true</code> if no prior ordering existed * between the nodes, <code>false</code>otherwise. */
public boolean setOrdering(Object first, Object second) { DigraphNode firstPONode = (DigraphNode)poNodes.get(first); DigraphNode secondPONode = (DigraphNode)poNodes.get(second); secondPONode.removeEdge(firstPONode); return firstPONode.addEdge(secondPONode); }
Removes any ordering between two nodes.
Returns:true if a prior prefence existed between the nodes.
/** * Removes any ordering between two nodes. * * @return true if a prior prefence existed between the nodes. */
public boolean unsetOrdering(Object first, Object second) { DigraphNode firstPONode = (DigraphNode)poNodes.get(first); DigraphNode secondPONode = (DigraphNode)poNodes.get(second); return firstPONode.removeEdge(secondPONode) || secondPONode.removeEdge(firstPONode); }
Returns true if an ordering exists between two nodes.
/** * Returns <code>true</code> if an ordering exists between two * nodes. */
public boolean hasOrdering(Object preferred, Object other) { DigraphNode preferredPONode = (DigraphNode)poNodes.get(preferred); DigraphNode otherPONode = (DigraphNode)poNodes.get(other); return preferredPONode.hasEdge(otherPONode); } } class PartialOrderIterator implements Iterator { LinkedList zeroList = new LinkedList(); Map inDegrees = new HashMap(); // DigraphNode -> Integer public PartialOrderIterator(Iterator iter) { // Initialize scratch in-degree values, zero list while (iter.hasNext()) { DigraphNode node = (DigraphNode)iter.next(); int inDegree = node.getInDegree(); inDegrees.put(node, new Integer(inDegree)); // Add nodes with zero in-degree to the zero list if (inDegree == 0) { zeroList.add(node); } } } public boolean hasNext() { return !zeroList.isEmpty(); } public Object next() { DigraphNode first = (DigraphNode)zeroList.removeFirst(); // For each out node of the output node, decrement its in-degree Iterator outNodes = first.getOutNodes(); while (outNodes.hasNext()) { DigraphNode node = (DigraphNode)outNodes.next(); int inDegree = ((Integer)inDegrees.get(node)).intValue() - 1; inDegrees.put(node, new Integer(inDegree)); // If the in-degree has fallen to 0, place the node on the list if (inDegree == 0) { zeroList.add(node); } } return first.getData(); } public void remove() { throw new UnsupportedOperationException(); } }