lojix/search/src/main/com/thesett/aima/search/impl/bidirectional/BaseBiDirectionalQueueSearch.java
private SearchNode<O, T> joinBothPaths(SearchNode<O, T> forwardPath, SearchNode<O, T> reversePath)
        throws SearchNotExhaustiveException
    {
        // Check if an alternative path join algorithm has been set and delegate to it if so
        if (pathJoiner != null)
        {
            return pathJoiner.joinBothPaths(forwardPath, reversePath);
        }

        // No alternative path join algorithm has been supplied so use this default one
        else
        {
            // Used to hold the current position along the reverse path of search nodes
            SearchNode<O, T> currentReverseNode = reversePath;

            // Used to hold the current position along the forward path of search nodes
            SearchNode<O, T> currentForwardNode = forwardPath;

            // Loop over all nodes in the reverse path checking if the current reverse node is the
            // goal state to terminate on.
            while (!goalPredicate.evaluate(currentReverseNode.getState()))
            {
                // Create a new forward node from the parent state of the current reverse node, the current reverse
                // nodes applied operation and cost, and an increment of one to the path depth
                SearchNode<O, T> reverseParentNode = currentReverseNode.getParent();
                T state = currentReverseNode.getParent().getState();
                Operator<O> operation = currentReverseNode.getAppliedOp();
                float cost = currentReverseNode.getPathCost() - reverseParentNode.getPathCost();

                currentForwardNode = currentForwardNode.makeNode(new Successor<O>(state, operation, cost));

                // Move one step up the reverse path
                currentReverseNode = reverseParentNode;
            }

            // Return the last forward search node found
            return currentForwardNode;
        }
    }
private SearchNode<O, T> joinBothPaths(SearchNode<O, T> forwardPath, SearchNode<O, T> reversePath)
        throws SearchNotExhaustiveException
    {
        // Check if an alternative path join algorithm has been set and delegate to it if so
        if (pathJoiner != null)
        {
            return pathJoiner.joinBothPaths(forwardPath, reversePath);
        }

        // No alternative path join algorithm has been supplied so use this default one
        else
        {
            // Used to hold the current position along the reverse path of search nodes
            SearchNode<O, T> currentReverseNode = reversePath;

            // Used to hold the current position along the forward path of search nodes
            SearchNode<O, T> currentForwardNode = forwardPath;

            // Loop over all nodes in the reverse path checking if the current reverse node is the
            // goal state to terminate on.
            while (!goalPredicate.evaluate(currentReverseNode.getState()))
            {
                // Create a new forward node from the parent state of the current reverse node, the current reverse
                // nodes applied operation and cost, and an increment of one to the path depth
                SearchNode<O, T> reverseParentNode = currentReverseNode.getParent();
                T state = currentReverseNode.getParent().getState();
                Operator<O> operation = currentReverseNode.getAppliedOp();
                float cost = currentReverseNode.getPathCost() - reverseParentNode.getPathCost();

                currentForwardNode = currentForwardNode.makeNode(new Successor<O>(state, operation, cost));

                // Move one step up the reverse path
                currentReverseNode = reverseParentNode;
            }

            // Return the last forward search node found
            return currentForwardNode;
        }
    }
private SearchNode < O , T > joinBothPaths ( SearchNode < O , T > forwardPath , SearchNode < O , T > reversePath ) throws SearchNotExhaustiveException { // Check if an alternative path join algorithm has been set and delegate to it if so if ( pathJoiner != null ) { return pathJoiner . joinBothPaths ( forwardPath , reversePath ) ; } // No alternative path join algorithm has been supplied so use this default one else { // Used to hold the current position along the reverse path of search nodes SearchNode < O , T > currentReverseNode = reversePath ; // Used to hold the current position along the forward path of search nodes SearchNode < O , T > currentForwardNode = forwardPath ; // Loop over all nodes in the reverse path checking if the current reverse node is the // goal state to terminate on. while ( ! goalPredicate . evaluate ( currentReverseNode . getState ( ) ) ) { // Create a new forward node from the parent state of the current reverse node, the current reverse // nodes applied operation and cost, and an increment of one to the path depth SearchNode < O , T > reverseParentNode = currentReverseNode . getParent ( ) ; T state = currentReverseNode . getParent ( ) . getState ( ) ; Operator < O > operation = currentReverseNode . getAppliedOp ( ) ; float cost = currentReverseNode . getPathCost ( ) - reverseParentNode . getPathCost ( ) ; currentForwardNode = currentForwardNode . makeNode ( new Successor < O > ( state , operation , cost ) ) ; // Move one step up the reverse path currentReverseNode = reverseParentNode ; } // Return the last forward search node found return currentForwardNode ; } }
Once a match has been found between the forward and reverse fringes of the search a path is known to exist from
the start to the goal. The path is not complete at this stage because it remains to reverse all of the steps in
the backward half of the path and add them to the forward half of the path to produce the complete forward path
from start to the goal.

<p>This method implements a standard algorithm for doing this. It assumes that the state space being searched by
both halfs of the search is over the same states. It also assumes that the applied operations in the reverse
search node have already been reverse. For example, if the search space was the eight tiles game then the moves
stored in the reverse half of the search would have to be stored in the reverse direction to that in which they
are applied when really playing the game backwards. This means that two implementations of
{@link com.thesett.aima.search.TraversableState} are needed, one that gives its operators reversed.

<p>It is possible to supply an alternative path joining algorithm that does know how to reverse the operators.
Set this in this search algorithm by calling the {@link #setPathJoinAlgorithm} method. This is an alternative to
writing two implementatios of {@link com.thesett.aima.search.TraversableState}

@param  forwardPath a search node for the forward portion of the goal path
@param  reversePath a search node for the reverse portion of the goal path

@return a search node corresponding to the path right from start to goal

@throws SearchNotExhaustiveException If the node implementation does not allow new nodes to be created from old.
See the {@link SearchNode#makeNode} method for more information.
Once a match has been found between the forward and reverse fringes of the search a path is known to exist from the start to the goal . The path is not complete at this stage because it remains to reverse all of the steps in the backward half of the path and add them to the forward half of the path to produce the complete forward path from start to the goal .