001: /*******************************************************************************
002: * Copyright (c) 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.ui.internal.texteditor.rulers;
011:
012: import java.util.Collections;
013: import java.util.Iterator;
014: import java.util.LinkedHashMap;
015: import java.util.LinkedHashSet;
016: import java.util.Map;
017: import java.util.Set;
018:
019: import org.eclipse.core.runtime.Assert;
020:
021: /**
022: * A directed acyclic graph. See http://en.wikipedia.org/wiki/Directed_acyclic_graph
023: *
024: * @since 3.3
025: */
026: public final class DAG {
027: /**
028: * Multimap, supports <code>null</code> key, but not <code>null</code> values.
029: */
030: private static final class MultiMap {
031: private final Map fMap = new LinkedHashMap();
032:
033: /**
034: * Adds <code>val</code> to the values mapped to by <code>key</code>. If
035: * <code>val</code> is <code>null</code>, <code>key</code> is added to the key set of
036: * the multimap.
037: *
038: * @param key the key
039: * @param val the value
040: */
041: public void put(Object key, Object val) {
042: Set values = (Set) fMap.get(key);
043: if (values == null) {
044: values = new LinkedHashSet();
045: fMap.put(key, values);
046: }
047: if (val != null)
048: values.add(val);
049: }
050:
051: /**
052: * Returns all mappings for the given key, an empty set if there are no mappings.
053: *
054: * @param key the key
055: * @return the mappings for <code>key</code>
056: */
057: public Set get(Object key) {
058: Set values = (Set) fMap.get(key);
059: return values == null ? Collections.EMPTY_SET : values;
060: }
061:
062: public Set keySet() {
063: return fMap.keySet();
064: }
065:
066: /**
067: * Removes all mappings for <code>key</code> and removes <code>key</code> from the key
068: * set.
069: *
070: * @param key the key to remove
071: * @return the removed mappings
072: */
073: public Set removeAll(Object key) {
074: Set values = (Set) fMap.remove(key);
075: return values == null ? Collections.EMPTY_SET : values;
076: }
077:
078: /**
079: * Removes a mapping from the multimap, but does not remove the <code>key</code> from the
080: * key set.
081: *
082: * @param key the key
083: * @param val the value
084: */
085: public void remove(Object key, Object val) {
086: Set values = (Set) fMap.get(key);
087: if (values != null)
088: values.remove(val);
089: }
090:
091: /*
092: * @see java.lang.Object#toString()
093: */
094: public String toString() {
095: return fMap.toString();
096: }
097: }
098:
099: private final MultiMap fOut = new MultiMap();
100: private final MultiMap fIn = new MultiMap();
101:
102: /**
103: * Adds a directed edge from <code>origin</code> to <code>target</code>. The vertices are not
104: * required to exist prior to this call - if they are not currently contained by the graph, they are
105: * automatically added.
106: *
107: * @param origin the origin vertex of the dependency
108: * @param target the target vertex of the dependency
109: * @return <code>true</code> if the edge was added, <code>false</code> if the
110: * edge was not added because it would have violated the acyclic nature of the
111: * receiver.
112: */
113: public boolean addEdge(Object origin, Object target) {
114: Assert.isLegal(origin != null);
115: Assert.isLegal(target != null);
116:
117: if (hasPath(target, origin))
118: return false;
119:
120: fOut.put(origin, target);
121: fOut.put(target, null);
122: fIn.put(target, origin);
123: fIn.put(origin, null);
124: return true;
125: }
126:
127: /**
128: * Adds a vertex to the graph. If the vertex does not exist prior to this call, it is added with
129: * no incoming or outgoing edges. Nothing happens if the vertex already exists.
130: *
131: * @param vertex the new vertex
132: */
133: public void addVertex(Object vertex) {
134: Assert.isLegal(vertex != null);
135: fOut.put(vertex, null);
136: fIn.put(vertex, null);
137: }
138:
139: /**
140: * Removes a vertex and all its edges from the graph.
141: *
142: * @param vertex the vertex to remove
143: */
144: public void removeVertex(Object vertex) {
145: Set targets = fOut.removeAll(vertex);
146: for (Iterator it = targets.iterator(); it.hasNext();)
147: fIn.remove(it.next(), vertex);
148: Set origins = fIn.removeAll(vertex);
149: for (Iterator it = origins.iterator(); it.hasNext();)
150: fOut.remove(it.next(), vertex);
151: }
152:
153: /**
154: * Returns the sources of the receiver. A source is a vertex with no incoming edges. The
155: * returned set's iterator traverses the nodes in the order they were added to the graph.
156: *
157: * @return the sources of the receiver
158: */
159: public Set getSources() {
160: return computeZeroEdgeVertices(fIn);
161: }
162:
163: /**
164: * Returns the sinks of the receiver. A sink is a vertex with no outgoing edges. The returned
165: * set's iterator traverses the nodes in the order they were added to the graph.
166: *
167: * @return the sinks of the receiver
168: */
169: public Set getSinks() {
170: return computeZeroEdgeVertices(fOut);
171: }
172:
173: private Set computeZeroEdgeVertices(MultiMap map) {
174: Set candidates = map.keySet();
175: Set roots = new LinkedHashSet(candidates.size());
176: for (Iterator it = candidates.iterator(); it.hasNext();) {
177: Object candidate = it.next();
178: if (map.get(candidate).isEmpty())
179: roots.add(candidate);
180: }
181: return roots;
182: }
183:
184: /**
185: * Returns the direct children of a vertex. The returned {@link Set} is unmodifiable.
186: *
187: * @param vertex the parent vertex
188: * @return the direct children of <code>vertex</code>
189: */
190: public Set getChildren(Object vertex) {
191: return Collections.unmodifiableSet(fOut.get(vertex));
192: }
193:
194: private boolean hasPath(Object start, Object end) {
195: // break condition
196: if (start == end)
197: return true;
198:
199: Set children = fOut.get(start);
200: for (Iterator it = children.iterator(); it.hasNext();)
201: // recursion
202: if (hasPath(it.next(), end))
203: return true;
204: return false;
205: }
206:
207: /*
208: * @see java.lang.Object#toString()
209: * @since 3.3
210: */
211: public String toString() {
212: return "Out: " + fOut.toString() + " In: " + fIn.toString(); //$NON-NLS-1$ //$NON-NLS-2$
213: }
214: }
|