SDSL  3.0.0
Succinct Data Structure Library
structure_tree.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_STRUCTURE_TREE
9 #define INCLUDED_SDSL_STRUCTURE_TREE
10 
11 #include <iostream>
12 #include <memory>
13 #include <sstream>
14 #include <string>
15 
16 #include <sdsl/config.hpp>
17 #include <sdsl/uintx_t.hpp>
18 
19 #include <unordered_map>
20 
22 namespace sdsl
23 {
24 
25 inline void output_tab(std::ostream & out, size_t level)
26 {
27  for (size_t i = 0; i < level; i++) out << "\t";
28 }
29 
31 {
32  private:
33  using map_type = std::unordered_map<std::string, std::unique_ptr<structure_tree_node>>;
34  map_type m_children;
35 
36  public:
37  const map_type & children = m_children;
38  size_t size = 0;
39  std::string name;
40  std::string type;
41 
42  public:
43  structure_tree_node(const std::string & n, const std::string & t)
44  : name(n)
45  , type(t)
46  {}
47  structure_tree_node * add_child(const std::string & n, const std::string & t)
48  {
49  auto hash = n + t;
50  auto child_itr = m_children.find(hash);
51  if (child_itr == m_children.end())
52  {
53  // add new child as we don't have one of this type yet
54  structure_tree_node * new_node = new structure_tree_node(n, t);
55  m_children[hash] = std::unique_ptr<structure_tree_node>(new_node);
56  return new_node;
57  }
58  else
59  {
60  // child of same type and name exists
61  return (*child_itr).second.get();
62  }
63  }
64  void add_size(size_t s) { size += s; }
65 };
66 
68 {
69  public:
70  static structure_tree_node * add_child(structure_tree_node * v, const std::string & name, const std::string & type)
71  {
72  if (v) return v->add_child(name, type);
73  return nullptr;
74  };
75  static void add_size(structure_tree_node * v, uint64_t value)
76  {
77  if (v) v->add_size(value);
78  };
79 };
80 
81 template <format_type F>
82 void write_structure_tree(const structure_tree_node * v, std::ostream & out, size_t level = 0);
83 
84 template <>
85 inline void write_structure_tree<JSON_FORMAT>(const structure_tree_node * v, std::ostream & out, size_t level)
86 {
87  if (v)
88  {
89  output_tab(out, level);
90  out << "{" << std::endl;
91  output_tab(out, level + 1);
92  out << "\"class_name\":"
93  << "\"" << v->type << "\"," << std::endl;
94  output_tab(out, level + 1);
95  out << "\"name\":"
96  << "\"" << v->name << "\"," << std::endl;
97  output_tab(out, level + 1);
98  out << "\"size\":"
99  << "\"" << v->size << "\"";
100 
101  if (v->children.size())
102  {
103  out << "," << std::endl; // terminate the size tag from before if there are children
104  output_tab(out, level + 1);
105  out << "\"children\":[" << std::endl;
106  size_t written_child_elements = 0;
107  for (const auto & child : v->children)
108  {
109  if (written_child_elements++ > 0) { out << "," << std::endl; }
110  write_structure_tree<JSON_FORMAT>(child.second.get(), out, level + 2);
111  }
112  out << std::endl;
113  output_tab(out, level + 1);
114  out << "]" << std::endl;
115  }
116  else
117  {
118  out << std::endl;
119  }
120  output_tab(out, level);
121  out << "}";
122  }
123 }
124 
125 inline std::string create_html_header(const char * file_name)
126 {
127  std::stringstream jsonheader;
128  jsonheader << "<html>\n"
129  << " <head>\n"
130  << " <meta http-equiv=\"Content-Type\" content=\"text/html;charset=utf-8\">\n"
131  << " <title>" << file_name << "</title>\n"
132  << " <script src=\"file:///builddir/build/BUILD/sdsl-lite-3.0.0/external/d3/d3.min.js\"></script>"
133  << " <script src=\"http://d3js.org/d3.v2.js\"></script>\n"
134  << " <style type=\"text/css\">\n"
135  << " path { stroke: #000; stroke-width: 0.8; cursor: pointer; }\n"
136  << " text { font: 11px sans-serif; cursor: pointer; }\n"
137  << " body { width: 900; margin: 0 auto; }\n"
138  << " h1 { text-align: center; margin: .5em 0; }\n"
139  << " #breadcrumbs { display: none; }\n"
140  << " svg { font: 10px sans-serif; }\n"
141  << " </style>\n"
142  << " </head>\n"
143  << "<body marginwidth=\"0\" marginheight=\"0\">\n"
144  << "<button><a id=\"download\">Save as SVG</a></button>\n"
145  << " <div id=\"chart\"></div>" << std::endl;
146  return jsonheader.str();
147 }
148 
149 inline std::string create_js_body(const std::string & jsonsize)
150 {
151  std::stringstream jsonbody;
152  jsonbody << "<script type=\"text/javascript\">" << std::endl
153  << ""
154  "var w = 800,\n"
155  " h = w,\n"
156  " r = w / 2,\n"
157  " x = d3.scale.linear().range([0, 2 * Math.PI]),\n"
158  " y = d3.scale.pow().exponent(1.3).domain([0, 1]).range([0, r]),\n"
159  " p = 5,\n"
160  " color = d3.scale.category20c(),\n"
161  " duration = 1000;\n"
162  "\n"
163  "var vis = d3.select(\"#chart\").append(\"svg:svg\")\n"
164  " .attr(\"width\", w + p * 2)\n"
165  " .attr(\"height\", h + p * 2)\n"
166  " .append(\"g\")\n"
167  " .attr(\"transform\", \"translate(\" + (r + p) + \",\" + (r + p) + \")\");\n"
168  "\n"
169  "vis.append(\"p\")\n"
170  " .attr(\"id\", \"intro\")\n"
171  " .text(\"Click to zoom!\");\n"
172  "\n"
173  "var partition = d3.layout.partition()\n"
174  " .sort(null)\n"
175  " .size([2 * Math.PI, r * r])\n"
176  " .value(function(d) { return d.size; });\n"
177  "\n"
178  "var arc = d3.svg.arc()\n"
179  " .startAngle(function(d) { return Math.max(0, Math.min(2 * Math.PI, x(d.x))); })\n"
180  " .endAngle(function(d) { return Math.max(0, Math.min(2 * Math.PI, x(d.x + d.dx))); })\n"
181  " .innerRadius(function(d) { return Math.max(0, d.y ? y(d.y) : d.y); })\n"
182  " .outerRadius(function(d) { return Math.max(0, y(d.y + d.dy)); });\n"
183  "\n"
184  " "
185  << std::endl
186  << "var spaceJSON = " << jsonsize << ";" << std::endl
187  << std::endl
188  << "\n"
189  "\n"
190  " var nodes = partition.nodes(spaceJSON);\n"
191  "\n"
192  " var path = vis.selectAll(\"path\").data(nodes);\n"
193  " path.enter().append(\"path\")\n"
194  " .attr(\"id\", function(d, i) { return \"path-\" + i; })\n"
195  " .attr(\"d\", arc)\n"
196  " .attr(\"fill-rule\", \"evenodd\")\n"
197  " .style(\"fill\", colour)\n"
198  " .on(\"click\", click);\n"
199  "\n"
200  " path.append(\"title\").text(function(d) { return 'class name: ' + d.class_name + "
201  "'\\nmember_name: ' + d.name + '\\n size: ' + sizeMB(d) });\n"
202  "\n"
203  " var text = vis.selectAll(\"text\").data(nodes);\n"
204  " var textEnter = text.enter().append(\"text\")\n"
205  " .style(\"opacity\", 1)\n"
206  " .style(\"fill\", function(d) {\n"
207  " return brightness(d3.rgb(colour(d))) < 125 ? \"#eee\" : \"#000\";\n"
208  " })\n"
209  " .attr(\"text-anchor\", function(d) {\n"
210  " return x(d.x + d.dx / 2) > Math.PI ? \"end\" : \"start\";\n"
211  " })\n"
212  " .attr(\"dy\", \".2em\")\n"
213  " .attr(\"transform\", function(d) {\n"
214  " var multiline = (d.name || \"\").split(\" \").length > 1,\n"
215  " angle = x(d.x + d.dx / 2) * 180 / Math.PI - 90,\n"
216  " rotate = angle + (multiline ? -.5 : 0);\n"
217  " return \"rotate(\" + rotate + \")translate(\" + (y(d.y) + p) + \")rotate(\" + (angle > "
218  "90 ? -180 : 0) + \")\";\n"
219  " })\n"
220  " .on(\"click\", click);\n"
221  "\n"
222  " textEnter.append(\"title\").text(function(d) { return 'class name: ' + d.class_name + "
223  "'\\nmember_name: ' + d.name + '\\n size: ' + sizeMB(d) });\n"
224  "\n"
225  " textEnter.append(\"tspan\")\n"
226  " .attr(\"x\", 0)\n"
227  " .text(function(d) { return d.dx < 0.05 ? \"\" : d.depth ? d.name.split(\" \")[0] : "
228  "\"\"; });\n"
229  " textEnter.append(\"tspan\")\n"
230  " .attr(\"x\", 0)\n"
231  " .attr(\"dy\", \"1em\")\n"
232  " .text(function(d) { return d.dx < 0.05 ? \"\" : d.depth ? d.name.split(\" \")[1] || "
233  "\"\" : \"\"; });\n"
234  "\n"
235  " function click(d) {\n"
236  " path.transition()\n"
237  " .duration(duration)\n"
238  " .attrTween(\"d\", arcTween(d));\n"
239  "\n"
240  " // Somewhat of a hack as we rely on arcTween updating the scales.\n"
241  " text\n"
242  " .style(\"visibility\", function(e) {\n"
243  " return isParentOf(d, e) ? null : d3.select(this).style(\"visibility\");\n"
244  " })\n"
245  " .transition().duration(duration)\n"
246  " .attrTween(\"text-anchor\", function(d) {\n"
247  " return function() {\n"
248  " return x(d.x + d.dx / 2) > Math.PI ? \"end\" : \"start\";\n"
249  " };\n"
250  " })\n"
251  " .attrTween(\"transform\", function(d) {\n"
252  " var multiline = (d.name || \"\").split(\" \").length > 1;\n"
253  " return function() {\n"
254  " var angle = x(d.x + d.dx / 2) * 180 / Math.PI - 90,\n"
255  " rotate = angle + (multiline ? -.5 : 0);\n"
256  " return \"rotate(\" + rotate + \")translate(\" + (y(d.y) + p) + \")rotate(\" + (angle "
257  "> 90 ? -180 : 0) + \")\";\n"
258  " };\n"
259  " })\n"
260  " .style(\"opacity\", function(e) { return isParentOf(d, e) ? 1 : 1e-6; })\n"
261  " .each(\"end\", function(e) {\n"
262  " d3.select(this).style(\"visibility\", isParentOf(d, e) ? null : \"hidden\");\n"
263  " });\n"
264  " }\n"
265  "\n"
266  "\n"
267  "function sizeMB(d) {\n"
268  "// if (d.children) {\n"
269  "// var sum = calcSum(d);\n"
270  "// return (sum / (1024*1024)).toFixed(2) + 'MB';\n"
271  "// } else {\n"
272  " return (d.size / (1024*1024)).toFixed(2) + 'MB';\n"
273  "// }\n"
274  "}\n"
275  "\n"
276  "function calcSum(d) {\n"
277  " if(d.children) {\n"
278  " var sum = 0;\n"
279  " function recurse(d) {\n"
280  " if(d.children) d.children.forEach( function(child) { recurse(child); } );\n"
281  " else sum += d.size;\n"
282  " }\n"
283  " recurse(d,sum);\n"
284  " console.log(sum);\n"
285  " console.log(d.children);\n"
286  " return sum;\n"
287  " } else {\n"
288  " console.log(d.size);\n"
289  " return d.size;\n"
290  " }\n"
291  "}\n"
292  "\n"
293  "function isParentOf(p, c) {\n"
294  " if (p === c) return true;\n"
295  " if (p.children) {\n"
296  " return p.children.some(function(d) {\n"
297  " return isParentOf(d, c);\n"
298  " });\n"
299  " }\n"
300  " return false;\n"
301  "}\n"
302  "\n"
303  "function colour(d) {\n"
304  " return color(d.name);\n"
305  "}\n"
306  "\n"
307  "// Interpolate the scales!\n"
308  "function arcTween(d) {\n"
309  " var my = maxY(d),\n"
310  " xd = d3.interpolate(x.domain(), [d.x, d.x + d.dx]),\n"
311  " yd = d3.interpolate(y.domain(), [d.y, my]),\n"
312  " yr = d3.interpolate(y.range(), [d.y ? 20 : 0, r]);\n"
313  " return function(d) {\n"
314  " return function(t) { x.domain(xd(t)); y.domain(yd(t)).range(yr(t)); return arc(d); };\n"
315  " };\n"
316  "}\n"
317  "\n"
318  "// Interpolate the scales!\n"
319  "function arcTween2(d) {\n"
320  " var xd = d3.interpolate(x.domain(), [d.x, d.x + d.dx]),\n"
321  " yd = d3.interpolate(y.domain(), [d.y, 1]),\n"
322  " yr = d3.interpolate(y.range(), [d.y ? 20 : 0, radius]);\n"
323  " return function(d, i) {\n"
324  " return i\n"
325  " ? function(t) { return arc(d); }\n"
326  " : function(t) { x.domain(xd(t)); y.domain(yd(t)).range(yr(t)); return arc(d); };\n"
327  " };\n"
328  "}\n"
329  "\n"
330  "function maxY(d) {\n"
331  " return d.children ? Math.max.apply(Math, d.children.map(maxY)) : d.y + d.dy;\n"
332  "}\n"
333  "\n"
334  "// http://www.w3.org/WAI/ER/WD-AERT/#color-contrast\n"
335  "function brightness(rgb) {\n"
336  " return rgb.r * .299 + rgb.g * .587 + rgb.b * .114;\n"
337  "}\n"
338  "d3.select(\"#download\").on(\"click\", function () {\n"
339  "d3.select(this).attr(\"href\", 'data:application/octet-stream;base64,' + "
340  "btoa(d3.select(\"#chart\").html())).attr(\"download\", \"memorysun.svg\")})\n\n"
341  "click(nodes[0]);\n"
342  " "
343  << std::endl
344  << "</script>" << std::endl
345  << "</body>" << std::endl
346  << "</html>" << std::endl;
347  return jsonbody.str();
348 }
349 
350 template <>
352  std::ostream & out,
353  SDSL_UNUSED size_t level)
354 {
355  std::stringstream json_data;
356  write_structure_tree<JSON_FORMAT>(v, json_data);
357 
358  out << create_html_header("sdsl data structure visualization");
359  out << create_js_body(json_data.str());
360 }
361 
362 } // namespace sdsl
363 #endif
structure_tree_node(const std::string &n, const std::string &t)
structure_tree_node * add_child(const std::string &n, const std::string &t)
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
#define SDSL_UNUSED
Definition: config.hpp:13
Namespace for the succinct data structure library.
void write_structure_tree< HTML_FORMAT >(const structure_tree_node *v, std::ostream &out, SDSL_UNUSED size_t level)
void write_structure_tree(const structure_tree_node *v, std::ostream &out, size_t level=0)
void output_tab(std::ostream &out, size_t level)
std::string create_js_body(const std::string &jsonsize)
void write_structure_tree< JSON_FORMAT >(const structure_tree_node *v, std::ostream &out, size_t level)
std::string create_html_header(const char *file_name)