package flare.vis.data {
	import flare.vis.events.DataEvent;

	/**
	 * Data structure for managing a collection of visual data objects in a
	 * tree (hierarchy) structure. This class extends the functionality of
	 * the Data class to model a hierarchy. The class can be used as an
	 * alternative to the Data class when the data forms a strict tree, or to
	 * model a spanning tree over a general graph.
	 */
	public class Tree extends Data
	{	
		/**
		 * Sets the root node of this tree. This property can only be set
		 * when the tree does not yet have a root node. */
		public override function set root(n:NodeSprite):void {
			if (_root == null) {
				super.addNode(n); _root = n; _root.parentIndex = -1;
				addDescendants(_root);
			} else {
				throw new ArgumentError("Can't set root unless the tree is empty." +
				"If you want to set an entirely new root, call clear() first.");
			}
		}
		
		/** This property simply points back to this object. */
		public override function get tree():Tree { return this; }
		public override function set tree(t:Tree):void { /* do nothing */ }
		
		// -- Methods ---------------------------------------------------------
		
		/**
		 * Creates and returns a new root NodeSprite for the tree. If the
		 * tree already has a root, this method throws an error.
		 * @return the newly added root
		 */
		public function addRoot():NodeSprite
		{
			if (_root != null) throw new Error(
				"addRoot can only be called on an empty tree!");
			return (_root = super.addNode());
		}
		
		/**
		 * Add a node to the tree. If the child node argument is null,
		 * a new NodeSprite will be created. A new EdgeSprite connecting
		 * the nodes will be created. Returns the new child node.
		 * @param p the parent node
		 * @param c the child node. If null, a new child node is created.
		 * @return the new child node
		 */
		public function addChild(p:NodeSprite, c:NodeSprite=null):NodeSprite
		{			
			if (!_nodes.contains(p)) {
				throw new ArgumentError("Parent node must be in the tree!");
			}
			c = super.addNode(c);
			var e:EdgeSprite = newEdge(p, c, directedEdges, null);
			c.parentIndex = p.addChildEdge(e);
			c.parentEdge = e;
			super.addEdge(e);
			return c;
		}
		
		/**
		 * Adds the given edge as a child edge between a node already
		 * in the tree and another node not yet in the tree.
		 * @param e the edge to add to the tree
		 * @return the newly added edge
		 */
		public function addChildEdge(e:EdgeSprite):EdgeSprite
		{
			var n1:NodeSprite = e.source, b1:Boolean = _nodes.contains(n1);
			var n2:NodeSprite = e.target, b2:Boolean = _nodes.contains(n2);
			
			if (b1 && b2) {
				throw new ArgumentError("One node must not be in the tree");
			}
			if (!(b1 || b2))
				throw new ArgumentError("One node must already be in the tree");
				
			var p:NodeSprite = b1 ? n1 : n2;
			var c:NodeSprite = b1 ? n2 : n1;
			
			c.parentEdge = e;
			c.parentIndex = p.addChildEdge(e);
			
			super.addNode(c);
			return super.addEdge(e);
		}
		
		/**
		 * Registers all tree descendants with this Tree instance. 
		 * @param n a sub-tree root that has already been added to this Tree
		 */
		protected function addDescendants(n:NodeSprite):void
		{
			for (var i:int=0; i<n.childDegree; ++i) {
				var e:EdgeSprite = n.getChildEdge(i);
				var c:NodeSprite = e.other(n);
				c.parentEdge = e;
				c.parentIndex = i;
				super.addNode(c);
				super.addEdge(e);
				addDescendants(c);
			}
		}
		
		/**
		 * Clears the tree, removing all nodes and edges.
		 */
		public override function clear():void
		{
			super.clear(); _root = null;
		}
		
		/**
		 * Removes a node from the tree, removing the entire
		 * subtree rooted at that node.
		 * @param n the node to remove
		 * @return true if the node was successfully removed, false otherwise
		 */
		public override function removeNode(n:NodeSprite):Boolean
		{
			if (n==_root) {
				clear(); return true;
			} else {
				return removeEdge(n.parentEdge);
			}
		}
		
		/**
		 * Removes an edge from tree tree, removing the entire
		 * subtree rooted at the child node adjacent to the edge.
		 * @param e the edge to remove from the tree
		 * @return true if the edge was successfully removed, false otherwise
		 */
		public override function removeEdge(e:EdgeSprite):Boolean
		{
			if (e==null || !_edges.contains(e)) return false;
			
			// disconnect tree
			var c:NodeSprite = (e.target.parentNode==e.source ? e.target : e.source);
			var p:NodeSprite = c.parentNode;
			var i:int = c.parentIndex;
			p.removeChildEdge(e);
			
			// walk disconnected segment to fire updates
			c.visitTreeDepthFirst(function(n:NodeSprite):void {
				_edges.remove(n.parentEdge);
				_nodes.remove(n);
			});
			_edges.remove(e);
			
			// update parent index values
			for (; i<p.childDegree; ++i) {
				p.getChildNode(i).parentIndex = i;
			}
			return true;	
		}
		
		/** @private */
		protected override function onRemoveNode(evt:DataEvent):void
		{
			fireEvent(evt);
		}
		
		/** @private */
		protected override function onRemoveEdge(evt:DataEvent):void
		{
			fireEvent(evt);
		}

		// --------------------------------------------------------------------
		
		/**
		 * Counts the number of leaf nodes in the tree.
		 * @return the number of leaf nodes
		 */
		public function countLeaves():int
		{
			var leaves:int = 0;
			for each (var ns:NodeSprite in _nodes.list) {
				if (ns.childDegree == 0) ++leaves;
			}
			return leaves;
		}

		// --------------------------------------------------------------------

		/**
		 * Continuously swaps the given node with its parent node
		 * until it is the root.
		 * <p>
		 * <strong>WARNING:</strong> this method causes connecting edges to be
		 * reconfigured. If this tree is a spanning tree, this can cause havoc.
		 * </p>
		 * @param n the node to swap with its parent until it becomes the root
		 */
		public function swapToRoot(n:NodeSprite):void
		{
			while (n.parent != null) {
				swapWithParent(n);
			}
		}

		/**
		 * Swaps the given node with its parent node.
		 * <p>
		 * <strong>WARNING:</strong> this method causes connecting edges to be
		 * reconfigured. If this tree is a spanning tree, this can cause havoc.
		 * </p>
		 * @param n the node to swap with its parent
		 */
		public function swapWithParent(n:NodeSprite):void
		{
			var p:NodeSprite = n.parentNode, gp:NodeSprite;
			var e:EdgeSprite, ge:EdgeSprite, idx:int;
			if (p==null) return;
			
			gp = p.parentNode;
			ge = p.parentEdge;
			idx = p.parentIndex;
			
			// swap parent edge
			e = n.parentEdge;
			p.removeChild(n);
			p.parentEdge = e;
			p.parentIndex = n.addChildEdge(e);
			
			// connect to grandparents
			if (gp==null) {
				n.parentIndex = -1;
				n.parentEdge = null;
			} else {
				if (ge.source == gp) {
					ge.target = n;
				} else {
					ge.source = n;
				}
				n.parentIndex = idx;
				n.parentEdge = ge;
			}
		}

	} // end of class Tree
}