public DependencyTreeNode[] readNextTree(BufferedReader reader) 
            throws IOException {
        List<SimpleDependencyTreeNode> nodes =
            new ArrayList<SimpleDependencyTreeNode>();

        // When building the tree, keep track of all the relations seen between
        // the nodes.  The nodes need to be linked by DependencyRelations, which
        // need DependencyTreeNode instances.  However, during parsing, we may
        // encounter a forward reference to a Node not yet created, so the map
        // ensures that the relation will still be added.
        MultiMap<Integer,Duple<Integer,String>> relationsToAdd 
            = new HashMultiMap<Integer,Duple<Integer,String>>();

        StringBuilder sb = new StringBuilder();

        // Read each line in the document to extract the feature set for each
        // word in the sentence.
        int id = 0;
        int offset = 0;
        for (String line = null; ((line = reader.readLine()) != null); ) {
            line = line.trim();

            // If a new line is encountered and no lines have been handled yet,
            // skip all new lines.
            if (line.length() == 0 && nodes.size() == 0)
                continue;

            // If a new line is encountered and lines have already been
            // processed, we have finished processing the entire sentence and
            // can stop.
            if (line.length() == 0)
                break;

            sb.append(line).append("\n");

            // CoNLL formats using tabs between features.
            String[] nodeFeatures = line.split("\t");
            
            // Sanity check that we have enough columns to support parsing
            if (nodeFeatures.length - 1 < idIndex) {
                reader.close();
                throw new IllegalStateException("While parsing, found line with"
                    + " too few columns.  Missing node id columns.  Offending "+
                    "line:\n" + line);
            }

            // Multiple parse trees may be within the same set of lines, so in
            // order for the later parse trees to be linked correctly, we need
            // to create an offset for the parent ids.
            int realId = Integer.parseInt(nodeFeatures[idIndex]);
            if ((realId == 0 && nodes.size() != offset) ||
                (realId == 1 &&
                 nodes.size() != offset && nodes.size() != offset+1))
                offset = nodes.size();

            // Get the node id and the parent node id.
            int parent =
                Integer.parseInt(nodeFeatures[parentIndex]) - 1 + offset;

            String word = getWord(nodeFeatures);

            String lemma = getLemma(nodeFeatures, word);

            // Get the part of speech of the node.
            String pos = nodeFeatures[posIndex];

            // Get the relation between this node and it's head node.
            String rel = nodeFeatures[relationIndex];

            // Create the new relation.
            SimpleDependencyTreeNode curNode = 
                new SimpleDependencyTreeNode(word, pos, lemma, id);

            // Set the dependency link between this node and it's parent node.
            // If the parent's real index  is negative then the node itself is a
            // root node and has no parent.
            if (parent - offset > 0) {
                // If the parent has already been seen, add the relation
                // directly.
                if (parent < nodes.size()) {
                    SimpleDependencyTreeNode parentNode = nodes.get(parent);
                    DependencyRelation r = new SimpleDependencyRelation(
                        parentNode, rel, curNode);
                    parentNode.addNeighbor(r);
                    curNode.addNeighbor(r);
                }
                // Otherwise, we'll fill in this link once the tree is has been
                // fully seen.
                else { 
                    relationsToAdd.put(id,
                        new Duple<Integer,String>(parent, rel));
                }
            }
            
            // Finally, add the current node to the
            nodes.add(curNode);
            id++;
        }

        if (nodes.size() == 0)
            return null;

        if (relationsToAdd.size() > 0) {
            // Process all the child links that were not handled during the
            // processing of the words.
            for (Map.Entry<Integer,Duple<Integer,String>> parentAndRel :
                     relationsToAdd.entrySet()) {
                SimpleDependencyTreeNode dep = nodes.get(parentAndRel.getKey());
                Duple<Integer,String> d = parentAndRel.getValue();
                SimpleDependencyTreeNode head = nodes.get(d.x);
                DependencyRelation r = new SimpleDependencyRelation(
                    head, d.y, dep);
                head.addNeighbor(r);
                dep.addNeighbor(r);                
            }
        }

        return nodes.toArray(
                new SimpleDependencyTreeNode[nodes.size()]);
    }
public DependencyTreeNode [ ] readNextTree ( BufferedReader reader ) throws IOException { List < SimpleDependencyTreeNode > nodes = new ArrayList < SimpleDependencyTreeNode > ( ) ; MultiMap < Integer , Duple < Integer , String > > relationsToAdd = new HashMultiMap < Integer , Duple < Integer , String > > ( ) ; StringBuilder sb = new StringBuilder ( ) ; int id = 0 ; int offset = 0 ; for ( String line = null ; ( ( line = reader . readLine ( ) ) != null ) ; ) { line = line . trim ( ) ; if ( line . length ( ) == 0 && nodes . size ( ) == 0 ) continue ; if ( line . length ( ) == 0 ) break ; sb . append ( line ) . append ( "\n" ) ; String [ ] nodeFeatures = line . split ( "\t" ) ; if ( nodeFeatures . length - 1 < idIndex ) { reader . close ( ) ; throw new IllegalStateException ( "While parsing, found line with" + " too few columns.  Missing node id columns.  Offending " + "line:\n" + line ) ; } int realId = Integer . parseInt ( nodeFeatures [ idIndex ] ) ; if ( ( realId == 0 && nodes . size ( ) != offset ) || ( realId == 1 && nodes . size ( ) != offset && nodes . size ( ) != offset + 1 ) ) offset = nodes . size ( ) ; int parent = Integer . parseInt ( nodeFeatures [ parentIndex ] ) - 1 + offset ; String word = getWord ( nodeFeatures ) ; String lemma = getLemma ( nodeFeatures , word ) ; String pos = nodeFeatures [ posIndex ] ; String rel = nodeFeatures [ relationIndex ] ; SimpleDependencyTreeNode curNode = new SimpleDependencyTreeNode ( word , pos , lemma , id ) ; if ( parent - offset > 0 ) { if ( parent < nodes . size ( ) ) { SimpleDependencyTreeNode parentNode = nodes . get ( parent ) ; DependencyRelation r = new SimpleDependencyRelation ( parentNode , rel , curNode ) ; parentNode . addNeighbor ( r ) ; curNode . addNeighbor ( r ) ; } else { relationsToAdd . put ( id , new Duple < Integer , String > ( parent , rel ) ) ; } } nodes . add ( curNode ) ; id ++ ; } if ( nodes . size ( ) == 0 ) return null ; if ( relationsToAdd . size ( ) > 0 ) { for ( Map . Entry < Integer , Duple < Integer , String > > parentAndRel : relationsToAdd . entrySet ( ) ) { SimpleDependencyTreeNode dep = nodes . get ( parentAndRel . getKey ( ) ) ; Duple < Integer , String > d = parentAndRel . getValue ( ) ; SimpleDependencyTreeNode head = nodes . get ( d . x ) ; DependencyRelation r = new SimpleDependencyRelation ( head , d . y , dep ) ; head . addNeighbor ( r ) ; dep . addNeighbor ( r ) ; } } return nodes . toArray ( new SimpleDependencyTreeNode [ nodes . size ( ) ] ) ; }
Extracts a dependency parse tree from the provided reader.  The tree is
assumed to be in the CoNLL format.

</p>

The CoNNLL features that are of interest are ID, LEMMA or FORM, POSTAG,
HEAD, and DEPREL which are the id of the node, the string for the word at
this position, the part of speech tag, the parent of this node, and the
relation to the parent, respectively.  These features will be extracted
and returned as an array based tree structure ordered by the occurrence
of the words in the sentence.

@param reader a reader containing one or more parse trees in the CoNLL
format

@return an array of {@link DependencyTreeNode}s that compose a dependency
tree, or {@code null} if no tree is present in the reader.

@throws IOException when errors are encountered during reading