Five Methods Missing from JavaScript Array

JavaScript is a computer programming language that most often runs inside a web browser as part of a web page. It is a simple yet powerful language that includes several built-in classes and methods. One of these built-in classes is the Array class which has powerful methods such as concat, sort, slice, and splice. However, there are several useful methods, including binarySearch, addAll, retainAll, removeAll, and retainUnique, that were not included in the Array class. This article shows you how to add these five useful methods to the JavaScript Array class. If you put these methods in a JavaScript file named array.js, you will be able to include and use them in a web page whenever you want.

Descriptions of the Five Methods

binarySearch

The existing Array.indexOf method searches an array for an occurrence of some value called a key. The existing indexOf method is an implementation of an algorithm called linear search. This means that indexOf searches an array from the beginning to the end of the array, stopping when it finds the key or reaches the end of the array. If the key is stored in the array, the indexOf method returns the index of the first occurrence of the key. Otherwise, it returns −1. The linear search algorithm (and indexOf) works well for arrays that are small (perhaps less than 100 elements).

If the elements in an array are sorted, then the computer can use a faster algorithm called binary search to find an element within that array. The binarySearch method works by comparing the key to the middle most element in the array. If the key is less than the middle most element, then the search is repeated in the first half of the array. If the key is greater than the middle most element, then the search is repeated in the last half of the array. Of course, if the key is equal to the middle most element, then the computer has found the key and the search is done. This process of comparing the key to the middle most element of the current interval is repeated until the computer finds the key or the interval has shrunk to only one element. If that one element is not the same as the key, then the key is not present in the array.

addAll
The addAll method is similar to the built-in concat method, but the addAll method adds elements to an existing array instead of returning a new array as the concat method does. The addAll method can be used to compute the union of arrays.
retainAll
The retainAll method retains in an array all the elements that are also contained in a second array. This is similar to computing the intersection of the two arrays.
removeAll
The removeAll method removes from an array all the elements that are also contained in another array. This is similar to computing the complement of the first array relative to the second.
distinct
If an array is sorted, the distinct method removes all duplicates of all elements, leaving one unique entry for each element. In other words, after the distinct method is finished all elements in the array will be unique. This is the same thing that the -u option of the unix sort command does.

Source Code for the Five Methods

Here are the five missing JavaScript Array methods. Copy these methods into a text file named "array.js". Notice that all the methods except addAll have an optional parameter which is a comparison method. If your program is storing complex objects in arrays, you can write your own comparison method to compare the objects any way you like.



"use strict";

/** If this array contains key, returns the index of any
 * occurrence of key; otherwise returns -insertion - 1,
 * where insertion is the location within the array at
 * which the key should be inserted. binarySearch assumes
 * this array is already sorted. */
Array.prototype.binarySearch = function(key, compare) {
    if (typeof(compare) == 'undefined') {
        compare = ascending;
    }
    let left = 0;
    let right = this.length - 1;
    while (left <= right) {
        let mid = left + ((right - left) >>> 1);
        let cmp = compare(key, this[mid]);
        if (cmp > 0)
            left = mid + 1;
        else if (cmp < 0)
            right = mid - 1;
        else
            return mid;
    }
    return -(left + 1);
}


/** Adds all the elements in the
 * specified arrays to this array. */
Array.prototype.addAll = function() {
    for (let a = 0;  a < arguments.length;  a++) {
        let arr = arguments[a];
        for (let i = 0;  i < arr.length;  i++) {
            this.push(arr[i]);
        }
    }
}


/** Retains in this array all the elements
 * that are also found in the specified array. */
Array.prototype.retainAll = function(arr, compare) {
    if (typeof(compare) == 'undefined') {
        compare = ascending;
    }
    let i = 0;
    while (i < this.length) {
        if (arr.indexOf(this[i], compare) == -1) {
            let end = i + 1;
            while (end < this.length &&
                    arr.indexOf(this[end], compare) == -1) {
                end++;
            }
            this.splice(i, end - i);
        }
        else {
            i++;
        }
    }
}


/** Removes from this array all the elements
 * that are also found in the specified array. */
Array.prototype.removeAll = function(arr, compare) {
    if (typeof(compare) == 'undefined') {
        compare = ascending;
    }
    let i = 0;
    while (i < this.length) {
        if (arr.indexOf(this[i], compare) != -1) {
            let end = i + 1;
            while (end < this.length &&
                    arr.indexOf(this[end], compare) != -1) {
                end++;
            }
            this.splice(i, end - i);
        }
        else {
            i++;
        }
    }
}


/** Makes all elements in this array unique. In other
 * words, removes all duplicate elements from this
 * array. Assumes this array is already sorted. */
Array.prototype.distinct = function(compare) {
    if (typeof(compare) == 'undefined') {
        compare = ascending;
    }
    let dst = 0;  // Destination for elements
    let src = 0;  // Source of elements
    let limit = this.length - 1;
    while (src < limit) {
        while (compare(this[src], this[src + 1]) == 0) {
            if (++src == limit) {
                break;
            }
        }
        this[dst++] = this[src++];
    }
    if (src == limit) {
        this[dst++] = this[src];
    }
    this.length = dst;
}


/** Compares two objects using
 * built-in JavaScript operators. */
function ascending(a, b) {
    if (a < b)
        return -1;
    else if (a > b)
        return 1;
    return 0;
}



Using the Five Methods


To use the five methods, include in the head of an HTML document, the
array.js file that you saved as shown on
line 9 of the next
code example. Then you can write JavaScript code to use the five methods
just like you would use other built-in JavaScript Array
methods. The testArray function at
lines 11–87 in the
next code example shows how to use the five missing methods.





<!DOCTYPE html>
<html lang="en-us">
<head>
    <meta charset="utf-8">
    <title>Using the Five Methods</title>

    <!-- Import the JavaScript code from array.js so that the
     browser will add the five methods to the Array class. -->
    <script src="array.js"></script>

    <script>
"use strict";

function testArray() {
    document.open();

    // Create an array named plants.
    let plants = ['apple', 'pear', 'plum', 'peach'];
    document.writeln('plants:  ' + plants + '<br>');
    document.writeln('<br>');

    // Use the indexOf() method.
    document.writeln('indexOf()<br>');
    let possible = 'plum';
    if (plants.indexOf(possible) >= 0)
        document.write('plants contains ' + possible);
    else
        document.write('plants does not contain ' + possible);
    document.writeln('<br>');

    possible = 'cherry';
    if (plants.indexOf(possible) >= 0)
        document.write('plants contains ' + possible);
    else
        document.write('plants does not contain ' + possible);
    document.writeln('<br>');
    document.writeln('<br>');

    // Use the addAll() method.
    let listX = ['cherry', 'banana', 'apricot', 'mango'];
    plants.addAll(listX);
    document.writeln('addAll()<br>');
    document.writeln('listX:  ' + listX + '<br>');
    document.writeln('plants:  ' + plants + '<br>');
    document.writeln('<br>');

    // Use the binarySearch() method.
    document.writeln('binarySearch()<br>');
    possible = 'peach';
    plants.sort();
    if (plants.binarySearch(possible) >= 0)
        document.write('plants contains ' + possible);
    else
        document.write('plants does not contain ' + possible);
    document.writeln('<br>');

    possible = 'coconut';
    if (plants.binarySearch(possible) >= 0)
        document.write('plants contains ' + possible);
    else
        document.write('plants does not contain ' + possible);
    document.writeln('<br>');
    document.writeln('<br>');

    // Use the addAll() method.
    let listY = ['elm', 'pine', 'rose', 'lilac'];
    let listZ = ['lilac', 'pine', 'fir'];
    plants.addAll(listY, listZ);
    document.writeln('addAll()<br>');
    document.writeln('listY:  ' + listY + '<br>');
    document.writeln('listZ:  ' + listZ + '<br>');
    document.writeln('plants:  ' + plants + '<br>');
    document.writeln('<br>');

    // Use the retainAll() method.
    listY.retainAll(listZ);
    document.writeln('retainAll()<br>');
    document.writeln('listY:  ' + listY + '<br>');
    document.writeln('<br>');

    // Use the removeAll() method.
    listY = ['elm', 'pine', 'rose', 'lilac'];
    listY.removeAll(listZ);
    document.writeln('removeAll()<br>');
    document.writeln('listY:  ' + listY + '<br>');
    document.writeln('<br>');

    // Use the distinct() method.
    plants.addAll(listX, listY, listZ);
    plants.sort();
    plants.distinct();
    document.writeln('distinct()<br>');
    document.writeln('plants:  ' + plants + '<br>');

    document.close();
}
    </script>
</head>

<body onload="testArray()">
</body>
</html>



Futher Reading


Some readers have pointed out that within the
binarySearch method, the line of code that computes the
midpoint is unnecessarily complex and inefficient. Here is the line of
code:



    let mid = left + ((right - left) >>> 1);



Some readers have stated that a simpler and more efficient line of
code would be this:



    let mid = (left + right) / 2;



However, if we use the simpler formula for computing the midpoint for
large arrays, left + right may overflow an
integer which would cause the binarySearch method to fail.
If you wish to read more about this possible overflow,
Overflow Bug in Binary Search
by Sourabh Gupta is a short clear article that explains it. In addition,
the binary search algorithm and computing the midpoint is explained in
both of the following books: