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<Integer> getDependencyIndices() {
284                    SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet());
285                    indices.add(0);
286                    return indices;
287            }
288            
289            protected DependencyNode link(DependencyNode x, DependencyNode y) {
290                    if (x.getRank() > y.getRank()) {
291                            y.setComponent(x);
292                    } else {
293                            x.setComponent(y);
294                            if (x.getRank() == y.getRank()) {
295                                    y.setRank(y.getRank()+1);
296                            }
297                            return y;
298                    }
299                    return x;
300            }
301            
302            public void linkAllTerminalsToRoot() throws MaltChainedException {
303                    clear();
304    
305                    for (int i : terminalNodes.keySet()) {
306                            DependencyNode node = terminalNodes.get(i);
307                            addDependencyEdge(root,node);
308                    }
309            }
310            
311            public void linkAllTreesToRoot() throws MaltChainedException {
312                    for (int i : terminalNodes.keySet()) {
313                            if (!terminalNodes.get(i).hasHead()) {
314                                    Edge e = addDependencyEdge(root,terminalNodes.get(i));
315                                    mapping.updatePhraseStructureGraph(this, e, false);
316                            }
317                    }
318            }
319            
320            public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
321                    if (rootLabels == null) {
322                            return null;
323                    }
324                    return rootLabels.getDefaultRootLabelSymbol(table);
325            }
326            
327            public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException {
328                    if (rootLabels == null) {
329                            return -1;
330                    }
331                    return rootLabels.getDefaultRootLabelCode(table);
332            }
333            
334            public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException {
335                    if (rootLabels == null) {
336                            rootLabels = new RootLabels();
337                    }
338                    rootLabels.setDefaultRootLabel(table, defaultRootSymbol);
339            }
340            
341            public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException {
342                    if (rootLabels == null) {
343                            rootLabels = new RootLabels();
344                    }
345                    rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables);
346            }
347            
348            public void clear() throws MaltChainedException {
349                    edgePool.checkInAll();
350                    graphEdges.clear();
351                    root.clear();
352                    root.setBelongsToGraph(this);
353                    nonTerminalPool.checkInAll();
354                    nonTerminalNodes.clear();
355                    if (mapping != null) {
356                            mapping.clear();        
357                    }
358                    super.clear();
359                    
360                    numberOfComponents++;
361            }
362            
363            public DependencyNode getDependencyRoot() {
364                    return root;
365            }
366            
367            public PhraseStructureNode addTerminalNode() throws MaltChainedException {
368                    return addTokenNode();
369            }
370            
371            public PhraseStructureNode addTerminalNode(int index) throws MaltChainedException {
372                    return addTokenNode(index);
373            }
374            
375            public PhraseStructureNode getTerminalNode(int index) {
376                    return getTokenNode(index);
377            }
378            
379            public int nTerminalNode() {
380                    return nTokenNode();
381            }
382            
383            public PhraseStructureNode addNonTerminalNode(int index) throws MaltChainedException {
384                    NonTerminal node = nonTerminalPool.checkOut();
385                    node.setIndex(index);
386                    node.setBelongsToGraph(this);
387                    nonTerminalNodes.put(index,node);
388                    return node;
389            }
390            
391            public PhraseStructureNode addNonTerminalNode() throws MaltChainedException {
392                    int index = getHighestNonTerminalIndex();
393                    if (index > 0) {
394                            return addNonTerminalNode(index+1);
395                    }
396                    return addNonTerminalNode(1);
397            }
398            
399            public PhraseStructureNode getNonTerminalNode(int index) throws MaltChainedException {
400                    return nonTerminalNodes.get(index);
401            }
402            
403            public int getHighestNonTerminalIndex() {
404                    try {
405                            return nonTerminalNodes.lastKey();
406                    } catch (NoSuchElementException e) {
407                            return 0;
408                    }
409            }
410            
411            public Set<Integer> getNonTerminalIndices() {
412                    return new TreeSet<Integer>(nonTerminalNodes.keySet());
413            }
414            
415            public boolean hasNonTerminals() {
416                    return !nonTerminalNodes.isEmpty();
417            }
418            
419            public int nNonTerminals() {
420                    return nonTerminalNodes.size();
421            }
422            
423            public PhraseStructureNode getPhraseStructureRoot() {
424                    return root;
425            }
426            
427            public Edge addPhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
428                    if (parent == null || child == null) {
429                            throw new MaltChainedException("Parent or child node is missing in sentence "+getSentenceID());
430                    } else if (parent.getBelongsToGraph() != this || child.getBelongsToGraph() != this) {
431                            throw new MaltChainedException("Parent or child node is not a member of the graph in sentence "+getSentenceID());
432                    } else if (parent == child) {
433                            throw new MaltChainedException("It is not allowed to add a phrase structure edge connecting the same node in sentence "+getSentenceID());
434                    } else if (parent instanceof NonTerminalNode && !child.isRoot()) {
435                            Edge e = edgePool.checkOut();
436                            e.setBelongsToGraph(this);
437                            e.setEdge((Node)parent, (Node)child, Edge.PHRASE_STRUCTURE_EDGE);
438                            graphEdges.add(e);
439                            return e;
440                    } else {
441                            throw new MaltChainedException("Parent or child node is not of correct node type.");
442                    }
443            }
444            
445            public void update(Observable  o, Object arg)  {
446                    if (o instanceof Edge && mapping != null) {
447                            try {
448                                    mapping.update(this, (Edge)o, arg);
449                            } catch (MaltChainedException ex) {
450                                    if (SystemLogger.logger().isDebugEnabled()) {
451                                            SystemLogger.logger().debug("",ex);
452                                    } else {
453                                            SystemLogger.logger().error(ex.getMessageChain());
454                                    }
455                                    System.exit(1);
456                            }
457                    }
458            }
459    
460            public LosslessMapping getMapping() {
461                    return mapping;
462            }
463    
464            public void setMapping(LosslessMapping mapping) {
465                    this.mapping = mapping;
466            }
467    
468            public void addLabel(Element element, String labelFunction, String label) throws MaltChainedException {
469                    super.addLabel(element, labelFunction, label);
470            }
471            
472            public void removePhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException {
473                    if (parent == null || child == null) {
474                            throw new MaltChainedException("Parent or child node is missing.");
475                    } else if (parent instanceof NonTerminalNode && !child.isRoot()) {
476                            for (Edge e : graphEdges) {
477                                    if (e.getSource() == parent && e.getTarget() == child) {
478                                            e.clear();
479                                            graphEdges.remove(e);
480                                            if (e instanceof GraphEdge) {
481                                                    edgePool.checkIn(e);
482                                            }
483                                    }
484                            }
485                    } else {
486                            throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
487                    }
488            }
489            
490            public boolean isContinuous() {
491                    for (int index : nonTerminalNodes.keySet()) {
492                            NonTerminalNode node = nonTerminalNodes.get(index);
493    
494                            if (!node.isContinuous()) {
495                                    return false;
496                            }
497                    }
498                    return true;
499            }
500            
501            public boolean isContinuousExcludeTerminalsAttachToRoot() {
502                    for (int index : nonTerminalNodes.keySet()) {
503                            NonTerminalNode node = nonTerminalNodes.get(index);
504                            if (!node.isContinuousExcludeTerminalsAttachToRoot()) {
505                                    return false;
506                            }
507                    }
508                    return true;
509            }
510            
511    //      public void makeContinuous() throws MaltChainedException {
512    //              if (root != null) {
513    //                      root.reArrangeChildrenAccordingToLeftAndRightProperDesendant();
514    //              }
515    //      }
516            
517            public String toStringTerminalNode(TokenNode node) {
518                    final StringBuilder sb = new StringBuilder();
519                    final DependencyNode depnode = node;
520    
521                    sb.append(node.toString().trim());
522                    if (depnode.hasHead()) {
523                            sb.append('\t');
524                            try {
525                                    sb.append(depnode.getHead().getIndex());
526                                    sb.append('\t');
527                                    sb.append(depnode.getHeadEdge().toString());
528                            } catch (MaltChainedException e) {
529                                    System.out.println(e);
530                            }
531                    }
532                    sb.append('\n');
533    
534                    return sb.toString();
535            }
536            
537            public String toStringNonTerminalNode(NonTerminalNode node) {
538                    final StringBuilder sb = new StringBuilder();
539    
540                    sb.append(node.toString().trim());
541                    sb.append('\n');
542                    Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator();
543                    while (ie.hasNext()) {
544                            Edge e = ie.next();
545                            if (e.getTarget() instanceof TokenNode) {
546                                    sb.append("   T");
547                                    sb.append(e.getTarget().getIndex());
548                            }
549                            if (e.getTarget() instanceof NonTerminalNode) {
550                                    sb.append("   N");
551                                    sb.append(e.getTarget().getIndex());
552                            }
553                            sb.append('\t');
554                            sb.append(e.toString());
555                            sb.append('\n');
556                    }
557                    return sb.toString();
558            }
559            
560            public String toString() {
561                    StringBuilder sb = new StringBuilder();
562                    for (int index : terminalNodes.keySet()) {
563                            sb.append(toStringTerminalNode(terminalNodes.get(index)));
564                    }
565                    sb.append('\n');
566                    sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot()));
567                    for (int index : nonTerminalNodes.keySet()) {
568                            sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index)));
569                    }
570                    return sb.toString();
571            }
572    }