def dfSearch(self, root_node, wLst):
        '''Implements the Depth-First Search (w/ special routines) for matching patterns'''

        global MAX_PHR_LEN
        global dfsStack
        dfsStack = []
        dfsStack.append( (root_node, 0, []) )
        patt_len = len(wLst)

        while len(dfsStack) > 0:
            sIndxLst = []

            (curr_node, search_indx, sIndxLst) = dfsStack.pop()   # get the lastly added element from the stack
            # @type curr_node SuffixTreeNode
            search_label = wLst[search_indx]
            curr_label = curr_node.getStrLabel()
            curr_node_depth = curr_node.getNodeDepth()

            if curr_label == "X__1" or curr_label == "X__2": prev_match = search_indx - curr_node_depth + 1
            else: prev_match = 0

            # a non-terminal X__1 or X__2 is found in the current node
            if search_label != "$$$" and (curr_node.__childIndxDict.has_key("X__1") or curr_node.__childIndxDict.has_key("X__2")):

                # either X__1 or X__2 is the child of the current node
                spanIndxLst = []
                for i in sIndxLst: spanIndxLst.append(i)
                spanIndxLst.append( search_indx )
                for child in ["X__1", "X__2"]:
                    if not curr_node.__childIndxDict.has_key(child): continue
                    new_node = curr_node.__childIndxDict[child]
                    new_search_indx = search_indx + 1
                    self.__processNewNode( new_node, new_search_indx, patt_len, spanIndxLst )

            # the word at the current position is found in the Trie
            if curr_node.__childIndxDict.has_key(search_label):
                new_node = curr_node.__childIndxDict[search_label]
                new_search_indx = search_indx + 1
                spanIndxLst = []
                for i in sIndxLst: spanIndxLst.append(i)
                if prev_match > 0:
                    spanIndxLst.append( search_indx - 1 )
                self.__processNewNode( new_node, new_search_indx, patt_len, spanIndxLst )

            # non-terminal X__1 or X__2 continues for the current position in the given pattern; or
            # also used when the word at the current position is not found in the Trie
            if prev_match > 0 and prev_match < MAX_PHR_LEN:
                new_search_indx = search_indx + 1
                spanIndxLst = []
                for i in sIndxLst: spanIndxLst.append(i)
                if new_search_indx < patt_len:
                    self.__processNewNode( curr_node, new_search_indx, patt_len, spanIndxLst )

        return None
dataset/ETHPy150Open sfu-natlang/Kriya/src/Kriya-Grammar-Xtrctr/myTrie1.py/SuffixTreeNode.dfSearch/original