Java example source code file (PartiallyOrderedSet.java)

This example Java source code file (PartiallyOrderedSet.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

abstractset, digraphnode, hashmap, integer, iterator, linkedlist, map, object, partiallyorderedset, partialorderiterator, unsupportedoperationexception, util

The PartiallyOrderedSet.java Java example source code

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

    /**
     * Adds an <code>Object to this
     * <code>PartiallyOrderedSet.
     */
    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 from this
     * <code>PartiallyOrderedSet.
     */
    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 if no prior ordering existed
     * between the nodes, <code>falseotherwise.
     */
    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.
     *
     * @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 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();
    }
}