| contact us | ||||
| articles | e-books | software | services | |
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 interpreted language that includes several built-in classes and functions. One of these built-in classes is the Array class which has powerful functions such as concat, sort, slice, and splice. However, there are several useful functions, linearSearch, binarySearch, retainAll, removeAll, and unique, that were not included in the Array class. This article shows you how to add these five useful functions plus a convenience function, addAll, to the JavaScript Array class. If you put these functions in a JavaScript file named "array.js", you will be able to include and use them in a web page whenever you want.
The linearSearch function searches an array for an occurrence of some value called a key. It searches the 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 linearSearch function returns the index of the first occurrence of the key. Otherwise, it returns -1. linearSearch 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 function 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 key has been found and the search is done. This process of comparing the key to the middle most element of the current interval is repeated until the key is found or the interval has shrunk to only 1 element. If that one element is not the same as the key, then the key is not present in the array.
The addAll function is similar to the built-in concat function, but the addAll function adds elements to an existing array instead of returning a new array as the concat function does. The addAll function can be used to compute the union of arrays.
The retainAll function 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.
The removeAll function 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.
If an array is sorted, the unique function removes all duplicates of all elements, leaving one unique entry for each element. In other words after the unique function 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.
Here are the six missing JavaScript Array functions. Copy these functions into a text file named "array.js". Notice that all the functions except addAll have an optional parameter which is a comparison function. If your program is storing complex objects in arrays, you can write your own comparison function to compare the objects any way you like.
/** If this array contains key, returns the index of
* the first occurrence of key; otherwise returns -1. */
Array.prototype.linearSearch = function(key, compare) {
if (typeof(compare) == 'undefined') {
compare = ascend;
}
for (var i = 0; i < this.length; i++) {
if (compare(this[i], key) == 0) {
return i;
}
}
return -1;
}
/** 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 = ascend;
}
var left = 0;
var right = this.length - 1;
while (left <= right) {
var mid = left + Math.floor((right - left) / 2);
var cmp = compare(key, this[mid]);
if (cmp < 0)
right = mid - 1;
else if (cmp > 0)
left = mid + 1;
else
return mid;
}
return -(left + 1);
}
/** Adds all the elements in the
* specified arrays to this array. */
Array.prototype.addAll = function() {
for (var a = 0; a < arguments.length; a++) {
arr = arguments[a];
for (var 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 = ascend;
}
var i = 0;
while (i < this.length) {
if (arr.linearSearch(this[i], compare) == -1) {
var end = i + 1;
while (end < this.length &&
arr.linearSearch(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 = ascend;
}
var i = 0;
while (i < this.length) {
if (arr.linearSearch(this[i], compare) != -1) {
var end = i + 1;
while (end < this.length &&
arr.linearSearch(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.unique = function(compare) {
if (typeof(compare) == 'undefined') {
compare = ascend;
}
var dst = 0; // Destination for elements
var src = 0; // Source of elements
var 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 ascend(a, b) {
if (a < b)
return -1;
else if (a > b)
return 1;
return 0;
}
To use the six functions, include the "array.js" file that you made in the head of an HTML file like this:
<script type="text/JavaScript" src="array.js"></script>
Then you can write JavaScript to use the six functions just like you would use other built-in JavaScript functions as shown in this example code.
<script type="text/JavaScript">
function testArrays() {
document.open();
// Create the array listW.
var listW = [ 'apple', 'pear', 'plum', 'peach' ];
document.writeln('listW: ' + listW + '<br />');
// Use the linearSearch() function.
document.writeln('linearSearch()<br />');
var possible = 'plum';
if (listW.linearSearch(possible) != -1)
document.writeln('listW contains ' + possible);
else
document.writeln('listW does not contain ' + possible);
possible = 'cherry';
if (listW.linearSearch(possible) != -1)
document.writeln('listW contains ' + possible + '<br />');
else
document.writeln('listW does not contain ' + possible + '<br />');
// Use the addAll() function.
var listX = [ 'cherry', 'banana', 'apricot', 'mango' ];
listW.addAll(listX);
listW.sort();
document.writeln('addAll()<br />');
document.writeln('listW: ' + listW + '<br />');
// Use the binarySearch() function.
document.writeln('binarySearch()<br />');
possible = 'peach';
if (listW.binarySearch(possible) != -1)
document.writeln('listW contains ' + possible + '<br />');
else
document.writeln('listW does not contain ' + possible + '<br />');
possible = 'coconut';
if (listW.binarySearch(possible) != -1)
document.writeln('listW contains ' + possible + '<br />');
else
document.writeln('listW does not contain ' + possible + '<br />');
// Use the addAll() function.
var listY = [ 'elm', 'pine', 'rose', 'lilac' ];
var listZ = [ 'lilac', 'pine', 'fir' ];
listW.addAll(listY, listZ);
document.writeln('addAll()<br />');
document.writeln('listY: ' + listY + '<br />');
document.writeln('listZ: ' + listZ + '<br />');
document.writeln('listW: ' + listW + '<br />');
// Use the retainAll() function.
listY.retainAll(listZ);
document.writeln('retainAll()<br />');
document.writeln('listY: ' + listY + '<br />');
// Use the removeAll() function.
listY = [ 'elm', 'pine', 'rose', 'lilac' ];
listY.removeAll(listZ);
document.writeln('removeAll()<br />');
document.writeln('listY: ' + listY + '<br />');
// Use the unique() function.
listW.addAll(listX, listY, listZ);
listW.sort();
listW.unique();
document.writeln('unique()<br />');
document.writeln('listW: ' + listW + '<br />');
document.close();
}
</script>
Maia L.L.C. and its employees have used their best efforts in preparing this article. These efforts include the development, research, and testing of the theories and computer programs in this article to determine their correctness. Maia L.L.C. makes no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this article. Maia L.L.C. shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.