Six Functions Missing From Javascript Arrays

Tue, 17 Jun 2008 02:04:30 PST

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, and removeAll, that were not included in the Array class. This article shows you how to add these four useful functions plus two other convenience functions, addAll and contains, 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.

Descriptions of the Functions

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 contains function is similar to linearSearch. However, the contains function returns true if the key is stored in the array and returns false otherwise. This is different from the linearSearch and binarySearch functions which both return the index where the key is stored 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.

The Six Missing Functions

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 = simpleCompare;

}

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 -1.

* Assumes this array is already sorted. */

Array.prototype.binarySearch = function(key, compare) {

if (typeof(compare) == "undefined") {

compare = simpleCompare;

}

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 -1;

}

/** Returns true if this array contains

* key; otherwise returns false. */

Array.prototype.contains = function(key, compare) {

return this.linearSearch(key, compare) != -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 = simpleCompare;

}

for (var i = 0; i < this.length; i++) {

if (arr.contains(this[i], compare) == false) {

var end = i + 1;

while (end < this.length &&

arr.contains(this[end], compare) == false) {

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 = simpleCompare;

}

var i = 0;

while (i < this.length) {

if (arr.contains(this[i], compare)) {

var end = i + 1;

while (end < this.length &&

arr.contains(this[end], compare)) {

end++;

}

this.splice(i, end - i);

}

else {

i++;

}

/** Compares two objects using

* built-in JavaScript operators. */

function simpleCompare(a, b) {

if (a < b)

return -1;

else if (a > b)

return 1;

return 0;

}

Using the Six Missing Functions

To use the six functions, include the array.js file that you made in the head of an HTML file like this:

Then you can write JavaScript to use the functions similar to this:

function test() {

document.open();

var setX = [ "apple", "pear", "plum", "peach" ];

document.writeln('setX: " + setX + "<br />');

var possible = "plum";

document.writeln('setX.contains(' + possible + ") " +

setX.contains(possible) + "<br />");

possible = "cherry";

document.writeln('setX.contains(' + possible + ") " +

setX.contains(possible) + "<br />");

var setW = [ "cherry", "banana", "apricot", "mango" ];

setX.addAll(setW);

setX.sort();

document.writeln('<br />');

document.writeln('setX: " + setX + "<br />');

possible = "peach";

if (setX.binarySearch(possible) != -1)

document.writeln('setX contains " + possible + "<br />');

else

document.writeln('setX does not contain " + possible + "<br />');

possible = "coconut";

if (setX.binarySearch(possible) != -1)

document.writeln('setX contains " + possible + "<br />');

else

document.writeln('setX does not contain " + possible + "<br />');

var setY = [ "elm", "pine", "rose", "lilac" ];

var setZ = [ "lilac", "pine", "fir" ];

document.writeln('<br />');

document.writeln('setY: " + setY + "<br/>');

document.writeln('setZ: " + setZ + "<br/>');

setX.addAll(setY, setZ);

document.writeln('setX.addAll(setY, setZ): " + setX + "<br />');

setY = [ "elm", "pine", "rose", "lilac" ];

setY.retainAll(setZ);

document.writeln('setY.retainAll(setZ): " + setY + "<br />');

setY = [ "elm", "pine", "rose", "lilac" ];

setY.removeAll(setZ);

document.writeln('setY.removeAll(setZ): " + setY + "<br />');

document.close();

}

</script>

AutoCAD Tutorial 4: Union, Subtract and Intersect Tools

Thu, 26 Jul 2007 08:05:01 PST

Uniting objects allows for multiple objects to become a single object, making modelling less messier and much neater.

Subtracting allows complex objects like a rectangle with a hole through it to be made.

Intersect is used for when 2 objects are drawn over each other and the part(s) where the objects overlapped are kept.

Union:

In this picture, I have 2 rectangles, a wedge and a cone:

Selected, the lines would appear like this:

Now that looks really messy doesn't it? To change this, select the union tool OR type “_union” then select all the objects:

Then we press ENTER. All these objects will become one big object:

Subtract:

In this picture, I have a normal rectangle:

Now I'm going to draw another one intersecting it:

I'm going to make a rectangle with a hole through it like a hole for a door. In order to do this I could draw a lots of rectangles or I could simply use the subtract tool. To do this, click on the subtract tool or type in “_subtract”.

There is a certain order you must select objects. Select the object you are going to subtract FROM, in this case the taller rectangle. Then you press ENTER. Now you select the object you are going to use to subtract, here it is the smaller rectangle. Then you press ENTER and you are left with this:

Intersect:

In this picture I have a sphere and a rectangle intersecting:

For some odd reason I want the part that is overlapping ONLY. To do this, select the intersect tool or type “_intersect”. I then select both objects and press ENTER and I'm left with this:

I hope you have learnt something from this tutorial!

Note: If you accidentally select the wrong object, you can unselect it by holding SHIFT and clicking on the selected object.