· 10 years ago · Jan 23, 2016, 11:39 AM
1/**
2 *
3 * Provides a stable dedupelication function for a list of items
4 *
5 */
6var Dedupe = (function() {
7
8 var dedupe = {};
9 var _root = null;
10
11 /**
12 * Removes duplicate items from the input array
13 * in a new array, while preserving the origional ordering
14 * Note: Keeps the first occurrence of any duplicate item
15 */
16 dedupe.clean = function(arr) {
17 var i, test;
18 var result = [];
19
20 // Clear tree from previous run
21 _root = null;
22
23 for (i in arr) {
24 if(_add(arr[i])) {
25 result.push(arr[i]);
26 }
27 }
28
29 return result;
30 }
31
32 /**
33 * Attempt to add the value to the tree of items.
34 * Returns true if the item was not already in the tree, false otherwise
35 */
36 _add = function(val) {
37 var current;
38
39 // Create new node
40 var newNode = {
41 data: val,
42 left: null,
43 right: null
44 };
45
46 // If the tree is empty, add the node to the root
47 if(!_root) {
48 _root = newNode;
49 return true;
50 }
51
52 // Use helper function to add node
53 return _addHelper(_root, newNode);
54 }
55
56 /**
57 * Use recursion to try and add the node to the list
58 */
59 _addHelper = function(root, node) {
60 if (root.data === node.data) {
61 // Duplicate found
62 return false;
63 }
64
65 // Add to left sub-tree
66 if(node.data < root.data) {
67 if(!root.left) {
68 root.left = node;
69 return true;
70 }
71 return _addHelper(root.left, node);
72 }
73
74 // Add to right sub-tree
75 if(!root.right) {
76 root.right = node;
77 return true;
78 }
79 return _addHelper(root.right, node);
80 }
81
82 return dedupe;
83
84})();
85
86/**
87 *
88 * Module to generate test data for this example
89 * Can create a random list of numbers or email addresses
90 *
91 */
92var Generator = (function() {
93 var generator = {};
94
95 /**
96 * Return a list of random numbers
97 *
98 * Param: num - the number of items to generate
99 * Return: A suffled list of random numbers
100 */
101 generator.getNumbers = function(num, dupPercent) {
102 var result = [], i, numDups, numOrig;
103
104 numDups = Math.ceil(num * dupPercent);
105 numOrig = Math.ceil(num - numDups);
106
107 for (i = 0; i < numOrig; i++) {
108 result.push(i);
109 }
110
111 for (i = 0; i < numDups; i++) {
112 result.push(result[i]);
113 }
114
115 return _shuffle(result);
116 }
117
118 /**
119 * Return a list of random email addresses
120 *
121 * Param: num - the number of items to generate
122 * Return: A suffled list of random email addresses
123 */
124 generator.getAddresses = function(num, percent) {
125 var result = [], i, numDups, numOrig;
126
127 numDups = Math.ceil(num * percent);
128 numOrig = Math.ceil(num - numDups);
129
130 for(i = 0; i < numOrig; i++) {
131 result.push(_createAddress());
132 }
133
134 for(i = 0; i < numDups; i++) {
135 result.push(result[i]);
136 }
137
138 return _shuffle(result);
139 }
140
141 /**
142 * Generate a random email name, and pick a random domain to go with it
143 */
144 _createAddress = function() {
145 var domains = ['@gmail.com', '@hotmail.com', '@yahoo.com', '@aol.com', '@chefsteps.com'];
146 var letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
147 var i, name = '', domainIdx;
148
149 for(i = 0; i < 7; i++) {
150 name = name + letters[_getRandomNumber(0, 25)];
151 }
152
153 domainIdx = _getRandomNumber(0, 4);
154
155 return name + domains[domainIdx];
156 }
157
158 /**
159 * Get a random number between min and max (inclusive)
160 */
161 _getRandomNumber = function(min, max) {
162 return Math.floor(Math.random() * (max - min + 1)) + min;
163 }
164
165 /**
166 * Shuffle the list of numbers to distribute duplicates.
167 * Uses the Fisher-Yates shuffle algorithm
168 */
169 _shuffle = function(arr) {
170 var i, tmp, rand;
171
172 for(i = arr.length - 1; i > 0; i--) {
173 rand = _getRandomNumber(0, i);
174 tmp = arr[i];
175 arr[i] = arr[rand];
176 arr[rand] = tmp;
177 }
178
179 return arr;
180 }
181
182 return generator;
183})();
184
185/**
186 *
187 * Module to provide application functionality
188 *
189 */
190var App = (function($) {
191 var app = {},
192 resultTemplate,
193 msgTemplate;
194
195 /**
196 * Initialize the click handler on the button
197 */
198 app.init = function() {
199 $('#go').on('click', _run);
200 }
201
202 /**
203 * Go button entry point
204 * Does some basic error checking and starts the generation
205 * and dedupelication process.
206 */
207 _run = function() {
208 var numStr = $('#number').val();
209 var filter = new RegExp(',', 'g');
210 numStr = numStr.replace(filter, '');
211
212 var number = parseInt(numStr, 10);
213 var percent = parseFloat($('#percent').val());
214
215 // Close any existing alert or results
216 $('.alert').alert('close');
217 $('#result').remove();
218
219 // Sanity checks
220 if(isNaN(number)) {
221 _showError('Invalid Number.');
222 } else if (isNaN(percent)) {
223 _showError('Invalid Percent.');
224 } else if (number < 1 || number > 100000) {
225 _showError('Number out of range 1 <= number <= 100,000.');
226 } else if (percent < .1 || percent > .5) {
227 _showError('Percent out of range .1 <= percent <= .5');
228 }
229
230 _dedupe(number, percent);
231 }
232
233 /**
234 * Display the specified error message to the user
235 */
236 _showError = function(message) {
237 var tmpl = Handlebars.compile($('#error-msg-template').html());
238
239 $('#form').prepend(tmpl({msg: message}));
240 }
241
242 /**
243 * Performs the work of generating the data, removing the duplicates,
244 * and records the stats for the output.
245 */
246 _dedupe = function(num, percent) {
247 var context = {
248 input: [],
249 output: [],
250 stats: {
251 inSize: 0,
252 outSize: 0,
253 time: 0
254 }
255 };
256
257 var t0, t1, itemType;
258
259 itemType = $('option').filter(':selected').val();
260
261 if(itemType === 'email') {
262 context.input = Generator.getAddresses(num, percent);
263 } else if (itemType === 'number') {
264 context.input = Generator.getNumbers(num, percent);
265 } else {
266 _showError('Invalid item type.');
267 return;
268 }
269
270 context.stats.inSize = context.input.length;
271
272 // Record the time it takes to remove duplicates
273 t0 = performance.now();
274 context.output = Dedupe.clean(context.input);
275 t1 = performance.now();
276
277 context.stats.outSize = context.output.length;
278 context.stats.time = (t1 - t0) / 1000.0
279
280 _printResult(context);
281 }
282
283 /**
284 * Show the results to the user
285 */
286 _printResult = function(data) {
287 var tmpl = Handlebars.compile($('#result-template').html());
288
289 $('#form').after(tmpl(data));
290 }
291
292 return app;
293
294})(jQuery);
295
296// Start this thang
297App.init();