001package org.maltparser.core.lw.graph;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.HashSet;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Set;
009import java.util.SortedMap;
010import java.util.SortedSet;
011import java.util.TreeMap;
012import java.util.TreeSet;
013
014import org.maltparser.concurrent.graph.dataformat.ColumnDescription;
015import org.maltparser.core.exception.MaltChainedException;
016import org.maltparser.core.symbol.SymbolTable;
017import org.maltparser.core.symbol.SymbolTableHandler;
018import org.maltparser.core.syntaxgraph.DependencyStructure;
019import org.maltparser.core.syntaxgraph.LabelSet;
020import org.maltparser.core.syntaxgraph.LabeledStructure;
021import org.maltparser.core.syntaxgraph.edge.Edge;
022import org.maltparser.core.syntaxgraph.node.ComparableNode;
023import org.maltparser.core.syntaxgraph.node.DependencyNode;
024import org.maltparser.core.syntaxgraph.node.Node;
025
026/**
027* A lightweight version of org.maltparser.core.syntaxgraph.node.{Token,Root}
028* 
029* @author Johan Hall
030*/
031public final class LWNode implements DependencyNode, Node {
032        private final LWDependencyGraph graph;
033        private int index;
034        private final SortedMap<Integer, String> labels;
035        private Edge headEdge;
036        
037        protected LWNode(LWNode node) throws LWGraphException {
038                this(node.graph, node);
039        }
040        
041        protected LWNode(LWDependencyGraph _graph, LWNode node) throws LWGraphException {
042                if (_graph == null) {
043                        throw new LWGraphException("The graph node must belong to a dependency graph.");
044                }
045                this.graph = _graph;
046                this.index = node.index;
047                this.labels = new TreeMap<Integer, String>(node.labels);
048                this.headEdge = node.headEdge;
049        }
050        
051        protected LWNode(LWDependencyGraph _graph, int _index) throws LWGraphException {
052                if (_graph == null) {
053                        throw new LWGraphException("The graph node must belong to a dependency graph.");
054                }
055                if (_index < 0) {
056                        throw new LWGraphException("Not allowed to have negative node index");
057                }
058                this.graph = _graph;
059                this.index = _index;
060                this.labels = new TreeMap<Integer, String>();
061                this.headEdge = null;
062        }
063        
064//      public void setHeadIndex(int _headIndex) throws LWGraphException {
065//              if (this.index == 0 && _headIndex != -1) {
066//                      throw new LWGraphException("Not allowed to add head to a root node.");
067//              }
068//              if (this.index == _headIndex) {
069//                      throw new LWGraphException("Not allowed to add head to itself");
070//              }
071//              this.headIndex = _headIndex;
072//      }
073//      
074//      public void removeHeadIndex() throws LWGraphException {
075//              this.headIndex = -1;
076//              for (Integer i : labels.keySet()) {
077//                      if (graph.getDataFormat().getColumnDescription(i).getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
078//                              this.labels.remove(i);
079//                      }
080//              }
081//      }
082        
083        protected DependencyStructure getGraph() {
084                return graph;
085        }
086        
087        public int getIndex() {
088                return this.index;
089        }
090        
091        @Override
092        public void setIndex(int index) throws MaltChainedException {
093                this.index = index;
094        }
095
096        public String getLabel(int columnPosition) {
097                if (labels.containsKey(columnPosition)) {
098                        return labels.get(columnPosition);
099                } else if (graph.getDataFormat().getColumnDescription(columnPosition).getCategory() == ColumnDescription.IGNORE) {
100                        return graph.getDataFormat().getColumnDescription(columnPosition).getDefaultOutput();
101                }
102                return "";
103        }
104        
105        public String getLabel(String columnName) {
106                ColumnDescription column = graph.getDataFormat().getColumnDescription(columnName);
107                if (column != null) {
108                        return getLabel(column.getPosition());
109                }
110                return "";
111        }
112        
113        public String getLabel(ColumnDescription column) {
114                return getLabel(column.getPosition());
115        }
116        
117        public boolean hasLabel(int columnPosition) {
118                return labels.containsKey(columnPosition);
119        }
120        
121        public boolean hasLabel(String columnName) {
122                ColumnDescription column = graph.getDataFormat().getColumnDescription(columnName);
123                if (column != null) {
124                        return hasLabel(column.getPosition());
125                }
126                return false;
127        }
128        
129        public boolean hasLabel(ColumnDescription column) {
130                return labels.containsKey(column.getPosition());
131        }
132        
133        public boolean isLabeled() {
134                for (Integer key : labels.keySet()) {
135                        if (graph.getDataFormat().getColumnDescription(key).getCategory() == ColumnDescription.INPUT) {
136                                return true;
137                        }
138                }
139                return false;
140        }
141        
142        public boolean isHeadLabeled() {
143                if (headEdge == null) {
144                        return false;
145                }
146                return headEdge.isLabeled();
147        }
148        
149        public int getHeadIndex() {
150                if (headEdge == null) {
151                        return -1;
152                }
153                return headEdge.getSource().getIndex();
154        }
155        
156        public SortedMap<ColumnDescription, String> getLabels() {
157                SortedMap<ColumnDescription, String> nodeLabels = Collections.synchronizedSortedMap(new TreeMap<ColumnDescription, String>());
158                for (Integer key : labels.keySet()) {
159                        nodeLabels.put(graph.getDataFormat().getColumnDescription(key), labels.get(key));
160                }
161                return nodeLabels;
162        }
163        
164//      public SortedMap<ColumnDescription, String> getEdgeLabels() {
165//              SortedMap<ColumnDescription, String> edgeLabels = Collections.synchronizedSortedMap(new TreeMap<ColumnDescription, String>());
166//              for (Integer key : labels.keySet()) {
167//                      if (graph.getDataFormat().getColumnDescription(key).getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
168//                              edgeLabels.put(graph.getDataFormat().getColumnDescription(key), labels.get(key));
169//                      }
170//              }
171//              return edgeLabels;
172//      }
173        
174        public DependencyNode getPredecessor() {
175                return index > 1 ? graph.getNode(index - 1) : null;
176        }
177        
178        public DependencyNode getSuccessor() {
179                return graph.getNode(index + 1);
180        }
181        
182        public boolean isRoot() {
183                return index == 0;
184        }
185        
186        public boolean hasAtMostOneHead() {
187                return true;
188        }
189        
190        public boolean hasHead() {
191                return headEdge != null;
192        }
193        
194        public boolean hasDependent() {
195                return graph.hasDependent(index);
196        }
197        
198        public boolean hasLeftDependent() {
199                return graph.hasLeftDependent(index);
200        }
201        
202        public boolean hasRightDependent() {
203                return graph.hasRightDependent(index);
204        }
205        
206        public SortedSet<DependencyNode> getHeads() {
207                SortedSet<DependencyNode> heads = Collections.synchronizedSortedSet(new TreeSet<DependencyNode>());
208                DependencyNode head = getHead();
209                if (head != null) {
210                        heads.add(head);
211                }
212                return heads; 
213        }
214        
215        public DependencyNode getHead() {
216                if (headEdge == null) {
217                        return null;
218                }
219                return graph.getNode(getHeadIndex());
220        }
221
222        public DependencyNode getLeftDependent(int leftDependentIndex) {        
223                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
224                if (leftDependentIndex >= 0 && leftDependentIndex < leftDependents.size()) {
225                        return leftDependents.get(leftDependentIndex);
226                }
227                return null;
228        }
229
230        public int getLeftDependentCount() {
231                return graph.getListOfLeftDependents(index).size();
232        }
233
234        public SortedSet<DependencyNode> getLeftDependents() {
235                return graph.getSortedSetOfLeftDependents(index);
236        }
237
238        public List<DependencyNode> getListOfLeftDependents() {
239                return graph.getListOfLeftDependents(index);
240        }
241        
242        public DependencyNode getLeftSibling() {
243                if (headEdge == null) {
244                        return null;
245                }
246                
247                int nodeDepedentPosition = 0;
248                List<DependencyNode> headDependents = getHead().getListOfDependents();
249                for (int i = 0; i < headDependents.size(); i++) {
250                        if (headDependents.get(i).getIndex() == index) {
251                                nodeDepedentPosition = i;
252                                break;
253                        }
254                }
255                
256                return (nodeDepedentPosition > 0) ? headDependents.get(nodeDepedentPosition - 1) : null;
257        }
258
259        public DependencyNode getSameSideLeftSibling() {
260                if (headEdge == null) {
261                        return null;
262                }
263                
264                List<DependencyNode> headDependents;
265                if (index < getHeadIndex()) {
266                        headDependents = getHead().getListOfLeftDependents();
267                } else { //(index > headIndex)
268                        headDependents = getHead().getListOfRightDependents();
269                }
270                int nodeDepedentPosition = 0;
271                for (int i = 0; i < headDependents.size(); i++) {
272                        if (headDependents.get(i).getIndex() == index) {
273                                nodeDepedentPosition = i;
274                                break;
275                        }
276                }
277                return (nodeDepedentPosition > 0) ? headDependents.get(nodeDepedentPosition - 1) : null;
278        }
279
280        public DependencyNode getClosestLeftDependent() {
281                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
282                return (leftDependents.size() > 0) ? leftDependents.get(leftDependents.size() - 1) : null;
283        }
284        
285        public DependencyNode getLeftmostDependent() {
286                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
287                return (leftDependents.size() > 0) ? leftDependents.get(0) : null;
288        }
289        
290        public DependencyNode getRightDependent(int rightDependentIndex) {      
291                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
292                if (rightDependentIndex >= 0 && rightDependentIndex < rightDependents.size()) {
293                        return rightDependents.get(rightDependents.size() - 1 - rightDependentIndex);
294                }
295                return null;
296        }
297        
298        public int getRightDependentCount() {
299                return graph.getListOfRightDependents(index).size();
300        }
301
302        public SortedSet<DependencyNode> getRightDependents() {
303                return graph.getSortedSetOfRightDependents(index);
304        }
305
306        public List<DependencyNode> getListOfRightDependents() {
307                return graph.getListOfRightDependents(index);
308        }
309        
310        public DependencyNode getRightSibling() {
311                if (headEdge == null) {
312                        return null;
313                }
314                
315                List<DependencyNode> headDependents = getHead().getListOfDependents();
316                int nodeDepedentPosition = headDependents.size() - 1;
317                for (int i = headDependents.size() - 1; i >= 0 ; i--) {
318                        if (headDependents.get(i).getIndex() == index) {
319                                nodeDepedentPosition = i;
320                                break;
321                        }
322                }
323                
324                return (nodeDepedentPosition < headDependents.size() - 1) ? headDependents.get(nodeDepedentPosition + 1) : null;
325        }
326
327        public DependencyNode getSameSideRightSibling() {
328                if (headEdge == null) {
329                        return null;
330                }
331                
332                List<DependencyNode> headDependents;
333                if (index < getHeadIndex()) {
334                        headDependents = getHead().getListOfLeftDependents();
335                } else {
336                        headDependents = getHead().getListOfRightDependents();
337                }
338                int nodeDepedentPosition = headDependents.size() - 1;
339                for (int i = headDependents.size() - 1; i >= 0 ; i--) {
340                        if (headDependents.get(i).getIndex() == index) {
341                                nodeDepedentPosition = i;
342                                break;
343                        }
344                }
345                
346                return (nodeDepedentPosition < headDependents.size() - 1) ? headDependents.get(nodeDepedentPosition + 1) : null;     
347        }
348
349        public DependencyNode getClosestRightDependent() {
350                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
351                return (rightDependents.size() > 0) ? rightDependents.get(0) : null;
352        }
353        
354        public DependencyNode getRightmostDependent(){
355                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
356                return (rightDependents.size() > 0) ? rightDependents.get(rightDependents.size() - 1) : null;
357        }
358        
359        public SortedSet<DependencyNode> getDependents() {
360                return graph.getSortedSetOfDependents(index);
361        }
362        
363        public List<DependencyNode> getListOfDependents() {
364                return graph.getListOfDependents(index);
365        }
366        
367        public int getInDegree() {
368                if (hasHead()) {
369                        return 1;
370                }
371                return 0;
372        }
373        
374        public int getOutDegree() {
375                return graph.getListOfDependents(index).size();
376        }
377        
378        public DependencyNode getAncestor() throws MaltChainedException {
379                if (!this.hasHead()) {
380                        return this;
381                }
382                
383                DependencyNode tmp = this;
384                while (tmp.hasHead()) {
385                        tmp = tmp.getHead();
386                }
387                return tmp;
388        }
389        
390        public DependencyNode getProperAncestor() throws MaltChainedException {
391                if (!this.hasHead()) {
392                        return null;
393                }
394                
395                DependencyNode tmp = this;
396                while (tmp.hasHead() && !tmp.isRoot()) {
397                        tmp = tmp.getHead();
398                }
399                return tmp;
400        }
401        
402        public boolean hasAncestorInside(int left, int right) throws MaltChainedException {
403                if (index == 0) {
404                        return false;
405                }
406                DependencyNode tmp = this;
407                if (tmp.getHead() != null) {
408                        tmp = tmp.getHead();
409                        if (tmp.getIndex() >= left && tmp.getIndex() <= right) {
410                                return true;
411                        }
412                }
413                return false;
414        }
415        
416        public boolean isProjective() throws MaltChainedException {
417                int headIndex = getHeadIndex();
418                if (headIndex > 0) {
419                        final DependencyNode head = getHead();
420                        if (headIndex < index) {
421                                DependencyNode terminals = head;
422                                DependencyNode tmp = null;
423                                while (true) {
424                                        if (terminals == null || terminals.getSuccessor() == null) {
425                                                return false;
426                                        }
427                                        if (terminals.getSuccessor() == this) {
428                                                break;
429                                        }
430                                        tmp = terminals = terminals.getSuccessor();
431                                        while (tmp != this && tmp != head) {
432                                                if (!tmp.hasHead()) {
433                                                        return false;
434                                                }
435                                                tmp = tmp.getHead();
436                                        }
437                                }
438                        } else {
439                                DependencyNode terminals = this;
440                                DependencyNode tmp = null;
441                                while (true) {
442                                        if (terminals == null || terminals.getSuccessor() == null) {
443                                                return false;
444                                        }
445                                        if (terminals.getSuccessor() == head) {
446                                                break;
447                                        }
448                                        tmp = terminals = terminals.getSuccessor();
449                                        while (tmp != this && tmp != head) {
450                                                if (!tmp.hasHead()) {
451                                                        return false;
452                                                }
453                                                tmp = tmp.getHead();
454                                        }
455                                }
456                        }
457                }
458                return true;
459        }
460        
461        public int getDependencyNodeDepth() throws MaltChainedException {
462                DependencyNode tmp = this;
463                int depth = 0;
464                while (tmp.hasHead()) {
465                        depth++;
466                        tmp = tmp.getHead();
467                }
468                return depth;
469        }
470
471        @Override
472        public int getCompareToIndex() {
473                return index;
474        }
475
476        @Override
477        public ComparableNode getLeftmostProperDescendant() throws MaltChainedException {
478                ComparableNode candidate = null;
479                List<DependencyNode> dependents = graph.getListOfDependents(index);
480                for (int i = 0; i < dependents.size(); i++) {
481                        final DependencyNode dep = dependents.get(i);
482                        if (candidate == null || dep.getIndex() < candidate.getIndex()) {
483                                candidate = dep;
484                        }
485                        final ComparableNode tmp = dep.getLeftmostProperDescendant();
486                        if (tmp == null) {
487                                continue;
488                        }
489                        if (candidate == null || tmp.getIndex() < candidate.getIndex()) {
490                                candidate = tmp;
491                        }
492                        if (candidate.getIndex() == 1) {
493                                return candidate;
494                        }
495                }
496                return candidate;
497        }
498
499        @Override
500        public ComparableNode getRightmostProperDescendant() throws MaltChainedException {
501                ComparableNode candidate = null;
502                List<DependencyNode> dependents = graph.getListOfDependents(index);
503                for (int i = 0; i < dependents.size(); i++) {
504                        final DependencyNode dep = dependents.get(i);
505                        if (candidate == null || dep.getIndex() > candidate.getIndex()) {
506                                candidate = dep;
507                        }
508                        final ComparableNode tmp = dep.getRightmostProperDescendant();
509                        if (tmp == null) {
510                                continue;
511                        }
512                        if (candidate == null || tmp.getIndex() > candidate.getIndex()) {
513                                candidate = tmp;
514                        }
515                }
516                return candidate;
517        }
518        @Override
519        public int getLeftmostProperDescendantIndex() throws MaltChainedException {
520                ComparableNode node = getLeftmostProperDescendant();
521                return (node != null)?node.getIndex():-1;
522        }
523        @Override
524        public int getRightmostProperDescendantIndex() throws MaltChainedException {
525                ComparableNode node = getRightmostProperDescendant();
526                return (node != null)?node.getIndex():-1;
527        }
528
529        @Override
530        public ComparableNode getLeftmostDescendant() throws MaltChainedException {
531                ComparableNode candidate = this;
532                List<DependencyNode> dependents = graph.getListOfDependents(index);
533                for (int i = 0; i < dependents.size(); i++) {
534                        final DependencyNode dep = dependents.get(i);
535                        if (dep.getIndex() < candidate.getIndex()) {
536                                candidate = dep;
537                        }
538                        final ComparableNode tmp = dep.getLeftmostDescendant();
539                        if (tmp == null) {
540                                continue;
541                        }
542                        if (tmp.getIndex() < candidate.getIndex()) {
543                                candidate = tmp;
544                        }
545                        if (candidate.getIndex() == 1) {
546                                return candidate;
547                        }
548                }
549                return candidate;
550        }
551
552        @Override
553        public ComparableNode getRightmostDescendant() throws MaltChainedException {
554                ComparableNode candidate = this;
555                List<DependencyNode> dependents = graph.getListOfDependents(index);
556                for (int i = 0; i < dependents.size(); i++) {
557                        final DependencyNode dep = dependents.get(i);
558                        if (dep.getIndex() > candidate.getIndex() ) {
559                                candidate = dep;
560                        }
561                        final ComparableNode tmp = dep.getRightmostDescendant();
562                        if (tmp == null) {
563                                continue;
564                        }
565                        if (tmp.getIndex() > candidate.getIndex() ) {
566                                candidate = tmp;
567                        }
568                }
569                return candidate;
570        }
571
572        @Override
573        public int getLeftmostDescendantIndex() throws MaltChainedException {
574                ComparableNode node = getLeftmostDescendant();
575                return (node != null)?node.getIndex():this.getIndex();
576        }
577        @Override
578        public int getRightmostDescendantIndex() throws MaltChainedException {
579                ComparableNode node = getRightmostDescendant();
580                return (node != null)?node.getIndex():this.getIndex();
581        }
582
583        @Override
584        public SortedSet<Edge> getIncomingSecondaryEdges() throws MaltChainedException {
585                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
586        }
587
588        @Override
589        public SortedSet<Edge> getOutgoingSecondaryEdges() throws MaltChainedException {
590                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
591        }
592        
593        @Override
594        public Set<Edge> getHeadEdges()  {
595                SortedSet<Edge> edges = Collections.synchronizedSortedSet(new TreeSet<Edge>());
596                if (hasHead()) {
597                        edges.add(headEdge);
598                }
599                return edges;
600        }
601
602        @Override
603        public Edge getHeadEdge() {
604                if (!hasHead()) {
605                        return null;
606                }
607                return headEdge;
608        }
609        
610        @Override
611        public void addHeadEdgeLabel(SymbolTable table, String symbol)
612                        throws MaltChainedException {
613                if (headEdge != null) {
614                        headEdge.addLabel(table, symbol);
615                }
616        }
617
618        @Override
619        public void addHeadEdgeLabel(SymbolTable table, int code) throws MaltChainedException {
620                if (headEdge != null) {
621                        headEdge.addLabel(table, code);
622                }
623        }
624
625        @Override
626        public void addHeadEdgeLabel(LabelSet labelSet) throws MaltChainedException {
627                if (headEdge != null) {
628                        headEdge.addLabel(labelSet);
629                }
630        }
631
632        @Override
633        public boolean hasHeadEdgeLabel(SymbolTable table)
634                        throws MaltChainedException {
635                if (headEdge != null) {
636                        return headEdge.hasLabel(table);
637                }
638                return false;
639        }
640
641        @Override
642        public String getHeadEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
643                if (headEdge != null) {
644                        return headEdge.getLabelSymbol(table);
645                }
646                return null;
647        }
648
649        @Override
650        public int getHeadEdgeLabelCode(SymbolTable table)
651                        throws MaltChainedException {
652                if (headEdge != null) {
653                        return headEdge.getLabelCode(table);
654                }
655                return 0;
656        }
657
658        @Override
659        public Set<SymbolTable> getHeadEdgeLabelTypes() throws MaltChainedException {
660                if (headEdge != null) {
661                        return headEdge.getLabelTypes();
662                }
663                return new HashSet<SymbolTable>();
664        }
665
666        @Override
667        public LabelSet getHeadEdgeLabelSet() throws MaltChainedException {
668                if (headEdge != null) {
669                        return headEdge.getLabelSet();
670                }
671                return new LabelSet();
672        }
673
674        
675        @Override
676        public void addIncomingEdge(Edge in) throws MaltChainedException {
677                headEdge = in;
678        }
679
680        @Override
681        public void addOutgoingEdge(Edge out) throws MaltChainedException {
682                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
683                
684        }
685
686        @Override
687        public void removeIncomingEdge(Edge in) throws MaltChainedException {
688                if (headEdge.equals(in)) {
689                        headEdge = null;
690                }
691        }
692
693        @Override
694        public void removeOutgoingEdge(Edge out) throws MaltChainedException {
695                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
696        }
697
698        @Override
699        public Iterator<Edge> getIncomingEdgeIterator() {
700                return getHeadEdges().iterator();
701        }
702
703        @Override
704        public Iterator<Edge> getOutgoingEdgeIterator() {
705                List<DependencyNode> dependents = getListOfDependents();
706                List<Edge> outEdges = new ArrayList<Edge>(dependents.size());
707                for (int i = 0; i < dependents.size(); i++) {
708                        try {
709                                outEdges.add(dependents.get(i).getHeadEdge());
710                        } catch (MaltChainedException e) {
711                                e.printStackTrace();
712                        }
713                }
714                return outEdges.iterator();
715        }
716
717        @Override
718        public void setRank(int r) {}
719
720        @Override
721        public DependencyNode getComponent() {
722                return null;
723        }
724
725        @Override
726        public void setComponent(DependencyNode x) {}
727
728        public DependencyNode findComponent() {
729                return graph.findComponent(index);
730        }
731        
732        public int getRank() {
733                return graph.getRank(index);
734        }
735        
736        public boolean isHeadEdgeLabeled() {
737                if (headEdge != null) {
738                        return headEdge.isLabeled();
739                }
740                return false;
741        }
742        
743        public int nHeadEdgeLabels() {
744                if (headEdge != null) {
745                        return headEdge.nLabels();
746                }
747                return 0;
748        }
749        
750        public void addColumnLabels(String[] columnLabels) throws MaltChainedException {
751                this.addColumnLabels(columnLabels, true);
752        }
753        
754        public void addColumnLabels(String[] columnLabels, boolean addEdges) throws MaltChainedException {
755                if (addEdges == true) {
756                        SortedMap<ColumnDescription,String> edgeLabels = new TreeMap<ColumnDescription,String>();
757                        int tmpHeadIndex = -1;
758                        if (columnLabels != null) {
759                                for (int i = 0; i < columnLabels.length; i++) {
760                                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
761                                        if (column.getCategory() == ColumnDescription.HEAD) {
762                                                tmpHeadIndex = Integer.parseInt(columnLabels[i]);
763                                        } else if (column.getCategory() == ColumnDescription.INPUT) {
764                                                addLabel(graph.getSymbolTables().addSymbolTable(column.getName()), columnLabels[i]);
765                                        } else if (column.getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
766                                                edgeLabels.put(column, columnLabels[i]);
767                                        }
768                                }
769                        }
770                        if (tmpHeadIndex == -1) {
771                                this.headEdge = null;
772                        } else {
773                                if (tmpHeadIndex < -1) {
774                                        throw new LWGraphException("Not allowed to have head index less than -1.");
775                                }
776                                if (this.index == 0 && tmpHeadIndex != -1) {
777                                        throw new LWGraphException("Not allowed to add head to a root node.");
778                                }
779                                if (this.index == tmpHeadIndex) {
780                                        throw new LWGraphException("Not allowed to add head to itself");
781                                }
782                                this.headEdge = new LWEdge(this.graph.getNode(tmpHeadIndex), this, edgeLabels);
783                        }
784                } else {
785                        if (columnLabels != null) {
786                                for (int i = 0; i < columnLabels.length; i++) {
787                                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
788                                        if (column.getCategory() == ColumnDescription.INPUT) {
789                                                addLabel(graph.getSymbolTables().addSymbolTable(column.getName()), columnLabels[i]);
790                                        } 
791                                }
792                        }
793                        this.headEdge = null;
794                }
795        }
796        
797        /**
798         * Adds a label (a string value) to the symbol table and to the graph element. 
799         * 
800         * @param table the symbol table
801         * @param symbol a label symbol
802         * @throws MaltChainedException
803         */
804        public void addLabel(SymbolTable table, String symbol) throws MaltChainedException {
805                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
806                table.addSymbol(symbol);
807                labels.put(column.getPosition(), symbol);
808        }
809        
810        /**
811         * Adds a label (an integer value) to the symbol table and to the graph element.
812         * 
813         * @param table the symbol table
814         * @param code a label code
815         * @throws MaltChainedException
816         */
817        public void addLabel(SymbolTable table, int code) throws MaltChainedException {
818                addLabel(table, table.getSymbolCodeToString(code));
819        }
820        
821        /**
822         * Adds the labels of the label set to the label set of the graph element.
823         * 
824         * @param labels a label set.
825         * @throws MaltChainedException
826         */
827        public void addLabel(LabelSet labels) throws MaltChainedException {
828                for (SymbolTable table : labels.keySet()) {
829                        addLabel(table, labels.get(table));
830                }
831        }
832        
833        /**
834         * Returns <i>true</i> if the graph element has a label for the symbol table, otherwise <i>false</i>.
835         * 
836         * @param table the symbol table
837         * @return <i>true</i> if the graph element has a label for the symbol table, otherwise <i>false</i>.
838         * @throws MaltChainedException
839         */
840        public boolean hasLabel(SymbolTable table) throws MaltChainedException {
841                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
842                return labels.containsKey(column.getPosition());
843        }
844        
845        /**
846         * Returns the label symbol(a string representation) of the symbol table if it exists, otherwise 
847         * an exception is thrown.
848         * 
849         * @param table the symbol table
850         * @return the label (a string representation) of the symbol table if it exists.
851         * @throws MaltChainedException
852         */
853        public String getLabelSymbol(SymbolTable table) throws MaltChainedException {
854                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
855                return labels.get(column.getPosition());
856        }
857        
858        /**
859         * Returns the label code (an integer representation) of the symbol table if it exists, otherwise 
860         * an exception is thrown.
861         * 
862         * @param table the symbol table
863         * @return the label code (an integer representation) of the symbol table if it exists
864         * @throws MaltChainedException
865         */
866        public int getLabelCode(SymbolTable table) throws MaltChainedException {
867                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
868                return table.getSymbolStringToCode(labels.get(column.getPosition()));
869        }
870        
871        /**
872         * Returns the number of labels of the graph element.
873         * 
874         * @return the number of labels of the graph element.
875         */
876        public int nLabels() {
877                return labels.size();
878        }
879        
880        /**
881         * Returns a set of symbol tables (labeling functions or label types) that labels the graph element.
882         * 
883         * @return a set of symbol tables (labeling functions or label types)
884         */
885        public Set<SymbolTable> getLabelTypes() {
886                Set<SymbolTable> labelTypes = new HashSet<SymbolTable>();
887                SymbolTableHandler symbolTableHandler = getBelongsToGraph().getSymbolTables();
888                SortedSet<ColumnDescription> selectedColumns = graph.getDataFormat().getSelectedColumnDescriptions(labels.keySet());
889                for (ColumnDescription column : selectedColumns) {
890                        try {
891                                labelTypes.add(symbolTableHandler.getSymbolTable(column.getName()));
892                        } catch (MaltChainedException e) {
893                                e.printStackTrace();
894                        }
895                }
896                return labelTypes;
897        }
898        
899        /**
900         * Returns the label set.
901         * 
902         * @return the label set.
903         */
904        public LabelSet getLabelSet() {
905                SymbolTableHandler symbolTableHandler = getBelongsToGraph().getSymbolTables();
906                LabelSet labelSet = new LabelSet();
907                SortedSet<ColumnDescription> selectedColumns = graph.getDataFormat().getSelectedColumnDescriptions(labels.keySet());
908                for (ColumnDescription column : selectedColumns) {
909                        try {
910                                SymbolTable table = symbolTableHandler.getSymbolTable(column.getName());
911                                int code = table.getSymbolStringToCode(labels.get(column.getPosition()));
912                                labelSet.put(table, code);
913                        } catch (MaltChainedException e) {
914                                e.printStackTrace();
915                        }
916                }
917                return labelSet;
918        }
919        
920        public void removeLabel(SymbolTable table) throws MaltChainedException {
921                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
922                labels.remove(column.getPosition());
923        }
924        
925        public void removeLabels() throws MaltChainedException {
926                labels.clear();
927        }
928        
929        /**
930         * Returns the graph (structure) in which the graph element belongs to. 
931         * 
932         * @return the graph (structure) in which the graph element belongs to. 
933         */
934        public LabeledStructure getBelongsToGraph()  {
935                return graph;
936        }
937        
938        public void setBelongsToGraph(LabeledStructure belongsToGraph)  {}
939        
940
941        /**
942         * Resets the graph element.
943         * 
944         * @throws MaltChainedException
945         */
946        public void clear() throws MaltChainedException {
947                labels.clear();
948        }
949        
950        @Override
951        public int compareTo(ComparableNode that) {
952                final int BEFORE = -1;
953            final int EQUAL = 0;
954            final int AFTER = 1;
955            if (this == that) return EQUAL;
956            if (this.index < that.getIndex()) return BEFORE;
957            if (this.index > that.getIndex()) return AFTER;
958            return EQUAL;
959        }
960
961        @Override
962        public int hashCode() {
963                final int prime = 31;
964                int result = 1;
965                result = prime * result
966                                + ((headEdge == null) ? 0 : headEdge.hashCode());
967                result = prime * result + index;
968                result = prime * result + ((labels == null) ? 0 : labels.hashCode());
969                return result;
970        }
971
972        @Override
973        public boolean equals(Object obj) {
974                if (this == obj)
975                        return true;
976                if (obj == null)
977                        return false;
978                if (getClass() != obj.getClass())
979                        return false;
980                LWNode other = (LWNode) obj;
981                if (headEdge == null) {
982                        if (other.headEdge != null)
983                                return false;
984                } else if (!headEdge.equals(other.headEdge))
985                        return false;
986                if (index != other.index)
987                        return false;
988                if (labels == null) {
989                        if (other.labels != null)
990                                return false;
991                } else if (!labels.equals(other.labels))
992                        return false;
993                return true;
994        }
995
996        public String toString() {
997                final StringBuilder sb = new StringBuilder();
998                for (int i = 0; i < graph.getDataFormat().numberOfColumns(); i++) {
999                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
1000                        if (!column.isInternal()) {
1001                                if (column.getCategory() == ColumnDescription.HEAD) {
1002                                        sb.append(getHeadIndex());
1003                                } else if (column.getCategory() == ColumnDescription.INPUT) {
1004                                        sb.append(labels.get(column.getPosition()));
1005                                } else if (column.getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
1006                                        if (headEdge != null) {
1007                                                sb.append(((LWEdge)headEdge).getLabel(column));
1008                                        } else {
1009                                                sb.append(column.getDefaultOutput());
1010                                        }
1011                                } else if (column.getCategory() == ColumnDescription.IGNORE) {
1012                                        sb.append(column.getDefaultOutput());
1013                                }
1014                                sb.append('\t');
1015                        }
1016                }
1017                sb.setLength((sb.length() > 0)?sb.length()-1:0);
1018                return sb.toString();
1019        }
1020}