    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    }