KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > ui > internal > texteditor > rulers > DAG


1 /*******************************************************************************
2  * Copyright (c) 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.ui.internal.texteditor.rulers;
12
13 import java.util.Collections JavaDoc;
14 import java.util.Iterator JavaDoc;
15 import java.util.LinkedHashMap JavaDoc;
16 import java.util.LinkedHashSet JavaDoc;
17 import java.util.Map JavaDoc;
18 import java.util.Set JavaDoc;
19
20 import org.eclipse.core.runtime.Assert;
21
22 /**
23  * A directed acyclic graph. See http://en.wikipedia.org/wiki/Directed_acyclic_graph
24  *
25  * @since 3.3
26  */
27 public final class DAG {
28     /**
29      * Multimap, supports <code>null</code> key, but not <code>null</code> values.
30      */
31     private static final class MultiMap {
32         private final Map JavaDoc fMap= new LinkedHashMap JavaDoc();
33
34         /**
35          * Adds <code>val</code> to the values mapped to by <code>key</code>. If
36          * <code>val</code> is <code>null</code>, <code>key</code> is added to the key set of
37          * the multimap.
38          *
39          * @param key the key
40          * @param val the value
41          */
42         public void put(Object JavaDoc key, Object JavaDoc val) {
43             Set JavaDoc values= (Set JavaDoc) fMap.get(key);
44             if (values == null) {
45                 values= new LinkedHashSet JavaDoc();
46                 fMap.put(key, values);
47             }
48             if (val != null)
49                 values.add(val);
50         }
51
52         /**
53          * Returns all mappings for the given key, an empty set if there are no mappings.
54          *
55          * @param key the key
56          * @return the mappings for <code>key</code>
57          */
58         public Set JavaDoc get(Object JavaDoc key) {
59             Set JavaDoc values= (Set JavaDoc) fMap.get(key);
60             return values == null ? Collections.EMPTY_SET : values;
61         }
62
63         public Set JavaDoc keySet() {
64             return fMap.keySet();
65         }
66
67         /**
68          * Removes all mappings for <code>key</code> and removes <code>key</code> from the key
69          * set.
70          *
71          * @param key the key to remove
72          * @return the removed mappings
73          */
74         public Set JavaDoc removeAll(Object JavaDoc key) {
75             Set JavaDoc values= (Set JavaDoc) fMap.remove(key);
76             return values == null ? Collections.EMPTY_SET : values;
77         }
78
79         /**
80          * Removes a mapping from the multimap, but does not remove the <code>key</code> from the
81          * key set.
82          *
83          * @param key the key
84          * @param val the value
85          */
86         public void remove(Object JavaDoc key, Object JavaDoc val) {
87             Set JavaDoc values= (Set JavaDoc) fMap.get(key);
88             if (values != null)
89                 values.remove(val);
90         }
91         
92         /*
93          * @see java.lang.Object#toString()
94          */
95         public String JavaDoc toString() {
96             return fMap.toString();
97         }
98     }
99
100     private final MultiMap fOut= new MultiMap();
101     private final MultiMap fIn= new MultiMap();
102
103     /**
104      * Adds a directed edge from <code>origin</code> to <code>target</code>. The vertices are not
105      * required to exist prior to this call - if they are not currently contained by the graph, they are
106      * automatically added.
107      *
108      * @param origin the origin vertex of the dependency
109      * @param target the target vertex of the dependency
110      * @return <code>true</code> if the edge was added, <code>false</code> if the
111      * edge was not added because it would have violated the acyclic nature of the
112      * receiver.
113      */
114     public boolean addEdge(Object JavaDoc origin, Object JavaDoc target) {
115         Assert.isLegal(origin != null);
116         Assert.isLegal(target != null);
117
118         if (hasPath(target, origin))
119             return false;
120
121         fOut.put(origin, target);
122         fOut.put(target, null);
123         fIn.put(target, origin);
124         fIn.put(origin, null);
125         return true;
126     }
127
128     /**
129      * Adds a vertex to the graph. If the vertex does not exist prior to this call, it is added with
130      * no incoming or outgoing edges. Nothing happens if the vertex already exists.
131      *
132      * @param vertex the new vertex
133      */
134     public void addVertex(Object JavaDoc vertex) {
135         Assert.isLegal(vertex != null);
136         fOut.put(vertex, null);
137         fIn.put(vertex, null);
138     }
139
140     /**
141      * Removes a vertex and all its edges from the graph.
142      *
143      * @param vertex the vertex to remove
144      */
145     public void removeVertex(Object JavaDoc vertex) {
146         Set JavaDoc targets= fOut.removeAll(vertex);
147         for (Iterator JavaDoc it= targets.iterator(); it.hasNext();)
148             fIn.remove(it.next(), vertex);
149         Set JavaDoc origins= fIn.removeAll(vertex);
150         for (Iterator JavaDoc it= origins.iterator(); it.hasNext();)
151             fOut.remove(it.next(), vertex);
152     }
153
154     /**
155      * Returns the sources of the receiver. A source is a vertex with no incoming edges. The
156      * returned set's iterator traverses the nodes in the order they were added to the graph.
157      *
158      * @return the sources of the receiver
159      */
160     public Set JavaDoc getSources() {
161         return computeZeroEdgeVertices(fIn);
162     }
163
164     /**
165      * Returns the sinks of the receiver. A sink is a vertex with no outgoing edges. The returned
166      * set's iterator traverses the nodes in the order they were added to the graph.
167      *
168      * @return the sinks of the receiver
169      */
170     public Set JavaDoc getSinks() {
171         return computeZeroEdgeVertices(fOut);
172     }
173
174     private Set JavaDoc computeZeroEdgeVertices(MultiMap map) {
175         Set JavaDoc candidates= map.keySet();
176         Set JavaDoc roots= new LinkedHashSet JavaDoc(candidates.size());
177         for (Iterator JavaDoc it= candidates.iterator(); it.hasNext();) {
178             Object JavaDoc candidate= it.next();
179             if (map.get(candidate).isEmpty())
180                 roots.add(candidate);
181         }
182         return roots;
183     }
184
185     /**
186      * Returns the direct children of a vertex. The returned {@link Set} is unmodifiable.
187      *
188      * @param vertex the parent vertex
189      * @return the direct children of <code>vertex</code>
190      */
191     public Set JavaDoc getChildren(Object JavaDoc vertex) {
192         return Collections.unmodifiableSet(fOut.get(vertex));
193     }
194
195     private boolean hasPath(Object JavaDoc start, Object JavaDoc end) {
196         // break condition
197 if (start == end)
198             return true;
199
200         Set JavaDoc children= fOut.get(start);
201         for (Iterator JavaDoc it= children.iterator(); it.hasNext();)
202             // recursion
203 if (hasPath(it.next(), end))
204                 return true;
205         return false;
206     }
207     
208     /*
209      * @see java.lang.Object#toString()
210      * @since 3.3
211      */
212     public String JavaDoc toString() {
213         return "Out: " + fOut.toString() + " In: " + fIn.toString(); //$NON-NLS-1$ //$NON-NLS-2$
214 }
215 }
Popular Tags