class Node:
    """
    node class
    
    represents a single node in the representation graph.
    @type isPredicate: bool
    @var  isPredicate: denotes if this node is a predicate
    
    @type text: list of Word object
    @var  text: the text contained within this node
    
    @type features: dict
    @var  features: syntactic features of this node (e.g., definiteness)
    
    @type propagateTo: list
    @var  propagateTo: list of Node objects onto which the properties of this node should propogate to
    
    @type span: list
    @var  span: list of indices in the original sentence which this node spans
    @todo think if this is needed, or consumed by Word
    
    @type valid: bool
    @var  valid: debug variable, indicates if this node should be converted

    @type uid: int
    @var  uid: unique id for this node, to be able to distinguish nodes with identical features
    """
    def __init__(self,text,isPredicate,features,gr,orderText = True,uid=-1):
        """
        initialize a node object
        
        @type  orderText: boolean
        @param orderText: defines if text elements should be sorted by indices upon printing in the __str__ function 
        """  
        self.isPredicate = isPredicate
        self.text = text
        self.surface_form = copy(text)
        self.features = features
        self.features["implicit"] = False
        global nodeCounter
        if uid == -1:
            self.uid  = nodeCounter
            nodeCounter +=1
        else:
            self.uid = uid
            nodeCounter = max(nodeCounter,uid)
        self.propagateTo = []
        self.orderText = orderText
        self.nodeShape = DEFAULT_NODE_SHAPE
        self.__str__() # calculate variables in str
        self.gr = gr
        gr.add_node(self)
        
    def removeLemma(self):
        if "Lemma" in self.features:
            del(self.features["Lemma"])
        
    def get_text(self,gr):
        return self.text
    
    def addPropogation(self,node):
        """
        Add a node onto which this node's properties should propogate.
        
        @type  node: Node
        @param node: The node onto which to propogate
        """
        if node not in self.propagateTo:
            self.propagateTo.append(node)
            
    def minIndex(self):
        """ 
        Minimum index covered by this node
        
        @rtype: int
        """
        if not self.surface_form:
            return NO_INDEX # TODO: why is this happenning?
        return min([w.index for w in self.surface_form])
    
    def maxIndex(self):
        """ 
        Minimum index covered by this node
        
        @rtype: int
        """
        if not self.text:
            return NO_INDEX # TODO: why is this happenning?
        return max([w.index for w in self.surface_form])
    
    def get_original_text(self):
        return " ".join([w.word for w in sorted(self.text,key=lambda w:w.index)])
    
    
    def get_sorted_text(self):
        return sorted(self.text,
                      key= lambda w:w.index)
    
    def __str__(self):
        ret = '<TABLE BORDER="0" CELLSPACING="0"><TR><TD>'
        filtered_spans = []
        for feat,_ in PRINT_FEATURES:
            if (feat in self.features) and (isinstance(self.features[feat], dict)) and ("Span" in self.features[feat]):
                filtered_spans.extend(self.features[feat]["Span"])
        
        
        if 'Lemma' in self.features and len(self.text)==1:
            self.str = [Word(index = self.text[0].index,word=self.features['Lemma'])]
        else:
            ls = self.text
            if self.orderText:
                ls = sorted(self.text,key=lambda word:word.index)
            # self.str stores the words as displayed in the node
            self.str = [w for w in ls if w.index not in filtered_spans] 
            
        self.str = strip_punctuations(self.str)
            
        ret+= "  ".join([str(x) for x in self.str])
        
        
        ret+="</TD></TR>"
        for feat, printFunc in PRINT_FEATURES:
            if feat in self.features:
                if self.isPredicate and feat =="Definite":
                    continue
                if self.features.get("Determiner",{"Value":""})["Value"] == "no":
                    del(self.features["Determiner"])
                    continue
                ret += "<TR><TD>" 
                ret+= '<FONT POINT-SIZE="10">{0}</FONT>'.format(cgi.escape(str(printFunc(self.features[feat]))))
                ret+="</TD></TR>"
            
        ret +="</TABLE>" 
        return ret
    
    
    def to_conll_like(self):
        return "\t".join([str(self.uid),
                          ";".join([w.to_conll_like() for w in self.text]),self.pos(),str(int(bool(self.isPredicate))),
                          str(int(self.features.get("top",False))),
                          ";".join([",".join([self.gr.edge_label((father,self)),str(father.uid)]) for father in self.gr.incidents(self)])
                          ])
    
    def neighbors(self):
        ret = {}
        for neighbour in self.gr.neighbors(self):
            label = self.gr.edge_label((self,neighbour))
            curEntry = ret.get(label,[])
            curEntry.append(neighbour)
            ret[label] = curEntry
        return ret
    
    def incidents(self):
        ret = {}
        for father in self.gr.incidents(self):
            label = self.gr.edge_label((father,self))
            curEntry = ret.get(label,[])
            curEntry.append(father)
            ret[label] = curEntry
        return ret
    
    
    def is_implicit(self):
        return self.features.get("implicit",False)
    
    def pos(self):
        return self.features.get("pos","")
    
    def isConj(self):
        return self.features.get("conj",False)

    def is_wh_question(self):
        """
        Returns True iff this is a WH-question word.
        From PTB pos tags, it seems that W as start of POS identifies
        such words:
        33. WDT        Wh-determiner
        34. WP         Wh-pronoun
        35. WP$        Possessive wh-pronoun
        36. WRB        Wh-adverb
        """
        return self.pos().startswith("W")


    def __hash__(self):
        return self.__str__().__hash__()
    
    def makeTopNode(self):
        if self.features.get("top",False):
            return False
        self.features["top"] = True
        return True
 def isDefinite(node):
    return node.features.get("Definite",False) == definite_label
 def getCopular(gr,index,features):
    if "Lemma" in features:
        del(features["Lemma"])
    ret = Node(text=[Word(index=index,word=COPULA)],
               isPredicate=True,
               features=features,
               gr=gr,
               orderText = True)
    ret.features["implicit"] = True
    ret.original_text=[]
    return ret
 def getPossesive(gr,index):
    ret = Node(text=[Word(index=index,word=POSSESSIVE)],
               isPredicate=True,
               features={},
               gr=gr,
               orderText = True)
    ret.features["implicit"] = True
    ret.original_text=[]
    return ret
 EXISTENSIAL = "Exists" # the textual value of a conjunction node
 def get_min_max_span(graph, node):
    """
    Get minimum and maximum indices covered by the subgraph rooted at a specific node
    
    @type  graph: graph_wrapper.GraphWrapper
    @param graph: a graph in which the node reside

    @type  node: node
    @param node: root of the given subgraph
    
    @rtype:  tuple [int]
    @return: (min,max) 
    """
    
    minInd = NO_INDEX
    maxInd = NO_INDEX
    
    for curNode in traversal(graph, node, 'pre'):
        curMin = curNode.minIndex()
        curMax = curNode.maxIndex()
        
        maxInd = max(maxInd, curMax)
        if curMin != NO_INDEX:
            if minInd == NO_INDEX:
                minInd = curMin
            else:
                minInd = min(minInd, curMin)
            
    return (minInd, maxInd)
 def find_nodes(graph, filterFunc):
    """
    Find nodes in graph that match a filter function
    
    @type  graph: graph_wrapper
    @param graph: the graph in which to find nodes
    
    @type  filterFunc: lambda(Node):bool
    @param filterFunc: function that receives a node and returns true if you want to include it in the return list
    
    @rtype list(Node)
    @param list of Node objects matching filter func.
    """
    return filter(filterFunc, graph.nodes())
 def find_edges(graph, filterFunc):
    """
    Find edges in graph that match a filter function
    
    @type  graph: graph_wrapper
    @param graph: the graph in which to find edges
    
    @type  filterFunc: lambda(edge):bool
    @param filterFunc: function that receives an edge and returns true if you want to include it in the return list
    
    @rtype list(edges)
    @param list of edges matching filter func. 
    """
    return filter(filterFunc, graph.edges())
 def merge_nodes(gr, node1, node2):
    if (gr.has_edge((node1, node2))):
        gr.del_edge((node1, node2))
    else:
        gr.del_edge((node2, node1))
        
    new = newNode.join(node1, node2, gr)
    for curNode in [node1, node2]:
        for curFather in gr.incidents(curNode):
            if (not gr.has_edge((curFather,new))):
                duplicateEdge(graph=gr,
                              orig=(curFather, curNode),
                              new=(curFather, new))
        for curNeigbour in gr.neighbors(curNode):
            if (not gr.has_edge((new,curNeigbour))):
                duplicateEdge(graph=gr,
                              orig=(curNode, curNeigbour),
                              new=(new, curNeigbour))
    gr.del_nodes([node1, node2])
 def multi_get(d, ls):
    ret = []
    for k in ls:
        ret.extend(d.get(k, []))
    return ret        
 def duplicateEdge(graph, orig, new, newLabel=""):
    """
    adds a new edge, duplicating the label of the original one
    """
    label = graph.edge_label(orig)
    if not label:
        label = newLabel
        
    graph.add_edge(edge=new,
                   label=label)
 def accessibility_wo_self(graph):
    ret = accessibility(graph)
    for k in ret:
        ret[k].remove(k)
    return ret
 def subgraph_to_string(graph,node,exclude=[]):
    nodes = [node]
    change = True
    while change:
        change=False
        for curNode in nodes:
            for curNeigbour in graph.neighbors(curNode):
                if (curNeigbour in nodes) or (curNeigbour in exclude): continue
                nodes.append(curNeigbour)
                change = True
    

#     minInd = min([n.minIndex() for n in nodes])-1
#     maxInd = max([n.maxIndex() for n in nodes])-1
#     ret = " ".join(graph.originalSentence.split(" ")[minInd:maxInd+1])
#     nodes = [n for n in minimal_spanning_tree(graph, node) if not n in exclude]
#     ret = " ".join(node.get_original_text() for node in sorted(nodes,key = lambda n: n.minIndex()))
    try:
        ret = ""
        words = []
        for n in nodes:
            words += n.surface_form
        words = list(set(words))
        ret = " ".join([w.word for w in strip_punctuations(sorted(words,key=lambda w:w.index))])+" "
    except:
        raise Exception()
#     
    
    return ret
 def find_top_of_component(graph, source_node):
    """
    Find the top node of the connected component in which source_node resides.
    Since this graph may contain cycles - we go "up" the graph, as long as we don't revisit nodes
    """
    _, d = shortest_path(reverse_graph_edges(graph), # Reverse graph to go up
                         source = source_node)
    return max(d.iteritems(),
               key = itemgetter(1))[0] # Returns the farthest away node
 class Word:
    """
    word container class, to add the index of the word in addition to the word 
    
    @type index: int
    @var  index: the index of the word within the sentence
    
    @type text: string
    @var  text: the text contained within this word
    """
    
    def __init__(self,index,word):
        """
        initialize a word container object
        """
        self.index = index
        self.word = word
    
    def to_conll_like(self):
        return ",".join([str(self.index),self.word])
    
    def __str__(self):
        ret = cgi.escape(self.word)
        if self.index != NO_INDEX:
            ret += '<FONT POINT-SIZE="7">[{0}]</FONT>'.format(self.index)
        return ret
    
    def __eq__(self,other_word):
        return (self.index == other_word.index) and (self.word == other_word.word)
    
    def __hash__(self):
        return self.__str__().__hash__()
 REASON_LABEL = "reason"
OUTCOME_LABEL = "outcome"
EVENT_LABEL = "event"
CONDITION_LABEL = "condition"
FIRST_ENTITY_LABEL = "sameAs_arg"
SECOND_ENTITY_LABEL = "sameAs_arg"
POSSESSOR_LABEL = "possessor"
POSSESSED_LABEL = "possessed"
ARG_LABEL = "arg"
POSS_LABEL = "poss"
MARK_LABEL = "mark"
EXPL_LABEL = 'expl'
SOURCE_LABEL = 'source'
MODIFIER_LABEL = "modifier"
POSSESSIVE_LABEL = "possessive"
SUBJ_LABEL  = "subj"
OBJECT_LABEL = "obj"
DIRECT_OBJECT_LABEL = "dobj"
INDIRECT_OBJECT_LABEL = "iobj"
VB = "VB"       #Verb, base form
VBD = "VBD"     #Verb, past tense
VBG = "VBG"     #Verb, gerund or present participle
VBN = "VBN"     #Verb, past participle
VBP = "VBP"     #Verb, non-3rd person singular present
VBZ = "VBZ"     #Verb, 3rd person singular present
VERB_POS = [VB,VBD,VBP,VBZ,VBN] # all types of verb pos
TO = "TO"
IN = "IN"
MD = "MD"
DOT = "."
COMMA = ","
TENSE_PAST = "past"
TENSE_PRESENT = "present"
TENSE_FUTURE = "future"
TENSE_UNKNOWN = "unknown"
WILL = "will"
WONT = "wo"
WOULD = "would"
D = "'d"
HAVE = "have"
BE = "be"
BEEN = "been"
FUTURE_MODALS = [WILL, WONT, WOULD, ll, D, "may", "might"] # "wo" is the Modal part of "won't"
AS = "as"
COND_IF = "if"
COND_AFTER = "after"
def aux_children_with_pos(pos_tag):
 class Proposition:
    def __init__(self,pred,args,outputType):
        self.pred = pred
        self.args = args
        self.outputType = outputType
        for ent in self.args:
            (rel,arg) = ent
            if rel == POSSESSOR_LABEL:
                ent[1] = fixPossessor(arg)
    
    def find_ent(self,ent):
        ret = []
        for i,(rel,arg) in enumerate(self.args):
            if ent in arg:
                ret.append(i)
        return ret
                 
        
    def rel_order(self,rel):
        if rel in subject_dependencies+[domain_label,POSSESSED_LABEL,POSSESSOR_LABEL]:
            return 0
        if rel == ARG_LABEL:
            return 1
        if rel in object_dependencies:
            return 2
        if rel.startswith("prep"):
            return 3
        if rel == SOURCE_LABEL:
            return 5
        else:
            return 4
        
    def __str__(self):
        PDF = (self.outputType == "pdf")
        HTML = (self.outputType == "html")
        if PDF:
            bold = lambda t:t
            color = lambda t,color:t
        if HTML:
            bold = lambda t:"<b>{0}</b>".format(t)
            color = lambda t,color:'<font color="{0}">{1}</font>'.format(color,t)
            
        curProp = r'{0}:({1})'.format(bold(self.pred),
                                      ", ".join([rel + ":" + bold(color(arg,"blue")) for rel,arg in sorted(self.args,key=lambda(rel,_):self.rel_order(rel))]))
        return curProp
 class Proposition:
    def __init__(self,pred,args,outputType):
        self.pred = pred
        self.args = args
        self.outputType = outputType
        for ent in self.args:
            (rel,arg) = ent
            if rel == POSSESSOR_LABEL:
                ent[1] = fixPossessor(arg)
    
    def find_ent(self,ent):
        ret = []
        for i,(rel,arg) in enumerate(self.args):
            if ent in arg:
                ret.append(i)
        return ret
                 
        
    def rel_order(self,rel):
        if rel in subject_dependencies+[domain_label,POSSESSED_LABEL,POSSESSOR_LABEL]:
            return 0
        if rel == ARG_LABEL:
            return 1
        if rel in object_dependencies:
            return 2
        if rel.startswith("prep"):
            return 3
        if rel == SOURCE_LABEL:
            return 5
        else:
            return 4
        
    def __str__(self):
        PDF = (self.outputType == "pdf")
        HTML = (self.outputType == "html")
        if PDF:
            bold = lambda t:t
            color = lambda t,color:t
        if HTML:
            bold = lambda t:"<b>{0}</b>".format(t)
            color = lambda t,color:'<font color="{0}">{1}</font>'.format(color,t)
            
        curProp = r'{0}:({1})'.format(bold(self.pred),
                                      ", ".join([rel + ":" + bold(color(arg,"blue")) for rel,arg in sorted(self.args,key=lambda(rel,_):self.rel_order(rel))]))
        return curProp
 COPULA = "SameAs"          # the textual value of a copula node
PROP = "PROP"          # the textual value of a property node
RCMOD_PROP = "PROP"    # the textual value of a property for rcmod node
POSSESSIVE = "have" # the textual value of a possessive node
APPOSITION = "appos"   # the textual value of an appositio n node
PREP = "PREP"          # the textual value of a preposition node
PREP_TYPE = "TYPE"     # the textual value of a preposition node's type
COND = "COND"          # the textual value of a conditional node
TIME = "TIME"          # the textual value of a time node
LOCATION = "LOCATION"  # the textual value of a location node
CONJUNCTION = "CONJ -" # the textual value of a conjunction node
ADVERB = "ADV"         # the textual value of a conjunction node
EXISTENSIAL = "Exists" # the textual value of a conjunction node
COND_TYPE= PREP_TYPE   # the textual value of a conditional node's type
RECT_NODE_SHAPE = "rect"
DEFAULT_NODE_SHAPE = "ellipse"
PRINT_FEATURES = [("Tense",lambda t:t),
                  ("Determiner",lambda t:"det: "+t["Value"]),
                  ("Time Value",lambda t:"date: "+t),
                  ("Negation", lambda t:"negated"),
                  ("Passive Voice", lambda t:"passive"),
                  ("Modal",lambda t:"modal: "+ " ".join(t["Value"])),
                  ("Definite",lambda t:t),
                  ("Modifier",lambda t:"modifier: "+t)]
def resetCounter():
    def __init__(self,text,isPredicate,features,gr,orderText = True,uid=-1):
    def removeLemma(self):
    def get_text(self,gr):
    def addPropogation(self,node):
    def minIndex(self):
    def maxIndex(self):
    def get_original_text(self):
    def get_sorted_text(self):
    def __str__(self):
    def to_conll_like(self):
    def neighbors(self):
    def incidents(self):
    def is_implicit(self):
    def pos(self):
    def isConj(self):
    def is_wh_question(self):
    def __hash__(self):
    def makeTopNode(self):
def getCopular(gr,index,features):
def getPossesive(gr,index):
def join(node1,node2,gr):
def isDefinite(node):
class Node:

from subprocess import call
from pygraph.classes.digraph import digraph
from props.graph_representation.newNode import Node, isDefinite, getCopular, \
    getPossesive, EXISTENSIAL
from pygraph.algorithms.accessibility import accessibility
from props.graph_representation.graph_utils import get_min_max_span, find_nodes, \
    find_edges, merge_nodes, multi_get, duplicateEdge, accessibility_wo_self, \
    subgraph_to_string, find_top_of_component
from props.graph_representation.word import Word
from props.dependency_tree.definitions import domain_label, copular_verbs, \
    subject_dependencies, clausal_complement, clausal_complements, \
    FIRST_ENTITY_LABEL, SECOND_ENTITY_LABEL, arguments_dependencies, gerund_pos, \
    determiner_dependencies, determined_labels, SOURCE_LABEL, ARG_LABEL,\
    contractions
from itertools import product
from props.graph_representation.proposition import Proposition
from copy import copy, deepcopy
from itertools import product
from props.graph_representation.proposition import Proposition
from copy import copy, deepcopy
from props.graph_representation import newNode
import pygraph.readwrite
import pygraph.readwrite.dot
import re, cgi, time, subprocess, math

                dups = topNode.features.get("dups", [])
                allDups = reduce(lambda x, y:list(x) + list(y), dups, [])
                rest = [n for n in self.neighbors(topNode) if n not in allDups]
                neigboursList = []
                for combination in product(*dups):
                    curNeigbourList = []
                    ls = list(combination) + rest
                    for curNode in ls:
                        curNeigbourList.append((self.edge_label((topNode, curNode)), curNode))
                    neigboursList.append(curNeigbourList)
                
                for nlist in neigboursList:
                    argList = []
                    all_neighbours = [n for _, n in nlist]
                    for k, curNeighbour in sorted(nlist, key=lambda(k, n):get_min_max_span(self, n)[0]):
                        curExclude = [n for n in all_neighbours if n != curNeighbour] + [topNode]
                        argList.append([k, subgraph_to_string(self, curNeighbour, exclude=curExclude)])
                    curProp = Proposition(topNode.get_original_text(), argList, outputType)
                    ret.append(curProp)
                    
        return ret
    
    def normalize_labels(self):
        for edge in self.edges():
            edgeLabel = self.edge_label(edge)
            if edgeLabel in normalize_labels_dic:
                self.del_edge(edge)
                self.add_edge(edge,label = normalize_labels_dic[edgeLabel])
    
    def do_vmod_relclause(self):
        edges = find_edges(self, lambda (u, v):(self.edge_label((u, v)) == "rcmod"))
        for (u, v) in edges:
            v.features["top"] = True
            if  u.pos() in determined_labels:
                self.del_edge((u, v))
                self.types.add("definite rcmod")
                if not self.has_edge((v, u)):
                    self.add_edge((v, u), label=ARG_LABEL)
        
        edges = find_edges(self, lambda (u, v):(self.edge_label((u, v)) == "vmod"))
        for (u, v) in edges:
            self.types.add("vmod")
            if u.pos() in determined_labels:
                self.del_edge((u, v))
                self.types.add("definite vmod")
                if not self.has_edge((v, u)):
                    self.add_edge((v, u), label=ARG_LABEL)
        
        
                                
    def do_poss(self):
        edges = find_edges(self, lambda (u, v):self.edge_label((u, v)) == "poss")
        for (possessed, possessor) in edges:
            self.types.add("Possessives")
            possessiveNode = getPossesive(self, possessor.minIndex())  # TODO: refine index
            self.add_edge(edge=(possessiveNode, possessor),
                          label=POSSESSOR_LABEL)
            self.add_edge(edge=(possessiveNode, possessed),
                          label=POSSESSED_LABEL)

    def do_questions(self):
        """
        Identify questions and introduce appropriate structure
        This currently follows the syntactic format of geo query wh-questions.
        Such as: "How large is Texas?"
        Where we have a WH question word ("How") dependent of a modifier of some property ("Large")
        """
        # Find relevant edges
        edges = find_edges(self,
                           lambda (u, v): v.is_wh_question())

        # Handle each separately
        for (modifier, wh_question) in edges:
            self.types.add("Questions")
            # 1. Remove dep edge
            self.del_edge((modifier, wh_question))

            # 2. Posit the wh question as head of the embedded clause
            self.add_edge(edge = (wh_question,
                                  find_top_of_component(self,
                                                        modifier)),
                          label = QUESTION_INQUIRY)

            # 3. Mark that the Wh-question node is a predicate
            wh_question.isPredicate = True

    def head(self, node):
        incidents = node.incidents()
        while (node.isPredicate) and ("xcomp" in incidents):
            node = incidents["xcomp"][0]
            incidents = node.incidents()
        return node
    
    
    def do_conj(self):
        edges = find_edges(self, lambda((u, v)):self.edge_label((u, v)).startswith("conj_"))# and (not u.isPredicate) and (not v.isPredicate))
        nodes = set([u for (u,_) in edges])
        for conj1 in nodes:
            curStartIndex = conj1.minIndex()+1
            curNeighbours = conj1.neighbors()
            isModifier = (not bool([father for father in self.incidents(conj1) if not self.is_aux_edge((father.uid, conj1.uid))])) and bool(self.incidents(conj1)) 
            for rel in [rel for rel in curNeighbours if rel.startswith("conj_")]:
                marker = rel.split("conj_")[1]
                
                markerNode = newNode.Node(text=[Word(curStartIndex+1,marker)], #TODO: how to find marker's index
                                          isPredicate=True,
                                          features={"conj":True},
                                          gr=self)

                #decide how to connect it to the rest of the graph, based on its type
                if isModifier:
                    duplicate_all_incidents(gr=self, source=conj1, target=markerNode)
                else:
                    for father in self.incidents(conj1):
                        for conj2 in curNeighbours[rel]:
                            duplicateEdge(graph=self, orig=((father,conj1)), new=((father,conj2)))
                        duplicateEdge(graph=self, orig=((father,conj1)), new=((father,markerNode)))
                        
                    if conj1.isPredicate:
                        for neighbor in self.neighbors(conj1):

                            if get_min_max_span(self, neighbor)[0] < curStartIndex:
