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.out.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    }