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 (!hasHead()) {
436 return null;
437 }
438 if (heads.size() > 1) {
439 throw new SyntaxGraphException("The dependency node is multi-headed and it is ambigious to return a single-head dependency node. ");
440 }
441 // heads.first();
442 for (DependencyNode head : heads) {
443 return head;
444 }
445 return null;
446 }
447
448 public Edge getHeadEdge() throws MaltChainedException {
449 if (heads.size() == 0) {
450 return null;
451 }
452 if (incomingEdges.size() == 1 && incomingEdges.first() instanceof DependencyNode) {
453 return incomingEdges.first();
454 }
455 if (heads.size() == 1) {
456 for (Edge e : incomingEdges) {
457 if (e.getSource() == heads.first()) {
458 return e;
459 }
460 }
461 }
462 return null;
463 }
464
465 public void addHeadEdgeLabel(SymbolTable table, String symbol) throws MaltChainedException {
466 if (hasHead()) {
467 getHeadEdge().addLabel(table, symbol);
468 }
469 }
470
471 public void addHeadEdgeLabel(SymbolTable table, int code) throws MaltChainedException {
472 if (hasHead()) {
473 getHeadEdge().addLabel(table, code);
474 }
475 }
476
477 public void addHeadEdgeLabel(LabelSet labelSet) throws MaltChainedException {
478 if (hasHead()) {
479 getHeadEdge().addLabel(labelSet);
480 }
481 }
482
483 public boolean hasHeadEdgeLabel(SymbolTable table) throws MaltChainedException {
484 if (!hasHead()) {
485 return false;
486 }
487 return getHeadEdge().hasLabel(table);
488 }
489
490 public String getHeadEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
491 return getHeadEdge().getLabelSymbol(table);
492 }
493
494 public int getHeadEdgeLabelCode(SymbolTable table) throws MaltChainedException {
495 if (!hasHead()) {
496 return 0;
497 }
498 return getHeadEdge().getLabelCode(table);
499 }
500
501 public boolean isHeadEdgeLabeled() throws MaltChainedException {
502 if (!hasHead()) {
503 return false;
504 }
505 return getHeadEdge().isLabeled();
506 }
507
508 public int nHeadEdgeLabels() throws MaltChainedException {
509 if (!hasHead()) {
510 return 0;
511 }
512 return getHeadEdge().nLabels();
513 }
514
515 public Set<SymbolTable> getHeadEdgeLabelTypes() throws MaltChainedException {
516 return getHeadEdge().getLabelTypes();
517 }
518
519 public LabelSet getHeadEdgeLabelSet() throws MaltChainedException {
520 return getHeadEdge().getLabelSet();
521 }
522
523 public boolean hasDependent() {
524 return hasLeftDependent() || hasRightDependent();
525 }
526
527 /**
528 * Returns <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
529 *
530 * @return <code>true</code> if the node has one or more left dependents, otherwise <code>false</code>.
531 */
532 public boolean hasLeftDependent() {
533 return !leftDependents.isEmpty();
534 }
535
536 /**
537 * Returns the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent.
538 *
539 * @param index the index
540 * @return the left dependent at the position <code>index</code>, where <code>index==0</code> equals the left most dependent
541 */
542 public DependencyNode getLeftDependent(int index) {
543 if (0 <= index && index < leftDependents.size()) {
544 int i = 0;
545 DependencyNode candidate = null;
546
547 for (DependencyNode node : leftDependents) {
548 candidate = node;
549 if (i == index) {
550 return candidate;
551 }
552 i++;
553 }
554 }
555 return null;
556 }
557
558 /**
559 * Return the number of left dependents
560 *
561 * @return the number of left dependents
562 */
563 public int getLeftDependentCount() {
564 return leftDependents.size();
565 }
566
567 public SortedSet<DependencyNode> getLeftDependents() {
568 return leftDependents;
569 }
570
571 /**
572 * Returns the left sibling if it exists, otherwise <code>null</code>
573 *
574 * @return the left sibling if it exists, otherwise <code>null</code>
575 */
576 public DependencyNode getLeftSibling() throws MaltChainedException {
577 if (getHead() == null) {
578 return null;
579 }
580
581 DependencyNode candidate = null;
582 for (DependencyNode node : getHead().getLeftDependents()) {
583 if (node == this) {
584 return candidate;
585 }
586 candidate = node;
587 }
588 for (DependencyNode node : getHead().getRightDependents()) {
589 if (node == this) {
590 return candidate;
591 }
592 candidate = node;
593 }
594 return null;
595 }
596
597 /**
598 * Returns the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
599 *
600 * @return the left sibling at the same side of head as the node it self. If not found <code>null</code is returned
601 */
602 public DependencyNode getSameSideLeftSibling() throws MaltChainedException {
603 if (getHead() == null) {
604 return null;
605 } else if (this.getIndex() < getHead().getIndex()) {
606 try {
607 return getHead().getLeftDependents().headSet(this).last();
608 } catch (NoSuchElementException e) {
609 return null;
610 }
611 } else if (this.getIndex() > getHead().getIndex()) {
612 try {
613 return getHead().getRightDependents().headSet(this).last();
614 } catch (NoSuchElementException e) {
615 return null;
616 }
617 }
618 return null;
619 }
620
621 /**
622 * Returns the closest left dependent to the node it self, if not found <code>null</code> is returned.
623 *
624 * @return the closest left dependent to the node it self, if not found <code>null</code> is returned.
625 */
626 public DependencyNode getClosestLeftDependent() {
627 try {
628 return leftDependents.last();
629 } catch (NoSuchElementException e) {
630 return null;
631 }
632 }
633
634 public DependencyNode getLeftmostDependent() {
635 for (DependencyNode dep : leftDependents) {
636 return dep;
637 }
638 return null;
639 // try {
640 // return leftDependents.first();
641 // } catch (NoSuchElementException e) {
642 // return null;
643 // }
644 }
645
646 public DependencyNode getRightDependent(int index) {
647 int size = rightDependents.size();
648 if (index < size) {
649 return rightDependents.toArray(new DependencyNode[size])[size - 1 - index];
650 }
651 return null;
652 // if (0 <= index && index < rightDependents.size()) {
653 // int i = 0;
654 // DependencyNode candidate = null;
655 //
656 // for (DependencyNode node : rightDependents) {
657 // candidate = node;
658 // if (i == index) {
659 // return candidate;
660 // }
661 // i++;
662 // }
663 // }
664 // return null;
665 }
666
667 /**
668 * Return the number of right dependents
669 *
670 * @return the number of right dependents
671 */
672 public int getRightDependentCount() {
673 return rightDependents.size();
674 }
675
676 /**
677 * Returns a sorted set of right dependents.
678 *
679 * @return a sorted set of right dependents.
680 */
681 public SortedSet<DependencyNode> getRightDependents() {
682 return rightDependents;
683 }
684
685 /**
686 * Returns the right sibling if it exists, otherwise <code>null</code>
687 *
688 * @return the right sibling if it exists, otherwise <code>null</code>
689 */
690 public DependencyNode getRightSibling() throws MaltChainedException {
691 if (getHead() == null) {
692 return null;
693 }
694
695 for (DependencyNode node : getHead().getLeftDependents()) {
696 if (node.getIndex() > this.getIndex()) {
697 return node;
698 }
699 }
700 for (DependencyNode node : getHead().getRightDependents()) {
701 if (node.getIndex() > this.getIndex()) {
702 return node;
703 }
704 }
705 return null;
706 }
707
708 /**
709 * Returns the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
710 *
711 * @return the right sibling at the same side of head as the node it self. If not found <code>null</code is returned
712 */
713 public DependencyNode getSameSideRightSibling() throws MaltChainedException {
714 if (getHead() == null) {
715 return null;
716 } else if (this.getIndex() < getHead().getIndex()) {
717 final SortedSet<DependencyNode> tailSet = getHead().getLeftDependents().tailSet(this);
718 if (tailSet.size() <= 1) {
719 return null;
720 }
721 return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
722 } else if (this.getIndex() > getHead().getIndex()) {
723 final SortedSet<DependencyNode> tailSet = getHead().getRightDependents().tailSet(this);
724 if (tailSet.size() <= 1) {
725 return null;
726 }
727 return tailSet.toArray(new DependencyNode[tailSet.size()])[1];
728 }
729 return null;
730 }
731
732 /**
733 * Returns the closest right dependent to the node it self, if not found <code>null</code> is returned.
734 *
735 * @return the closest right dependent to the node it self, if not found <code>null</code> is returned.
736 */
737 public DependencyNode getClosestRightDependent() {
738 for (DependencyNode dep : rightDependents) {
739 return dep;
740 }
741 return null;
742 // try {
743 // return rightDependents.first();
744 // } catch (NoSuchElementException e) {
745 // return null;
746 // }
747 }
748
749 public DependencyNode getRightmostDependent() {
750 int n = rightDependents.size();
751 int i = 1;
752 for (DependencyNode node : rightDependents) {
753 if (i == n) {
754 return node;
755 }
756 i++;
757 }
758 return null;
759 // try {
760 // return rightDependents.last();
761 // } catch (NoSuchElementException e) {
762 // return null;
763 // }
764 }
765
766 protected void getDependencyDominationSet(SortedSet<DependencyNode> dominationSet) {
767 if (leftDependents.size() > 0 || rightDependents.size() > 0) {
768 dominationSet.addAll(leftDependents);
769 dominationSet.addAll(rightDependents);
770
771 for (DependencyNode node : leftDependents) {
772 ((Token)node).getDependencyDominationSet(dominationSet);
773 }
774 for (DependencyNode node : rightDependents) {
775 ((Token)node).getDependencyDominationSet(dominationSet);
776 }
777 }
778 }
779
780 // private SortedSet<DependencyNode> getDependencyDominationSet() {
781 // SortedSet<DependencyNode> dominationSet = new TreeSet<DependencyNode>();
782 // getDependencyDominationSet(dominationSet);
783 // return dominationSet;
784 // }
785
786
787 /**
788 * Returns <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
789 *
790 * @return <code>true</code> if the node has one or more right dependents, otherwise <code>false</code>.
791 */
792 public boolean hasRightDependent() {
793 return !rightDependents.isEmpty();
794 }
795
796 public boolean isProjective() throws MaltChainedException {
797 if (hasHead() && !getHead().isRoot()) {
798 final DependencyNode head = getHead();
799 if (getHead().getIndex() < this.getIndex()) {
800 TokenNode terminals = ((TokenNode)head);
801 DependencyNode tmp = null;
802 while (true) {
803 if (terminals == null || terminals.getSuccessor() == null) {
804 return false;
805 }
806 if (terminals.getSuccessor() == this) {
807 break;
808 }
809 tmp = terminals = terminals.getSuccessor();
810 while (tmp != this && tmp != head) {
811 if (!tmp.hasHead()) {
812 return false;
813 }
814 tmp = tmp.getHead();
815 }
816 }
817 } else {
818 TokenNode terminals = ((TokenNode)this);
819 DependencyNode tmp = null;
820 while (true) {
821 if (terminals == null || terminals.getSuccessor() == null) {
822 return false;
823 }
824 if (terminals.getSuccessor() == head) {
825 break;
826 }
827 tmp = terminals = terminals.getSuccessor();
828 while (tmp != this && tmp != head) {
829 if (!tmp.hasHead()) {
830 return false;
831 }
832 tmp = tmp.getHead();
833 }
834 }
835 }
836 }
837 return true;
838 }
839
840 public int getDependencyNodeDepth() throws MaltChainedException {
841 DependencyNode tmp = this;
842 int depth = 0;
843 while (tmp.hasHead()) {
844 depth++;
845 tmp = tmp.getHead();
846 }
847 return depth;
848 }
849
850 public void clear() throws MaltChainedException {
851 super.clear();
852 predecessor = null;
853 successor = null;
854 component = this;
855 rank = 0;
856 parent = null;
857 heads.clear();
858 leftDependents.clear();
859 rightDependents.clear();
860 }
861
862 @Override
863 public int compareTo(ComparableNode that) {
864 final int BEFORE = -1;
865 final int EQUAL = 0;
866 final int AFTER = 1;
867 if (this == that) return EQUAL;
868
869 if (that instanceof TokenNode) {
870 if (this.index < that.getCompareToIndex()) return BEFORE;
871 if (this.index > that.getCompareToIndex()) return AFTER;
872 return super.compareTo(that);
873 }
874 if (that instanceof NonTerminalNode) {
875 try {
876 final int thisLCorner = this.index;
877 final int thatLCorner = that.getLeftmostProperDescendantIndex();
878 final int thisRCorner = this.index;
879 final int thatRCorner = that.getRightmostProperDescendantIndex();
880
881 // if (thisLCorner == -1 || thatLCorner == -1) {
882 // if (thisRCorner < thatRCorner) return BEFORE;
883 // if (thisRCorner > thatRCorner) return AFTER;
884 // }
885 // if (thisRCorner == -1 || thatRCorner == -1) {
886 // if (thisLCorner < thatLCorner) return BEFORE;
887 // if (thisLCorner > thatLCorner) return AFTER;
888 // }
889
890 if (thisLCorner != -1 && thatLCorner != -1 && thisRCorner != -1 && thatRCorner != -1) {
891 if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
892 if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
893 if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
894 if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
895 } else {
896 if (thisLCorner != -1 && thatLCorner != -1) {
897 if (thisLCorner < thatLCorner) return BEFORE;
898 if (thisLCorner > thatLCorner) return AFTER;
899 }
900 if (thisRCorner != -1 && thatRCorner != -1) {
901 if (thisRCorner < thatRCorner) return BEFORE;
902 if (thisRCorner > thatRCorner) return AFTER;
903 }
904 }
905
906
907
908 // final int thisLCorner = this.index;
909 // final int thatLCorner = that.getLeftmostDescendantIndex();
910 // final int thisRCorner = this.index;
911 // final int thatRCorner = that.getRightmostDescendantIndex();
912 //
913 // if (thisLCorner == -1 || thatLCorner == -1) {
914 // if (thisRCorner < thatRCorner) return BEFORE;
915 // if (thisRCorner > thatRCorner) return AFTER;
916 // }
917 // if (thisRCorner == -1 || thatRCorner == -1) {
918 // if (thisLCorner < thatLCorner) return BEFORE;
919 // if (thisLCorner > thatLCorner) return AFTER;
920 // }
921 // if (thisLCorner < thatLCorner && thisRCorner < thatRCorner) return BEFORE;
922 // if (thisLCorner > thatLCorner && thisRCorner > thatRCorner) return AFTER;
923 // if (thisLCorner > thatLCorner && thisRCorner < thatRCorner) return BEFORE;
924 // if (thisLCorner < thatLCorner && thisRCorner > thatRCorner) return AFTER;
925
926
927
928 // int corner = that.getLeftmostDescendantIndex();
929 // if (corner != -1) {
930 // if (this.index < corner) return BEFORE;
931 // if (this.index > corner) return AFTER;
932 // }
933 // corner = that.getRightmostDescendantIndex();
934 // if (corner != -1) {
935 // if (this.index < corner) return BEFORE;
936 // if (this.index > corner) return AFTER;
937 // }
938 } catch (MaltChainedException e) {
939 if (SystemLogger.logger().isDebugEnabled()) {
940 SystemLogger.logger().debug("",e);
941 } else {
942 SystemLogger.logger().error(e.getMessageChain());
943 }
944 System.exit(1);
945 }
946 }
947 if (this.index < that.getCompareToIndex()) return BEFORE;
948 if (this.index > that.getCompareToIndex()) return AFTER;
949 return super.compareTo(that);
950 }
951
952 public boolean equals(Object obj) {
953 Token v = (Token)obj;
954 if (!(this.predecessor == v.predecessor && this.successor == v.successor)) return false;
955 return super.equals(obj);
956 }
957
958 public int hashCode() {
959 int hash = 7;
960 hash = 31 * hash + (null == predecessor ? 0 : predecessor.hashCode());
961 hash = 31 * hash + (null == successor ? 0 : successor.hashCode());
962 return 31 * hash + super.hashCode();
963 }
964
965
966 public String toString() {
967 final StringBuilder sb = new StringBuilder();
968 sb.append(super.toString());
969 return sb.toString();
970 }
971 }