gt: 				LabeledSpan childSpan = (LabeledSpan) childSpans.get (i);
context: /* Copyright (C) 2003 Univ. of Massachusetts Amherst, Computer Science Dept.
     This file is part of "MALLET" (MAchine Learning for LanguagE Toolkit).
     http://www.cs.umass.edu/~mccallum/mallet
     This software is provided under the terms of the Common Public License,
     version 1.0, as published by http://www.opensource.org.  For further
     information, see the file `LICENSE' included with this distribution. */
  package cc.mallet.extract;
  
  import cc.mallet.types.*;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  import java.util.Formatter;
  
  import com.carrotsearch.hppc.ObjectObjectHashMap;
  
  /**
   * Created: Oct 12, 2004
   *
   * @author <A HREF="mailto:casutton@cs.umass.edu>casutton@cs.umass.edu</A>
   * @version $Id: DocumentExtraction.java,v 1.1 2007/10/22 21:37:44 mccallum Exp $
   */
  //TODO: Add place where user can have general Transducers to change CRF tokenization into LabeledSpans
  //TODO: Add field for CRF's labeled tokenization
  public class DocumentExtraction implements Serializable {
  
  	private Tokenization input;
  	private Sequence predictedLabels;
  	private LabelSequence target;
  
  	private LabeledSpans extractedSpans;
  	private LabeledSpans targetSpans;
  
  	private Object document;
  	private Label backgroundTag;
  	private String name;
  
  
  	public DocumentExtraction (String name, LabelAlphabet dict, Tokenization input, Sequence predicted, String background) {
  		this (name, dict, input, predicted, null, background, new BIOTokenizationFilter ());
  	}
  
  	public DocumentExtraction (String name, LabelAlphabet dict, Tokenization input, Sequence predicted,
  							   Sequence target, String background) {
  		this (name, dict, input, predicted, target, background, new BIOTokenizationFilter ());
  	}
  
  	public DocumentExtraction (String name, LabelAlphabet dict, Tokenization input,
  							   Sequence predicted, Sequence target, String background,
  							   TokenizationFilter filter) {
  
  		this.document = input.getDocument ();
  		this.name = name;
  		assert (input.size() == predicted.size());
  
  		this.backgroundTag = dict.lookupLabel (background);
  		this.input = input;
  
  		this.predictedLabels = predicted;
  		this.extractedSpans = filter.constructLabeledSpans (dict, document, backgroundTag, input, predicted);
  
  		if (target != null) {
  			if (target instanceof LabelSequence) this.target = (LabelSequence) target;
  			this.targetSpans = filter.constructLabeledSpans (dict, document, backgroundTag, input, target);
  		}
  
  	}
  
  	public DocumentExtraction (String name, LabelAlphabet dict, Tokenization input,
  							   LabeledSpans predictedSpans, LabeledSpans trueSpans, String background) {
  
  		this.document = input.getDocument ();
  		this.name = name;
  
  		this.backgroundTag = dict.lookupLabel (background);
  		this.input = input;
  
  		this.extractedSpans = predictedSpans;
  		this.targetSpans = trueSpans;
  	}
  
  
  
  	public Object getDocument () {
  		return document;
  	}
  
  	public Tokenization getInput () {
  		return input;
  	}
  
  
  	public Sequence getPredictedLabels () {
  		return predictedLabels;
  	}
  
  
  	public LabeledSpans getExtractedSpans () {
  		return extractedSpans;
  	}
  
  	public LabeledSpans getTargetSpans () {
  		return targetSpans;
  	}
  
  	public LabelSequence getTarget () {
  		return target;
  	}
  
  
  	public String getName () {
  		return name;
  	}
  
  	public Label getBackgroundTag () {
  		return backgroundTag;
  	}
  
  	//xxx nyi
  	public Span subspan (int start, int end) {
  		throw new UnsupportedOperationException ("not yet implemented.");
  	}
  
  
  	public Element toXmlDocument () {
  		return toXmlDocument ("doc", null);
  	}
  
  	/*
  	  public Document toXmlDocument (String rootEltName, Namespace ns)
  	  {
  	  Element element = new Element (rootEltName, ns);
  	  for (int i = 0; i < extractedSpans.size(); i++) {
  	  LabeledSpan span = (LabeledSpan) extractedSpans.get(i);
  	  Label tag = span.getLabel();
  	  if (tag == backgroundTag) {
  	  org.jdom.Parent p = element.addContent (span.getText ());
  	  } else {
  	  Element field = new Element (tag.toString(), ns);
  	  field.setText (span.getText ());
  	  element.addContent (field);
  	  }
  	  }
  	  return new Document (element);
  	  }
  	*/
  
  	// does not do non-overlap sanity checking
  	// "Namespace" parameter is a no-op left over for compatibility. It was ignored anyway.
  	public Element toXmlDocument (String rootEltName, Object ns) {
  		ArrayList orderedByStart = new ArrayList (extractedSpans);
  		Collections.sort (orderedByStart, new Comparator () {
  				public int compare (Object o, Object o1)
  				{
  					int start1 = ((Span)o).getStartIdx ();
  					int start2 = ((Span)o1).getStartIdx ();
  					return Double.compare (start1, start2);
  				}
  			} );
  
  		ArrayList roots = new ArrayList (orderedByStart);
  		ObjectObjectHashMap children = new ObjectObjectHashMap ();
  		for (int i = 0; i < orderedByStart.size(); i++) {
  			LabeledSpan child = (LabeledSpan) orderedByStart.get (i);
  			for (int j = i-1; j >= 0; j--) {
  				LabeledSpan parent = (LabeledSpan) orderedByStart.get (j);
  				if (parent.isSubspan (child)) {
  					List childList = (List) children.get (parent);
  					if (childList == null) {
  						childList = new ArrayList ();
  						children.put (parent, childList);
  					}
  					roots.remove (child);
  					childList.add (child);
  					break;
  				}
  			}
  		}
  
  		CharSequence doc = (CharSequence) document;
  		Span wholeDoc = new StringSpan (doc, 0, doc.length ());
  
  		return generateElement (rootEltName, wholeDoc, roots, children);
  	}
  
  
  	private Element generateElement (String parentName, Span span, List childSpans, ObjectObjectHashMap tree) {
  		Element parentElt = new Element (parentName);
  		if (childSpans == null || childSpans.isEmpty ()) {
  			parentElt.setContent (new Text (span.getText ()));
  		} else {
  			List childElts = new ArrayList (childSpans.size());
  			int start = span.getStartIdx ();
  			int current = 0;
  			for (int i = 0; i < childSpans.size(); i++) {
  