1a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 2a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)// found in the LICENSE file. 4a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 5a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 6a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)(function(exports) { 7a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 8a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Orientation of a line. 9a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @enum {boolean} 10a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 11a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var Orientation = { 12a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) VERTICAL: false, 13a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) HORIZONTAL: true 14a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 15a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 16a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 17a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Map from keysetId to layout. 18a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {Map<String,KeysetLayout>} 19a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @private 20a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 21a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var layouts = {}; 22a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 23a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 24a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Container for storing a keyset's layout. 25a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 26a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var KeysetLayout = function() { 27a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.keys = []; 28a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 30a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) KeysetLayout.prototype = { 31a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 32a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * All keys in the keyset. 33a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {Array<Key>} 34a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 35a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) keys: undefined, 36a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 37a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 38a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Spacial partitioning of all keys in the keyset. 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {DecisionNode} 40a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 41a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) tree: undefined, 42a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 43a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 44a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Add a key to the keyset. 45a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 46a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) add: function(key) { 47a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.keys.push(key); 48a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 49a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 50a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 51a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Regenerates a decision tree using the keys in the keyset. 52a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 53a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) regenerateTree: function() { 54a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Split using horizontal lines first, as keyboards tend to be 55a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // row-centric. 56a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var splits = findSplits(this.keys, Orientation.HORIZONTAL); 57a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.tree = createBinaryTree(0, splits.length - 1, splits); 58effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch if (this.tree) 59effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch this.tree.populate(this.keys); 60a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 61a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 62a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 63a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Searches the tree for the key closest to the point provided. 64a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} x The x-coordinate. 65a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} y The y-coordinate. 66a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {?kb-key} The key, or null if none found. 67a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 68a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) findClosestKey: function(x, y) { 69a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var closestNode = this.tree.findClosestNode(x, y); 70c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch var key = closestNode.data; 71c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch if (!key) 72c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return; 73c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch // Ignore touches that aren't close. 741320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return key.distanceTo(x, y) <= MAX_TOUCH_FUZZ_DISTANCE ? 75c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch key.key : null; 76a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 77a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 78a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 79a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns the position data of all keys in this keyset. 80a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {Array<Map>} 81a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 82a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) getLayout: function() { 83a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return this.keys.map(function(key) { 84a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return key.toMap(); 85a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }); 86a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 87a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 88a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 89a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 90a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Container for caching a key's data. 911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {{style: {left: number, top: number, width: number, 921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * height: number}}} key The key to cache. 931320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * left: The x-coordinate of the left edge of the key. 941320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * top: The y-coordinate of the top edge of the key. 951320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * width: The width of the key in px. 961320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * height: The height of the key in px. 971320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @constructor 98a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 99a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var Key = function(key) { 100a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.key = key; 101a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var style = key.style; 102a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.top = parseFloat(style.top) - KEY_PADDING_TOP; 103a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.left = parseFloat(style.left); 104a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.right = this.left + parseFloat(style.width); 105a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.bottom = this.top + parseFloat(style.height) + KEY_PADDING_TOP 106a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) + KEY_PADDING_BOTTOM; 107a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 108a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 109a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Key.prototype = { 110a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 111a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Manhattan distance from the the provided point to the key. 112a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} x The x-coordinate of the point. 113a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} y The y-coordinate of the point. 1141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @return {number} 115a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 1161320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci distanceTo: function(x, y) { 117c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch return Math.abs(this.intersect(new Line(x))) + 118c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch Math.abs(this.intersect(new Line(y, true))); 119a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 120a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 121a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 122a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Checks whether the key intersects with the line provided. 123a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {!Line} line The line. 124a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {number} Zero if it intersects, signed manhattan distance if it 125a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * does not. 126a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 127a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) intersect: function(line) { 128a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var min = line.rotated ? this.top : this.left; 129a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var max = line.rotated ? this.bottom : this.right; 130a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return (line.c > max) ? line.c - max : Math.min(0, line.c - min); 131a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 132a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 133a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 134a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns the Key as a map. 135a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {Map<String,number>} 136a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 137a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) toMap: function() { 138a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return { 139a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 'x': this.left, 140a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 'y': this.top, 141a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 'width': this.right - this.left, 142a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 'height': this.bottom - this.bottom, 143a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 144a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 145a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 146a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 147a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 148a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Object representing the line y = c or x = c. 1491320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {number} c The x or y coordinate of the intersection line depending 1501320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * on orientation. 151a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Orientation} orientation The orientation of the line. 1521320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @constructor 153a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 154a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var Line = function(c, orientation) { 155a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.c = c; 156a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.rotated = orientation; 157a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 158a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 159a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Line.prototype = { 160a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 161a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The position of the provided point in relation to the line. 162a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} x The x-coordinate of the point. 163a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} y The y-coordinate of the point. 164a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {number} Zero if they intersect, negative if the point is before 165a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * the line, positive if it's after. 166a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 1671320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci testPoint: function(x, y) { 168a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var c = this.rotated ? y : x; 169a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return this.c == c ? 0 : c - this.c; 170a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 171a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 1721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci test: function(key) { 173a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Key already provides an intersect method. If the key is to the right of 174a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // the line, then the line is to the left of the key. 175a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return -1 * key.intersect(this); 176a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 177a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 178a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 179a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 180a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * A node used to split 2D space. 1811320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {Line} line The line to split the space with. 1821320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @constructor 183a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 184a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var DecisionNode = function(line) { 185a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.decision = line; 186a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 187a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 188a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DecisionNode.prototype = { 189a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 190a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The test whether to proceed in the left or right branch. 191a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {Line} 192a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 193a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) decision: undefined, 194a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 195a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 196a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The branch for nodes that failed the decision test. 197a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {?DecisionNode} 198a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 199a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) fail: undefined, 200a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 201a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 202a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * The branch for nodes that passed the decision test. 203a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @type {?DecisionNode} 204a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 205a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pass: undefined, 206a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 207a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 208a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Finds the node closest to the point provided. 209a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} x The x-coordinate. 210a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} y The y-coordinate. 211a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {DecisionNode | LeafNode} 212a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 213a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) findClosestNode: function(x, y) { 2141320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return this.search(function(node) { 2151320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return node.decision.testPoint(x, y) >= 0; 216a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }); 217a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 218a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 219a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 220a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Populates the decision tree with elements. 221a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Array{Key}} The child elements. 222a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 223a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) populate: function(data) { 224a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (!data.length) 225a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 226a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var pass = []; 227a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var fail = []; 2281320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (var i = 0; i < data.length; i++) { 229a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var result = this.decision.test(data[i]); 230a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Add to both branches if result == 0. 231a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (result >= 0) 232a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) pass.push(data[i]); 233a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (result <= 0) 234a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) fail.push(data[i]); 235a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 236a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var currentRotation = this.decision.rotated; 237a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 238a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Splits the tree further such that each leaf has exactly one data point. 239a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Array} array The data points. 240a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {DecisionNode | LeafNode} The new branch for the tree. 241a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 242a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var updateBranch = function(array) { 243a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (array.length == 1) { 244a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return new LeafNode(array[0]); 245a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } else { 2461320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci var splits = findSplits(array, !currentRotation); 247a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var tree = createBinaryTree(0, splits.length - 1, splits); 248a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) tree.populate(array); 249a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return tree; 250a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 251a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 252a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // All elements that passed the decision test. 253a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (pass.length > 0) { 254a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (this.pass) 255a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.pass.populate(pass); 256a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) else 257a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.pass = updateBranch(pass); 258a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 259a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // All elements that failed the decision test. 260a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (fail.length > 0) { 261a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (this.fail) 262a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.fail.populate(fail); 263a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) else 264a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.fail = updateBranch(fail); 265a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 266a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 267a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 268a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 269a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Searches for the first leaf that matches the search function. 270a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Function<DecisionNode>: Boolean} searchFn The function used to 271a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * determine whether to search in the left or right subtree. 2721320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @return {DecisionNode | LeafNode} The node that most closely matches the 273a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * search parameters. 274a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 275a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) search: function(searchFn) { 276a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (searchFn(this)) { 277a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return this.pass ? this.pass.search(searchFn) : this; 278a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 279a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return this.fail ? this.fail.search(searchFn) : this; 280a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 281a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 282a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 283a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Tests whether the key belongs in the left or right branch of this node. 284a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Key} key The key being tested. 285a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {boolean} Whether it belongs in the right branch. 286a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 287a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) test: function(key) { 2881320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci return this.decision.testKey(key); 289a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 290a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 291a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 292a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 293a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Structure representing a leaf in the decision tree. It contains a single 294a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * data point. 295a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 296a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var LeafNode = function(data) { 297a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) this.data = data; 298a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 299a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 300a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) LeafNode.prototype = { 301a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) search: function() { 302a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return this; 303a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }, 304a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 305a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 306a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 307a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Converts the array to a binary tree. 308a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} start The start index. 309a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} end The end index. 310a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Array} nodes The array to convert. 311a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {DecisionNode} 312a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 313a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var createBinaryTree = function(start, end, nodes) { 314a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (start > end) 315a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 316a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var midpoint = Math.floor((end + start)/2); 317a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var root = new DecisionNode(nodes[midpoint]); 318a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) root.fail = createBinaryTree(start, midpoint - 1, nodes); 319a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) root.pass = createBinaryTree(midpoint + 1, end, nodes); 320a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return root; 321a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 322a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 323a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 324a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Calculates the optimum split points on the specified axis. 3251320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {Array.<Keys>} allKeys All keys in the keyset. 3261320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {Orientation} orientation Whether to split on the y-axis instead. 3271320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @return {Array.<Line>} The optimum split points. 328a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 329a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var findSplits = function(allKeys, orientation) { 330a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 331a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns the minimum edge on the key. 3321320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {Key} key The key. 333a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {number} 334a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 335a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var getMin = function(key) { 336a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return orientation == Orientation.HORIZONTAL ? key.top : key.left; 337a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 338a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 339a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 340a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns the maximum edge on the key. 3411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * @param {Key} key The key. 342a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 343a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var getMax = function(key) { 344a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return orientation == Orientation.HORIZONTAL ? key.bottom : key.right; 345a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 346a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 347a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 348a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns a duplicate free version of array. 349a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {Array} array A sorted array. 350a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {Array} Sorted array without duplicates. 351a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 352a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var unique = function(array) { 353a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var result = []; 354a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 0; i< array.length; i++) { 355a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (i == 0 || result[result.length -1] != array[i]) 356a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) result.push(array[i]); 357a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 358a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return result; 359a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 360a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 361a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 362a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Creates an array of zeroes. 363a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param {number} length The length of the array. 364a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @return {Array{number}} 365a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 366a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var zeroes = function(length) { 367a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var array = new Array(length); 368a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 0; i < length; i++) { 369a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) array[i] = 0; 370a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 371a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return array; 372a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 373a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // All edges of keys. 374a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var edges = []; 375a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 0; i < allKeys.length; i++) { 376a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var key = allKeys[i]; 377a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var min = getMin(key); 378a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var max = getMax(key); 379a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) edges.push(min); 380a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) edges.push(max); 381a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 382a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Array.sort() sorts lexicographically by default. 383a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) edges.sort(function(a, b) { 384a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return a - b; 385a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }); 386a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) edges = unique(edges); 387a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Container for projection sum from edge i to edge i + 1. 388a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var intervalWeight = zeroes(edges.length); 389a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 390a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 0; i < allKeys.length; i++) { 391a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var key = allKeys[i]; 392a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var min = getMin(key); 393a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var max = getMax(key); 394a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var index = 395a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) exports.binarySearch(edges, 0, edges.length - 1, function(index) { 396a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var edge = edges[index]; 397a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return edge == min ? 0 : min - edge; 398a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }); 399a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (index < 0 || min != edges[index]) { 400a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) console.error("Unable to split keys."); 401a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 402a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 403a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Key can span multiple edges. 404a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var j = index; j < edges.length && edges[j] < max; j++) { 405a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) intervalWeight[j] ++; 406a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 407a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 408a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 409a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var splits = []; 410a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Min and max are bad splits. 411a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 1; i < intervalWeight.length - 1; i++) { 412a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (intervalWeight[i] < intervalWeight[i - 1]) { 413a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var mid = Math.abs((edges[i] + edges[i+1]) / 2) 414a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) splits.push(new Line(mid, orientation)); 415a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 416a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 417a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return splits; 418a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 419a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 420a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 421a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Caches the layout of current keysets. 422a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 423a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) function recordKeysets_() { 424a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) layouts = {}; 425a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var keysets = $('keyboard').querySelectorAll('kb-keyset').array(); 426a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var i = 0; i < keysets.length; i++) { 427a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var keyset = keysets[i]; 428a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var layout = new KeysetLayout(); 429a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var rows = keyset.querySelectorAll('kb-row').array(); 430a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var j = 0; j < rows.length; j++) { 431a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var row = rows[j]; 432a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var nodes = row.children; 433a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) for (var k = 0 ; k < nodes.length; k++) { 434a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) layout.add(new Key(nodes[k])); 435a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 436a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 437a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) layout.regenerateTree(); 438a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) layouts[keyset.id] = layout; 439a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 440a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 441a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 442a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) /** 443a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * Returns the layout of the keyset. 444a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @param{!String} id The id of the keyset. 445a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) * @private 446a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) */ 447a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) var getKeysetLayout_ = function(id) { 448a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return layouts[id]; 449a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) }; 450a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 451a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) exports.getKeysetLayout = getKeysetLayout_; 452a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) exports.recordKeysets = recordKeysets_; 453a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)})(this); 454