- /*
- * @(#)PartiallyOrderedSet.java 1.9 03/01/23
- *
- * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
- * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
- */
-
- 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 <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.
- *
- * @version 0.5
- */
- 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 <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 <code>setOrdering</code> method.
- */
- public Iterator iterator() {
- return new PartialOrderIterator(poNodes.values().iterator());
- }
-
- /**
- * 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 <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.
- *
- * @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(secondPONode);
- return firstPONode.addEdge(secondPONode);
- }
-
- /**
- * 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 <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();
- }
- }