/*    Copyright 2012 10gen Inc.
 *
 *    Licensed under the Apache License, Version 2.0 (the "License");
 *    you may not use this file except in compliance with the License.
 *    You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing, software
 *    distributed under the License is distributed on an "AS IS" BASIS,
 *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *    See the License for the specific language governing permissions and
 *    limitations under the License.
 */

#include "mongo/base/initializer_dependency_graph.h"

#include <algorithm>
#include <iterator>
#include <sstream>

namespace mongo {

    InitializerDependencyGraph::InitializerDependencyGraph() {}
    InitializerDependencyGraph::~InitializerDependencyGraph() {}

    Status InitializerDependencyGraph::addInitializer(const std::string& name,
                                                      const InitializerFunction& fn,
                                                      const std::vector<std::string>& prerequisites,
                                                      const std::vector<std::string>& dependents) {
        if (!fn)
            return Status(ErrorCodes::BadValue, "Illegal to supply a NULL function");

        NodeData& newNode = _nodes[name];
        if (newNode.fn) {
            return Status(ErrorCodes::DuplicateKey, name);
        }

        newNode.fn = fn;

        for (size_t i = 0; i < prerequisites.size(); ++i) {
            newNode.prerequisites.insert(prerequisites[i]);
        }

        for (size_t i = 0; i < dependents.size(); ++i) {
            _nodes[dependents[i]].prerequisites.insert(name);
        }

        return Status::OK();
    }

    InitializerFunction InitializerDependencyGraph::getInitializerFunction(
            const std::string& name) const {

        NodeMap::const_iterator iter = _nodes.find(name);
        if (iter == _nodes.end())
            return InitializerFunction();
        return iter->second.fn;
    }

    Status InitializerDependencyGraph::topSort(std::vector<std::string>* sortedNames) const {
        /*
         * This top-sort is implemented by performing a depth-first traversal of the dependency
         * graph, once for each node.  "visitedNodeNames" tracks the set of node names ever visited,
         * and it is used to prune each DFS.  A node that has been visited once on any DFS is never
         * visited again.  Complexity of this implementation is O(n+m) where "n" is the number of
         * nodes and "m" is the number of prerequisite edges.  Space complexity is O(n), in both
         * stack space and size of the "visitedNodeNames" set.
         *
         * "inProgressNodeNames" is used to detect and report cycles.
         */

        std::vector<std::string> inProgressNodeNames;
        unordered_set<std::string> visitedNodeNames;

        sortedNames->clear();
        for (NodeMap::const_iterator iter = _nodes.begin(), end = _nodes.end();
             iter != end; ++iter) {

            Status status = recursiveTopSort(_nodes,
                                             *iter,
                                             &inProgressNodeNames,
                                             &visitedNodeNames,
                                             sortedNames);
            if (Status::OK() != status)
                return status;
        }
        return Status::OK();
    }

    Status InitializerDependencyGraph::recursiveTopSort(
            const NodeMap& nodeMap,
            const Node& currentNode,
            std::vector<std::string>* inProgressNodeNames,
            unordered_set<std::string>* visitedNodeNames,
            std::vector<std::string>* sortedNames) {

        /*
         * The top sort is performed by depth-first traversal starting at each node in the
         * dependency graph, short-circuited any time a node is seen that has already been visited
         * in any traversal.  "visitedNodeNames" is the set of nodes that have been successfully
         * visited, while "inProgressNodeNames" are nodes currently in the exploration chain.  This
         * structure is kept explicitly to facilitate cycle detection.
         *
         * This function implements a depth-first traversal, and is called once for each node in the
         * graph by topSort(), above.
         */

        if ((*visitedNodeNames).count(currentNode.first))
            return Status::OK();

        if (!currentNode.second.fn)
            return Status(ErrorCodes::BadValue, currentNode.first);

        inProgressNodeNames->push_back(currentNode.first);

        std::vector<std::string>::iterator firstOccurence = std::find(
                inProgressNodeNames->begin(), inProgressNodeNames->end(), currentNode.first);
        if (firstOccurence + 1 != inProgressNodeNames->end()) {
            sortedNames->clear();
            std::copy(firstOccurence, inProgressNodeNames->end(), std::back_inserter(*sortedNames));
            std::ostringstream os;
            os << "Cycle in dependendcy graph: " << sortedNames->at(0);
            for (size_t i = 1; i < sortedNames->size(); ++i)
                os << " -> " << sortedNames->at(i);
            return Status(ErrorCodes::GraphContainsCycle, os.str());
        }

        for (unordered_set<std::string>::const_iterator
                 iter = currentNode.second.prerequisites.begin(),
                 end = currentNode.second.prerequisites.end();
             iter != end; ++iter) {

            NodeMap::const_iterator nextNode = nodeMap.find(*iter);
            if (nextNode == nodeMap.end())
                return Status(ErrorCodes::BadValue, *iter);

            Status status = recursiveTopSort(nodeMap,
                                             *nextNode,
                                             inProgressNodeNames,
                                             visitedNodeNames,
                                             sortedNames);
            if (Status::OK() != status)
                return status;
        }
        sortedNames->push_back(currentNode.first);
        if (inProgressNodeNames->back() != currentNode.first)
            return Status(ErrorCodes::InternalError, "inProgressNodeNames stack corrupt");
        inProgressNodeNames->pop_back();
        visitedNodeNames->insert(currentNode.first);
        return Status::OK();
    }

}  // namespace mongo