/*-----------------------------------------------------------------------------
-- JAWAA 2.0 --

Copyright information:

Susan H. Rodger, Pretesh Patel, Diana Jackson, Ayonike Akingbade
Computer Science Department
Duke University
August 2002
Supported by National Science Foundation DUE-9752583.

Copyright (c) 2002
All rights reserved.

Redistribution and use in source and binary forms are permitted
provided that the above copyright notice and this paragraph are
duplicated in all such forms and that any documentation,
advertising materials, and other materials related to such
distribution and use acknowledge that the software was developed
by the author.  The name of the author may not be used to
endorse or promote products derived from this software without
specific prior written permission.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.

--------------------------------------------------------------------------------*/


/*-------------------------------------------------------------------------------
File:                           RootedTreeEngine.java
Package:                        JAWAA Version 2.0
Author:                         Pretesh Patel, Diana Jackson, Ayonike Akingbade
Date:                           August 2002
Description of Contents:        
                                
---------------------------------------------------------------------------------*/
package jawaa.layout;

import java.awt.*;
import jawaa.structure.*;

public class RootedTreeEngine
{
    protected RootedTreeEngine()
    {
	
    }

    public static void layout(JawaaTreeNode root, Point p, int width)
    {
	vertOffset = root.getHeight() + 15;
	horzOffset = root.getWidth() + 15;
	root.setLocation(p.x, p.y);
	getContour(root);
	setLocation(root, p, 0);
    }

    protected static void debug(ListNode n, String s, JawaaTreeNode
				node)
    {
	System.out.print(node.getName() +" " + s +": ");
	while(n != null)
	{
	    System.out.print(((JawaaTreeNode)n.myData).getName() + " ");
	    n = n.myNext;
	}
	System.out.println("");
    }
    
    protected static void getContour(JawaaTreeNode n)
    {
	if(n == null)
	    return;
	getContour(n.getRightChild());
	getContour(n.getLeftChild());
	getLeftContour(n);
	getRightContour(n);

	JawaaTreeNode left = n.getLeftChild();
	JawaaTreeNode right = n.getRightChild();
	if((left != null) || (right != null))
	{
	    if((left == null) && (right != null))
	    {
		right.offset = 1;
		//right.setText(right.get(0) + " 1");
	    }
	    else if((left != null) && (right == null))
	    {
		left.offset = -1;
		//left.setText(left.get(0) + " -1");
	    }
	    else
	    {
		int height = Math.min(treeHeight(n.getLeftChild()),
				      treeHeight(n.getRightChild()));
		ListNode leftside = left.rightContour;
		ListNode rightside = right.leftContour;
		//debug(leftside, "right contour of left", n);
		//debug(rightside, "left contour of right", n);
		int leftspace = 0;
		int rightspace = 0;
/*		
		for(int i=0; i<height; i++)
		{
		    leftspace += ((JawaaTreeNode)leftside.myData).offset;
		    rightspace +=
			((JawaaTreeNode)rightside.myData).offset;
		    
		    if((leftside.myNext == null) ||
		       (((JawaaTreeNode)leftside.myNext.myData).offset
			>= 0))
			leftside = leftside.myNext;
		    if((rightside.myNext == null) ||
		       (((JawaaTreeNode)rightside.myNext.myData).offset <= 0))
			rightside = rightside.myNext;

		    
		}
*/	   
		leftspace=getTotalOffset(left, height, 1);
		rightspace=getTotalOffset(right, height, 0);

		int j = 0;
		int k = 0;
		while((rightspace - leftspace) != 2)
		{
		    if(Math.abs(leftspace) > Math.abs(rightspace))
		    {
			leftspace--;
			k++;
		    }
		    else if(Math.abs(rightspace)>Math.abs(leftspace))
		    {
			rightspace++;
			j++;
		    }
		    else
		    {
			rightspace++;
			leftspace--;
			j++;
			k++;
		    }
		}
		if((j == 0) && (k==0))
		{
		    j++;
		    k++;
		}
		right.offset = (j);
		//	right.setText(right.get(0)+" " +j);
		left.offset = (-1*k);
		//	left.setText(left.get(0) + " " +left.offset);
	    }
	}
	return;
    }

    protected static ListNode getLeftContour(JawaaTreeNode n)
    {
	try{
		
	if(n == null)
	{
	    return null;
	}
	if(n.leftContour != null)
	    return n.leftContour;
	int leftTreeHeight = treeHeight(n.getLeftChild());
	int rightTreeHeight = treeHeight(n.getRightChild());
	if(leftTreeHeight < rightTreeHeight)
	{
	    ListNode contour = getLeftContour(n.getLeftChild());
	    ListNode contour_pointer = contour;
	    ListNode temp = getLeftContour(n.getRightChild());
	    for(int i=0; i<leftTreeHeight; i++)
	    {
		temp = temp.myNext;
		if(contour_pointer.myNext != null)
		    contour_pointer = contour_pointer.myNext;
	    }
	    if(contour != null)
		contour_pointer.myNext = temp;
	    else contour = temp;
	    n.leftContour = new ListNode(n, contour);
	    return n.leftContour;
	}
	else{

	    n.leftContour = new ListNode(n, getLeftContour(n.getLeftChild()));
	    return n.leftContour;
	}
	}
	catch(NullPointerException e)
	{
	    //    e.printStackTrace();
	}
	return null;
    }

    protected static ListNode getRightContour(JawaaTreeNode n)
    {
	if(n == null)
	{
	    return null;
	}
	if(n.rightContour != null)
	    return n.rightContour;
	int leftTreeHeight = treeHeight(n.getLeftChild());
	int rightTreeHeight = treeHeight(n.getRightChild());
	if(rightTreeHeight < leftTreeHeight)
	{
	    ListNode contour = getRightContour(n.getRightChild());
	    ListNode contour_pointer = contour;
	    ListNode temp = getRightContour(n.getLeftChild());
	    for(int i=0; i<rightTreeHeight; i++)
	    {
		temp = temp.myNext;
		if(contour_pointer.myNext != null)
		    contour_pointer = contour_pointer.myNext;
	    }
	    if(contour != null)
		contour_pointer.myNext = temp;
	    else contour = temp;
	    n.rightContour = new ListNode(n, contour);
	    return n.rightContour;
	}
	else{
	    n.rightContour = new ListNode(n, getRightContour(n.getRightChild()));
	    return n.rightContour;
	}
    }
    

    protected static void setLocation(JawaaTreeNode n, Point p, int y)
    {
	if(n == null)
	    return;
	Point loc = new Point(p.x, p.y);
	loc.y += y * vertOffset;
	loc.x += n.offset * horzOffset;
	y = 1;
	n.setCenterLocation(loc.x, loc.y);
	setLocation(n.getLeftChild(), loc, y);
	setLocation(n.getRightChild(), loc, y);
	return;
    }

    /**
     * @param direction indicates which direction you are searching
     * in. 0 means left, 1 means right
     */
    protected static int getTotalOffset(JawaaTreeNode n, int maxheight, int direction)
    {
	if((n == null) || (maxheight==0))
	    return 0;
	else
	{
	    int left=getTotalOffset(n.getLeftChild(), maxheight--, direction);
	    int right=getTotalOffset(n.getRightChild(), maxheight--,
				     direction);
	    int pick=0;
	    if(direction == 0)
	    {
		pick= Math.min(left,right);
	    }
	    else if(direction == 1)
	    {
		pick= Math.max(left,right);
	    }
	    return n.offset + pick;
	    
	}
    }
    
    protected static int treeHeight(JawaaTreeNode root)
    {
	if(root == null)
	    return 0;
	else
	{
	    return 1 + Math.max(treeHeight(root.getLeftChild()),
				treeHeight(root.getRightChild()));
	}
    }

    private static int vertOffset = 0;
    private static int horzOffset = 0;
    //   private Point root = null;
}