# Copyright 2019 Nokia

# 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.
from __future__ import print_function
from cmframework.apis import cmerror


class TopSort(object):
    """
    This class implements a topological sort algorithm.

    It expects a dependency graph as an input and returns a sorted list as an
    output. The returned list contains lists sorted accordingly to the dependency
    graph:

    Usage Example:
        # The following graph indicates that 2 depends on 11, 9 depends on 11,8,10 and so on...
        graph = {2: [11],
                 9: [11, 8, 10],
                10: [11, 3],
                11: [7, 5],
                8: [7, 3]}

        sort = TopSort(graph)
        try:
            sorted = sort.sort()
            for entry in sorted:
                print('%r' % entry)
        except cmerror.CMError as exp:
           print('Got exception %s' % str(exp))

    The above example will generate the following output:
    [3, 5, 7]
    [8, 11]
    [2, 10]
    [9]
    """

    def __init__(self, graph):
        self.graph = graph
        self.output = {}
        self.recursionlevel = 0

    def _get_dependent_entries(self, entry):
        result = []
        for e, deps in self.graph.iteritems():
            if entry in deps:
                result.append(e)
        return result

    def _update_dependent_entries(self, entry):
        maximumrecursion = (len(self.graph)) * (len(self.graph))
        if (self.recursionlevel + 1) >= maximumrecursion:
            raise cmerror.CMError('cyclic dependency detected, graph %r' % self.graph)
        self.recursionlevel += 1
        dependententries = self._get_dependent_entries(entry)
        entrydepth = self.output[entry]
        for e in dependententries:
            if e in self.output:
                if entrydepth >= self.output[e]:
                    self.output[e] = entrydepth + 1
                    self._update_dependent_entries(e)

    def sort(self):
        for entry, deps in self.graph.iteritems():
            depth = 0
            if entry in self.output:
                depth = self.output[entry]

            # calculate new depth according to dependencies
            newdepth = depth
            for dep in deps:
                if dep in self.output:
                    weight = self.output[dep]
                else:
                    weight = 0
                    self.output[dep] = 0
                if weight >= newdepth:
                    newdepth = weight + 1

            # if our depth is changed we need to update the entries depending on us
            self.output[entry] = newdepth
            if newdepth > depth and entry in self.output:
                self.recursionlevel = 0
                self._update_dependent_entries(entry)

        return self._getsorted()

    def _getsorted(self):
        import operator
        sortedoutput = sorted(self.output.items(), key=operator.itemgetter(1))
        result = {}
        for entry in sortedoutput:
            if entry[1] not in result:
                result[entry[1]] = []
            result[entry[1]].append(entry[0])

        returned = []
        for entry, data in result.iteritems():
            returned.append(data)

        return returned


def main():
    graph1 = {2: [11],
              9: [11, 8, 10],
              10: [11, 3],
              11: [7, 5],
              8: [7, 3]}

    graph2 = {'playbook2.yaml': [], 'playbook1.yaml': ['playbook2.yaml']}

    topsort1 = TopSort(graph1)
    topsort2 = TopSort(graph2)

    try:
        print(graph1)
        sortedlists1 = topsort1.sort()
        for entry in sortedlists1:
            print('%r' % entry)

        print(graph2)
        sortedlists2 = topsort2.sort()
        for entry in sortedlists2:
            print('%r' % entry)
    except cmerror.CMError as exp:
        print(str(exp))


if __name__ == '__main__':
    main()