package bhuffake.plankton;
import java.awt.*;
import java.lang.Math;
import java.util.Random;

/**************************************************************************
* File: Format.java	Class: Format
* Goal: To arrange the nodes in a more meaningful fashion
* 	arrages the nodes of the passed Display using a depth 
*	first algorthim.
*
* Written: Bradley Huffaker             (12/20/97)
*
* Modified: Jaeyeon Jung		(2/13/98)
* To arrange nodes in a World Map 
*
* For:Cooperative Association for Internet Data Analysis
***************************************************************************
***************************************************************************
By accessing this software, FORMAT, you are duly informed of and 
agree to be bound by the conditions described below in this notice:
 
This software product, FORMAT, is developed by Bradley Huffaker, and
Jaeyeon Jung copyrighted(C) 1998 by the University of California, 
San Diego (UCSD), with all rights reserved.  UCSD administers the NLANR 
Cache grants, NCR-9796082 and NCR-9616602, under which most of this code 
was developed.
 
There is no charge for FORMAT software. You can redistribute it and/or
modify it under the terms of the GNU General Public License, v. 2 dated
June 1991 which is incorporated by reference herein.  FORMAT is
distributed WITHOUT ANY WARRANTY, IMPLIED OR EXPRESS, OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE or that the use of
it will not infringe on any third party's intellectual property
rights.
 
You should have received a copy of the GNU GPL along with the FORMAT
program.  Copies can also be obtained from
http://www.gnu.org/copyleft/gpl.html or by writing to
 
                        University of California, San Diego
                        SDSC/CAIDA/NLANR
                        9500 Gilman Dr., MS-0505
                        La Jolla, CA 92093 - 0505  USA
 
  Or contact INFO@NLANR.NET
**************************************************************************/    
public class Format extends Thread
{
	// The list of DisplayObjects to format
	Display display;
	int oldMode;
		
	// The size of the current node
	int size;
	// Used for random effect
	Random random = new Random();

	// The differt ways to format
	static final int FORCE = 0;
	static final int ROOT = 1;
	static final int GEO = 2;

	protected int mode = FORCE;
	protected DList dlist; 

	// The default size of the Root nodes
	final int ROOT_SIZE = 8;

	// This is used between Animator and Format
	// If it is null it is ingnored
	FormatInterface parent;

	public Format(Display display_input)
	{
		display = display_input;
		dlist = display.getList();
	}

	public void setMode(int input) { mode = input; }
	public int getMode() {return mode; }

	public void setParent(FormatInterface input)
	{
		parent = input;
	}

	public void printMessage(String msg)
	{
		if (parent == null)
			display.printMessage(msg);
		else
			parent.printMessage(msg);
	}
	
	public void run()
	{
		oldMode = display.getMode();
		display.setMode(Display.FORMAT);
		printMessage("Formatting");
		switch (mode)
		{
/*
			case FORCE:
				ProcessForce();
				break;
*/
			case ROOT:
				ProcessRoot();
				break;
			case GEO:
				ProcessGeo();
				break;
			default:
				System.err.println("Unknow type type of format");
				break;
		}
		printMessage("Finished");
		if (mode == ROOT)
			display.ChangeRootXY();
		if (parent != null)
			parent.finished();
		else 
			display.repaintNodes();
		//display.setMode(oldMode);
		display.setMode(display.MOVE);
	}
	
/*********************** Root Methods ***********************************/
	
	// The basic limiting angel
	final double ANGLE_SCOPE = Math.PI;

	protected void ProcessRoot()
	{
		Dimension dim = display.displaySize();
		int center_x = dim.width/2;
		int center_y = dim.height/2;
		DList queue = SetUpRoot();
		DList ordered = new DList();
	
		if (queue == null)
			return;

		queue.reset();
		while(!queue.end()) {
			DisplayObject object = queue.next();
			if(((Node)object).getRank()==1)
				ordered.enqueue(object);
		}	
		while (!queue.empty())
		{
			double angle_scope = ANGLE_SCOPE;
			Node top = (Node) queue.pop();
			int[] xy = top.getXY();
			int x = xy[0];
			int y = xy[1];
			int rank = top.getRank();
				
			int delta_x = x-center_x;
			int delta_y = y-center_y;
			double base_angle;
			if (delta_x == 0 && delta_y == 0)
			{
				base_angle = 1.5*Math.PI;
				angle_scope = 2*Math.PI;
			}	
			else if (delta_x == 0)
				base_angle = 0;
			else if (delta_y == 0)
				if (delta_x > 0)
			 		base_angle = .5*Math.PI;	
				else
			 		base_angle = 1.5*Math.PI;	
			else
				base_angle = Math.atan ((delta_x)
					/(double)(delta_y));
			if (delta_y < 0)
				base_angle += Math.PI;
			int size = top.getSize();
			Node[] neighbors = top.getNeighbors();
			int num_neighbors = neighbors.length;

			// This should remove any nodes which have already
			// had their xy set
			
			// This removes any node from the end of the
			// list which are already set.  this is so 
			// the last node is unset.
			while (num_neighbors > 0 
				&& neighbors[num_neighbors-1].isSetXY()) 
			{
				num_neighbors--;
			}
			// This removes the those neighbors that 
			// have already be set.
			int where = 0;
			while (where < num_neighbors)
			{
				if (neighbors[where].isSetXY())
				{
				  num_neighbors--;
				  neighbors[where] = neighbors[num_neighbors];
				}
				else
					where++;
			}	
/*
			if (num_neighbors%2 == 0)
				base_angle = base_angle 
				  + (angle_scope/2*num_neighbors);
*/
			// The array of children for the current node
			// this array will be given to top at the end 
			// of the for loop
			Node[] children = new Node[num_neighbors];
				
			// Here we set all of the nodes neighbors
			// which have not yet set and added them
			// to the bottom of the queue.  so that 
			// the new nodes neighbors can be set.
			for (int index=0;index< num_neighbors; index++)
			{
			    Node node = neighbors[index];
			    children[index] = node;
			    if (!node.isSetXY())
			    {
			      double length=size*2 + 
				2*node.countLink()+num_neighbors;
			      double angle = 0;
				
			      // This will have the angle swap be between 
			      // the potive and negative sides of the base
			      // angle
			      if (index%2 == 0)
				angle = base_angle 
				  + (angle_scope*(index/2)/num_neighbors);
			      else
				angle = base_angle 
				  - (angle_scope*((index+1)/2)/num_neighbors);

			      node.setRootXY(x+(int)(length*Math.sin(angle)),
			 		y+(int)(length*Math.cos(angle)));
			      node.setToRootXY();
			      node.setNameLocation(angle);
			      node.setRank(rank+1);
			 	
			      if (size > 3)
				node.setSize(size-1);
			      else 
			        node.setSize(2);
			      if (node.countLink() > 1)
			        queue.enqueue(node);

			      ordered.enqueue((DisplayObject)node);
			    }
			}
			top.setChildren(children);
		}
		display.setOrderedList(ordered);
	}

	protected DList SetUpRoot()
	{
		Dimension dim = display.displaySize();
	
		DList queue = new DList();

		DList mylist = dlist.DList();
		DList roots = new DList();

		// This is a special case if there are not roots.
		Node most= null;
		int most_size = 0;
		int most_root = 0;
		int most_count = 0;

		mylist.reset();
		while (!mylist.end())
		{
		    DisplayObject object = mylist.next();
		    if (object instanceof Node)
  		    {
			Node node = (Node) object;
			int count = node.countLink();
			node.unSetXY();

			if (node.isRoot())
			{
				if (count > most_root)
					most_root = count;
				int size = node.getSize();
				if (size > most_size)
					most_size = size;
				roots.push(node);
			}
			if (count > most_count)
			{
				most = node;
				most_count = count;
			}
		    }
		}
		if (roots.count() <= 0)
			if (most == null)
				return null;
			else
				roots.push(most);	
			
		if (roots.count() == 1)
		{
			Node root = (Node) roots.pop();
			root.setSize(ROOT_SIZE);
			root.setRootXY(dim.width/2,dim.height/2);
			root.setToRootXY();
			root.setRank(1);
			queue.enqueue(root);
		}
		else
		{
			int count = roots.count();
			int length = (int)(
				(count*most_size)+most_count/2);
			int shortest = dim.width/3;
			if (dim.height/3 < shortest)
				shortest = dim.height/3;
			if (length > shortest)
				length = shortest;
			for (int index=1; index <= count; index++)
			{
				Node root = (Node) roots.pop();
				double angle = (index*2*Math.PI)/count;
			 	int my_len = length 
					+ root.getNeighbors().length;
				int width = (int)(my_len* Math.cos(angle));
				int height = (int)(my_len* Math.sin(angle));
				root.setSize(ROOT_SIZE);
				root.setRootXY(dim.width/2+ width, dim.height/2+height);
				root.setToRootXY();
				root.setNameLocation(angle);
				root.setRank(1);
				queue.enqueue(root);
			}
		}
		return queue;
	}

/*********************** Geo Methods ***********************************/
	
	protected void ProcessGeo()
	{
		Dimension dim = display.displaySize();
		DList queue = SetUpGeo();
		DList mylist = dlist.DList();
		DList ordered = new DList();
		if (queue == null)
			return;

		queue.reset();
		while(!queue.end()) {
			DisplayObject object = queue.next();
			if (((Node)object).getRank()==1)
				ordered.enqueue(object);
		}

		while (!queue.empty())
		{
			Node top = (Node) queue.pop();
			int size = top.getSize();
			int rank = top.getRank();
			Node[] neighbors = top.getNeighbors();
			int num_neighbors = neighbors.length;

			// This removes any at the end 
			while (num_neighbors > 0 
				&& neighbors[num_neighbors-1].isSetXY()) 
				num_neighbors--;
			// This removes the rest
			int where = 0;
			while (where < num_neighbors)
			{
				if (neighbors[where].isSetXY())
				{
				  num_neighbors--;
				  neighbors[where] = neighbors[num_neighbors];
				}
				else
					where++;
			}	
	
			Node[] children = new Node[num_neighbors];
	
			for (int index=0;index<num_neighbors;index++)
			{
			    Node node = neighbors[index];
			    children[index] = node;
			    if (!node.isSetXY())
			    {
				DisplayObject object  = (DisplayObject)node;
			  	double lat = object.getLatitude();
			  	double lon = object.getLongitude(); 
			  	int to_map[] = display.ToMap(lat,lon);
				node.setGeoXY(to_map[0],to_map[1]); 
				node.setToGeoXY();
			 	node.setNameLocation(1.5*Math.PI);
				node.setRank(rank+1);

			      	if (size > 3)
					node.setSize(size-1);
			      	else 
			        	node.setSize(1);

			      	if (node.countLink() > 1) 
			        	queue.enqueue(node);

				ordered.enqueue((DisplayObject)node);
			    }
			}
			top.setChildren(children);
		}

		mylist.reset();
		while(!mylist.end())
		{
			DisplayObject object = mylist.next();
			object.setGeo(true);
		}
		mylist.reset();
		while(!mylist.end())
		{
			DisplayObject object = mylist.next();
			double lat = object.getLatitude();
                        double lon = object.getLongitude();
                        if (object instanceof Node && (lat > 90 || lat < -90 || lon > 180 || lon < -180))
                         {
				object.setGeo(false);
				DList links = ((Node)object).getLink();
				links.reset();
				while(!links.end())
				{
					object = links.next();
					object.setGeo(false);
				}
			}
		}
		display.setOrderedList(ordered);
	}

	protected DList SetUpGeo()
	{
		Dimension dim = display.displaySize();
	
		DList queue = new DList();

		DList mylist = dlist.DList();
		DList roots = new DList();

		// This is a special case if there are not roots.
		Node most= null;
		int most_size = 0;
		int most_root = 0;
		int most_count = 0;

		mylist.reset();
		while (!mylist.end())
		{
		    DisplayObject object = mylist.next();
		    object.setGeo(false);
		    if (object instanceof Node)
  		    {
			Node node = (Node) object;
			int count = node.countLink();
			node.unSetXY();

			if (node.isRoot())
			{
				if (count > most_root)
					most_root = count;
				int size = node.getSize();
				if (size > most_size)
					most_size = size;
				roots.push(node);
			}
			if (count > most_count)
			{
				most = node;
				most_count = count;
			}
		    }
		}

		if (roots.count() <= 0)
			if (most == null)
				return null;
			else
				roots.push(most);	
			
		if (roots.count() == 1)
		{
			Node root = (Node) roots.pop();
			root.setSize(ROOT_SIZE);
			DisplayObject obj = (DisplayObject)root;
			double lat = obj.getLatitude();
			double lon = obj.getLongitude(); 
			int to_map[] = display.ToMap(lat,lon) ;
			root.setGeoXY(to_map[0],to_map[1]);
			root.setToGeoXY();
			root.setRank(1);

			queue.enqueue(root);
		}
		else
		{
			int count = roots.count();
			for (int index=1; index <= count; index++)
			{
				Node root = (Node) roots.pop();
				root.setSize(ROOT_SIZE);
				DisplayObject obj = (DisplayObject)root;
				double lat = obj.getLatitude();
				double lon = obj.getLongitude(); 
				int to_map[] = display.ToMap(lat,lon);
				root.setGeoXY(to_map[0],to_map[1]);
				root.setToGeoXY();
				root.setNameLocation(1.5*Math.PI);
				root.setRank(1);
				queue.enqueue(root);
			}
		}
		return queue;
	}

/*************************************************************************/

/*********************** Force Methods **********************************/
	
/*
	// The number of cycles to go throught
	int num_cycles = 1;
	int num_steps  = 1;

	// Node Wight
	double nodeWieght = 10;
	double neighborWieght = 1;

	// An array of all the nodes
	Node[] nodes;
	// An array of all the link pairs
	Node[][] links;

	protected void ProcessForce()
	{
		SetUpForce();
		if (nodes.length > 0)
			size = 4*nodes[0].getSize();
		int cycles = num_cycles * num_steps; 
		while (cycles > 0)
		{
			if (cycles %num_steps == 0)
				printMessage("Number of steps left " 
					+ cycles);
			for (int index=nodes.length-1;index >= 0; index--)
			{	
				Node node = nodes[index];
				// push works on both nodes so it only needs to						// be called once for each par
				for (int i=index-1; i >=0;i--)
					node.push(nodes[i]);
			}
			for (int index=links.length-1;index >=0;index--)
				links[index][0].pull(links[index][1]);
			for (int index=nodes.length-1;index >= 0; index--)
				nodes[index].change();
			cycles--;
		}
	}

	protected void SetUpForce()
	{
		DList mylist = dlist.DList();
		mylist.reset();
		int num_nodes = 0;
		int num_links = 0;
		while(!mylist.end())
			if (mylist.next() instanceof Node)
				num_nodes++;
			else 
				num_links++;
		nodes = new Node[num_nodes];
		links = new Node[num_links][2];
		mylist.reset();
		num_nodes = 0;
		num_links = 0;
		while(!mylist.end())
		{
			DisplayObject object = mylist.next();
			if (object instanceof Node)
			{
				nodes[num_nodes] = (Node)object;
				num_nodes++;
			}
			else if (object instanceof Link)
			{
				links[num_links][0] = (Node) ((Link)object).getParent(); 
				links[num_links][1] = (Node) ((Link)object).getChild();
				num_links++;
			}
		}
	}
*/
}