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