keyboard/resources/touch_fuzzing.js

// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.


(function(exports) {
  /**
   * Orientation of a line.
   * @enum {boolean}
   */
  var Orientation = {
    VERTICAL: false,
    HORIZONTAL: true
  }

  /**
   * Map from keysetId to layout.
   * @type {Map<String,KeysetLayout>}
   * @private
   */
  var layouts = {};

  /**
   * Container for storing a keyset's layout.
   */
  var KeysetLayout = function() {
    this.keys = [];
  }

  KeysetLayout.prototype = {
    /**
     * All keys in the keyset.
     * @type {Array<Key>}
     */
    keys: undefined,

    /**
     * Spacial partitioning of all keys in the keyset.
     * @type {DecisionNode}
     */
    tree: undefined,

    /**
     * Add a key to the keyset.
     */
    add: function(key) {
      this.keys.push(key);
    },

    /**
     * Regenerates a decision tree using the keys in the keyset.
     */
    regenerateTree: function() {
      // Split using horizontal lines first, as keyboards tend to be
      // row-centric.
      var splits = findSplits(this.keys, Orientation.HORIZONTAL);
      this.tree = createBinaryTree(0, splits.length - 1, splits);
      if (this.tree)
        this.tree.populate(this.keys);
    },

    /**
     * Searches the tree for the key closest to the point provided.
     * @param {number} x The x-coordinate.
     * @param {number} y The y-coordinate.
     * @return {?kb-key} The key, or null if none found.
     */
    findClosestKey: function(x, y) {
      var closestNode = this.tree.findClosestNode(x, y);
      var key = closestNode.data;
      if (!key)
        return;
      // Ignore touches that aren't close.
      return key.distanceTo(x, y) <= MAX_TOUCH_FUZZ_DISTANCE ?
          key.key : null;
    },

    /**
     * Returns the position data of all keys in this keyset.
     * @return {Array<Map>}
     */
    getLayout: function() {
      return this.keys.map(function(key) {
        return key.toMap();
      });
    },
  };

  /**
   * Container for caching a key's data.
   * @param {{style: {left: number, top: number, width: number,
   *                  height: number}}} key The key to cache.
   *     left: The x-coordinate of the left edge of the key.
   *     top: The y-coordinate of the top edge of the key.
   *     width: The width of the key in px.
   *     height: The height of the key in px.
   * @constructor
   */
  var Key = function(key) {
    this.key = key;
    var style = key.style;
    this.top = parseFloat(style.top) - KEY_PADDING_TOP;
    this.left = parseFloat(style.left);
    this.right = this.left + parseFloat(style.width);
    this.bottom = this.top + parseFloat(style.height) + KEY_PADDING_TOP
        + KEY_PADDING_BOTTOM;
  }

  Key.prototype = {
    /**
     * Manhattan distance from the the provided point to the key.
     * @param {number} x The x-coordinate of the point.
     * @param {number} y The y-coordinate of the point.
     * @return {number}
     */
    distanceTo: function(x, y) {
      return Math.abs(this.intersect(new Line(x))) +
          Math.abs(this.intersect(new Line(y, true)));
    },

    /**
     * Checks whether the key intersects with the line provided.
     * @param {!Line} line The line.
     * @return {number} Zero if it intersects, signed manhattan distance if it
     *     does not.
     */
    intersect: function(line) {
      var min = line.rotated ? this.top : this.left;
      var max = line.rotated ? this.bottom : this.right;
      return (line.c > max) ? line.c - max : Math.min(0, line.c - min);
    },

    /**
     * Returns the Key as a map.
     * @return {Map<String,number>}
     */
    toMap: function() {
      return {
        'x': this.left,
        'y': this.top,
        'width': this.right - this.left,
        'height': this.bottom - this.bottom,
      }
    },
  };

  /**
   * Object representing the line y = c or x = c.
   * @param {number} c The x or y coordinate of the intersection line depending
   *     on orientation.
   * @param {Orientation} orientation The orientation of the line.
   * @constructor
   */
  var Line = function(c, orientation) {
    this.c = c;
    this.rotated = orientation;
  };

  Line.prototype = {
    /**
     * The position of the provided point in relation to the line.
     * @param {number} x The x-coordinate of the point.
     * @param {number} y The y-coordinate of the point.
     * @return {number} Zero if they intersect, negative if the point is before
     *    the line, positive if it's after.
     */
    testPoint: function(x, y) {
      var c = this.rotated ? y : x;
      return this.c == c ? 0 : c - this.c;
    },

    test: function(key) {
      // Key already provides an intersect method. If the key is to the right of
      // the line, then the line is to the left of the key.
      return -1 * key.intersect(this);
    },
  };

  /**
   * A node used to split 2D space.
   * @param {Line} line The line to split the space with.
   * @constructor
   */
  var DecisionNode = function(line) {
    this.decision = line;
  };

  DecisionNode.prototype = {
    /**
     * The test whether to proceed in the left or right branch.
     * @type {Line}
     */
    decision: undefined,

    /**
     * The branch for nodes that failed the decision test.
     * @type {?DecisionNode}
     */
    fail: undefined,

    /**
     * The branch for nodes that passed the decision test.
     * @type {?DecisionNode}
     */
    pass: undefined,

    /**
     * Finds the node closest to the point provided.
     * @param {number} x The x-coordinate.
     * @param {number} y The y-coordinate.
     * @return {DecisionNode | LeafNode}
     */
    findClosestNode: function(x, y) {
      return this.search(function(node) {
        return node.decision.testPoint(x, y) >= 0;
      });
    },

    /**
     * Populates the decision tree with elements.
     * @param {Array{Key}} The child elements.
     */
    populate: function(data) {
      if (!data.length)
        return;
      var pass = [];
      var fail = [];
      for (var i = 0; i < data.length; i++) {
        var result = this.decision.test(data[i]);
        // Add to both branches if result == 0.
        if (result >= 0)
          pass.push(data[i]);
        if (result <= 0)
          fail.push(data[i]);
      }
      var currentRotation = this.decision.rotated;
      /**
       * Splits the tree further such that each leaf has exactly one data point.
       * @param {Array} array The data points.
       * @return {DecisionNode | LeafNode} The new branch for the tree.
       */
      var updateBranch = function(array) {
        if (array.length == 1) {
          return new LeafNode(array[0]);
        } else {
          var splits = findSplits(array, !currentRotation);
          var tree = createBinaryTree(0, splits.length - 1, splits);
          tree.populate(array);
          return tree;
        }
      };
      // All elements that passed the decision test.
      if (pass.length > 0) {
        if (this.pass)
          this.pass.populate(pass);
        else
          this.pass = updateBranch(pass);
      }
      // All elements that failed the decision test.
      if (fail.length > 0) {
        if (this.fail)
          this.fail.populate(fail);
        else
          this.fail = updateBranch(fail);
      }
    },

    /**
     * Searches for the first leaf that matches the search function.
     * @param {Function<DecisionNode>: Boolean} searchFn The function used to
     *    determine whether to search in the left or right subtree.
     * @return {DecisionNode | LeafNode} The node that most closely matches the
     *    search parameters.
     */
    search: function(searchFn) {
      if (searchFn(this)) {
        return this.pass ? this.pass.search(searchFn) : this;
      }
      return this.fail ? this.fail.search(searchFn) : this;
    },

    /**
     * Tests whether the key belongs in the left or right branch of this node.
     * @param {Key} key The key being tested.
     * @return {boolean} Whether it belongs in the right branch.
     */
    test: function(key) {
      return this.decision.testKey(key);
    },
  };

  /**
   * Structure representing a leaf in the decision tree. It contains a single
   * data point.
   */
  var LeafNode = function(data) {
    this.data = data;
  };

  LeafNode.prototype = {
    search: function() {
      return this;
    },
  };

  /**
   * Converts the array to a binary tree.
   * @param {number} start The start index.
   * @param {number} end The end index.
   * @param {Array} nodes The array to convert.
   * @return {DecisionNode}
   */
  var createBinaryTree = function(start, end, nodes) {
    if (start > end)
      return;
    var midpoint = Math.floor((end + start)/2);
    var root = new DecisionNode(nodes[midpoint]);
    root.fail = createBinaryTree(start, midpoint - 1, nodes);
    root.pass = createBinaryTree(midpoint + 1, end, nodes);
    return root;
  };

  /**
   * Calculates the optimum split points on the specified axis.
   * @param {Array.<Keys>} allKeys All keys in the keyset.
   * @param {Orientation} orientation Whether to split on the y-axis instead.
   * @return {Array.<Line>} The optimum split points.
   */
  var findSplits = function(allKeys, orientation) {
    /**
     * Returns the minimum edge on the key.
     * @param {Key} key The key.
     * @return {number}
     */
    var getMin = function(key) {
      return orientation == Orientation.HORIZONTAL ? key.top : key.left;
    };

    /**
     * Returns the maximum edge on the key.
     * @param {Key} key The key.
     */
    var getMax = function(key) {
      return orientation == Orientation.HORIZONTAL ? key.bottom : key.right;
    };

    /**
     * Returns a duplicate free version of array.
     * @param {Array} array A sorted array.
     * @return {Array} Sorted array without duplicates.
     */
    var unique = function(array) {
      var result = [];
      for (var i = 0; i< array.length; i++) {
        if (i == 0 || result[result.length -1] != array[i])
            result.push(array[i]);
      }
      return result;
    };

    /**
     * Creates an array of zeroes.
     * @param {number} length The length of the array.
     * @return {Array{number}}
     */
    var zeroes = function(length) {
      var array = new Array(length);
      for (var i = 0; i < length; i++) {
        array[i] = 0;
      }
      return array;
    }
    // All edges of keys.
    var edges = [];
    for (var i = 0; i < allKeys.length; i++) {
      var key = allKeys[i];
      var min = getMin(key);
      var max = getMax(key);
      edges.push(min);
      edges.push(max);
    }
    // Array.sort() sorts lexicographically by default.
    edges.sort(function(a, b) {
      return a - b;
    });
    edges = unique(edges);
    // Container for projection sum from edge i to edge i + 1.
    var intervalWeight = zeroes(edges.length);

    for (var i = 0; i < allKeys.length; i++) {
      var key = allKeys[i];
      var min = getMin(key);
      var max = getMax(key);
      var index =
          exports.binarySearch(edges, 0, edges.length - 1, function(index) {
        var edge = edges[index];
        return edge == min ? 0 : min - edge;
      });
      if (index < 0 || min != edges[index]) {
        console.error("Unable to split keys.");
        return;
      }
      // Key can span multiple edges.
      for (var j = index; j < edges.length && edges[j] < max; j++) {
        intervalWeight[j] ++;
      }
    }

    var splits = [];
    // Min and max are bad splits.
    for (var i = 1; i < intervalWeight.length - 1; i++) {
      if (intervalWeight[i] < intervalWeight[i - 1]) {
        var mid = Math.abs((edges[i] + edges[i+1]) / 2)
        splits.push(new Line(mid, orientation));
      }
    }
    return splits;
  }

  /**
   * Caches the layout of current keysets.
   */
  function recordKeysets_() {
    layouts = {};
    var keysets = $('keyboard').querySelectorAll('kb-keyset').array();
    for (var i = 0; i < keysets.length; i++) {
      var keyset = keysets[i];
      var layout = new KeysetLayout();
      var rows = keyset.querySelectorAll('kb-row').array();
      for (var j = 0; j < rows.length; j++) {
        var row = rows[j];
        var nodes = row.children;
        for (var k = 0 ; k < nodes.length; k++) {
          layout.add(new Key(nodes[k]));
        }
      }
      layout.regenerateTree();
      layouts[keyset.id] = layout;
    }
  };

  /**
   * Returns the layout of the keyset.
   * @param{!String} id The id of the keyset.
   * @private
   */
  var getKeysetLayout_ = function(id) {
    return layouts[id];
  };

  exports.getKeysetLayout = getKeysetLayout_;
  exports.recordKeysets = recordKeysets_;
})(this);