| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 | |
| 6 (function(exports) { | |
| 7 /** | |
| 8 * Orientation of a line. | |
| 9 * @enum {boolean} | |
| 10 */ | |
| 11 var Orientation = { | |
| 12 VERTICAL: false, | |
| 13 HORIZONTAL: true | |
| 14 } | |
| 15 | |
| 16 /** | |
| 17 * Map from keysetId to layout. | |
| 18 * @type {Map<String,KeysetLayout>} | |
| 19 * @private | |
| 20 */ | |
| 21 var layouts = {}; | |
| 22 | |
| 23 /** | |
| 24 * Container for storing a keyset's layout. | |
| 25 */ | |
| 26 var KeysetLayout = function() { | |
| 27 this.keys = []; | |
| 28 } | |
| 29 | |
| 30 KeysetLayout.prototype = { | |
| 31 /** | |
| 32 * All keys in the keyset. | |
| 33 * @type {Array<Key>} | |
| 34 */ | |
| 35 keys: undefined, | |
| 36 | |
| 37 /** | |
| 38 * Spacial partitioning of all keys in the keyset. | |
| 39 * @type {DecisionNode} | |
| 40 */ | |
| 41 tree: undefined, | |
| 42 | |
| 43 /** | |
| 44 * Add a key to the keyset. | |
| 45 */ | |
| 46 add: function(key) { | |
| 47 this.keys.push(key); | |
| 48 }, | |
| 49 | |
| 50 /** | |
| 51 * Regenerates a decision tree using the keys in the keyset. | |
| 52 */ | |
| 53 regenerateTree: function() { | |
| 54 // Split using horizontal lines first, as keyboards tend to be | |
| 55 // row-centric. | |
| 56 var splits = findSplits(this.keys, Orientation.HORIZONTAL); | |
| 57 this.tree = createBinaryTree(0, splits.length - 1, splits); | |
| 58 if (this.tree) | |
| 59 this.tree.populate(this.keys); | |
| 60 }, | |
| 61 | |
| 62 /** | |
| 63 * Searches the tree for the key closest to the point provided. | |
| 64 * @param {number} x The x-coordinate. | |
| 65 * @param {number} y The y-coordinate. | |
| 66 * @return {?kb-key} The key, or null if none found. | |
| 67 */ | |
| 68 findClosestKey: function(x, y) { | |
| 69 var closestNode = this.tree.findClosestNode(x, y); | |
| 70 var key = closestNode.data; | |
| 71 if (!key) | |
| 72 return; | |
| 73 // Ignore touches that aren't close. | |
| 74 return key.distanceTo(x, y) <= MAX_TOUCH_FUZZ_DISTANCE ? | |
| 75 key.key : null; | |
| 76 }, | |
| 77 | |
| 78 /** | |
| 79 * Returns the position data of all keys in this keyset. | |
| 80 * @return {Array<Map>} | |
| 81 */ | |
| 82 getLayout: function() { | |
| 83 return this.keys.map(function(key) { | |
| 84 return key.toMap(); | |
| 85 }); | |
| 86 }, | |
| 87 }; | |
| 88 | |
| 89 /** | |
| 90 * Container for caching a key's data. | |
| 91 * @param {{style: {left: number, top: number, width: number, | |
| 92 * height: number}}} key The key to cache. | |
| 93 * left: The x-coordinate of the left edge of the key. | |
| 94 * top: The y-coordinate of the top edge of the key. | |
| 95 * width: The width of the key in px. | |
| 96 * height: The height of the key in px. | |
| 97 * @constructor | |
| 98 */ | |
| 99 var Key = function(key) { | |
| 100 this.key = key; | |
| 101 var style = key.style; | |
| 102 this.top = parseFloat(style.top) - KEY_PADDING_TOP; | |
| 103 this.left = parseFloat(style.left); | |
| 104 this.right = this.left + parseFloat(style.width); | |
| 105 this.bottom = this.top + parseFloat(style.height) + KEY_PADDING_TOP | |
| 106 + KEY_PADDING_BOTTOM; | |
| 107 } | |
| 108 | |
| 109 Key.prototype = { | |
| 110 /** | |
| 111 * Manhattan distance from the the provided point to the key. | |
| 112 * @param {number} x The x-coordinate of the point. | |
| 113 * @param {number} y The y-coordinate of the point. | |
| 114 * @return {number} | |
| 115 */ | |
| 116 distanceTo: function(x, y) { | |
| 117 return Math.abs(this.intersect(new Line(x))) + | |
| 118 Math.abs(this.intersect(new Line(y, true))); | |
| 119 }, | |
| 120 | |
| 121 /** | |
| 122 * Checks whether the key intersects with the line provided. | |
| 123 * @param {!Line} line The line. | |
| 124 * @return {number} Zero if it intersects, signed manhattan distance if it | |
| 125 * does not. | |
| 126 */ | |
| 127 intersect: function(line) { | |
| 128 var min = line.rotated ? this.top : this.left; | |
| 129 var max = line.rotated ? this.bottom : this.right; | |
| 130 return (line.c > max) ? line.c - max : Math.min(0, line.c - min); | |
| 131 }, | |
| 132 | |
| 133 /** | |
| 134 * Returns the Key as a map. | |
| 135 * @return {Map<String,number>} | |
| 136 */ | |
| 137 toMap: function() { | |
| 138 return { | |
| 139 'x': this.left, | |
| 140 'y': this.top, | |
| 141 'width': this.right - this.left, | |
| 142 'height': this.bottom - this.bottom, | |
| 143 } | |
| 144 }, | |
| 145 }; | |
| 146 | |
| 147 /** | |
| 148 * Object representing the line y = c or x = c. | |
| 149 * @param {number} c The x or y coordinate of the intersection line depending | |
| 150 * on orientation. | |
| 151 * @param {Orientation} orientation The orientation of the line. | |
| 152 * @constructor | |
| 153 */ | |
| 154 var Line = function(c, orientation) { | |
| 155 this.c = c; | |
| 156 this.rotated = orientation; | |
| 157 }; | |
| 158 | |
| 159 Line.prototype = { | |
| 160 /** | |
| 161 * The position of the provided point in relation to the line. | |
| 162 * @param {number} x The x-coordinate of the point. | |
| 163 * @param {number} y The y-coordinate of the point. | |
| 164 * @return {number} Zero if they intersect, negative if the point is before | |
| 165 * the line, positive if it's after. | |
| 166 */ | |
| 167 testPoint: function(x, y) { | |
| 168 var c = this.rotated ? y : x; | |
| 169 return this.c == c ? 0 : c - this.c; | |
| 170 }, | |
| 171 | |
| 172 test: function(key) { | |
| 173 // Key already provides an intersect method. If the key is to the right of | |
| 174 // the line, then the line is to the left of the key. | |
| 175 return -1 * key.intersect(this); | |
| 176 }, | |
| 177 }; | |
| 178 | |
| 179 /** | |
| 180 * A node used to split 2D space. | |
| 181 * @param {Line} line The line to split the space with. | |
| 182 * @constructor | |
| 183 */ | |
| 184 var DecisionNode = function(line) { | |
| 185 this.decision = line; | |
| 186 }; | |
| 187 | |
| 188 DecisionNode.prototype = { | |
| 189 /** | |
| 190 * The test whether to proceed in the left or right branch. | |
| 191 * @type {Line} | |
| 192 */ | |
| 193 decision: undefined, | |
| 194 | |
| 195 /** | |
| 196 * The branch for nodes that failed the decision test. | |
| 197 * @type {?DecisionNode} | |
| 198 */ | |
| 199 fail: undefined, | |
| 200 | |
| 201 /** | |
| 202 * The branch for nodes that passed the decision test. | |
| 203 * @type {?DecisionNode} | |
| 204 */ | |
| 205 pass: undefined, | |
| 206 | |
| 207 /** | |
| 208 * Finds the node closest to the point provided. | |
| 209 * @param {number} x The x-coordinate. | |
| 210 * @param {number} y The y-coordinate. | |
| 211 * @return {DecisionNode | LeafNode} | |
| 212 */ | |
| 213 findClosestNode: function(x, y) { | |
| 214 return this.search(function(node) { | |
| 215 return node.decision.testPoint(x, y) >= 0; | |
| 216 }); | |
| 217 }, | |
| 218 | |
| 219 /** | |
| 220 * Populates the decision tree with elements. | |
| 221 * @param {Array{Key}} The child elements. | |
| 222 */ | |
| 223 populate: function(data) { | |
| 224 if (!data.length) | |
| 225 return; | |
| 226 var pass = []; | |
| 227 var fail = []; | |
| 228 for (var i = 0; i < data.length; i++) { | |
| 229 var result = this.decision.test(data[i]); | |
| 230 // Add to both branches if result == 0. | |
| 231 if (result >= 0) | |
| 232 pass.push(data[i]); | |
| 233 if (result <= 0) | |
| 234 fail.push(data[i]); | |
| 235 } | |
| 236 var currentRotation = this.decision.rotated; | |
| 237 /** | |
| 238 * Splits the tree further such that each leaf has exactly one data point. | |
| 239 * @param {Array} array The data points. | |
| 240 * @return {DecisionNode | LeafNode} The new branch for the tree. | |
| 241 */ | |
| 242 var updateBranch = function(array) { | |
| 243 if (array.length == 1) { | |
| 244 return new LeafNode(array[0]); | |
| 245 } else { | |
| 246 var splits = findSplits(array, !currentRotation); | |
| 247 var tree = createBinaryTree(0, splits.length - 1, splits); | |
| 248 tree.populate(array); | |
| 249 return tree; | |
| 250 } | |
| 251 }; | |
| 252 // All elements that passed the decision test. | |
| 253 if (pass.length > 0) { | |
| 254 if (this.pass) | |
| 255 this.pass.populate(pass); | |
| 256 else | |
| 257 this.pass = updateBranch(pass); | |
| 258 } | |
| 259 // All elements that failed the decision test. | |
| 260 if (fail.length > 0) { | |
| 261 if (this.fail) | |
| 262 this.fail.populate(fail); | |
| 263 else | |
| 264 this.fail = updateBranch(fail); | |
| 265 } | |
| 266 }, | |
| 267 | |
| 268 /** | |
| 269 * Searches for the first leaf that matches the search function. | |
| 270 * @param {Function<DecisionNode>: Boolean} searchFn The function used to | |
| 271 * determine whether to search in the left or right subtree. | |
| 272 * @return {DecisionNode | LeafNode} The node that most closely matches the | |
| 273 * search parameters. | |
| 274 */ | |
| 275 search: function(searchFn) { | |
| 276 if (searchFn(this)) { | |
| 277 return this.pass ? this.pass.search(searchFn) : this; | |
| 278 } | |
| 279 return this.fail ? this.fail.search(searchFn) : this; | |
| 280 }, | |
| 281 | |
| 282 /** | |
| 283 * Tests whether the key belongs in the left or right branch of this node. | |
| 284 * @param {Key} key The key being tested. | |
| 285 * @return {boolean} Whether it belongs in the right branch. | |
| 286 */ | |
| 287 test: function(key) { | |
| 288 return this.decision.testKey(key); | |
| 289 }, | |
| 290 }; | |
| 291 | |
| 292 /** | |
| 293 * Structure representing a leaf in the decision tree. It contains a single | |
| 294 * data point. | |
| 295 */ | |
| 296 var LeafNode = function(data) { | |
| 297 this.data = data; | |
| 298 }; | |
| 299 | |
| 300 LeafNode.prototype = { | |
| 301 search: function() { | |
| 302 return this; | |
| 303 }, | |
| 304 }; | |
| 305 | |
| 306 /** | |
| 307 * Converts the array to a binary tree. | |
| 308 * @param {number} start The start index. | |
| 309 * @param {number} end The end index. | |
| 310 * @param {Array} nodes The array to convert. | |
| 311 * @return {DecisionNode} | |
| 312 */ | |
| 313 var createBinaryTree = function(start, end, nodes) { | |
| 314 if (start > end) | |
| 315 return; | |
| 316 var midpoint = Math.floor((end + start)/2); | |
| 317 var root = new DecisionNode(nodes[midpoint]); | |
| 318 root.fail = createBinaryTree(start, midpoint - 1, nodes); | |
| 319 root.pass = createBinaryTree(midpoint + 1, end, nodes); | |
| 320 return root; | |
| 321 }; | |
| 322 | |
| 323 /** | |
| 324 * Calculates the optimum split points on the specified axis. | |
| 325 * @param {Array.<Keys>} allKeys All keys in the keyset. | |
| 326 * @param {Orientation} orientation Whether to split on the y-axis instead. | |
| 327 * @return {Array.<Line>} The optimum split points. | |
| 328 */ | |
| 329 var findSplits = function(allKeys, orientation) { | |
| 330 /** | |
| 331 * Returns the minimum edge on the key. | |
| 332 * @param {Key} key The key. | |
| 333 * @return {number} | |
| 334 */ | |
| 335 var getMin = function(key) { | |
| 336 return orientation == Orientation.HORIZONTAL ? key.top : key.left; | |
| 337 }; | |
| 338 | |
| 339 /** | |
| 340 * Returns the maximum edge on the key. | |
| 341 * @param {Key} key The key. | |
| 342 */ | |
| 343 var getMax = function(key) { | |
| 344 return orientation == Orientation.HORIZONTAL ? key.bottom : key.right; | |
| 345 }; | |
| 346 | |
| 347 /** | |
| 348 * Returns a duplicate free version of array. | |
| 349 * @param {Array} array A sorted array. | |
| 350 * @return {Array} Sorted array without duplicates. | |
| 351 */ | |
| 352 var unique = function(array) { | |
| 353 var result = []; | |
| 354 for (var i = 0; i< array.length; i++) { | |
| 355 if (i == 0 || result[result.length -1] != array[i]) | |
| 356 result.push(array[i]); | |
| 357 } | |
| 358 return result; | |
| 359 }; | |
| 360 | |
| 361 /** | |
| 362 * Creates an array of zeroes. | |
| 363 * @param {number} length The length of the array. | |
| 364 * @return {Array{number}} | |
| 365 */ | |
| 366 var zeroes = function(length) { | |
| 367 var array = new Array(length); | |
| 368 for (var i = 0; i < length; i++) { | |
| 369 array[i] = 0; | |
| 370 } | |
| 371 return array; | |
| 372 } | |
| 373 // All edges of keys. | |
| 374 var edges = []; | |
| 375 for (var i = 0; i < allKeys.length; i++) { | |
| 376 var key = allKeys[i]; | |
| 377 var min = getMin(key); | |
| 378 var max = getMax(key); | |
| 379 edges.push(min); | |
| 380 edges.push(max); | |
| 381 } | |
| 382 // Array.sort() sorts lexicographically by default. | |
| 383 edges.sort(function(a, b) { | |
| 384 return a - b; | |
| 385 }); | |
| 386 edges = unique(edges); | |
| 387 // Container for projection sum from edge i to edge i + 1. | |
| 388 var intervalWeight = zeroes(edges.length); | |
| 389 | |
| 390 for (var i = 0; i < allKeys.length; i++) { | |
| 391 var key = allKeys[i]; | |
| 392 var min = getMin(key); | |
| 393 var max = getMax(key); | |
| 394 var index = | |
| 395 exports.binarySearch(edges, 0, edges.length - 1, function(index) { | |
| 396 var edge = edges[index]; | |
| 397 return edge == min ? 0 : min - edge; | |
| 398 }); | |
| 399 if (index < 0 || min != edges[index]) { | |
| 400 console.error("Unable to split keys."); | |
| 401 return; | |
| 402 } | |
| 403 // Key can span multiple edges. | |
| 404 for (var j = index; j < edges.length && edges[j] < max; j++) { | |
| 405 intervalWeight[j] ++; | |
| 406 } | |
| 407 } | |
| 408 | |
| 409 var splits = []; | |
| 410 // Min and max are bad splits. | |
| 411 for (var i = 1; i < intervalWeight.length - 1; i++) { | |
| 412 if (intervalWeight[i] < intervalWeight[i - 1]) { | |
| 413 var mid = Math.abs((edges[i] + edges[i+1]) / 2) | |
| 414 splits.push(new Line(mid, orientation)); | |
| 415 } | |
| 416 } | |
| 417 return splits; | |
| 418 } | |
| 419 | |
| 420 /** | |
| 421 * Caches the layout of current keysets. | |
| 422 */ | |
| 423 function recordKeysets_() { | |
| 424 layouts = {}; | |
| 425 var keysets = $('keyboard').querySelectorAll('kb-keyset').array(); | |
| 426 for (var i = 0; i < keysets.length; i++) { | |
| 427 var keyset = keysets[i]; | |
| 428 var layout = new KeysetLayout(); | |
| 429 var rows = keyset.querySelectorAll('kb-row').array(); | |
| 430 for (var j = 0; j < rows.length; j++) { | |
| 431 var row = rows[j]; | |
| 432 var nodes = row.children; | |
| 433 for (var k = 0 ; k < nodes.length; k++) { | |
| 434 layout.add(new Key(nodes[k])); | |
| 435 } | |
| 436 } | |
| 437 layout.regenerateTree(); | |
| 438 layouts[keyset.id] = layout; | |
| 439 } | |
| 440 }; | |
| 441 | |
| 442 /** | |
| 443 * Returns the layout of the keyset. | |
| 444 * @param{!String} id The id of the keyset. | |
| 445 * @private | |
| 446 */ | |
| 447 var getKeysetLayout_ = function(id) { | |
| 448 return layouts[id]; | |
| 449 }; | |
| 450 | |
| 451 exports.getKeysetLayout = getKeysetLayout_; | |
| 452 exports.recordKeysets = recordKeysets_; | |
| 453 })(this); | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 730573002:
Remove dead code for system VK. (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master