Source code

001package org.maltparser.core.syntaxgraph.node;
002
003import java.util.NoSuchElementException;
004import java.util.SortedSet;
005import java.util.TreeSet;
006
007import org.maltparser.core.exception.MaltChainedException;
008import org.maltparser.core.helper.SystemLogger;
009import org.maltparser.core.symbol.SymbolTable;
010import org.maltparser.core.syntaxgraph.SyntaxGraphException;
011import org.maltparser.core.syntaxgraph.TokenStructure;
012import org.maltparser.core.syntaxgraph.edge.Edge;
013import org.maltparser.core.syntaxgraph.headrules.Direction;
014import org.maltparser.core.syntaxgraph.headrules.HeadRules;
015
016public 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.getTokenNodeSuccessor();
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.getTokenNodeSuccessor();
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.getTokenNodeSuccessor();
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
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}