001: package com.quadcap.util.collections;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: //-//#ifdef JDK11
042: //-import com.sun.java.util.collections.ArrayList;
043: //-import com.sun.java.util.collections.Comparable;
044: //-import com.sun.java.util.collections.HashMap;
045: //-import com.sun.java.util.collections.HashSet;
046: //-import com.sun.java.util.collections.Iterator;
047: //-import com.sun.java.util.collections.Map;
048: //-import com.sun.java.util.collections.Set;
049: //#else
050: import java.util.ArrayList;
051: import java.util.HashMap;
052: import java.util.HashSet;
053: import java.util.Iterator;
054: import java.util.Map;
055: import java.util.Set; //#endif
056:
057: import com.quadcap.util.Debug;
058:
059: /**
060: * A simple implementation of a directed graph of Objects. Each node
061: * is represented using HashSets of incoming and outgoing arcs.
062: *
063: * @author Stan Bailes
064: */
065: public class DiGraph {
066: // Could replace by any Map
067: final HashMap nodes = new HashMap();
068:
069: public DiGraph() {
070: }
071:
072: public void addNode(Object obj) {
073: mapNode(obj);
074: }
075:
076: public final Iterator getNodes() {
077: return new NodeIterator(nodes.values().iterator());
078: }
079:
080: public void addArc(Object from, Object to) {
081: Node f = mapNode(from);
082: Node t = mapNode(to);
083: f.addTo(t);
084: t.addFrom(f);
085: }
086:
087: public final boolean hasChildren(Object obj) {
088: return mapNode(obj).toSize() > 0;
089: }
090:
091: public final boolean hasParents(Object obj) {
092: return mapNode(obj).fromSize() > 0;
093: }
094:
095: public boolean hasNode(Object obj) {
096: Node node = (Node) nodes.get(obj);
097: return node != null;
098: }
099:
100: public final Iterator getParents(Object to) {
101: return new NodeIterator(mapNode(to).iterateFrom());
102: }
103:
104: public final Iterator getChildren(Object from) {
105: return new NodeIterator(mapNode(from).iterateTo());
106: }
107:
108: public void removeNode(Object obj, boolean force) {
109: Node node = mapNode(obj);
110: if (!force) {
111: if (node.toSize() != 0 || node.fromSize() != 0) {
112: throw new RuntimeException("node has links");
113: }
114: } else {
115: Iterator iter = node.iterateTo();
116: while (iter.hasNext()) {
117: Node to = (Node) iter.next();
118: node.removeTo(to);
119: to.removeFrom(node);
120: }
121: iter = node.iterateFrom();
122: while (iter.hasNext()) {
123: Node from = (Node) iter.next();
124: node.removeFrom(from);
125: from.removeTo(node);
126: }
127: }
128: nodes.remove(obj);
129: }
130:
131: public void removeArc(Object from, Object to) {
132: Node f = mapNode(from);
133: Node t = mapNode(to);
134: f.removeTo(t);
135: t.removeFrom(f);
136: }
137:
138: public Iterator levelize() {
139: return levelize(false);
140: }
141:
142: public Iterator levelize(boolean cyclesOK) {
143: ArrayList v = new ArrayList();
144: Iterator iter = nodes.values().iterator();
145: while (iter.hasNext()) {
146: Node node = (Node) iter.next();
147: node.level = -1;
148: node.visitCnt = 0;
149: if (node.fromSize() == 0) {
150: node.level = 0;
151: v.add(node);
152: }
153: }
154: for (int i = 0; i < v.size(); i++) {
155: Node node = (Node) v.get(i);
156: Iterator t = node.iterateTo();
157: while (t.hasNext()) {
158: Node to = (Node) t.next();
159: if (++to.visitCnt == to.fromSize()) {
160: to.level = node.level + 1;
161: v.add(to);
162: }
163: }
164: }
165: if (!cyclesOK && v.size() != nodes.size()) {
166: throw new RuntimeException(
167: "can't levelize, contains cycles");
168: }
169: return new NodeIterator(v.iterator());
170: }
171:
172: public String toString() {
173: StringBuffer sb = new StringBuffer();
174: Iterator iter = getNodes();
175: String ldelim = "";
176: while (iter.hasNext()) {
177: sb.append(ldelim);
178: ldelim = "\n";
179: Object obj = iter.next();
180: Iterator i2 = getParents(obj);
181: String delim = "";
182: sb.append("(");
183: while (i2.hasNext()) {
184: sb.append(delim);
185: delim = " ";
186: sb.append(i2.next().toString());
187: }
188: sb.append(") ");
189: sb.append(obj.toString());
190: sb.append(" (");
191: i2 = getChildren(obj);
192: delim = "";
193: while (i2.hasNext()) {
194: sb.append(delim);
195: delim = " ";
196: sb.append(i2.next().toString());
197: }
198: sb.append(") ");
199: }
200: return sb.toString();
201: }
202:
203: final Node mapNode(Object obj) {
204: Node node = (Node) nodes.get(obj);
205: if (node == null) {
206: node = new Node(obj);
207: nodes.put(obj, node);
208: }
209: return node;
210: }
211:
212: class Node implements Comparable {
213: Object obj;
214:
215: final HashSet to = new HashSet();
216: final HashSet from = new HashSet();
217: int level = 0;
218: int visitCnt = 0;
219:
220: Node(Object obj) {
221: this .obj = obj;
222: }
223:
224: void addTo(Node node) {
225: to.add(node);
226: }
227:
228: void addFrom(Node node) {
229: from.add(node);
230: }
231:
232: void removeTo(Node obj) {
233: to.remove(obj);
234: }
235:
236: void removeFrom(Node obj) {
237: from.remove(obj);
238: }
239:
240: int toSize() {
241: return to.size();
242: }
243:
244: int fromSize() {
245: return from.size();
246: }
247:
248: Iterator iterateTo() {
249: return to.iterator();
250: }
251:
252: Iterator iterateFrom() {
253: return from.iterator();
254: }
255:
256: public int compareTo(Object other) {
257: Node no = (Node) other;
258: return ((Comparable) obj).compareTo(no.obj);
259: }
260:
261: public int hashCode() {
262: return obj.hashCode();
263: }
264:
265: public boolean equals(Object obj) {
266: return 0 == compareTo(obj);
267: }
268:
269: public String toString() {
270: return obj.toString();
271: }
272: }
273:
274: class NodeIterator implements Iterator {
275: Iterator iter;
276:
277: NodeIterator(Iterator iter) {
278: this .iter = iter;
279: }
280:
281: public boolean hasNext() {
282: return iter.hasNext();
283: }
284:
285: public Object next() {
286: Node node = (Node) iter.next();
287: return node.obj;
288: }
289:
290: public void remove() {
291: }
292: }
293: }
|