-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBlogMTree.html
281 lines (268 loc) · 13.8 KB
/
BlogMTree.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
<!DOCTYPE html>
<html>
<!--
BlogMTree.html
-->
<head>
<title>Blog MTree</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<!-- <link rel="icon" type="image/x-icon" href="./images/favicon.ico" /> -->
<link rel="stylesheet" href="css/StylesPhoto.css" />
<link rel="stylesheet" href="css/StylesSizerComp.css" />
<!-- PageFrame infrastructure -->
<link rel="stylesheet" href="css/StylesPageFrameDefaults.css" />
<link rel="stylesheet" href="css/StylesPageFrameStructure.css" />
<link rel="stylesheet" href="css/StylesPageFrameMenus.css" />
<link rel="stylesheet" href="css/StylesPageFrameThemePython.css" />
<link rel="stylesheet" href="css/StylesWebComponents.css" />
<script src="js/ScriptsWebComponents.js"></script>
<!--<script src="js/ScriptsPageFrameDefaults.js"></script>-->
<script src="js/ScriptsPageFramePosts.js"></script>
<script src="js/ScriptsPageFramePagesPosts.js"></script>
<script src="js/ScriptsPageFrameKeyboard.js"></script>
<!-- <script src="js/ScriptsSizerComp.js"></script> -->
<!-- No need for Pages script for pages with no next or prev pages -->
<!--<script src="js/ScriptsPageFramePages.js"></script>-->
<!-- <script src="js/ScriptsTemplate.js"></script>
<link rel="stylesheet" href="css/StylesTemplate.css" /> -->
<style>
h3 {
margin-top: 1.5em;
}
#subtitle {
margin-top: 0.4em;
margin-bottom: 0.3em;
}
#github header summary {
border: 1px solid var(--light);
}
#github summary {
padding-right: 2em;
}
/* #github .menuHead {
margin:0em -0.25em 0.0em -0.25em;
padding:0.25em 0.5em;
} */
</style>
<script>
function load() {
initialize();
//loadif();
}
</script>
<style>
#github note {
display: block;
width:max-content;
border:1px solid red;
padding:0.5em 1.0em;
margin:0.5em 0em;
}
#github .bargraph {
border: 1px solid var(--dark);
/* background-color: #bbb; */
padding: 0.1em 0.5em;
font-size:0.9em;
}
#github table {
border:2px solid var(--dark);
}
#github table td {
padding:0.25em 1.0em;
border:none;
}
body {
user-select:none;
}
</style>
<script>
function clickstat() {
// prevent parent click event handling
event.stopImmediatePropagation();
}
</script>
</head>
<body id="github" onload="load()" style="position:relative;">
<a id="Next" href="BlogGraph.html">Next</a>
<a id="Prev" href="BlogCodeAnalyzer.html">Prev</a>
<page-frame>
<frame-header>
<nav id="navbar"></nav>
</frame-header>
<main id="main">
<div id="about" onclick="this.style.display = 'none'">about</div>
<div id="page">Blog: MTree</div>
<div id="modified">11/28/2024</div>
<div id="hlp"></div>
<a id="top"></a>
<content style="height:100vh; position:relative;">
<header style="cursor:pointer;" onclick="loadif()">
<!-- <a target="_blank" class="repoLink" href="https://github.com/JimFawcett">github Repositories</a> -->
<hgroup id="pagetitle" style="border: 2px solid var(--dark);">
<h1 id="title">Blog: MTree</h1>
<h3 class="indent" id="subtitle">
linked m-ary tree structure
</h3>
</hgroup>
<!-- <img style="width:100%; margin:-0.1em 0em; border:2px solid var(--dark); padding:0.5em; background-color:var(--light);" src="Pictures/officestrip3a.svg" /> -->
<div class="darkItem" onclick="loadif()" style="cursor:pointer; position:relative; padding:0.0em 0em 0.25em 0em; margin-top:-0.50em; border:2px solid var(--dark);">
<a class="repoLinks" target="_blank" href="https://github.com/JimFawcett" style="color:var(--atten); margin-left:1.5em;">About</a>
<div style="font-size:0.9em; position:absolute; top:0.1em; right:1.5em;">click to toggle Site Explorer</div>
<div style="height:0.5em;"></div>
</div>
</header>
<h3>Initial Thoughts:</h3>
<t-b>
The Trees we are concerned with here are not balanced binary trees used for quick access to ordered data.
They are simple tree structures where each tree node may have zero or more child nodes. They are often used
as in-memory representations of tree structures that occur as artifacts of processing activities, i.e., parse trees
resulting from processing markup like XML or HTML.
</t-b>
<t-b>
Our interests focus on using M-ary Trees to support code analysis. We will use instances of a C++ template class MTree<T>, discussed here,
to capture the structure of code scopes<sup>1</sup>. For example, one measure of complexity of a function written in C, C++, Java, or C#
is the number of scopes the function uses for branching and looping to carry out its processing activities. This is
closely related to the well-know McCabe Cyclomatic Complexity metric.
</t-b>
<!-- <div class="right" style="display:flex; flex-direction: column;"> -->
<div class="right">
<photosizer-block src="Pictures/CodeScopes.PNG" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 1. - Code Scopes Walker</span>
</photosizer-block>
</div>
<div class="right clear">
<photosizer-block src="Pictures/WalkMTree.PNG" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 2. - Code Scopes Fragment</span>
</photosizer-block>
</div>
<div class="right clear">
<photosizer-block src="Pictures/MTreeClassDiag.PNG" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 3. - MTree<Node> Package Classes</span>
</photosizer-block>
</div>
<div class="right clear">
<photosizer-block src="Pictures/MTreeOutput.PNG" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 4. - MTree<Node> Output</span>
</photosizer-block>
</div>
<!-- </div> -->
<h3 id="background">Background:</h3>
<t-b>
The Spring 2014 CSE687 - Object Oriented Design class will, in their first project, build a code analyzer that, for each file it processes,
finds the size and complexity of all function definitions. We will use some of that code to build, in Project #2, a code similarity
detector. That would be useful for code refactoring: to find, for later replacement, duplicated code in a set of packages. The intent
is to replace duplicated code with invocations of an extracted function.
</t-b>
<t-b>
Eliminating redundancies avoids fixing bugs in multiple places or worse, fixing in only one of several places the bug occurs.
Our redundancy analysis seeks to find congruencies within the scope trees
of analyzed function definitions. So we will need a way to capture a representation of the these scope trees - enter the class MTree<T>.
</t-b>
<h3 id="core_idea">Core Idea:</h3>
<t-b>
A function's scope tree is something like it's DNA. If two functions have scope subtrees that are identical in structure and the scope nodes
have similar line counts the behavior of those parts of the code may not be identical, but their processing is certainly similar. We've shown
in Figures 1 and 2 the code and scope tree of member function MTree<Node>::walk(Node*).
</t-b>
<t-b>
Each tree node has been annotated with the line count of the scope it represents. If we find, in some other function, a tree with similar structure
and line counts that becomes a candidate to examine for code duplication. We won't go into how we measure similarity - its not complicated, but
isn't relevant to a discussion of the M-ary Tree.
</t-b>
<h3 id="design">Design:</h3>
<t-b>
The MTree<Node> class and helper class, MNode<T>, are relatively simple template classes. The template parameter Node used by
MTree<Node> is expected to take the type MNode<T> where T represents the type of data held by each node. That may be a library type
like a string or some user-defined type that holds composite information.
</t-b>
<t-b>
Each instance of MNode<T> holds a vector of pointers to child nodes, created on the native C++ heap. The class provides methods to
add and remove child nodes and mark nodes for traversal. The MTree<Node> class provides a method to make an instance of its Node parameter
the tree root and assumes that the Node addChild method will be used to build out the tree.
</t-b>
<t-b>
Client programs interact with an instance of MTree<Node> in two ways. The using code may define a class derived from the Operation<Node>
class that defines what processing should occur when nodes are encountered on a depth first tree traversal. The class can provide accessor functions
to feed the operation, initializing data and collect results at the end of traversal.
</t-b>
<t-b>
Clients may also use the methods MTree<Node>::find() and MTree<Node>::finder(). find() simply returns with a pointer to a Node that
has a specified value, if it exists, else returns null. finder() uses an instance of finderOp<Node>, derived from Operation<Node>.
This nominally does the same thing, except that finder() has more control over how the search is implemented.
</t-b>
<h3 id="output">Typical Output:</h3>
<t-b>
Demo output is presented in Figure 4, which shows test code traversing the MTree and using find and finder. Also shown is the removal
of an MTree<Node> node, making copies of the tree and assigning to other tree instances.
</t-b>
<h3 id="code">Source Code:</h3>
<t-b>
This M-ary Tree Demo is written in C++ using Visual Studio 2012 and compiles and runs using Visual Studio 2013 as well.
You will find the code here:
</t-b>
<div style="width:calc(100vw - 9rem)">
<div class="indent" style="margin: 10px;">
<a href="../CoreTechnologies/Cpp/code/MTree">MTree<Node> Demo Code</a>
</div>
</div>
<t-b>This code bears a copyright © that grants all rights to users except the right to publish and requires retention of the copyright notice.</t-b>
<h3 id="conclusions">Conclusions:</h3>
<t-b>
The MTree<Node> package demonstrates how you can use C++ to build something close to an Abstract Data Type (ADT). We haven't made an
effort to make this container compatible with the algorithms in the STL. That wouldn't be too hard to do, but the package isn't widely applicable
outside of the way we will be using it, so we chose not to do that.
</t-b>
<div style="height:0.75em;"></div>
<div class="footnote clear"></div>
<hr />
<ol>
<li>
The <a href="BlogGlobals.htm">Global Data Blog entry</a> has a fairly complete discussion of code scope structure.
</li>
</ol>
<div style="height:1.0em;"></div>
<t-b>
<div style="width:calc(100vw - 9rem);"><img class="photo" src="Pictures/linkStrip.jpg" alt="Newhouse" style="width:100%;" /></div>
</t-b>
<!-- <div style="height:1.75em;"></div>
<div>
<img class="photo" src="Pictures/campusStrip.jpg" alt="Newhouse" style="width:100%;" />
</div> -->
<div style="height:1.0em;"></div>
<a id="bottom"></a>
</content>
<page-TOC id="pages" style="display:none;">
</page-TOC>
<page-sections id="sections" style="display:none;">
<menu-elem style="width:0.0em"> </menu-elem>
<menu-elem class="secElem"><a href="#bottom">bottom</a></menu-elem>
<menu-elem class="secElem"><a href="#conclusions">conclusions</a></menu-elem>
<menu-elem class="secElem"><a href="#code">code</a></menu-elem>
<menu-elem class="secElem"><a href="#output">output</a></menu-elem>
<menu-elem class="secElem"><a href="#design">design</a></menu-elem>
<menu-elem class="secElem"><a href="#core_idea">core idea</a></menu-elem>
<menu-elem class="secElem"><a href="#background">background</a></menu-elem>
<menu-elem class="secElem"><a href="#top">top</a></menu-elem>
<div class='darkItem popupHeader' style="padding:0.25em 2.0em;" onclick="this.parentElement.style.display='none'">Sections</div>
</page-sections>
</main>
<frame-footer>
<menu-item style="width:2.0em;"> </menu-item>
<menu-elem id="nextLink2" onclick="bottomMenu.next()">Next</menu-elem>
<menu-elem id="prevLink2" onclick="bottomMenu.prev()">Prev</menu-elem>
<menu-elem id="pgbtn" onclick="bottomMenu.pages()">Pages</menu-elem>
<menu-elem onclick="bottomMenu.sections()">Sections</menu-elem>
<menu-elem onclick="bottomMenu.about()">About</menu-elem>
<menu-elem id="kysbtn" onclick="storyHlpMenu.keys()">Keys</menu-elem>
<menu-elem style="margin-right:1em">
<span id="loc" style="display:inline-block; font-weight:normal"></span>
</menu-elem>
</frame-footer>
</page-frame>
<script>
let loc = document.getElementById("loc");
let fn = window.location.href.split(/\/|\\/).pop();
loc.innerHTML = fn + ":";
</script>
</body>
</html>