Return inex position of value in multi dim array

[Andrew Poulos]

If I'm searching for an occurance of a value in a multi-dimensional
array how can I get it's index returned as an array, if found? For
example, if:

foo = new Array();
foo = [1, 2, 3, [4, '4a'], 5, [6, 7, 8], 9, 10];

Array.prototype.findValue = function(val) {
// blah
}

var foundInd = foo.findValue(8);

Then searching for 8 returns [5, 2] and searching for 'fred' returns,
say, -1. It's seemed simple enough with a one dimensional array but I'm
stuck when the array is multi dimensional.
Andrew Poulos

[Michael Winter]

Andrew Poulos wrote:

If I'm searching for an occurance of a value in a multi-dimensional
array how can I get it's index returned as an array, if found? For
example, if:

foo = new Array();
foo = [1, 2, 3, [4, '4a'], 5, [6, 7, 8], 9, 10];
The first line isn't necessary. The array literal will create an array
object.
Array.prototype.findValue = function(val) {
// blah
}

var foundInd = foo.findValue(8);

Then searching for 8 returns [5, 2] and searching for 'fred' returns,
say, -1.

/* An array can either be an object or a function (varies by host),
* but any array should have the Array object as its constructor.
*/
function isArray(o) {
return ((o && ('object' == typeof o)) || ('function' == typeof o))
&& (Array == o.constructor);
}

/* The findValue method returns the first matching value
* using a depth-first search algorithm. If a match is
* found, the return value will be an array containing
* as many elements as necessary to subscript the match.
* If no match was found, -1 is returned.
*
* For example,
*
* [1, [2, 3], 3]
*
* searching for 3 will return [1, 1] not [2]. Searching
* for 4 will return -1.
*/
Array.prototype.findValue = function(v) {var i, j, n;
for(i = 0, n = this.length; i < n; ++i) {
/* If the current element is an array... */
if(isArray(this[i])) {
/* ...search it for matching values. */
j = this[i].findValue(v);
/* If the search was a success... */
if(-1 != j) {
/* ...create an array containing the index of
* the current element and append the result
* of searching the nested array.
*/
return [i].concat(j);
}
/* If the current element matches the search value,
* return an array containing the index of that
* element.
*/
} else if(this[i] == v) {return [i];}
}
/* If no matches have been found, return -1. */
return -1;
};

Instead of returning -1, you could also return an empty array. To do
that, modify the most-nested if statement to:

if(j.length) {

and the final return statement to:

return [];

You might also want to change the "else if" condition to use strict
equality. This would prevent '3' (string) from matching 3 (number).

[snip]

Hope that helps,
Mike

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

[Dr John Stockton]

JRS: In article <422627a4$0$19799$5a62ac22@per-qv1-newsreader-
01.iinet.net.au>, dated Thu, 3 Mar 2005 07:53:03, seen in
news:comp.lang.javascript, Andrew Poulos <ap*****@hotmail.com> posted :

If I'm searching for an occurance of a value in a multi-dimensional
array how can I get it's index returned as an array, if found? For
example, if:

foo = new Array();
foo = [1, 2, 3, [4, '4a'], 5, [6, 7, 8], 9, 10];

Array.prototype.findValue = function(val) {
// blah
}

var foundInd = foo.findValue(8);

Then searching for 8 returns [5, 2] and searching for 'fred' returns,
say, -1. It's seemed simple enough with a one dimensional array but I'm
stuck when the array is multi dimensional.

Recurse.

Scan an array; if the value is found stack the index and return; if an
array is found, stack the index and scan. If nothing is found, you
should get an empty stack. The stack can be an array.

Presumably you only want the first entry.
function Scan(F, B, V) { var j
for (j=0 ; j<F.length ; j++) {
if (F[j] == V) { B[B.length]=j ; return true }
if (typeof F[j] == 'object') {
B[B.length]=j /* push */
if (Scan(F[j], B, V)) return true
B.length-- /* pop */ }
}
}

foo = [1, 2, 3, [4, '4a'], 5, [6, 7, 8], 9, 10];
bar = []
val = 8
Scan(foo, bar, val)

Answer = bar // an array value [5,2]
It may need making safer; that assumes that an object entry can be
treated as an array. Under-tested.

Actually, this also serves; but it pushes and pops more often than
needed :-

function Scan(F, B, V) { var j
for (j=0 ; j<F.length ; j++) {
B[B.length]=j
if (F[j] == V) return true
if (typeof F[j] == 'object' && Scan(F[j], B, V)) return true
B.length-- }
}

Then there is :-

function Scan(F, B, V) { var j
for (j in F) {
B[B.length]=j
if (F[j] == V) return true
if (typeof F[j] == 'object' && Scan(F[j], B, V)) return true
B.length-- }
}

foo = [1, new Date(), 3, {k:[1,8]}, [4, '4a'], 5, [6,, 7, 8], 9, 10];

giving [3,k,1]

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 ©
<URL:http://www.jibbering.com/faq/> JL/RC: FAQ of news:comp.lang.javascript
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

[rh]

Michael Winter wrote:

<..>

/* An array can either be an object or a function (varies by host), * but any array should have the Array object as its constructor.
*/
Not that I doubt your note, but that seems to be in contravention of
ECMA 262/3 11.4.3 which says typeof == "function" implies native Object
with [[Call]] implementation.
function isArray(o) {
return ((o && ('object' == typeof o)) || ('function' == typeof o)) && (Array == o.constructor);
}

Perhaps the isArray global requirement, and the accompanying bit of
twisting, can be circumvented as in the following (minimally tested):

Array.prototype.findValue = function( val ) {
for ( var k = 0, o, ret; k < this.length; k++ ) {
if ( (o = this[k]) === val) return [k];
if (o && o.findValue === arguments.callee
&& (ret = o.findValue( val )) ) return ret.unshift( k ), ret;
}
}

<..>

../rh

[Michael Winter]

rh wrote:

Michael Winter wrote:

<..>

/* An array can either be an object or a function (varies by
* host), but any array should have the Array object as its
* constructor.
*/
Not that I doubt your note, but that seems to be in contravention
of ECMA 262/3 11.4.3 which says typeof == "function" implies native
Object with [[Call]] implementation.

I might have been thinking of something else. For example, IE seems to
think that the getElementById method is an object rather than a
function. Anyway, at worst the user has to download an extra bit of an
expression which is never executed.

[snip]
Perhaps the isArray global requirement,

The isArray function doesn't have to be global...

[snip]

Mike

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

[rh]

Michael Winter wrote:

rh wrote:

Michael Winter wrote:

<..>

/* An array can either be an object or a function (varies by
>> * host), but any array should have the Array object as its
>> * constructor.
>> */
Not that I doubt your note, but that seems to be in contravention
of ECMA 262/3 11.4.3 which says typeof == "function" implies native
Object with [[Call]] implementation.

I might have been thinking of something else.

It may be that it's evidenced in some browser/host that pre-dates the
standard. If it does exist somewhere, it would be nice to know of a
concrete example. Anything's possible, I suppose, but it would seem
particularly strange to arise as a host dependency.

<..>
Anyway, at worst the user has to download an extra bit of an
expression which is never executed.

The concern isn't there. It's the inclusion of "funny" tests, which
possibly no-one knows if, or why, they're necessary.
[snip]

Perhaps the isArray global requirement,

The isArray function doesn't have to be global...

Did you forget to put a smiley there? ;-)

../rh