def BP_tree_to_nltk_tree(tree):
    root = Tree(str(tree.keys), children = [])
    if isinstance(tree, BPnode) or isinstance(tree, Node):
        for child in tree.children:
            root.append(BP_tree_to_nltk_tree(child))

    return root

def wsjtree2pos(wsj_corpus_path):
    print >> sys.stderr, "Reading in corpus..."
    sentences = []
    for d in os.listdir(wsj_corpus_path):
        if os.path.isdir(wsj_corpus_path + "/" + d) and d != "CVS" and int(d) < 8:
            for f in os.listdir(wsj_corpus_path + "/" + d):
                if f.endswith(".mrg"):
                    fname = wsj_corpus_path + "/" + d + "/" + f
                    # print fname
                    tree_f = open(fname, "r")
                    tree_string = ""
                    for line in tree_f:
                        if line.strip():
                            if line.startswith("( (") or line.startswith("(("):
                                if tree_string:
                                    tr = Tree(tree_string)
                                    sentences.append(tr.pos())
                                    tree_string = line.strip()
                                else:
                                    tree_string = line.strip()
                            else:
                                tree_string += line.strip()
                    if tree_string:
                        tr = Tree(tree_string)
                        sentences.append(tr.pos())

    return sentences

 def __init__(self, node, children, parent_node=None,
              rel=None, attrs=None, head=None):
   self.parent_node = parent_node
   self.rel = rel
   self.attrs = attrs
   self.head = head  
   Tree.__init__(self, node, children)  

    def parse_tree(self, text, binary=False, preprocessed=False):
        nlp_output = self.nlp.annotate(text, properties={
            'annotators': 'tokenize,ssplit,pos,parse',
            'outputFormat': 'json',
            'parse.binaryTrees': 'true'
        })
        if type(nlp_output) == str:
            nlp_output = json.loads(nlp_output, strict=False)

        if len(nlp_output['sentences']) > 1:
            #merge trees from sentences
            tree_string = "(Top "
            for s in nlp_output['sentences']:
                p_tree = Tree.fromstring(s['parse'])
                tree_string += str(p_tree[0])
            tree_string += ")"
            merged_tree = Tree.fromstring(tree_string)
        else:
            #no merging required
            merged_tree = Tree.fromstring(nlp_output['sentences'][0]['parse'])
            #remove root
            merged_tree = merged_tree[0]

        if binary:
            nltk.treetransforms.chomsky_normal_form(merged_tree)

        if preprocessed:
            merged_tree = preprocess_parse_tree(merged_tree)

        return merged_tree

def attach_tree(head,dep,attachment,chain,indexes,flag,coindex=None):
    #head,dep: trees; flag: 'right'/'left'
    """ attach dep's projection chain to head's projection chain """
    if isinstance(coindex,int): # handle coindex tag
        label = attachment['label2']
        offset = attachment['offset2']
        dep = Tree(dep.label(),['*-'+str(coindex)])        
    else:
        label = attachment['label']
        offset = attachment['offset']
        
    l_index = [l[0] for l in chain[0]].index(label)
    count = sum([l[1] for l in chain[0]][:l_index+1])-offset
    if flag=='right':
        a_index = indexes[count-1]+1
    elif flag=='left':
        a_index = indexes[count-1]
        indexes[count-1] += 1
    else:
        return "Invalid flag!"
    if head.label()=='PRN':
        s = 'head[0]'
    else:
        s = 'head'
    for i in range(count-1):
        s += '['+str(indexes[i])+']'
    eval(s+'.insert('+str(a_index)+',dep)') # insert() vs pop()
    
    if 'f_tag' in attachment:
        if attachment['f_tag'] not in {'PRD','PRDs'}:
            eval(s+'.set_label('+s+'.label()+"-"+attachment["f_tag"])')
        else:
            s += '['+str(indexes[count-1])+']'
            eval(s+'.set_label('+s+'.label()+"-"+attachment["f_tag"])')
    return head,indexes

 def munge(t):
     if type(t) == Tree:
         toks = t.leaves()
         t = Tree(t.label(), [munge(child) for child in t])
         setattr(t, "tokens", toks)
         return t
     else:
         return Tree(t, [])

def parser_output_to_parse_deriv_trees(output):
    lines = output.strip().split("\n")
    deriv_tree_lines = lines[::2]
    parse_tree_lines = lines[1::2]

    parse_trees = [Tree.fromstring(line.replace('\x06', 'epsilon_')) for line in parse_tree_lines if line != '']
    deriv_trees = [Tree.fromstring(line) for line in deriv_tree_lines if line != '']
    return parse_trees, deriv_trees

def removeNounMods(tree):
    tree_str = tsurgeon.remove_internal_mods(tree)
    if tree_str != '':
        tree = Tree.fromstring(tree_str)
    tree_str = tsurgeon.remove_participle_mods(tree)
    if tree_str != '':
        tree = Tree.fromstring(tree_str)
    return tree

    def parse(self, tagged_sent):
        """Parse a tagged sentence.

        tagged_sent -- the tagged sentence (a list of pairs (word, tag)).
        """
        t = Tree(self.start, [Tree(tag, [word]) for word, tag in tagged_sent])
        t.chomsky_normal_form(factor='left', horzMarkov=0)
        return t

	def _get_tense(cls, parse, token_indices, use_gold=False):
		if len(token_indices) == 1:
			return 'one_token'
		parse_tree = Tree(parse['parsetree'])
		start_index = min(token_indices)
		end_index = max(token_indices) + 1
		tree_position = parse_tree.treeposition_spanning_leaves(start_index, end_index)
		arg_subtree = parse_tree[tree_position]
		return cls._recurse_search_tag(arg_subtree, ['VP'], [])

    def test_lbranch_parse(self):
        model = LBranch([], 'S')  # empty training set

        trees = [model.parse(s) for s in self.tagged_sents]

        trees2 = [
            Tree.fromstring("""(S (S|<> (S|<> (S|<> (D El) (N gato)) (V come)) (N pescado)) (P .))"""),
            Tree.fromstring("""(S (S|<> (S|<> (S|<> (D La) (N gata)) (V come)) (N salmón)) (P .))"""),
        ]
        self.assertEqual(trees, trees2)

    def test_flat_parse(self):
        model = Flat([], 'S')  # empty training set

        trees = [model.parse(s) for s in self.tagged_sents]

        trees2 = [
            Tree.fromstring("(S (D El) (N gato) (V come) (N pescado) (P .))"),
            Tree.fromstring("(S (D La) (N gata) (V come) (N salmón) (P .))"),
        ]
        self.assertEqual(trees, trees2)

 def tags2tree(sentence, root_label='S', strict=False):
     tree = Tree(root_label, [])
     for (word, postag, chunktag) in sentence:
         if chunktag is None:
             if strict:
                 raise ValueError("Bad tag sequence")
             else:
                 # Treat as O
                 tree.append((word, postag))
         elif chunktag.startswith('B'):
             tree.append(Tree(chunktag[2:], [(word, postag)]))
         elif chunktag.startswith('I'):
             if (len(tree) == 0 or not isinstance(tree[-1], Tree) or
                         tree[-1].label() != chunktag[2:]):
                 if strict:
                     raise ValueError("Bad tag sequence")
                 else:
                     # Treat as B-*
                     tree.append(Tree(chunktag[2:], [(word, postag)]))
             else:
                 tree[-1].append((word, postag))
         elif chunktag == 'O':
             tree.append((word, postag))
         else:
             raise ValueError("Bad tag %r" % chunktag)
     return tree

def conlltags2tree(sentence, chunk_types=('NP','PP','VP'),
                   root_label='S', strict=False):
    """
    Convert the CoNLL IOB format to a tree.
    """
    tree = Tree(root_label, [])
    for (word, postag, chunktag) in sentence:
        if chunktag is None:
            if strict:
                raise ValueError("Bad conll tag sequence")
            else:
                # Treat as O
                tree.append((word,postag))
        elif chunktag.startswith('B-'):
            tree.append(Tree(chunktag[2:], [(word,postag)]))
        elif chunktag.startswith('I-'):
            if (len(tree)==0 or not isinstance(tree[-1], Tree) or
                tree[-1].label() != chunktag[2:]):
                if strict:
                    raise ValueError("Bad conll tag sequence")
                else:
                    # Treat as B-*
                    tree.append(Tree(chunktag[2:], [(word,postag)]))
            else:
                tree[-1].append((word,postag))
        elif chunktag == 'O':
            tree.append((word,postag))
        else:
            raise ValueError("Bad conll tag {0!r}".format(chunktag))
    return tree

 def __str2BguTree(self,text):
     lines = text.split('\n')
     tree = Tree('s',[])
     for line in lines:
         if line=='':
             continue
         mlist = line.split("\t")
         word = mlist[0]
         raw = mlist[1]
         tree.append((word,bguTag(raw)))
     return tree

    def __build_tree(self, node_num):
        word_tuple = self.words[node_num]
        tree_node = Tree(word_tuple[1], [])

        node_dependencies = self.dependencies.get(node_num)
        if node_dependencies is not None:
            for dependency in node_dependencies:
                dependency_node = self.__build_tree(dependency[0])
                tree_node.append(dependency_node)

        return tree_node

def extractParticiple(tree):
    part_mod = tsurgeon.hasParticipleMod(tree)
    if part_mod != '':
        subject = tsurgeon.findSubject(tree)
        subject_words = Tree.fromstring(subject).leaves()
        part_tree = Tree.fromstring(part_mod)
        part_words = part_tree.leaves()
        # Ignoring inflection
        result_words = subject_words + ['is'] + part_words[1:]
        sentence = ' '.join(result_words).strip() + '.'
        return sentence
    pass

def postag_tree(tree):
    # Part-of-speech tagging.
    words = tree.leaves()
    tag_iter = (pos for (word, pos) in pos_tag(words))
    newtree = Tree('S', [])
    for child in tree:
        if isinstance(child, Tree):
            newtree.append(Tree(child.label(), []))
            for subchild in child:
                newtree[-1].append( (subchild, next(tag_iter)) )
        else:
            newtree.append( (child, next(tag_iter)) )
    return newtree

    def _strip_functional_tags(self, tree: Tree) -> None:
        """
        Removes all functional tags from constituency labels in an NLTK tree.
        We also strip off anything after a =, - or | character, because these
        are functional tags which we don't want to use.

        This modification is done in-place.
        """
        clean_label = tree.label().split("=")[0].split("-")[0].split("|")[0]
        tree.set_label(clean_label)
        for child in tree:
            if not isinstance(child[0], str):
                self._strip_functional_tags(child)

def visualize_sentence_tree(sentence_tree):
    
    processed_tree = process_sentence_tree(sentence_tree)
    processed_tree = [
                        Tree( item[0],
                             [
                                 Tree(x[1], [x[0]])
                                 for x in item[1]
                             ]
                            )
                            for item in processed_tree
                     ]
    tree = Tree('S', processed_tree )
    tree.draw()