/*
 * 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}s with pairwise orderings between them.
 * The {@code iterator} method provides the elements in
 * topologically sorted order.  Elements participating in a cycle
 * are not returned.
 *
 * Unlike the {@code SortedSet} and {@code SortedMap}
 * interfaces, which require their elements to implement the
 * {@code Comparable} interface, this class receives ordering
 * information via its {@code setOrdering} and
 * {@code 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.
 *
 */
class PartiallyOrderedSet<E> extends AbstractSet<E> {

    // 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<E, DigraphNode<E>> poNodes = new HashMap<>();

    // The set of Objects
    private Set<E> nodes = poNodes.keySet();

    
Constructs a PartiallyOrderedSet. /**
     * Constructs a {@code PartiallyOrderedSet}.
     */
    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} method.
     */
    public Iterator<E> iterator() {
        return new PartialOrderIterator<>(poNodes.values().iterator());
    }

    
Adds an Object to this PartiallyOrderedSet. /**
     * Adds an {@code Object} to this
     * {@code PartiallyOrderedSet}.
     */
    public boolean add(E o) {
        if (nodes.contains(o)) {
            return false;
        }

        DigraphNode<E> node = new DigraphNode<>(o);
        poNodes.put(o, node);
        return true;
    }

    
Removes an Object from this PartiallyOrderedSet. /**
     * Removes an {@code Object} from this
     * {@code PartiallyOrderedSet}.
     */
    public boolean remove(Object o) {
        DigraphNode<E> node = 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, false otherwise./**
     * 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} if no prior ordering existed
     * between the nodes, {@code false} otherwise.
     */
    public boolean setOrdering(E first, E second) {
        DigraphNode<E> firstPONode = poNodes.get(first);
        DigraphNode<E> secondPONode = 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(E first, E second) {
        DigraphNode<E> firstPONode = poNodes.get(first);
        DigraphNode<E> secondPONode = poNodes.get(second);

        return firstPONode.removeEdge(secondPONode) ||
            secondPONode.removeEdge(firstPONode);
    }

    
Returns true if an ordering exists between two nodes. /**
     * Returns {@code true} if an ordering exists between two
     * nodes.
     */
    public boolean hasOrdering(E preferred, E other) {
        DigraphNode<E> preferredPONode = poNodes.get(preferred);
        DigraphNode<E> otherPONode = poNodes.get(other);

        return preferredPONode.hasEdge(otherPONode);
    }
}

class PartialOrderIterator<E> implements Iterator<E> {

    LinkedList<DigraphNode<E>> zeroList = new LinkedList<>();
    Map<DigraphNode<E>, Integer> inDegrees = new HashMap<>();

    public PartialOrderIterator(Iterator<DigraphNode<E>> iter) {
        // Initialize scratch in-degree values, zero list
        while (iter.hasNext()) {
            DigraphNode<E> node = iter.next();
            int inDegree = node.getInDegree();
            inDegrees.put(node, inDegree);

            // Add nodes with zero in-degree to the zero list
            if (inDegree == 0) {
                zeroList.add(node);
            }
        }
    }

    public boolean hasNext() {
        return !zeroList.isEmpty();
    }

    public E next() {
        DigraphNode<E> first = zeroList.removeFirst();

        // For each out node of the output node, decrement its in-degree
        Iterator<DigraphNode<E>> outNodes = first.getOutNodes();
        while (outNodes.hasNext()) {
            DigraphNode<E> node = outNodes.next();
            int inDegree = inDegrees.get(node).intValue() - 1;
            inDegrees.put(node, 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();
    }
}