/*
 * Name   : graph.cpp
 * Purpose: Find the shortest distance between 2 vertices in a graph
 *          by using graph breadth-first traversal
 *          This program has been developped as an assignment during a remote interview process
 *          with facebook.
 *
 * Known limitation: Another approach would be required on a weighted graph
 *                   such computing the minimum span tree of the graph.
 *
 * To know more about the graph breadth-first traversal algorithm,
 * I recommend Robert Sedgewick excellent book on algorithms
 *
 * Author : Olivier Langlois <olivier@olivierlanglois.net>
 *
 * Date: October 05, 2009
 */

#include <ctype.h>    // For isalpha(), islower()
#include <set>
#include <deque>
#include <bitset>
#include <vector>
#include <iostream>
#include <sstream>    // For std::ostringstream
#include <iterator>   // For std::ostream_iterator and std::iterator
#include <algorithm>  // For std::copy(), count_if() and for_each()
#include <stdexcept>  // For std::runtime_error
#include <functional> // For std::binary_function, bind2nd and not_equal_to

namespace {

const unsigned MAXNODES = 52;

// forward declaration
class Node;

/*
 * Predicate to sort Node pointers by ascending order of their ids.
 */
class NodePtrPred : public std::binary_function<Node*,Node*,bool>
{
    public:
    bool operator()( const Node *a, const Node *b ) const;
};

/*
 * class Node
 *
 * Purpose: Contains a reference to all neighbors nodes.
 *          Note that if the graph is undirected, all neighbors will
 *          also point to this Node.
 */
class Node
{
  public:
  typedef std::set<Node *,NodePtrPred> NeighborsCont_t;

  Node(unsigned id);

  static unsigned index( char a );
  static char     name( unsigned idx );

  // getters
  unsigned getId()   const { return m_id; }
  char     getName() const { return name(getId()); }
  const NeighborsCont_t &getNeighbors() const { return m_neighbors; }

  bool operator<( const Node &a ) const { return getId()<a.getId(); }
  friend std::ostream &operator<<( std::ostream &o, const Node &n );

  void AddNeighbor( Node *n );

  private:
  unsigned            m_id; // Unique node id.
  NeighborsCont_t m_neighbors;
};

/*
 * Predicate that sorts Node pointers based on the class operator<
 */
bool NodePtrPred::operator()( const Node *a, const Node *b ) const
{
    return *a<*b;
}

Node::Node(unsigned id)
: m_id(id)
{
}

inline void Node::AddNeighbor( Node *n )
{
    /*
     * Insertion will silently fail if n is already in the set.
     */
    m_neighbors.insert(n);
}


/*
 * Convert a letter to the corresponding Node index.
 */
unsigned Node::index( char a )
{
    if( !isalpha(a) )
    {
        throw std::runtime_error("Vertex name is limited to alpha chars for now");
    }
    if( islower(a) )
    {
        return a-'a';
    }
    else // isupper(a)
    {
        return 26+a-'A';
    }
}

/*
 * Convert a node index back to its name.
 */
char Node::name( unsigned idx )
{
    if( idx >= MAXNODES )
    {
        throw std::runtime_error("Vertex index is limited to MAXNODES");
    }
    if( idx < 26 )
    {
        return 'a'+idx;
    }
    else
    {
        return idx-26+'A';
    }
}

/*
 * Output iterator adapter
 *
 * Purpose: Allows to traverse a container of pointers and dereference each of them
 *          when they are assigned to the output iterator.
 */
template<class iterator_t>
class Deref_output_iterator_adapter : public std::iterator<std::output_iterator_tag,void,void,void,void>
{
    public:
    explicit Deref_output_iterator_adapter(iterator_t &x) : m_iterator(x) {}

    template<class T>
    Deref_output_iterator_adapter &operator=( const T *x )
    {
        *m_iterator = *x; return *this;
    }
    Deref_output_iterator_adapter &operator*()     { return *this; }
    Deref_output_iterator_adapter &operator++()    { ++m_iterator; return *this; }
    Deref_output_iterator_adapter &operator++(int) { m_iterator++; return *this; }
    private:
    iterator_t &m_iterator;
};

/*
 * operator= specialization for Node
 *
 * Note: The Deref_output_iterator_adapter is finally not that generic!
 */
typedef std::ostream_iterator<char> output_iterator_t;

template<>
  template<>
Deref_output_iterator_adapter<output_iterator_t> &
Deref_output_iterator_adapter<output_iterator_t>::operator=( const Node *x )
{
    *m_iterator = x->getName(); return *this;
}

/*
 * output stream operator for the class Node.
 */
std::ostream &operator<<( std::ostream &o, const Node &n )
{
    o << "Node " << n.getName() << " has " << n.m_neighbors.size()
      << " neighbors : ";
    output_iterator_t out_it(o," ");
    std::copy(n.m_neighbors.begin(),n.m_neighbors.end(),
              Deref_output_iterator_adapter<output_iterator_t>(out_it));
    return o;
}

/*
 * class NodeContainer
 *
 * This is the class representing the graph.
 */
class NodeContainer
{
    public:
    NodeContainer();
    ~NodeContainer();

    void AddEdge( char a, char b, bool bUndirected = true );

    /*
     * Input param:
     *              a (char) Node name. (Valid range is a-z & A-Z).
     *              idx (unsigned) Node index.
     * Return value: A pointer on the requested node or NULL if not found.
     *
     * Note: Can throw a std::out_of_range exception if passed an invalid param
     *       such as an idx greater than MAXNODES.
     *       Can throw a std::runtime_error if the 'a' param is an invalid node name.
     */
    Node *FindNode( char a )       { return FindNode(Node::index(a)); }
    Node *FindNode( unsigned idx ) { return m_Nodes.at(idx); }

    const Node *FindNode( char a ) const       { return FindNode(Node::index(a)); }
    const Node *FindNode( unsigned idx ) const { return m_Nodes.at(idx); }

    /*
     * Purpose: Find the shortest distance from node a to node b by using the
     *          graph breadth-first traversal algorithm.
     *
     * Return value: Number of hops between nodes or NOT_CONNECTED
     */
    static const unsigned NOT_CONNECTED = static_cast<unsigned>(-1); // Will become the biggest unsigned value
    unsigned distance( char a, char b ) const;

    friend std::ostream &operator<<( std::ostream &o, const NodeContainer &c );

    private:
    /*
     * Purpose: Check the existence of the node at index idx of m_Nodes vector
     *          and create a Node if not present.
     *
     * Return value: Node at idx.
     *
     * Note: Can throw a std::out_of_range exception if idx is invalid.
     */
    Node *CreateNode( unsigned idx );
    std::vector<Node*> m_Nodes;
};

NodeContainer::NodeContainer()
: m_Nodes(MAXNODES)
{
}

NodeContainer::~NodeContainer()
{
    for( unsigned i = 0; i < m_Nodes.size(); ++i )
    {
        /*
         * No need to check for NULL as it is harmless to delete NULL.
         */
        delete m_Nodes[i];
    }
}

/*
 * CreateNode()
 *
 * Purpose: Private method to create a node at index idx only if it does not exists yet.
 */
Node *NodeContainer::CreateNode( unsigned idx )
{
    if( !m_Nodes.at(idx) )
    {
        m_Nodes[idx] = new Node(idx);
    }
    return m_Nodes[idx];
}

/*
 * AddEdge()
 *
 * Purpose: Add an edge between node a and node b. Make the edge
 *          bidirectional if bUndirected true
 */
void NodeContainer::AddEdge( char a, char b, bool bUndirected )
{
    unsigned aIdx = Node::index(a);
    unsigned bIdx = Node::index(b);

    Node *nodeA = CreateNode(aIdx);
    Node *nodeB = CreateNode(bIdx);

    nodeA->AddNeighbor(nodeB);
    if( bUndirected )
    {
        nodeB->AddNeighbor(nodeA);
    }
}

/*
 * distance()
 *
 * Purpose: Find the shortest distance from node a to node b by using the
 *          graph breadth-first traversal algorithm.
 *
 * Return value: Number of hops between nodes or NOT_CONNECTED
 *
 * To know more about the graph breadth-first traversal algorithm,
 * I recommend Robert Sedgewick excellent book on algorithms
 */
unsigned NodeContainer::distance( char a, char b ) const
{
    // Input validation
    const Node *nodeA = FindNode(a);
    const Node *nodeB = FindNode(b);

    if( !nodeA || !nodeB )
    {
        return NOT_CONNECTED;
    }
    else if( a == b )
    {
        return 0;
    }

    // Store nodes reachable in the next hop
    std::deque<const Node*> lQueue;

    // Keep track of visited nodes to avoid graph cycles.
    std::bitset<MAXNODES> lVisitedNodes;

    // Initialize working vars
    lVisitedNodes.set(nodeA->getId());
    lQueue.push_front(nodeA);
    unsigned numHop = 1;

    // Main loop
    while( !lQueue.empty() )
    {
        unsigned curIterNodeNum = lQueue.size();
        for( unsigned i = 0; i < curIterNodeNum; ++i )
        {
            const Node *curNode = lQueue.back();
            lQueue.pop_back();

            Node::NeighborsCont_t::const_iterator first = curNode->getNeighbors().begin();
            Node::NeighborsCont_t::const_iterator last  = curNode->getNeighbors().end();

            while( first != last )
            {
                unsigned curNodeId = (*first)->getId();
                if( curNodeId == nodeB->getId() )
                {
                    return numHop;
                }
                else if( !lVisitedNodes[curNodeId] )
                {
                    lVisitedNodes.set(curNodeId);
                    lQueue.push_front(*first);
                }
                ++first;
            }
        }
        ++numHop;
    }

    // The graph have been fully analyzed without find any path between a and b.
    return NOT_CONNECTED;
}

/*
 * class NodeCondOutputAndCount
 *
 * Auxiliary functor applied to all nodes inside NodeContainer stream output operator<<
 */
class NodeCondOutputAndCount
{
    public:
    NodeCondOutputAndCount( std::ostream &o )
    : m_nodeNum(0), m_rO(o) {}

    // getters
    unsigned getNodeNum() const { return m_nodeNum; }

    void operator()( Node *a )
    {
        if(a)
        {
            m_rO << *a << '\n';
            ++m_nodeNum;
        }
    }

    private:
    unsigned m_nodeNum;
    std::ostream &m_rO;
};

std::ostream &operator<<( std::ostream &o, const NodeContainer &c )
{
    /*
     * If execution time was an issue, a counter could be added to NodeContainer class
     * and would be incremented in method CreateNode().
     *
     * Note: I had to get rid of my cleverly crafted STL statement as I have realized that both
     *       tasks could be performed in 1 iteration. The tradeoff is some memory to store the nodes
     *       output in a temporary string.
     */
/*
    unsigned nodeNum = std::count_if(c.m_Nodes.begin(),c.m_Nodes.end(),
                                     std::bind2nd(std::not_equal_to<Node*>(),static_cast<Node*>(NULL)));
 */
    std::ostringstream ost;
    o << "The graph has " << std::for_each(c.m_Nodes.begin(),c.m_Nodes.end(),
                                           NodeCondOutputAndCount(ost)).getNodeNum()
      << " vertices\n";
    o << ost.str();
    return o;
}

/*
 * Sample graph definition consisting of an enumeration of edges connecting the graph nodes.
 */
const char * const SampleGraphEdges[] = {
    "ab", "ac", "ad",
    "bf", "ba", "bc",
    "cb", "cd", "ce", "ca",
    "da", "dc", "do",
    "ef", "em", "ec",
    "fe", "fg", "fb",
    "gh", "gk", "gf",
    "hj", "hi", "hg",
    "il", "ij", "ih",
    "ji", "jh", "jk", "jl",
    "kj", "kg", "kn",
    "lj", "li", "lA",
    "mn", "me", "mp",
    "nm", "nk", "nB",
    "op", "od", "or",
    "po", "pq", "pm",
    "qp", "qC", "qs",
    "ru", "ro", "rs", "rt",
    "sq", "sx", "sr",
    "tr", "tu", "tv",
    "ut", "ur", "uw",
    "vt", "vx", "vw",
    "wu", "wv", "wy",
    "xs", "xv", "xz",
    "yw", "yH", "yF",
    "zx", "zD", "zF",
    "Al", "AB", "AE",
    "Bn", "BA", "BC",
    "CB", "Cq", "CD",
    "DC", "Dz", "DE",
    "EA", "ED", "EG", "EH",
    "Fz", "Fy", "FG",
    "GF", "GE", "GH",
    "Hy", "HG", "HE"
};

/*
 * fillGraph
 */
void fillGraph( NodeContainer &c )
{
    /*
     * You could do loop unrolling here if performance was an issue.
     */
    for( unsigned i = 0; i < sizeof(SampleGraphEdges)/sizeof(const char * const); ++i )
    {
        c.AddEdge(SampleGraphEdges[i][0],SampleGraphEdges[i][1]);
    }
}

/*
 * printDistance
 */
void printDistance( NodeContainer &c, char a, char b, std::ostream &o )
{
    unsigned res = NodeContainer::NOT_CONNECTED;
    try
    {
        res = c.distance(a,b);
    }
    catch( std::exception &e )
    {
        std::cerr << "Exception caught while calling NodeContainer::distance() : " << e.what() << std::endl;
    }
    o << "The distance between " << a << " and " << b << " is : ";
    if( res != NodeContainer::NOT_CONNECTED )
    {
        o << res;
    }
    else
    {
        o << "NOT CONNECTED";
    }
    o << '\n';
}

}

int main( int argc, char *argv[] )
{
    try
    {
        NodeContainer SimpleGraph;
        fillGraph(SimpleGraph);
        std::cout << SimpleGraph << std::endl;
        printDistance(SimpleGraph,'a','a',std::cout);
        printDistance(SimpleGraph,'a','b',std::cout);
        printDistance(SimpleGraph,'c','C',std::cout);
        printDistance(SimpleGraph,'a','H',std::cout);
        printDistance(SimpleGraph,'a','Z',std::cout);
    }
    catch( std::exception &e )
    {
        std::cerr << "Exception caught : " << e.what() << std::endl;
    }
    return 0;
}