001: /*
002: *
003: * The DbUnit Database Testing Framework
004: * Copyright (C)2005, DbUnit.org
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2.1 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: *
016: * You should have received a copy of the GNU Lesser General Public
017: * License along with this library; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019: *
020: */
021:
022: package org.dbunit.util.search;
023:
024: import java.util.HashSet;
025: import java.util.Iterator;
026: import java.util.Set;
027: import java.util.SortedSet;
028:
029: import org.apache.commons.collections.set.ListOrderedSet;
030: import org.slf4j.Logger;
031: import org.slf4j.LoggerFactory;
032: import org.dbunit.util.CollectionsHelper;
033:
034: /**
035: * Search using depth-first algorithm.<br>
036: * <br>
037: * An instance of this class must be used only once, as it maintains the
038: * internal state of the search.<br>
039: * <br>
040: *
041: * @author Felipe Leme <dbunit@felipeal.net>
042: * @version $Revision: 554 $
043: * @since Aug 25, 2005
044: *
045: */
046: public class DepthFirstSearch implements ISearchAlgorithm {
047:
048: // nodes that were already scanned during the search
049: private Set scannedNodes;
050: private Set reverseScannedNodes;
051:
052: protected final Logger logger = LoggerFactory.getLogger(getClass());
053:
054: // result of the search
055: private Set result;
056:
057: // input of the search
058: private Set nodesFrom;
059:
060: // callback used to help the search
061: private ISearchCallback callback;
062:
063: // flag, as one instance cannot be used more than once
064: private boolean searching = false;
065:
066: /**
067: * Alternative option to search() that takes an array of nodes as input (instead of a Set)
068: */
069: public Set search(Object[] nodesFrom, ISearchCallback callback)
070: throws SearchException {
071: logger.debug("search(nodesFrom=" + nodesFrom + ", callback="
072: + callback + ") - start");
073:
074: return search(CollectionsHelper.objectsToSet(nodesFrom),
075: callback);
076: }
077:
078: /**
079: * @see ISearchAlgorithm
080: */
081: public Set search(Set nodesFrom, ISearchCallback callback)
082: throws SearchException {
083: logger.debug("search(nodesFrom=" + nodesFrom + ", callback="
084: + callback + ") - start");
085:
086: synchronized (this ) {
087: if (searching) {
088: throw new IllegalStateException(
089: "already searching/searched");
090: }
091: this .searching = true;
092: }
093:
094: // set of tables that will be returned (i.e, the declared tables and its
095: // depedencies)
096: this .result = new ListOrderedSet();
097:
098: // callback used to help the search
099: this .callback = callback;
100:
101: this .nodesFrom = new ListOrderedSet();
102:
103: int sizeNodesFromBefore = 0;
104: int sizeResultBefore = 0;
105: boolean keepSearching = true;
106: this .scannedNodes = new HashSet();
107: this .reverseScannedNodes = new HashSet();
108: this .scannedNodes = new HashSet();
109: do {
110:
111: // In a traditional depth-first search, the getEdges() method should return only
112: // edges where this node is the 'from' vertex, as the graph is known in advance.
113: // But in our case, the graph is built 'on the fly', so it's possible that the
114: // getEdges() also returns edges where the node is the 'to' vertex.
115: // So, before we do the "real" search, we need to do a reverse search to find out
116: // all the nodes that should be part of the input.
117: Iterator iterator = nodesFrom.iterator();
118: while (iterator.hasNext()) {
119: Object node = iterator.next();
120: reverseSearch(node);
121: }
122:
123: // now that the input is adjusted, do the search
124: iterator = this .nodesFrom.iterator();
125:
126: while (iterator.hasNext()) {
127: Object node = iterator.next();
128: search(node);
129: }
130:
131: nodesFrom = new HashSet(this .result);
132:
133: // decides if we continue searching
134: boolean sizesDontMatch = this .result.size() != this .nodesFrom
135: .size();
136: boolean resultChanged = this .result.size() != sizeResultBefore;
137: boolean nodesFromChanged = this .nodesFrom.size() != sizeNodesFromBefore;
138: sizeNodesFromBefore = this .nodesFrom.size();
139: sizeResultBefore = this .result.size();
140: keepSearching = sizesDontMatch
141: && (resultChanged || nodesFromChanged);
142:
143: } while (keepSearching);
144:
145: return this .result;
146:
147: }
148:
149: /**
150: * This is the real depth first search algorithm, which is called recursively.
151: *
152: * @param node node where the search starts
153: * @return true if the node has been already searched before
154: * @throws Exception if an exception occurs while getting the edges
155: */
156: private boolean search(Object node) throws SearchException {
157: if (this .logger.isDebugEnabled()) {
158: this .logger.debug("search:" + node);
159: }
160: if (this .scannedNodes.contains(node)) {
161: if (this .logger.isDebugEnabled()) {
162: this .logger.debug("already searched; returning true");
163: }
164: return true;
165: }
166: if (!this .callback.searchNode(node)) {
167: if (this .logger.isDebugEnabled()) {
168: this .logger
169: .debug("Callback handler blocked search for node "
170: + node);
171: }
172: return true;
173: }
174:
175: if (this .logger.isDebugEnabled()) {
176: this .logger.debug("Pushing " + node);
177: }
178: this .scannedNodes.add(node);
179:
180: // first, search the nodes the node depends on
181: SortedSet edges = this .callback.getEdges(node);
182: if (edges != null) {
183: Iterator iterator = edges.iterator();
184: while (iterator.hasNext()) {
185: // and recursively search these nodes
186: IEdge edge = (IEdge) iterator.next();
187: Object toNode = edge.getTo();
188: search(toNode);
189: }
190: }
191:
192: // finally, add the node to the result
193: if (this .logger.isDebugEnabled()) {
194: this .logger.debug("Adding node " + node
195: + " to the final result");
196: }
197: // notify the callback a node was added
198: this .callback.nodeAdded(node);
199: result.add(node);
200:
201: return false;
202: }
203:
204: /**
205: * Do a reverse search (i.e, searching the other way of the edges) in order
206: * to adjust the input before the real search.
207: * @param node node where the search starts
208: * @return true if the node has been already reverse-searched before
209: * @throws Exception if an exception occurs while getting the edges
210: */
211: private boolean reverseSearch(Object node) throws SearchException {
212: if (this .logger.isDebugEnabled()) {
213: this .logger.debug("reverseSearch:" + node);
214: }
215: if (this .reverseScannedNodes.contains(node)) {
216: if (this .logger.isDebugEnabled()) {
217: this .logger.debug("already searched; returning true");
218: }
219: return true;
220: }
221:
222: if (!this .callback.searchNode(node)) {
223: if (this .logger.isDebugEnabled()) {
224: this .logger
225: .debug("callback handler blocked reverse search for node "
226: + node);
227: }
228: return true;
229: }
230:
231: if (this .logger.isDebugEnabled()) {
232: this .logger.debug("Pushing (reverse) " + node);
233: }
234: this .reverseScannedNodes.add(node);
235:
236: // first, search the nodes the node depends on
237: SortedSet edges = this .callback.getEdges(node);
238: if (edges != null) {
239: Iterator iterator = edges.iterator();
240: while (iterator.hasNext()) {
241: // and recursively search these nodes if we find a match
242: IEdge edge = (IEdge) iterator.next();
243: Object toNode = edge.getTo();
244: if (toNode.equals(node)) {
245: Object fromNode = edge.getFrom();
246: reverseSearch(fromNode);
247: }
248: }
249: }
250:
251: // finally, add the node to the input
252: this .nodesFrom.add(node);
253:
254: return false;
255:
256: }
257:
258: }
|