package flare.vis.operator.layout {
	import flare.util.Orientation;
	import flare.util.Property;
	import flare.util.Vectors;
	import flare.vis.data.EdgeSprite;
	import flare.vis.data.NodeSprite;

	/**
	 * Layout that places items in a dendrogram for displaying the results of
	 * hierarchical clustering. This class computes a dendrogram layout and sets
	 * edge control points to create "U" shaped dendrogram branches. It is
	 * common, though by no means required, to hide the node instances in a
	 * dendrogram display.
	 * 
	 * <p>To determine the height of dendrogram branches, a distance property
	 * can be provided. The values of this property will directly determine
	 * node heights by laying out the depth axis using a linear scale of
	 * distance values. The distance property should be set for all non-leaf
	 * nodes in the tree. Typically, leaf nodes have a distance of zero,
	 * resulting in an aligned list of leaf nodes.</p>
	 */
	public class DendrogramLayout extends Layout
	{
		// TODO: support axes, too
		
		private var _orient:String = Orientation.TOP_TO_BOTTOM; // the orientation of the tree
		private var _dp:Property;
		
		private var _leafCount:int;
		private var _leafIndex:int = 0;
		private var _maxDist:Number;
		private var _b1:Number;
		private var _db:Number;
		private var _d1:Number;
		private var _dd:Number;
		
		/** Data property to use as the distance field for
		 *  determining the height values of dendrogram branches. */
		public function get distanceProperty():String { return _dp.name; }
		public function set distanceProperty(dp:String):void {
			_dp = Property.$(dp);
		}
		
		/** The orientation of the dendrogram */
		public function get orientation():String { return _orient; }
		public function set orientation(o:String):void { _orient = o; }
		
		/**
		 * Creates a new DendrogramLayout.
		 * @param distField data property to use as the distance field for
		 *  determining the height values of dendrogram branches
		 * @param orientation the orientation of the dendrogram
		 */
		public function DendrogramLayout(distField:String=null,
			orientation:String=Orientation.TOP_TO_BOTTOM)
		{
			_dp = distField==null ? null : Property.$(distField);
			_orient = orientation;
		}
		
		/** @inheritDoc */
		protected override function layout():void
		{
			init();
			doLayout(visualization.tree.root);
		}
		
		/**
		 * Initialize the layout.
		 */
		private function init():void
		{
			var root:NodeSprite = visualization.tree.root;
			_leafCount = visualization.tree.countLeaves();
			_leafIndex = 0;
			_maxDist = _dp!=null ? _dp.getValue(root) : computeHeights(root);
			
			switch (_orient) {
				case Orientation.TOP_TO_BOTTOM:
					_b1 = layoutBounds.left;
					_db = layoutBounds.width;
					_d1 = layoutBounds.bottom;
					_dd = -layoutBounds.height;
					break;
				case Orientation.BOTTOM_TO_TOP:
					_b1 = layoutBounds.left;
					_db = layoutBounds.width;
					_d1 = layoutBounds.top;
					_dd = layoutBounds.height;
					break;
				case Orientation.LEFT_TO_RIGHT:
					_b1 = layoutBounds.top;
					_db = layoutBounds.height;
					_d1 = layoutBounds.right;
					_dd = -layoutBounds.width;
					break;
				case Orientation.RIGHT_TO_LEFT:
					_b1 = layoutBounds.top;
					_db = layoutBounds.height;
					_d1 = layoutBounds.left;
					_dd = layoutBounds.width;
					break;
			}
		}
		
		private function computeHeights(n:NodeSprite):int
		{
			n.u = 0;
			for (var i:int=0; i<n.childDegree; ++i) {
				n.u = Math.max(n.u, 1 + computeHeights(n.getChildNode(i)));
			}
			return n.u;
		}
		
		private function doLayout(n:NodeSprite):Number
		{
			var d:Number = _dp!=null ? _dp.getValue(n) : n.u;
			d = _d1 + _dd * (d / _maxDist);
			
			if (n.childDegree > 0) {
				var b:Number = 0, bc:Number;
				for (var i:int=0; i<n.childDegree; ++i) {
					var c:NodeSprite = n.getChildNode(i);
					b += (bc=doLayout(c));
					layoutEdge(c.parentEdge, bc, d);
				}
				b /= n.childDegree;
			} else {
				var step:Number = 1.0 / _leafCount;
				b = _b1 + _db * step * (0.5 + _leafIndex++);
			}
			layoutNode(n, b, d);
			return b;
		}
		
		private function layoutNode(n:NodeSprite, b:Number, d:Number):void
		{
			var o:Object = _t.$(n);
			if (Orientation.isVertical(_orient)) {
				o.x = b; o.y = d;
			} else {
				o.x = d; o.y = b;
			}
		}
		
		private function layoutEdge(e:EdgeSprite, b:Number, d:Number):void
		{
			var vert:Boolean = Orientation.isVertical(_orient);
			if (e.points == null) {
				var s:NodeSprite = e.source;
				var t:NodeSprite = e.target;
				e.points = new Vector.<Object>();
				e.points.push((s.x+t.x)/2); e.points.push((s.y+t.y)/2);
			}
			_dummy.x = b; b = _dummy.x;
			_dummy.x = d; d = _dummy.x;
			_t.$(e).points = vert ? Vectors.copyFromArray([b, d]) : Vectors.copyFromArray([d, b]);
		}
		
	} // end of class DendrogramLayout
}