001: /*
002: * (c) Copyright 2007 by Volker Bergmann. All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, is permitted under the terms of the
006: * GNU General Public License.
007: *
008: * For redistributing this software or a derivative work under a license other
009: * than the GPL-compatible Free Software License as defined by the Free
010: * Software Foundation or approved by OSI, you must first obtain a commercial
011: * license to this software product from Volker Bergmann.
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
014: * WITHOUT A WARRANTY OF ANY KIND. ALL EXPRESS OR IMPLIED CONDITIONS,
015: * REPRESENTATIONS AND WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF
016: * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE
017: * HEREBY EXCLUDED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
018: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
019: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
020: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
021: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
022: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
023: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
024: * POSSIBILITY OF SUCH DAMAGE.
025: */
026:
027: package org.databene.model.depend;
028:
029: import java.util.ArrayList;
030: import java.util.HashMap;
031: import java.util.Iterator;
032: import java.util.List;
033: import java.util.Map;
034:
035: import org.apache.commons.logging.Log;
036: import org.apache.commons.logging.LogFactory;
037:
038: import static org.databene.model.depend.NodeState.*;
039:
040: /**
041: * Orders objects by dependency.
042: * @author Volker Bergmann
043: * @since 0.3.04
044: * @param <E>
045: */
046: public class DependencyModel<E extends Dependent<E>> {
047:
048: private static final Log logger = LogFactory
049: .getLog(DependencyModel.class);
050:
051: private Map<E, Node<E>> nodeMappings;
052:
053: public DependencyModel() {
054: this .nodeMappings = new HashMap<E, Node<E>>();
055: }
056:
057: public void addNode(E object) {
058: nodeMappings.put(object, new Node<E>(object));
059: }
060:
061: public List<E> dependencyOrderedObjects(boolean acceptingCycles) {
062: // set up dependencies
063: for (Node<E> node : nodeMappings.values()) {
064: E subject = node.getSubject();
065: for (int i = 0; i < subject.countProviders(); i++) {
066: E provider = subject.getProvider(i);
067: Node<E> providerNode = nodeMappings.get(provider);
068: if (providerNode == null)
069: throw new IllegalStateException(
070: "Node is not part of model: " + provider);
071: providerNode.addClient(node);
072: node.addProvider(providerNode, subject
073: .requiresProvider(i));
074: }
075: }
076:
077: // set up lists for processing
078: List<Node<E>> heads = new ArrayList<Node<E>>();
079: List<Node<E>> tails = new ArrayList<Node<E>>();
080: List<Node<E>> tmp = new ArrayList<Node<E>>(nodeMappings.size());
081: List<Node<E>> orderedNodes = new ArrayList<Node<E>>(
082: nodeMappings.size());
083: List<Node<E>> incompletes = new ArrayList<Node<E>>();
084:
085: try {
086: // determine types and extract islands
087: Iterator<Node<E>> iterator = nodeMappings.values()
088: .iterator();
089: while (iterator.hasNext()) {
090: Node<E> node = iterator.next();
091: if (node.hasClients()) {
092: if (node.hasProviders()) {
093: tmp.add(node);
094: } else {
095: node.initialize();
096: heads.add(node);
097: }
098: } else {
099: if (node.hasProviders()) {
100: tails.add(node);
101: } else {
102: node.initialize();
103: orderedNodes.add(node);
104: }
105: }
106: }
107:
108: // extract heads
109: orderedNodes.addAll(heads);
110:
111: // sort remaining nodes
112: while (tmp.size() > 0) {
113: boolean found = extractNodes(tmp, INITIALIZABLE,
114: orderedNodes, null);
115: if (!found)
116: found = extractNodes(tmp, PARTIALLY_INITIALIZABLE,
117: orderedNodes, incompletes);
118: if (!found) {
119: if (acceptingCycles) {
120: // force one node
121: Node<E> node = findForceable(tmp);
122: logger.debug("forcing " + node);
123: tmp.remove(node);
124: node.force();
125: orderedNodes.add(node);
126: incompletes.add(node);
127: } else
128: throw new CyclicDependencyException(
129: "Cyclic dependency in " + tmp);
130: }
131: postProcessNodes(incompletes);
132: }
133:
134: if (incompletes.size() > 0)
135: throw new IllegalStateException(
136: "Incomplete nodes left: " + incompletes);
137:
138: // extract tails
139: for (Node<E> tail : tails)
140: tail.initialize();
141: orderedNodes.addAll(tails);
142:
143: // done
144: if (logger.isDebugEnabled())
145: logger.debug("ordered to " + orderedNodes);
146:
147: // map result
148: List<E> result = new ArrayList<E>(orderedNodes.size());
149: for (Node<E> node : orderedNodes) {
150: E subject = node.getSubject();
151: if (node.getState() != INITIALIZED)
152: throw new IllegalStateException(
153: "Node '"
154: + subject
155: + "' is expected to be in INITIALIZED state, found: "
156: + node.getState());
157: result.add(subject);
158: }
159: return result;
160: } catch (RuntimeException e) {
161: if (!(e instanceof CyclicDependencyException))
162: logState(tmp);
163: throw e;
164: }
165: }
166:
167: private void postProcessNodes(List<Node<E>> nodes) {
168: Iterator<Node<E>> iterator = nodes.iterator();
169: while (iterator.hasNext()) {
170: Node<E> node = iterator.next();
171: switch (node.getState()) {
172: case PARTIALLY_INITIALIZABLE:
173: node.initializePartially();
174: break;
175: case INITIALIZED:
176: node.initializePartially();
177: break;
178: case INITIALIZABLE:
179: node.initialize();
180: iterator.remove();
181: break;
182: }
183: }
184: }
185:
186: private boolean extractNodes(List<Node<E>> source,
187: NodeState requiredState, List<Node<E>> target,
188: List<Node<E>> incompletes) {
189: Iterator<Node<E>> iterator;
190: boolean found = false;
191: iterator = source.iterator();
192: while (iterator.hasNext()) {
193: Node<E> node = iterator.next();
194: if (node.getState() == requiredState) {
195: iterator.remove();
196: switch (requiredState) {
197: case INITIALIZABLE:
198: node.initialize();
199: break;
200: case PARTIALLY_INITIALIZABLE:
201: node.initializePartially();
202: if (incompletes != null)
203: incompletes.add(node);
204: break;
205: default:
206: throw new IllegalArgumentException(
207: "state not supported: " + requiredState);
208: }
209: if (target != null)
210: target.add(node);
211: found = true;
212: }
213: }
214: return found;
215: }
216:
217: private void logState(List<Node<E>> intermediates) {
218: logger
219: .error(intermediates.size()
220: + " unresolved intermediates on DependencyModel error: ");
221: for (Node<E> node : intermediates)
222: logger.error(node);
223: }
224:
225: private Node<E> findForceable(List<Node<E>> candidates) {
226: for (Node<E> candidate : candidates)
227: if (candidate.getState() == FORCEABLE)
228: return candidate;
229: return candidates.get(0);
230: }
231:
232: /*
233: private Node<E> breakCycle(List<Node<E>> remainingNodes, List<Node<E>> availableNodes, boolean hard) {
234: for (Node<E> node : remainingNodes) {
235: if (available(node))
236: logger.warn("Cyclic dependency in " + tmpList + ". Breaking cycle by extracting " + node);
237: result.add(node);
238: tmpList.remove(0);
239: }
240: }
241:
242: private Node<E> findAvailableNode(List<Node<E>> tmpList, List<Node<E>> availableNodes) {
243: for (Node<E> node : tmpList)
244: if (available(node, availableNodes))
245: return node;
246: return null;
247: }
248:
249: private boolean available(Node<E> candidate, List<Node<E>> availableNodes) {
250: for (Node<E> usedNode : candidate.getProviders())
251: if (!availableNodes.contains(usedNode))
252: return false;
253: return true;
254: }
255: */
256: }
|