-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBlogMTreeOld.html
214 lines (196 loc) · 10 KB
/
BlogMTreeOld.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
<!DOCTYPE html>
<html>
<head>
<!--
- BlogMTree.htm - Code Artist Thoughts
- ver 1.2 - 15 August 2013
- Jim Fawcett, Syracuse University
-->
<meta http-equiv="content-type" content="text/html;charset=UTF-8" />
<meta name="description" content="Software Engineering course notes. Code Samples. Software Links" />
<meta name="keywords" content="Lecture, Notes, Code, Syracuse,University" />
<meta name="Author" content="Jim Fawcett" />
<meta name="Author" content="James Fawcett" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>Blog.MTree</title>
<script src="js/ScriptsUtilities.js"></script>
<script src="js/ScriptsTemplate.js"></script>
<script src="js/ScriptsKeyboard.js"></script>
<script src="js/ScriptsMenu.js"></script>
<link rel="stylesheet" href="css/StylesTemplate.css" />
<link rel="stylesheet" href="css/StylesDefault.css" />
<link rel="stylesheet" href="css/StylesMenu.css" />
<link rel="stylesheet" href="css/StylesBrownTheme.css" />
<style>
#github header {
margin-left: 0px;
margin-right: 0px;
}
#github #pagetitle {
background-color: #e3dac9;
color: #800020;
border: 1px solid maroon;
}
#github #title {
background-color: #e3dac9;
color: #3f000f;
}
</style>
</head>
<body id="github" onload="initializeMenu()">
<navKeys-Container>
<nav-Key id="sKey" onclick="toggleSwipeEvents()">S</nav-Key>
<nav-Key id="rKey" onclick="location.reload()">R</nav-Key>
<nav-Key id="tKey" onclick="scrollPageTop()">T</nav-Key>
<nav-Key id="bKey" onclick="scrollPageBottom()">B</nav-Key>
<nav-Key id="hKey" onclick="helpWin()">H</nav-Key>
<nav-Key id="pKey" onclick="loadPrev()">P</nav-Key>
<nav-Key id="nKey" onclick="loadNext()">N</nav-Key>
</navKeys-Container>
<nav>
<div id="navbar"></div>
</nav>
<a id="Next" href="BlogGraph.html">N</a>
<a id="Prev" href="BlogCodeAnalyzer.html">P</a>
<header>
<hgroup id="pagetitle">
<h1 id="title">Code Artistry - C++ M-ary Tree</h1>
</hgroup>
</header>
<!-- page content -->
<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 style="width:calc(100vw - 9rem)">
<div class="photo" style="float:right">
<div align="right" style="margin-right:40px; margin-top:0px;">
MTree
<input type="button" value="+" onclick="incrementSize(1);" />
<input type="button" value="-" onclick="decrementSize(1);" />
</div>
<img id="1" src="Pictures/CodeScopes.PNG" width="475" />
<div> Figure 1. - Code Scopes Tree Representation</div>
</div>
</div>
<div style="width:calc(100vw - 9rem)">
<div class="photo" style="float:right; clear:both;">
<div align="right" style="margin-right:40px; margin-top:0px;">
MTree
<input type="button" value="+" onclick="incrementSize(2);" />
<input type="button" value="-" onclick="decrementSize(2);" />
</div>
<img id="2" src="Pictures/WalkMTree.PNG" width="300" />
<div> Figure 2. - Code Scopes Fragment</div>
</div>
</div>
<h3>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>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>
<div style="width:calc(100vw - 9rem)">
<div class="photo" style="float:right; clear:both;">
<div align="right" style="margin-right:40px; margin-top:0px;">
MTree
<input type="button" value="+" onclick="incrementSize(3);" />
<input type="button" value="-" onclick="decrementSize(3);" />
</div>
<img id="3" src="Pictures/MTreeClassDiag.PNG" width="475" />
<div> Figure 3. - MTree<Node> Package Classes</div>
</div>
</div>
<h3>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>
<div style="width:calc(100vw - 9rem)">
<div class="photo" style="float:right; clear:both;">
<div align="right" style="margin-right:40px; margin-top:0px;">
MTree
<input type="button" value="+" onclick="incrementSize(4);" />
<input type="button" value="-" onclick="decrementSize(4);" />
</div>
<img id="4" src="Pictures/MTreeOutput.PNG" width="475" />
<div> Figure 4. - MTree<Node> Output</div>
</div>
</div>
<h3>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>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>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 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>
<t-b>
<div style="width:calc(100vw - 9rem);"><img class="photo" src="Pictures/linkStrip.jpg" alt="Newhouse" style="width:100%;" /></div>
</t-b>
<info-bar></info-bar>
</body>
</html>