%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 1996-2010. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%------------------------------------------------------------
%%
%% Places a Digraph in a tree-like manner. The vertices in the digraph
%% is updated with x and y positions. The operation is not atomic. The
%% digraph may be cyclic but edges must then have been labeled primary
%% or secondary and the set of primary links must make up a non-cyclic
%% graph (a tree).
%%
%%
%%		IMPLEMENTATION DETAIL
%%		---------------------
%%
%%		The placement algorithm is straightforward, place the
%%		nodes in the vertical plane (y-plane) and then place
%%		nodes in the horisontal plane (x-plane).
%%
%%		First all nodes are placed in the y (vertical) plane
%%		by a standard traversing of the tree. We then place
%%		the tree in the x (horisontal) plane. Each node is
%%		placed in the middle of its children as far to the
%%		left as possible, preferably at the left margin. Two
%%		things can make a node not be placed at the left
%%		margin and that is the case when a previous node has
%%		been placed at the same vertical level as the node we
%%		are trying to place (thus forcing a placement further
%%		to the right), and the second case is when the middle
%%		of the subtree of the node is not at the left margin
%%		(which it only is when the subtree is empty). The
%%		algorithm obviously depends on keeping track of the
%%		rightmost positions at all depths, and this
%%		information is also usefull when calculating the width
%%		of the tree.
%%
%%
%%
%%------------------------------------------------------------



-module(appmon_place).

-export([place/2]).

-include("appmon_dg.hrl").


-import(lists, [foreach/2, foldl/3]).


place(DG, Root) ->
    case appmon_dg:get(data, DG, Root) of
	false -> [0];
	_Other -> 
	    placey(DG, Root, 1),
	    placex(DG, Root, [])
    end.


%%------------------------------------------------------------
%%
%%
%%	Placing a graph in y plane
%%	--------------------------
%%
%%	Place nodes in the graph in the y plane rather stupidly
%%

placey(DG, V, Y) ->
    appmon_dg:set(y, DG, V, Y),
    Y1 = Y+1,
    foreach(fun(C) -> placey(DG, C, Y1) end, appmon_dg:get(out, DG, V)).




%%------------------------------------------------------------
%%
%%
%%	Place a tree in the x plane
%%	---------------------------	
%%
%%	Place nodes in the tree in the x plane. The goal of the x
%%	placement is to place all nodes as far to the left as possible
%%	while maintaining a nice tree shape.
%%
%%	To place a node we must first place its children, the
%%	intention is to place the current node in the middle and above
%%	its children. The calc_mid function will place the node in the
%%	middle of its children. If the node should be placed further
%%	to the right than the middle of its children, then its
%%	children are moved DeltaX positions to be balanced under the
%%	node.  Thus at the end the node and its children form a nice
%%	looking tree.
%%
%%	The function also maintains the 'rightmost x on each level'
%%	list LastX by putting its own position on top of the list
%%
%%

placex(DG, V, LastX) ->
    Ch = appmon_dg:get(out, DG, V),
    ChLX = foldl(fun(C, Accu) -> placex(DG, C, Accu) end,
		 tll(LastX),
		 Ch),
    
    Width	= appmon_dg:get(w, DG, V),
    MyX		= calc_mid(DG, Width, Ch),
    DeltaX	= calc_delta(MyX, hdd(LastX)+spacex()),

    appmon_dg:set(x, DG, V, MyX),
    move(DG, V, [MyX+Width | ChLX], DeltaX).


%%------------------------------------------------------------
%%
%%
%%	Move a subtree DeltaX positions to the right
%%	--------------------------------------------
%%
%%	Used when moving children to balance under an already placed
%%	parent. Note that the correct LastX depends on the ordering of
%%	the children which must be the same as when the children were
%%	first placed. It must be ensured that hdd(NewLastX) is the
%%	same as hdd(NewLastX)+DeltaX. If the order of children is
%%	preserved then so is hdd(LastX). Another solution would be to
%%	set hdd(LastX) from the parent
%%
%%	Note the two base clauses, one for the no-children case and
%%	one optimisation clause (unneccessary perhaps) for DeltaX==0
%%

move(_DG, _L, LastX, 0) -> LastX;
move(DG, V, LastX, DeltaX) -> move2(DG, V, LastX, DeltaX).

move2(DG, V, LastX, DeltaX) ->
    NewX = appmon_dg:get(x, DG, V)+DeltaX,
    appmon_dg:set(x, DG, V, NewX),
    ChLX = foldl(fun(C, LX) -> move2(DG, C, LX, DeltaX) end,
		 tll(LastX), 
		 appmon_dg:get(out, DG, V)),
    [erlang:max(NewX+appmon_dg:get(w, DG, V), hdd(LastX)) | ChLX].


%%------------------------------------------------------------
%%
%%
%%	Calculate the middle position of the children
%%	---------------------------------------------
%%
%%	Calculates the mid x position for a list of children. This
%%	position is later compared to the position dictated by LastX
%%	in calc_delta.

calc_mid(_DG, _Width, []) -> 0;
calc_mid(DG, Width, ChList) ->
    LeftMostX = appmon_dg:get(x, DG, hd(ChList)),
    Z2 = lists:last(ChList),
    RightMostX = appmon_dg:get(x, DG, Z2)+appmon_dg:get(w, DG, Z2),
    trunc((LeftMostX+RightMostX)/2)-trunc(Width/2).

calc_delta(Mid, Right) ->    
    if  Right>Mid	-> Right-Mid;
	true		-> 0
    end.



%% Special head and tail
%% Handles empty list in a non-standard way
tll([]) -> [];
tll([_|T]) -> T.
hdd([]) -> 0;
hdd([H|_]) -> H.

spacex() -> 20.					% Should be macro??