OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 | 5 |
6 (function(exports) { | 6 (function(exports) { |
7 /** | 7 /** |
8 * Orientation of a line. | 8 * Orientation of a line. |
9 * @enum {boolean} | 9 * @enum {boolean} |
10 */ | 10 */ |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
64 * @param {number} x The x-coordinate. | 64 * @param {number} x The x-coordinate. |
65 * @param {number} y The y-coordinate. | 65 * @param {number} y The y-coordinate. |
66 * @return {?kb-key} The key, or null if none found. | 66 * @return {?kb-key} The key, or null if none found. |
67 */ | 67 */ |
68 findClosestKey: function(x, y) { | 68 findClosestKey: function(x, y) { |
69 var closestNode = this.tree.findClosestNode(x, y); | 69 var closestNode = this.tree.findClosestNode(x, y); |
70 var key = closestNode.data; | 70 var key = closestNode.data; |
71 if (!key) | 71 if (!key) |
72 return; | 72 return; |
73 // Ignore touches that aren't close. | 73 // Ignore touches that aren't close. |
74 return key.distanceTo(x,y) <= MAX_TOUCH_FUZZ_DISTANCE ? | 74 return key.distanceTo(x, y) <= MAX_TOUCH_FUZZ_DISTANCE ? |
75 key.key : null; | 75 key.key : null; |
76 }, | 76 }, |
77 | 77 |
78 /** | 78 /** |
79 * Returns the position data of all keys in this keyset. | 79 * Returns the position data of all keys in this keyset. |
80 * @return {Array<Map>} | 80 * @return {Array<Map>} |
81 */ | 81 */ |
82 getLayout: function() { | 82 getLayout: function() { |
83 return this.keys.map(function(key) { | 83 return this.keys.map(function(key) { |
84 return key.toMap(); | 84 return key.toMap(); |
85 }); | 85 }); |
86 }, | 86 }, |
87 }; | 87 }; |
88 | 88 |
89 /** | 89 /** |
90 * Container for caching a key's data. | 90 * Container for caching a key's data. |
91 * @param {Object} key The key to cache. | 91 * @param {{style: {left: number, top: number, width: number, |
92 * @param {number} left The x-coordinate of the left edge of the key. | 92 * height: number}}} key The key to cache. |
93 * @param {number} top The y-coordinate of the top edge of the key. | 93 * left: The x-coordinate of the left edge of the key. |
94 * @param {number} width The width of the key in px. | 94 * top: The y-coordinate of the top edge of the key. |
95 * @param {number} height The height of the key in px. | 95 * width: The width of the key in px. |
| 96 * height: The height of the key in px. |
| 97 * @constructor |
96 */ | 98 */ |
97 var Key = function(key) { | 99 var Key = function(key) { |
98 this.key = key; | 100 this.key = key; |
99 var style = key.style; | 101 var style = key.style; |
100 this.top = parseFloat(style.top) - KEY_PADDING_TOP; | 102 this.top = parseFloat(style.top) - KEY_PADDING_TOP; |
101 this.left = parseFloat(style.left); | 103 this.left = parseFloat(style.left); |
102 this.right = this.left + parseFloat(style.width); | 104 this.right = this.left + parseFloat(style.width); |
103 this.bottom = this.top + parseFloat(style.height) + KEY_PADDING_TOP | 105 this.bottom = this.top + parseFloat(style.height) + KEY_PADDING_TOP |
104 + KEY_PADDING_BOTTOM; | 106 + KEY_PADDING_BOTTOM; |
105 } | 107 } |
106 | 108 |
107 Key.prototype = { | 109 Key.prototype = { |
108 /** | 110 /** |
109 * Manhattan distance from the the provided point to the key. | 111 * Manhattan distance from the the provided point to the key. |
110 * @param {number} x The x-coordinate of the point. | 112 * @param {number} x The x-coordinate of the point. |
111 * @param {number} y The y-coordinate of the point. | 113 * @param {number} y The y-coordinate of the point. |
112 * @return {number}. | 114 * @return {number} |
113 */ | 115 */ |
114 distanceTo: function (x, y) { | 116 distanceTo: function(x, y) { |
115 return Math.abs(this.intersect(new Line(x))) + | 117 return Math.abs(this.intersect(new Line(x))) + |
116 Math.abs(this.intersect(new Line(y, true))); | 118 Math.abs(this.intersect(new Line(y, true))); |
117 }, | 119 }, |
118 | 120 |
119 /** | 121 /** |
120 * Checks whether the key intersects with the line provided. | 122 * Checks whether the key intersects with the line provided. |
121 * @param {!Line} line The line. | 123 * @param {!Line} line The line. |
122 * @return {number} Zero if it intersects, signed manhattan distance if it | 124 * @return {number} Zero if it intersects, signed manhattan distance if it |
123 * does not. | 125 * does not. |
124 */ | 126 */ |
(...skipping 12 matching lines...) Expand all Loading... |
137 'x': this.left, | 139 'x': this.left, |
138 'y': this.top, | 140 'y': this.top, |
139 'width': this.right - this.left, | 141 'width': this.right - this.left, |
140 'height': this.bottom - this.bottom, | 142 'height': this.bottom - this.bottom, |
141 } | 143 } |
142 }, | 144 }, |
143 }; | 145 }; |
144 | 146 |
145 /** | 147 /** |
146 * Object representing the line y = c or x = c. | 148 * Object representing the line y = c or x = c. |
147 * @param {number} The x or y coordinate of the intersection line depending on | 149 * @param {number} c The x or y coordinate of the intersection line depending |
148 * on orientation. | 150 * on orientation. |
149 * @param {Orientation} orientation The orientation of the line. | 151 * @param {Orientation} orientation The orientation of the line. |
| 152 * @constructor |
150 */ | 153 */ |
151 var Line = function(c, orientation) { | 154 var Line = function(c, orientation) { |
152 this.c = c; | 155 this.c = c; |
153 this.rotated = orientation; | 156 this.rotated = orientation; |
154 }; | 157 }; |
155 | 158 |
156 Line.prototype = { | 159 Line.prototype = { |
157 /** | 160 /** |
158 * The position of the provided point in relation to the line. | 161 * The position of the provided point in relation to the line. |
159 * @param {number} x The x-coordinate of the point. | 162 * @param {number} x The x-coordinate of the point. |
160 * @param {number} y The y-coordinate of the point. | 163 * @param {number} y The y-coordinate of the point. |
161 * @return {number} Zero if they intersect, negative if the point is before | 164 * @return {number} Zero if they intersect, negative if the point is before |
162 * the line, positive if it's after. | 165 * the line, positive if it's after. |
163 */ | 166 */ |
164 testPoint: function (x, y) { | 167 testPoint: function(x, y) { |
165 var c = this.rotated ? y : x; | 168 var c = this.rotated ? y : x; |
166 return this.c == c ? 0 : c - this.c; | 169 return this.c == c ? 0 : c - this.c; |
167 }, | 170 }, |
168 | 171 |
169 test: function (key) { | 172 test: function(key) { |
170 // Key already provides an intersect method. If the key is to the right of | 173 // Key already provides an intersect method. If the key is to the right of |
171 // the line, then the line is to the left of the key. | 174 // the line, then the line is to the left of the key. |
172 return -1 * key.intersect(this); | 175 return -1 * key.intersect(this); |
173 }, | 176 }, |
174 }; | 177 }; |
175 | 178 |
176 /** | 179 /** |
177 * A node used to split 2D space. | 180 * A node used to split 2D space. |
178 * @param {Line} The line to split the space with. | 181 * @param {Line} line The line to split the space with. |
| 182 * @constructor |
179 */ | 183 */ |
180 var DecisionNode = function(line) { | 184 var DecisionNode = function(line) { |
181 this.decision = line; | 185 this.decision = line; |
182 }; | 186 }; |
183 | 187 |
184 DecisionNode.prototype = { | 188 DecisionNode.prototype = { |
185 /** | 189 /** |
186 * The test whether to proceed in the left or right branch. | 190 * The test whether to proceed in the left or right branch. |
187 * @type {Line} | 191 * @type {Line} |
188 */ | 192 */ |
(...skipping 11 matching lines...) Expand all Loading... |
200 */ | 204 */ |
201 pass: undefined, | 205 pass: undefined, |
202 | 206 |
203 /** | 207 /** |
204 * Finds the node closest to the point provided. | 208 * Finds the node closest to the point provided. |
205 * @param {number} x The x-coordinate. | 209 * @param {number} x The x-coordinate. |
206 * @param {number} y The y-coordinate. | 210 * @param {number} y The y-coordinate. |
207 * @return {DecisionNode | LeafNode} | 211 * @return {DecisionNode | LeafNode} |
208 */ | 212 */ |
209 findClosestNode: function(x, y) { | 213 findClosestNode: function(x, y) { |
210 return this.search(function(node){ | 214 return this.search(function(node) { |
211 return node.decision.testPoint(x,y) >= 0; | 215 return node.decision.testPoint(x, y) >= 0; |
212 }); | 216 }); |
213 }, | 217 }, |
214 | 218 |
215 /** | 219 /** |
216 * Populates the decision tree with elements. | 220 * Populates the decision tree with elements. |
217 * @param {Array{Key}} The child elements. | 221 * @param {Array{Key}} The child elements. |
218 */ | 222 */ |
219 populate: function(data) { | 223 populate: function(data) { |
220 if (!data.length) | 224 if (!data.length) |
221 return; | 225 return; |
222 var pass = []; | 226 var pass = []; |
223 var fail = []; | 227 var fail = []; |
224 for (var i = 0; i< data.length; i++) { | 228 for (var i = 0; i < data.length; i++) { |
225 var result = this.decision.test(data[i]); | 229 var result = this.decision.test(data[i]); |
226 // Add to both branches if result == 0. | 230 // Add to both branches if result == 0. |
227 if (result >= 0) | 231 if (result >= 0) |
228 pass.push(data[i]); | 232 pass.push(data[i]); |
229 if (result <= 0) | 233 if (result <= 0) |
230 fail.push(data[i]); | 234 fail.push(data[i]); |
231 } | 235 } |
232 var currentRotation = this.decision.rotated; | 236 var currentRotation = this.decision.rotated; |
233 /** | 237 /** |
234 * Splits the tree further such that each leaf has exactly one data point. | 238 * Splits the tree further such that each leaf has exactly one data point. |
235 * @param {Array} array The data points. | 239 * @param {Array} array The data points. |
236 * @return {DecisionNode | LeafNode} The new branch for the tree. | 240 * @return {DecisionNode | LeafNode} The new branch for the tree. |
237 */ | 241 */ |
238 var updateBranch = function(array) { | 242 var updateBranch = function(array) { |
239 if (array.length == 1) { | 243 if (array.length == 1) { |
240 return new LeafNode(array[0]); | 244 return new LeafNode(array[0]); |
241 } else { | 245 } else { |
242 var splits = findSplits(array, !currentRotation) | 246 var splits = findSplits(array, !currentRotation); |
243 var tree = createBinaryTree(0, splits.length - 1, splits); | 247 var tree = createBinaryTree(0, splits.length - 1, splits); |
244 tree.populate(array); | 248 tree.populate(array); |
245 return tree; | 249 return tree; |
246 } | 250 } |
247 }; | 251 }; |
248 // All elements that passed the decision test. | 252 // All elements that passed the decision test. |
249 if (pass.length > 0) { | 253 if (pass.length > 0) { |
250 if (this.pass) | 254 if (this.pass) |
251 this.pass.populate(pass); | 255 this.pass.populate(pass); |
252 else | 256 else |
253 this.pass = updateBranch(pass); | 257 this.pass = updateBranch(pass); |
254 } | 258 } |
255 // All elements that failed the decision test. | 259 // All elements that failed the decision test. |
256 if (fail.length > 0) { | 260 if (fail.length > 0) { |
257 if (this.fail) | 261 if (this.fail) |
258 this.fail.populate(fail); | 262 this.fail.populate(fail); |
259 else | 263 else |
260 this.fail = updateBranch(fail); | 264 this.fail = updateBranch(fail); |
261 } | 265 } |
262 }, | 266 }, |
263 | 267 |
264 /** | 268 /** |
265 * Searches for the first leaf that matches the search function. | 269 * Searches for the first leaf that matches the search function. |
266 * @param {Function<DecisionNode>: Boolean} searchFn The function used to | 270 * @param {Function<DecisionNode>: Boolean} searchFn The function used to |
267 * determine whether to search in the left or right subtree. | 271 * determine whether to search in the left or right subtree. |
268 * @param {DecisionNode | LeafNode} The node that most closely matches the | 272 * @return {DecisionNode | LeafNode} The node that most closely matches the |
269 * search parameters. | 273 * search parameters. |
270 */ | 274 */ |
271 search: function(searchFn) { | 275 search: function(searchFn) { |
272 if (searchFn(this)) { | 276 if (searchFn(this)) { |
273 return this.pass ? this.pass.search(searchFn) : this; | 277 return this.pass ? this.pass.search(searchFn) : this; |
274 } | 278 } |
275 return this.fail ? this.fail.search(searchFn) : this; | 279 return this.fail ? this.fail.search(searchFn) : this; |
276 }, | 280 }, |
277 | 281 |
278 /** | 282 /** |
279 * Tests whether the key belongs in the left or right branch of this node. | 283 * Tests whether the key belongs in the left or right branch of this node. |
280 * @param {Key} key The key being tested. | 284 * @param {Key} key The key being tested. |
281 * @return {boolean} Whether it belongs in the right branch. | 285 * @return {boolean} Whether it belongs in the right branch. |
282 */ | 286 */ |
283 test: function(key) { | 287 test: function(key) { |
284 return this.decision.testKey(key) | 288 return this.decision.testKey(key); |
285 }, | 289 }, |
286 }; | 290 }; |
287 | 291 |
288 /** | 292 /** |
289 * Structure representing a leaf in the decision tree. It contains a single | 293 * Structure representing a leaf in the decision tree. It contains a single |
290 * data point. | 294 * data point. |
291 */ | 295 */ |
292 var LeafNode = function(data) { | 296 var LeafNode = function(data) { |
293 this.data = data; | 297 this.data = data; |
294 }; | 298 }; |
(...skipping 16 matching lines...) Expand all Loading... |
311 return; | 315 return; |
312 var midpoint = Math.floor((end + start)/2); | 316 var midpoint = Math.floor((end + start)/2); |
313 var root = new DecisionNode(nodes[midpoint]); | 317 var root = new DecisionNode(nodes[midpoint]); |
314 root.fail = createBinaryTree(start, midpoint - 1, nodes); | 318 root.fail = createBinaryTree(start, midpoint - 1, nodes); |
315 root.pass = createBinaryTree(midpoint + 1, end, nodes); | 319 root.pass = createBinaryTree(midpoint + 1, end, nodes); |
316 return root; | 320 return root; |
317 }; | 321 }; |
318 | 322 |
319 /** | 323 /** |
320 * Calculates the optimum split points on the specified axis. | 324 * Calculates the optimum split points on the specified axis. |
321 * @param {Array<Keys>} allKeys All keys in the keyset. | 325 * @param {Array.<Keys>} allKeys All keys in the keyset. |
322 * @param {Partition=} axis Whether to split on the y-axis instead. | 326 * @param {Orientation} orientation Whether to split on the y-axis instead. |
323 * @return {Array<Line>} The optimum split points. | 327 * @return {Array.<Line>} The optimum split points. |
324 */ | 328 */ |
325 var findSplits = function(allKeys, orientation) { | 329 var findSplits = function(allKeys, orientation) { |
326 /** | 330 /** |
327 * Returns the minimum edge on the key. | 331 * Returns the minimum edge on the key. |
328 * @param {Key} The key. | 332 * @param {Key} key The key. |
329 * @return {number} | 333 * @return {number} |
330 */ | 334 */ |
331 var getMin = function(key) { | 335 var getMin = function(key) { |
332 return orientation == Orientation.HORIZONTAL ? key.top : key.left; | 336 return orientation == Orientation.HORIZONTAL ? key.top : key.left; |
333 }; | 337 }; |
334 | 338 |
335 /** | 339 /** |
336 * Returns the maximum edge on the key. | 340 * Returns the maximum edge on the key. |
337 * @param {Key} The key. | 341 * @param {Key} key The key. |
338 */ | 342 */ |
339 var getMax = function(key) { | 343 var getMax = function(key) { |
340 return orientation == Orientation.HORIZONTAL ? key.bottom : key.right; | 344 return orientation == Orientation.HORIZONTAL ? key.bottom : key.right; |
341 }; | 345 }; |
342 | 346 |
343 /** | 347 /** |
344 * Returns a duplicate free version of array. | 348 * Returns a duplicate free version of array. |
345 * @param {Array} array A sorted array. | 349 * @param {Array} array A sorted array. |
346 * @return {Array} Sorted array without duplicates. | 350 * @return {Array} Sorted array without duplicates. |
347 */ | 351 */ |
(...skipping 92 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
440 * @param{!String} id The id of the keyset. | 444 * @param{!String} id The id of the keyset. |
441 * @private | 445 * @private |
442 */ | 446 */ |
443 var getKeysetLayout_ = function(id) { | 447 var getKeysetLayout_ = function(id) { |
444 return layouts[id]; | 448 return layouts[id]; |
445 }; | 449 }; |
446 | 450 |
447 exports.getKeysetLayout = getKeysetLayout_; | 451 exports.getKeysetLayout = getKeysetLayout_; |
448 exports.recordKeysets = recordKeysets_; | 452 exports.recordKeysets = recordKeysets_; |
449 })(this); | 453 })(this); |
OLD | NEW |