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