001    package org.maltparser.core.syntaxgraph.node;
002    
003    import java.util.NoSuchElementException;
004    import java.util.SortedSet;
005    import java.util.TreeSet;
006    
007    import org.maltparser.core.exception.MaltChainedException;
008    import org.maltparser.core.helper.SystemLogger;
009    import org.maltparser.core.symbol.SymbolTable;
010    import org.maltparser.core.syntaxgraph.LabelSet;
011    import org.maltparser.core.syntaxgraph.PhraseStructure;
012    import org.maltparser.core.syntaxgraph.SyntaxGraphException;
013    import org.maltparser.core.syntaxgraph.TokenStructure;
014    import org.maltparser.core.syntaxgraph.edge.Edge;
015    import org.maltparser.core.syntaxgraph.headrules.Direction;
016    import org.maltparser.core.syntaxgraph.headrules.HeadRules;
017    
018    public class NonTerminal extends GraphNode implements PhraseStructureNode, NonTerminalNode {
019            public final static int INDEX_OFFSET = 10000000;
020            protected final SortedSet<PhraseStructureNode> children;
021            protected PhraseStructureNode parent;
022            protected int index;
023            
024            public NonTerminal() throws MaltChainedException {
025                    super();
026                    index = -1;
027                    children = new TreeSet<PhraseStructureNode>();
028            }
029            
030            public void addIncomingEdge(Edge in) throws MaltChainedException {
031                    super.addIncomingEdge(in);
032                    if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
033                            parent = (PhraseStructureNode)in.getSource();
034                    }
035            }
036            
037            public void removeIncomingEdge(Edge in) throws MaltChainedException {
038                    super.removeIncomingEdge(in);
039                    if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
040                            if (in.getSource() == parent) {
041                                    this.parent = null;
042                            }
043                    }
044            }
045            
046            public void addOutgoingEdge(Edge out) throws MaltChainedException {
047                    super.addOutgoingEdge(out);
048                    if (out.getType() == Edge.PHRASE_STRUCTURE_EDGE && out.getTarget() instanceof PhraseStructureNode) {
049                            children.add((PhraseStructureNode)out.getTarget());
050    //                      boolean notSorted = true;
051    //                      PhraseStructureNode prev = children.first();
052    //                      for (PhraseStructureNode node : children) {
053    //                              if (prev != node) {
054    //                                      if (node.compareTo(prev) == -1) {
055    //                                              notSorted = false;
056    //                                              System.out.println("NS");
057    //                                              break;
058    //                                      }
059    //                              } 
060    //                              prev = node;
061    //                      }
062    //                      if (notSorted == false) {
063    //                              SortedSet<PhraseStructureNode> tmp = new TreeSet<PhraseStructureNode>(children);
064    //                              children.clear();
065    //                              for (PhraseStructureNode node : tmp) {
066    //                                      children.add(node);
067    //                              }
068    //                      }
069                    }
070            }
071            
072            public void removeOutgoingEdge(Edge out) throws MaltChainedException {
073                    super.removeOutgoingEdge(out);
074                    if (out.getType() == Edge.PHRASE_STRUCTURE_EDGE && out.getTarget() instanceof PhraseStructureNode) {
075                            children.remove(out.getTarget());
076                    }
077            }
078            
079            public PhraseStructureNode getParent() {
080                    return parent;
081            }
082            
083            public Edge getParentEdge() throws MaltChainedException {
084                    for (Edge e : incomingEdges) {
085                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
086                                    return e;
087                            }
088                    }
089                    return null;
090            }
091            
092            public String getParentEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
093                    for (Edge e : incomingEdges) {
094                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
095                                    return e.getLabelSymbol(table);
096                            }
097                    }
098                    return null;
099            }
100    
101            public int getParentEdgeLabelCode(SymbolTable table) throws MaltChainedException {
102                    for (Edge e : incomingEdges) {
103                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
104                                    return e.getLabelCode(table);
105                            }
106                    }
107                    return -1;
108            }
109            
110            public boolean hasParentEdgeLabel(SymbolTable table) throws MaltChainedException {
111                    for (Edge e : incomingEdges) {
112                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
113                                    return e.hasLabel(table);
114                            }
115                    }
116                    return false;
117            }
118            
119            public int getHeight() {
120                    int max = -1;
121                    for (PhraseStructureNode node : children) {
122                            if (node instanceof Token) {
123                                    if (max < 0) {
124                                            max = 0;
125                                    }
126                            } else {
127                                    int nodeheight = ((NonTerminalNode)node).getHeight();
128                                    if (max < nodeheight) {
129                                            max = nodeheight;
130                                    }
131                            }
132                    }
133                    return max + 1;
134            }
135            
136            public SortedSet<PhraseStructureNode> getChildren() {
137                    return new TreeSet<PhraseStructureNode>(children);
138            }
139    
140            public PhraseStructureNode getChild(int index) {
141                    if (index >= 0 && index < children.size()) {
142                            int i = 0;
143                            for (PhraseStructureNode node : children) {
144                                    if (i == index) {
145                                            return node;
146                                    }
147                                    i++;
148                            }
149    //                      return children.toArray(new PhraseStructureNode[children.size()])[index];
150                    }
151                    return null;
152            }
153            
154            public PhraseStructureNode getLeftChild() {
155                    for (PhraseStructureNode node : children) {
156                            return node;
157                    }
158                    return null;
159            }
160            
161            public PhraseStructureNode getRightChild() {
162                    int n = children.size();
163                    int i = 1;
164                    for (PhraseStructureNode node : children) {
165                            if (i == n) {
166                                    return node;
167                            }
168                            i++;
169                    }
170                    return null;
171            }
172            
173            public int nChildren() {
174                    return children.size();
175            }
176            
177            public boolean hasNonTerminalChildren() {
178                    for (PhraseStructureNode node : children) {
179                            if (node instanceof NonTerminal) {
180                                    return true;
181                            }
182                    }
183                    return false;
184            }
185            
186            public boolean hasTerminalChildren() {
187                    for (PhraseStructureNode node : children) {
188                            if (node instanceof Token) {
189                                    return true;
190                            }
191                    }
192                    return false;
193            }
194            
195            public TokenNode getLexicalHead(HeadRules headRules) throws MaltChainedException {
196                    return identifyHead(headRules);
197            }
198    
199            public PhraseStructureNode getHeadChild(HeadRules headRules) throws MaltChainedException {
200                    return identifyHeadChild(headRules);
201            }
202            
203            public TokenNode getLexicalHead() throws MaltChainedException {
204                    return identifyHead(null);
205            }
206    
207            public PhraseStructureNode getHeadChild() throws MaltChainedException {
208                    return identifyHeadChild(null);
209            }
210            
211            private PhraseStructureNode identifyHeadChild(HeadRules headRules) throws MaltChainedException {
212                    PhraseStructureNode headChild = (headRules == null)?null:headRules.getHeadChild(this);
213                    if (headChild == null) {
214                            Direction direction = (headRules == null)?Direction.LEFT:headRules.getDefaultDirection(this);
215                            if (direction == Direction.LEFT) {
216                                    if ((headChild = leftmostTerminalChild()) == null) {
217                                            headChild = leftmostNonTerminalChild();
218                                    }
219                            } else {
220                                    if ((headChild = rightmostTerminalChild()) == null) {
221                                            headChild = rightmostNonTerminalChild();
222                                    }
223                            }
224                    }
225                    return headChild;
226            }
227            
228            public TokenNode identifyHead(HeadRules headRules) throws MaltChainedException {
229                    PhraseStructureNode headChild = identifyHeadChild(headRules);
230                    TokenNode lexicalHead = null;
231                    if (headChild instanceof NonTerminalNode) {
232                            lexicalHead = ((NonTerminalNode)headChild).identifyHead(headRules);
233                    } else if (headChild instanceof TokenNode) {
234                            lexicalHead = (TokenNode)headChild;
235                    }
236                    for (PhraseStructureNode node : children) {
237                            if (node != headChild && node instanceof NonTerminalNode) {
238                                    ((NonTerminalNode)node).identifyHead(headRules);
239                            }
240                    }
241                    return lexicalHead;
242            }
243            
244            public int getIndex() {
245                    return index;
246            }
247            
248            public int getCompareToIndex() {
249                    return index + INDEX_OFFSET;
250            }
251            
252            private PhraseStructureNode leftmostTerminalChild() {
253                    for (PhraseStructureNode node : children) {
254                            if (node instanceof TokenNode) {
255                                    return node;
256                            }
257                    }
258                    return null;
259            }
260            
261            private PhraseStructureNode leftmostNonTerminalChild() {
262                    for (PhraseStructureNode node : children) {
263                            if (node instanceof NonTerminalNode) {
264                                    return node;
265                            }
266                    }
267                    return null;
268            }
269            
270            private PhraseStructureNode rightmostTerminalChild() {
271                    try {
272                            if (children.last() instanceof TokenNode) {
273                                    return children.last();
274                            }
275                    } catch (NoSuchElementException e) { }
276                    
277                    PhraseStructureNode candidate = null;
278                    for (PhraseStructureNode node : children) {
279                            if (node instanceof TokenNode) {
280                                    candidate = node;
281                            }
282                    }
283                    return candidate;
284            }
285            
286            private PhraseStructureNode rightmostNonTerminalChild() {
287                    try {
288                            if (children.last() instanceof NonTerminalNode) {
289                                    return children.last();
290                            }
291                    } catch (NoSuchElementException e) { }
292                    
293                    PhraseStructureNode candidate = null;
294                    for (PhraseStructureNode node : children) {
295                            if (node instanceof NonTerminalNode) {
296                                    candidate = node;
297                            }
298                    }
299                    return candidate;
300            }
301            
302    //      protected void getPhraseDominationSet(SortedSet<PhraseStructureNode> dominationSet) {
303    //              for (PhraseStructureNode node : children) {
304    //                      if (node instanceof TerminalNode) {
305    //                              dominationSet.add(node);
306    //                      } else {
307    //                              ((NonTerminal)node).getPhraseDominationSet(dominationSet);
308    //                      }
309    //              }
310    //      }
311    //      
312    //      private SortedSet<PhraseStructureNode> getPhraseDominationSet() {
313    //              SortedSet<PhraseStructureNode> dominationSet = new TreeSet<PhraseStructureNode>();
314    //              getPhraseDominationSet(dominationSet);
315    //              return dominationSet;
316    //      }
317            
318    
319            
320            public boolean isContinuous() {
321                    int lcorner = getLeftmostProperDescendant().getIndex();
322                    int rcorner = getRightmostProperDescendant().getIndex();
323                    
324                    if (lcorner == rcorner) {
325                            return true;
326                    }
327                    
328                    TokenNode terminal = ((TokenStructure)getBelongsToGraph()).getTokenNode(lcorner);
329                    while (terminal.getIndex() != rcorner) {
330                            PhraseStructureNode tmp = terminal.getParent();
331                            while (true) {
332                                    if (tmp == this) {
333                                            break;
334                                    }
335                                    if (tmp == null) {
336                                            return false;
337                                    }
338                                    tmp = tmp.getParent();
339                            }
340                            terminal = terminal.getSuccessor();
341                    }
342                    
343                    return true;
344            }
345    
346            public boolean isContinuousExcludeTerminalsAttachToRoot() {
347                    int lcorner = getLeftmostProperDescendant().getIndex();
348                    int rcorner = getRightmostProperDescendant().getIndex();
349                    
350                    if (lcorner == rcorner) {
351                            return true;
352                    }
353                    
354                    TokenNode terminal = ((TokenStructure)getBelongsToGraph()).getTokenNode(lcorner);
355                    while (terminal.getIndex() != rcorner) {
356                            if (terminal.getParent() != null && terminal.getParent().isRoot()) {
357                                    terminal = terminal.getSuccessor();
358                                    continue;
359                            }
360                            PhraseStructureNode tmp = terminal.getParent();
361                            while (true) {
362                                    if (tmp == this) {
363                                            break;
364                                    }
365                                    if (tmp == null) {
366                                            return false;
367                                    }
368                                    tmp = tmp.getParent();
369                            }
370                            terminal = terminal.getSuccessor();
371                    }
372                    return true;
373            }
374            
375            @Override
376            public boolean isRoot() {
377                    return false;
378            }
379    
380            
381            public ComparableNode getLeftmostProperDescendant() {
382                    NonTerminalNode node = this;
383                    PhraseStructureNode candidate = null;
384                    while (node != null) {
385                            candidate = node.getLeftChild();
386                            if (candidate == null || candidate instanceof TokenNode) {
387                                    return candidate;
388                            }
389                            node = (NonTerminalNode)candidate;
390                    }
391                    return null;
392            }
393            
394            public ComparableNode getRightmostProperDescendant() {
395                    NonTerminalNode node = this;
396                    PhraseStructureNode candidate = null;
397                    while (node != null) {
398                            candidate = node.getRightChild();
399                            if (candidate == null || candidate instanceof TokenNode) {
400                                    return candidate;
401                            }
402                            node = (NonTerminalNode)candidate;
403                    }
404                    return null;
405            }
406            
407            public ComparableNode getLeftmostDescendant() throws MaltChainedException {
408                    return getLeftmostProperDescendant();
409            }
410            
411            public ComparableNode getRightmostDescendant() throws MaltChainedException {
412                    return getRightmostProperDescendant();
413            }
414            
415    //      public void reArrangeChildrenAccordingToLeftAndRightProperDesendant() throws MaltChainedException {
416    //              int i = 0;
417    //              int leftMostCorner = -1;
418    //              int leftMostCornerChildIndex = -1;
419    //              while (i < children.size()) {        
420    //                      if (leftMostCorner == -1) {
421    //                              leftMostCorner = getChild(i).getLeftmostProperDescendantIndex();
422    //                              leftMostCornerChildIndex = i;
423    //                      } else if (getChild(i) instanceof NonTerminal && getChild(i).getLeftmostProperDescendantIndex() < leftMostCorner) {
424    //                              NonTerminalNode child = (NonTerminal)getChild(i);
425    //                              PhraseStructureNode leftMostCornerChild = getChild(leftMostCornerChildIndex);
426    //                              if (leftMostCornerChild.getParent() != null) {
427    //                                      LabelSet labelSet = leftMostCornerChild.getParentEdge().getLabelSet();
428    //                                      ((PhraseStructure)getBelongsToGraph()).removePhraseStructureEdge(this, leftMostCornerChild);
429    //                                      Edge e = ((PhraseStructure)getBelongsToGraph()).addPhraseStructureEdge(child, leftMostCornerChild);
430    //                                      e.addLabel(labelSet);
431    //                              }
432    //                              child.reArrangeChildrenAccordingToLeftAndRightProperDesendant();
433    //                              i = -1;
434    //                              leftMostCorner = -1;
435    //                              leftMostCornerChildIndex = -1;
436    //                      } else {
437    //                              leftMostCorner = getChild(i).getLeftmostProperDescendantIndex();
438    //                              leftMostCornerChildIndex = i;
439    //                      }
440    //                      i++;
441    //              }
442    //
443    //              for (int j = 0, n=children.size(); j < n; j++) {
444    //                      if (getChild(j) instanceof NonTerminalNode) {
445    //                              ((NonTerminalNode)getChild(j)).reArrangeChildrenAccordingToLeftAndRightProperDesendant();
446    //                      }
447    //              }
448    //      }
449            
450            @Override
451            public void setIndex(int index) throws MaltChainedException {
452                    if (index > 0) { 
453                            this.index = index; //INDEX_OFFSET+index;
454                    } else {
455                            throw new SyntaxGraphException("The index must be a positive index");
456                    }
457                    
458            }
459    
460            public void clear() throws MaltChainedException {
461                    super.clear();
462                    children.clear();
463                    parent = null;
464                    index = -1;
465            }
466            
467            @Override
468            public int compareTo(ComparableNode o) {
469                    final int BEFORE = -1;
470                final int EQUAL = 0;
471                final int AFTER = 1;
472                if ( this == o ) return EQUAL;
473                try {
474                        final int thisLCorner = this.getLeftmostProperDescendantIndex();
475                        final int thatLCorner = (o instanceof TokenNode)?o.getCompareToIndex():o.getLeftmostProperDescendantIndex();
476                        final int thisRCorner = this.getRightmostProperDescendantIndex();
477                        final int thatRCorner = (o instanceof TokenNode)?o.getCompareToIndex():o.getRightmostProperDescendantIndex();
478    
479    //                  if (thisLCorner == -1 || thatLCorner == -1) {
480    //                          if (thisRCorner < thatRCorner) return BEFORE;
481    //                          if (thisRCorner > thatRCorner) return AFTER;
482    //                  }
483    //                  if (thisRCorner == -1 || thatRCorner == -1) {
484    //                          if (thisLCorner < thatLCorner) return BEFORE;
485    //                          if (thisLCorner > thatLCorner) return AFTER;
486    //                  }
487                        
488                        if (thisLCorner != -1 && thatLCorner != -1 && thisRCorner != -1 && thatRCorner != -1) {
489                                if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
490                                if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
491                                if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
492                                if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;     
493                        } else {
494                                if (thisLCorner != -1 && thatLCorner != -1) {
495                                        if (thisLCorner < thatLCorner) return BEFORE;
496                                        if (thisLCorner > thatLCorner) return AFTER;
497                                }
498                                if (thisRCorner != -1 && thatRCorner != -1) {
499                                        if (thisRCorner < thatRCorner) return BEFORE;
500                                        if (thisRCorner > thatRCorner) return AFTER;
501                                }
502                        }
503    
504                    
505                    
506    //                  final int thisLCorner = this.getLeftmostDescendantIndex();
507    //                  final int thatLCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getLeftmostDescendantIndex();
508    //                  final int thisRCorner = this.getRightmostDescendantIndex();
509    //                  final int thatRCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getRightmostDescendantIndex();
510    //
511    //                  if (thisLCorner == -1 || thatLCorner == -1) {
512    //                          if (thisRCorner < thatRCorner) return BEFORE;
513    //                          if (thisRCorner > thatRCorner) return AFTER;
514    //                  }
515    //                  if (thisRCorner == -1 || thatRCorner == -1) {
516    //                          if (thisLCorner < thatLCorner) return BEFORE;
517    //                          if (thisLCorner > thatLCorner) return AFTER;
518    //                  }
519    //                  if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
520    //                  if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
521    //                  if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
522    //                  if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
523                    
524    //                  System.out.println(thisLCorner + " " + thatLCorner + " " +thisRCorner + " " + thatRCorner);
525                    
526    //                  int thisCorner = this.getLeftmostDescendantIndex();
527    //                  int thatCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getLeftmostDescendantIndex();
528    //                  if (thisCorner != -1 && thatCorner != -1) {
529    //                          if (thisCorner < thatCorner) return BEFORE;
530    //                          if (thisCorner > thatCorner) return AFTER;
531    //                  }
532    //                  thisCorner = this.getRightmostDescendantIndex();
533    //                  thatCorner = (o instanceof TerminalNode)?o.getCompareToIndex():o.getRightmostDescendantIndex();
534    //                  if (thisCorner != -1 && thatCorner != -1) {
535    //                          if (thisCorner < thatCorner) return BEFORE;
536    //                          if (thisCorner > thatCorner) return AFTER;
537    //                  }
538            } catch (MaltChainedException e) {
539                            if (SystemLogger.logger().isDebugEnabled()) {
540                                    SystemLogger.logger().debug("",e);
541                            } else {
542                                    SystemLogger.logger().error(e.getMessageChain());
543                            }
544                            System.exit(1);
545            }
546                if (this.getCompareToIndex() < o.getCompareToIndex()) return BEFORE;
547                if (this.getCompareToIndex() > o.getCompareToIndex()) return AFTER;
548                    return super.compareTo(o);
549            }
550            
551            public boolean equals(Object obj) {
552                    if (this == obj) return true;
553                    if (!(obj instanceof NonTerminal)) return false;
554                    return super.equals(obj);
555            }
556            
557            public int hashCode() {
558                    return 31 * 7 + super.hashCode();
559            }
560            
561            public String toString() {
562                    final StringBuilder sb = new StringBuilder();
563                    sb.append(getIndex());
564                    sb.append('\t');
565                    if (getLabelTypes() != null) {
566                            for (SymbolTable table : getLabelTypes()) {
567                                    try {
568                                            sb.append(getLabelSymbol(table));
569                                    } catch (MaltChainedException e) {
570                                            System.err.println("Print error : "+e.getMessageChain());
571                                    }
572                                    sb.append('\t');
573                            }
574                    }
575                    return sb.toString();
576            }
577            
578    }