    001    package org.maltparser.core.syntaxgraph;
    002
    003    import java.util.Iterator;
    004    import java.util.NoSuchElementException;
    005    import java.util.Observable;
    006    import java.util.Set;
    007    import java.util.SortedMap;
    008    import java.util.SortedSet;
    009    import java.util.TreeMap;
    010    import java.util.TreeSet;
    011
    012
    013    import org.maltparser.core.exception.MaltChainedException;
    014    import org.maltparser.core.helper.SystemLogger;
    015    import org.maltparser.core.pool.ObjectPoolList;
    016    import org.maltparser.core.symbol.SymbolTable;
    017    import org.maltparser.core.symbol.SymbolTableHandler;
    018    import org.maltparser.core.syntaxgraph.ds2ps.LosslessMapping;
    019    import org.maltparser.core.syntaxgraph.edge.Edge;
    020    import org.maltparser.core.syntaxgraph.edge.GraphEdge;
    021    import org.maltparser.core.syntaxgraph.node.ComparableNode;
    022    import org.maltparser.core.syntaxgraph.node.DependencyNode;
    023    import org.maltparser.core.syntaxgraph.node.Node;
    024    import org.maltparser.core.syntaxgraph.node.NonTerminal;
    025    import org.maltparser.core.syntaxgraph.node.NonTerminalNode;
    026    import org.maltparser.core.syntaxgraph.node.PhraseStructureNode;
    027    import org.maltparser.core.syntaxgraph.node.Root;
    028    import org.maltparser.core.syntaxgraph.node.TokenNode;
    029    /**
    030    *
    031    *
    032    * @author Johan Hall
    033    */
    034    public class MappablePhraseStructureGraph extends Sentence implements DependencyStructure, PhraseStructure {
    035            private final ObjectPoolList<Edge> edgePool;
    036            private final SortedSet<Edge> graphEdges;
    037            private Root root;
    038            private boolean singleHeadedConstraint;
    039            private final SortedMap<Integer, NonTerminal> nonTerminalNodes;
    040            private final ObjectPoolList<NonTerminal> nonTerminalPool;
    041            private LosslessMapping mapping;
    042            private RootLabels rootLabels;
    043
    044            public MappablePhraseStructureGraph(SymbolTableHandler symbolTables) throws MaltChainedException {
    045                    super(symbolTables);
    046                    setSingleHeadedConstraint(true);
    047                    root = new Root();
    048                    root.setBelongsToGraph(this);
    049                    graphEdges = new TreeSet<Edge>();
    050                    edgePool = new ObjectPoolList<Edge>() {
    051                            protected Edge create() { return new GraphEdge(); }
    052                            public void resetObject(Edge o) throws MaltChainedException { o.clear(); }
    053                    };
    054
    055                    nonTerminalNodes = new TreeMap<Integer,NonTerminal>();
    056                    nonTerminalPool = new ObjectPoolList<NonTerminal>() {
    057                            protected NonTerminal create() throws MaltChainedException { return new NonTerminal(); }
    058                            public void resetObject(NonTerminal o) throws MaltChainedException { o.clear(); }
    059                    };
    060                    clear();
    061            }
    062
    063            public DependencyNode addDependencyNode() throws MaltChainedException {
    064                    return addTokenNode();
    065            }
    066
    067            public DependencyNode addDependencyNode(int index) throws MaltChainedException {
    068                    if (index == 0) {
    069                            return root;
    070                    }
    071                    return addTokenNode(index);
    072            }
    073
    074            public DependencyNode getDependencyNode(int index) throws MaltChainedException {
    075                    if (index == 0) {
    076                            return root;
    077                    }
    078                    return getTokenNode(index);
    079            }
    080
    081            public int nDependencyNode() {
    082                    return nTokenNode() + 1;
    083            }
    084
    085            public int getHighestDependencyNodeIndex() {
    086                    if (hasTokens()) {
    087                            return getHighestTokenIndex();
    088                    }
    089                    return 0;
    090            }
    091
    092            public Edge addDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
    093                    DependencyNode head = null;
    094                    DependencyNode dependent = null;
    095                    if (headIndex == 0) {
    096                            head = root;
    097                    } else if (headIndex > 0) {
    098                            head = getOrAddTerminalNode(headIndex);
    099                    }
    100
    101                    if (dependentIndex > 0) {
    102                            dependent = getOrAddTerminalNode(dependentIndex);
    103                    }
    104                    return addDependencyEdge(head, dependent);
    105            }
    106
    107            public Edge addDependencyEdge(DependencyNode head, DependencyNode dependent) throws MaltChainedException {
    108                    if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
    109                            throw new SyntaxGraphException("Head or dependent node is missing.");
    110                    } else if (!dependent.isRoot()) {
    111                            if (singleHeadedConstraint && dependent.hasHead()) {
    112                                    throw new SyntaxGraphException("The dependent already have a head. ");
    113                            }
    114                            DependencyNode hc = ((DependencyNode)head).findComponent();
    115                            DependencyNode dc = ((DependencyNode)dependent).findComponent();
    116                            if (hc != dc) {
    117                                    link(hc, dc);
    118                                    numberOfComponents--;
    119                            }
    120                            Edge e = edgePool.checkOut();
    121                            e.setBelongsToGraph(this);
    122                            e.setEdge((Node)head, (Node)dependent, Edge.DEPENDENCY_EDGE);
    123                            graphEdges.add(e);
    124                            return e;
    125                    } else {
    126                            throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
    127                    }
    128            }
    129
    130            public Edge moveDependencyEdge(int newHeadIndex, int dependentIndex) throws MaltChainedException {
    131                    DependencyNode newHead = null;
    132                    DependencyNode dependent = null;
    133                    if (newHeadIndex == 0) {
    134                            newHead = root;
    135                    } else if (newHeadIndex > 0) {
    136                            newHead = terminalNodes.get(newHeadIndex);
    137                    }
    138
    139                    if (dependentIndex > 0) {
    140                            dependent = terminalNodes.get(dependentIndex);
    141                    }
    142                    return moveDependencyEdge(newHead, dependent);
    143            }
    144
    145            public Edge moveDependencyEdge(DependencyNode newHead, DependencyNode dependent) throws MaltChainedException {
    146                    if (dependent == null || !dependent.hasHead() || newHead.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
    147                            return null;
    148                    }
    149                    Edge headEdge = dependent.getHeadEdge();
    150
    151                    LabelSet labels = null;
    152                    if (headEdge.isLabeled()) {
    153                            labels = checkOutNewLabelSet();
    154                            for (SymbolTable table : headEdge.getLabelTypes()) {
    155                                    labels.put(table, headEdge.getLabelCode(table));
    156                            }
    157                    }
    158                    headEdge.clear();
    159                    headEdge.setBelongsToGraph(this);
    160                    headEdge.setEdge((Node)newHead, (Node)dependent, Edge.DEPENDENCY_EDGE);
    161                    if (labels != null) {
    162                            headEdge.addLabel(labels);
    163                            labels.clear();
    164                            checkInLabelSet(labels);
    165                    }
    166                    return headEdge;
    167            }
    168
    169            public void removeDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
    170                    Node head = null;
    171                    Node dependent = null;
    172                    if (headIndex == 0) {
    173                            head = root;
    174                    } else if (headIndex > 0) {
    175                            head = terminalNodes.get(headIndex);
    176                    }
    177
    178                    if (dependentIndex > 0) {
    179                            dependent = terminalNodes.get(dependentIndex);
    180                    }
    181                    removeDependencyEdge(head, dependent);
    182            }
    183
    184            protected void removeDependencyEdge(Node head, Node dependent) throws MaltChainedException {
    185                    if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) {
    186                            throw new SyntaxGraphException("Head or dependent node is missing.");
    187                    } else if (!dependent.isRoot()) {
    188                            Iterator<Edge> ie = dependent.getIncomingEdgeIterator();
    189                            while (ie.hasNext()) {
    190                                    Edge e = ie.next();
    191                                    if (e.getSource() == head) {
    192                                            ie.remove();
    193                                            graphEdges.remove(e);
    194                                            edgePool.checkIn(e);
    195                                    }
    196                            }
    197                    } else {
    198                            throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
    199                    }
    200            }
    201
    202            public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
    203                    if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) {
    204                            throw new SyntaxGraphException("Head or dependent node is missing.");
    205                    } else if (!target.isRoot()) {
    206                            Edge e = edgePool.checkOut();
    207                            e.setBelongsToGraph(this);
    208                            e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE);
    209                            graphEdges.add(e);
    210                            return e;
    211                    }
    212                    return null;
    213            }
    214
    215            public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
    216                    if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) {
    217                            throw new SyntaxGraphException("Head or dependent node is missing.");
    218                    } else if (!target.isRoot()) {
    219                            Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator();
    220                            while (ie.hasNext()) {
    221                                    Edge e = ie.next();
    222                                    if (e.getSource() == source) {
    223                                            ie.remove();
    224                                            graphEdges.remove(e);
    225                                            edgePool.checkIn(e);
    226                                    }
    227                            }
    228                    }
    229            }
    230
    231            public boolean hasLabeledDependency(int index) throws MaltChainedException {
    232                    return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled());
    233            }
    234
    235            public boolean isConnected() {
    236                    return (numberOfComponents == 1);
    237            }
    238
    239            public boolean isProjective()  throws MaltChainedException {
    240                    for (int i : terminalNodes.keySet()) {
    241                            if (!terminalNodes.get(i).isProjective()) {
    242                                    return false;
    243                            }
    244                    }
    245                    return true;
    246            }
    247
    248            public boolean isTree() {
    249                    return isConnected() && isSingleHeaded();
    250            }
    251
    252            public boolean isSingleHeaded() {
    253                    for (int i : terminalNodes.keySet()) {
    254                            if (!terminalNodes.get(i).hasAtMostOneHead()) {
    255                                    return false;
    256                            }
    257                    }
    258                    return true;
    259            }
    260
    261            public boolean isSingleHeadedConstraint() {
    262                    return singleHeadedConstraint;
    263            }
    264
    265            public void setSingleHeadedConstraint(boolean singleHeadedConstraint) {
    266                    this.singleHeadedConstraint = singleHeadedConstraint;
    267            }
    268
    269            public int nNonProjectiveEdges() throws MaltChainedException {
    270                    int c = 0;
    271                    for (int i : terminalNodes.keySet()) {
    272                            if (!terminalNodes.get(i).isProjective()) {
    273                                    c++;
    274                            }
    275                    }
    276                    return c;
    277            }
    278
    279            public int nEdges() {
    280                    return graphEdges.size();
    281            }
    282
    283            public SortedSet<Edge> getEdges() {
    284                    return graphEdges;
    285            }
    286
    287            public SortedSet<Integer> getDependencyIndices() {
    288                    SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet());
    289                    indices.add(0);
    290                    return indices;
    291            }
    292
    293            protected DependencyNode link(DependencyNode x, DependencyNode y) {
    294                    if (x.getRank() > y.getRank()) {
    295                            y.setComponent(x);
    296                    } else {
    297                            x.setComponent(y);
    298                            if (x.getRank() == y.getRank()) {
    299                                    y.setRank(y.getRank()+1);
    300                            }
    301                            return y;
    302                    }
    303                    return x;
    304            }
    305
    306            public void linkAllTerminalsToRoot() throws MaltChainedException {
    307                    clear();
    308
    309                    for (int i : terminalNodes.keySet()) {
    310                            DependencyNode node = terminalNodes.get(i);
    311                            addDependencyEdge(root,node);
    312                    }
    313            }
    314
    315            public void linkAllTreesToRoot() throws MaltChainedException {
    316                    for (int i : terminalNodes.keySet()) {
    317                            if (!terminalNodes.get(i).hasHead()) {
    318                                    Edge e = addDependencyEdge(root,terminalNodes.get(i));
    319                                    mapping.updatePhraseStructureGraph(this, e, false);
    320                            }
    321                    }
    322            }
    323
    324            public LabelSet getDefaultRootEdgeLabels() throws MaltChainedException {
    325                    if (rootLabels == null) {
    326                            return null;
    327                    }
    328                    return rootLabels.getDefaultRootLabels();
    329            }
    330
    331            public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
    332                    if (rootLabels == null) {
    333                            return null;
    334                    }
    335                    return rootLabels.getDefaultRootLabelSymbol(table);
    336            }
    337
    338            public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException {
    339                    if (rootLabels == null) {
    340                            return -1;
    341                    }
    342                    return rootLabels.getDefaultRootLabelCode(table);
    343            }
    344
    345            public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException {
    346                    if (rootLabels == null) {
    347                            rootLabels = new RootLabels();
    348                    }
    349                    rootLabels.setDefaultRootLabel(table, defaultRootSymbol);
    350            }
    351
    352            public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException {
    353                    if (rootLabels == null) {
    354                            rootLabels = new RootLabels();
    355                    }
    356                    rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables);
    357            }
    358
    359            public void clear() throws MaltChainedException {
    360                    edgePool.checkInAll();
    361                    graphEdges.clear();
    362                    root.clear();
    363                    root.setBelongsToGraph(this);
    364                    nonTerminalPool.checkInAll();
    365                    nonTerminalNodes.clear();
    366                    if (mapping != null) {
    367                            mapping.clear();
    368                    }
    369                    super.clear();
    370
    371                    numberOfComponents++;
    372            }
    373
    374            public DependencyNode getDependencyRoot() {
    375                    return root;
    376            }
    377
    378            public PhraseStructureNode addTerminalNode() throws MaltChainedException {
    379                    return addTokenNode();
    380            }
    381
    382            public PhraseStructureNode addTerminalNode(int index) throws MaltChainedException {
    383                    return addTokenNode(index);
    384            }
    385
    386            public PhraseStructureNode getTerminalNode(int index) {
    387                    return getTokenNode(index);
    388            }
    389
    390            public int nTerminalNode() {
    391                    return nTokenNode();
    392            }
    393
    394            public PhraseStructureNode addNonTerminalNode(int index) throws MaltChainedException {
    395                    NonTerminal node = nonTerminalPool.checkOut();
    396                    node.setIndex(index);
    397                    node.setBelongsToGraph(this);
    398                    nonTerminalNodes.put(index,node);
    399                    return node;
    400            }
    401
    402            public PhraseStructureNode addNonTerminalNode() throws MaltChainedException {
    403                    int index = getHighestNonTerminalIndex();
    404                    if (index > 0) {
    405                            return addNonTerminalNode(index+1);
    406                    }
    407                    return addNonTerminalNode(1);
    408            }
    409
    410            public PhraseStructureNode getNonTerminalNode(int index) throws MaltChainedException {
    411                    return nonTerminalNodes.get(index);
    412            }
    413
    414            public int getHighestNonTerminalIndex() {
    415                    try {
    416                            return nonTerminalNodes.lastKey();
    417                    } catch (NoSuchElementException e) {
    418                            return 0;
    419                    }
    420            }
    421
    422            public Set<Integer> getNonTerminalIndices() {
    423                    return new TreeSet<Integer>(nonTerminalNodes.keySet());
    424            }
    425
    426            public boolean hasNonTerminals() {
    427                    return !nonTerminalNodes.isEmpty();
    428            }
    429
    430            public int nNonTerminals() {
    431                    return nonTerminalNodes.size();
    432            }
    433
    434            public PhraseStructureNode getPhraseStructureRoot() {
    435                    return root;
    436            }
    437
    438            public Edge addPhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
    439                    if (parent == null || child == null) {
    440                            throw new MaltChainedException("Parent or child node is missing in sentence "+getSentenceID());
    441                    } else if (parent.getBelongsToGraph() != this || child.getBelongsToGraph() != this) {
    442                            throw new MaltChainedException("Parent or child node is not a member of the graph in sentence "+getSentenceID());
    443                    } else if (parent == child) {
    444                            throw new MaltChainedException("It is not allowed to add a phrase structure edge connecting the same node in sentence "+getSentenceID());
    445                    } else if (parent instanceof NonTerminalNode && !child.isRoot()) {
    446                            Edge e = edgePool.checkOut();
    447                            e.setBelongsToGraph(this);
    448                            e.setEdge((Node)parent, (Node)child, Edge.PHRASE_STRUCTURE_EDGE);
    449                            graphEdges.add(e);
    450                            return e;
    451                    } else {
    452                            throw new MaltChainedException("Parent or child node is not of correct node type.");
    453                    }
    454            }
    455
    456            public void update(Observable  o, Object arg)  {
    457                    if (o instanceof Edge && mapping != null) {
    458                            try {
    459                                    mapping.update(this, (Edge)o, arg);
    460                            } catch (MaltChainedException ex) {
    461                                    if (SystemLogger.logger().isDebugEnabled()) {
    462                                            SystemLogger.logger().debug("",ex);
    463                                    } else {
    464                                            SystemLogger.logger().error(ex.getMessageChain());
    465                                    }
    466                                    System.exit(1);
    467                            }
    468                    }
    469            }
    470
    471            public LosslessMapping getMapping() {
    472                    return mapping;
    473            }
    474
    475            public void setMapping(LosslessMapping mapping) {
    476                    this.mapping = mapping;
    477            }
    478
    479            public void addLabel(Element element, String labelFunction, String label) throws MaltChainedException {
    480                    super.addLabel(element, labelFunction, label);
    481            }
    482
    483            public void removePhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
    484                    if (parent == null || child == null) {
    485                            throw new MaltChainedException("Parent or child node is missing.");
    486                    } else if (parent instanceof NonTerminalNode && !child.isRoot()) {
    487                            for (Edge e : graphEdges) {
    488                                    if (e.getSource() == parent && e.getTarget() == child) {
    489                                            e.clear();
    490                                            graphEdges.remove(e);
    491                                            if (e instanceof GraphEdge) {
    492                                                    edgePool.checkIn(e);
    493                                            }
    494                                    }
    495                            }
    496                    } else {
    497                            throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
    498                    }
    499            }
    500
    501            public boolean isContinuous() {
    502                    for (int index : nonTerminalNodes.keySet()) {
    503                            NonTerminalNode node = nonTerminalNodes.get(index);
    504
    505                            if (!node.isContinuous()) {
    506                                    return false;
    507                            }
    508                    }
    509                    return true;
    510            }
    511
    512            public boolean isContinuousExcludeTerminalsAttachToRoot() {
    513                    for (int index : nonTerminalNodes.keySet()) {
    514                            NonTerminalNode node = nonTerminalNodes.get(index);
    515                            if (!node.isContinuousExcludeTerminalsAttachToRoot()) {
    516                                    return false;
    517                            }
    518                    }
    519                    return true;
    520            }
    521
    522    //      public void makeContinuous() throws MaltChainedException {
    523    //              if (root != null) {
    524    //                      root.reArrangeChildrenAccordingToLeftAndRightProperDesendant();
    525    //              }
    526    //      }
    527
    528            public String toStringTerminalNode(TokenNode node) {
    529                    final StringBuilder sb = new StringBuilder();
    530                    final DependencyNode depnode = node;
    531
    532                    sb.append(node.toString().trim());
    533                    if (depnode.hasHead()) {
    534                            sb.append('\t');
    535                            try {
    536                                    sb.append(depnode.getHead().getIndex());
    537                                    sb.append('\t');
    538                                    sb.append(depnode.getHeadEdge().toString());
    539                            } catch (MaltChainedException e) {
    540                                    System.err.println(e);
    541                            }
    542                    }
    543                    sb.append('\n');
    544
    545                    return sb.toString();
    546            }
    547
    548            public String toStringNonTerminalNode(NonTerminalNode node) {
    549                    final StringBuilder sb = new StringBuilder();
    550
    551                    sb.append(node.toString().trim());
    552                    sb.append('\n');
    553                    Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator();
    554                    while (ie.hasNext()) {
    555                            Edge e = ie.next();
    556                            if (e.getTarget() instanceof TokenNode) {
    557                                    sb.append("   T");
    558                                    sb.append(e.getTarget().getIndex());
    559                            }
    560                            if (e.getTarget() instanceof NonTerminalNode) {
    561                                    sb.append("   N");
    562                                    sb.append(e.getTarget().getIndex());
    563                            }
    564                            sb.append('\t');
    565                            sb.append(e.toString());
    566                            sb.append('\n');
    567                    }
    568                    return sb.toString();
    569            }
    570
    571            public String toString() {
    572                    StringBuilder sb = new StringBuilder();
    573                    for (int index : terminalNodes.keySet()) {
    574                            sb.append(toStringTerminalNode(terminalNodes.get(index)));
    575                    }
    576                    sb.append('\n');
    577                    sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot()));
    578                    for (int index : nonTerminalNodes.keySet()) {
    579                            sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index)));
    580                    }
    581                    return sb.toString();
    582            }
    583    }