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