Quadcap Embeddable Server

com/quadcap/util/collections/DiGraph.java

Go to the documentation of this file.

package com.quadcap.util.collections;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

//-//#ifdef JDK11
//-import com.sun.java.util.collections.ArrayList;
//-import com.sun.java.util.collections.Comparable;
//-import com.sun.java.util.collections.HashMap;
//-import com.sun.java.util.collections.HashSet;
//-import com.sun.java.util.collections.Iterator;
//-import com.sun.java.util.collections.Map;
//-import com.sun.java.util.collections.Set;
//#else
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
//#endif

import com.quadcap.util.Debug;

/**
 * A simple implementation of a directed graph of Objects.  Each node
 * is represented using HashSets of incoming and outgoing arcs.
 *
 * @author Stan Bailes
 */
public class DiGraph {
    // Could replace by any Map
    final HashMap                               nodes   = new HashMap();
    
    public DiGraph() {}

    public void addNode(Object obj) {
        mapNode(obj);
    }

    public final Iterator getNodes() {
        return new NodeIterator(nodes.values().iterator());
    }

    public void addArc(Object from, Object to) {
        Node f = mapNode(from);
        Node t = mapNode(to);
        f.addTo(t);
        t.addFrom(f);
    }

    public final boolean hasChildren(Object obj) {
        return mapNode(obj).toSize() > 0;
    }

    public final boolean hasParents(Object obj) {
        return mapNode(obj).fromSize() > 0;
    }

    public boolean hasNode(Object obj) {
        Node node = (Node)nodes.get(obj);
        return node != null;
    }

    public final Iterator getParents(Object to) {
        return new NodeIterator(mapNode(to).iterateFrom());
    }

    public final Iterator getChildren(Object from) {
        return new NodeIterator(mapNode(from).iterateTo());
    }

    public void removeNode(Object obj, boolean force) {
        Node node = mapNode(obj);
        if (!force) {
            if (node.toSize() != 0 || node.fromSize() != 0) {
                throw new RuntimeException("node has links");
            }
        } else {
            Iterator iter = node.iterateTo();
            while (iter.hasNext()) {
                Node to = (Node)iter.next();
                node.removeTo(to);
                to.removeFrom(node);
            }
            iter = node.iterateFrom();
            while (iter.hasNext()) {
                Node from = (Node)iter.next();
                node.removeFrom(from);
                from.removeTo(node);
            }
        }
        nodes.remove(obj);
    }

    public void removeArc(Object from, Object to) {
        Node f = mapNode(from);
        Node t = mapNode(to);
        f.removeTo(t);
        t.removeFrom(f);
    }

    public Iterator levelize() {
        return levelize(false);
    }
    
    public Iterator levelize(boolean cyclesOK) {
        ArrayList v = new ArrayList();
        Iterator iter = nodes.values().iterator();
        while (iter.hasNext()) {
            Node node = (Node)iter.next();
            node.level = -1;
            node.visitCnt = 0;
            if (node.fromSize() == 0) {
                node.level = 0;
                v.add(node);
            }
        }
        for (int i = 0; i < v.size(); i++) {
            Node node = (Node)v.get(i);
            Iterator t = node.iterateTo();
            while (t.hasNext()) {
                Node to = (Node)t.next();
                if (++to.visitCnt == to.fromSize()) {
                    to.level = node.level + 1;
                    v.add(to);
                }
            }
        }
        if (!cyclesOK && v.size() != nodes.size()) {
            throw new RuntimeException("can't levelize, contains cycles");
        }
        return new NodeIterator(v.iterator());
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        Iterator iter = getNodes();
        String ldelim = "";
        while (iter.hasNext()) {
            sb.append(ldelim);
            ldelim = "\n";
            Object obj = iter.next();
            Iterator i2 = getParents(obj);
            String delim = "";
            sb.append("(");
            while (i2.hasNext()) {
                sb.append(delim);
                delim = " ";
                sb.append(i2.next().toString());
            }
            sb.append(") ");
            sb.append(obj.toString());
            sb.append(" (");
            i2 = getChildren(obj);
            delim = "";
            while (i2.hasNext()) {
                sb.append(delim);
                delim = " ";
                sb.append(i2.next().toString());
            }
            sb.append(") ");
        }
        return sb.toString();
    }

    final Node mapNode(Object obj) {
        Node node = (Node)nodes.get(obj);
        if (node == null) {
            node = new Node(obj);
            nodes.put(obj, node);
        }
        return node;
    }
                
    class Node implements Comparable {
        Object                  obj;

        final HashSet           to              = new HashSet();
        final HashSet           from            = new HashSet();
        int                     level           = 0;
        int                     visitCnt        = 0;

        Node(Object obj) { this.obj = obj; }    
        void addTo(Node node) {
            to.add(node);
        }
        void addFrom(Node node) {
            from.add(node);
        }
        void removeTo(Node obj) { to.remove(obj); }
        void removeFrom(Node obj) { from.remove(obj); }

        int toSize() { return to.size(); }
        int fromSize() { return from.size(); }

        Iterator iterateTo() { return to.iterator(); }
        Iterator iterateFrom() { return from.iterator(); }

        public int compareTo(Object other) {
            Node no = (Node)other;
            return ((Comparable)obj).compareTo(no.obj);
        }

        public int hashCode() { return obj.hashCode(); }

        public boolean equals(Object obj) {
            return 0 == compareTo(obj);
        }
        public String toString() {
            return obj.toString();
        }
    }

    class NodeIterator implements Iterator {
        Iterator                        iter;
        NodeIterator(Iterator iter) { this.iter = iter; }
        public boolean hasNext() { return iter.hasNext(); }
        public Object next() {
            Node node = (Node)iter.next();
            return node.obj;
        }
        public void remove() {}
    }
}