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 heads.add((DependencyNode)in.getSource());
116 } else if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
117 parent = (PhraseStructureNode)in.getSource();
118 }
119 }
120 }
121
122 public void removeIncomingEdge(Edge in) throws MaltChainedException {
123 super.removeIncomingEdge(in);
124 if (in.getSource() != null) {
125 if (in.getType() == Edge.DEPENDENCY_EDGE && in.getSource() instanceof DependencyNode) {
126 heads.remove((DependencyNode)in.getSource());
127 } else if (in.getType() == Edge.PHRASE_STRUCTURE_EDGE && in.getSource() instanceof PhraseStructureNode) {
128 if (in.getSource() == parent) {
129 this.parent = null;
130 }
131 }
132 }
133 }
134
135 public void addOutgoingEdge(Edge out) throws MaltChainedException {
136 super.addOutgoingEdge(out);
137 if (out.getType() == Edge.DEPENDENCY_EDGE && out.getTarget() instanceof DependencyNode) {
138 final DependencyNode dependent = (DependencyNode)out.getTarget();
139 if (compareTo(dependent) > 0) {
140 leftDependents.add((DependencyNode)dependent);
141 } else if (compareTo(dependent) < 0) {
142 rightDependents.add((DependencyNode)dependent);
143 }
144 }
145 }
146
147 public void removeOutgoingEdge(Edge out) throws MaltChainedException {
148 super.removeOutgoingEdge(out);
149 if (out.getType() == Edge.DEPENDENCY_EDGE && out.getTarget() instanceof DependencyNode) {
150 final DependencyNode dependent = (DependencyNode)out.getTarget();
151 if (compareTo(dependent) > 0) {
152 leftDependents.remove((DependencyNode)dependent);
153 } else if (compareTo(dependent) < 0) {
154 rightDependents.remove((DependencyNode)dependent);
155 }
156 }
157 }
158
159 public void setIndex(int index) throws MaltChainedException {
160 if (index > 0) {
161 this.index = index;
162 } else {
163 throw new SyntaxGraphException("A terminal node must have a positive integer value and not index "+index+". ");
164 }
165 }
166
167 public int getIndex() {
168 return index;
169 }
170
171 public int getCompareToIndex() {
172 return index;
173 }
174
175 public boolean isRoot() {
176 return false;
177 }
178
179 public DependencyNode getAncestor() throws MaltChainedException {
180 if (!this.hasHead()) {
181 return this;
182 }
183
184 DependencyNode tmp = this;
185 while (tmp.hasHead()) {
186 tmp = tmp.getHead();
187 }
188 return tmp;
189 }
190
191 public DependencyNode getProperAncestor() throws MaltChainedException {
192 if (!this.hasHead()) {
193 return null;
194 }
195
196 DependencyNode tmp = this;
197 while (tmp.hasHead()) {
198 tmp = tmp.getHead();
199 }
200 return tmp;
201 }
202
203 public ComparableNode getLeftmostProperDescendant() throws MaltChainedException {
204 ComparableNode candidate = null;
205 ComparableNode tmp = null;
206 for (DependencyNode ldep : leftDependents) {
207 if (candidate == null) {
208 candidate = ldep;
209 } else if (ldep.getIndex() < candidate.getIndex() ) {
210 candidate = ldep;
211 }
212 tmp = ((Token)ldep).getLeftmostProperDescendant();
213 if (tmp == null) {
214 continue;
215 }
216 if (candidate == null) {
217 candidate = tmp;
218 } else if (tmp.getIndex() < candidate.getIndex() ) {
219 candidate = tmp;
220 }
221 if (candidate.getIndex() == 1) {
222 return candidate;
223 }
224 }
225 for (DependencyNode rdep : rightDependents) {
226 if (candidate == null) {
227 candidate = rdep;
228 } else if (rdep.getIndex() < candidate.getIndex() ) {
229 candidate = rdep;
230 }
231 tmp = ((Token)rdep).getLeftmostProperDescendant();
232 if (tmp == null) {
233 continue;
234 }
235 if (candidate == null) {
236 candidate = tmp;
237 } else if (tmp.getIndex() < candidate.getIndex() ) {
238 candidate = tmp;
239 }
240 if (candidate.getIndex() == 1) {
241 return candidate;
242 }
243 }
244 return candidate;
245 }
246
247 public ComparableNode getRightmostProperDescendant() throws MaltChainedException {
248 ComparableNode candidate = null;
249 ComparableNode tmp = null;
250 for (DependencyNode ldep : leftDependents) {
251 if (candidate == null) {
252 candidate = ldep;
253 } else if (ldep.getIndex() > candidate.getIndex() ) {
254 candidate = ldep;
255 }
256 tmp = ((Token)ldep).getRightmostProperDescendant();
257 if (tmp == null) {
258 continue;
259 }
260 if (candidate == null) {
261 candidate = tmp;
262 } else if (tmp.getIndex() > candidate.getIndex() ) {
263 candidate = tmp;
264 }
265 }
266 for (DependencyNode rdep : rightDependents) {
267 if (candidate == null) {
268 candidate = rdep;
269 } else if (rdep.getIndex() > candidate.getIndex() ) {
270 candidate = rdep;
271 }
272 tmp = ((Token)rdep).getRightmostProperDescendant();
273 if (tmp == null) {
274 continue;
275 }
276 if (candidate == null) {
277 candidate = tmp;
278 } else if (tmp.getIndex() > candidate.getIndex() ) {
279 candidate = tmp;
280 }
281 }
282 return candidate;
283 }
284
285 public ComparableNode getLeftmostDescendant() throws MaltChainedException {
286 ComparableNode candidate = this;
287 ComparableNode tmp = null;
288 for (DependencyNode ldep : leftDependents) {
289 if (candidate == null) {
290 candidate = ldep;
291 } else if (ldep.getIndex() < candidate.getIndex() ) {
292 candidate = ldep;
293 }
294 tmp = ((Token)ldep).getLeftmostDescendant();
295 if (tmp == null) {
296 continue;
297 }
298 if (candidate == null) {
299 candidate = tmp;
300 } else if (tmp.getIndex() < candidate.getIndex() ) {
301 candidate = tmp;
302 }
303 if (candidate.getIndex() == 1) {
304 return candidate;
305 }
306 }
307 for (DependencyNode rdep : rightDependents) {
308 if (candidate == null) {
309 candidate = rdep;
310 } else if (rdep.getIndex() < candidate.getIndex() ) {
311 candidate = rdep;
312 }
313 tmp = ((Token)rdep).getLeftmostDescendant();
314 if (tmp == null) {
315 continue;
316 }
317 if (candidate == null) {
318 candidate = tmp;
319 } else if (tmp.getIndex() < candidate.getIndex() ) {
320 candidate = tmp;
321 }
322 if (candidate.getIndex() == 1) {
323 return candidate;
324 }
325 }
326 return candidate;
327 }
328
329 public ComparableNode getRightmostDescendant() throws MaltChainedException {
330 ComparableNode candidate = this;
331 ComparableNode tmp = null;
332 for (DependencyNode ldep : leftDependents) {
333 if (candidate == null) {
334 candidate = ldep;
335 } else if (ldep.getIndex() > candidate.getIndex() ) {
336 candidate = ldep;
337 }
338 tmp = ((Token)ldep).getRightmostDescendant();
339 if (tmp == null) {
340 continue;
341 }
342 if (candidate == null) {
343 candidate = tmp;
344 } else if (tmp.getIndex() > candidate.getIndex() ) {
345 candidate = tmp;
346 }
347 }
348 for (DependencyNode rdep : rightDependents) {
349 if (candidate == null) {
350 candidate = rdep;
351 } else if (rdep.getIndex() > candidate.getIndex() ) {
352 candidate = rdep;
353 }
354 tmp = ((Token)rdep).getRightmostDescendant();
355 if (tmp == null) {
356 continue;
357 }
358 if (candidate == null) {
359 candidate = tmp;
360 } else if (tmp.getIndex() > candidate.getIndex() ) {
361 candidate = tmp;
362 }
363 }
364 return candidate;
365 }
366
367 public PhraseStructureNode getParent() {
368 return parent;
369 }
370
371 public Edge getParentEdge() throws MaltChainedException {
372 for (Edge e : incomingEdges) {
373 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
374 return e;
375 }
376 }
377 return null;
378 }
379
380 public String getParentEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
381 for (Edge e : incomingEdges) {
382 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
383 return e.getLabelSymbol(table);
384 }
385 }
386 return null;
387 }
388
389 public int getParentEdgeLabelCode(SymbolTable table) throws MaltChainedException {
390 for (Edge e : incomingEdges) {
391 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
392 return e.getLabelCode(table);
393 }
394 }
395 return -1;
396 }
397
398 public boolean hasParentEdgeLabel(SymbolTable table) throws MaltChainedException {
399 for (Edge e : incomingEdges) {
400 if (e.getSource() == parent && e.getType() == Edge.PHRASE_STRUCTURE_EDGE) {
401 return e.hasLabel(table);
402 }
403 }
404 return false;
405 }
406
407 public boolean hasAtMostOneHead() {
408 return heads.size() <= 1;
409 }
410
411 public boolean hasAncestorInside(int left, int right) throws MaltChainedException {
412 DependencyNode tmp = this;
413 if (tmp.getHead() != null) {
414 tmp = tmp.getHead();
415 if (tmp.getIndex() >= left && tmp.getIndex() <= right) {
416 return true;
417 }
418 }
419 return false;
420 }
421
422 public Set<Edge> getHeadEdges() throws MaltChainedException {
423 return incomingEdges;
424 }
425
426 public Set<DependencyNode> getHeads() throws MaltChainedException {
427 return heads;
428 }
429
430 public boolean hasHead() {
431 return heads.size() != 0;
432 }
433
434 public DependencyNode getHead() throws MaltChainedException {
435 if (heads.size() == 0) {
436 return null;
437 }
438 if (heads.size() == 1) {
439 for (DependencyNode head : heads) {
440 return head;
441 }
442 }
443
444 if (heads.size() > 1) {
445 throw new SyntaxGraphException("The dependency node is multi-headed and it is ambigious to return a single-head dependency node. ");
446 }
447 // heads.first();
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 node;
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 }