src/ui/keyboard/resources/touch_fuzzing.js

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