// -------------------------------------------------------------------------
// bfs.h
// Version: 1.0
// Date: 2003/04/14
// Purpose: Provide template for Breadth First Search algorithm
// Note: Self contained, does not depend on STL, or any other library code
// (c) T.Frogley 2003
// -------------------------------------------------------------------------

#ifndef TFROGLEY_BFS_H_2003
#define TFROGLEY_BFS_H_2003

namespace bfs {

    // helper type(s), do not overload, specialise etc
    namespace helper{
        template<typename T>
        struct node_link {
            node_link( const T& node, node_link<T>* parent=0 )
                : m_node(node)
                , m_parent(parent)
                , m_next(0)
                , m_last(0)
            { }
            node_link<T>* m_next;
            node_link<T>* m_last;
            node_link<T>* const m_parent;
            T m_node;
        };
    }

    //  function template, bfs
    //  Does a Breadth First Search from 'a' until it finds 'b'
    //  If a path/route is found, returns true and 
    //    Outputs into 'results' full path, including end nodes
    //  Else, returns false.

    // NodeType requirements: 
    // * NodeType must appear to be a Container of NodeTypes, that is:
    // -> Must have a "iterator" type, and have begin() and end() 
    // -> Assignable (Copy Constructible)
    // * Comparison operators: == and !=
    
    template<typename NodeType, typename OutputIterator>
    bool bfs(const NodeType a, const NodeType b, OutputIterator results)
    {
        bool found_route = false;
        typedef bfs::helper::node_link<NodeType> node;
        typedef typename NodeType::iterator NodeItr;
        node * head = new node(a);
        node * tail = head;
        node * current = head;

        while(current && current->m_node != b){

            //add child nodes to graph
            const NodeItr end = current->m_node.end();
            for(NodeItr i = current->m_node.begin();i!=end;++i){

                //check for circular paths
                node * search_back = tail;
                do{
                    if (search_back->m_node == *i){
                        //already visited this node
                        break;
                    }
                    //search_back = search_back->m_parent;
                    search_back = search_back->m_last;
                }while(search_back);
		
                if (!search_back){
                    tail->m_next = new node(*i,current);
                    tail->m_next->m_last = tail;
                    tail = tail->m_next;
                }
            }

            //move to next node
            current = current->m_next;
        }

        //found a route!
        if (current){
            found_route = true;
            //work back up route
            do{
                //results.push_front( current->m_node );
                *results++ = current->m_node;
                current = current->m_parent;
            }while(current);
        }

        //clean up memory
        do{
            current = head->m_next;
            delete head;
            head = current;
        }while(head);

        return found_route;
    }
}

#endif