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 DependencyNode getAncestor() throws MaltChainedException {
184                    if (!this.hasHead()) {
185                            return this;
186                    }
187                    
188                    DependencyNode tmp = this;
189                    while (tmp.hasHead()) {
190                            tmp = tmp.getHead();
191                    }
192                    return tmp;
193            }
194            
195            public DependencyNode getProperAncestor() throws MaltChainedException {
196                    if (!this.hasHead()) {
197                            return null;
198                    }
199                    
200                    DependencyNode tmp = this;
201                    while (tmp.hasHead()) {
202                            tmp = tmp.getHead();
203                    }
204                    return tmp;
205            }
206            
207            public ComparableNode getLeftmostProperDescendant() throws MaltChainedException {
208                    ComparableNode candidate = null;
209                    ComparableNode tmp = null;
210                    for (DependencyNode ldep : leftDependents) {
211                            if (candidate == null) {
212                                    candidate = ldep;
213                            } else if (ldep.getIndex() < candidate.getIndex() ) {
214                                    candidate = ldep;
215                            }
216                            tmp = ((Token)ldep).getLeftmostProperDescendant();
217                            if (tmp == null) {
218                                    continue;
219                            }
220                            if (candidate == null) {
221                                    candidate = tmp;
222                            } else if (tmp.getIndex() < candidate.getIndex() ) {
223                                    candidate = tmp;
224                            }
225                            if (candidate.getIndex() == 1) {
226                                    return candidate;
227                            }
228                    }
229                    for (DependencyNode rdep : rightDependents) {
230                            if (candidate == null) {
231                                    candidate = rdep;
232                            } else if (rdep.getIndex() < candidate.getIndex() ) {
233                                    candidate = rdep;
234                            }
235                            tmp = ((Token)rdep).getLeftmostProperDescendant();
236                            if (tmp == null) {
237                                    continue;
238                            }
239                            if (candidate == null) {
240                                    candidate = tmp;
241                            } else if (tmp.getIndex() < candidate.getIndex() ) {
242                                    candidate = tmp;
243                            }
244                            if (candidate.getIndex() == 1) {
245                                    return candidate;
246                            }
247                    }
248                    return candidate;
249            }
250            
251            public ComparableNode getRightmostProperDescendant() throws MaltChainedException {
252                    ComparableNode candidate = null;
253                    ComparableNode tmp = null;
254                    for (DependencyNode ldep : leftDependents) {
255                            if (candidate == null) {
256                                    candidate = ldep;
257                            } else if (ldep.getIndex() > candidate.getIndex() ) {
258                                    candidate = ldep;
259                            }
260                            tmp = ((Token)ldep).getRightmostProperDescendant();
261                            if (tmp == null) {
262                                    continue;
263                            }
264                            if (candidate == null) {
265                                    candidate = tmp;
266                            } else if (tmp.getIndex() > candidate.getIndex() ) {
267                                    candidate = tmp;
268                            }
269                    }
270                    for (DependencyNode rdep : rightDependents) {
271                            if (candidate == null) {
272                                    candidate = rdep;
273                            } else if (rdep.getIndex() > candidate.getIndex() ) {
274                                    candidate = rdep;
275                            }
276                            tmp = ((Token)rdep).getRightmostProperDescendant();
277                            if (tmp == null) {
278                                    continue;
279                            }
280                            if (candidate == null) {
281                                    candidate = tmp;
282                            } else if (tmp.getIndex() > candidate.getIndex() ) {
283                                    candidate = tmp;
284                            }
285                    }
286                    return candidate;
287            }
288            
289            public ComparableNode getLeftmostDescendant() throws MaltChainedException {
290                    ComparableNode candidate = this;
291                    ComparableNode tmp = null;
292                    for (DependencyNode ldep : leftDependents) {
293                            if (candidate == null) {
294                                    candidate = ldep;
295                            } else if (ldep.getIndex() < candidate.getIndex() ) {
296                                    candidate = ldep;
297                            }
298                            tmp = ((Token)ldep).getLeftmostDescendant();
299                            if (tmp == null) {
300                                    continue;
301                            }
302                            if (candidate == null) {
303                                    candidate = tmp;
304                            } else if (tmp.getIndex() < candidate.getIndex() ) {
305                                    candidate = tmp;
306                            }
307                            if (candidate.getIndex() == 1) {
308                                    return candidate;
309                            }
310                    }
311                    for (DependencyNode rdep : rightDependents) {
312                            if (candidate == null) {
313                                    candidate = rdep;
314                            } else if (rdep.getIndex() < candidate.getIndex() ) {
315                                    candidate = rdep;
316                            }
317                            tmp = ((Token)rdep).getLeftmostDescendant();
318                            if (tmp == null) {
319                                    continue;
320                            }
321                            if (candidate == null) {
322                                    candidate = tmp;
323                            } else if (tmp.getIndex() < candidate.getIndex() ) {
324                                    candidate = tmp;
325                            }
326                            if (candidate.getIndex() == 1) {
327                                    return candidate;
328                            }
329                    }
330                    return candidate;
331            }
332            
333            public ComparableNode getRightmostDescendant() throws MaltChainedException {
334                    ComparableNode candidate = this;
335                    ComparableNode tmp = null;
336                    for (DependencyNode ldep : leftDependents) {
337                            if (candidate == null) {
338                                    candidate = ldep;
339                            } else if (ldep.getIndex() > candidate.getIndex() ) {
340                                    candidate = ldep;
341                            }
342                            tmp = ((Token)ldep).getRightmostDescendant();
343                            if (tmp == null) {
344                                    continue;
345                            }
346                            if (candidate == null) {
347                                    candidate = tmp;
348                            } else if (tmp.getIndex() > candidate.getIndex() ) {
349                                    candidate = tmp;
350                            }
351                    }
352                    for (DependencyNode rdep : rightDependents) {
353                            if (candidate == null) {
354                                    candidate = rdep;
355                            } else if (rdep.getIndex() > candidate.getIndex() ) {
356                                    candidate = rdep;
357                            }
358                            tmp = ((Token)rdep).getRightmostDescendant();
359                            if (tmp == null) {
360                                    continue;
361                            }
362                            if (candidate == null) {
363                                    candidate = tmp;
364                            } else if (tmp.getIndex() > candidate.getIndex() ) {
365                                    candidate = tmp;
366                            }
367                    }
368                    return candidate;
369            }
370            
371            public PhraseStructureNode getParent() {
372                    return parent;
373            }
374    
375            public Edge getParentEdge() throws MaltChainedException {
376                    for (Edge e : incomingEdges) {
377                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
378                                    return e;
379                            }
380                    }
381                    return null;
382            }
383            
384            public String getParentEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
385                    for (Edge e : incomingEdges) {
386                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
387                                    return e.getLabelSymbol(table);
388                            }
389                    }
390                    return null;
391            }
392    
393            public int getParentEdgeLabelCode(SymbolTable table) throws MaltChainedException {
394                    for (Edge e : incomingEdges) {
395                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
396                                    return e.getLabelCode(table);
397                            }
398                    }
399                    return -1;
400            }
401            
402            public boolean hasParentEdgeLabel(SymbolTable table) throws MaltChainedException {
403                    for (Edge e : incomingEdges) {
404                            if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
405                                    return e.hasLabel(table);
406                            }
407                    }
408                    return false;
409            }
410            
411            public boolean hasAtMostOneHead() {
412                    return heads.size() <= 1;
413            }
414            
415            public boolean hasAncestorInside(int left, int right) throws MaltChainedException {
416                    DependencyNode tmp = this;
417                    if (tmp.getHead() != null) {
418                            tmp = tmp.getHead();
419                            if (tmp.getIndex() >= left && tmp.getIndex() <= right) {
420                                    return true;
421                            }
422                    }
423                    return false;
424            }
425            
426            public Set<Edge> getHeadEdges() throws MaltChainedException {
427                    return incomingEdges;
428            }
429    
430            public Set<DependencyNode> getHeads() throws MaltChainedException {
431                    return heads;
432            }
433    
434            public boolean hasHead() {
435                    return heads.size() != 0;
436            }
437            
438            public DependencyNode getHead() throws MaltChainedException {
439                    if (!hasHead()) {
440                            return null;
441                    }
442                    if (heads.size() > 1) {
443                            throw new SyntaxGraphException("The dependency node is multi-headed and it is ambigious to return a single-head dependency node. ");
444                    }
445                    // heads.first();
446                    for (DependencyNode head : heads) {
447                            return head;
448                    }
449                    return null;
450            }
451            
452            public Edge getHeadEdge() throws MaltChainedException {
453                    if (heads.size() == 0) {
454                            return null;
455                    }
456                    if (incomingEdges.size() == 1 && incomingEdges.first() instanceof DependencyNode) {
457                            return incomingEdges.first();
458                    }
459                    if (heads.size() == 1) {
460                            for (Edge e : incomingEdges) {
461                                    if (e.getSource() == heads.first()) {
462                                            return e;
463                                    }
464                            }
465                    }
466                    return null;
467            }
468            
469            public void addHeadEdgeLabel(SymbolTable table, String symbol) throws MaltChainedException {
470                    if (hasHead()) {
471                            getHeadEdge().addLabel(table, symbol);
472                    }
473            }
474            
475            public void addHeadEdgeLabel(SymbolTable table, int code) throws MaltChainedException {
476                    if (hasHead()) {
477                            getHeadEdge().addLabel(table, code);
478                    }
479            }
480            
481            public void addHeadEdgeLabel(LabelSet labelSet) throws MaltChainedException {
482                    if (hasHead()) {
483                            getHeadEdge().addLabel(labelSet);
484                    }
485            }
486            
487            public boolean hasHeadEdgeLabel(SymbolTable table) throws MaltChainedException {
488                    if (!hasHead()) {
489                            return false;
490                    }
491                    return getHeadEdge().hasLabel(table);
492            }
493            
494            public String getHeadEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
495                    return getHeadEdge().getLabelSymbol(table);
496            }
497            
498            public int getHeadEdgeLabelCode(SymbolTable table) throws MaltChainedException {
499                    if (!hasHead()) {
500                            return 0;
501                    }
502                    return getHeadEdge().getLabelCode(table);
503            }
504            
505            public boolean isHeadEdgeLabeled() throws MaltChainedException {
506                    if (!hasHead()) {
507                            return false;
508                    }
509                    return getHeadEdge().isLabeled();
510            }
511            
512            public int nHeadEdgeLabels() throws MaltChainedException {
513                    if (!hasHead()) {
514                            return 0;
515                    }
516                    return getHeadEdge().nLabels();
517            }
518            
519            public Set<SymbolTable> getHeadEdgeLabelTypes() throws MaltChainedException {
520                    return getHeadEdge().getLabelTypes();
521            }
522            
523            public LabelSet getHeadEdgeLabelSet() throws MaltChainedException {
524                    return getHeadEdge().getLabelSet();
525            }
526            
527            public boolean hasDependent() {
528                    return hasLeftDependent() || hasRightDependent();
529            }
530            
531            /**
532             * Returns <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
533             * 
534             * @return <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
535             */
536            public boolean hasLeftDependent() {
537                    return !leftDependents.isEmpty();
538            }
539            
540            /**
541             * Returns the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent.
542             * 
543             * @param index the index
544             * @return the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent
545             */
546            public DependencyNode getLeftDependent(int index) {
547                    if (0 <= index && index < leftDependents.size()) {
548                            int i = 0;
549                            DependencyNode candidate = null;
550                            
551                            for (DependencyNode node : leftDependents) {
552                                    candidate = node;
553                                    if (i == index) {
554                                            return candidate;
555                                    }
556                                    i++;
557                            }
558                    }
559                    return null;
560            }
561            
562            /**
563             * Return the number of left dependents
564             * 
565             * @return the number of left dependents
566             */
567            public int getLeftDependentCount() {
568                    return leftDependents.size();
569            }
570            
571            public SortedSet<DependencyNode> getLeftDependents() {
572                    return leftDependents;
573            }
574            
575            /**
576             * Returns the left sibling if it exists, otherwise <code>null</code>
577             * 
578             * @return the left sibling if it exists, otherwise <code>null</code>
579             */
580            public DependencyNode getLeftSibling() throws MaltChainedException {
581                    if (getHead() == null) {
582                            return null;
583                    }
584    
585                    DependencyNode candidate = null;
586                    for (DependencyNode node : getHead().getLeftDependents()) {
587                            if (node == this) {
588                                    return candidate;
589                            }
590                            candidate = node;
591                    }
592                    for (DependencyNode node : getHead().getRightDependents()) {
593                            if (node == this) {
594                                    return candidate;
595                            }
596                            candidate = node;
597                    }
598                    return null;
599            }
600            
601            /**
602             * Returns the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
603             * 
604             * @return the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
605             */
606            public DependencyNode getSameSideLeftSibling() throws MaltChainedException {
607                    if (getHead() == null) {
608                            return null;
609                    } else if (this.getIndex() < getHead().getIndex()) {
610                            try {
611                                    return getHead().getLeftDependents().headSet(this).last();
612                            } catch (NoSuchElementException e) {
613                                    return null;
614                            }
615                    } else if (this.getIndex() > getHead().getIndex()) {
616                            try {
617                                    return getHead().getRightDependents().headSet(this).last();
618                            } catch (NoSuchElementException e) {
619                                    return null;
620                            }
621                    }
622                    return null;
623            }
624            
625            /**
626             * Returns the closest left dependent to the node it self, if not found <code>null</code> is returned.
627             * 
628             * @return the closest left dependent to the node it self, if not found <code>null</code> is returned.
629             */
630            public DependencyNode getClosestLeftDependent() {
631                    try {
632                            return leftDependents.last();
633                    } catch (NoSuchElementException e) {
634                            return null;
635                    }
636            }
637            
638            public DependencyNode getLeftmostDependent() {
639                    for (DependencyNode dep : leftDependents) {
640                            return dep;
641                    }
642                    return null;
643    //              try {
644    //                      return leftDependents.first();
645    //              } catch (NoSuchElementException e) {
646    //                      return null;
647    //              }
648            }
649            
650            public DependencyNode getRightDependent(int index) {
651                    int size = rightDependents.size();
652                    if (index < size) {
653                            return rightDependents.toArray(new DependencyNode[size])[size - 1 - index];
654                    }
655                    return null;
656    //              if (0 <= index && index < rightDependents.size()) {
657    //                      int i = 0;
658    //                      DependencyNode candidate = null;
659    //                      
660    //                      for (DependencyNode node : rightDependents) {
661    //                              candidate = node;
662    //                              if (i == index) {
663    //                                      return candidate;
664    //                              }
665    //                              i++;
666    //                      }
667    //              }
668    //              return null;
669            }
670            
671            /**
672             * Return the number of right dependents
673             * 
674             * @return the number of right dependents
675             */
676            public int getRightDependentCount() {
677                    return rightDependents.size();
678            }
679            
680            /**
681             * Returns a sorted set of right dependents.
682             * 
683             * @return a sorted set of right dependents.
684             */
685            public SortedSet<DependencyNode> getRightDependents() {
686                    return rightDependents;
687            }
688            
689            /**
690             * Returns the right sibling if it exists, otherwise <code>null</code>
691             * 
692             * @return the right sibling if it exists, otherwise <code>null</code>
693             */
694            public DependencyNode getRightSibling() throws MaltChainedException {
695                    if (getHead() == null) {
696                            return null;
697                    }
698    
699                    for (DependencyNode node : getHead().getLeftDependents()) {
700                            if (node.getIndex() > this.getIndex()) {
701                                    return node;
702                            }
703                    }
704                    for (DependencyNode node : getHead().getRightDependents()) {
705                            if (node.getIndex() > this.getIndex()) {
706                                    return node;
707                            }
708                    }
709                    return null;
710            }
711            
712            /**
713             * Returns the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
714             * 
715             * @return the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
716             */
717            public DependencyNode getSameSideRightSibling() throws MaltChainedException {
718                    if (getHead() == null) {
719                            return null;
720                    } else if (this.getIndex() < getHead().getIndex()) {
721                            final SortedSet<DependencyNode> tailSet = getHead().getLeftDependents().tailSet(this);
722                            if (tailSet.size() <= 1)  {
723                                    return null;
724                            }
725                            return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
726                    } else if (this.getIndex() > getHead().getIndex()) {
727                            final SortedSet<DependencyNode> tailSet = getHead().getRightDependents().tailSet(this);
728                            if (tailSet.size() <= 1)  {
729                                    return null;
730                            }
731                            return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
732                    }
733                    return null;
734            }
735            
736            /**
737             * Returns the closest right dependent to the node it self, if not found <code>null</code> is returned.
738             * 
739             * @return the closest right dependent to the node it self, if not found <code>null</code> is returned.
740             */
741            public DependencyNode getClosestRightDependent() {
742                    for (DependencyNode dep : rightDependents) {
743                            return dep;
744                    }
745                    return null;
746    //              try {
747    //                      return rightDependents.first();
748    //              } catch (NoSuchElementException e) {
749    //                      return null;
750    //              }
751            }
752            
753            public DependencyNode getRightmostDependent() {
754                    int n = rightDependents.size();
755                    int i = 1;
756                    for (DependencyNode node : rightDependents) {
757                            if (i == n) {
758                                    return node;
759                            }
760                            i++;
761                    }
762                    return null;
763    //              try {
764    //                      return rightDependents.last();
765    //              } catch (NoSuchElementException e) {
766    //                      return null;
767    //              }
768            }
769            
770            protected void getDependencyDominationSet(SortedSet<DependencyNode> dominationSet) {
771                    if (leftDependents.size() > 0 || rightDependents.size() > 0) {
772                            dominationSet.addAll(leftDependents);
773                            dominationSet.addAll(rightDependents);
774                            
775                            for (DependencyNode node : leftDependents) {
776                                    ((Token)node).getDependencyDominationSet(dominationSet);
777                            }
778                            for (DependencyNode node : rightDependents) {
779                                    ((Token)node).getDependencyDominationSet(dominationSet);
780                            }
781                    }
782            }
783            
784    //      private SortedSet<DependencyNode> getDependencyDominationSet() {
785    //              SortedSet<DependencyNode> dominationSet = new TreeSet<DependencyNode>();
786    //              getDependencyDominationSet(dominationSet);
787    //              return dominationSet;
788    //      }
789            
790            
791            /**
792             * Returns <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
793             * 
794             * @return <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
795             */
796            public boolean hasRightDependent() {
797                    return !rightDependents.isEmpty();
798            }
799    
800            public boolean isProjective() throws MaltChainedException {
801                    if (hasHead() && !getHead().isRoot()) {
802                            final DependencyNode head = getHead();
803                            if (getHead().getIndex() < this.getIndex()) {
804                                    TokenNode terminals = ((TokenNode)head);
805                                    DependencyNode tmp = null;
806                                    while (true) {
807                                            if (terminals == null || terminals.getSuccessor() == null) {
808                                                    return false;
809                                            }
810                                            if (terminals.getSuccessor() == this) {
811                                                    break;
812                                            }
813                                            tmp = terminals = terminals.getSuccessor();
814                                            while (tmp != this && tmp != head) {
815                                                    if (!tmp.hasHead()) {
816                                                            return false;
817                                                    }
818                                                    tmp = tmp.getHead();
819                                            }
820                                    }
821                            } else {
822                                    TokenNode terminals = ((TokenNode)this);
823                                    DependencyNode tmp = null;
824                                    while (true) {
825                                            if (terminals == null || terminals.getSuccessor() == null) {
826                                                    return false;
827                                            }
828                                            if (terminals.getSuccessor() == head) {
829                                                    break;
830                                            }
831                                            tmp = terminals = terminals.getSuccessor();
832                                            while (tmp != this && tmp != head) {
833                                                    if (!tmp.hasHead()) {
834                                                            return false;
835                                                    }
836                                                    tmp = tmp.getHead();
837                                            }
838                                    }
839                            }
840                    }
841                    return true;
842            }
843    
844            public int getDependencyNodeDepth() throws MaltChainedException {
845                    DependencyNode tmp = this;
846                    int depth = 0;
847                    while (tmp.hasHead()) {
848                            depth++;
849                            tmp = tmp.getHead();
850                    }
851                    return depth;
852            }
853            
854            public void clear() throws MaltChainedException {
855                    super.clear();
856                    predecessor = null;
857                    successor = null;
858                    component = this;
859                    rank = 0;
860                    parent = null;
861                    heads.clear();
862                    leftDependents.clear();
863                    rightDependents.clear();
864            }
865            
866            @Override
867            public int compareTo(ComparableNode that) {
868                    final int BEFORE = -1;
869                final int EQUAL = 0;
870                final int AFTER = 1;
871                if (this == that) return EQUAL;
872    
873                if (that instanceof TokenNode) {
874                        if (this.index < that.getCompareToIndex()) return BEFORE;
875                        if (this.index > that.getCompareToIndex()) return AFTER;
876                        return super.compareTo(that);
877                }
878                if (that instanceof NonTerminalNode) {
879                    try {
880                                final int thisLCorner = this.index;
881                                final int thatLCorner = that.getLeftmostProperDescendantIndex();
882                                final int thisRCorner = this.index;
883                                final int thatRCorner = that.getRightmostProperDescendantIndex();
884    
885    //                          if (thisLCorner == -1 || thatLCorner == -1) {
886    //                                  if (thisRCorner < thatRCorner) return BEFORE;
887    //                                  if (thisRCorner > thatRCorner) return AFTER;
888    //                          }
889    //                          if (thisRCorner == -1 || thatRCorner == -1) {
890    //                                  if (thisLCorner < thatLCorner) return BEFORE;
891    //                                  if (thisLCorner > thatLCorner) return AFTER;
892    //                          }
893                                
894                                if (thisLCorner != -1 && thatLCorner != -1 && thisRCorner != -1 && thatRCorner != -1) {
895                                        if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
896                                        if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
897                                        if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
898                                        if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
899                                } else {
900                                        if (thisLCorner != -1 && thatLCorner != -1) {
901                                                if (thisLCorner < thatLCorner) return BEFORE;
902                                                if (thisLCorner > thatLCorner) return AFTER;
903                                        }
904                                        if (thisRCorner != -1 && thatRCorner != -1) {
905                                                if (thisRCorner < thatRCorner) return BEFORE;
906                                                if (thisRCorner > thatRCorner) return AFTER;
907                                        }
908                                }
909                            
910                            
911                            
912    //                          final int thisLCorner = this.index;
913    //                          final int thatLCorner = that.getLeftmostDescendantIndex();
914    //                          final int thisRCorner = this.index;
915    //                          final int thatRCorner = that.getRightmostDescendantIndex();
916    //
917    //                          if (thisLCorner == -1 || thatLCorner == -1) {
918    //                                  if (thisRCorner < thatRCorner) return BEFORE;
919    //                                  if (thisRCorner > thatRCorner) return AFTER;
920    //                          }
921    //                          if (thisRCorner == -1 || thatRCorner == -1) {
922    //                                  if (thisLCorner < thatLCorner) return BEFORE;
923    //                                  if (thisLCorner > thatLCorner) return AFTER;
924    //                          }
925    //                          if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
926    //                          if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
927    //                          if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
928    //                          if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
929                            
930                            
931                            
932    //                      int corner = that.getLeftmostDescendantIndex();
933    //                      if (corner != -1) {
934    //                              if (this.index < corner) return BEFORE;
935    //                              if (this.index > corner) return AFTER;
936    //                      }
937    //                      corner = that.getRightmostDescendantIndex();
938    //                      if (corner != -1) {
939    //                              if (this.index < corner) return BEFORE;
940    //                              if (this.index > corner) return AFTER;
941    //                      }
942                    } catch (MaltChainedException e) {
943                                    if (SystemLogger.logger().isDebugEnabled()) {
944                                            SystemLogger.logger().debug("",e);
945                                    } else {
946                                            SystemLogger.logger().error(e.getMessageChain());
947                                    }
948                                    System.exit(1);
949                    }
950                }
951                if (this.index < that.getCompareToIndex()) return BEFORE;
952                if (this.index > that.getCompareToIndex()) return AFTER;
953                    return super.compareTo(that);
954            }
955    
956            public boolean equals(Object obj) {
957                    Token v = (Token)obj;
958                    if (!(this.predecessor == v.predecessor && this.successor == v.successor)) return false;
959                    return super.equals(obj);
960            }
961            
962            public int hashCode() {
963                    int hash = 7;
964                    hash = 31 * hash + (null == predecessor ? 0 : predecessor.hashCode());
965                    hash = 31 * hash + (null == successor ? 0 : successor.hashCode());
966                    return 31 * hash + super.hashCode();
967            }
968            
969    
970            public String toString() {
971                    final StringBuilder sb = new StringBuilder();
972                    sb.append(super.toString());
973                    return sb.toString();
974            }
975    }