1 /*
   2  * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package javax.imageio.spi;
  27 
  28 import java.io.Serializable;
  29 import java.util.HashSet;
  30 import java.util.Iterator;
  31 import java.util.Set;
  32 
  33 /**
  34  * A node in a directed graph.  In addition to an arbitrary
  35  * <code>Object</code> containing user data associated with the node,
  36  * each node maintains a <code>Set</code>s of nodes which are pointed
  37  * to by the current node (available from <code>getOutNodes</code>).
  38  * The in-degree of the node (that is, number of nodes that point to
  39  * the current node) may be queried.
  40  *
  41  */
  42 class DigraphNode implements Cloneable, Serializable {
  43 
  44     /** The data associated with this node. */
  45     protected Object data;
  46 
  47     /**
  48      * A <code>Set</code> of neighboring nodes pointed to by this
  49      * node.
  50      */
  51     protected Set outNodes = new HashSet();
  52 
  53     /** The in-degree of the node. */
  54     protected int inDegree = 0;
  55 
  56     /**
  57      * A <code>Set</code> of neighboring nodes that point to this
  58      * node.
  59      */
  60     private Set inNodes = new HashSet();
  61 
  62     public DigraphNode(Object data) {
  63         this.data = data;
  64     }
  65 
  66     /** Returns the <code>Object</code> referenced by this node. */
  67     public Object getData() {
  68         return data;
  69     }
  70 
  71     /**
  72      * Returns an <code>Iterator</code> containing the nodes pointed
  73      * to by this node.
  74      */
  75     public Iterator getOutNodes() {
  76         return outNodes.iterator();
  77     }
  78 
  79     /**
  80      * Adds a directed edge to the graph.  The outNodes list of this
  81      * node is updated and the in-degree of the other node is incremented.
  82      *
  83      * @param node a <code>DigraphNode</code>.
  84      *
  85      * @return <code>true</code> if the node was not previously the
  86      * target of an edge.
  87      */
  88     public boolean addEdge(DigraphNode node) {
  89         if (outNodes.contains(node)) {
  90             return false;
  91         }
  92 
  93         outNodes.add(node);
  94         node.inNodes.add(this);
  95         node.incrementInDegree();
  96         return true;
  97     }
  98 
  99     /**
 100      * Returns <code>true</code> if an edge exists between this node
 101      * and the given node.
 102      *
 103      * @param node a <code>DigraphNode</code>.
 104      *
 105      * @return <code>true</code> if the node is the target of an edge.
 106      */
 107     public boolean hasEdge(DigraphNode node) {
 108         return outNodes.contains(node);
 109     }
 110 
 111     /**
 112      * Removes a directed edge from the graph.  The outNodes list of this
 113      * node is updated and the in-degree of the other node is decremented.
 114      *
 115      * @return <code>true</code> if the node was previously the target
 116      * of an edge.
 117      */
 118     public boolean removeEdge(DigraphNode node) {
 119         if (!outNodes.contains(node)) {
 120             return false;
 121         }
 122 
 123         outNodes.remove(node);
 124         node.inNodes.remove(this);
 125         node.decrementInDegree();
 126         return true;
 127     }
 128 
 129     /**
 130      * Removes this node from the graph, updating neighboring nodes
 131      * appropriately.
 132      */
 133     public void dispose() {
 134         Object[] inNodesArray = inNodes.toArray();
 135         for(int i=0; i<inNodesArray.length; i++) {
 136             DigraphNode node = (DigraphNode) inNodesArray[i];
 137             node.removeEdge(this);
 138         }
 139 
 140         Object[] outNodesArray = outNodes.toArray();
 141         for(int i=0; i<outNodesArray.length; i++) {
 142             DigraphNode node = (DigraphNode) outNodesArray[i];
 143             removeEdge(node);
 144         }
 145     }
 146 
 147     /** Returns the in-degree of this node. */
 148     public int getInDegree() {
 149         return inDegree;
 150     }
 151 
 152     /** Increments the in-degree of this node. */
 153     private void incrementInDegree() {
 154         ++inDegree;
 155     }
 156 
 157     /** Decrements the in-degree of this node. */
 158     private void decrementInDegree() {
 159         --inDegree;
 160     }
 161 }