001    package org.maltparser.core.syntaxgraph.node;
002    
003    import java.util.NoSuchElementException;
004    import java.util.Set;
005    import java.util.SortedSet;
006    import java.util.TreeSet;
007    
008    import org.maltparser.core.exception.MaltChainedException;
009    import org.maltparser.core.helper.SystemLogger;
010    import org.maltparser.core.symbol.SymbolTable;
011    import org.maltparser.core.syntaxgraph.LabelSet;
012    import org.maltparser.core.syntaxgraph.SyntaxGraphException;
013    import org.maltparser.core.syntaxgraph.edge.Edge;
014    
015    
016    public class Token extends GraphNode implements TokenNode, DependencyNode, PhraseStructureNode {
017            /**
018             * the previous terminal node in the linear precedence
019             */
020            protected TokenNode predecessor = null;
021            /**
022             * the next terminal node in the linear precedence
023             */
024            protected TokenNode successor = null;
025    
026            /**
027             * a reference to a node where the node is part of a component. If the node is unconnected it will reference to it self. 
028             */
029            protected DependencyNode component;
030            protected int rank;
031            
032            protected int index;
033            
034            protected PhraseStructureNode parent;
035            protected final SortedSet<DependencyNode> heads;
036            protected final SortedSet<DependencyNode> leftDependents;
037            protected final SortedSet<DependencyNode> rightDependents;
038            
039            
040            public Token() throws MaltChainedException { 
041                    parent = null;
042                    heads = new TreeSet<DependencyNode>();
043                    leftDependents = new TreeSet<DependencyNode>();
044                    rightDependents = new TreeSet<DependencyNode>();
045                    clear();
046            }
047            
048            /**
049             * Sets the predecessor terminal node in the linear order of the terminal nodes.
050             * 
051             * @param predecessor the predecessor terminal node
052             */
053            public void setPredecessor(TokenNode predecessor) {
054                    this.predecessor = predecessor;
055            }
056            
057            /**
058             * Sets the predecessor terminal node in the linear order of the terminal nodes.
059             * 
060             * @param successor the successor terminal node
061             */
062            public void setSuccessor(TokenNode successor) {
063                    this.successor = successor;
064            }
065            
066            /**
067             * Returns the predecessor terminal node in the linear order of the terminal nodes.
068             * 
069             * @return the predecessor terminal node in the linear order of the terminal nodes.
070             */
071            public TokenNode getPredecessor() {
072                    return predecessor;
073            }
074    
075            /**
076             * Returns the successor terminal node in the linear order of the terminal nodes.
077             * 
078             * @return the successor terminal node in the linear order of the terminal nodes.
079             */
080            public TokenNode getSuccessor() {
081                    return successor;
082            }
083            
084            public int getRank() {
085                    return rank;
086            }
087            
088            public void setRank(int r) {
089                    this.rank = r;
090            }
091            
092            public DependencyNode findComponent() {
093                    return findComponent(this);
094            }
095            
096            private DependencyNode findComponent(DependencyNode x) {        
097                    if (x != x.getComponent()) {
098                            x.setComponent(findComponent(x.getComponent()));
099                    }
100                    return x.getComponent();
101            }
102            
103            public DependencyNode getComponent() {
104                    return component;
105            }
106            
107            public void setComponent(DependencyNode x) {
108                    this.component = x;
109            }
110            
111            public void addIncomingEdge(Edge in) throws MaltChainedException {
112                    super.addIncomingEdge(in);
113                    if (in.getSource() != null) {
114                            if (in.getType() == Edge.DEPENDENCY_EDGE && in.getSource() instanceof DependencyNode) {
115                                    if (heads.size() >= 1) {
116                                            heads.add((DependencyNode)in.getSource());
117                                    } else {
118                                            heads.add((DependencyNode)in.getSource());
119                                    }
120                            } else if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
121                                    parent = (PhraseStructureNode)in.getSource();
122                            }
123                    }
124            }
125            
126            public void removeIncomingEdge(Edge in) throws MaltChainedException {
127                    super.removeIncomingEdge(in);
128                    if (in.getSource() != null) {
129                            if (in.getType() == Edge.DEPENDENCY_EDGE && in.getSource() instanceof DependencyNode) {
130                                    heads.remove((DependencyNode)in.getSource());
131                            } else if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
132                                    if (in.getSource() == parent) {
133                                            this.parent = null;
134                                    }
135                            }
136                    }
137            }
138            
139            public void addOutgoingEdge(Edge out) throws MaltChainedException {
140                    super.addOutgoingEdge(out);
141                    if (out.getType() == Edge.DEPENDENCY_EDGE && out.getTarget() instanceof DependencyNode) {       
142                            final DependencyNode dependent = (DependencyNode)out.getTarget();
143                            if (compareTo(dependent) > 0) {
144                                    leftDependents.add((DependencyNode)dependent);
145                            } else if (compareTo(dependent) < 0) {
146                                    rightDependents.add((DependencyNode)dependent);
147                            }
148                    }
149            }
150            
151            public void removeOutgoingEdge(Edge out) throws MaltChainedException {
152                    super.removeOutgoingEdge(out);
153                    if (out.getType() == Edge.DEPENDENCY_EDGE && out.getTarget() instanceof DependencyNode) {
154                            final DependencyNode dependent = (DependencyNode)out.getTarget();
155                            if (compareTo(dependent) > 0) {
156                                    leftDependents.remove((DependencyNode)dependent);
157                            } else if (compareTo(dependent) < 0) {
158                                    rightDependents.remove((DependencyNode)dependent);
159                            }
160                    }
161            }
162            
163            public void setIndex(int index) throws MaltChainedException {
164                    if (index > 0) {
165                            this.index = index;
166                    } else {
167                            throw new SyntaxGraphException("A terminal node must have a positive integer value and not index "+index+". ");
168                    }
169            }
170            
171            public int getIndex() {
172                    return index;
173            }
174            
175            public int getCompareToIndex() {
176                    return index;
177            }
178            
179            public boolean isRoot() {
180                    return false;
181            }
182            
183            public ComparableNode getLeftmostProperDescendant() throws MaltChainedException {
184                    ComparableNode candidate = null;
185                    ComparableNode tmp = null;
186                    for (DependencyNode ldep : leftDependents) {
187                            if (candidate == null) {
188                                    candidate = ldep;
189                            } else if (ldep.getIndex() < candidate.getIndex() ) {
190                                    candidate = ldep;
191                            }
192                            tmp = ((Token)ldep).getLeftmostProperDescendant();
193                            if (tmp == null) {
194                                    continue;
195                            }
196                            if (candidate == null) {
197                                    candidate = tmp;
198                            } else if (tmp.getIndex() < candidate.getIndex() ) {
199                                    candidate = tmp;
200                            }
201                            if (candidate.getIndex() == 1) {
202                                    return candidate;
203                            }
204                    }
205                    for (DependencyNode rdep : rightDependents) {
206                            if (candidate == null) {
207                                    candidate = rdep;
208                            } else if (rdep.getIndex() < candidate.getIndex() ) {
209                                    candidate = rdep;
210                            }
211                            tmp = ((Token)rdep).getLeftmostProperDescendant();
212                            if (tmp == null) {
213                                    continue;
214                            }
215                            if (candidate == null) {
216                                    candidate = tmp;
217                            } else if (tmp.getIndex() < candidate.getIndex() ) {
218                                    candidate = tmp;
219                            }
220                            if (candidate.getIndex() == 1) {
221                                    return candidate;
222                            }
223                    }
224                    return candidate;
225            }
226            
227            public ComparableNode getRightmostProperDescendant() throws MaltChainedException {
228                    ComparableNode candidate = null;
229                    ComparableNode tmp = null;
230                    for (DependencyNode ldep : leftDependents) {
231                            if (candidate == null) {
232                                    candidate = ldep;
233                            } else if (ldep.getIndex() > candidate.getIndex() ) {
234                                    candidate = ldep;
235                            }
236                            tmp = ((Token)ldep).getRightmostProperDescendant();
237                            if (tmp == null) {
238                                    continue;
239                            }
240                            if (candidate == null) {
241                                    candidate = tmp;
242                            } else if (tmp.getIndex() > candidate.getIndex() ) {
243                                    candidate = tmp;
244                            }
245                    }
246                    for (DependencyNode rdep : rightDependents) {
247                            if (candidate == null) {
248                                    candidate = rdep;
249                            } else if (rdep.getIndex() > candidate.getIndex() ) {
250                                    candidate = rdep;
251                            }
252                            tmp = ((Token)rdep).getRightmostProperDescendant();
253                            if (tmp == null) {
254                                    continue;
255                            }
256                            if (candidate == null) {
257                                    candidate = tmp;
258                            } else if (tmp.getIndex() > candidate.getIndex() ) {
259                                    candidate = tmp;
260                            }
261                    }
262                    return candidate;
263            }
264            
265            public ComparableNode getLeftmostDescendant() throws MaltChainedException {
266                    ComparableNode candidate = this;
267                    ComparableNode tmp = null;
268                    for (DependencyNode ldep : leftDependents) {
269                            if (candidate == null) {
270                                    candidate = ldep;
271                            } else if (ldep.getIndex() < candidate.getIndex() ) {
272                                    candidate = ldep;
273                            }
274                            tmp = ((Token)ldep).getLeftmostDescendant();
275                            if (tmp == null) {
276                                    continue;
277                            }
278                            if (candidate == null) {
279                                    candidate = tmp;
280                            } else if (tmp.getIndex() < candidate.getIndex() ) {
281                                    candidate = tmp;
282                            }
283                            if (candidate.getIndex() == 1) {
284                                    return candidate;
285                            }
286                    }
287                    for (DependencyNode rdep : rightDependents) {
288                            if (candidate == null) {
289                                    candidate = rdep;
290                            } else if (rdep.getIndex() < candidate.getIndex() ) {
291                                    candidate = rdep;
292                            }
293                            tmp = ((Token)rdep).getLeftmostDescendant();
294                            if (tmp == null) {
295                                    continue;
296                            }
297                            if (candidate == null) {
298                                    candidate = tmp;
299                            } else if (tmp.getIndex() < candidate.getIndex() ) {
300                                    candidate = tmp;
301                            }
302                            if (candidate.getIndex() == 1) {
303                                    return candidate;
304                            }
305                    }
306                    return candidate;
307            }
308            
309            public ComparableNode getRightmostDescendant() throws MaltChainedException {
310                    ComparableNode candidate = this;
311                    ComparableNode tmp = null;
312                    for (DependencyNode ldep : leftDependents) {
313                            if (candidate == null) {
314                                    candidate = ldep;
315                            } else if (ldep.getIndex() > candidate.getIndex() ) {
316                                    candidate = ldep;
317                            }
318                            tmp = ((Token)ldep).getRightmostDescendant();
319                            if (tmp == null) {
320                                    continue;
321                            }
322                            if (candidate == null) {
323                                    candidate = tmp;
324                            } else if (tmp.getIndex() > candidate.getIndex() ) {
325                                    candidate = tmp;
326                            }
327                    }
328                    for (DependencyNode rdep : rightDependents) {
329                            if (candidate == null) {
330                                    candidate = rdep;
331                            } else if (rdep.getIndex() > candidate.getIndex() ) {
332                                    candidate = rdep;
333                            }
334                            tmp = ((Token)rdep).getRightmostDescendant();
335                            if (tmp == null) {
336                                    continue;
337                            }
338                            if (candidate == null) {
339                                    candidate = tmp;
340                            } else if (tmp.getIndex() > candidate.getIndex() ) {
341                                    candidate = tmp;
342                            }
343                    }
344                    return candidate;
345            }
346            
347            public PhraseStructureNode getParent() {
348                    return parent;
349            }
350    
351            public Edge getParentEdge() throws MaltChainedException {
352                    for (Edge e : incomingEdges) {
353                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
354                                    return e;
355                            }
356                    }
357                    return null;
358            }
359            
360            public String getParentEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
361                    for (Edge e : incomingEdges) {
362                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
363                                    return e.getLabelSymbol(table);
364                            }
365                    }
366                    return null;
367            }
368    
369            public int getParentEdgeLabelCode(SymbolTable table) throws MaltChainedException {
370                    for (Edge e : incomingEdges) {
371                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
372                                    return e.getLabelCode(table);
373                            }
374                    }
375                    return -1;
376            }
377            
378            public boolean hasParentEdgeLabel(SymbolTable table) throws MaltChainedException {
379                    for (Edge e : incomingEdges) {
380                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
381                                    return e.hasLabel(table);
382                            }
383                    }
384                    return false;
385            }
386            
387            public boolean hasAtMostOneHead() {
388                    return heads.size() <= 1;
389            }
390            
391            public boolean hasAncestorInside(int left, int right) throws MaltChainedException {
392                    DependencyNode tmp = this;
393                    if (tmp.getHead() != null) {
394                            tmp = tmp.getHead();
395                            if (tmp.getIndex() >= left && tmp.getIndex() <= right) {
396                                    return true;
397                            }
398                    }
399                    return false;
400            }
401            
402            public Set<Edge> getHeadEdges() throws MaltChainedException {
403                    return incomingEdges;
404            }
405    
406            public Set<DependencyNode> getHeads() throws MaltChainedException {
407                    return heads;
408            }
409    
410            public boolean hasHead() {
411                    return heads.size() != 0;
412            }
413            
414            public DependencyNode getHead() throws MaltChainedException {
415                    if (!hasHead()) {
416                            return null;
417                    }
418                    if (heads.size() > 1) {
419                            throw new SyntaxGraphException("The dependency node is multi-headed and it is ambigious to return a single-head dependency node. ");
420                    }
421                    // heads.first();
422                    for (DependencyNode head : heads) {
423                            return head;
424                    }
425                    return null;
426            }
427            
428            public Edge getHeadEdge() throws MaltChainedException {
429                    if (heads.size() == 0) {
430                            return null;
431                    }
432                    if (incomingEdges.size() == 1 && incomingEdges.first() instanceof DependencyNode) {
433                            return incomingEdges.first();
434                    }
435                    if (heads.size() == 1) {
436                            for (Edge e : incomingEdges) {
437                                    if (e.getSource() == heads.first()) {
438                                            return e;
439                                    }
440                            }
441                    }
442                    return null;
443            }
444            
445            public void addHeadEdgeLabel(SymbolTable table, String symbol) throws MaltChainedException {
446                    if (hasHead()) {
447                            getHeadEdge().addLabel(table, symbol);
448                    }
449            }
450            
451            public void addHeadEdgeLabel(SymbolTable table, int code) throws MaltChainedException {
452                    if (hasHead()) {
453                            getHeadEdge().addLabel(table, code);
454                    }
455            }
456            
457            public void addHeadEdgeLabel(LabelSet labelSet) throws MaltChainedException {
458                    if (hasHead()) {
459                            getHeadEdge().addLabel(labelSet);
460                    }
461            }
462            
463            public boolean hasHeadEdgeLabel(SymbolTable table) throws MaltChainedException {
464                    if (!hasHead()) {
465                            return false;
466                    }
467                    return getHeadEdge().hasLabel(table);
468            }
469            
470            public String getHeadEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
471                    return getHeadEdge().getLabelSymbol(table);
472            }
473            
474            public int getHeadEdgeLabelCode(SymbolTable table) throws MaltChainedException {
475                    if (!hasHead()) {
476                            return 0;
477                    }
478                    return getHeadEdge().getLabelCode(table);
479            }
480            
481            public boolean isHeadEdgeLabeled() throws MaltChainedException {
482                    if (!hasHead()) {
483                            return false;
484                    }
485                    return getHeadEdge().isLabeled();
486            }
487            
488            public int nHeadEdgeLabels() throws MaltChainedException {
489                    if (!hasHead()) {
490                            return 0;
491                    }
492                    return getHeadEdge().nLabels();
493            }
494            
495            public Set<SymbolTable> getHeadEdgeLabelTypes() throws MaltChainedException {
496                    return getHeadEdge().getLabelTypes();
497            }
498            
499            public LabelSet getHeadEdgeLabelSet() throws MaltChainedException {
500                    return getHeadEdge().getLabelSet();
501            }
502            
503            public boolean hasDependent() {
504                    return hasLeftDependent() || hasRightDependent();
505            }
506            
507            /**
508             * Returns <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
509             * 
510             * @return <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
511             */
512            public boolean hasLeftDependent() {
513                    return !leftDependents.isEmpty();
514            }
515            
516            /**
517             * Returns the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent.
518             * 
519             * @param index the index
520             * @return the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent
521             */
522            public DependencyNode getLeftDependent(int index) {
523                    if (0 <= index && index < leftDependents.size()) {
524                            int i = 0;
525                            DependencyNode candidate = null;
526                            
527                            for (DependencyNode node : leftDependents) {
528                                    candidate = node;
529                                    if (i == index) {
530                                            return candidate;
531                                    }
532                                    i++;
533                            }
534                    }
535                    return null;
536            }
537            
538            /**
539             * Return the number of left dependents
540             * 
541             * @return the number of left dependents
542             */
543            public int getLeftDependentCount() {
544                    return leftDependents.size();
545            }
546            
547            public SortedSet<DependencyNode> getLeftDependents() {
548                    return leftDependents;
549            }
550            
551            /**
552             * Returns the left sibling if it exists, otherwise <code>null</code>
553             * 
554             * @return the left sibling if it exists, otherwise <code>null</code>
555             */
556            public DependencyNode getLeftSibling() throws MaltChainedException {
557                    if (getHead() == null) {
558                            return null;
559                    }
560    
561                    DependencyNode candidate = null;
562                    for (DependencyNode node : getHead().getLeftDependents()) {
563                            if (node == this) {
564                                    return candidate;
565                            }
566                            candidate = node;
567                    }
568                    for (DependencyNode node : getHead().getRightDependents()) {
569                            if (node == this) {
570                                    return candidate;
571                            }
572                            candidate = node;
573                    }
574                    return null;
575            }
576            
577            /**
578             * Returns the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
579             * 
580             * @return the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
581             */
582            public DependencyNode getSameSideLeftSibling() throws MaltChainedException {
583                    if (getHead() == null) {
584                            return null;
585                    } else if (this.getIndex() < getHead().getIndex()) {
586                            try {
587                                    return getHead().getLeftDependents().headSet(this).last();
588                            } catch (NoSuchElementException e) {
589                                    return null;
590                            }
591                    } else if (this.getIndex() > getHead().getIndex()) {
592                            try {
593                                    return getHead().getRightDependents().headSet(this).last();
594                            } catch (NoSuchElementException e) {
595                                    return null;
596                            }
597                    }
598                    return null;
599            }
600            
601            /**
602             * Returns the closest left dependent to the node it self, if not found <code>null</code> is returned.
603             * 
604             * @return the closest left dependent to the node it self, if not found <code>null</code> is returned.
605             */
606            public DependencyNode getClosestLeftDependent() {
607                    try {
608                            return leftDependents.last();
609                    } catch (NoSuchElementException e) {
610                            return null;
611                    }
612            }
613            
614            public DependencyNode getLeftmostDependent() {
615                    for (DependencyNode dep : leftDependents) {
616                            return dep;
617                    }
618                    return null;
619    //              try {
620    //                      return leftDependents.first();
621    //              } catch (NoSuchElementException e) {
622    //                      return null;
623    //              }
624            }
625            
626            public DependencyNode getRightDependent(int index) {
627                    int size = rightDependents.size();
628                    if (index < size) {
629                            return rightDependents.toArray(new DependencyNode[size])[size - 1 - index];
630                    }
631                    return null;
632    //              if (0 <= index && index < rightDependents.size()) {
633    //                      int i = 0;
634    //                      DependencyNode candidate = null;
635    //                      
636    //                      for (DependencyNode node : rightDependents) {
637    //                              candidate = node;
638    //                              if (i == index) {
639    //                                      return candidate;
640    //                              }
641    //                              i++;
642    //                      }
643    //              }
644    //              return null;
645            }
646            
647            /**
648             * Return the number of right dependents
649             * 
650             * @return the number of right dependents
651             */
652            public int getRightDependentCount() {
653                    return rightDependents.size();
654            }
655            
656            /**
657             * Returns a sorted set of right dependents.
658             * 
659             * @return a sorted set of right dependents.
660             */
661            public SortedSet<DependencyNode> getRightDependents() {
662                    return rightDependents;
663            }
664            
665            /**
666             * Returns the right sibling if it exists, otherwise <code>null</code>
667             * 
668             * @return the right sibling if it exists, otherwise <code>null</code>
669             */
670            public DependencyNode getRightSibling() throws MaltChainedException {
671                    if (getHead() == null) {
672                            return null;
673                    }
674    
675                    for (DependencyNode node : getHead().getLeftDependents()) {
676                            if (node.getIndex() > this.getIndex()) {
677                                    return node;
678                            }
679                    }
680                    for (DependencyNode node : getHead().getRightDependents()) {
681                            if (node.getIndex() > this.getIndex()) {
682                                    return node;
683                            }
684                    }
685                    return null;
686            }
687            
688            /**
689             * Returns the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
690             * 
691             * @return the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
692             */
693            public DependencyNode getSameSideRightSibling() throws MaltChainedException {
694                    if (getHead() == null) {
695                            return null;
696                    } else if (this.getIndex() < getHead().getIndex()) {
697                            final SortedSet<DependencyNode> tailSet = getHead().getLeftDependents().tailSet(this);
698                            if (tailSet.size() <= 1)  {
699                                    return null;
700                            }
701                            return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
702                    } else if (this.getIndex() > getHead().getIndex()) {
703                            final SortedSet<DependencyNode> tailSet = getHead().getRightDependents().tailSet(this);
704                            if (tailSet.size() <= 1)  {
705                                    return null;
706                            }
707                            return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
708                    }
709                    return null;
710            }
711            
712            /**
713             * Returns the closest right dependent to the node it self, if not found <code>null</code> is returned.
714             * 
715             * @return the closest right dependent to the node it self, if not found <code>null</code> is returned.
716             */
717            public DependencyNode getClosestRightDependent() {
718                    for (DependencyNode dep : rightDependents) {
719                            return dep;
720                    }
721                    return null;
722    //              try {
723    //                      return rightDependents.first();
724    //              } catch (NoSuchElementException e) {
725    //                      return null;
726    //              }
727            }
728            
729            public DependencyNode getRightmostDependent() {
730                    int n = rightDependents.size();
731                    int i = 1;
732                    for (DependencyNode node : rightDependents) {
733                            if (i == n) {
734                                    return node;
735                            }
736                            i++;
737                    }
738                    return null;
739    //              try {
740    //                      return rightDependents.last();
741    //              } catch (NoSuchElementException e) {
742    //                      return null;
743    //              }
744            }
745            
746            protected void getDependencyDominationSet(SortedSet<DependencyNode> dominationSet) {
747                    if (leftDependents.size() > 0 || rightDependents.size() > 0) {
748                            dominationSet.addAll(leftDependents);
749                            dominationSet.addAll(rightDependents);
750                            
751                            for (DependencyNode node : leftDependents) {
752                                    ((Token)node).getDependencyDominationSet(dominationSet);
753                            }
754                            for (DependencyNode node : rightDependents) {
755                                    ((Token)node).getDependencyDominationSet(dominationSet);
756                            }
757                    }
758            }
759            
760    //      private SortedSet<DependencyNode> getDependencyDominationSet() {
761    //              SortedSet<DependencyNode> dominationSet = new TreeSet<DependencyNode>();
762    //              getDependencyDominationSet(dominationSet);
763    //              return dominationSet;
764    //      }
765            
766            
767            /**
768             * Returns <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
769             * 
770             * @return <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
771             */
772            public boolean hasRightDependent() {
773                    return !rightDependents.isEmpty();
774            }
775    
776            public boolean isProjective() throws MaltChainedException {
777                    if (hasHead() && !getHead().isRoot()) {
778                            final DependencyNode head = getHead();
779                            if (getHead().getIndex() < this.getIndex()) {
780                                    TokenNode terminals = ((TokenNode)head);
781                                    DependencyNode tmp = null;
782                                    while (true) {
783                                            if (terminals == null || terminals.getSuccessor() == null) {
784                                                    return false;
785                                            }
786                                            if (terminals.getSuccessor() == this) {
787                                                    break;
788                                            }
789                                            tmp = terminals = terminals.getSuccessor();
790                                            while (tmp != this && tmp != head) {
791                                                    if (!tmp.hasHead()) {
792                                                            return false;
793                                                    }
794                                                    tmp = tmp.getHead();
795                                            }
796                                    }
797                            } else {
798                                    TokenNode terminals = ((TokenNode)this);
799                                    DependencyNode tmp = null;
800                                    while (true) {
801                                            if (terminals == null || terminals.getSuccessor() == null) {
802                                                    return false;
803                                            }
804                                            if (terminals.getSuccessor() == head) {
805                                                    break;
806                                            }
807                                            tmp = terminals = terminals.getSuccessor();
808                                            while (tmp != this && tmp != head) {
809                                                    if (!tmp.hasHead()) {
810                                                            return false;
811                                                    }
812                                                    tmp = tmp.getHead();
813                                            }
814                                    }
815                            }
816                    }
817                    return true;
818            }
819    
820            public int getDependencyNodeDepth() throws MaltChainedException {
821                    DependencyNode tmp = this;
822                    int depth = 0;
823                    while (tmp.hasHead()) {
824                            depth++;
825                            tmp = tmp.getHead();
826                    }
827                    return depth;
828            }
829            
830            public void clear() throws MaltChainedException {
831                    super.clear();
832                    predecessor = null;
833                    successor = null;
834                    component = this;
835                    rank = 0;
836                    parent = null;
837                    heads.clear();
838                    leftDependents.clear();
839                    rightDependents.clear();
840            }
841            
842            @Override
843            public int compareTo(ComparableNode that) {
844                    final int BEFORE = -1;
845                final int EQUAL = 0;
846                final int AFTER = 1;
847                if (this == that) return EQUAL;
848    
849                if (that instanceof TokenNode) {
850                        if (this.index < that.getCompareToIndex()) return BEFORE;
851                        if (this.index > that.getCompareToIndex()) return AFTER;
852                        return super.compareTo(that);
853                }
854                if (that instanceof NonTerminalNode) {
855                    try {
856                                final int thisLCorner = this.index;
857                                final int thatLCorner = that.getLeftmostProperDescendantIndex();
858                                final int thisRCorner = this.index;
859                                final int thatRCorner = that.getRightmostProperDescendantIndex();
860    
861    //                          if (thisLCorner == -1 || thatLCorner == -1) {
862    //                                  if (thisRCorner < thatRCorner) return BEFORE;
863    //                                  if (thisRCorner > thatRCorner) return AFTER;
864    //                          }
865    //                          if (thisRCorner == -1 || thatRCorner == -1) {
866    //                                  if (thisLCorner < thatLCorner) return BEFORE;
867    //                                  if (thisLCorner > thatLCorner) return AFTER;
868    //                          }
869                                
870                                if (thisLCorner != -1 && thatLCorner != -1 && thisRCorner != -1 && thatRCorner != -1) {
871                                        if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
872                                        if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
873                                        if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
874                                        if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
875                                } else {
876                                        if (thisLCorner != -1 && thatLCorner != -1) {
877                                                if (thisLCorner < thatLCorner) return BEFORE;
878                                                if (thisLCorner > thatLCorner) return AFTER;
879                                        }
880                                        if (thisRCorner != -1 && thatRCorner != -1) {
881                                                if (thisRCorner < thatRCorner) return BEFORE;
882                                                if (thisRCorner > thatRCorner) return AFTER;
883                                        }
884                                }
885                            
886                            
887                            
888    //                          final int thisLCorner = this.index;
889    //                          final int thatLCorner = that.getLeftmostDescendantIndex();
890    //                          final int thisRCorner = this.index;
891    //                          final int thatRCorner = that.getRightmostDescendantIndex();
892    //
893    //                          if (thisLCorner == -1 || thatLCorner == -1) {
894    //                                  if (thisRCorner < thatRCorner) return BEFORE;
895    //                                  if (thisRCorner > thatRCorner) return AFTER;
896    //                          }
897    //                          if (thisRCorner == -1 || thatRCorner == -1) {
898    //                                  if (thisLCorner < thatLCorner) return BEFORE;
899    //                                  if (thisLCorner > thatLCorner) return AFTER;
900    //                          }
901    //                          if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
902    //                          if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
903    //                          if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
904    //                          if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
905                            
906                            
907                            
908    //                      int corner = that.getLeftmostDescendantIndex();
909    //                      if (corner != -1) {
910    //                              if (this.index < corner) return BEFORE;
911    //                              if (this.index > corner) return AFTER;
912    //                      }
913    //                      corner = that.getRightmostDescendantIndex();
914    //                      if (corner != -1) {
915    //                              if (this.index < corner) return BEFORE;
916    //                              if (this.index > corner) return AFTER;
917    //                      }
918                    } catch (MaltChainedException e) {
919                                    if (SystemLogger.logger().isDebugEnabled()) {
920                                            SystemLogger.logger().debug("",e);
921                                    } else {
922                                            SystemLogger.logger().error(e.getMessageChain());
923                                    }
924                                    System.exit(1);
925                    }
926                }
927                if (this.index < that.getCompareToIndex()) return BEFORE;
928                if (this.index > that.getCompareToIndex()) return AFTER;
929                    return super.compareTo(that);
930            }
931    
932            public boolean equals(Object obj) {
933                    Token v = (Token)obj;
934                    if (!(this.predecessor == v.predecessor && this.successor == v.successor)) return false;
935                    return super.equals(obj);
936            }
937            
938            public int hashCode() {
939                    int hash = 7;
940                    hash = 31 * hash + (null == predecessor ? 0 : predecessor.hashCode());
941                    hash = 31 * hash + (null == successor ? 0 : successor.hashCode());
942                    return 31 * hash + super.hashCode();
943            }
944            
945    
946            public String toString() {
947                    final StringBuilder sb = new StringBuilder();
948                    sb.append(super.toString());
949                    return sb.toString();
950            }
951    }