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