// packing gene circles into the wheel center......

       var MAX_VALUE = Number.MAX_VALUE;
	   var MIN_VALUE = -MAX_VALUE;
	   var EPSILON = 1.0/MAX_VALUE	


	//       Calculate  the layout for a group
	//


	   function organizeCircles(childIndices, sizeBy, colorBy, areLeafs) {
			// return a list
			var sites = [];
			hackSiteCount =0;
			var g;
			var circleGroup = new GircleGroup();
			if(childIndices.length == 0) return circleGroup;
			
			if(areLeafs) {
				g = getGroupGeneData(childIndices, sizeBy, colorBy, areLeafs);  // sorted by size
			} else {
				g = getContainerData(childIndices);
			}
			//now calculate placement for all genes. They'll be resized to fit within
			//the wheel center later
			//and then after that all the raphael graphics objects will be created
			var c0 = circleGroup.append(new Gircle({x:-g[0].size,y:0}, g[0].size, g[0].size, g[0].color, g[0].geneIndex)); // largest
			if(g.length == 1) {
				circleGroup.calcBoundingCircle();
				return circleGroup;
			}
			var c1= circleGroup.append(new Gircle({x:g[1].size,y:0}, g[1].size, g[1].size, g[1].color, g[1].geneIndex));  // the pair are centered at origin

			// now process all other nodes.... here......
			sites.push(new Site(c0, c1, null));  // the  bonding parent, auxiliary parent and child.. for the first two there is no child
			sites.push(new Site(c1, c0, null));  // there's two for the first pair - order is reversed
			sites[0].direction = {cx:0, cy:1};
			sites[1].direction = {cx:0, cy:-1};

			var bestSiteIndex;
			for (var j=2; j< g.length; j++) {  // layout all remaining genes
		          var cur = {cx:0, cy:0, radius:g[j].size};   // a surregate
		          var foundIt = false;
		          var i=0;
				  bestSiteIndex = -1;
				  while (i< sites.length) {
		          		 // the best one is the first one that fits
		                 // create a provisional node on this site - testLoc is the one at this site with this radius
						var testLoc = sites[i].accomodate(cur.radius);
						var collided = true;
						
						// do the big compare
						var ncomp =0;
						for (var m=circleGroup.children.length-1; m>=0; m--) {  // test more recent additions first... some speedup (30%?)
							var other = circleGroup.children[m];
							var rad2 = (testLoc.radius + other.radius)*(testLoc.radius + other.radius);  // the distance based on the radii squared
							dst2 = (testLoc.cx-other.cx)*(testLoc.cx-other.cx) + (testLoc.cy-other.cy)*(testLoc.cy-other.cy);
							// its slower to test for x, then y then dist*dist
							// dist btwn the two
							if(dst2 + 0.00001 < rad2) break;  // break if this site can't accomodate this radius
							ncomp++;
						}
						if(ncomp == circleGroup.children.length) {
							// no collisions
							collided = false;
							bestSiteIndex = i;
							break;  // break out of the while loop
						} else {
							sites.splice(i,1);  // just get rid of this one (although smaller genes could fit later on..) - BIG optimization
						}
					}  // end while i	
					if(bestSiteIndex < 0) {
						alert("Error encountered during wheel gene layout");  // this is for debugging... it should never be hit...
						circleGroup.calcBoundingCircle();
						return circleGroup;
					}
					// save it and update the bounding circle list
					circleGroup.append(new Gircle({x:testLoc.cx, y:testLoc.cy}, testLoc.dist, g[j].size, g[j].color, g[j].geneIndex)); 
					// now add some more sites.
					var par1 = sites[bestSiteIndex].n[0];
					var par2 = sites[bestSiteIndex].n[1];
					sites.push(new Site(par1, par2, testLoc));
					sites.push(new Site(par2, par1, testLoc));
					sites.splice(bestSiteIndex,1);   // splice out this site 
			}  // end for (var j=2 ....)
			circleGroup.calcBoundingCircle(); // approximate the center and minimum bounding radius
			return circleGroup;
		}  // end of organizeCircles


// 
// constructors
//			
			
        function Gircle(p, dist, r, color, geneIndex) {  // a circle by any other name is just a circle the same
            this.cx = p.x;  // a point
			this.cy = p.y;
            this.radius = r;
            this.color = color;
			this.geneIndex = geneIndex;
			this.dist = dist;

			this.getBBox = function() {
				var x = this.cx-this.radius;
				var width = this.radius*2;
				var y = this.cy-this.radius;
				var height =this.radius*2;
				return {x:x, y:y, width:width, height:height, cx:x+width/2, cy:y+height/2}
			}
			this.getCenter = function() {
				return {cx:this.cx, cy:this.cy}
			}
			this.getRadius = function() {
				return this.radius;
			}
			this.getDistSqFromOrigin = function(xo, yo) {
				var x = (this.cx < 0)? this.cx-this.radius: this.cx+this.radius;
				var y = (this.cy < 0)? this.cy-this.radius: this.cy+this.radius;
				return (x-xo)*(x-xo) + (y-yo)*(y-yo);
			}
			this.calcDistance = function() {
				this.dist = Math.sqrt(this.cx*this.cx + this.cy*this.cy);  // distance from origin
			}
        }

        function GircleGroup() {
			this.children = [];
			this.cx = 0;
			this.cy = 0;
			this.radius = 0;
			this.scale = 1;
			this.bc = {cx:null, cy:null, radius:null};
			
			var numBuckets = 90;
			this.boundCircle = new BoundingCircle(numBuckets);  // performance isn't really dependent on numBuckets
			
			this.append = function(o) {
				this.children.push(o);
				this.boundCircle.store(o, o.dist+o.radius);
				return this.children[this.children.length-1];
			};
			
			this.getRadius = function() {
				return this.bc.radius;
			};
			
			this.calcBoundingCircle = function() {
				if(this.children.length <2) {  // special treatment if there's only one gene
					this.bc = {cx:this.children[0].cx, cy:this.children[0].cy, radius:this.children[0].radius};
				} else {
					this.bc = this.boundCircle.getBoundingCircle();
				}
				this.cx = this.bc.cx;
				this.cy = this.bc.cy;
				this.radius = this.bc.radius;
			};
			
			this.getBBox = function() {
				var minx = this.cx - this.radius;
				var maxx = this.cx + this.radius;
				var miny = this.cy - this.radius;
				var maxy = this.cy + this.radius;
				return {x:minx, y:miny, width:maxx-minx, height:maxy-miny, 
					    cx:(minx+maxx)/2, cy:(miny+maxy)/2};
			};
			
			this.setCenter = function(x,y) {
				this.cx = x;
				this.cy = y;
				var curCenter = this.getCenter();
				for (var i=0; i<this.children.length; i++) {
					this.children[i].cx = this.cx-curCenter.cx;
					this.children[i].cy = this.cy-curCenter.cy;
				}
			};
			
			this.getCenter = function() {
				return this.bc;
			};
			
			this.scale = function(scale) {  // scales on center
				var bb = this.getBBox();
				var center = {cx:bb.cx, cy:bb.cy};
				for(var i=0; i<this.children.length; i++) {
					var child = this.children[i];
					var cxNorm = (child.cx-bb.x)/bb.width;	
					child.cx = bb.width*scale*cxNorm - bb.width*scale/2;
					var cyNorm = (child.cy-bb.y)/bb.height;
					child.cy = bb.height*scale*cyNorm - bb.height*scale/2;
					child.radius = child.radius*scale;
				}
				this.bc.cx = 0;  // now everything is centered at origin and scaled to fit
				this.bc.cy = 0;
				this.radius = bb.width*scale;
			};
		}
		
		
        function LineSeg(p1, p2) {
            this.p1 = p1;
			this.p2 = p2;
			this.pvec1 = {x:null, y:null};
			this.pvec2 = {x:null, y:null};
			
            this.len = Math.sqrt((p2.cy - p1.cy)*(p2.cy - p1.cy) +
                        (p2.cx-p1.cx)*(p2.cx-p1.cx));
			this.dx = p2.cx - p1.cx;
			this.dy = p2.cy - p1.cy;
			// now determine the point tangent to both circles on this segment
			var cx = p1.cx + (p2.cx-p1.cx)*p1.radius/this.len;
			var cy = p1.cy + (p2.cy-p1.cy)*p1.radius/this.len;
			this.tangentPoint = {cx:cx, cy:cy};
			
			if(Math.abs(p2.cx-p1.cx) < EPSILON) {
				if(p2.cy > p1.cy) {  // vertical line up
					this.slope = MAX_VALUE;
					this.perpendicularSlope = 0;
					this.pvec1 = {cx:1, cy:0};  // these are vectors perpendicular to the segment
					this.pvec2 = {cx:-1, cy:0};
				} else {             // vertical line down
					this.slope = MIN_VALUE
					this.perpendicularSlope = 0;
					this.pvec1 = {cx:-1, cy:0};
					this.pvec2 = {cx:1, cy:0};
				}
			} else {
				this.slope = (p2.cy - p1.cy)/(p2.cx - p1.cx);
				if(Math.abs(this.slope) < EPSILON) {  // horizontal line
					this.perpendicularSlope = MAX_VALUE;
					this.pvec1 = {cx:0, cy:1};
					this.pvec2 = {cx:0, cy:-1};
				} else { // not axis aligned line
					this.perpendicularSlope = -1.0/this.slope;
					this.pvec1 = {cx:1, cy:this.perpendicularSlope};
					this.pvec2 = {cx:-1, cy:-this.perpendicularSlope};
				}
			}
			
			this.normalize = function() {
				// normalize them for use with site selection ... not sure this is needed...
				var d = Math.sqrt(this.pvec1.cx*this.pvec1.cx+this.pvec1.cy*this.pvec1.cy);
				this.pvec1.cx = this.pvec1.cx/d;
				this.pvec1.cy = this.pvec1.cy/d;
				d = Math.sqrt(this.pvec2.cx*this.pvec2.cx+this.pvec2.cy*this.pvec2.cy);
				this.pvec2.cx = this.pvec2.cx/d;
				this.pvec2.cy = this.pvec2.cy/d;
			}
			
			this.intersect = function(seg2) {
				// find the intersection point between two line segments
				return lineSegmentIntersection(this.p1,this.p2, seg2.p1, seg2.p2);
			}
        }
		function circleIntersect(a,b, d) {  // two possible solutions
			var d2 = d*d;
			// k is the area of the triangle formed by the three centerpoints
			var k = 0.25*Math.sqrt(((a.radius+b.radius)*(a.radius+b.radius)-d2)*(d2-(a.radius-b.radius)*(a.radius-b.radius)));
			var rd2 = (a.radius*a.radius-b.radius*b.radius)/d2;
			var xa = 0.5*(b.cx+a.cx) + 0.5*(b.cx-a.cx)*rd2
			var x1 = xa + 2.0*(b.cy-a.cy)*k/d2;
			var x2 = xa - 2.0*(b.cy-a.cy)*k/d2;
			var ya = 0.5*(b.cy+a.cy) + 0.5*(b.cy-a.cy)*rd2; 
			var y1 = ya - 2.0*(b.cx-a.cx)*k/d2;
			var y2 = ya + 2.0*(b.cx-a.cx)*k/d2;
			
			return [{cx:x1, cy:y1}, {cx:x2, cy:y2}];
		}
		
		function Site(primaryParent, secondaryParent, child) {
			this.isActive = true;
			/*
				the primaryParent and child form one site - using the secondaryParent to disambiguate bwtn 2 choice
			*/
			this.radius = 0;
			this.location = new Gircle(0,0,0);
			this.location.fits = false;
			if(!child) { // first two nodes don't have children vector is up and down dx=0;
				this.n = [primaryParent, secondaryParent];
				this.seg = new LineSeg(this.n[0], this.n[1]);  // btwn n0 and n1 centers
				this.direction = this.seg.pvec1;     // is different for the two generators
			} else {
				this.n = [primaryParent, child];
				this.seg = new LineSeg(this.n[0], this.n[1]);  // btwn n0 and n1 centers
				//this.seg.normalize();   // normalize the pvecs
				// compare this with a vector pointing towards the secondary parent from the tangent point
				// the perpVector is in the same quadrant as this vector then its the wrong site
				var secVec = {cx:secondaryParent.cx-this.seg.tangentPoint.cx, cy:secondaryParent.cy-this.seg.tangentPoint.cy}
				var dp1 = dotProduct(secVec, this.seg.pvec1);
				var dp2 = dotProduct(secVec, this.seg.pvec2);
				if(dp1 < dp2) {
					// want the direction away from secondaryParent - since that site is occupied
					this.direction = this.seg.pvec1;
				} else {
					this.direction = this.seg.pvec2;
				}
			}
			this.tangentPoint = this.seg.tangentPoint;
			this.len = this.seg.len;

			
			this.accomodate = function(radius) {
				// find the location on the direction vector starting at the tangentPoint such that
				// the node of given radius will fit.
				var t1 = {cx:this.n[0].cx, cy:this.n[0].cy, radius:(this.n[0].radius+radius)};
				var t2 = {cx:this.n[1].cx, cy:this.n[1].cy, radius:(this.n[1].radius+radius)};
				var pts = circleIntersect(t1, t2, this.len);
				if(dotProduct(pts[0], this.direction) > dotProduct(pts[1], this.direction)) {
					this.location = pts[0];
				} else {
					this.location = pts[1];
				}
				this.location.radius = radius;
				this.location.dist = Math.sqrt(this.location.cx*this.location.cx+this.location.cy*this.location.cy);
				this.location.fits = true;
				return this.location;
			}
		}


		function getContainerData(childIndices) {
			// only sort .. no color or size needed... retain container index
			// geneIndex property contains the container index, color is blank... radius is the key property
			var g = [];
			childIndices.sort(function(a,b) {
				return b.radius - a.radius;
			});
			for (i=0; i< childIndices.length; i++) {
				g.push({geneIndex:i, color:"", size:childIndices[i].radius})
			}
			return g;
		}
		
		function getGroupGeneData(childIndices, sizeBy, colorBy, areLeafs)  {
			var colorCnt = 0;
			var sizeCnt  = 0;
			var workingList = [];
			var g = [];
			var minSize = 0.5;
			switch(pageHeaders["context"].viewState.colorBy) {
				case "diseases count":
					colorCnt =  Math.max(0.5, genes.maxNumMembers["diseases"]);
					break;
				case "processes count":
					colorCnt =  Math.max(0.5, genes.maxNumMembers["processes"]);
					break;
				case "pathways count":
					colorCnt =  Math.max(0.5, genes.maxNumMembers["pathways"]);
					break;
				case "interactions count":
					colorCnt =  Math.max(0.5, genes.maxNumMembers["neighbors"]);
					break;
				default:
					colorCnt = 0.5;  // for none, etc
			}
				
			for (var i=0; i<childIndices.length; i++) {
				var ii = childIndices[i];
				var curG = genes.list[ii];
			
				switch(pageHeaders["context"].viewState.sizeBy) {
					case "diseases count":
						sizeCnt = curG.diseases.length;
						break;
					case "processes count":
						sizeCnt = curG.bioProcesses.length;
						break;
					case "pathways count":
						sizeCnt = curG.pathways.length;
						break;
					case "interactions count":
						sizeCnt = curG.neighborCount;
						break;
					default:  // use this for none
						sizeCnt = minSize;
				}
				var size = Math.max(minSize, Math.sqrt(sizeCnt)/Math.PI) // sqrt to account for area - brings the little genes up  				
				workingList.push({geneIndex:curG.index, color:"#FFFFFF", size:size})	
			}
			workingList.sort(function(a,b) {  // now sort them biggest to smallest.. Biggest get layedout first
				return  b.size - a.size;
			})
			
			// Create an ordered list of objects in decreasing size and add color
			
			for (ii=0; ii<childIndices.length; ii++) {
				
				g.push(workingList[ii]);
				var geneInd = workingList[ii].geneIndex;
				var colorLen = 0;
				if(pageHeaders["context"].viewState.colorBy == "diseases count") colorLen = genes.list[geneInd].diseases.length;
				if(pageHeaders["context"].viewState.colorBy == "processes count") colorLen = genes.list[geneInd].bioProcesses.length;
				if(pageHeaders["context"].viewState.colorBy == "pathways count") colorLen = genes.list[geneInd].pathways.length;	
				if(pageHeaders["context"].viewState.colorBy == "interactions count") colorLen = genes.list[geneInd].neighborCount;
				if(pageHeaders["context"].viewState.colorBy == "none none") colorLen = 0;
				if(pageHeaders["context"].viewState.colorBy == "gene foldChange") {
					g[ii].color = genes.list[geneInd].getExpColor();
				} else {
					var colorFract = (colorCnt ==0)? 0 : colorLen/colorCnt;
					g[ii].color = getColorByFraction(colorFract, false);  // defaults from blue to green
				}
			}
			return g;
		}
		
// misc layout calculation utilities
//

	function dotProduct(a,b) {
		return a.cx*b.cx + a.cy*b.cy;
	}

	function lineSegmentIntersection(a,b,c,d) {
		var Ax = a.cx;
		var Ay = a.cy;
		var Bx = b.cx;
		var By = b.cy;
		var Cx = c.cx;
		var Cy = c.cy;
		var Dx = d.cx;
		var Dy = d.cy;


		 var  distAB, theCos, theSin, newX, ABpos ;

		 //  Fail if either line segment is zero-length.
		 if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return {intersects:false, cx:null, cy:null, radius:0}

		 //  Fail if the segments share an end-point.
		 if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy ||  Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) {
		   		return {intersects:false, cx:null, cy:null, radius:0}
		}

		 //  (1) Translate the system so that point A is on the origin.
		Bx-=Ax;
		By-=Ay;
		Cx-=Ax; 
		Cy-=Ay;
		Dx-=Ax; 
		Dy-=Ay;

		 //  Discover the length of segment A-B.
		 distAB=Math.sqrt(Bx*Bx+By*By);

		 //  (2) Rotate the system so that point B is on the positive X axis.
		 theCos=Bx/distAB;
		 theSin=By/distAB;
		 newX=Cx*theCos+Cy*theSin;
		 Cy  =Cy*theCos-Cx*theSin; 
		 Cx  =newX;
		 newX=Dx*theCos+Dy*theSin;
		 Dy  =Dy*theCos-Dx*theSin; 
		 Dx  =newX;

		 //  Fail if segment C-D doesn't cross line A-B.
		 if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return {intersects:false, cx:null, cy:null, radius:0}

		 //  (3) Discover the position of the intersection point along line A-B.
		 ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);

		 //  Fail if segment C-D crosses line A-B outside of segment A-B.
		 if (ABpos<0. || ABpos>distAB) return {intersects:false, cx:null, cy:null, radius:0}

		 //  (4) Apply the discovered position to line A-B in the original coordinate system.
		 var cx=Ax+ABpos*theCos;
		 var cy=Ay+ABpos*theSin;

		 //  Success.
		 return {intersects:true, cx:cx, cy:cy, radius:0};

	}
	
//	
	// bounding circle calculation - to get the right sizing for center genes
	//    this is an efficient approximation - but not an exact solution
	//		
	function BoundingCircle(nbuckets) {
		this.buckets = [];
		this.centers = [];
		this.circle = {cx:null, cy:null, radius:null};
		this.numBuckets = Math.floor(nbuckets/2)*2; // even
		this.mult = this.numBuckets/(Math.PI*2);  // delta(theta) = 1/this.mult
		this.xmin = null;
		this.xmax = null;
		this.ymin = null;
		this.ymax = null;
		this.numNodes = 0;

		for (var i=0; i<this.numBuckets+1; i++) {
			this.buckets[i] = 0;
		}

		this.getIndex = function(pt) {  // pt = {cx, cy}  - calculate the bucket index
			var theta;
			if(Math.abs(pt.cx)< 0.0001) {
				theta = (pt.cy<0)? Math.PI/2: 3*Math.PI/2;
			} else {
				theta = Math.atan2(-pt.cy, pt.cx);
				if(theta < 0) theta=Math.PI*2+theta;
			}
			return Math.round(theta*this.mult)%this.numBuckets;  // the bucket index based on theta
		};

		this.store = function(pt, value) {    // value is distance from origin + radius
			var indx = this.getIndex(pt);
			this.buckets[indx] = Math.max(this.buckets[indx], value);
			this.numNodes++;
			if(this.numNodes < 10) { // cant get an accurate bounding circle with small numbers ... use extrema
				// this is better than nothing for small gene sets, but not perfect
				// perhaps an exact solution should be used in .getBoundingCircle()
				var i = this.getIndex({cx:pt.cx, cy:pt.cy-pt.radius});   // ymin
				var dist = Math.sqrt(pt.cx*pt.cx+(pt.cy-pt.radius)*(pt.cy-pt.radius));
				this.buckets[i] = Math.max(this.buckets[i], dist);
				i = this.getIndex({cx:pt.cx, cy:pt.cy+pt.radius});   // ymax
				dist = Math.sqrt(pt.cx*pt.cx+(pt.cy+pt.radius)*(pt.cy+pt.radius));
				this.buckets[i] = Math.max(this.buckets[i], dist);
				i = this.getIndex({cx:pt.cx-pt.radius, cy:pt.cy});   // xmin
				dist = Math.sqrt((pt.cx-pt.radius)*(pt.cx-pt.radius)+pt.cy*pt.cy);
				this.buckets[i] = Math.max(this.buckets[i], dist);
				i = this.getIndex({cx:pt.cx+pt.radius, cy:pt.cy});   // xmax
				dist = Math.sqrt((pt.cx+pt.radius)*(pt.cx+pt.radius)+pt.cy*pt.cy);
				this.buckets[i] = Math.max(this.buckets[i], dist);
			}
			return indx;
		};
		this.getBoundingCircle = function() {
			var xmin = 1.0e+10;
			var xmax = -xmin;
			var ymin = xmin;
			var ymax = -ymin;
			for (var i=0; i<this.numBuckets/2; i++) {
				var dist = this.buckets[i] + this.buckets[i+this.numBuckets/2]; // opposing sides 
				var theta = i/this.mult;
				var x0 = this.buckets[i]*Math.cos(theta);
				var y0 = -this.buckets[i]*Math.sin(theta);
				var x1 = this.buckets[i+this.numBuckets/2]*Math.cos(theta+Math.PI);
				var y1 = -this.buckets[i+this.numBuckets/2]*Math.sin(theta+Math.PI);  // > 0
				xmin = Math.min(xmin,x0,x1);
				xmax = Math.max(xmax,x0,x1);
				ymin = Math.min(ymin,y0,y1);
				ymax = Math.max(ymax,y0,y1);
				var cx = (x0+x1)/2;  // center along this diagonal
				var cy = (y0+y1)/2;
				this.centers[i] = {cx:cx, cy:cy,radius:dist/2,p0:{cx:x0,cy:y0}, p1:{cx:x1, cy:y1}};
			}
			this.circle.cx  = (xmax+xmin)/2;  // the center
			this.circle.cy  =  (ymax+ymin)/2;
			this.xmin = this.circle.cx - xmin;  // the bounding rectangular box
			this.xmax = this.circle.cx + xmax;
			this.ymin = this.circle.cy - ymin;
			this.ymax = this.circle.cy + ymax;
			
			// now search each diagonal and find longest radius from this center
			var dmax =0;
			for (i=0;i<this.numBuckets/2; i++) {
				var dx = this.circle.cx-this.centers[i].p0.cx;
				var dy = this.circle.cy-this.centers[i].p0.cy;
				var d1 = Math.sqrt(dx*dx+dy*dy);
				dx = this.circle.cx-this.centers[i].p1.cx;
				dy = this.circle.cy-this.centers[i].p1.cy;
				var d2 = Math.sqrt(dx*dx+dy*dy);
				dmax = Math.max(dmax,d1, d2);
			}
			this.circle.radius = dmax;
			return this.circle;	
		};
	}