1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// Copyright 2013 The Chromium Authors. All rights reserved. 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com// Use of this source code is governed by a BSD-style license that can be 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// found in the LICENSE file. 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/** 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * This function returns the first element index that >= target, when no element 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * in the array >= target, return array.length. 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * This function must be called in the shape of binarySearch(array, target). 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * @param {number} target 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * @return {number} 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvar binarySearch = function(target) { 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 'use strict'; 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com var left = 0; 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com var right = this.length - 1; 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (left <= right) { 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com var mid = Math.floor((left + right) / 2); 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this[mid] < target) 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com left = mid + 1; 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (this[mid] > target) 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com right = mid - 1; 23d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com else 24d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com return mid; 25d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com } 26d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com return left; 27d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com}; 28d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com 29d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com/** 30d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * Return the intersection set of two sorted arrays. 31d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * @param {Array.<*>} left 32d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * @param {Array.<*>} right 33d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * @return {Array.<*>} 34d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com */ 35d26147adbbdca85f07dff432025afee0c8614387caryclark@google.comvar intersectionOfSorted = function(left, right) { 36d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com var from = 0; 37d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com return left.reduce(function(previous, current) { 38d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com var idx = right.indexOf(current, from); 39d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com if (idx != -1) { 40d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com previous.push(current); 41d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com from = idx; 42d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com } 43d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com return previous; 44d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com }, []); 45d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com}; 46d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com 47d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com/** 48d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * Output object with indented format. 49d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * @param {Object} obj 50d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com * @param {string} title 51d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com */ 52d26147adbbdca85f07dff432025afee0c8614387caryclark@google.comvar inspect = function(obj, title) { 53d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com if (title) console.log(title); 54d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com console.log(JSON.stringify(obj, null, 2)); 55d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com}; 56d26147adbbdca85f07dff432025afee0c8614387caryclark@google.com