Skip to content

Commit b224af5

Browse files
64json64json
committed
add ArrayTracer
1 parent fa6f854 commit b224af5

File tree

11 files changed

+326
-21
lines changed

11 files changed

+326
-21
lines changed

‎algorithm/sorting/insertion/basic/code.js‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
for (var j = 1; j < D.length; j++) {
2+
var key = D[j];
3+
tracer._select(j);
4+
for (var i = j - 1; (i >= 0) && (D[i] < key); i--) {
5+
D[i + 1] = D[i];
6+
}
7+
D[i + 1] = key;
8+
tracer._change(j);
9+
}

‎algorithm/sorting/insertion/basic/data.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
var tracer = new Array1DTracer();
2+
var D = tracer.createRandomData();
3+
tracer.setData(D);

‎algorithm/sorting/insertion/config.json‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
{
2+
"def": "Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.",
3+
"apps": [],
4+
"cpx": {
5+
"time": "O(n<sup>2</sup>)",
6+
"space": "O(n)"
7+
},
8+
"refs": [
9+
"https://en.wikipedia.org/wiki/Insertion_sort"
10+
],
11+
"files": {
12+
"basic": "Basic"
13+
}
14+
}

‎css/stylesheet.css‎

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -131,11 +131,12 @@ section {
131131
right: 0;
132132
}
133133

134-
.visualize_container {
134+
.module_container {
135135
top: 0;
136136
bottom: 50%;
137137
left: 0;
138138
right: 0;
139+
text-align: center;
139140
}
140141

141142
.tab_container {
@@ -217,7 +218,7 @@ pre {
217218
bottom: 0;
218219
right: 0;
219220
padding: 12px;
220-
z-index: 2;
221+
z-index: 4;
221222
}
222223

223224
.toast {
@@ -231,4 +232,22 @@ pre {
231232
.toast.error {
232233
border-color: rgb(150, 0, 0);
233234
background: rgba(120, 0, 0, .8);
235+
}
236+
237+
.mtbl-table {
238+
display: inline-table;
239+
color: white;
240+
table-layout: fixed;
241+
}
242+
243+
.mtbl-row {
244+
display: table-row;
245+
}
246+
247+
.mtbl-cell {
248+
padding: 3px 6px;
249+
display: table-cell;
250+
vertical-align: middle;
251+
text-align: center;
252+
background: #888;
234253
}

‎index.html‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ <h3>
3232
</section>
3333
<div class="workspace">
3434
<div class="viewer_container">
35-
<section class="visualize_container"></section>
35+
<section class="module_container"></section>
3636
<section class="tab_container">
3737
<div class="tab active" id="tab_description">
3838
<div class="wrapper">
@@ -85,6 +85,8 @@ <h3>Reference</h3>
8585
<script src="js/tracer.js"></script>
8686
<script src="js/module/graph.js"></script>
8787
<script src="js/module/weighted_graph.js"></script>
88+
<script src="js/module/array2d.js"></script>
89+
<script src="js/module/array1d.js"></script>
8890
<script src="js/script.js"></script>
8991
</body>
9092
</html>

‎js/module/array1d.js‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
function Array1DTracer(module) {
2+
return Array2DTracer.call(this, module || Array1DTracer);
3+
}
4+
5+
Array1DTracer.prototype = Object.create(Array2DTracer.prototype);
6+
Array1DTracer.prototype.constructor = Array1DTracer;
7+
8+
// Override
9+
Array1DTracer.prototype.createRandomData = function (N, min, max) {
10+
return Array2DTracer.prototype.createRandomData.call(this, 1, N, min, max)[0];
11+
};
12+
13+
// Override
14+
Array1DTracer.prototype.setData = function (D) {
15+
return Array2DTracer.prototype.setData.call(this, [D]);
16+
};
17+
18+
// Override
19+
Array1DTracer.prototype._change = function (s, e) {
20+
if (s instanceof Array) {
21+
this.pushStep({type: 'select', indexes: s, color: tableColor.changed}, true);
22+
this.pushStep({type: 'deselect', indexes: s}, false);
23+
} else if (e !== undefined) {
24+
this.pushStep({type: 'select', index: s, color: tableColor.changed}, true);
25+
this.pushStep({type: 'deselect', index: s}, false);
26+
} else {
27+
this.pushStep({type: 'select', s: s, e: e, color: tableColor.changed}, true);
28+
this.pushStep({type: 'deselect', s: s, e: e}, false);
29+
}
30+
};
31+
32+
// Override
33+
Array1DTracer.prototype._select = function (s, e) {
34+
if (s instanceof Array) {
35+
this.pushStep({type: 'select', indexes: s}, true);
36+
} else if (e !== undefined) {
37+
this.pushStep({type: 'select', index: s}, true);
38+
} else {
39+
this.pushStep({type: 'select', s: s, e: e}, true);
40+
}
41+
};
42+
43+
// Override
44+
Array1DTracer.prototype._deselect = function (s, e) {
45+
if (s instanceof Array) {
46+
this.pushStep({type: 'deselect', indexes: s}, true);
47+
} else if (e !== undefined) {
48+
this.pushStep({type: 'deselect', index: s}, true);
49+
} else {
50+
this.pushStep({type: 'deselect', s: s, e: e}, true);
51+
}
52+
};
53+
54+
// Override
55+
Array1DTracer.prototype.processStep = function (step, options) {
56+
switch (step.type) {
57+
case 'select':
58+
case 'deselect':
59+
var select = step.type == 'select';
60+
var color = select ? step.color !== undefined ? step.color : tableColor.selected : tableColor.default;
61+
if (step.indexes) {
62+
step.indexes.forEach(function (index) {
63+
paintColor(0, index, 0, index, color);
64+
});
65+
} else {
66+
var s = step.s;
67+
var e = step.e;
68+
if (s === undefined) s = step.index;
69+
if (e === undefined) e = step.index;
70+
paintColor(0, s, 0, e, color);
71+
}
72+
break;
73+
}
74+
};

‎js/module/array2d.js‎

Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,186 @@
1+
var $table = null;
2+
3+
function Array2DTracer(module) {
4+
if (Tracer.call(this, module || Array2DTracer)) {
5+
initTable();
6+
return true;
7+
}
8+
return false;
9+
}
10+
11+
Array2DTracer.prototype = Object.create(Tracer.prototype);
12+
Array2DTracer.prototype.constructor = Array2DTracer;
13+
14+
// Override
15+
Array2DTracer.prototype.resize = function () {
16+
Tracer.prototype.resize.call(this);
17+
18+
var $parent = $table.parent();
19+
$table.css('margin-top', $parent.height() / 2 - $table.height() / 2);
20+
};
21+
22+
// Override
23+
Array2DTracer.prototype.clear = function () {
24+
Tracer.prototype.clear.call(this);
25+
26+
clearTableColor();
27+
};
28+
29+
Array2DTracer.prototype.createRandomData = function (N, M, min, max) {
30+
if (!N) N = 10;
31+
if (!M) M = 10;
32+
if (min === undefined) min = 1;
33+
if (max === undefined) max = 9;
34+
var D = [];
35+
for (var i = 0; i < N; i++) {
36+
D.push([]);
37+
for (var j = 0; j < M; j++) {
38+
D[i].push((Math.random() * (max - min + 1) | 0) + min);
39+
}
40+
}
41+
return D;
42+
};
43+
44+
// Override
45+
Array2DTracer.prototype.setData = function (D) {
46+
if (Tracer.prototype.setData.call(this, arguments)) return true;
47+
48+
$table.empty();
49+
for (var i = 0; i < D.length; i++) {
50+
var $row = $('<div class="mtbl-row">');
51+
$table.append($row);
52+
for (var j = 0; j < D[i].length; j++) {
53+
var $cell = $('<div class="mtbl-cell">').text(D[i][j]);
54+
$row.append($cell);
55+
}
56+
}
57+
this.resize();
58+
59+
return false;
60+
};
61+
62+
Array2DTracer.prototype._change = function (sx, sy, ex, ey) {
63+
if (sx instanceof Array) {
64+
this.pushStep({type: 'select', coords: sx, color: tableColor.changed}, true);
65+
this.pushStep({type: 'deselect', coords: sx}, false);
66+
} else if (ex !== undefined && ey !== undefined) {
67+
this.pushStep({type: 'select', sx: sx, sy: sy, ex: ex, ey: ey, color: tableColor.changed}, true);
68+
this.pushStep({type: 'deselect', sx: sx, sy: sy, ex: ex, ey: ey}, false);
69+
} else {
70+
this.pushStep({type: 'select', x: sx, y: sy, color: tableColor.changed}, true);
71+
this.pushStep({type: 'deselect', x: sx, y: sy}, false);
72+
}
73+
};
74+
75+
Array2DTracer.prototype._changeRow = function (x, sy, ey) {
76+
this.pushStep({type: 'select', x: x, sy: sy, ey: ey, color: tableColor.changed}, true);
77+
this.pushStep({type: 'deselect', x: x, sy: sy, ey: ey}, false);
78+
};
79+
80+
Array2DTracer.prototype._changeCol = function (y, sx, ex) {
81+
this.pushStep({type: 'select', y: y, sx: sx, ex: ex, color: tableColor.changed}, true);
82+
this.pushStep({type: 'deselect', y: y, sx: sx, ex: ex}, false);
83+
};
84+
85+
Array2DTracer.prototype._select = function (sx, sy, ex, ey) {
86+
if (sx instanceof Array) {
87+
this.pushStep({type: 'select', coords: sx}, true);
88+
} else if (ex !== undefined && ey !== undefined) {
89+
this.pushStep({type: 'select', sx: sx, sy: sy, ex: ex, ey: ey}, true);
90+
} else {
91+
this.pushStep({type: 'select', x: sx, y: sy}, true);
92+
}
93+
};
94+
95+
Array2DTracer.prototype._selectRow = function (x, sy, ey) {
96+
this.pushStep({type: 'select', x: x, sy: sy, ey: ey}, true);
97+
};
98+
99+
Array2DTracer.prototype._selectCol = function (y, sx, ex) {
100+
this.pushStep({type: 'select', y: y, sx: sx, ex: ex}, true);
101+
};
102+
103+
Array2DTracer.prototype._deselect = function (sx, sy, ex, ey) {
104+
if (sx instanceof Array) {
105+
this.pushStep({type: 'deselect', coords: sx}, true);
106+
} else if (ex !== undefined && ey !== undefined) {
107+
this.pushStep({type: 'deselect', sx: sx, sy: sy, ex: ex, ey: ey}, true);
108+
} else {
109+
this.pushStep({type: 'deselect', x: sx, y: sy}, true);
110+
}
111+
};
112+
113+
Array2DTracer.prototype._deselectRow = function (x, sy, ey) {
114+
this.pushStep({type: 'deselect', x: x, sy: sy, ey: ey}, true);
115+
};
116+
117+
Array2DTracer.prototype._deselectCol = function (y, sx, ex) {
118+
this.pushStep({type: 'deselect', y: y, sx: sx, ex: ex}, true);
119+
};
120+
121+
Array2DTracer.prototype.processStep = function (step, options) {
122+
switch (step.type) {
123+
case 'select':
124+
case 'deselect':
125+
var select = step.type == 'select';
126+
var color = select ? step.color !== undefined ? step.color : tableColor.selected : tableColor.default;
127+
if (step.coords) {
128+
step.coords.forEach(function (coord) {
129+
var x = coord.x;
130+
var y = coord.y;
131+
paintColor(x, y, x, y, color);
132+
});
133+
} else {
134+
var sx = step.sx;
135+
var sy = step.sy;
136+
var ex = step.ex;
137+
var ey = step.ey;
138+
if (sx === undefined) sx = step.x;
139+
if (sy === undefined) sy = step.y;
140+
if (ex === undefined) ex = step.x;
141+
if (ey === undefined) ey = step.y;
142+
paintColor(sx, sy, ex, ey, color);
143+
}
144+
break;
145+
}
146+
};
147+
148+
// Override
149+
Array2DTracer.prototype.prevStep = function () {
150+
this.clear();
151+
$('#tab_trace .wrapper').empty();
152+
var finalIndex = this.traceIndex - 1;
153+
if (finalIndex < 0) {
154+
this.traceIndex = -1;
155+
return;
156+
}
157+
for (var i = 0; i < finalIndex; i++) {
158+
this.step(i, {virtual: true});
159+
}
160+
this.step(finalIndex);
161+
};
162+
163+
var initTable = function () {
164+
$('.module_container').empty();
165+
$table = $('<div class="mtbl-table">');
166+
$('.module_container').append($table);
167+
};
168+
169+
var tableColor = {
170+
selected: '#0ff',
171+
changed: '#f00',
172+
default: ''
173+
};
174+
175+
var paintColor = function (sx, sy, ex, ey, color) {
176+
for (var i = sx; i <= ex; i++) {
177+
var $row = $table.find('.mtbl-row').eq(i);
178+
for (var j = sy; j <= ey; j++) {
179+
$row.find('.mtbl-cell').eq(j).css('background', color);
180+
}
181+
}
182+
};
183+
184+
var clearTableColor = function () {
185+
$table.find('.mtbl-cell').css('background', '');
186+
};

0 commit comments

Comments
 (0)