1 /**
  2  * Constructs a new, empty tree layout. Layouts are not typically constructed
  3  * directly; instead, they are added to an existing panel via
  4  * {@link pv.Mark#add}.
  5  *
  6  * @class Implements a node-link tree diagram using the Reingold-Tilford "tidy"
  7  * tree layout algorithm. The specific algorithm used by this layout is based on
  8  * <a href="http://citeseer.ist.psu.edu/buchheim02improving.html">"Improving
  9  * Walker's Algorithm to Run in Linear Time"</A> by C. Buchheim, M. Jünger
 10  * & S. Leipert, Graph Drawing 2002. This layout supports both cartesian and
 11  * radial orientations orientations for node-link diagrams.
 12  *
 13  * <p>The tree layout supports a "group" property, which if true causes siblings
 14  * to be positioned closer together than unrelated nodes at the same depth. The
 15  * layout can be configured using the <tt>depth</tt> and <tt>breadth</tt>
 16  * properties, which control the increments in pixel space between nodes in both
 17  * dimensions, similar to the indent layout.
 18  *
 19  * <p>For more details on how to use this layout, see
 20  * {@link pv.Layout.Hierarchy}.
 21  *
 22  * @extends pv.Layout.Hierarchy
 23  */
 24 pv.Layout.Tree = function() {
 25   pv.Layout.Hierarchy.call(this);
 26 };
 27 
 28 pv.Layout.Tree.prototype = pv.extend(pv.Layout.Hierarchy)
 29     .property("group", Number)
 30     .property("breadth", Number)
 31     .property("depth", Number)
 32     .property("orient", String);
 33 
 34 /**
 35  * Default properties for tree layouts. The default orientation is "top", the
 36  * default group parameter is 1, and the default breadth and depth offsets are
 37  * 15 and 60 respectively.
 38  *
 39  * @type pv.Layout.Tree
 40  */
 41 pv.Layout.Tree.prototype.defaults = new pv.Layout.Tree()
 42     .extend(pv.Layout.Hierarchy.prototype.defaults)
 43     .group(1)
 44     .breadth(15)
 45     .depth(60)
 46     .orient("top");
 47 
 48 /** @private */
 49 pv.Layout.Tree.prototype.buildImplied = function(s) {
 50   if (pv.Layout.Hierarchy.prototype.buildImplied.call(this, s)) return;
 51 
 52   var nodes = s.nodes,
 53       orient = s.orient,
 54       depth = s.depth,
 55       breadth = s.breadth,
 56       group = s.group,
 57       w = s.width,
 58       h = s.height;
 59 
 60   /** @private */
 61   function firstWalk(v) {
 62     var l, r, a;
 63     if (!v.firstChild) {
 64       if (l = v.previousSibling) {
 65         v.prelim = l.prelim + distance(v.depth, true);
 66       }
 67     } else {
 68       l = v.firstChild;
 69       r = v.lastChild;
 70       a = l; // default ancestor
 71       for (var c = l; c; c = c.nextSibling) {
 72         firstWalk(c);
 73         a = apportion(c, a);
 74       }
 75       executeShifts(v);
 76       var midpoint = .5 * (l.prelim + r.prelim);
 77       if (l = v.previousSibling) {
 78         v.prelim = l.prelim + distance(v.depth, true);
 79         v.mod = v.prelim - midpoint;
 80       } else {
 81         v.prelim = midpoint;
 82       }
 83     }
 84   }
 85 
 86   /** @private */
 87   function secondWalk(v, m, depth) {
 88     v.breadth = v.prelim + m;
 89     m += v.mod;
 90     for (var c = v.firstChild; c; c = c.nextSibling) {
 91       secondWalk(c, m, depth);
 92     }
 93   }
 94 
 95   /** @private */
 96   function apportion(v, a) {
 97     var w = v.previousSibling;
 98     if (w) {
 99       var vip = v,
100           vop = v,
101           vim = w,
102           vom = v.parentNode.firstChild,
103           sip = vip.mod,
104           sop = vop.mod,
105           sim = vim.mod,
106           som = vom.mod,
107           nr = nextRight(vim),
108           nl = nextLeft(vip);
109       while (nr && nl) {
110         vim = nr;
111         vip = nl;
112         vom = nextLeft(vom);
113         vop = nextRight(vop);
114         vop.ancestor = v;
115         var shift = (vim.prelim + sim) - (vip.prelim + sip) + distance(vim.depth, false);
116         if (shift > 0) {
117           moveSubtree(ancestor(vim, v, a), v, shift);
118           sip += shift;
119           sop += shift;
120         }
121         sim += vim.mod;
122         sip += vip.mod;
123         som += vom.mod;
124         sop += vop.mod;
125         nr = nextRight(vim);
126         nl = nextLeft(vip);
127       }
128       if (nr && !nextRight(vop)) {
129         vop.thread = nr;
130         vop.mod += sim - sop;
131       }
132       if (nl && !nextLeft(vom)) {
133         vom.thread = nl;
134         vom.mod += sip - som;
135         a = v;
136       }
137     }
138     return a;
139   }
140 
141   /** @private */
142   function nextLeft(v) {
143     return v.firstChild || v.thread;
144   }
145 
146   /** @private */
147   function nextRight(v) {
148     return v.lastChild || v.thread;
149   }
150 
151   /** @private */
152   function moveSubtree(wm, wp, shift) {
153     var subtrees = wp.number - wm.number;
154     wp.change -= shift / subtrees;
155     wp.shift += shift;
156     wm.change += shift / subtrees;
157     wp.prelim += shift;
158     wp.mod += shift;
159   }
160 
161   /** @private */
162   function executeShifts(v) {
163     var shift = 0, change = 0;
164     for (var c = v.lastChild; c; c = c.previousSibling) {
165       c.prelim += shift;
166       c.mod += shift;
167       change += c.change;
168       shift += c.shift + change;
169     }
170   }
171 
172   /** @private */
173   function ancestor(vim, v, a) {
174     return (vim.ancestor.parentNode == v.parentNode) ? vim.ancestor : a;
175   }
176 
177   /** @private */
178   function distance(depth, siblings) {
179     return (siblings ? 1 : (group + 1)) / ((orient == "radial") ? depth : 1);
180   }
181 
182   /* Initialize temporary layout variables. TODO: store separately. */
183   var root = nodes[0];
184   root.visitAfter(function(v, i) {
185       v.ancestor = v;
186       v.prelim = 0;
187       v.mod = 0;
188       v.change = 0;
189       v.shift = 0;
190       v.number = v.previousSibling ? (v.previousSibling.number + 1) : 0;
191       v.depth = i;
192     });
193 
194   /* Compute the layout using Buchheim et al.'s algorithm. */
195   firstWalk(root);
196   secondWalk(root, -root.prelim, 0);
197 
198   /** @private Returns the angle of the given node. */
199   function midAngle(n) {
200     return (orient == "radial") ? n.breadth / depth : 0;
201   }
202 
203   /** @private */
204   function x(n) {
205     switch (orient) {
206       case "left": return n.depth;
207       case "right": return w - n.depth;
208       case "top":
209       case "bottom": return n.breadth + w / 2;
210       case "radial": return w / 2 + n.depth * Math.cos(midAngle(n));
211     }
212   }
213 
214   /** @private */
215   function y(n) {
216     switch (orient) {
217       case "left":
218       case "right": return n.breadth + h / 2;
219       case "top": return n.depth;
220       case "bottom": return h - n.depth;
221       case "radial": return h / 2 + n.depth * Math.sin(midAngle(n));
222     }
223   }
224 
225   /* Clear temporary layout variables; transform depth and breadth. */
226   root.visitAfter(function(v) {
227       v.breadth *= breadth;
228       v.depth *= depth;
229       v.midAngle = midAngle(v);
230       v.x = x(v);
231       v.y = y(v);
232       if (v.firstChild) v.midAngle += Math.PI;
233       delete v.breadth;
234       delete v.depth;
235       delete v.ancestor;
236       delete v.prelim;
237       delete v.mod;
238       delete v.change;
239       delete v.shift;
240       delete v.number;
241       delete v.thread;
242     });
243 };
244 
245 /**
246  * The offset between siblings nodes; defaults to 15.
247  *
248  * @type number
249  * @name pv.Layout.Tree.prototype.breadth
250  */
251 
252 /**
253  * The offset between parent and child nodes; defaults to 60.
254  *
255  * @type number
256  * @name pv.Layout.Tree.prototype.depth
257  */
258 
259 /**
260  * The orientation. The default orientation is "top", which means that the root
261  * node is placed on the top edge, leaf nodes appear at the bottom, and internal
262  * nodes are in-between. The following orientations are supported:<ul>
263  *
264  * <li>left - left-to-right.
265  * <li>right - right-to-left.
266  * <li>top - top-to-bottom.
267  * <li>bottom - bottom-to-top.
268  * <li>radial - radially, with the root at the center.</ul>
269  *
270  * @type string
271  * @name pv.Layout.Tree.prototype.orient
272  */
273 
274 /**
275  * The sibling grouping, i.e., whether differentiating space is placed between
276  * sibling groups. The default is 1 (or true), causing sibling leaves to be
277  * separated by one breadth offset. Setting this to false (or 0) causes
278  * non-siblings to be adjacent.
279  *
280  * @type number
281  * @name pv.Layout.Tree.prototype.group
282  */
283