�PNG  IHDR��;���IDATx��ܻn�0���K�� �)(�pA��� ���7�LeG{�� �§㻢|��ذaÆ 6lذaÆ 6lذaÆ 6lom��$^�y���ذag�5bÆ 6lذaÆ 6lذa{���� 6lذaÆ �`����}H�Fkm�,�m����Ӫ���ô�ô!� �x�|'ܢ˟;�E:���9�&ᶒ�}�{�v]�n&�6� �h��_��t�ڠ͵-ҫ���Z;��Z$�.�P���k�ž)�!��o���>}l�eQfJ�T��u і���چ��\��X=8��Rن4`Vw�l�>����n�G�^��i�s��"ms�$�u��i��?w�bs[m�6�K4���O���.�4��%����/����b�C%��t ��M�ז� �-l�G6�mrz2���s�%�9��s@���-�k�9�=���)������k�B5����\��+͂�Zsٲ ��Rn��~G���R���C����� �wIcI��n7jJ���hۛNCS|���j0��8y�iHKֶۛ�k�Ɉ+;Sz������L/��F�*\��Ԕ�#"5��m�2��[S��������=�g��n�a�P�e�ғ�L�� lذaÆ 6l�^k��̱aÆ 6lذaÆ 6lذa;���� �_��ذaÆ 6lذaÆ 6lذaÆ ���R���IEND�B` /* -*- Mode: js; js-indent-level: 2; -*- */ /* * Copyright 2011 Mozilla Foundation and contributors * Licensed under the New BSD license. See LICENSE or: * http://opensource.org/licenses/BSD-3-Clause */ exports.GREATEST_LOWER_BOUND = 1; exports.LEAST_UPPER_BOUND = 2; /** * Recursive implementation of binary search. * * @param aLow Indices here and lower do not contain the needle. * @param aHigh Indices here and higher do not contain the needle. * @param aNeedle The element being searched for. * @param aHaystack The non-empty array being searched. * @param aCompare Function which takes two elements and returns -1, 0, or 1. * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the * closest element that is smaller than or greater than the one we are * searching for, respectively, if the exact element cannot be found. */ function recursiveSearch(aLow, aHigh, aNeedle, aHaystack, aCompare, aBias) { // This function terminates when one of the following is true: // // 1. We find the exact element we are looking for. // // 2. We did not find the exact element, but we can return the index of // the next-closest element. // // 3. We did not find the exact element, and there is no next-closest // element than the one we are searching for, so we return -1. var mid = Math.floor((aHigh - aLow) / 2) + aLow; var cmp = aCompare(aNeedle, aHaystack[mid], true); if (cmp === 0) { // Found the element we are looking for. return mid; } else if (cmp > 0) { // Our needle is greater than aHaystack[mid]. if (aHigh - mid > 1) { // The element is in the upper half. return recursiveSearch(mid, aHigh, aNeedle, aHaystack, aCompare, aBias); } // The exact needle element was not found in this haystack. Determine if // we are in termination case (3) or (2) and return the appropriate thing. if (aBias == exports.LEAST_UPPER_BOUND) { return aHigh < aHaystack.length ? aHigh : -1; } else { return mid; } } else { // Our needle is less than aHaystack[mid]. if (mid - aLow > 1) { // The element is in the lower half. return recursiveSearch(aLow, mid, aNeedle, aHaystack, aCompare, aBias); } // we are in termination case (3) or (2) and return the appropriate thing. if (aBias == exports.LEAST_UPPER_BOUND) { return mid; } else { return aLow < 0 ? -1 : aLow; } } } /** * This is an implementation of binary search which will always try and return * the index of the closest element if there is no exact hit. This is because * mappings between original and generated line/col pairs are single points, * and there is an implicit region between each of them, so a miss just means * that you aren't on the very start of a region. * * @param aNeedle The element you are looking for. * @param aHaystack The array that is being searched. * @param aCompare A function which takes the needle and an element in the * array and returns -1, 0, or 1 depending on whether the needle is less * than, equal to, or greater than the element, respectively. * @param aBias Either 'binarySearch.GREATEST_LOWER_BOUND' or * 'binarySearch.LEAST_UPPER_BOUND'. Specifies whether to return the * closest element that is smaller than or greater than the one we are * searching for, respectively, if the exact element cannot be found. * Defaults to 'binarySearch.GREATEST_LOWER_BOUND'. */ exports.search = function search(aNeedle, aHaystack, aCompare, aBias) { if (aHaystack.length === 0) { return -1; } var index = recursiveSearch(-1, aHaystack.length, aNeedle, aHaystack, aCompare, aBias || exports.GREATEST_LOWER_BOUND); if (index < 0) { return -1; } // We have found either the exact element, or the next-closest element than // the one we are searching for. However, there may be more than one such // element. Make sure we always return the smallest of these. while (index - 1 >= 0) { if (aCompare(aHaystack[index], aHaystack[index - 1], true) !== 0) { break; } --index; } return index; };