1/*
2 * Copyright (c) 2000, 2014, 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
26package javax.imageio.spi;
27
28import java.io.Serializable;
29import java.util.HashSet;
30import java.util.Iterator;
31import java.util.Set;
32
33/**
34 * A node in a directed graph.  In addition to an arbitrary
35 * {@code Object} containing user data associated with the node,
36 * each node maintains a {@code Set}s of nodes which are pointed
37 * to by the current node (available from {@code getOutNodes}).
38 * The in-degree of the node (that is, number of nodes that point to
39 * the current node) may be queried.
40 *
41 */
42class DigraphNode<E> implements Cloneable, Serializable {
43    private static final long serialVersionUID = 5308261378582246841L;
44
45    /** The data associated with this node. */
46    protected E data;
47
48    /**
49     * A {@code Set} of neighboring nodes pointed to by this
50     * node.
51     */
52    protected Set<DigraphNode<E>> outNodes = new HashSet<>();
53
54    /** The in-degree of the node. */
55    protected int inDegree = 0;
56
57    /**
58     * A {@code Set} of neighboring nodes that point to this
59     * node.
60     */
61    private Set<DigraphNode<E>> inNodes = new HashSet<>();
62
63    public DigraphNode(E data) {
64        this.data = data;
65    }
66
67    /** Returns the {@code Object} referenced by this node. */
68    public E getData() {
69        return data;
70    }
71
72    /**
73     * Returns an {@code Iterator} containing the nodes pointed
74     * to by this node.
75     */
76    public Iterator<DigraphNode<E>> getOutNodes() {
77        return outNodes.iterator();
78    }
79
80    /**
81     * Adds a directed edge to the graph.  The outNodes list of this
82     * node is updated and the in-degree of the other node is incremented.
83     *
84     * @param node a {@code DigraphNode}.
85     *
86     * @return {@code true} if the node was not previously the
87     * target of an edge.
88     */
89    public boolean addEdge(DigraphNode<E> node) {
90        if (outNodes.contains(node)) {
91            return false;
92        }
93
94        outNodes.add(node);
95        node.inNodes.add(this);
96        node.incrementInDegree();
97        return true;
98    }
99
100    /**
101     * Returns {@code true} if an edge exists between this node
102     * and the given node.
103     *
104     * @param node a {@code DigraphNode}.
105     *
106     * @return {@code true} if the node is the target of an edge.
107     */
108    public boolean hasEdge(DigraphNode<E> node) {
109        return outNodes.contains(node);
110    }
111
112    /**
113     * Removes a directed edge from the graph.  The outNodes list of this
114     * node is updated and the in-degree of the other node is decremented.
115     *
116     * @return {@code true} if the node was previously the target
117     * of an edge.
118     */
119    public boolean removeEdge(DigraphNode<E> node) {
120        if (!outNodes.contains(node)) {
121            return false;
122        }
123
124        outNodes.remove(node);
125        node.inNodes.remove(this);
126        node.decrementInDegree();
127        return true;
128    }
129
130    /**
131     * Removes this node from the graph, updating neighboring nodes
132     * appropriately.
133     */
134    public void dispose() {
135        Object[] inNodesArray = inNodes.toArray();
136        for(int i=0; i<inNodesArray.length; i++) {
137            @SuppressWarnings("unchecked")
138            DigraphNode<E> node = (DigraphNode<E>)inNodesArray[i];
139            node.removeEdge(this);
140        }
141
142        Object[] outNodesArray = outNodes.toArray();
143        for(int i=0; i<outNodesArray.length; i++) {
144            @SuppressWarnings("unchecked")
145            DigraphNode<E> node = (DigraphNode<E>)outNodesArray[i];
146            removeEdge(node);
147        }
148    }
149
150    /** Returns the in-degree of this node. */
151    public int getInDegree() {
152        return inDegree;
153    }
154
155    /** Increments the in-degree of this node. */
156    private void incrementInDegree() {
157        ++inDegree;
158    }
159
160    /** Decrements the in-degree of this node. */
161    private void decrementInDegree() {
162        --inDegree;
163    }
164}
165