import copy
from Logger import Logger
from constants import constants
from SpecData import SPECS

def removeDuplicateEntriesInList(myList):
    myListCopy = []
    for p in myList:
        if p not in myListCopy:
            myListCopy.append(p)
    return myListCopy

class PackageBuildDataGenerator(object):

    cycleCount = 0

    def __init__(self, logName=None, logPath=None):
        if logName is None:
            logName = "PackageBuildDataGenerator"
        if logPath is None:
            logPath = constants.logPath
        self.logName = logName
        self.logPath = logPath
        self.logger = Logger.getLogger(logName, logPath)
        self.__mapCyclesToPackageList = {}
        self.__mapPackageToCycle = {}
        self.__buildDependencyGraph = {}
        self.__runTimeDependencyGraph = {}
        self.__sortedPackageList = []
        self.__sortedBuildDependencyGraph = {}

    def getPackageBuildData(self, listPackages):
        self.__readDependencyGraphAndCyclesForGivenPackages(listPackages)
        self.__getSortedBuildOrderListForGivenPackages(listPackages)
        return self.__mapCyclesToPackageList, self.__mapPackageToCycle, self.__sortedPackageList

    #todo
    def findCompleteListOfPackagesRequiredToBuildGivenPackages(self, listPackages):
        return list(self.__buildDependencyGraph.keys())

    def createSortListForPkg(self, pkg):
        runTimeDepPkgList = self.__runTimeDependencyGraph[pkg]
        runTimeDepPkgList.append(pkg)
        sortListForPkg = []

        for p in runTimeDepPkgList:
            basePkg = SPECS.getData().getSpecName(p)
            for bPkg in self.__sortedBuildDependencyGraph[basePkg]:
                if bPkg not in sortListForPkg:
                    sortListForPkg.append(bPkg)

        return sortListForPkg

    def getCircularDependentPackages(self, pkg):
        circularDependentPackages = []
        if pkg in self.__mapPackageToCycle:
            circularDependentPackages.extend(
                self.__mapCyclesToPackageList[self.__mapPackageToCycle[pkg]])
            circularDependentPackages.remove(pkg)
        return circularDependentPackages

    def __getSortedBuildOrderListForGivenPackages(self, listPackages):

        alreadyProcessedPackages = []
        sortedList = []
        completeListPackagesToBuild = self.findCompleteListOfPackagesRequiredToBuildGivenPackages(
            listPackages)
        packageIndexInSortedList = 0
        prevSortListLen = 0

        while completeListPackagesToBuild:

            # find next package to process
            pkg = None
            index = -1
            lenList = len(sortedList)
            for  i in range(lenList):
                if sortedList[i] in alreadyProcessedPackages:
                    continue
                pkg = sortedList[i]
                packageIndexInSortedList = i
                break

            if pkg is None:
                pkg = completeListPackagesToBuild.pop()
                packageIndexInSortedList = len(sortedList)

            #creating sort list for package
            sortListForPkg = self.createSortListForPkg(pkg)

            #remove any cyclic packages in sortListForPkg if they already exists in sortedList
            circularDependentPackages = self.getCircularDependentPackages(pkg)
            for p in circularDependentPackages:
                if p in sortedList and p in sortListForPkg:
                    sortListForPkg.remove(p)

            # insert sort list of package in global sorted list
            index = packageIndexInSortedList
            subList = []
            if packageIndexInSortedList > 0:
                subList = sortedList[:packageIndexInSortedList]
            for p in sortListForPkg:
                if  p not in subList:
                    sortedList.insert(index, p)
                    index = index + 1

            alreadyProcessedPackages.append(p)

            # Remove duplicate entries in sorted list in intervals
            if (len(sortedList) - prevSortListLen) > 100:
                self.logger.info("Removing duplicates in sortedList")
                sortedList = removeDuplicateEntriesInList(sortedList)
            else:
                prevSortListLen = len(sortedList)

        self.logger.info("Removing duplicates in sorted list")
        sortedList = removeDuplicateEntriesInList(sortedList)

        self.logger.info("Sorted list:")
        self.logger.info(sortedList)
        self.__sortedPackageList = sortedList

    def __constructBuildAndRunTimeDependencyGraph(self, package):
        basePackage = SPECS.getData().getSpecName(package)

        addBuildTimeGraph = True
        addRunTimeGraph = True
        if basePackage in self.__buildDependencyGraph:
            addBuildTimeGraph = False
        if basePackage in self.__runTimeDependencyGraph:
            addRunTimeGraph = False

        nextPackagesToConstructGraph = []
        if addBuildTimeGraph:
            listDependentRpmPackages = SPECS.getData().getBuildRequiresForPackage(basePackage)
            listDependentPackages = []
            for rpmPkg in listDependentRpmPackages:
                basePkg = SPECS.getData().getSpecName(rpmPkg)
                if basePkg not in listDependentPackages:
                    listDependentPackages.append(basePkg)
            self.__buildDependencyGraph[basePackage] = listDependentPackages
            nextPackagesToConstructGraph.extend(listDependentPackages)

        if addRunTimeGraph:
            listRpmPackages = SPECS.getData().getPackages(basePackage)
            for rpmPkg in listRpmPackages:
                listDependentRpmPackages = SPECS.getData().getRequiresAllForPackage(rpmPkg)
                self.__runTimeDependencyGraph[rpmPkg] = listDependentRpmPackages[:]
                nextPackagesToConstructGraph.extend(listDependentRpmPackages)

        for pkg in nextPackagesToConstructGraph:
            self.__constructBuildAndRunTimeDependencyGraph(pkg)

    def __readDependencyGraphAndCyclesForGivenPackages(self, listPackages):
        self.logger.info("Reading dependency graph to check for cycles")
        for pkg in listPackages:
            self.__constructBuildAndRunTimeDependencyGraph(pkg)

        for pkg in self.__buildDependencyGraph.keys():
            sortedPackageList, circularDependentPackages = self.topologicalSortPackages(
                self.__buildDependencyGraph, pkg)
            if len(circularDependentPackages) > 0:
                self.logger.error("Found circular dependency")
                self.logger.error(circularDependentPackages)
                raise Exception("Build Time Circular Dependency")
            self.__sortedBuildDependencyGraph[pkg] = sortedPackageList
        sortedPackageList, circularDependentPackages = self.topologicalSortPackages(
            self.__runTimeDependencyGraph)
        if len(circularDependentPackages) > 0:
            self.__findCircularDependencies(circularDependentPackages)

    def topologicalSortPackages(self, dependencyGraph, package=None):
        noDepPackages = set()
        sortedPackageList = []
        dependentOfPackage = dict()

        dependentPackages = {}
        if package is None:
            dependentPackages = copy.deepcopy(dependencyGraph)
        else:
            listDepPkgs = set()
            listDepPkgs.add(package)
            while listDepPkgs:
                pkg = listDepPkgs.pop()
                if pkg in dependentPackages:
                    continue
                dependentPackages[pkg] = dependencyGraph[pkg][:]
                for depPkg in dependencyGraph[pkg]:
                    listDepPkgs.add(depPkg)

        #Find packages with no dependencies and generate dependentof_package edge list
        for pkg in dependentPackages:
            if len(dependentPackages[pkg]) == 0:
                noDepPackages.add(pkg)
            else:
                for depPkg in dependentPackages[pkg]:
                    if depPkg not in dependentOfPackage:
                        dependentOfPackage[depPkg] = [pkg]
                    else:
                        if pkg not in dependentOfPackage[depPkg]:
                            dependentOfPackage[depPkg].append(pkg)

        while noDepPackages:
            pkg = noDepPackages.pop()
            sortedPackageList.append(pkg)
            if dependentOfPackage.get(pkg) is not None:
                for childPkg in list(dependentOfPackage.get(pkg)):
                    dependentOfPackage.get(pkg).remove(childPkg)
                    dependentPackages[childPkg].remove(pkg)
                    if len(dependentPackages[childPkg]) == 0:
                        noDepPackages.add(childPkg)

        # creating circular dependency graph for given dependency graph
        circularDependencyGraph = {}
        for pkg in dependentPackages.keys():
            if len(dependentPackages[pkg]) != 0:
                circularDependencyGraph[pkg] = dependentPackages[pkg]

        #return (non-circular dependent package in sorted order and circular dependent
        #package list in a dependencyGraph)
        return sortedPackageList, circularDependencyGraph

    def __constructDependencyMap(self, yclicDependencyGraph):
        self.logger.info("Constructing dependency map from circular dependency graph.....")
        constructDependencyMap = {}
        for node in cyclicDependencyGraph.keys():
            tmpDepNodeList = []
            tmpDepNodeList.append(node)
            depNodeList = []
            while len(tmpDepNodeList) != 0:
                currentNode = tmpDepNodeList.pop()
                addDepNodeList = cyclicDependencyGraph[currentNode]
                depNodeList.append(currentNode)
                for depNode in addDepNodeList:
                    if depNode in depNodeList:
                        continue
                    else:
                        if depNode not in tmpDepNodeList:
                            tmpDepNodeList.append(depNode)
            depNodeList.remove(node)
            constructDependencyMap[node] = depNodeList
        self.logger.info("Dependency Map:")
        self.logger.info(constructDependencyMap)
        return constructDependencyMap

    def __findCircularDependencies(self, cyclicDependencyGraph):
        self.logger.info("Looking for circular dependencies")
        if len(cyclicDependencyGraph) == 0:
            return
        #step1: construct dependency map from dependency graph
        constructDependencyMap = self.__constructDependencyMap(cyclicDependencyGraph)

        #step2: find cycles in dependency map
        self.logger.info("Finding and adding cycles using constructed dependency map......")
        cycleCount = 0
        for node in cyclicDependencyGraph.keys():
            listDepPkg = constructDependencyMap[node]
            cycPkgs = []
            if node not in self.__mapPackageToCycle:
                for depPkg in listDepPkg:
                    x = constructDependencyMap[depPkg]
                    if node in x:
                        cycPkgs.append(depPkg)

                if len(cycPkgs) != 0:
                    cycPkgs.append(node)
                    cycleName = "cycle" + str(PackageBuildDataGenerator.cycleCount)
                    PackageBuildDataGenerator.cycleCount += 1
                    for x in cycPkgs:
                        self.__mapPackageToCycle[x] = cycleName
                    self.__mapCyclesToPackageList[cycleName] = cycPkgs
                    self.logger.info("New circular dependency found:")
                    self.logger.info(cycleName + " " + ",".join(cycPkgs))
                    cycleCount += 1

        if cycleCount > 0:
            self.logger.info("Found " + str(cycleCount) + " cycles.")
            self.logger.info("Successfully added all detected circular dependencies to list.")
        else:
            self.logger.info("No circular dependencies found.")