• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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);
454