001: // Copyright 2006 The Apache Software Foundation
002: //
003: // Licensed under the Apache License, Version 2.0 (the "License");
004: // you may not use this file except in compliance with the License.
005: // You may obtain a copy of the License at
006: //
007: // http://www.apache.org/licenses/LICENSE-2.0
008: //
009: // Unless required by applicable law or agreed to in writing, software
010: // distributed under the License is distributed on an "AS IS" BASIS,
011: // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
012: // See the License for the specific language governing permissions and
013: // limitations under the License.
014:
015: /**
016: *
017: */package org.apache.tapestry.ioc.internal.util;
018:
019: import static org.apache.tapestry.ioc.internal.util.CollectionFactory.newList;
020:
021: import java.util.List;
022:
023: import org.apache.commons.logging.Log;
024: import org.apache.tapestry.ioc.Orderable;
025:
026: /**
027: * Used by {@link org.apache.tapestry.ioc.internal.util.Orderer} to establish backward dependencies for
028: * {@link org.apache.tapestry.ioc.Orderable} objects.
029: *
030: * @param <T>
031: */
032:
033: class DependencyNode<T> {
034: private final Log _log;
035:
036: private final Orderable<T> _orderable;
037:
038: private final List<DependencyNode<T>> _dependencies = newList();
039:
040: DependencyNode(Log errorLog, Orderable<T> orderable) {
041: _log = errorLog;
042: _orderable = orderable;
043: }
044:
045: @Override
046: public String toString() {
047: StringBuilder buffer = new StringBuilder(String.format("[%s",
048: getId()));
049:
050: boolean first = true;
051:
052: for (DependencyNode<T> node : _dependencies) {
053:
054: buffer.append(first ? ": " : ", ");
055:
056: buffer.append(node.toString());
057:
058: first = false;
059: }
060:
061: buffer.append("]");
062:
063: return buffer.toString();
064: }
065:
066: /**
067: * Returns the underlying {@link Orderable}'s id.
068: */
069: public String getId() {
070: return _orderable.getId();
071: }
072:
073: void addDependency(DependencyNode<T> node) {
074: if (node.isReachable(this )) {
075: String message = UtilMessages.dependencyCycle(node, this );
076: _log.warn(message, null);
077: return;
078: }
079:
080: // Make this node depend on the other node.
081: // That forces the other node's orderable
082: // to appear before this node's orderable.
083:
084: _dependencies.add(node);
085: }
086:
087: boolean isReachable(DependencyNode<T> node) {
088: if (this == node)
089: return true;
090:
091: // Quick fast pass for immediate dependencies
092:
093: for (DependencyNode<T> d : _dependencies) {
094: if (d == node)
095: return true;
096: }
097:
098: // Slower second pass looks for
099: // indirect dependencies
100:
101: for (DependencyNode<T> d : _dependencies) {
102: if (d.isReachable(node))
103: return true;
104: }
105:
106: return false;
107: }
108:
109: /**
110: * Returns the {@link Orderable} objects for this node ordered based on dependencies.
111: */
112: List<Orderable<T>> getOrdered() {
113: List<Orderable<T>> result = newList();
114:
115: fillOrder(result);
116:
117: return result;
118: }
119:
120: private void fillOrder(List<Orderable<T>> list) {
121: if (list.contains(_orderable))
122: return;
123:
124: // Recusively add dependencies
125:
126: for (DependencyNode<T> node : _dependencies) {
127: node.fillOrder(list);
128: }
129:
130: list.add(_orderable);
131: }
132:
133: }
|