001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.modules.languages.parser;
043:
044: import java.util.*;
045:
046: /**
047: * Directed Graph implementation.
048: *
049: * @author Jan Jancura
050: */
051: public class DG<N, E, K, V> {
052:
053: static <N, E, K, V> DG<N, E, K, V> createDG(N node) {
054: return new DG<N, E, K, V>(node);
055: }
056:
057: static <N, E, K, V> DG<N, E, K, V> createDG() {
058: return new DG<N, E, K, V>();
059: }
060:
061: private Map<N, Node<N, E, K, V>> idToNode = new HashMap<N, Node<N, E, K, V>>();
062: private Map<Node<N, E, K, V>, N> nodeToId = new HashMap<Node<N, E, K, V>, N>();
063: private N start;
064: private Set<N> ends = new HashSet<N>();
065:
066: private DG() {
067: }
068:
069: private DG(N node) {
070: start = node;
071: Node<N, E, K, V> n = new Node<N, E, K, V>();
072: idToNode.put(node, n);
073: nodeToId.put(n, node);
074: ends.add(node);
075: }
076:
077: N getStartNode() {
078: return start;
079: }
080:
081: void setStart(N node) {
082: if (idToNode.get(node) == null)
083: new NullPointerException();
084: start = node;
085: }
086:
087: Set<N> getEnds() {
088: return Collections.<N> unmodifiableSet(ends);
089: }
090:
091: void setEnds(Set<N> ends) {
092: this .ends = new HashSet<N>(ends);
093: }
094:
095: void addEnd(N end) {
096: assert (end != null);
097: ends.add(end);
098: }
099:
100: void removeEnd(N end) {
101: ends.remove(end);
102: }
103:
104: void addNode(N node) {
105: assert (node != null);
106: if (idToNode.containsKey(node)) {
107: //throw new IllegalArgumentException ();
108: return;
109: }
110: Node<N, E, K, V> n = new Node<N, E, K, V>();
111: idToNode.put(node, n);
112: nodeToId.put(n, node);
113: }
114:
115: void removeNode(N node) {
116: Node<N, E, K, V> n = idToNode.remove(node);
117: nodeToId.remove(n);
118: }
119:
120: boolean containsNode(N node) {
121: return idToNode.containsKey(node);
122: }
123:
124: Set<N> getNodes() {
125: return Collections.<N> unmodifiableSet(idToNode.keySet());
126: }
127:
128: N getNode(N node, E edge) {
129: Node<N, E, K, V> s = idToNode.get(node);
130: Node<N, E, K, V> e = s.getNode(edge);
131: return nodeToId.get(e);
132: }
133:
134: void addEdge(N startNode, N endNode, E edge) {
135: assert (startNode != null);
136: assert (endNode != null);
137: assert (edge != null);
138: Node<N, E, K, V> s = idToNode.get(startNode);
139: Node<N, E, K, V> e = idToNode.get(endNode);
140: assert (s != null);
141: assert (e != null);
142: s.addEdge(edge, e);
143: }
144:
145: Set<E> getEdges(N node) {
146: Node<N, E, K, V> n = idToNode.get(node);
147: return n.edges();
148: }
149:
150: E getEdge(N node, E edge) {
151: Node<N, E, K, V> n = idToNode.get(node);
152: return n.getEdge(edge);
153: }
154:
155: V getProperty(N node, K key) {
156: Node<N, E, K, V> n = idToNode.get(node);
157: return n.getProperty(key);
158: }
159:
160: Map<K, V> getProperties(N node) {
161: Node<N, E, K, V> n = idToNode.get(node);
162: if (n.properties == null)
163: return Collections.<K, V> emptyMap();
164: return Collections.<K, V> unmodifiableMap(n.properties);
165: }
166:
167: void putAllProperties(N node, Map<K, V> properties) {
168: if (properties.size() == 0)
169: return;
170: Node<N, E, K, V> n = idToNode.get(node);
171: if (n.properties == null)
172: n.properties = new HashMap<K, V>();
173: n.properties.putAll(properties);
174: }
175:
176: void setProperty(N node, K key, V value) {
177: Node<N, E, K, V> n = idToNode.get(node);
178: n.setProperty(key, value);
179: }
180:
181: V getProperty(N node, E edge, K key) {
182: Node<N, E, K, V> n = idToNode.get(node);
183: return n.getEdgeProperty(edge, key);
184: }
185:
186: Map<K, V> getProperties(N node, E edge) {
187: Node<N, E, K, V> n = idToNode.get(node);
188: if (n.idToProperties == null
189: || n.idToProperties.get(edge) == null)
190: return Collections.<K, V> emptyMap();
191: return Collections.<K, V> unmodifiableMap(n.idToProperties
192: .get(edge));
193: }
194:
195: void putAllProperties(N node, E edge, Map<K, V> properties) {
196: if (properties.size() == 0)
197: return;
198: Node<N, E, K, V> n = idToNode.get(node);
199: if (n.idToProperties == null)
200: n.idToProperties = new HashMap<E, Map<K, V>>();
201: if (n.idToProperties.get(edge) == null)
202: n.idToProperties.put(edge, new HashMap<K, V>());
203: n.idToProperties.get(edge).putAll(properties);
204: }
205:
206: void setProperty(N node, E edge, K key, V value) {
207: Node<N, E, K, V> n = idToNode.get(node);
208: n.setEdgeProperty(edge, key, value);
209: }
210:
211: void changeKey(N oldNode, N newNode) {
212: Node<N, E, K, V> n = idToNode.get(oldNode);
213: idToNode.remove(oldNode);
214: idToNode.put(newNode, n);
215: nodeToId.put(n, newNode);
216: }
217:
218: public String toString() {
219: StringBuffer sb = new StringBuffer();
220:
221: sb.append(" start: ").append(getStartNode()).append(" end: ");
222: Iterator<N> it = getEnds().iterator();
223: while (it.hasNext()) {
224: N end = it.next();
225: sb.append(end);
226: if (it.hasNext())
227: sb.append(',');
228: }
229: sb.append('\n');
230:
231: it = getNodes().iterator();
232: while (it.hasNext()) {
233: N node = it.next();
234: sb.append(node).append('(');
235: Iterator<E> it2 = getEdges(node).iterator();
236: while (it2.hasNext()) {
237: E edge = it2.next();
238: N end = getNode(node, edge);
239: sb.append(convert(edge)).append(end);
240: if (it2.hasNext())
241: sb.append(',');
242: }
243: sb.append(')');
244: sb.append('\n');
245: }
246:
247: it = getNodes().iterator();
248: while (it.hasNext()) {
249: N node = it.next();
250: Node<N, E, K, V> n = idToNode.get(node);
251: sb.append(" ").append(node).append(": ");
252: if (n.properties != null)
253: sb.append(n.properties);
254: sb.append('\n');
255: if (n.idToProperties != null) {
256: Iterator<E> it2 = n.idToProperties.keySet().iterator();
257: while (it2.hasNext()) {
258: E edge = it2.next();
259: Map<K, V> m = n.idToProperties.get(edge);
260: sb.append(" ").append(convert(edge))
261: .append(": ").append(m).append('\n');
262: }
263: }
264: }
265: return sb.toString();
266: }
267:
268: private static Character NN = new Character('\n');
269: private static Character NR = new Character('\n');
270: private static Character NT = new Character('\n');
271: private static Character NS = new Character('\n');
272:
273: private static final Character STAR = new Character((char) 0);
274:
275: private String convert(E edge) {
276: if (STAR.equals(edge))
277: return ".";
278: if (NN.equals(edge))
279: return "\\n";
280: if (NR.equals(edge))
281: return "\\r";
282: if (NT.equals(edge))
283: return "\\t";
284: if (NS.equals(edge))
285: return "' '";
286: return edge.toString();
287: }
288:
289: private static class Node<N, E, K, V> {
290:
291: private Map<K, V> properties;
292: private Map<E, Map<K, V>> idToProperties;
293: private Map<E, Node<N, E, K, V>> edgeToNode;
294: private Map<E, E> edges;
295:
296: V getProperty(K key) {
297: if (properties == null)
298: return null;
299: return properties.get(key);
300: }
301:
302: void setProperty(K key, V value) {
303: if (properties == null)
304: properties = new HashMap<K, V>();
305: properties.put(key, value);
306: }
307:
308: Node<N, E, K, V> getNode(E edge) {
309: if (edgeToNode == null)
310: return null;
311: return edgeToNode.get(edge);
312: }
313:
314: void addEdge(E edge, Node<N, E, K, V> node) {
315: if (edgeToNode == null)
316: edgeToNode = new HashMap<E, Node<N, E, K, V>>();
317: if (edges == null)
318: edges = new HashMap<E, E>();
319: edgeToNode.put(edge, node);
320: edges.put(edge, edge);
321: }
322:
323: E getEdge(E edge) {
324: if (edges == null)
325: return null;
326: return edges.get(edge);
327: }
328:
329: Set<E> edges() {
330: if (edgeToNode == null)
331: return Collections.<E> emptySet();
332: return edgeToNode.keySet();
333: }
334:
335: V getEdgeProperty(E edge, K key) {
336: if (idToProperties == null)
337: return null;
338: if (idToProperties.get(edge) == null)
339: return null;
340: return idToProperties.get(edge).get(key);
341: }
342:
343: void setEdgeProperty(E edge, K key, V value) {
344: if (idToProperties == null)
345: idToProperties = new HashMap<E, Map<K, V>>();
346: Map<K, V> m = idToProperties.get(edge);
347: if (m == null) {
348: m = new HashMap<K, V>();
349: idToProperties.put(edge, m);
350: }
351: m.put(key, value);
352: }
353: }
354: }
|