#Given a sorted dictionary of an alien language, find order of characters
class graphNode(object):
    def __init__(self, data):
        self.data = data
        self.link = []

class CreateGraph():
    def __init__(self):
        #key is node data and value is node object
        self.nodesDictionary = {}
        self.root = None

    def createNode(self, data):
        node = graphNode(data)
        return node

    def addChildNode(self, parentNode, childNode):
        parentNode.link.append(childNode)
        return parentNode

    #Creates uni directed graph from given array
    #So if array is b,a,d then graph will be
    #b->a->d
    def createGraph(self, array):
        #Create graph nodes and fill dictionary
        for letter in array:
            if not letter in self.nodesDictionary:
                node = self.createNode(letter)
                self.nodesDictionary[letter] = node
                if self.root == None:
                    self.root = node
        #Add edges
        for i in range(len(array)-1):
            pnode = self.nodesDictionary[array[i]]
            cnode = self.nodesDictionary[array[i+1]]
            pnode = self.addChildNode(pnode, cnode)

    def dfs(self, node, output):
        if not node.link:
            print output
            return
        for child in node.link:
            output.append(child.data)
            self.dfs(child, output)
            output.pop()

    def dfsTraversal(self):
        self.dfs(self.root, [self.root.data])
        
        
                
                
        
        
class trieNode(object):
    def __init__(self, letter):
        self.letter = letter
        self.childern = []
        self.childCount = 0

class CreateTrie():
    def __init__(self):
        self.trieRoot = trieNode("")
        #keeps track of all letters of all words in trie
        self.letterDictionary = []
        self.childCollector = []

    def traverse_collectChildern(self, parentNode):
        if not parentNode.childern:
            return       
        for child in parentNode.childern:
            if child.childCount > 1:
                childNodeData = self.returnChildNodeData(child)
                self.childCollector.append(childNodeData)
            self.traverse_collectChildern(child)
    #Traverses the trie and returns all the intermediate node childern    
    def collectChildern(self):
        rootChildern = self.returnChildNodeData(self.trieRoot)
        self.childCollector.append(rootChildern)
        self.traverse_collectChildern(self.trieRoot)
        return self.childCollector

    def findWord(self, word):
        parentNode = self.trieRoot
        for letter in word:
            childFlag, childNode = self.findChild(parentNode, letter)
            if childFlag:
                parentNode = childNode
            else:
                return False
        return True

    def returnChildNodeData(self, node):
        if not node.childern:
            return False
        output = []
        for child in node.childern:
            output.append(child.letter)
        return output

    def createNode(self, letter):
        node = trieNode(letter)
        return node

    def addChildToTrieNode(self, child, node):
        node.childern.append(child)
        node.childCount = node.childCount + 1

    def findChild(self, node, childData):
        #if Node does not have childern
        if not node.childern:
            return False, -1
        for child in node.childern:
            if(child.letter == childData):
                return True, child
        return False, -1
        
    def addWordToTrie(self, word):
        parentNode = self.trieRoot
        for letter in word:
            #Add letter to letter dictionary
            if not letter in self.letterDictionary:
                self.letterDictionary.append(letter)
            childFlag, childNode = self.findChild(parentNode, letter)
            if childFlag:
                parentNode = childNode
            else:
                #Create child node
                cnode = self.createNode(letter)
                self.addChildToTrieNode(cnode, parentNode)
                parentNode = cnode

class AlienDictionary(object):
    def __init__(self, words):
        self.graph = CreateGraph()
        self.trie = CreateTrie()
        #Create a trie
        for word in words:
            self.trie.addWordToTrie(word)

    def print_order(self):
        allChildern = self.trie.collectChildern()
        for child in allChildern:
            self.graph.createGraph(child)
        self.graph.dfsTraversal()



#Leetcode solution
class LeetCodeGraphNode(object):
    def __init__(self, letter):
        self.letter = letter
        self.next = None
        #To detect cycle
        self.seen = False
        
class Solution(object):
    def __init__(self):
        self.hashTable = {}
        self.root = None
        
    def createNode(self, letter):
        node = LeetCodeGraphNode(letter)
        return node
    
    def addNextToNode(self, node, nextLink):
        node.next = nextLink

    def addToHashTable(self,letter):
        if not(letter in self.hashTable):
            self.hashTable[letter] = self.createNode(letter)
        if(self.root == None):
            print "root is ", letter
            self.root = self.hashTable[letter]

    #creates nodes from letters and adds edge between node1 -> node2
    def connect2Letters(self, letter1, letter2):
        #if the nodes are not in hash table then add them
        self.addToHashTable(letter1)
        self.addToHashTable(letter2)
        #add edge from node1 -> node2
        self.addNextToNode(self.hashTable[letter1], self.hashTable[letter2])
        print "Added edge between ", letter1, " and ", letter2

    #need to imporve this function, right now its only doing simple traversal, we need topo sort or dfs
    def traverseLinkedList(self):
        ptr = self.root
        output = ""
        while(ptr != None):
            if(ptr.seen == True):
                return ""
            output = output +  ptr.letter
            ptr.seen = True
            ptr = ptr.next
        #Go through hash table, if there is no edgebetween rest of them then add it to output by alphabetical order
            
        return output

    def logic(self, words):
        for i in range(1, len(words)):
            if(words[i-1] == words[i]):
                return ""
            self.root = self.hashTable[letter]

    def logic(self, words):
        for i in range(1, len(words)):
            letterIndex = 0
            while(letterIndex < len(words[i-1]) and letterIndex < len(words[i]) and words[i-1][letterIndex] == words[i][letterIndex]):
                self.addToHashTable(words[i][letterIndex])
                letterIndex = letterIndex+1
            if(letterIndex < len(words[i-1]) and letterIndex < len(words[i]) ):
                self.connect2Letters(words[i-1][letterIndex], words[i][letterIndex])
        #Traverse the created linked list
        return self.traverseLinkedList()
                
    def alienOrder(self, words):
        print self.logic(words)
        self.logic(words)
        """
        :type words: List[str]
        :rtype: str
        """






#Main program
words1 = ["baa", "abcd", "abca", "cab", "cad"]
words2 = ["caa", "aaa", "aab"]
words3 = ["wrt", "wrf", "er", "ett", "rftt"]
words4 = [ "z","x","z"]
words5 = ["z", "z"]
words6 = ["wrt","wrtkj"]
#words = ["baa", "abcd", "abca", "cab", "cad"]
#words = ["caa", "aaa", "aab"]
words = ["wrt", "wrf", "er", "ett", "rftt"]
#o = AlienDictionary(words)
#o.print_order()

obj1 = Solution()
obj1.alienOrder(words1)

obj2 = Solution()
obj2.alienOrder(words2)

obj3 = Solution()
obj3.alienOrder(words3)

obj4 = Solution()
obj4.alienOrder(words4)

obj5 = Solution()
obj5.alienOrder(words5)

obj6 = Solution()
obj6.alienOrder(words6)