public class XmidComparator implements Comparator<GenericSegment>
	{
		public int compare(GenericSegment obj1, GenericSegment obj2)
		{
			// sorts in x order
			double x1 = obj1.getXmid();
			double x2 = obj2.getXmid();

//			causes a contract violation (rounding?)
//			return (int) (x1 - x2);
			
			if (x2 > x1) return -1;
			else if (x2 == x1) return 0;
			else return 1;
		}

		public boolean equals(Object obj)
		{
			return obj.equals(this);
		}
	} public class Y1Comparator implements Comparator<GenericSegment>
{
	public int compare(GenericSegment obj1, GenericSegment obj2)
	{
		// sorts in y order
//		double y1 = obj1.getY1();
//		double y2 = obj2.getY1();

		int y1 = (int) obj1.getY2();
		int y2 = (int) obj2.getY2();
		
		return (int) (y2 - y1);
	}

	public boolean equals(Object obj)
	{
		return obj.equals(this);
	}
} public class Y2Comparator implements Comparator<GenericSegment>
{
	public int compare(GenericSegment obj1, GenericSegment obj2)
	{
		// sorts in y order
//		double y1 = obj1.getY2();
//		double y2 = obj2.getY2();
		
		int y1 = (int) obj1.getY2();
		int y2 = (int) obj2.getY2();
		
//		System.out.println("y1= " + y1 + " y2= " + y2 + " returning: " + ((int) (y2 - y1)));

		return (int) (y2 - y1);
	}

	public boolean equals(Object obj)
	{
		return obj.equals(this);
	}
} public class DocumentProcessingException extends Exception
{
    private Exception embedded;
    
    public DocumentProcessingException(String msg)
    {
        super(msg);
    }
    
    public DocumentProcessingException(Exception e)
    {
        super(e.getMessage());
        setEmbedded(e);
    }
    
    public Exception getEmbedded()
    {
        return embedded;
    }
    
    private void setEmbedded(Exception e)
    {
        embedded = e;
    }
} public class AdjacencyGraph<T extends GenericSegment>// extends DocumentGraph 
{   
//	protected List<T> nodes;
	protected List<AdjacencyEdge<T>> edges;
	
	/*
	protected List<T> neighboursLeft;
	protected List<T> neighboursRight;
	protected List<T> neighboursAbove;
	protected List<T> neighboursBelow;
	*/
	
	// temporary for edge generation only
	protected List<T> horiz;
	protected List<T> vert;
	
	protected X1Comparator xComp = new X1Comparator();
	protected Y1Comparator yComp = new Y1Comparator();

	// 2011-11-17 does not appear to be in use!
//	protected HashMap<T, List<AdjacencyEdge<T>>> edgesFrom;
//	protected HashMap<T, List<AdjacencyEdge<T>>> edgesTo;
	
	public final static int NEIGHBOUR_INTERSECTING_X_Y_MID = 0;
	public final static int NEIGHBOUR_X_Y_INTERSECT = 1;
	
	protected int neighbourRules = 1;
	
	/**
     * Constructor.
     *
     * @param to fill in! todo!
     */
    public AdjacencyGraph()
    // initialize a blank neighbourhood graph
    {
//    	nodes = new ArrayList<T>();
    	edges = new ArrayList<AdjacencyEdge<T>>();
    	
    	horiz = new ArrayList<T>();
    	vert = new ArrayList<T>();
    	
//    	2011-01-27 TODO: implement HashMap
//    	edgesFrom = new HashMap<T, List<AdjacencyEdge<T>>>();
//    	edgesTo = new HashMap<T, List<AdjacencyEdge<T>>>();
    }
    
    /*
    public List<T> getNodes() {
		return nodes;
	}

	public void setNodes(List<T> nodes) {
		this.nodes = nodes;
	}
	*/
    
    /**
     * creates a new graph object with shallow copies
     * of horiz, vert and edge lists
     * 
     * @return
     */
    public AdjacencyGraph<T> duplicate()
    {
    	AdjacencyGraph<T> retVal = new AdjacencyGraph<T>();
    	retVal.getHorizSegmentList().addAll(this.getHorizSegmentList());
    	retVal.getVertSegmentList().addAll(this.getVertSegmentList());
    	retVal.getEdges().addAll(this.getEdges());
    	
    	return retVal;
    }
    
	public void addList(List<? extends T> nodes)
	{
		horiz.addAll(nodes);
		vert.addAll(nodes);
	}
	
	public List<AdjacencyEdge<T>> getEdges() {
		return edges;
	}

	public void setEdges(List<AdjacencyEdge<T>> edges) {
		this.edges = edges;
	}
	
	public List<AdjacencyEdge<T>> horizEdges() {
		List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
		for (AdjacencyEdge<T> ae : edges)
			if (ae.isHorizontal()) retVal.add(ae);
		return retVal;
	}
	
	public List<AdjacencyEdge<T>> vertEdges() {
		List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
		for (AdjacencyEdge<T> ae : edges)
			if (ae.isVertical()) retVal.add(ae);
		return retVal;
	}

	public List<T> getHorizSegmentList() {
		return horiz;
	}

	public List<T> getVertSegmentList() {
		return vert;
	}

	public int getNeighbourRules() {
		return neighbourRules;
	}

	public void setNeighbourRules(int neighbourRules) {
		this.neighbourRules = neighbourRules;
	}

	/**
	 * returns the length of the common horizontal edge
	 * of two segments
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	protected float yEdgeIntersect(T seg1, T seg2)
	{
		
		if (seg1.getY1() >= seg2.getY1() && seg1.getY1() <= seg2.getY2())
		{
			// seg1.getY1() lies within bounds of seg2
			// intersection between seg1.getY1() and min(seg1.getY2(), seg2.getY2())
			return Utils.minimum(seg1.getY2(), seg2.getY2()) - seg1.getY1();
		}
		else if (seg2.getY1() >= seg1.getY1() && seg2.getY1() <= seg1.getY2())
		{
			// seg2.getY1() lies within bounds of seg1
			// intersection between seg2.getX1() and min(seg1.getX2(), seg2.getX2())
			return Utils.minimum(seg1.getY2(), seg2.getY2()) - seg2.getY1();
		}
		
		return 0;
	}
	
	/**
	 * returns the length of the common vertical edge
	 * of two segments
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	protected float xEdgeIntersect(T seg1, T seg2)
	{
		// seg1.getX1() lies within bounds of seg2
		//    ###      ####  seg1
		//  #######  ####    seg2
		if (seg1.getX1() >= seg2.getX1() && seg1.getX1() <= seg2.getX2())
		{
			// intersection between seg1.getX1() and min(seg1.getX2(), seg2.getX2())
			return Utils.minimum(seg1.getX2(), seg2.getX2()) - seg1.getX1();
		}
		// seg2.getX1() lies within bounds of seg1
		//	#######  ####    seg1
		//    ###      ####  seg2
		else if (seg2.getX1() >= seg1.getX1() && seg2.getX1() <= seg1.getX2())
		{
			// intersection between seg2.getX1() and min(seg1.getX2(), seg2.getX2())
			return Utils.minimum(seg1.getX2(), seg2.getX2()) - seg2.getX1();
		}
				
		return 0;
	}
	
	/**
	 * returns first neighbour below thisSegment according to
	 * straight-line distance
	 * 
	 * @param thisSegment
	 * @return found neighbour or null if no neighbour found within line of sight
	 */
	protected T findNeighbourBelow(T thisSegment)
    {
//		T retVal = null;
//		float currSLD = -1;
	    
	    // returns -1 if the given node is not in the list
	    // TODO: return an exception in this case
	    int index = vert.indexOf(thisSegment);
	    
	    // look for neighbours below, return the first or null!
	    // list is sorted in Y1 (baseline) order
        for (int n = index + 1; n < vert.size(); n ++)
        {
        	T o = vert.get(n);
        	
//        	float vertDist = thisSegment.getY1() - o.getY2();
            
        	// use line-of-sight definition
    		boolean isNeighbour = SegmentUtils.horizIntersect(o, thisSegment);
    		
        	if (neighbourRules == NEIGHBOUR_INTERSECTING_X_Y_MID)
        	{
        		isNeighbour = SegmentUtils.horizIntersect(o, thisSegment) 
                		&& (SegmentUtils.horizIntersect(thisSegment, o.getXmid()) 
                    	|| SegmentUtils.horizIntersect(o, thisSegment.getXmid()));
        	}
            
            if (isNeighbour)
            {
            	// calculate straight line distance from horizontal centres
            	// of vertical edges
            	
            	float horizDist = thisSegment.getXmid() - o.getXmid();
            	if (horizDist < 0) horizDist = o.getXmid() - thisSegment.getXmid();
            	
            	// extra check for "touching" segments
            	if (SegmentUtils.vertIntersect(o, thisSegment))
        		{
            		/*
        			float vertMidDist = thisSegment.getYmid() - o.getYmid();
        			if (horizDist > vertMidDist) continue;
        			*/
            		
            		if (yEdgeIntersect(o, thisSegment) > xEdgeIntersect(o, thisSegment))
            			continue;
        		}
            	
            	return o;
            	
            	/*
            	float sld = (float) Math.sqrt((Math.pow(vertDist, 2) + Math.pow(horizDist, 2))); 
            	
            	// assign retVal or update
            	// if sld is shorter than that of previous retVal
            	
            	if (retVal == null || sld < currSLD)
            	{
            		retVal = o;
            		currSLD = sld;
            	}
            	*/
            }

            // check whether to exit loop
            /*
            if (retVal != null && vertDist > currSLD)
            {
            	return retVal;
            }
            */
        }
//      return retVal;
        return null;
    }
	
	/**
	 * returns first neighbour above thisSegment according to
	 * straight-line distance
	 * 
	 * @param thisSegment
	 * @return found neighbour or null if no neighbour found within line of sight
	 */
	protected T findNeighbourAbove(T thisSegment)
    {
//		T retVal = null;
//		float currSLD = -1;
	    
	    // returns -1 if the given node is not in the list
	    // TODO: return an exception in this case
	    int index = vert.indexOf(thisSegment);
	    
	    // look for neighbours above, return the first or null!
	    // list is sorted in Y1 (baseline) order
	    for (int n = index - 1; n >= 0; n --)
        {
        	T o = vert.get(n);
        	
//        	float vertDist = o.getY1() - thisSegment.getY2();
            
        	 // use line-of-sight definition
        	boolean isNeighbour = SegmentUtils.horizIntersect(o, thisSegment);
        	
        	if (neighbourRules == NEIGHBOUR_INTERSECTING_X_Y_MID)
        	{
        		isNeighbour = SegmentUtils.horizIntersect(o, thisSegment) 
		        		&& (SegmentUtils.horizIntersect(thisSegment, o.getXmid()) 
		            	|| SegmentUtils.horizIntersect(o, thisSegment.getXmid()));
        	}
            
            if (isNeighbour)
            {
            	// calculate straight line distance from horizontal centres
            	// of vertical edges
            	
            	float horizDist = thisSegment.getXmid() - o.getXmid();
            	if (horizDist < 0) horizDist = o.getXmid() - thisSegment.getXmid();
            	
            	// extra check for "touching" segments
            	if (SegmentUtils.vertIntersect(o, thisSegment))
        		{
            		/*
        			float vertMidDist = o.getYmid() - thisSegment.getYmid();
        			if (horizDist > vertMidDist) continue;
        			*/
            		
        			if (yEdgeIntersect(o, thisSegment) > xEdgeIntersect(o, thisSegment))
            			continue;
        		}
            	
            	return o;
            	
            	/*
            	float sld = (float) Math.sqrt((Math.pow(vertDist, 2) + Math.pow(horizDist, 2))); 
            	
            	// assign retVal or update
            	// if sld is shorter than that of previous retVal
            	if (retVal == null || sld < currSLD)
            	{
            		retVal = o;
            		currSLD = sld;
            	}
            	*/
            }

            // check whether to exit loop
            /*
            if (retVal != null && vertDist > currSLD)
            {
            	return retVal;
            }
            */
        }
//      return retVal;
	    return null;
    }
	
    /**
	 * returns first neighbour left of thisSegment according to
	 * straight-line distance
	 * 
	 * @param thisSegment
	 * @return found neighbour or null if no neighbour found within line of sight
	 */
	protected T findNeighbourLeft(T thisSegment)
    {
//		T retVal = null;
//		float currSLD = -1;
	    
	    // returns -1 if the given node is not in the list
	    // TODO: return an exception in this case
	    int index = horiz.indexOf(thisSegment);
	    
	    // look for neighbours above, return the first or null!
	    // list is sorted in X1 order
	    for (int n = index - 1; n >= 0; n --)
        {
        	T o = horiz.get(n);
        	
//        	float horizDist = thisSegment.getX2() - o.getX1();
            
            // use line-of-sight definition
        	boolean isNeighbour = SegmentUtils.vertIntersect(o, thisSegment);
        	
        	if (neighbourRules == NEIGHBOUR_INTERSECTING_X_Y_MID)
        	{
        		isNeighbour = SegmentUtils.vertIntersect(o, thisSegment) 
		        		&& (SegmentUtils.vertIntersect(thisSegment, o.getXmid()) 
		            	|| SegmentUtils.vertIntersect(o, thisSegment.getXmid()));
        	}
            
            if (isNeighbour)
            {
            	// calculate straight line distance from horizontal centres
            	// of vertical edges
            	
            	float vertDist = thisSegment.getYmid() - o.getYmid();
            	if (vertDist < 0) vertDist = o.getYmid() - thisSegment.getYmid();
            	
            	// extra check for "touching" segments
            	if (SegmentUtils.horizIntersect(o, thisSegment))
        		{
            		/*
        			float horizMidDist = thisSegment.getXmid() - o.getXmid();
        			if (vertDist > horizMidDist) continue;
        			*/
            		
            		if (xEdgeIntersect(o, thisSegment) > yEdgeIntersect(o, thisSegment))
            			continue;
        		}
            	
            	return o;
            	
            	/*
            	float sld = (float) Math.sqrt((Math.pow(vertDist, 2) + Math.pow(horizDist, 2))); 
            	
            	// assign retVal or update
            	// if sld is shorter than that of previous retVal
            	if (retVal == null || sld < currSLD)
            	{
            		retVal = o;
            		currSLD = sld;
            	}
            	*/
            }

            // check whether to exit loop
            /*
            if (retVal != null && horizDist > currSLD)
            {
            	return retVal;
            }
            */
        }
//      return retVal;
        return null;
    }
    
    /**
	 * returns first neighbour left of thisSegment according to
	 * straight-line distance
	 * 
	 * @param thisSegment
	 * @return found neighbour or null if no neighbour found within line of sight
	 */
	protected T findNeighbourRight(T thisSegment)
    {
//		T retVal = null;
//		float currSLD = -1;
	    
	    // returns -1 if the given node is not in the list
	    // TODO: return an exception in this case
	    int index = horiz.indexOf(thisSegment);
	    
	    // look for neighbours above, return the first or null!
	    // list is sorted in X1 order
	    for (int n = index + 1; n < horiz.size(); n ++)
        {
        	T o = horiz.get(n);
        	
//        	float horizDist = o.getX1() - thisSegment.getX2();
            
        	// use line-of-sight definition
        	boolean isNeighbour = SegmentUtils.vertIntersect(o, thisSegment);
        	
        	if (neighbourRules == NEIGHBOUR_INTERSECTING_X_Y_MID)
        	{
            	isNeighbour = SegmentUtils.vertIntersect(o, thisSegment) 
		        		&& (SegmentUtils.vertIntersect(thisSegment, o.getXmid()) 
		            	|| SegmentUtils.vertIntersect(o, thisSegment.getXmid()));
        	}
        	
            if (isNeighbour)
            {
            	// calculate straight line distance from horizontal centres
            	// of vertical edges
            	
            	float vertDist = thisSegment.getYmid() - o.getYmid();
            	if (vertDist < 0) vertDist = o.getYmid() - thisSegment.getYmid();
            	
            	// extra check for "touching" segments
            	if (SegmentUtils.horizIntersect(o, thisSegment))
        		{
            		/*
        			float horizMidDist = o.getXmid() - thisSegment.getXmid();
        			if (vertDist > horizMidDist) continue;
        			*/
            		
            		if (xEdgeIntersect(o, thisSegment) > yEdgeIntersect(o, thisSegment))
            			continue;
        		}
            	
            	return o;
            	
            	/*
            	float sld = (float) Math.sqrt((Math.pow(vertDist, 2) + Math.pow(horizDist, 2))); 
            	
            	// assign retVal or update
            	// if sld is shorter than that of previous retVal
            	if (retVal == null || sld < currSLD)
            	{
            		retVal = o;
            		currSLD = sld;
            	}
            	*/
            }

            // check whether to exit loop
            /*
            if (retVal != null && horizDist > currSLD)
            {
            	return retVal;
            }
            */
        }
//      return retVal;
        return null;
    }
    
    public void generateEdges()
    {
    	edges.clear();
    	
    	// TODO: clear hash maps too
    	
    	Collections.sort(horiz, new X2Comparator());
    	Collections.sort(vert, new Y2Comparator());
    	
        for (T thisBlock: vert)
        {
        	T neighbourLeft = findNeighbourLeft(thisBlock);
        	if (neighbourLeft != null)
        	{
        		edges.add(new AdjacencyEdge<T>(thisBlock, neighbourLeft, AdjacencyEdge.REL_LEFT));
                edges.add(new AdjacencyEdge<T>(neighbourLeft, thisBlock, AdjacencyEdge.REL_RIGHT));
        	}
        	
        	T neighbourAbove = findNeighbourAbove(thisBlock);
        	if (neighbourAbove != null)
        	{
        		edges.add(new AdjacencyEdge<T>(thisBlock, neighbourAbove, AdjacencyEdge.REL_ABOVE));
                edges.add(new AdjacencyEdge<T>(neighbourAbove, thisBlock, AdjacencyEdge.REL_BELOW));
        	}
        }
        
    	Collections.sort(horiz, new X1Comparator());
    	Collections.sort(vert, new Y1Comparator());
    	
    	// TODO: clear hash maps too
    	
        for (T thisBlock: vert)
        {
        	T neighbourRight = findNeighbourRight(thisBlock);
        	if (neighbourRight != null)
        	{
        		edges.add(new AdjacencyEdge<T>(thisBlock, neighbourRight, AdjacencyEdge.REL_RIGHT));
                edges.add(new AdjacencyEdge<T>(neighbourRight, thisBlock, AdjacencyEdge.REL_LEFT));
        	}
        	
        	T neighbourBelow = findNeighbourBelow(thisBlock);
        	if (neighbourBelow != null)
        	{
        		edges.add(new AdjacencyEdge<T>(thisBlock, neighbourBelow, AdjacencyEdge.REL_BELOW));
                edges.add(new AdjacencyEdge<T>(neighbourBelow, thisBlock, AdjacencyEdge.REL_ABOVE));
        	}
        }
        
        generateComplementaryEdges();
        removeDuplicateEdges();
        
        // horiz and vert lists remain sorted in X1 and Y1 (baseline)
        // order respectively
    }
    
    public void generateComplementaryEdges()
    {
    	List<AdjacencyEdge<T>> edgesToAdd = 
    		new ArrayList<AdjacencyEdge<T>>();
    	
    	for (AdjacencyEdge<T> e : edges)
    	{
    		int newDirection = -1;
    		if (e.getDirection() == AdjacencyEdge.REL_ABOVE)
    			newDirection = AdjacencyEdge.REL_BELOW;
    		else if (e.getDirection() == AdjacencyEdge.REL_BELOW)
    			newDirection = AdjacencyEdge.REL_ABOVE;
    		else if (e.getDirection() == AdjacencyEdge.REL_LEFT)
    			newDirection = AdjacencyEdge.REL_RIGHT;
    		else if (e.getDirection() == AdjacencyEdge.REL_RIGHT)
    			newDirection = AdjacencyEdge.REL_LEFT;
    		
    		edgesToAdd.add(new AdjacencyEdge<T>
    			(e.nodeTo, e.nodeFrom, newDirection));
    	}
    	edges.addAll(edgesToAdd);
    	
    	removeDuplicateEdges();
    }
    
    // TODO: to speed this up (and other operations...)
    // implement a hash map lookup for edges in the DocumentGraph method
    // or, rather EdgeList?
    /**
     * Removes extra instances of an edge between two
     * given nodes (even if they are distinct objects)
     * 
     * TODO: move to ListUtils?
     */
    protected void removeDuplicateEdges()
    {
    	List<AdjacencyEdge<T>> edgesToRemove = 
    		new ArrayList<AdjacencyEdge<T>>();
    	
    	for (AdjacencyEdge<T> e1 : edges)
    	{
			for (AdjacencyEdge<T> e2 : edges)
			{
				if (e1.getDirection() == e2.getDirection() &&
					e1.getNodeFrom() == e2.getNodeFrom() &&
					e1.getNodeTo() == e2.getNodeTo() &&
					e1 != e2 && !edgesToRemove.contains(e1))
				{
					edgesToRemove.add(e2);
				}
			}
    	}
    	edges.removeAll(edgesToRemove);
    }
    
    public void removeEdgesAboveLeft()
    {
    	List<AdjacencyEdge<? extends GenericSegment>> edgesToRemove =
			new ArrayList<AdjacencyEdge<? extends GenericSegment>>();
		
		for (AdjacencyEdge<? extends GenericSegment> ag : edges)
			if (ag.getDirection() == AdjacencyEdge.REL_LEFT ||
				ag.getDirection() == AdjacencyEdge.REL_ABOVE)
				edgesToRemove.add(ag);
		
		edges.removeAll(edgesToRemove);
    }
    
    public List<AdjacencyEdge<T>> edgesForSegment(T seg)
    {
    	List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
    	
    	for (AdjacencyEdge<T> e : edges)
    	{
    		if (e.getNodeFrom() == seg | e.getNodeTo() == seg)
    			retVal.add(e);
    	}
    	
    	return retVal;
    }
    
    /*
     here, we only seem look at nodes pointing FROM
     the given segment in the relevant direction --
     the other edges are duplicated anyway ...
     
     this way, we should end up with each neighbouring
     item once ...
     */
    
    public List<T> returnNeighboursLeft(T thisSeg)
    {
        List<T> retVal = new ArrayList<T>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_LEFT &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e.getNodeTo());
        }
        return retVal;
    }
    
    public List<T> returnNeighboursRight(GenericSegment thisSeg)
    {
    	List<T> retVal = new ArrayList<T>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_RIGHT &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e.getNodeTo());
        }
        return retVal;
    }
    
    public List<T> returnNeighboursAbove(GenericSegment thisSeg)
    {
    	List<T> retVal = new ArrayList<T>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_ABOVE &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e.getNodeTo());
        }
        return retVal;
    }
    
    public List<T> returnNeighboursBelow(GenericSegment thisSeg)
    {
    	List<T> retVal = new ArrayList<T>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_BELOW &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e.getNodeTo());
        }
        return retVal;
    }
    
    public List<AdjacencyEdge<T>> returnEdgesLeft(T thisSeg)
    {
        List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_LEFT &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e);
        }
        return retVal;
    }
    
    public List<AdjacencyEdge<T>> returnEdgesRight(T thisSeg)
    {
        List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_RIGHT &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e);
        }
        return retVal;
    }
    
    public List<AdjacencyEdge<T>> returnEdgesAbove(T thisSeg)
    {
        List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_ABOVE &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e);
        }
        return retVal;
    }
    
    public List<AdjacencyEdge<T>> returnEdgesBelow(T thisSeg)
    {
        List<AdjacencyEdge<T>> retVal = new ArrayList<AdjacencyEdge<T>>();
        for (AdjacencyEdge<T> e : edges)
        {
        	if (e.getDirection() == AdjacencyEdge.REL_BELOW &&
        		e.getNodeFrom() == thisSeg)
        		retVal.add(e);
        }
        return retVal;
    }
    
    public AdjacencyGraph<T> generateSubgraph(List<T> segments)
    {
    	AdjacencyGraph<T> retVal = new AdjacencyGraph<T>();
    	for (AdjacencyEdge<T> ae : edges)
    		if (segments.contains(ae.getNodeFrom()) && 
    			segments.contains(ae.getNodeTo()))
    			retVal.edges.add(ae);
    	for (T seg : horiz)
    		if (segments.contains(seg)) retVal.horiz.add(seg);
    	for (T seg : vert)
    		if (segments.contains(seg)) retVal.vert.add(seg);
    	
    	return retVal;
    }
    
    /**
     * deprecated - used by clusterXThreshold
     * 
     * @param node1
     * @param node2
     * @param newSegment
     */
    public void mergeNodes(T node1, T node2, T newSegment)
    {
    	// list of all edges pointing to or from merged segment
    	List<AdjacencyEdge<T>> newEdges = edgesForSegment(node1);
    	newEdges.addAll(edgesForSegment(node2));
    	ListUtils.removeDuplicates(newEdges);
    	
    	// remove edges between the two segments
    	List<AdjacencyEdge<T>> edgesToRemove = new ArrayList<AdjacencyEdge<T>>();
    	for (AdjacencyEdge<T> e : newEdges)
    	{
    		if (e.getNodeFrom() == node1 && e.getNodeTo() == node2 ||
    				e.getNodeFrom() == node2 && e.getNodeTo() == node1)
    		{
//    			newEdges.remove(e);
    			edgesToRemove.add(e);
    			edges.remove(e);
    		}
    		else if (e.getNodeFrom() == node1 || e.getNodeFrom() == node2)
    		{
    			e.setNodeFrom(newSegment);
    		}
    		else if (e.getNodeTo() == node1 || e.getNodeTo() == node2)
    		{
    			e.setNodeTo(newSegment);
    		}
    	}
    	
    	newEdges.removeAll(edgesToRemove);
    	horiz.remove(node1);
    	horiz.remove(node2);
    	orderedAdd(newSegment);
    }
    
    /**
     * removed - no more generateEdgesSingle method
     * 
     * @param node
     * @param newSeg1
     * @param newSeg2
     */
    /*
    public void splitNodes(T node, T newSeg1, T newSeg2)
    {
    	// remove node
    	horiz.remove(node);
    	vert.remove(node);
    	// remove all edges to/from node
    	edges.removeAll(edgesForSegment(node));
    	
    	orderedAdd(newSeg1);
    	orderedAdd(newSeg2);
    	
    	generateEdgesSingle(newSeg1);
    	generateEdgesSingle(newSeg2);
    	removeDuplicateEdges();
    }
    */
    
    /**
     * deprecated - used by mergeNodes
     * 
     * @param element
     */
    // adapted from https://stackoverflow.com/questions/18144820/inserting-into-sorted-linkedlist-java#19614083
    public void orderedAdd(T element) 
    {      
    	{
	    	ListIterator<T> itr = horiz.listIterator();
	        boolean loop = true;
	    	while(loop) {
	            if (itr.hasNext() == false) {
	                itr.add(element);
	                loop = false;
	                break;
	            }
	
	            T elementInList = itr.next();
	            if (xComp.compare(elementInList,element) > 0) {
	                itr.previous();
	                itr.add(element);
	                System.out.println("Adding to horiz");
	                loop = false;
	                break;
	            }
	        }
    	}
    	
    	{
	    	ListIterator<T> itr = vert.listIterator();
	        boolean loop = true;
	    	while(loop) {
	            if (itr.hasNext() == false) {
	                itr.add(element);
	                loop = false;
	                break;
	            }
	
	            T elementInList = itr.next();
	            if (yComp.compare(elementInList,element) > 0) {
	                itr.previous();
	                itr.add(element);
	                System.out.println("Adding to vert");
	                loop = false;
	                break;
	            }
	        }
    	}
    }
    
    public String toString()
    {
        StringBuffer retVal = new StringBuffer("");
        for (T seg : vert)
        {
            retVal.append(seg.toString() + "\n");
            List<T> neighboursLeft = returnNeighboursLeft(seg);
            List<T> neighboursRight = returnNeighboursRight(seg);
            List<T> neighboursAbove = returnNeighboursAbove(seg);
            List<T> neighboursBelow = returnNeighboursBelow(seg);
            retVal.append("     Neighbours left: " + neighboursLeft.size() +
                " right: " + neighboursRight.size() +
                " above: " + neighboursAbove.size() +
                " below: " + neighboursBelow.size() + "\n");
        }
        return retVal.toString();
    }
    
    /**
     * adds page graph as XML
     * 
     * @param resultDocument
     * @param parent
     * @param pageDim
     * @param resolution
     * @param pageNo if >=0 will be included as attribute
     */
    public void addAsXML(Document resultDocument, Element parent, 
    		GenericSegment pageDim, float resolution, int pageNo)
    {
    	Element newPageElement = resultDocument.createElement("page-graph");
    	if (pageNo >= 0)
    		newPageElement.setAttribute("page-no", Integer.toString(pageNo));
    		
    	// number vert nodes 0-based consec.
    	List<T> vertCopy = new ArrayList<T>();
    	vertCopy.addAll(vert);
    	Collections.sort(vertCopy, new Y1Comparator());
    	
    	int index = 0;
    	for (T node : vertCopy)
    	{
    		node.addAsXML(resultDocument, newPageElement, pageDim, resolution, index);
    		index ++;
    	}
    	
    	// TODO: sort edges horiz first?
        // add edges
        for (AdjacencyEdge<T> e : edges)
        {
        	String elementName = "vert-edge";
        	if (e.isHorizontal()) elementName = "horiz-edge";
        	
        	Element newEdgeElement = resultDocument.createElement(elementName);
        	newEdgeElement.setAttribute("node-from", Integer.toString(vertCopy.indexOf(e.getNodeFrom()))); 
        	newEdgeElement.setAttribute("node-to", Integer.toString(vertCopy.indexOf(e.getNodeTo()))); 
        	
        	newPageElement.appendChild(newEdgeElement);
        }
        
        // output other relations
        
//        newPageElement.appendChild
//            (resultDocument.createTextNode("Page " + pageNo));
        
        parent.appendChild(newPageElement);
        

    }
} public class GenericSegment implements Cloneable, IXMLSegment, Serializable {
    private static final long serialVersionUID = 1L;

    protected float x1, x2, y1, y2;
	boolean zeroSize = false;
	

	public GenericSegment(){
	}



    /**
     * Constructor.
     *
     * @param x1
     *            The x1 coordinate of the segment.
     * @param x2
     *            The x2 coordinate of the segment.
     * @param y1
     *            The y1 coordinate of the segment.
     * @param y2
     *            The y2 coordinate of the segment.
     */
	public GenericSegment(float x1, float x2, float y1, float y2)
	{
		this();
		this.x1 = x1;
		this.x2 = x2;
		this.y1 = y1;
		this.y2 = y2;
	}

	public GenericSegment(float[] boundingBox)
	{
		this();
		this.setBoundingBox(boundingBox);
	}

	public GenericSegment(PDRectangle bBox)
	{
		this();
		this.setBoundingBox(bBox);
	}

	/**
	 * This will get the x1 position of the segment.
	 * 
	 * @return The x1 coordinate of the segment.
	 */
	public float getX1()
	{
		return x1;
	}

	/**
	 * @param scale
	 *            The x1 to set.
	 */
	public void setX1(float x1)
	{
		this.x1 = x1;
	}

	/**
	 * This will get the x2 position of the segment.
	 * 
	 * @return The x2 coordinate of the segment.
	 */
	public float getX2()
	{
		return x2;
	}

	/**
	 * @param scale
	 *            The x2 to set.
	 */
	public void setX2(float x2)
	{
		this.x2 = x2;
	}

	/**
	 * This will get the y1 position of the segment.
	 * 
	 * @return The y1 coordinate of the segment.
	 */
	public float getY1()
	{
		return y1;
	}

	/**
	 * @param scale
	 *            The y1 to set.
	 */
	public void setY1(float y1)
	{
		this.y1 = y1;
	}

	/**
	 * This will get the y2 position of the segment.
	 * 
	 * @return The y2 coordinate of the segment.
	 */
	public float getY2()
	{
		return y2;
	}

	/**
	 * @param scale
	 *            The y2 to set.
	 */
	public void setY2(float y2)
	{
		this.y2 = y2;
	}

	public float getXmid()
	{
		return (x1 + x2) / 2;
	}

	public float getYmid()
	{
		return (y1 + y2) / 2;
	}

	/**
	 * This will get the width of the segment.
	 * 
	 * @return The width of the segment.
	 */
	public float getWidth()
	{
		return (x2 - x1);
	}

	/**
	 * This will get the height of the segment.
	 * 
	 * @return The height of the segment.
	 */
	public float getHeight()
	{
		return (y2 - y1);
	}

	/**
	 * This will return the area of the segment.
	 * 
	 * @return The area of the segment (in pt^2).
	 */
	public float getArea()
	{
		return getHeight() * getWidth();
	}

	// note: these methods assume no negative widths!
	// TODO: implement all Allen relations

	@Override
	public String toString()
	{
		return getAttributes().toString();
	}
	
	/**
	 * Merges this segment with the input segment.
	 * Make sure to include everything you want your segments to share within the body of this or inherited methods.
	 * 
	 * @param seg A segment you want to merge with
	 */
	public void mergeSegment(GenericSegment seg) {
		
		//TODO: better to create new objects? this is dangerous
		
		//Enlarges the bounding rectangle to fit the biggest bounds
		x1 = (seg.x1 < x1) ? seg.x1 : x1;
		x2 = (seg.x2 > x2) ? seg.x2 : x2;
		y1 = (seg.y1 < y1) ? seg.y1 : y1;
		y2 = (seg.y2 > y2) ? seg.y2 : y2;
	}
	
	/**
	 * Getter method for attributes
	 * 
	 * @return returns a list of all attributes that this segments contains together with the segment type
	 */
	public List<AttributeTuple> getAttributes() {
		
		ArrayList<AttributeTuple> attributeList = new ArrayList<AttributeTuple>();
		
		//Add segment type for later recognition purposes
		attributeList.add(new AttributeTuple("type", tagName()));
		
		//Add new attributes here
		attributeList.add(new AttributeTuple("x1", x1));
		attributeList.add(new AttributeTuple("y1", y1));
		attributeList.add(new AttributeTuple("x2", x2));
		attributeList.add(new AttributeTuple("y2", y2));	
		
		return attributeList;
	}

	public void setElementAttributes(Document resultDocument, 
		Element newSegmentElement,
		GenericSegment pageDim, float resolution, int id)
	{
		if (id >= 0)
			newSegmentElement.setAttribute("id", Integer.toString(id));
		
		float pageHeight = pageDim.getHeight();
		//float pageHeight = pageDim.getY2() + pageDim.getY1();
		newSegmentElement.setAttribute("x", Float.toString(this.getX1() * 
			resolution / Utils.PDF_POINT_RESOLUTION));
		newSegmentElement.setAttribute("y", Float.toString((pageHeight
			- this.getY1() - this.getHeight()) * resolution / Utils.PDF_POINT_RESOLUTION));
		newSegmentElement.setAttribute("w", Float.toString(this.getWidth() * 
			resolution / Utils.PDF_POINT_RESOLUTION));
		newSegmentElement.setAttribute("h", Float.toString(this.getHeight() * 
			resolution / Utils.PDF_POINT_RESOLUTION));
	}

	public void correctNegativeDimensions()
	{
		if (x1 > x2)
		{
			float temp = x1;
			x1 = x2;
			x2 = temp;
		}
		if (y1 > y2)
		{
			float temp = y1;
			y1 = y2;
			y2 = temp;
		}
	}

	public void enlargeCoordinates(float amount)
	{
		x1 = x1 - amount;
		x2 = x2 + amount;
		y1 = y1 - amount;
		y2 = y2 + amount;
	}

	public void scaleCoordinates(float multiple)
	{
		x1 = x1 * multiple;
		x2 = x2 * multiple;
		y1 = y1 * multiple;
		y2 = y2 * multiple;
	}

	public void invertYCoordinates(GenericSegment page)
	{
		float pageHeight = page.getHeight();
		y1 = pageHeight - y1;
		y2 = pageHeight - y2;
	}

	public void rotate(float pointX, float pointY, int amount)
	{
		// if (amount == null) return;
		
		float px1 = x1 - pointX, px2 = x2 - pointX;
		float py1 = y1 - pointY, py2 = y2 - pointY;
		
		if (amount == 90 || amount == -270)
		{
			x1 = pointX - py2; x2 = pointX - py1;
			y1 = pointY + px1; y2 = pointY + px2;
		}
		else if (amount == 270 || amount == -90)
		{
			x1 = pointX + py1; x2 = pointX + py2;
			y1 = pointY - px2; y2 = pointY - px1;
		}
	}
	
	public void rotate(PDPage page)
	{
		GenericSegment mediaBox = new GenericSegment(page.getMediaBox());
		if (page.getRotation() != 0)
		{
			rotate(mediaBox.getX1(), mediaBox.getY1(), page.getRotation());

			if (page.getRotation() == 90 || page.getRotation() == -270)
			{
				x1 = x1 + mediaBox.getHeight();
				x2 = x2 + mediaBox.getHeight();
			}
			else if (page.getRotation() == 270 || page.getRotation() == -90)
			{
				y1 = y1 + mediaBox.getWidth();
				y2 = y2 + mediaBox.getWidth();
			}
		}
	}
	
	/*
	 * 22.01.07
	 * added to make processing faster when recalculating
	 * bbox of a composite segment after only one element
	 * has been added (clustering)
	 * 
	 */
	public void growBoundingBox(GenericSegment thisSegment)
	{
		if (thisSegment.getX1() < x1)
			x1 = thisSegment.getX1();
		if (thisSegment.getY1() < y1)
			y1 = thisSegment.getY1();
		if (thisSegment.getX2() > x2)
			x2 = thisSegment.getX2();
		if (thisSegment.getY2() > y2)
			y2 = thisSegment.getY2();
	}
	
	public void shrinkBoundingBox(GenericSegment thisSegment)
	{
		if (SegmentUtils.intersects(this, thisSegment))
		{
			if (thisSegment.getX1() > x1)
				x1 = thisSegment.getX1();
			if (thisSegment.getY1() > y1)
				y1 = thisSegment.getY1();
			if (thisSegment.getX2() < x2)
				x2 = thisSegment.getX2();
			if (thisSegment.getY2() < y2)
				y2 = thisSegment.getY2();
		}
		else
			this.setZeroSize(true); // intersection is 0
	}
	
	public boolean isZeroSize() {
		return zeroSize;
	}

	public void setZeroSize(boolean zeroSize) {
		this.zeroSize = zeroSize;
	}

	public Rectangle getBoundingRectangle()
	{
		int x = (int) x1;
		int y = (int) y1;
		int w = (int) this.getWidth();
		int h = (int) this.getHeight();

		return new Rectangle(x, y, w, h);
	}

	public void setBoundingBox(float[] bBox)
	{
		// TODO: not sure if we should bother
		// with exception stuff?
		x1 = bBox[0]; x2 = bBox[1];
		y1 = bBox[2]; y2 = bBox[3];
	}
	
	public void setBoundingBox(PDRectangle bBox)
	{
		x1 = bBox.getLowerLeftX(); x2 = bBox.getUpperRightX();
		y1 = bBox.getLowerLeftY(); y2 = bBox.getUpperRightY();
	}
	
	public float[] getBoundingBox()
	{
		float[] bBox =
		{ x1, x2, y1, y2 };
		return bBox;
	}

	public PDRectangle toPDRectangle()
	{
		PDRectangle retVal = new PDRectangle();
		retVal.setLowerLeftX(x1);
		retVal.setLowerLeftY(y1);
		retVal.setUpperRightX(x2);
		retVal.setUpperRightY(y2);
		return retVal;
	}

	/**
	 * @return Returns a clone of this segment, i.e.
	 * the co-ordinates and level
	 * TODO: implement for sub-objects
	 */
	public Object clone()
	{
		try {
            return super.clone();
        }
        catch (CloneNotSupportedException e) {
            // This should never happen
            throw new InternalError(e.toString());
        }
	}

	public String tagName()
	{
//		if (classification == C_WRAPPING_INSTANCE)
//			return "wrapping-instance";
//		else if (classification == C_SUB_INSTANCE)
//			return "sub-instance";
		//String className =  this.getClass().getSimpleName();
		String className =  Utils.stripClassName(this.getClass().getName());
		StringBuffer retVal = new StringBuffer(className.length());
		
		boolean afterHyphen = true;
		for (int n = 0; n < className.length(); n ++)
		{
			String chr = className.substring(n, n + 1);
			if (chr.toLowerCase().equals(chr))
			{
				// lower case; just add
				retVal.append(chr);
				afterHyphen = false;
			}
			else
			{
				if (!afterHyphen)
				{
					retVal.append("-");
					retVal.append(chr.toLowerCase());
					afterHyphen = true;
				}
				else
				{
					retVal.append(chr.toLowerCase());
					afterHyphen = true;
				}
			}
		}
		
		return retVal.toString();
	}

	public void addAsXML(Document resultDocument, Element parent,
		GenericSegment pageDim, float resolution, int id)
	{
		Element newSegmentElement = resultDocument
			.createElement(tagName());
		
		this.setElementAttributes(resultDocument, newSegmentElement, pageDim, 
				resolution, id);
		parent.appendChild(newSegmentElement);
	}
} public class Page extends CompositeSegment<GenericSegment> implements IXHTMLSegment
{   
    int pageNo = 0;
    int rotation = 0;
    int lastOpIndex = -1;
//  removed 2011-01-24
//  DocumentGraph docGraph;
    
    public Page()
    {
        super();
    }
    
    public Page(List<GenericSegment> items)
    {
        super(items);
    }
    
    public Page(
        float x1,
        float x2,
        float y1,
        float y2
        )
    {
		super(x1, x2, y1, y2);
    }
    
    public Page(
        float x1,
        float x2,
        float y1,
        float y2,
		List<GenericSegment> items
        )
    {
		super(x1, x2, y1, y2, items);
    }
    
    public void addAsXHTML(Document resultDocument, Element parent)
    {
        Element newPageElement = resultDocument.createElement("h2");
        
        newPageElement.appendChild
            (resultDocument.createTextNode("Page " + pageNo));
        
        parent.appendChild(newPageElement);
        
        for(GenericSegment thisItem : items)
        {
            // eventually, this line should take care of everything here...
            // thisItem.addAsXHTML(resultDocument, parent);
            
            // but for now, enable only for those elements that have
            // it defined...

            if (thisItem instanceof IXHTMLSegment)// && 
//            	thisItem.getClass() != TableColumn.class &&
//            	thisItem.getClass() != TableRow.class)
            {
            	//System.out.println("adding class: " + thisItem.getClass());
            	((IXHTMLSegment)thisItem).addAsXHTML(resultDocument, parent);
            }
        }
    }
    
    public void addAsXML(Document resultDocument, Element parent, 
    	GenericSegment pageDim, float resolution, int id)
    {
    	//System.out.println("adding as XML with pageDim: " + pageDim);
        Iterator itemIter = items.iterator();
        while(itemIter.hasNext())
        {
            GenericSegment thisItem = (GenericSegment)itemIter.next();
        	thisItem.addAsXML(resultDocument, parent, pageDim, resolution, -1);
        }
    }
    
    @Override
    public List<AttributeTuple> getAttributes() {

    	List<AttributeTuple> attList = super.getAttributes();
    	
    	attList.add(new AttributeTuple("pageNo", pageNo));
    	
    	return attList;
    }
    
    /**
     * @return Returns the pageNo.
     */
    public int getPageNo() {
        return pageNo;
    }
    

    /**
     * @param pageNo The pageNo to set.
     */
    public void setPageNo(int pageNo) {
        this.pageNo = pageNo;
    }

    public int getRotation() {
		return rotation;
	}

	public void setRotation(int rotation) {
		this.rotation = rotation;
	}

	public int getLastOpIndex() {
		return lastOpIndex;
	}

	public void setLastOpIndex(int lastOpIndex) {
		this.lastOpIndex = lastOpIndex;
	}
} public class TextBlock extends CompositeSegment<TextLine> //implements ResultSegment
	implements IXHTMLSegment
{
	protected float rejectDistance = Float.MAX_VALUE;
	protected boolean branchMerged = false;
	protected boolean branchSplit = false; // add edge or distance?
	
//	Other ideas: firstChild/secondChild (hierarchical)
//	             lastGoodSegmentation
//	Merge history allows linear search
	
//	List<List<CandidateBlock>> mergeHistory = new ArrayList<List<CandidateBlock>>();
	
	final public static int ALIGN_UNSET = -1;
	final public static int ALIGN_LEFT = 0;
	final public static int ALIGN_CENTRE = 1;
	//final public static int ALIGN_CENTRE_KNUTH = 11;
	final public static int ALIGN_JUSTIFY = 2;
	final public static int ALIGN_RIGHT = 3;
	final public static int ALIGN_FORCE_JUSTIFY = 4;
	
	int alignment = -1;
	
	final public static int LBL_UNSET = -1;
	final public static int LBL_PARA = 10;
	final public static int LBL_CELL = 20;
	final public static int LBL_TD = 21;
	final public static int LBL_TH = 22;
	final public static int LBL_CELLS = 25;
	final public static int LBL_LIST = 30;
	final public static int LBL_LIST_LABEL = 31;
	final public static int LBL_LIST_TEXT = 32;
	
//	int label = -1;
	
	float evalPara = -1.0f;
	float evalCell = -1.0f;
	float evalBullet = -1.0f;
	
	float lineSpacing = -1.0f;
	
	int colSpan; // TODO: move elsewhere perhaps
	
	
	public TextBlock()
    {
        super();
    }
	
	/**
	 * Creates candidate block with single line item
	 * and sets its calculated fields
	 * 
	 * @param firstSegment
	 */
	public TextBlock(TextFragment firstSegment)
    {
    	super();
    	
    	this.items.add(new TextLine(firstSegment));
    	this.setCalculatedFields(firstSegment);
    }
	
	/*
	public boolean addSegmentHorizontally(TextFragment newSegment)
	{
		// try adding as superscript to existing line
		
		// 
		
		return false;
	}
	*/
	
	/**
	 * creates a copy with new line objects pointing
	 * to the same text fragment objects
	 * 
	 * @return
	 */
	public TextBlock(TextBlock blockToCopy)
	{
		super();
		
		for (TextLine tl : blockToCopy.items)
			this.items.add(new TextLine(tl));
		this.setCalculatedFields(blockToCopy);
		this.rejectDistance = blockToCopy.rejectDistance;
		this.branchMerged = blockToCopy.branchMerged;
		this.branchSplit = blockToCopy.branchSplit;
		
		this.alignment = blockToCopy.alignment;
//		this.label = blockToCopy.label;
		
		this.evalPara = blockToCopy.evalPara;
		this.evalCell = blockToCopy.evalCell;
		this.evalBullet = blockToCopy.evalBullet;
	}
	
	
	// inherited: List<RTTextLine> items;
	// when adding, this list should be kept 
	// sorted in descending Y order (top to bottom)
	
	public float getRejectDistance() {
		return rejectDistance;
	}

	public void setRejectDistance(float rejectDistance) {
		this.rejectDistance = rejectDistance;
	}

	public boolean isBranchMerged() {
		return branchMerged;
	}

	public void setBranchMerged(boolean branchMerged) {
		this.branchMerged = branchMerged;
	}

	public boolean isBranchSplit() {
		return branchSplit;
	}

	public void setBranchSplit(boolean branchSplit) {
		this.branchSplit = branchSplit;
	}

	public int getAlignment() {
		return alignment;
	}

	public void setAlignment(int alignment) {
		this.alignment = alignment;
	}

	public float getLineSpacing() {
		return lineSpacing;
	}

	public void setLineSpacing(float lineSpacing) {
		this.lineSpacing = lineSpacing;
	}

	/*
	public int getLabel() {
		return label;
	}

	public void setLabel(int label) {
		this.label = label;
	}
	 */
	
	public float getEvalPara() {
		return evalPara;
	}

	public void setEvalPara(float evalPara) {
		this.evalPara = evalPara;
	}

	public float getEvalCell() {
		return evalCell;
	}

	public void setEvalCell(float evalCell) {
		this.evalCell = evalCell;
	}

	public float getEvalBullet() {
		return evalBullet;
	}

	public void setEvalBullet(float evalBullet) {
		this.evalBullet = evalBullet;
	}

	public int getColSpan() {
		return colSpan;
	}

	public void setColSpan(int colSpan) {
		this.colSpan = colSpan;
	}

	/**
	 * Generates a list of text fragments by recursing the line objects
	 */
	public List<TextFragment> fragments()
	{
		List<TextFragment> retVal = new ArrayList<TextFragment>();
		
		for(TextLine l : items)
			retVal.addAll(l.getItems());
		
		return retVal;
	}
	
	/**
	 * Returns the line containing the fragment
	 */
	public TextLine getLineContainingFragment(TextFragment tf)
	{
		for (TextLine l : items)
		{
			if (l.getItems().contains(tf))
				return l;
		}
		return null;
	}
	
	/**
	 * sets average line spacing (baseline distance) in points
	 * (not as multiple of fontsize)
	 * 
	 * pre: lines must be sorted from top to bottom
	 * 
	 */
	public void findLineSpacing()
	{
		if (items.size() >= 2)
		{
			float lineSum = 0.0f;
			TextLine prevLine = null;
			for (TextLine l : items)
			{
				if (prevLine != null)
				{
					lineSum += (prevLine.getY1() - l.getY1());
				}
				prevLine = l;
			}
			lineSpacing = lineSum / (float)(items.size() - 1);
		}
		else
		{
			lineSpacing = -1.0f;
		}
	}
	
	// demerits a la Knuth(-Plass)
	//
	// penalties: 0 - irrelevant; +1000 prohibited -1000 compulsory
	//
	// adjustment ratio: +ve until 1 (max stretchability) or -ve until -1
	//   i.e. relative space with 1 = loose -1 = tight; >1 too loose; <1 too tight
	// 
	// badness: 100 * (|adj ratio|)^3
	//
	// demerits: (1 + badness + penalty)^2 + additional line penalty
	//   (always positive, from 1 to the thousands)
	//
	// formula quite arbitrary
	//
	// adding 1 to the badness instead of using badness by itself will
	// minimize the total number of lines in cases where there are breaks
	// with approximately zero badness
	
	// TODO: calculated fields
	// likelihood of left alignment
	// likelihood of centre "
	// "             justified "
	// "             force justified "
	//
	// if indentations present,
	//   likelihood of 1st line indentation
	//   likelihood fo several paragraphs with indentations
	
	
	
	
	
	// regular paragraph (i.e. without forced line breaks)
	// funny shape or fit, but syntactically correct
	// possibilities for left, centre and right alignment (max deviation gaussian evaluation)
	// constant line spacing (max deviation gaussian evaluation)
	
	// ORDER
	// regular paras first
	// then add superscripts
	// non-aligned paragraphs if not preferred by aligned
	// L-shaped and funny shaped if not preferred by something else
	
	
	/**
	 * @return Likelihood that the candidate block is a bullet
	 */
	public float evalAsBullet()
	{
		if (items.size() > 1) return 0.0f;
		
		float val = Utils.normgaussian(text.length(), 1.0f, 1.0f);
		
		return (val * 0.9f) + 0.1f;
	}
	
	/**
	 * @return Likelihood that the candidate block is a paragraph
	 */
	public float evalAsParagraph()
	{
		float relWidth = getWidth() / fontSize;
		
		float val = Utils.normgaussian(relWidth, 28.0f, 12.0f);
		
//		return (val * 0.75f) + 0.25f;
		return (val * 0.5f) + 0.5f;
		
		/*
		if (true)
//		if (val < 28.0f)
		{
			return (val * 0.75f) + 0.25f;
		}
		else
		{
			// ensure higher score than cell for unusually long lines
			return (val * 0.5f) + 0.5f;
		}
		*/
	}
	
	/**
	 * @return Likelihood that the candidate block is a cell
	 */
	public float evalAsCell()
	{
		float relWidth = getWidth() / fontSize;
		
//		float val = Utils.normgaussian(relWidth, 4.0f, 2.0f);
		float val = Utils.normgaussian(relWidth, 4.0f, 4.0f);
				
//		return (val * 0.5f) + 0.5f;
		return (val * 0.6f) + 0.4f;
	}
	
	/**
	 * @return Likelihood that the candidate block is a table column
	 */
	public float evalAsCol()
	{
		float relWidth = getWidth() / fontSize;
		
//		float val = Utils.normgaussian(relWidth, 4.0f, 2.0f);
		float val = Utils.normgaussian(relWidth, 4.0f, 4.0f);
		
		// prefer longer columns
		float recipItems = 1.0f / items.size();
		float multiplicator = 1.0f - (recipItems * 0.5f);
		
		// TODO: look at alignment
		
//		return (val * 0.5f) + 0.5f;
//		return (val * 0.6f) + 0.4f;
		return (val * multiplicator * 0.6f) + 0.4f;
	}
	
	/**
	 * @return Likelihood that the candidate block is segmented correctly
	 * Uses a heuristic that calls the other eval methods
	 */
	public float evalBlock()
	{
		float retVal = evalAlignment() * evalLineSpacing() * evalNumLines() * evalWhitespace();
		
		if (!evalOverlappingLines()) retVal = retVal * 0.25f;
		
		return retVal;
	}
	
	
	/**
	 * prefers larger numbers of lines
	 * (asymptotic function)
	 * 
	 * @return
	 */
	public float evalNumLines()
	{
		if (this.items.size() < 1) return 0.0f;
		
		/*
		float numLines = this.items.size();
		
		float retVal = 1.0f - (0.50f * (1.0f / numLines));
		
		// for     0.25
		// returns 0.75        for 1 line
		//         0.875       for 2 lines
		//         0.91666 ... for 3 lines
		//         etc
		
		return retVal;
		*/
		
		else if (this.items.size() == 1) return 0.99f;
		else return 1.0f;
	}
	
	
	/**
	 * returns true if no overlapping lines found (OK)
	 * otherwise false
	 * pre: lines correctly found and sorted in vertical order
	 * 
	 * @return
	 */
	public boolean evalOverlappingLines()
	{
		// check that no line vertically overlaps the centre of another
		for (TextLine l1 : items)
		{
			for (TextLine l2 : items)
			{
				if (l1 != l2)
				{
					if (SegmentUtils.vertCentresIntersect(l1, l2))
						return false;
				}
			}
		}
		
		// check that all sequential pairs of lines intersect one another horizontally
		TextLine prevLine = null;
		for (TextLine thisLine : items)
		{
			if (prevLine != null)
			{
				if (!SegmentUtils.horizIntersect(thisLine, prevLine))
					return false;
			}
			prevLine = thisLine;
		}
		
		return true;
	}
	
	/**
	 * Returns a value corresponding to the evenness of the line spacing
	 * higher = better/more even
	 * max is 1
	 * 
	 * @return
	 */
	public float evalLineSpacing()
	{
		if (items.size() < 2)
			return 1;
	
		// 2019-03-20 changed from distance to als
		// to min/max calculations, so they don't cancel each other out
		
		// calculate existing line spacing average
    	float als = calcAvgLineSpacing();
		
		// assume sorted vertically
//		Collections.sort(blockFrom.getItems(), new YComparator());
		
//    	float maxDeviation = 0.0f;
		float maxLS = Float.MIN_VALUE;
		float minLS = Float.MAX_VALUE;
		TextSegment prevSeg = null;
		for (TextLine thisSeg : items)
		{
			if (prevSeg == null)
			{
				// do nothing
			}
			else
			{
				float lineSpacing = prevSeg.getY1() - thisSeg.getY1();
				/*
				float deviation = lineSpacing - als;
				if (deviation < 0) deviation = 0.0f - deviation;
				
				if (deviation > maxDeviation)
					maxDeviation = deviation;
				*/
				if (lineSpacing > maxLS) maxLS = lineSpacing;
				if (lineSpacing < minLS) minLS = lineSpacing;
			}
			prevSeg = thisSeg;
		}
		
		// OLD: calculate related deviation to fontsize
		// float relMaxDiff = maxDeviation / calcAvgFontSize();
		
		// calculate related deviation to average
//		float relMaxDiff = maxDeviation / als;
		float deviation = maxLS - minLS;
		float relMaxDiff = deviation / als;
		
		return Utils.normgaussian(relMaxDiff, 0, 0.20f);
	}

	
	public float evalWordSpacing()
	{
		// returns minimum value for all lines
		
		if (items.size() == 0)
			return -1.0f;
    	
		float minVal = Float.MAX_VALUE;
		for (TextLine l : items)
		{
			float val = l.evalSpacing();
			if (val < minVal)
				minVal = val;
		}
		
    	return minVal;
	}
	
	/*
	public float evalBlock()
	{
		return evalAlignment() * evalWhitespace();
	}
	*/
	
	/**
	 * 
	 * returns the max alignment score of left/right/cen/jus
	 * multiplied by wordspacing eval
	 * 
	 * and sets alignment variable
	 *  
	 * @return
	 */
	public float evalAlignment()
	{
		// return the max alignment score of left/right/cen/jus
		// multiplied by wordspacing eval
		
		float evalLeft = evalLeftAlign();
		float evalCentre = evalCentreAlign();
		float evalRight = evalRightAlign();
		float evalJustify = evalJustify();
		
		float evalWordSpacing = evalWordSpacing();
		
		// for justify ignore wordspacing eval
		
		float retVal = 0.0f;
		
		if (evalLeft * evalWordSpacing > retVal)
		{
			retVal = evalLeft * evalWordSpacing;
			alignment = ALIGN_LEFT;
		}
		
		if (evalJustify > retVal)
		{
			retVal = evalJustify;
			alignment = ALIGN_JUSTIFY;
		}
		
		if (evalCentre * evalWordSpacing > retVal)
		{
			retVal = evalCentre * evalWordSpacing;
			alignment = ALIGN_CENTRE;
		}
		
		if (evalRight * evalWordSpacing > retVal)
		{
			retVal = evalRight * evalWordSpacing;
			alignment = ALIGN_RIGHT;
		}
		
		return retVal;
	}
	
	public float evalWhitespace()
	{
		return evalWhitespace(0.5f);
	}
	
	/**
	 * returns false if whitespace gap found with
	 * gapWidth on two consecutive lines
	 * or 1/2 gapWidth on more than two consecutive lines
	 * 
	 * @param gapWidth
	 * @return
	 */
	public float evalWhitespace(float gapWidth)
	{
		float retVal = 1.0f;
		
		List<WhitespaceGap> finalGaps = new ArrayList<WhitespaceGap>();
		
		List<WhitespaceGap> currGaps = new ArrayList<WhitespaceGap>();
		for (TextLine l : items)
		{
			List<WhitespaceGap> thisLineGaps = new ArrayList<WhitespaceGap>();
			
			TextSegment prevSeg = null;
			for (TextSegment thisSeg : l.getItems())
			{
				if (prevSeg != null && thisSeg.getX1() > prevSeg.getX2())
				{
					thisLineGaps.add(new WhitespaceGap
							(prevSeg.getX2(), thisSeg.getX1(), l.getY1(), l.getY2(),
									l.getFontSize()));
				}
				
				prevSeg = thisSeg;
			}
			
			List<WhitespaceGap> usedCurrGaps = new ArrayList<WhitespaceGap>();
			List<WhitespaceGap> newCurrGaps = new ArrayList<WhitespaceGap>();
			List<WhitespaceGap> matchedLineGaps = new ArrayList<WhitespaceGap>();
			
			// create lengthened gaps from currGaps by seeing whether they intersect
			// with this line's gaps
			for (WhitespaceGap wgc : currGaps)
			{
				for (WhitespaceGap wgl : thisLineGaps)
				{
					if (SegmentUtils.horizIntersect(wgc, wgl))
					{
						// create new wgc and shrink its horizontal extent if necessary
						// for n+1 lines
						
						WhitespaceGap wgc1 = new WhitespaceGap(wgc);
						wgc1.numLines ++;
						
						if (wgl.getX1() > wgc.getX1()) wgc1.setX1(wgl.getX1());
						if (wgl.getX2() < wgc.getX2()) wgc1.setX2(wgl.getX2());
						
						// set fontsize to the larger of the two
						if (wgl.fontSize > wgc.fontSize)
							wgc1.fontSize = wgl.fontSize;
						
						// mark the old wgc as "used"
						// this will stop it being removed from currGaps later
						usedCurrGaps.add(wgc);
						newCurrGaps.add(wgc1);
						
//						matchedLineGaps.add(wgl);
						
						// create new wgc for this line only for 1 line
						
						/*
						wgc.numLines ++;
						if (wgl.fontSize > wgc.fontSize)
							wgc.fontSize = wgl.fontSize;
						usedCurrGaps.add(wgc);
						matchedLineGaps.add(wgl);
						break;
						*/
						
						// do not break as there may be further gaps to enlarge
					}
				}
			}
			
			
			// move all gaps from currGaps, which did not intersect this line's gaps
			// and therefore cannot be extended any more, to finalGaps
			List<WhitespaceGap> unusedCurrGaps = new ArrayList<WhitespaceGap>();
			for (WhitespaceGap wgc : currGaps)
				if (!usedCurrGaps.contains(wgc))
					unusedCurrGaps.add(wgc);
			finalGaps.addAll(unusedCurrGaps);
			
			// currGaps will now contain the newly extended gaps and the single-liners
			// from the current line
			currGaps.clear();
			currGaps.addAll(newCurrGaps);
			currGaps.addAll(thisLineGaps);
		}
		
		finalGaps.addAll(currGaps);
		
		
		
		for (WhitespaceGap wgf : finalGaps)
		{
			if (wgf.numLines == 2)
			{
				if (wgf.getWidth() > wgf.fontSize * gapWidth)
				{
					retVal = 0;
				}
			}
			if (wgf.numLines > 2)
			{
				if (wgf.getWidth() > wgf.fontSize * gapWidth * 0.5)
				{
					retVal = 0;
				}
			}
		}
		
		return retVal;
	}
	
	// 2019-05-06
	public float evalWhitespaceOld()
	{
		float retVal = 1.0f;
		
		List<WhitespaceGap> finalGaps = new ArrayList<WhitespaceGap>();
		
		List<WhitespaceGap> currGaps = new ArrayList<WhitespaceGap>();
		for (TextLine l : items)
		{
			List<WhitespaceGap> thisLineGaps = new ArrayList<WhitespaceGap>();
			
			TextSegment prevSeg = null;
			for (TextSegment thisSeg : l.getItems())
			{
				if (prevSeg != null && thisSeg.getX1() > prevSeg.getX2())
				{
					thisLineGaps.add(new WhitespaceGap
							(prevSeg.getX2(), thisSeg.getX1(), l.getY1(), l.getY2(),
									l.getFontSize()));
				}
				
				prevSeg = thisSeg;
			}
			
			List<WhitespaceGap> usedCurrGaps = new ArrayList<WhitespaceGap>();
			List<WhitespaceGap> matchedLineGaps = new ArrayList<WhitespaceGap>();
			
			for (WhitespaceGap wgc : currGaps)
			{
				for (WhitespaceGap wgl : thisLineGaps)
				{
					if (SegmentUtils.horizIntersect(wgc, wgl))
					{
						wgc.numLines ++;
						if (wgl.fontSize > wgc.fontSize)
							wgc.fontSize = wgl.fontSize;
						usedCurrGaps.add(wgc);
						matchedLineGaps.add(wgl);
						break;
					}
					// TODO: if doesn't intersect 100%, reduce with
				}
			}
			
			// TODO: if gap is shrunk (or later grown) horizontally, add twice!
			
			// move all gaps from currGaps which are not in usedCurrGaps to finalGaps
			List<WhitespaceGap> unusedCurrGaps = new ArrayList<WhitespaceGap>();
			for (WhitespaceGap wgc : currGaps)
				if (!usedCurrGaps.contains(wgc))
					unusedCurrGaps.add(wgc);
			currGaps.removeAll(unusedCurrGaps);
			finalGaps.addAll(unusedCurrGaps);
			
			// add all unmatched thisLineGaps to currGaps
			for (WhitespaceGap wgl : thisLineGaps)
				if (!matchedLineGaps.contains(wgl))
					currGaps.add(wgl);
		}
		
		finalGaps.addAll(currGaps);
		
		
		
		for (WhitespaceGap wgf : finalGaps)
		{
			if (wgf.numLines == 2)
			{
				if (wgf.getWidth() > wgf.fontSize * 0.5)
				{
					retVal = 0;
				}
			}
			if (wgf.numLines > 2)
			{
				if (wgf.getWidth() > wgf.fontSize * 0.25)
				{
					retVal = 0;
				}
			}
		}
		
		return retVal;
	}
	
	// TODO: for alignment, also depend slightly on segment width?
	
	public float evalLeftAlign()
	{
		if (items.size() < 1)
			return -1;
		
		// calculate average leftmost coordinate
		float sumX1 = 0.0f;
    	int numValues = 0;
		for (TextLine thisSeg : items)
		{
			sumX1 += thisSeg.getX1();
			numValues ++;
		}
		
		float avgX1 = sumX1 / numValues;
		
		float maxDiff = 0;
		
		for (TextLine thisSeg : items)
		{
			float x1Diff = thisSeg.getX1() - avgX1;
			if (x1Diff < 0) x1Diff = 0.0f - x1Diff;
			
			if (x1Diff > maxDiff) maxDiff = x1Diff;
		}
		
		// calculate related deviation to fontsize
		float relMaxDiff = maxDiff / calcAvgFontSize();
		
		// TODO: add 10% of width of block to standard deviation
		return Utils.normgaussian(relMaxDiff, 0, 0.5f);
	}
	
	public float evalCentreAlign()
	{
		if (items.size() < 1)
			return -1;
		
		// calculate average centre coordinate
		float sumXmid = 0.0f;
    	int numValues = 0;
		for (TextLine thisSeg : items)
		{
			sumXmid += thisSeg.getXmid();
			numValues ++;
		}
		
		float avgXmid = sumXmid / numValues;
		
		float maxDiff = 0;
		
		for (TextLine thisSeg : items)
		{
			float xMidDiff = thisSeg.getXmid() - avgXmid;
			if (xMidDiff < 0) xMidDiff = 0.0f - xMidDiff;
			
			if (xMidDiff > maxDiff) maxDiff = xMidDiff;
		}
		
		// calculate related deviation to fontsize
		float relMaxDiff = maxDiff / calcAvgFontSize();
		
		// TODO: add 10% of width of block to standard deviation
		return Utils.normgaussian(relMaxDiff, 0, 0.5f);
	}
	
	public float evalRightAlign(boolean lastLine)
	{
		if (items.size() < 1)
			return -1;
		
		if (!lastLine && items.size() < 2)
			return -1;
		
		// calculate average rightmost coordinate
		float sumX2 = 0.0f;
    	int numValues = 0;
		for (TextLine thisSeg : items)
		{
			if (lastLine || thisSeg != items.get(items.size() - 1))
			{
				sumX2 += thisSeg.getX2();
				numValues ++;
			}
		}
		
		float avgX2 = sumX2 / numValues;
		
		float maxDiff = 0;
		
		for (TextLine thisSeg : items)
		{
			if (lastLine || thisSeg != items.get(items.size() - 1))
			{
				float x2Diff = thisSeg.getX2() - avgX2;
				if (x2Diff < 0) x2Diff = 0.0f - x2Diff;
				
				if (x2Diff > maxDiff) maxDiff = x2Diff;
			}
		}
		
		// calculate related deviation to fontsize
		float relMaxDiff = maxDiff / calcAvgFontSize();
		
		// TODO: add 10% of width of block to standard deviation
		return Utils.normgaussian(relMaxDiff, 0, 0.5f);
	}
	
	public float evalRightAlign()
	{
		return evalRightAlign(true);
	}
	
	public float evalBlockAlign()
	{
		return Utils.minimum(evalLeftAlign(), evalRightAlign());
	}
	
	public float evalJustify()
	{
		if (items.size() < 2) // currently returns -1 and not 1 if no check possible
			return evalLeftAlign();
		else
			return Utils.minimum(evalLeftAlign(), evalRightAlign(false));
	}
	
	public float calcAvgLineSpacing()
    {
    	// calculate existing line spacing average
    	
		// assume sorted vertically
//		Collections.sort(blockFrom.getItems(), new YComparator());
		
    	float sumLineSpaces = 0.0f;
    	int numValues = 0;
		TextSegment prevSeg = null;
		for (TextLine thisSeg : items)
		{
			if (prevSeg == null)
			{
				// do nothing
			}
			else
			{
				float lineSpacing = prevSeg.getY1() - thisSeg.getY1();
				sumLineSpaces += lineSpacing;
				numValues ++;
			}
			prevSeg = thisSeg;
		}
		
		return(sumLineSpaces / numValues);
    }
	
	// potentially useful later for "paragraphs" with variable
	// fontsize/line heights
	public float calcAvgLineGaps()
    {
    	// calculate existing line spacing average
    	
		// assume sorted vertically
//		Collections.sort(blockFrom.getItems(), new YComparator());
		
    	float sumLineGaps = 0.0f;
    	int numValues = 0;
		TextSegment prevSeg = null;
		for (TextLine thisSeg : items)
		{
			if (prevSeg == null)
			{
				// do nothing
			}
			else
			{
				float lineGap = prevSeg.getY1() - thisSeg.getY2();
				sumLineGaps += lineGap;
				numValues ++;
			}
			prevSeg = thisSeg;
		}
		
		return(sumLineGaps / numValues);
    }
	
	public float calcAvgFontSize()
    {
    	// calculate existing font size average
    	
		// assume sorted vertically
//		Collections.sort(blockFrom.getItems(), new YComparator());
		
    	float sumLineSpacings = 0.0f;
    	int numValues = 0;
		for (TextLine thisSeg : items)
		{
			if (thisSeg.getFontSize() <= 0)
			{
//				System.err.println("invalid fontsize of line");
			}
			else
			{
				sumLineSpacings += thisSeg.getFontSize();
				numValues ++;
			}
		}
		
		return(sumLineSpacings / numValues);
    }
	
    // IXMillumSegment
	public void setElementAttributes(Document resultDocument, 
    	Element newSegmentElement, GenericSegment pageDim, float resolution, int id)
    {
        super.setElementAttributes(resultDocument, newSegmentElement, pageDim, 
        		resolution, id);
        
        // TODO: HACK -- the below lines refer to the this.getText() method, as the
        // text currently is not stored.  But this is due to change when the
        // line-finding is integrated.
        newSegmentElement.setAttribute
            ("font-size", Float.toString(this.getFontSize()));
//	        newSegmentElement.setAttribute
//	            ("text-ratio", Float.toString(this.getTextRatio()));
//	        newSegmentElement.setAttribute
//	        	("info", getInfoString());
        
        String type = "unknown";
        switch(classification)
        {
        	case PARAGRAPH:
        		type = "paragraph"; break;
        	case HEADING:
        		type = "heading"; break;
        	case OTHER_TEXT:
        		type = "other-text"; break;
        	case CELL:
        		type = "cell"; break;
        	case ORDERED_LIST_ITEM:
        		type = "ol-item"; break;
        	case UNORDERED_LIST_ITEM:
        		type = "ul-item"; break;
        	case HEADER:
        		type = "header"; break;
        	case FOOTER:
        		type = "footer"; break;
        	case TABLE_HEADING:
        		type = "table-heading"; break;
        	case TABLE_SUBTITLE:
        		type = "table-subtitle"; break;
        	default:
        		type = "other";
        }
        
        newSegmentElement.setAttribute("type", type);
        
        // System.out.println("creating text node: " + this.getText());
        // done in super!
        //newSegmentElement.appendChild
            //(resultDocument.createTextNode(this.getText()));
    }

	public void addAsXHTML(Document resultDocument, Element parent)//, GenericSegment pageDim)
    {
        Element newParagraphElement, newTextElement, tempElement = null;
        
        if (classification == HEADING || classification == HEADING_3)
            newParagraphElement = resultDocument.createElement("h3");
        else if (classification == HEADING_2)
            newParagraphElement = resultDocument.createElement("h2");
        else if (classification == HEADING_1)
            newParagraphElement = resultDocument.createElement("h1");
        else if (classification == UNORDERED_LIST_ITEM)
        {
//        	tempElement = resultDocument.createElement("ul");
//        	newParagraphElement = resultDocument.createElement("li");
        	// 22.01.2011 <ul>s are now separate objects
        	newParagraphElement = resultDocument.createElement("li");
        }
        else
            newParagraphElement = resultDocument.createElement("p");

        // HEADING_1 to HEADING_3 in str mode
        if (classification >= 40 && classification < 60)
        {
        	boolean bold = false;
        	boolean italic = false;
        	boolean underlined = false;
        	int superSubscript = 0;
        	String textToAdd = "";
        	float prevX2 = -1.0f;
        	
        	Iterator iter1 = items.iterator();
        	while(iter1.hasNext())
        	{
        		TextLine tl1 = (TextLine)iter1.next();
//        		System.out.println("tl1: " + tl1);
        		if (tl1.getX1() < prevX2)
				{
					// new line: do we insert a carriage return?
					if (prevX2 < strXPosNewline)
						textToAdd = textToAdd + ("\n");
				}
				prevX2 = tl1.getX2();
				
        		Iterator iter2 = tl1.getItems().iterator();
        		while(iter2.hasNext())
        		{
        			TextLine tl2 = (TextLine)iter2.next();
//        			System.out.println("tl2: " + tl2);
        			TextFragment prevFrag = null;
        			Iterator iter3 = tl2.getItems().iterator();
        			while(iter3.hasNext())
        			{
        				TextFragment tf = (TextFragment)iter3.next();
//        				System.out.println("tf: " + tf);
//        				System.out.println("tf is superSubscript: " + tf.isStrIsUnderlined());
        				
        				// if neither matches the whitespace character
        				// and horiz gap > 0.25(afs)
        				if (prevFrag != null)
        				{
        					float horizGap = tf.getX1() - prevFrag.getX2();
        					float afs = (tf.getFontSize() + prevFrag.getFontSize()) / 2.0f;
        					if (!(tf.getText().trim().matches("[\\s]") || prevFrag.getText().trim().matches("[\\s]")) &&
        						horizGap > afs * 0.15f)
        					{
        						textToAdd = textToAdd + " ";
        					}
        				}	
        				
        				if (tf.isBold() == bold && tf.isItalic() == italic && 
        					tf.isUnderlined() == underlined && tf.getSuperSubscript() == superSubscript)
        				{
        					// same style as previous character
//        					textToAdd.concat(tf.getText()); // doesn't work?!?
        					textToAdd = textToAdd + (tf.getText());
        				}
        				else
        				{
        					// add text
//        					if (textToAdd.length() > 0)
        					if (textToAdd.trim().length() > 0)
        					{
        						if (superSubscript == 1)
        						{
	        						if (underlined)
	        						{
	//        							System.out.println("underlined with textToAdd: " + textToAdd);
	//	        		        		System.out.println("textToAdd.length: " + textToAdd.trim().length());
	        							if (bold && italic)
	    	        		        	{
	        								Element newTextElement4 = resultDocument.createElement("sup");
	        								newParagraphElement.appendChild(newTextElement4);
	        								Element newTextElement3 = resultDocument.createElement("u");
	    	        		        		newTextElement4.appendChild(newTextElement3);
	    	        		            	Element newTextElement2 = resultDocument.createElement("b");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (bold)
	    	        		        	{
	    	        		        		Element newTextElement3 = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement3);
	    	        		        		Element newTextElement2 = resultDocument.createElement("u");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("b");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (italic)
	    	        		        	{
	    	        		        		Element newTextElement3 = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement3);
	    	        		        		Element newTextElement2 = resultDocument.createElement("u");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("u");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	        						}
	        						else
	        						{
	        							if (bold && italic)
	    	        		        	{
	        								Element newTextElement3 = resultDocument.createElement("sup");
	        								newParagraphElement.appendChild(newTextElement3);
	    	        		            	Element newTextElement2 = resultDocument.createElement("b");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (bold)
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("b");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (italic)
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else
	    	        		        	{
	    	        		        		newTextElement = resultDocument.createElement("sup");
	    	        		        		newParagraphElement.appendChild(newTextElement);
	    	        		        	}
	        						}
        						}
        						else if (superSubscript == -1)
        						{
//        							System.out.println("outputting subscript");
        							if (underlined)
	        						{
	//        							System.out.println("underlined with textToAdd: " + textToAdd);
	//	        		        		System.out.println("textToAdd.length: " + textToAdd.trim().length());
	        							if (bold && italic)
	    	        		        	{
	        								Element newTextElement4 = resultDocument.createElement("sub");
	        								newParagraphElement.appendChild(newTextElement4);
	        								Element newTextElement3 = resultDocument.createElement("u");
	    	        		        		newTextElement4.appendChild(newTextElement3);
	    	        		            	Element newTextElement2 = resultDocument.createElement("b");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (bold)
	    	        		        	{
	    	        		        		Element newTextElement3 = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement3);
	    	        		        		Element newTextElement2 = resultDocument.createElement("u");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("b");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (italic)
	    	        		        	{
	    	        		        		Element newTextElement3 = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement3);
	    	        		        		Element newTextElement2 = resultDocument.createElement("u");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("u");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	        						}
	        						else
	        						{
	        							if (bold && italic)
	    	        		        	{
	        								Element newTextElement3 = resultDocument.createElement("sub");
	        								newParagraphElement.appendChild(newTextElement3);
	    	        		            	Element newTextElement2 = resultDocument.createElement("b");
	    	        		        		newTextElement3.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (bold)
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("b");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else if (italic)
	    	        		        	{
	    	        		        		Element newTextElement2 = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement2);
	    	        		        		newTextElement = resultDocument.createElement("i");
	    	        		        		newTextElement2.appendChild(newTextElement);
	    	        		        	}
	    	        		        	else
	    	        		        	{
	    	        		        		newTextElement = resultDocument.createElement("sub");
	    	        		        		newParagraphElement.appendChild(newTextElement);
	    	        		        	}
	        						}
        						}
        						else // normal text (required in order to initialize newTextElement)
        						{
        							if (underlined)
            						{
//            							System.out.println("underlined with textToAdd: " + textToAdd);
//    	        		        		System.out.println("textToAdd.length: " + textToAdd.trim().length());
            							if (bold && italic)
        	        		        	{
            								Element newTextElement3 = resultDocument.createElement("u");
        	        		        		newParagraphElement.appendChild(newTextElement3);
        	        		            	Element newTextElement2 = resultDocument.createElement("b");
        	        		        		newTextElement3.appendChild(newTextElement2);
        	        		        		newTextElement = resultDocument.createElement("i");
        	        		        		newTextElement2.appendChild(newTextElement);
        	        		        	}
        	        		        	else if (bold)
        	        		        	{
        	        		        		Element newTextElement2 = resultDocument.createElement("u");
        	        		        		newParagraphElement.appendChild(newTextElement2);
        	        		        		newTextElement = resultDocument.createElement("b");
        	        		        		newTextElement2.appendChild(newTextElement);
        	        		        	}
        	        		        	else if (italic)
        	        		        	{
        	        		        		Element newTextElement2 = resultDocument.createElement("u");
        	        		        		newParagraphElement.appendChild(newTextElement2);
        	        		        		newTextElement = resultDocument.createElement("i");
        	        		        		newTextElement2.appendChild(newTextElement);
        	        		        	}
        	        		        	else
        	        		        	{
        	        		        		newTextElement = resultDocument.createElement("u");
        	        		        		newParagraphElement.appendChild(newTextElement);
        	        		        	}
            						}
            						else
            						{
            							if (bold && italic)
        	        		        	{
        	        		            	Element newTextElement2 = resultDocument.createElement("b");
        	        		        		newParagraphElement.appendChild(newTextElement2);
        	        		        		newTextElement = resultDocument.createElement("i");
        	        		        		newTextElement2.appendChild(newTextElement);
        	        		        	}
        	        		        	else if (bold)
        	        		        	{
//        	        		        		System.out.println("bold with textToAdd: " + textToAdd);
//        	        		        		System.out.println("textToAdd.length: " + textToAdd.trim().length());
        	        		        		newTextElement = resultDocument.createElement("b");
        	        		        		newParagraphElement.appendChild(newTextElement);
        	        		        	}
        	        		        	else if (italic)
        	        		        	{
        	        		        		newTextElement = resultDocument.createElement("i");
        	        		        		newParagraphElement.appendChild(newTextElement);
        	        		        	}
        	        		        	else
        	        		        	{
        	        		            	newTextElement = newParagraphElement;
        	        		        	}
            						}
        						}
	        		            
	        		            // the following lines would just add the string
	        		            // without <br/>s
	        		            //newColumnElement.appendChild
	        		    		//(resultDocument.createTextNode(theText));
	        		            String textSection = new String();
	        		            
	        		            for (int n = 0; n < textToAdd.length(); n ++)
	        		            {
	        		            	String thisChar = textToAdd.substring(n, n + 1);
	        		            	if (thisChar.equals("\n"))
	        		            	{
	        		            		newTextElement.appendChild
	        		            			(resultDocument.createTextNode(textSection));
	        		                    newTextElement.appendChild
	        		                    	(resultDocument.createElement("br"));
	        		                    textSection = "";
	        		            	}
	        		            	else
	        		            	{
	        		            		textSection = textSection.concat(thisChar);
	        		            	}
	        		            }
	        		            
	        		            if (textSection.length() > 0)
	        		            	
	        		            	newTextElement.appendChild
	        		            	(resultDocument.createTextNode(textSection));
        					
        					}
        					
        					// update bold and italic
        		            bold = tf.isBold();
        		            italic = tf.isItalic();
        		            underlined = tf.isUnderlined();
        		            textToAdd = "";
        		            textToAdd = textToAdd + (tf.getText());
        		            superSubscript = tf.getSuperSubscript();
        				}
        				prevFrag = tf;
        			}
        		}
        	}
        	
        	// if remaining text
        	if(textToAdd.trim().length() > 0)
        	{
        		if (bold && italic)
	        	{
	            	Element newTextElement2 = resultDocument.createElement("b");
	        		newParagraphElement.appendChild(newTextElement2);
	        		newTextElement = resultDocument.createElement("i");
	        		newTextElement2.appendChild(newTextElement);
	        	}
	        	else if (bold)
	        	{
	        		newTextElement = resultDocument.createElement("b");
	        		newParagraphElement.appendChild(newTextElement);
	        	}
	        	else if (italic)
	        	{
	        		newTextElement = resultDocument.createElement("i");
	        		newParagraphElement.appendChild(newTextElement);
	        	}
	        	else
	        	{
	            	newTextElement = newParagraphElement;
	        	}
	            
	            // the following lines would just add the string
	            // without <br/>s
	            //newColumnElement.appendChild
	    		//(resultDocument.createTextNode(theText));
	            String textSection = new String();
	            
	            for (int n = 0; n < textToAdd.length(); n ++)
	            {
	            	String thisChar = textToAdd.substring(n, n + 1);
	            	if (thisChar.equals("\n"))
	            	{
	            		newTextElement.appendChild
	            			(resultDocument.createTextNode(textSection));
	                    newTextElement.appendChild
	                    	(resultDocument.createElement("br"));
	                    textSection = "";
	            	}
	            	else
	            	{
	            		textSection = textSection.concat(thisChar);
	            	}
	            }
	            
	            if (textSection.length() > 0)
	            	
	            	newTextElement.appendChild
	            	(resultDocument.createTextNode(textSection));

        	}
        	
        }
        else // normal mode
        {
        	if (isBold() && isItalic())
        	{
            	Element newTextElement2 = resultDocument.createElement("b");
        		newParagraphElement.appendChild(newTextElement2);
        		newTextElement = resultDocument.createElement("i");
        		newTextElement2.appendChild(newTextElement);
        	}
        	else if (isBold())
        	{
        		newTextElement = resultDocument.createElement("b");
        		newParagraphElement.appendChild(newTextElement);
        	}
        	else if (isItalic())
        	{
        		newTextElement = resultDocument.createElement("i");
        		newParagraphElement.appendChild(newTextElement);
        	}
        	else
        	{
            	newTextElement = newParagraphElement;
        	}
            
            String theText = this.getText();
            // the following lines would just add the string
            // without <br/>s
            //newColumnElement.appendChild
    		//(resultDocument.createTextNode(theText));
            String textSection = new String();
            
            for (int n = 0; n < theText.length(); n ++)
            {
            	String thisChar = theText.substring(n, n + 1);
            	if (thisChar.equals("\n"))
            	{
            		newTextElement.appendChild
            			(resultDocument.createTextNode(textSection));
                    newTextElement.appendChild
                    	(resultDocument.createElement("br"));
                    textSection = "";
            	}
            	else
            	{
            		textSection = textSection.concat(thisChar);
            	}
            }
            
            if (textSection.length() > 0)
            	
            	newTextElement.appendChild
            	(resultDocument.createTextNode(textSection));
        }

        /*
        newParagraphElement.appendChild
            (resultDocument.createTextNode(this.getText()));
        */
        
        // 22.01.2011 <ul>s are now separate objects
        /*
        if (classification == UNORDERED_LIST_ITEM)
        {
        	tempElement.appendChild(newParagraphElement);
        	parent.appendChild(tempElement);
        }
        else
        */
        	parent.appendChild(newParagraphElement);
    }
	
	class WhitespaceGap extends GenericSegment
	{
		int numLines = 1;
		float fontSize = 0;
		
		public WhitespaceGap(float x1, float x2, float y1, float y2, float fontSize)
		{
			super(x1, x2, y1, y2);
			this.fontSize = fontSize;
		}
		
		// clones
		public WhitespaceGap(WhitespaceGap wgc)
		{
			super(wgc.x1, wgc.x2, wgc.y1, wgc.y2);
			this.fontSize = wgc.fontSize;
			this.numLines = wgc.numLines;
		}
	}
} public class TextFragment extends CompositeSegment<CharSegment>
{
	// TODO: what about rotated text/text with negative width/height?

	// should these variables be included even in the base class?
	/*
	float xScale;
	float yScale;
	float wordSpacing;
	float widthOfSpace;
	*/
	boolean overprint = false;

//	2011-01-24 unnecessary
//	protected String tagName = "text-fragment";
	
    /**
     * Constructor.
     *
     * @param x1 The x1 coordinate of the segment.
     * @param x2 The x2 coordinate of the segment.
     * @param y1 The y1 coordinate of the segment.
     * @param y2 The y2 coordinate of the segment.
     * @param text The textual contents of the segment.
     * @param font The (main) font of the segment.
     * @param fontSize The (main) font size in the segment.
     */
    public TextFragment(
        float x1,
        float x2,
        float y1,
        float y2,
        String text,
        String fontName,
        float fontSize
        )
    {
		super(x1, x2, y1, y2, text, fontName, fontSize);
    }
    
    public TextFragment(
        float x1,
        float x2,
        float y1,
        float y2,
        String text,
        PDFont font,
        float fontSize
        )
    {
		super(x1, x2, y1, y2, text, Utils.findFontName(font), fontSize);
    }
    
    public TextFragment(
        float x1,
        float x2,
        float y1,
        float y2
        )
    {
		super(x1, x2, y1, y2);
    }
    
    public TextFragment()
    {
		super();
    }
    
    public TextFragment(CharSegment c)
    {
		super(c.getX1(), c.getX2(), c.getY1(), c.getY2());
		items.add(c);
		text = c.getText();
		fontName = c.getFontName();
		fontSize = c.getFontSize();
    }

	// not in current use (I think) -- WRONG
    // now by default sets level to zero (primitive)
    public TextFragment(TextPosition tPos)
    {
    	super(tPos.getX(),
                tPos.getX() + (tPos.getWidth()),
                tPos.getY(),
                tPos.getY() + (tPos.getFontSize() * tPos.getYScale()),
//              tPos.getCharacter(),
                tPos.getUnicode(),
//              tPos.getFont().getBaseFont(),
                Utils.findFontName(tPos.getFont()),
                tPos.getFontSize() * tPos.getYScale());
    }

	/**
     * This will create a TextFragment object from a TextPosition object.
     * As of PDFBox 0.7.2, this is the method currently in use, which
	 * converts co-ordinates back to the original system.
	 *
     * @param tPos - the TextPosition object; pageDim - page dimensions in order to
	 * convert co-ordinates
	 * @return The new TextFragment object
     */
    public TextFragment(TextPosition tPos, GenericSegment pageDim)
    {
        super(tPos.getX(),
                tPos.getX() + tPos.getWidth(),
                pageDim.getY2() - tPos.getY(),
                pageDim.getY2() - tPos.getY() + (tPos.getFontSize() * tPos.getYScale()),
//              tPos.getCharacter(),
                tPos.getUnicode(),
//              tPos.getFont().getBaseFont(),
                Utils.findFontName(tPos.getFont()),
                tPos.getFontSize() * tPos.getYScale());
    }
    
    public List<OpTuple> sourceOps()
    {
    	List<OpTuple> retVal = new ArrayList<OpTuple>();
    	
    	for (CharSegment cs : items)
    		retVal.add(cs.getSourceOp());
    	
    	ListUtils.removeDuplicates(retVal);
    	return retVal;
    }
    
	public boolean isOverprint() {
		return overprint;
	}

	public void setOverprint(boolean overprint) {
		this.overprint = overprint;
	}
    
    /*
     * with the tagName stuff this should not be necessary
     * 
    public void addAsXML(Document resultDocument, Element parent, GenericSegment pageDim,
    	float resolution)
    {
        //TODO: find a better name for this element?
        Element newSegmentElement = resultDocument.createElement("text-fragment");
        super.setElementAttributes(resultDocument, newSegmentElement, pageDim, resolution);
        parent.appendChild(newSegmentElement);
    }
    */
	
	// 2011-11-02 overrides method from CompositeSegment
	// to ignore whitespace characters (with sometimes fancy coordinates)
	public void findBoundingBox()
	{
		boolean first = true;

		int noItems = 0;
		double fontSizeTotal = 0.0;

		for (CharSegment thisSegment : items)
		{
//			System.out.println(thisSegment.getText());
			if (!(thisSegment instanceof IBlankSegment))// &&
//				thisSegment.getText() != null && // keeps from crashing if text missing due to e.g. missing unicode mapping
//				!(thisSegment.getText().equals(" ")))
			{
				if (thisSegment instanceof TextSegment)
				{
					noItems++;
					fontSizeTotal += ((TextSegment) thisSegment).getFontSize();
				}
	
				if (first)
				{
					x1 = thisSegment.getX1();
					x2 = thisSegment.getX2();
					y1 = thisSegment.getY1();
					y2 = thisSegment.getY2();
					first = false;
				} else
				{
					growBoundingBox(thisSegment);
				}
			}
		}
		if (noItems >= 0)
		{
			fontSize = (float) (fontSizeTotal / noItems);
		} else
		{
			fontSize = -1.0f;
		}
	}
} public class ImgOutputUtils 
{
	
	final public static boolean DEBUG_TEXT = false;
	
	public static void outputPNG(List<? extends GenericSegment> segments, 
			GenericSegment pageBounds, String filename)
	{
		outputPNG(segments, pageBounds, filename, 1.0f);
	}
	
	
	/**
	 * todo: 
	 * 
	 * @param bi
	 * @param segments
	 * @param pageBounds
	 * @param scale
	 * @param col
	 */
	public static void drawSegments(BufferedImage bi, List<? extends GenericSegment> segments, 
			GenericSegment pageBounds, float scale, Color col)
	{
		Graphics2D g = bi.createGraphics();
		
		GenericSegment dim = new GenericSegment(
				pageBounds.getX1() * scale, 
				pageBounds.getX2() * scale, 
				pageBounds.getY1() * scale, 
				pageBounds.getY2() * scale
		);
		
		for (GenericSegment gs : segments)
		{
			// draw text lines first if CandidateBlock
			/*
			if (gs instanceof CandidateBlock)
			{
				CandidateBlock cb = (CandidateBlock)gs;
				
				for (GenericSegment gs2 : cb.getItems())
				{
					RTTextLine tl = (RTTextLine)gs2;
					
					GenericSegment s2 = new GenericSegment(
							tl.getX1() * scale, 
							tl.getX2() * scale, 
							tl.getY1() * scale, 
							tl.getY2() * scale);
					
					g.setColor(Color.lightGray);
					
					g.drawRect((int)s2.getX1(), (int)dim.getHeight() - (int)s2.getY2(), 
							(int)s2.getWidth(), (int)s2.getHeight());
					
					g.setColor(Color.black);
				}
			}
			*/
			
			GenericSegment s = new GenericSegment(
					gs.getX1() * scale, 
					gs.getX2() * scale, 
					gs.getY1() * scale, 
					gs.getY2() * scale
			);
			
			g.setColor(col);
			
			g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
					(int)s.getWidth(), (int)s.getHeight());
			
			g.setColor(Color.black);
		}
	}
	
	
	public static BufferedImage createImage(List<? extends GenericSegment> segments, 
			GenericSegment pageBounds, float scale)
	{
		long t1 = System.currentTimeMillis();
		
		GenericSegment dim = new GenericSegment(
				pageBounds.getX1() * scale, 
				pageBounds.getX2() * scale, 
				pageBounds.getY1() * scale, 
				pageBounds.getY2() * scale
		);
		
		BufferedImage bi = new BufferedImage((int)dim.getWidth(), (int)dim.getHeight(), 
				BufferedImage.TYPE_INT_RGB);
		
		Graphics2D g = bi.createGraphics();
		
		// white background
		g.setColor(Color.white);
		g.fillRect(0, 0, bi.getWidth(), bi.getHeight());
		
		g.setColor(Color.black);
		for (GenericSegment gs : segments)
		{
			GenericSegment s = new GenericSegment(
					gs.getX1() * scale, 
					gs.getX2() * scale, 
					gs.getY1() * scale, 
					gs.getY2() * scale
			);
			
			if (gs instanceof CharSegment)
			{
				CharSegment cs = (CharSegment)gs;
				if (cs.getText() != null && cs.getText().equals(" "))
				{
					g.setColor(Color.red);
					
					g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
							(int)s.getWidth(), (int)s.getHeight());
					
					g.setColor(Color.black);
				}
				else
				{
					g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
							(int)s.getWidth(), (int)s.getHeight());
				}
			}
			else
			{
				g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
						(int)s.getWidth(), (int)s.getHeight());
			}
			
			g.setColor(Color.black);
		}
		
		long t2 = System.currentTimeMillis();
		
		if (DEBUG_TEXT) System.out.println("Time to generate image: " + (t2 - t1));
		
		return bi;
	}
	
	/*
	// TODO: refactor and include as extendable class
	
	public static BufferedImage createImage(
			AdjacencyGraph<? extends GenericSegment> ag, 
			GenericSegment pageBounds, float scale)
	{
		long t1 = System.currentTimeMillis();
		
		GenericSegment dim = new GenericSegment(
				pageBounds.getX1() * scale, 
				pageBounds.getX2() * scale, 
				pageBounds.getY1() * scale, 
				pageBounds.getY2() * scale
		);
		
		BufferedImage bi = new BufferedImage((int)dim.getWidth(), (int)dim.getHeight(), 
				BufferedImage.TYPE_INT_RGB);
		
		Graphics2D g = bi.createGraphics();
		
		// white background
		g.setColor(Color.white);
		g.fillRect(0, 0, bi.getWidth(), bi.getHeight());
		
		g.setColor(Color.black);
		for (GenericSegment gs : ag.getVertSegmentList())
		{
			GenericSegment s = new GenericSegment(
					gs.getX1() * scale, 
					gs.getX2() * scale, 
					gs.getY1() * scale, 
					gs.getY2() * scale
			);
			
			if (gs instanceof CharSegment)
			{
				CharSegment cs = (CharSegment)gs;
				if (cs.getText() != null && cs.getText().equals(" "))
				{
					g.setColor(Color.gray);
					
					g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
							(int)s.getWidth(), (int)s.getHeight());
					
					g.setColor(Color.black);
				}
				else
				{
					g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
							(int)s.getWidth(), (int)s.getHeight());
				}
			}
			else
			{
				if (gs instanceof TextBlock)
					g.setColor(Color.blue);
					
				g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
						(int)s.getWidth(), (int)s.getHeight());
			}
			
			g.setColor(Color.black);
		}
		g.setColor(Color.red);
		for (AdjacencyEdge<? extends GenericSegment> e : ag.getEdges())
		{
			GenericSegment s = e.toBoundingSegment();
			g.drawRect((int)s.getX1(), (int)dim.getHeight() - (int)s.getY2(), 
					(int)s.getWidth(), (int)s.getHeight());
		}
		g.setColor(Color.black);
		
		long t2 = System.currentTimeMillis();
		
		if (DEBUG_TEXT) System.out.println("Time to generate image: " + (t2 - t1));
		
		return bi;
	}
	*/
	
	public static void outputPNG(List<? extends GenericSegment> segments, 
			GenericSegment pageBounds, String filename, float scale)
	{
//		Uncomment for JPEG output (faster)
//		String newFilename = filename.replaceFirst("\\.png$", ".jpeg");
//		File outputfile = new File(newFilename);
		File outputfile = new File(filename);
		try 
		{
			long t3 = System.currentTimeMillis();
			ImageIO.write(createImage(segments, pageBounds, scale), "png", outputfile);
			long t4 = System.currentTimeMillis();
			if (DEBUG_TEXT) System.out.println("Time to write image: " + (t4 - t3));
		} 
		catch (IOException e) 
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/*
	public static void outputPNG(AdjacencyGraph<? extends GenericSegment> ag, 
			GenericSegment pageBounds, String filename, float scale)
	{
//		Uncomment for JPEG output (faster)
//		String newFilename = filename.replaceFirst("\\.png$", ".jpeg");
//		File outputfile = new File(newFilename);
		File outputfile = new File(filename);
		try 
		{
			long t3 = System.currentTimeMillis();
			ImageIO.write(createImage(ag, pageBounds, scale), "png", outputfile);
			long t4 = System.currentTimeMillis();
			if (DEBUG_TEXT) System.out.println("Time to write image: " + (t4 - t3));
		} 
		catch (IOException e) 
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	*/
} public class SegmentUtils
{
	/*
	public static void mergeIntersectingCompositeSegs
		(List<CompositeSegment<? extends GenericSegment>> segs)
	{
		List<CompositeSegment<? extends GenericSegment>> segsToRemove =
			new ArrayList<CompositeSegment<? extends GenericSegment>>();
		
		for (CompositeSegment<? extends GenericSegment> cs : segs)
		{
			for (CompositeSegment<? extends GenericSegment> cs1 : segs)
			{
				if (centresIntersect(cs, cs1))
				{
					segsToRemove.add(cs1);
					cs.getItems().addAll(cs1.getItems());
					cs.setCalculatedFields();
				}
			}
		}
	}
	*/
	
	public static boolean horizMinIntersect(GenericSegment seg1,
		GenericSegment seg2, float percent)
	{
		// calculate intersectionWidth as the * of the
		// smaller width dimension
		float intersectionWidth = seg1.getWidth() * percent;
		if (seg2.getWidth() < seg1.getWidth())
			intersectionWidth = seg2.getWidth() * percent;
		
		// seg1.getX1() lies within bounds of seg2
		//    ###      ####  seg1
		//  #######  ####    seg2
		if (seg1.getX1() >= seg2.getX1() && seg1.getX1() <= seg2.getX2())
		{
			// intersection between seg1.getX1() and min(seg1.getX2(), seg2.getX2())
			return (Utils.minimum(seg1.getX2(), seg2.getX2()) - seg1.getX1() 
				>= intersectionWidth);
		}
		// seg2.getX1() lies within bounds of seg1
		//	#######  ####    seg1
		//    ###      ####  seg2
		else if (seg2.getX1() >= seg1.getX1() && seg2.getX1() <= seg1.getX2())
		{
			// intersection between seg2.getX1() and min(seg1.getX2(), seg2.getX2())
		//	System.out.println("actual: " + (Utils.minimum(seg1.getX2(), seg2.getX2()) - seg1.getX1()));
		//	System.out.println("required 0.2: " + intersectionWidth);
			return (Utils.minimum(seg1.getX2(), seg2.getX2()) - seg2.getX1() 
				>= intersectionWidth);
		}
		return false;
	}
	
	public static boolean horizIntersect(GenericSegment seg1,
		GenericSegment seg2)
	{
		return (seg1.getX1() >= seg2.getX1() && seg1.getX1() <= seg2.getX2())  //seg1.getX1() edge lies along seg2 boundary
			|| (seg2.getX1() >= seg1.getX1() && seg2.getX1() <= seg1.getX2()); //or seg2.getX1() edge lies along seg1 boundary
		// 13.07.10 seems sufficient
	}

	public static boolean horizIntersect(GenericSegment seg1, float sx1,
		float sx2)
	{
		GenericSegment seg2 = new GenericSegment(sx1, sx2, -1, -1);
		return (seg1.getX1() >= seg2.getX1() && seg1.getX1() <= seg2.getX2())
			|| (seg2.getX1() >= seg1.getX1() && seg2.getX1() <= seg1.getX2());
	}

	public static boolean horizIntersect(GenericSegment seg, float val)
	{
		return (seg.getX1() <= val && seg.getX2() >= val)
			|| (seg.getX1() >= val && seg.getX2() <= val);
	}

	public static boolean vertMinIntersect(GenericSegment seg1,
		GenericSegment seg2, float percent)
	{
		// calculate intersectionWidth as the * of the
		// smaller width dimension
		float intersectionHeight = seg1.getHeight() * percent;
		if (seg2.getHeight() < seg1.getHeight())
			intersectionHeight = seg2.getHeight() * percent;
		
//			System.out.println("intersection height limit: " + intersectionHeight);
		// seg1.getY1() lies within bounds of seg2
		if (seg1.getY1() >= seg2.getY1() && seg1.getY1() <= seg2.getY2())
		{
			// intersection between seg1.getY1() and min(seg1.getY2(), seg2.getY2())
//				System.out.println("actual intersection height: "+(Utils.minimum(seg1.getY2(), seg2.getY2()) - seg1.getY1()));
			return (Utils.minimum(seg1.getY2(), seg2.getY2()) - seg1.getY1() 
				>= intersectionHeight);
		}
		// seg2.getY1() lies within bounds of seg1
		else if (seg2.getY1() >= seg1.getY1() && seg2.getY1() <= seg1.getY2())
		{
			// intersection between seg2.getX1() and min(seg1.getX2(), seg2.getX2())
//				System.out.println("actual intersection height: "+(Utils.minimum(seg1.getY2(), seg2.getY2()) - seg1.getY1()));
			return (Utils.minimum(seg1.getY2(), seg2.getY2()) - seg2.getY1() 
				>= intersectionHeight);
		}
		return false;
	}
	
	public static boolean vertIntersect(GenericSegment seg1, GenericSegment seg2)
	{
		return (seg1.getY1() >= seg2.getY1() && seg1.getY1() <= seg2.getY2())
			|| (seg2.getY1() >= seg1.getY1() && seg2.getY1() <= seg1.getY2());
	}

	public static boolean vertIntersect(GenericSegment seg1, float sy1,
		float sy2)
	{
		GenericSegment seg2 = new GenericSegment(-1, -1, sy1, sy2);
		return (seg1.getY1() >= seg2.getY1() && seg1.getY1() <= seg2.getY2())
			|| (seg2.getY1() >= seg1.getY1() && seg2.getY1() <= seg1.getY2());
	}

	public static boolean vertIntersect(GenericSegment seg, float val)
	{
		return (seg.getY1() <= val && seg.getY2() >= val)
			|| (seg.getY1() >= val && seg.getY2() <= val);
	}

	public static boolean horizCentresIntersect(GenericSegment seg1, GenericSegment seg2)
	{
		return (horizIntersect(seg1, seg2.getXmid()) ||
				horizIntersect(seg2, seg1.getXmid()));
	}
	
	public static boolean vertCentresIntersect(GenericSegment seg1, GenericSegment seg2)
	{
		return (vertIntersect(seg1, seg2.getYmid()) ||
				vertIntersect(seg2, seg1.getYmid()));
	}
	
	public static boolean centresIntersect(GenericSegment seg1, GenericSegment seg2)
	{
		return (horizCentresIntersect(seg1, seg2) && vertCentresIntersect(seg1, seg2));
	}
	
	public static boolean intersects(GenericSegment seg1, GenericSegment seg2)
	{
		//System.out.println("seg1: " + seg1 + "\nseg2: " + seg2);
		//System.out.println("H: " + horizIntersect(seg1, seg2) + " V: " + vertIntersect(seg1, seg2));
		return horizIntersect(seg1, seg2) && vertIntersect(seg1, seg2);
	}
	
	public static boolean intersects(AdjacencyEdge<? extends GenericSegment> e1,
		AdjacencyEdge<? extends GenericSegment> e2)
    {
		/* 2011-01-26 variables never read...
		GenericSegment a1 = e1.getNodeFrom();
        GenericSegment b1 = e1.getNodeTo();
        GenericSegment a2 = e2.getNodeFrom();
        GenericSegment b2 = e2.getNodeTo();
        */
		
        // returns FALSE if a nonsensical comparison is requested
        // TODO: throw exception if a horizontal edge
        // is compared with a vertical?
        if ((e1.isHorizontal() == false && e2.isHorizontal() == true) ||
            (e1.isHorizontal() == true && e2.isHorizontal() == false))
            return false;
        
        float hi1, low1, hi2, low2;
        
        switch(e1.getDirection())
        {
            case AdjacencyEdge.REL_LEFT:
                hi1 = e1.getNodeFrom().getX1();
                low1 = e1.getNodeTo().getX2();
                break;
            case AdjacencyEdge.REL_RIGHT:
                hi1 = e1.getNodeTo().getX1();
                low1 = e1.getNodeFrom().getX2();
                break;
            case AdjacencyEdge.REL_ABOVE:
                hi1 = e1.getNodeTo().getY1();
                low1 = e1.getNodeFrom().getY2();
                break;
            case AdjacencyEdge.REL_BELOW:
                hi1 = e1.getNodeFrom().getY1();
                low1 = e1.getNodeTo().getY2();
                break;
            default:
                // yet another nonsensical comparison!
                return false;
        }
        
        switch(e2.getDirection())
        {
            case AdjacencyEdge.REL_LEFT:
                hi2 = e2.getNodeFrom().getX1();
                low2 = e2.getNodeTo().getX2();
                break;
            case AdjacencyEdge.REL_RIGHT:
                hi2 = e2.getNodeTo().getX1();
                low2 = e2.getNodeFrom().getX2();
                break;
            case AdjacencyEdge.REL_ABOVE:
                hi2 = e2.getNodeTo().getY1();
                low2 = e2.getNodeFrom().getY2();
                break;
            case AdjacencyEdge.REL_BELOW:
                hi2 = e2.getNodeFrom().getY1();
                low2 = e2.getNodeTo().getY2();
                break;
            default:
                // yet another nonsensical comparison!
                return false;
        }
        
        return (low1 >= low2 && low1 <= hi2) ||
        (hi1 >= low2 && hi1 <= hi2) ||
        (low1 < low2 && hi1 > hi2);
    }
} public class XMLUtils 
{
	/**
     * This is the default encoding of the text to be output.
     */
    public static final String DEFAULT_ENCODING =
        //null;
        //"ISO-8859-1";
        //"ISO-8859-6"; //arabic
        //"US-ASCII";
        "UTF-8";
        //"UTF-16";
        //"UTF-16BE";
        //"UTF-16LE";
    
    /**
     * Generates an XML resultDocument from the processing result passed in theResult
     * 
     * @param theResult - result document in internal model consisting of a list of Pages
     * @param toXHTML - true for XHTML output, false for XMIllum output (no longer in use)
     * @param borders - true if the resulting HTML should make table borders black
     * @return the XML result document
     * @throws DocumentProcessingException
     */
	public static org.w3c.dom.Document processResultToXMLDocument
	(List<Page> theResult, boolean toXHTML, boolean borders)
	throws DocumentProcessingException
	{
	    org.w3c.dom.Document resultDocument;
	    
	    // only used in the case of XHTML
	    Element newBodyElement = null;
	    Element docElement = null;
	    
	    // set up the XML file
	    try
	    {
	        if (toXHTML)
	        {
	            resultDocument = setUpXML("html");
	            docElement = resultDocument.getDocumentElement();
	            if (borders)
	            {
	            	// add borders stuff here
	            	Element newHeadElement = resultDocument.createElement("head");
	            	Element newStyleElement = resultDocument.createElement("style");
	            	newStyleElement.setAttribute("type", "text/css");
	            	Text newTextElement = resultDocument.createTextNode
	        			("table {border-collapse: collapse;}");
	            	Text newTextElement2 = resultDocument.createTextNode
	            		("td, th {border: 1px solid grey; padding: 2px 4px;}");
	            	newStyleElement.appendChild(newTextElement);
	            	newStyleElement.appendChild(newTextElement2);
	            	newHeadElement.appendChild(newStyleElement);
	            	docElement.appendChild(newHeadElement);
	            }
	            newBodyElement = resultDocument.createElement("body");
	        }
	        else
	        {
	            resultDocument = setUpXML("PDFResult");
	            docElement = resultDocument.getDocumentElement();
	        }
	    }
	    catch (ParserConfigurationException e)
	    {
	        throw new DocumentProcessingException(e);
	    }
	    
	    // add the new page element
	    //docElement = resultDocument.getDocumentElement();
	    
	    int pageNo = 0;
	    Iterator resultIter = theResult.iterator();
	    while(resultIter.hasNext())
	    {
	    	GenericSegment gs = (GenericSegment)resultIter.next();
	    	if (gs instanceof Page)
	    	{
	            Page resultPage = (Page)gs;
	            pageNo ++;
	            if (toXHTML)
	            {
	                resultPage.setPageNo(pageNo);
	                resultPage.addAsXHTML(resultDocument, newBodyElement);
	            }
	            else
	            {
	                Element newPageElement = resultDocument.createElement("page");
	                newPageElement.setAttribute("page_number", Integer.toString(pageNo));
	                //we want to use the MediaBox!
	                //resultPage.findBoundingBox();
	                // System.out.println("Result page: " + resultPage);
	                
	                resultPage.addAsXML(resultDocument, newPageElement, 
		                	resultPage, Utils.XML_RESOLUTION, -1);
	                
	                docElement.appendChild(newPageElement);
	            }
	    	}
	    	else if (gs instanceof IXHTMLSegment)//(gs.getClass() == Cluster.class || gs.getClass() == strRasterSegment.class)
	    	{
	    		IXHTMLSegment c = (IXHTMLSegment)gs;
	    		if (toXHTML)
	            {
	                c.addAsXHTML(resultDocument, newBodyElement);
	            }
	    		// for XMIllum output, the top-level segment is always a Page
	    	}
	        // run NG on page
	        // output page (cluster-wise) to ontology
	    }
	
	    if (toXHTML)
	        docElement.appendChild(newBodyElement);
	    
	    return resultDocument;
	}
	
	/**
	 * Sets up the XML document structure
	 * 
	 * @param nodeName
	 * @return
	 * @throws ParserConfigurationException
	 */
	protected static org.w3c.dom.Document setUpXML(String nodeName) 
	        throws ParserConfigurationException
    {
        //try
        //{
            DocumentBuilderFactory myFactory = DocumentBuilderFactory.newInstance();
            DocumentBuilder myDocBuilder = myFactory.newDocumentBuilder();
            DOMImplementation myDOMImpl = myDocBuilder.getDOMImplementation();
            // resultDocument = myDOMImpl.createDocument("at.ac.tuwien.dbai.pdfwrap", "PDFResult", null);
            org.w3c.dom.Document resultDocument = 
                myDOMImpl.createDocument("at.ac.tuwien.dbai.pdfwrap", nodeName, null);
            return resultDocument;
        //}
        //catch (ParserConfigurationException e)
        //{
         //   e.printStackTrace();
         //   return null;
        //}
        
    }
	
	/**
	 * Returns the contents of the file in a byte array.
	 * 
	 * @param file
	 * @return
	 * @throws IOException
	 */
    public static byte[] getBytesFromFile(File file) throws IOException {
        	InputStream is = new FileInputStream(file);
    
        // Get the size of the file
        long length = file.length();
    
        // You cannot create an array using a long type.
        // It needs to be an int type.
        // Before converting to an int type, check
        // to ensure that file is not larger than Integer.MAX_VALUE.
        if (length > Integer.MAX_VALUE) {
            // File is too large
        }
    
        // Create the byte array to hold the data
        byte[] bytes = new byte[(int)length];
    
        // Read in the bytes
        int offset = 0;
        int numRead = 0;
        while (offset < bytes.length
               && (numRead=is.read(bytes, offset, bytes.length-offset)) >= 0) {
            offset += numRead;
        }
    
        // Ensure all the bytes have been read in
        if (offset < bytes.length) {
            throw new IOException("Could not completely read file "+file.getName());
        }
    
        // Close the input stream and return bytes
        is.close();
        return bytes;
    }
    
    
    /**
     * Outputs the processing result as XHTML
     *
     * @param pages       - processing result as list of Page objects
     * @param outFilePath - full path of output file, including filename and extension
     * @throws IOException
     */
    public static void outputXHTMLResult(List<Page> pages, String outFilePath)
            throws IOException 
    {
        try 
        {
            Document resultDocument = XMLUtils.processResultToXMLDocument(pages, true, true);

            Writer output = null;

            boolean toConsole = false;
            String encoding = null;
            System.out.println("writing " + outFilePath);
            File outFile = new File(outFilePath);

            if (toConsole) 
            {
                output = new OutputStreamWriter(System.out);
            } 
            else 
            {
                if (encoding != null) 
                {
                    output = new OutputStreamWriter(
                            new FileOutputStream(outFile), encoding);
                } 
                else 
                {
                    //use default encoding
                    output = new OutputStreamWriter(
                            new FileOutputStream(outFile));
                }
            }
            XMLUtils.serializeXML(resultDocument, output);

            if (output != null) 
            {
                output.close();
            }
        } 
        catch (DocumentProcessingException dpe) 
        {
            dpe.printStackTrace();
        }
    }
    
    
    /**
     * Serializes the resultDocument to XML
     * 
     * @param resultDocument
     * @return
     * @throws DocumentProcessingException
     */
    public static byte[] serializeXML(org.w3c.dom.Document resultDocument)
    		throws DocumentProcessingException
    {
        // calls the above and returns a byte[] from the XML Document.
        
        ByteArrayOutputStream outStream = new ByteArrayOutputStream();
        
        try
        {
        	Writer output = new OutputStreamWriter(outStream, DEFAULT_ENCODING);
            serializeXML(resultDocument, output);
        }
        catch (IOException e)
        {
        	throw new DocumentProcessingException(e);
    	}

        return outStream.toByteArray();
    }
    
    /**
     * Serializes the resultDocument to XML
     * 
     * @param resultDocument
     * @param outStream
     * @throws DocumentProcessingException
     */
    public static void serializeXML(org.w3c.dom.Document resultDocument, OutputStream outStream)
    		throws DocumentProcessingException
    {
        try
        {
        	Writer output = new OutputStreamWriter(outStream, DEFAULT_ENCODING);
            serializeXML(resultDocument, output);
        }
        catch (IOException e)
        {
        	throw new DocumentProcessingException(e);
    	}
    }
    
    /**
     * Serializes the resultDocument to XML
     * 
     * @param resultDocument
     * @param output
     * @throws IOException
     */
    public static void serializeXML
        (org.w3c.dom.Document resultDocument, Writer output)
        throws IOException
    {
        // The third parameter in the constructor method for
        // _OutputFormat_ controls whether indenting should be
        // used.  Unfortunately, I have found some bugs in the
        // indenting implementation that have corrupted the text
        // so I have switched it off. 
         
        OutputFormat myOutputFormat =
            new OutputFormat(resultDocument,
                             "UTF-8",
                             true);

        // output used to be replaced with System.out
        XMLSerializer s = 
        new XMLSerializer(output, 
                              myOutputFormat);

        try {
        s.serialize(resultDocument);
        // next line added by THA 21.03.05
        output.flush();
        }
        catch (IOException e) {
            System.err.println("Couldn't serialize document: "+
               e.getMessage());
            throw e;
        }        

         // end of addition
    }
}
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import org.w3c.dom.DOMImplementation;
import org.w3c.dom.Element;
import com.tamirhassan.pdfxtk.comparators.XmidComparator;
import com.tamirhassan.pdfxtk.comparators.Y1Comparator;
import com.tamirhassan.pdfxtk.comparators.Y2Comparator;
import com.tamirhassan.pdfxtk.exceptions.DocumentProcessingException;
import com.tamirhassan.pdfxtk.graph.AdjacencyGraph;
import com.tamirhassan.pdfxtk.model.GenericSegment;
import com.tamirhassan.pdfxtk.model.Page;
import com.tamirhassan.pdfxtk.model.TextBlock;
import com.tamirhassan.pdfxtk.model.TextFragment;
import com.tamirhassan.pdfxtk.utils.ImgOutputUtils;
import com.tamirhassan.pdfxtk.utils.SegmentUtils;
import com.tamirhassan.pdfxtk.utils.XMLUtils;
package com.tamirhassan.pdfxtk;





/* modified from CustomPageDrawer.java
 * these portions are subject to the following license:
 * 
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


/**
 * Main method to load a document and return a list of paragraphs in XHTML format
 *
 * @author Tamir Hassan
 */
public class PageAnalyser extends DocumentProcessor{

    // 
    // the following constants are used for debugging
    //
    protected final static boolean DEBUG_1 = false;
    protected final static boolean DEBUG_2 = false;
    protected final static boolean DEBUG_3 = false;
    
    protected final static boolean WRITE_IMAGES = false;
    
    protected final static boolean DEBUG_PRINT = false;
    //	protected final static boolean DEBUG_PRINT = false;
    protected final static boolean DEBUG_IMG_FAIL = false;
    protected final static boolean DEBUG_IMG_SH = false;
    //	protected final static boolean DEBUG_IMG_SH = true;
    //	protected final static boolean DEBUG_IMG = true;
    protected final static boolean DEBUG_IMG = false;
    protected final static boolean DEBUG_IMG_TF = false;
    protected final static boolean DEBUG_IMG_TF_FAIL = false;
    //	protected final static boolean DEBUG_IMG_FAIL = true;
    //	protected final static boolean LIMIT_COORDS = true;
    protected final static boolean LIMIT_COORDS = false;

    //	protected final static boolean RESORT = true;
    protected final static boolean RESORT = false;
    //	protected final static boolean CHECK_OVERLAP = false;
    protected final static boolean CHECK_OVERLAP = true;
    	protected final static boolean UNMERGE = false;
//    protected final static boolean UNMERGE = true;

    protected final static boolean DEBUG_IMG_UT = false;
    //	protected final static boolean DEBUG_IMG_UT = false;
    
    protected AdjacencyGraph<TextFragment> ag;
    
	public PageAnalyser()
	{
		
	}
	
	public Page customPageProcessing()
	{
		if (OUTPUT_TEXT_IMG)
            ImgOutputUtils.outputPNG(getMtf(),
                    getPageDims(), "intermediate/text-merged-subinstr.png");


        List<TextFragment> mtfCrop = new ArrayList<>();
        for (TextFragment tf : getMtf()) {
            if (LIMIT_COORDS) {
                if (tf.getY1() > 328.0 && tf.getY1() < 686.0)
                    mtfCrop.add(tf);
            } else {
                mtfCrop.add(tf);
            }
        }

        if (mtfCrop.size() == 0) {
            System.err.println("No text found!");

            if (LIMIT_COORDS) {
                System.out.println("LIMIT_COORDS is true!");
                System.exit(0);
            }
        }

        List<TextBlock> unmergedBlocks =
                initialSegmentation(mtfCrop, getPageDims());
        Collections.sort(unmergedBlocks, new Y1Comparator());
        
        
        Page theResult = new Page();
        theResult.getItems().addAll(unmergedBlocks);
        
        return theResult;
	}
	
    /**
     * Initial segmentation, to be carried out before ruled and unruled table detection
     *
     * @param mtfCrop
     * @param dims
     * @return
     */
    protected List<TextBlock> initialSegmentation
    (List<TextFragment> mtfCrop, GenericSegment dims) 
    {
    	// AdjacencyGraph<TextFragment> ag = new AdjacencyGraph<>();
    	ag = new AdjacencyGraph<>();
        // add all TextFragments (i.e. sub-instructions)
        ag.addList(mtfCrop);

        // TODO: join 

//      ag.setNeighbourRules(AdjacencyGraph.NEIGHBOUR_X_Y_INTERSECT);
//      ag.generateEdgesSingle();

        ag.generateEdges();
        ag.removeEdgesAboveLeft();

        SegmentationEngine se = new SegmentationEngine(ag, new SegmentationRules());
        se.setPageDims(dims);
        se.setDebugPrint(DEBUG_PRINT);
        se.setDebugImg(DEBUG_IMG);
        se.setDebugImgFail(DEBUG_IMG_FAIL);
        se.setResort(RESORT);
        se.setCheckOverlap(CHECK_OVERLAP);

        List<TextBlock> blocks = se.doSegmentation();
        if (WRITE_IMAGES) ImgOutputUtils.outputPNG(blocks, dims, "intermediate/segmentation-initialblocks.png");

        List<TextBlock> retVal;
        if (UNMERGE) 
        {
            List<TextBlock> unmergedBlocks = se.postUnmerging(blocks);

            if (WRITE_IMAGES) 
            {
                createLabelledImage(blocks, se, "intermediate/segmentation-labelled-blocks.jpeg");

                ImgOutputUtils.outputPNG(unmergedBlocks, dims, "intermediate/segmentation-unmerged-blocks.png");
                createLabelledImage(unmergedBlocks, se, "intermediate/segmentation-labelled-unmerged-blocks.jpeg");
            }

            retVal = unmergedBlocks;
        } 
        else 
        {

            retVal = blocks;
        }
        
    	Collections.sort(retVal, new Y1Comparator());
    	for (TextBlock b : retVal)
    		b.setCalculatedFields();
    	
    	return retVal;
    }


    /**
     * Methods for finding neighbouring CandidateBlocks after initial segmentation
     * TODO: These should be replaced by non-static methods and
     * the list should be generated only once for both directions
     *
     * @param gs   - list of CandidateBlocks
     * @param segs - list of segments from which the CandidateBlocks were built
     * @return nearest left neighbour or null
     */
    protected static TextBlock findLeftNeighbour(TextBlock gs, List<? extends GenericSegment> segs) {
        List<TextBlock> blocksAtHeight = new ArrayList<>();

        for (GenericSegment gs2 : segs)
            if (gs2 instanceof TextBlock && SegmentUtils.vertCentresIntersect(gs, gs2))
                blocksAtHeight.add((TextBlock) gs2);

//    	if (blocksAtHeight.contains((gs))) System.out.print("assertion failed: " + (3/0));

        blocksAtHeight.add(gs);
        blocksAtHeight.sort(new XmidComparator());