| 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 |