1 // TODO share code with Treemap
  2 // TODO inspect parent panel dimensions to set inner and outer radii
  3 
  4 /**
  5  * Returns a new sunburst tree layout.
  6  *
  7  * @class A tree layout in the form of a sunburst. <img
  8  * src="../sunburst.png" width="160" height="160" align="right"> The
  9  * center circle corresponds to the root of the tree; subsequent rings
 10  * correspond to each tier. Rings are subdivided into wedges based on the size
 11  * of nodes, per {@link #size}. Within a ring, wedges are sorted by size.
 12  *
 13  * <p>The tree layout is intended to be extended (see {@link pv.Mark#extend} by
 14  * a {@link pv.Wedge}. The data property returns an array of nodes for use by
 15  * other property functions. The following node attributes are supported:
 16  *
 17  * <ul>
 18  * <li><tt>left</tt> - the wedge left position.
 19  * <li><tt>top</tt> - the wedge top position.
 20  * <li><tt>innerRadius</tt> - the wedge inner radius.
 21  * <li><tt>outerRadius</tt> - the wedge outer radius.
 22  * <li><tt>startAngle</tt> - the wedge start angle.
 23  * <li><tt>endAngle</tt> - the wedge end angle.
 24  * <li><tt>angle</tt> - the wedge angle.
 25  * <li><tt>depth</tt> - the node depth (tier; the root is 0).
 26  * <li><tt>keys</tt> - an array of string keys for the node.
 27  * <li><tt>size</tt> - the aggregate node size.
 28  * <li><tt>children</tt> - child nodes, if any.
 29  * <li><tt>data</tt> - the associated tree element, for leaf nodes.
 30  * </ul>
 31  *
 32  * <p>To produce a default sunburst layout, say:
 33  *
 34  * <pre>.add(pv.Wedge)
 35  *   .extend(pv.Layout.sunburst(tree))</pre>
 36  *
 37  * To only show nodes at a depth of two or greater, you might say:
 38  *
 39  * <pre>.add(pv.Wedge)
 40  *   .extend(pv.Layout.sunburst(tree))
 41  *   .visible(function(n) n.depth > 1)</pre>
 42  *
 43  * The format of the <tt>tree</tt> argument is a hierarchical object whose leaf
 44  * nodes are numbers corresponding to their size. For an example, and
 45  * information on how to convert tabular data into such a tree, see
 46  * {@link pv.Tree}. If the leaf nodes are not numbers, a {@link #size} function
 47  * can be specified to override how the tree is interpreted. This size function
 48  * can also be used to transform the data.
 49  *
 50  * <p>By default, the sunburst fills the full width and height of the parent
 51  * panel. An optional root key can be specified using {@link #root} for
 52  * convenience.
 53  *
 54  * @param tree a tree (an object) who leaf attributes have sizes.
 55  * @returns {pv.Layout.sunburst} a tree layout.
 56  */
 57 pv.Layout.sunburst = function(tree) {
 58   var keys = [], sizeof = Number, w, h, r;
 59 
 60   /** @private */
 61   function accumulate(map) {
 62     var node = {size: 0, children: [], keys: keys.slice()};
 63     for (var key in map) {
 64       var child = map[key], size = sizeof(child);
 65       keys.push(key);
 66       if (isNaN(size)) {
 67         child = accumulate(child);
 68       } else {
 69         child = {size: size, data: child, keys: keys.slice()};
 70       }
 71       node.children.push(child);
 72       node.size += child.size;
 73       keys.pop();
 74     }
 75     node.children.sort(function(a, b) { return b.size - a.size; });
 76     return node;
 77   }
 78 
 79   /** @private */
 80   function scale(node, k) {
 81     node.size *= k;
 82     if (node.children) {
 83       for (var i = 0; i < node.children.length; i++) {
 84         scale(node.children[i], k);
 85       }
 86     }
 87   }
 88 
 89   /** @private */
 90   function depth(node, i) {
 91     i = i ? (i + 1) : 1;
 92     return node.children
 93         ? pv.max(node.children, function(n) { return depth(n, i); })
 94         : i;
 95   }
 96 
 97   /** @private */
 98   function layout(node) {
 99     if (node.children) {
100       wedgify(node);
101       for (var i = 0; i < node.children.length; i++) {
102         layout(node.children[i]);
103       }
104     }
105   }
106 
107   /** @private */
108   function wedgify(node) {
109     var startAngle = node.startAngle;
110     for (var i = 0; i < node.children.length; i++) {
111       var child = node.children[i], angle = (child.size / node.size) * node.angle;
112       child.startAngle = startAngle;
113       child.angle = angle;
114       child.endAngle = startAngle + angle;
115       child.depth = node.depth + 1;
116       child.left = w / 2;
117       child.top = h / 2;
118       child.innerRadius = Math.max(0, child.depth - .5) * r;
119       child.outerRadius = (child.depth + .5) * r;
120       startAngle += angle;
121       if (child.children) {
122         wedgify(child);
123       }
124     }
125   }
126 
127   /** @private */
128   function flatten(node, array) {
129     if (node.children) {
130       for (var i = 0; i < node.children.length; i++) {
131         flatten(node.children[i], array);
132       }
133     }
134     array.push(node)
135     return array;
136   }
137 
138   /** @private */
139   function data() {
140     var root = accumulate(tree);
141     w = this.parent.width();
142     h = this.parent.height();
143     r = Math.min(w, h) / 2 / (depth(root) - .5);
144     root.left = w / 2;
145     root.top = h / 2;
146     root.startAngle = 0;
147     root.angle = 2 * Math.PI;
148     root.endAngle = 2 * Math.PI;
149     root.innerRadius = 0;
150     root.outerRadius = r;
151     root.depth = 0;
152     layout(root);
153     return flatten(root, []).reverse();
154   }
155 
156   /* A dummy mark, like an anchor, which the caller extends. */
157   var mark = new pv.Mark()
158       .data(data)
159       .left(function(n) { return n.left; })
160       .top(function(n) { return n.top; })
161       .startAngle(function(n) { return n.startAngle; })
162       .angle(function(n) { return n.angle; })
163       .innerRadius(function(n) { return n.innerRadius; })
164       .outerRadius(function(n) { return n.outerRadius; });
165 
166   /**
167    * Specifies the root key; optional. The root key is prepended to the
168    * <tt>keys</tt> attribute for all generated nodes. This method is provided
169    * for convenience and does not affect layout.
170    *
171    * @param {string} v the root key.
172    * @function
173    * @name pv.Layout.sunburst.prototype.root
174    * @returns {pv.Layout.sunburst} this.
175    */
176   mark.root = function(v) {
177     keys = [v];
178     return this;
179   };
180 
181   /**
182    * Specifies the sizing function. By default, the sizing function is
183    * <tt>Number</tt>. The sizing function is invoked for each node in the tree
184    * (passed to the constructor): the sizing function must return
185    * <tt>undefined</tt> or <tt>NaN</tt> for internal nodes, and a number for
186    * leaf nodes. The aggregate sizes of internal nodes will be automatically
187    * computed by the layout.
188    *
189    * <p>For example, if the tree data structure represents a file system, with
190    * files as leaf nodes, and each file has a <tt>bytes</tt> attribute, you can
191    * specify a size function as:
192    *
193    * <pre>.size(function(d) d.bytes)</pre>
194    *
195    * This function will return <tt>undefined</tt> for internal nodes (since
196    * these do not have a <tt>bytes</tt> attribute), and a number for leaf nodes.
197    *
198    * <p>Note that the built-in <tt>Math.sqrt</tt> and <tt>Math.log</tt> methods
199    * can be used as sizing functions. These function similarly to
200    * <tt>Number</tt>, except perform a root and log scale, respectively.
201    *
202    * @param {function} f the new sizing function.
203    * @function
204    * @name pv.Layout.sunburst.prototype.size
205    * @returns {pv.Layout.sunburst} this.
206    */
207   mark.size = function(f) {
208     sizeof = f;
209     return this;
210   };
211 
212   return mark;
213 };
214