preface

The learning underscore. Js source code version is 1.13.1. FindIndex, findLastIndex, sortedIndex, indexOf, lastIndexOf

ES6 findIndex

The findIndex method has been added to arrays in ES6, which returns the index of the first element in the array that satisfies the provided test function. Returns -1 if no corresponding element is found;

Let’s take a look at the usage:

const arr = [5.12.8.130.44];

const isLargeNumber = (element) = > element > 13;

console.log(arr.findIndex(isLargeNumber));  / / 3
Copy the code

FindIndex will find the index of the first element greater than 13, so it returns 3

Implement findIndex

function findIndex (array, predicate, context) {
  var length = array.length;
  for (var index = 0; index < length; index++) {
    if (predicate.call(context, array[index], index, array)) return index;
  }
  return -1;
}

const arr = [5.12.8.130.44];
findIndex(arr, function (item, index, array) {
    return item > 13;
});
/ / 3

Copy the code

Implement findLastIndex

FindIndex is a positive lookup, and we can also implement a reverse lookup of findLastIndex

function findLastIndex (array, predicate, context) {
  var length = array.length;
  for (var index = length - 1; index >= 0; index--) {
    if (predicate.call(context, array[index], index, array)) return index;
  }
  return -1;
}

const arr = [5.12.8.130.44];
findLastIndex(arr, function (item, index, array) {
    return item > 13;
});
/ / 4
Copy the code

createPredicateIndexFinder

/ / findIndex/findLastIndex/findIndex/findLastIndex/findIndex/findLastIndex/findIndex/findLastIndex/findIndex/findLastIndex/findIndex/findLastIndex/findIndex/lastIndex/findIndex/findLastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex/findIndex/lastIndex /

/** * return a different function * depending on the parameters passed@param {number} Dir implements the key factor */ for both forward and backward traversal
function createPredicateIndexFinder (dir) {
  return function (array, predicate, context) {
    var length = arr.length;
    var index = dir > 0 ? 0 : length - 1;
    for (; index >= 0 && index < length; index += dir) {
      if (predicate.call(context, array[index], index, array)) return index;
    }
    return -1;
  };
}
var findIndex = createPredicateIndexFinder(1);
var findLastIndex = createPredicateIndexFinder(-1);
Copy the code

sortedIndex

Use binary lookup to determine the ordinal number of a value in a list. Inserting a value by this ordinal number preserves the original order of the list.

Use:

_.sortedIndex([10.20.30.40.50].35);  / / 3
Copy the code

Since the list is ordered, we can use dichotomy to find the insertion position.

First version implementation

function sortedIndex (array, obj) {
  var low = 0, high = array.length;
  while (low < high) {
    var mid = Math.floor((low + high) / 2);
    if (array[mid] < obj) low = mid + 1; 
    else high = mid;
  }
  return low;
}
sortedIndex([10.20.30.40.50].35);  / / 3
Copy the code

But this is very limited, we also want to achieve the following:

var stooges = [{name: 'moe'.age: 40}, {name: 'curly'.age: 60}];
_.sortedIndex(stooges, {name: 'larry'.age: 50}, 'age');  / / 1
Copy the code

So we need to add an iteratee function to each element of the array, and we need to worry about this; In the last article we learned about the inner function cb, which handles different types of iteratee

function sortedIndex(array, obj, iteratee, context) {
  iteratee = cb(iteratee, context, 1);
  var value = iteratee(obj);
  var low = 0, high = array.length;
  while (low < high) {
    var mid = Math.floor((low + high) / 2);
    if (iteratee(array[mid]) < value) low = mid + 1; 
    else high = mid;
  }
  return low;
}
Copy the code

IndexOf, lastIndexOf

Based on the above implementation of findIndex and FindLastIndex, it is easy to write the first version of indexOf and lastIndexOf

The first edition

function createIndexFinder(dir) {
  return function(array, item, idx) {
    var i = 0, length = array.length;
    for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
      if (array[idx] === item) return idx;
    }
    return -1;
  };
}
var indexOf = createIndexFinder(1);
var lastIndexOf = createIndexFinder(-1);


indexOf([1.2.3].2);    //  1
lastIndexOf([1.2.3.1.2.3].2);   / / 4

Copy the code

Version 2 supports fromIndex

IndexOf fromIndex MDN

The location to start the search. If the index value is greater than or equal to the length of the array, it means that it is not searched in the array, and returns -1. If the index value provided in the argument is a negative value, it is treated as an offset at the end of the array, with -1 indicating the search starts from the last element, -2 indicating the search starts from the next-to-last element, and so on. Note: If the index value provided in the argument is a negative value, the lookup order does not change, and the lookup order is still the array queried from front to back. If the offset index is still less than 0, the entire array will be queried. The default value is 0.

FromIndex MDN

Start looking backwards from this location. The default is the length of the array minus 1(arr.length-1), that is, the entire array is searched. If the value is greater than or equal to the length of the array, the entire array is searched. If it is negative, it is treated as an offset forward from the end of the array. Even if the value is negative, the array will still be looked up backwards. If the value is negative and its absolute value is greater than the array length, the method returns -1, meaning that the array is not found.

The second version implements:

function createIndexFinder(dir) {
  return function(array, item, idx) {
    var i = 0, length = array.length;
    if (typeof idx == 'number') {
      // indexOf handles the location where the search started
      if (dir > 0) {
        i = idx >= 0 ? idx : Math.max(idx + length, i);
      } else {
        // lastIndexOf iterates through the length of the array
        length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; }}for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
      if (array[idx] === item) return idx;
    }
    return -1;
  };
}

var indexOf = createIndexFinder(1);
var lastIndexOf = createIndexFinder(-1);


indexOf([1.2.3.2].2.2);    //  3
lastIndexOf([1.2.3.1.2.3].2.2);   / / 1

Copy the code

The third edition optimization takes NaN into account

IndexOf is implemented using ===, we know NaN! == NaN, then you can use the initial findIndex to find the subscript of the eligible value from the array

var isNumber = function (num) {
  return Object.prototype.toString.call(num) === '[object Number]'
}
function isNaN$1(obj) {
  return isNumber(obj) && isNaN(obj);
}


function createIndexFinder(dir, predicateFind) {
  return function(array, item, idx) {
    var i = 0, length = array.length;
    if (typeof idx == 'number') {
      if (dir > 0) {
        i = idx >= 0 ? idx : Math.max(idx + length, i);
      } else {
        length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; }}// NaN ! == NaN
    if(item ! == item) {// Find the index of the first element in the truncated array that satisfies the isNaN$1 function
      idx = predicateFind(array.slice.call(array, i, length), isNaN$1);
      return idx >= 0 ? idx + i : -1;
    }
    for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
      if (array[idx] === item) return idx;
    }
    return -1;
  };
}

var indexOf = createIndexFinder(1, findIndex);
var lastIndexOf = createIndexFinder(-1, findLastIndex);

indexOf([1.NaN.3.NaN].NaN.2);    //  3
lastIndexOf([1.NaN.3.1.NaN.3].NaN.2);   / / 1
Copy the code

The fourth edition of indexOf is optimized to support binary lookup

Support for faster binary lookups of ordered arrays. If the third argument to indexOf does not pass the subscript value that started the search, but a Boolean value true, the array is considered to be a sorted array. In this case, the faster binary lookups are used. We can use the final sortedIndex function we wrote:

function createIndexFinder(dir, predicateFind, sortedIndex) {
  return function(array, item, idx) {
    var i = 0, length = array.length;
    // Process the search location
    if (typeof idx == 'number') {
      if (dir > 0) {
        i = idx >= 0 ? idx : Math.max(idx + length, i);
      } else {
        length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; }}else if (sortedIndex && idx && length) {  // Use the faster dichotomy method for lookup
      idx = sortedIndex(array, item);
      return array[idx] === item ? idx : -1;
    }
    / / deal with NaN
    if(item ! == item) {// Find the index of the first element in the truncated array that satisfies the isNaN$1 function
      idx = predicateFind(array.slice.call(array, i, length), isNaN$1);
      return idx >= 0 ? idx + i : -1;
    }
    for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
      if (array[idx] === item) return idx;
    }
    return -1;
  };
}
// Only indexOf supports binary lookup for ordered arrays. LastIndexOf does not
var indexOf = createIndexFinder(1, findIndex, sortedIndex);
var lastIndexOf = createIndexFinder(-1, findLastIndex);
Copy the code

Reference: github.com/mqyqingfeng… Developer.mozilla.org/zh-CN/docs/…