<a href="https://bytes.com/topic/javascript/answers/150205-iterating-sparse-arrays">Iterating sparse arrays

Christopher Benson-Manica wrote:

If an array is sparse, say something like

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

is there a way to iterate through the entire array?

<snip>

for (var c = foo.length; c--; ){
... // using foo[c]
}

The values at indexes 0 to 2 will return Undefined values. The named
properties are not related to the Arrayness of the Array object but
rather to its Objectness. As such they should not be considered relevant
to a desire to iterate through the "entire array".

Richard.

Jul 23 '05 #2

Douglas Crockford

> If an array is sparse, say something like

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

is there a way to iterate through the entire array?

It is incorrect to use an array when the keys are non-integers. If you
have keys like 'bar' and 'quux', you should be using an object. You can
then use the for..in statement to iterate through them.

var foo = {};
foo[3] = 4;
foo.bar = 'baz';
foo['quux'] = 'moo';

for (key in foo) {
...
}

See http://www.crockford.com/javascript/survey.html

Jul 23 '05 #3

Robert

In article <cs**********@chessie.cirr.com>,
Christopher Benson-Manica <at***@nospam.cyberspace.org> wrote:

If an array is sparse, say something like

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

is there a way to iterate through the entire array?

Yes.

Note: The length property includes the numeric indexes. Since three is
the highest index, the length property has a value of four.

Robert

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Sparse array</title>

<script type="text/javascript">

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

var accumulate = "";

for (var i in foo)
{
accumulate += "foo["+ i + "] = " + foo[i] + "; ";
}

alert(accumulate);

alert("number of elements in foo = " + foo.length);
</script>
</head>
<body>
<p>Demonstrate retrieving all set array values.</p>
</body>

Jul 23 '05 #4

Robert

In article <d9**************************@msgid.meganewsserver s.com>,
Douglas Crockford <no****@covad.net> wrote:

If an array is sparse, say something like

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

is there a way to iterate through the entire array?

It is incorrect to use an array when the keys are non-integers.

I think this is too strong of a statement since the array declaration
supports string values as references. See my post to this thread for
the example code.

When you declare an object an array your javascript supports methods
like pop and the length property with the array object. When you
declare a variable an object you get fewer methods and properties. The
author of the javascript code should decide what is more appropriate.

I do not think we can tell from the segment of code shown what is more
appropriate.

The object declaration does allow for a more compact declaration:

var foo= { 3: 4, bar: "baz", "quux": "moo" };
Robert

Jul 23 '05 #5

Douglas Crockford

>>It is incorrect to use an array when the keys are non-integers.

I think this is too strong of a statement since the array declaration
supports string values as references.

Wrong is wrong even if you do not understand the difference.

Jul 23 '05 #6

Robert wrote:
[...]

When you declare an object an array your javascript supports methods
like pop and the length property with the array object.
What do push and pop do if there are non-integer keys in the array?

[...] I do not think we can tell from the segment of code shown what is more
appropriate.

With better designed programming languages, associative arrays distinguish
between methods and data, so you can have a key "push" which doesn't
conflict with the method push(). Alas, Javascript doesn't seem to have this
concept, which is a shame.

It's usually considered good practice (in other languages with similar
semantics to Javascript) that associative arrays are used for storing
stupid data and objects are used for storing smart data; that is, it's
intended that the data gets modified by calling methods on the object.

--
+- David Given --McQ-+ (base 10) = (base pi)
| dg@cowlark.com | 1 = 1; 2 = 2; 3 = 3
| (dg@tao-group.com) | 3.1415926... = 10.0
+- www.cowlark.com --+ 4 = 12.201220211...

Jul 23 '05 #7

Robert

My understanding that a numeric index of an array is converted to a
string then looked up in the array. The code below seems to
demonstrate this:

var list = [];
list[1] = "abc";
alert("Index as a number one and the string one is " +
(list["1"] == list[1] ));

What I am staying is that you need to use the data structure the best
represents your intent.

Robert

Jul 23 '05 #8

Robert

In article <Ms***************@newsfe5-gui.ntli.net>,
David Given <dg@cowlark.com> wrote:

With better designed programming languages, associative arrays distinguish
between methods and data, so you can have a key "push" which doesn't
conflict with the method push(). Alas, Javascript doesn't seem to have this
concept, which is a shame.
This is unfortunate. Seems like 'informal' languages win out in market
share over 'formal' one.
It's usually considered good practice (in other languages with similar
semantics to Javascript) that associative arrays are used for storing
People freak out over the term 'associative arrays' in this forum.
'cause it's not in the standard they stay.
stupid data and objects are used for storing smart data; that is, it's
intended that the data gets modified by calling methods on the object.

Robert

Jul 23 '05 #9

Christopher Benson-Manica

Douglas Crockford <no****@covad.net> spoke thus:

It is incorrect to use an array when the keys are non-integers. If you
have keys like 'bar' and 'quux', you should be using an object. You can
then use the for..in statement to iterate through them. var foo = {};
foo[3] = 4;
foo.bar = 'baz';
foo['quux'] = 'moo'; for (key in foo) {
...
}

That is a beautiful thing - thank you for showing me the light!

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Jul 23 '05 #10

Robert wrote:
[...]

It's usually considered good practice (in other languages with similar
semantics to Javascript) that associative arrays are used for storing

People freak out over the term 'associative arrays' in this forum.
'cause it's not in the standard they stay.

Having done some experimentation... you're right, they aren't true
associative arrays.

a = new Array();
b = {value:"object1"};
c = {value:"object2"};
a[b] = 42;
a[c] = 42;
for (i in a) alert(a[i])

How many alert boxes do you get? One. It would appear that Array is hashing
both objects to the same value. In fact...

for (i in a) alert(i.value)

....produces 'undefined', so it's not even storing a real object.

Using an object instead of an array for 'a' does the same thing. That sucks.
If it doesn't work properly with values that aren't a particular type, it
should damn well produce a run-time error.

Here we go. ECMAscript specification, 15.2.4.5: property names seem to have
toString called on them before hashing. Which means that both object keys
are turning into '[object Object]'. That's grotesque...

....and Arrays are just Objects with some utility methods, so the same thing
applies there.

I'm going to need a real associative array; I think I can come up with a
reasonably efficient one using two Arrays. Anyone interested?

--
+- David Given --McQ-+ "I don't like the thought of her hearing what I'm
| dg@cowlark.com | thinking." "*No-one* likes the thought of hearing
| (dg@tao-group.com) | what you're thinking." --- Firefly, _Objects in
+- www.cowlark.com --+ Space_

Jul 23 '05 #11

On Wed, 19 Jan 2005 14:25:24 -0500, Robert <rc*******@my-deja.com> wrote:

[snip]

People freak out over the term 'associative arrays' in this forum.

No-one has "freaked out" over the term, however there is disagreement with
regard to its suitability.

ECMAScript provides a syntax that resembles associative array usage and
does, to a certain extent, meet what is expected of the data type.
However, all objects in ECMAScript have predefined members and these may
cause problems, especially as you cannot determine (without supporting
code) whether a member is predefined or part of the "associative array".
There are other issues:

- You cannot reliably enumerate elements within the "associative
array".

Whilst a for..in statement will enumerate all properties within an
object, it may not be possible to determine what has been added and
what was predefined. Though I haven't encountered a user agent that
allows a host- or specification-defined property to be enumerated,
that (1) doesn't mean the former would never happen, and (2) doesn't
account for any properties added to the prototype of Object or a
more specific object (such as Array, if you decided to use that for
some reason).

- You cannot determine the number of elements within an "associative
array".

Though this might not be important in all instances, this feature
is not available in ECMAScript.

The main objection I have to the term is that it leads to confusion.
Examples such as

var hash = new Array();
hash['property'] = value;

do nothing but instill the mistaken belief that arrays can be subscripted
using arbitrary strings. The same effect could be achieved with

var hash = new Object();
hash.property = value;

or

var hash = {property : value};

but this isn't shown.

Instead of understanding the actual mechanics - which really are quite
simple - new programmers believe a feature exists where in fact it does
not.

ECMAScript allows one to use square brackets to access the
properties of an object in addition to the normal dot notation
form. The use of expressions within the square bracket property
accessors provides a great deal of flexibility and allows something
akin to associative arrays or hash tables using nothing more than
an object. However, there are some caveats to this usage.

Fleshed out to include descriptions of the topics mentioned in that
paragraph and clear code examples should provide an accurate
understanding. The reader would know about the square bracket property
accessors and how they can be used to construct property names (hopefully
reducing the incidence of eval usage), *and* how objects can be used to
implement a basic hash table. The article
(<URL:http://www.jibbering.com/faq/faq_notes/square_brackets.html>) in the
FAQ notes certainly goes a long way to accomplish this.

[snip]

Mike

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

Jul 23 '05 #12

On Thu, 20 Jan 2005 15:06:45 GMT, David Given <dg@cowlark.com> wrote:

In fact...

for (i in a) alert(i.value)

...produces 'undefined',
It should in every case. The value assigned to i on each iteration is the
property name as a string, and strings don't have a value property. If you
want the value of the enumerated property, use

a[i]
Using an object instead of an array for 'a' does the same thing.
Again, it should. This whole business has nothing to do with arrays. See
my other post (and the link therein).
I'm going to need a real associative array;

There are several in the archives. Mine is at
<URL:http://www.mlwinter.pwp.blueyonder.co.uk/clj/hash.js> (14.4KB). This
particular implementation allows objects to be true keys (rather than only
their toString value). However, it's also more readable than efficient (or
small). If you do end up using it, at the very least I'd advise you to
make a copy, remove methods that you aren't using (including the Iterator,
if appropriate) and run it through JSMin
(<URL:http://www.crockford.com/javascript/jsmin.html>). That'll take out
about 10.5KBs of comments and whitespace. If you want to be adventurous,
you could also shorten the variable names - that'll shave off another
kilobyte or so.

I'm terrible at formal testing procedures, so the script hasn't undergone
any, but playing with it hasn't uncovered any errors (unlike the last time
I uploaded it[1] :-().

Mike
[1] My apologies for asking for a check of a blatently non-functioning
script.

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

Jul 23 '05 #13

Michael Winter wrote:
[...]

http://www.mlwinter.pwp.blueyonder.co.uk/clj/hash.js

I'll certainly use this; ta. However, looking at the code, you seem to be
using toString() as your hash function. This will mean that all objects
hash to the same value, which means that in the common case of...

twoWayHashTable = new AssociativeArray()
for (lots)
{
twoWayHashTable.put(key, value);
twoWayHashTable.put(value, key);
}

....then if value is an object, I'm going to end up with a vast linear list
as one of the hash chains.

Does Javascript have a real hash function? I couldn't find one, and I notice
that:

a = {}
b = {}
ASSERT(a != b)
ASSERT(!(a < b))
ASSERT(!(a > b))

Aaargh. This is, of course, completely useless for constructing trees.

--
+- David Given --McQ-+ "I don't like the thought of her hearing what I'm
| dg@cowlark.com | thinking." "*No-one* likes the thought of hearing
| (dg@tao-group.com) | what you're thinking." --- Firefly, _Objects in
+- www.cowlark.com --+ Space_

Jul 23 '05 #14

On Thu, 20 Jan 2005 16:48:20 GMT, David Given <dg@cowlark.com> wrote:

[...] looking at the code, you seem to be using toString() as your hash
function.
Yes, as their's no native alternative (answering your later question). One
could force client code to implement a hashCode method like Java, but that
would add (*way*) too much of a burden.
[...] I'm going to end up with a vast linear list [...]
True, iff all of the objects have the same toString result[1], but I seem
to remember good performance (see the end of
<URL:http://groups.google.co.uk/groups?selm=opsilrs6aax13kvk%40atlantis>).

[snip]
a = {}
b = {}
ASSERT(a != b)
Object equality is based on references to the object itself, not its
content. References are only equal if they refer to the same object or a
joined object (algorithm: 11.9.3; joined objects 13.1.2).
ASSERT(!(a < b))
ASSERT(!(a > b))

In relational comparisons (11.8.5), the internal ToPrimitive operator
(9.1) is called on both objects with the hint, Number. If a valueOf method
is defined, the return value is used when comparing, otherwise toString is
used (8.6.2.6).

Mike

And here I was thinking I'd take a break from Usenet...
[1] If they're your own objects, you could implement a toString method
that generates a return based on the content of that object.
Alternatively, you could just generate random numbers:

function MyObject() {
var id = String((Math.random() % 1) * 100000);

this.toString = function() {return id;};
}

Although there would be some clashes, it would prevent a single list and
should have relatively little overhead.

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

Jul 23 '05 #15

Michael Winter wrote:
<snip>

[1] If they're your own objects, you could implement a toString
method that generates a return based on the content of that object.
Alternatively, you could just generate random numbers:

function MyObject() {
var id = String((Math.random() % 1) * 100000);

this.toString = function() {return id;};
}

Although there would be some clashes, it would prevent a single
list and should have relatively little overhead.

I would have thought a non-repeating sequence would avoid clashes:-

(function(){
var baseNum = 1; //or maybe (new Date()).getTime();
Object.prototype.toString = function(){
var id = ' _$'+(++baseNum);
return (this.toString = function(){
return id;
})();
};
})();

Richard.

Jul 23 '05 #16

On Thu, 20 Jan 2005 21:48:46 -0000, Richard Cornford
<Ri*****@litotes.demon.co.uk> wrote:

[snip]

I would have thought a non-repeating sequence would avoid clashes:-

It would, but the issue isn't really avoiding clashes altogether but
reducing the length of the internal linked lists. A random return value
just happened to be the first thing that entered my mind.

[snip]

Mike

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

Jul 23 '05 #17

Michael Winter wrote:
[...]

ASSERT(a != b)

Object equality is based on references to the object itself, not its
content. References are only equal if they refer to the same object or a
joined object (algorithm: 11.9.3; joined objects 13.1.2).
ASSERT(!(a < b))
ASSERT(!(a > b))

Oh, I realise (any other behaviour would be broken), but I wouldn't expect
*all* of the above assertions to be true...

Here's an approach:

_id = 0
_ids = []
_data = []

function put(key, value)
{
var i = _id++;
key[" id"] = i;
_ids[i] = value;
_data[i] = value;
}

function get(key)
{
var i = key[" id"];
return _data[i];
}

function remove(key)
{
var i = key[" id"];
delete key[" id"];
delete _ids[i];
delete _data[i];
}

Only works with object keys, but it'd be easy enough to strings and integers
by using a conventional array for keys of those type. The " id" string
would need to be unique per associative array so that you could use the
same key in multiple associative arrays. The _ids array is necessary to
prevent garbage collection of forgotten keys.

--
+- David Given --McQ-+ "...it's not that well-designed GUI's are rare,
| dg@cowlark.com | it's just that the three-armed users GUI's are
| (dg@tao-group.com) | designed for are rare." --- Mike Uhl on a.f.c
+- www.cowlark.com --+

Jul 23 '05 #18

David Given wrote:

Michael Winter wrote:
[...] <...>
Here's an approach:

_id = 0
_ids = []
_data = []

function put(key, value)
{
var i = _id++;
key[" id"] = i;
_ids[i] = value;
_data[i] = value;
}

function get(key)
{
var i = key[" id"];
return _data[i];
}

function remove(key)
{
var i = key[" id"];
delete key[" id"];
delete _ids[i];
delete _data[i];
}

Only works with object keys, but it'd be easy enough to strings and integers by using a conventional array for keys of those type. The " id" string would need to be unique per associative array so that you could use the same key in multiple associative arrays. The _ids array is necessary to prevent garbage collection of forgotten keys.

Similar an updated version of the Hashtable constructor that I put
together yesterday. It should handle keys of all types, based on a
modification of Richard's *very neat* idea of assigning a univesal
unique id to the objects. Richards id creation appeared to be limited
to objects that didn't have their own version of "toString", which
would eliminate "Array", "Date", etc. objects as keys, if I followed it
correctly.

[I'm out for the day, but will perhaps get something posted later].
.... /rh

Jul 23 '05 #19

rh wrote:
<...>

Similar an updated version of the Hashtable constructor that I put
together yesterday. It should handle keys of all types, based on a
modification of Richard's *very neat* idea of assigning a univesal
unique id to the objects. Richards id creation appeared to be limited
to objects that didn't have their own version of "toString", which
would eliminate "Array", "Date", etc. objects as keys, if I followed it correctly.

[Sorry for the bad grammar/spelling - I was in a rush :)]

This (very lightly tested) version can be found at:
<url:http://www3.telus.net/rhall/Misc/DGHash.js>

../rh

Jul 23 '05 #20

Michael Winter wrote:

On Wed, 19 Jan 2005 14:25:24 -0500, Robert <rc*******@my-deja.com> wrote:
[snip]
People freak out over the term 'associative arrays' in this forum.
No-one has "freaked out" over the term, however there is disagreement

with regard to its suitability.

It seems evident from the discussions on the issue, though, that there
are a number of different conceptions of what constitutes an
"associative array". That in itself is generally sufficient to ensure
there won't be agreement.
ECMAScript provides a syntax that resembles associative array usage and does, to a certain extent, meet what is expected of the data type.
Some would even say to a "high" extent. ;-)
However, all objects in ECMAScript have predefined members and these may cause problems, especially as you cannot determine (without supporting code) whether a member is predefined or part of the "associative array". There are other issues:

- You cannot reliably enumerate elements within the "associative
array".

A fundamental definition of associative array (at least mine) doesn't
include enumeration -- the supported operations are insert, replace,
remove and lookup. So the question, it seems to me, is whether you can
reliably do lookup.
Whilst a for..in statement will enumerate all properties within an object, it may not be possible to determine what has been added and what was predefined. Though I haven't encountered a user agent that allows a host- or specification-defined property to be enumerated, that (1) doesn't mean the former would never happen, and (2) doesn't account for any properties added to the prototype of Object or a
more specific object (such as Array, if you decided to use that for some reason).

In the case of lookup, it means that one cannot blithely assume that a
retrieval from an object corresponds to a [key,data] pair within the
"associative array". That is a major problem, and it is something that
all users must be aware of (and of course we know they are not).

Can it be reliably determined whether a key-lookup returns a
pre-defined property outside the "associative array"? Yes, provided
that hasOwnProperty is supported, and provided that string has not been
used as a key in the "associative array". And those conditions are
easy to check (and, if necessary, but perhaps not quite so easy, to
supplant).
- You cannot determine the number of elements within an "associative array".

Though this might not be important in all instances, this feature
is not available in ECMAScript.

The main objection I have to the term is that it leads to confusion. Examples such as

var hash = new Array();
hash['property'] = value;

do nothing but instill the mistaken belief that arrays can be subscripted using arbitrary strings.
Agreed, that is entirely wrong.
The same effect could be achieved with
var hash = new Object();
hash.property = value;

or

var hash = {property : value};

but this isn't shown.

Instead of understanding the actual mechanics - which really are quite simple - new programmers believe a feature exists where in fact it does not.

On the other hand, if programmers wish to understand Objects in
ECMAScript, they need to understand the close relationship between
Objects and their foundation in associative arrays. Objects are, in
fundamental concept, simply linked associative arrays.

The following demonstrates the battle you're waging is likely lost:

<url:http://en.wikipedia.org/wiki/Associative_array#JavaScript>

The good news, perhaps, is that you can edit it. :-)
<...>

Regards,

.../rh

Jul 23 '05 #21

rh wrote:
<snip>

Can it be reliably determined whether a key-lookup returns a
pre-defined property outside the "associative array"? Yes,
provided that hasOwnProperty is supported, and provided that
string has not been used as a key in the "associative array".
And those conditions are easy to check (and, if necessary,
but perhaps not quite so easy, to supplant).

<snip>

I have never seen - hasOwnProperty - as a solution to this problem as it
still leaves the code subject to the possibility that the language
implementation is exposing internal properties of the object instances
(rather than their prototypes). If that was an unusual, or unexpected,
situation then it probably could be disregarded and the transgressing
implementation dismissed as fatally broken, but ECMA 262 doesn't
explicate forbid the possibility and Mozilla demonstrates its reality.
Try:-

var t = {};
alert(
t.hasOwnProperty('__proto__')+'\n'+
t.hasOwnProperty('__parent__')+'\n'+
'');

- in a Mozilla/Gecko browser and see two properties of an object
instance that were never explicitly created by script code.
Konqueror/Safari offers another set of similar object instance
properties.

Unfortunately, using a javascript object for the storage of name/value
(or key/data, if you prefer) pairs is not safe if the names/keys are
expected to be arbitrary. Hence the preference for implementing such
storage objects in a way that takes control of the arbitrary name/key
strings and shifts then into a 'safe' set. How safe that 'safe' set is
remains a subject for debate.

Richard.

Jul 23 '05 #22

Richard Cornford wrote:

rh wrote:
<snip>
Can it be reliably determined whether a key-lookup returns a
pre-defined property outside the "associative array"? Yes,
provided that hasOwnProperty is supported, and provided that
string has not been used as a key in the "associative array".
And those conditions are easy to check (and, if necessary,
but perhaps not quite so easy, to supplant). <snip>

I have never seen - hasOwnProperty - as a solution to this problem as

it still leaves the code subject to the possibility that the language
implementation is exposing internal properties of the object instances (rather than their prototypes). If that was an unusual, or unexpected, situation then it probably could be disregarded and the transgressing
implementation dismissed as fatally broken, but ECMA 262 doesn't
explicate forbid the possibility and Mozilla demonstrates its reality. Try:-

var t = {};
alert(
t.hasOwnProperty('__proto__')+'\n'+
t.hasOwnProperty('__parent__')+'\n'+
'');

- in a Mozilla/Gecko browser and see two properties of an object
instance that were never explicitly created by script code.
Konqueror/Safari offers another set of similar object instance
properties.

Interesting, and how dastardly of them :-(! So in your interpretation
of ECMA-262/3:

[15.2.5 Properties of Object Instances

Object instances have no special properties beyond those inherited from
the Object prototype object.]

are you saying because the word "special" is there, that brower
manufacturer's implementations can add properties to Object instances,
as long as they're not "special", and remain in conformance with the
standard?

Surely, anything added by the language implementation that affects the
usage behaviour of an object instance is "special".

Nonetheless, I note that an attempt to delete the properties given
above returns false (presumabley because they have a DontDelete
attribute). That makes these particular properties very much "special".
Moreover, if you make an assignment to these properties, no assignment
is made. That makes these properties "special".

And further, these properties are not enumerable. That also makes them
"special".

Clearly it's a transgression of the standard!
Unfortunately, using a javascript object for the storage of name/value (or key/data, if you prefer) pairs is not safe if the names/keys are
expected to be arbitrary. Hence the preference for implementing such
storage objects in a way that takes control of the arbitrary name/key
strings and shifts then into a 'safe' set. How safe that 'safe' set is remains a subject for debate.

I'm not sure there's any great argument about using a controlled
approach, after all I did produce a couple of versions of Hashtable.
For a completely arbitrary set of keys (presumably, with control and
some work you can tranform the names of the "bad" keys to something
non-conflicting and use some separate storage).

However, it should be kept in mind that the problem of key conflicts
doesn't just affect the presumption of "associative arrays" at the
language level. It affects all Object usage in ECMAScript. The fact
that you may assign a key/value (such as the key __proto__, or some
other yet to be revealed key) and have nothing happen is a matter for
some concern.

So, facing certain realities, that now leaves the question of how to
determine which keys are going to be problematic, in the event you
actually want to test. I'd still be inclined to use "hasOwnProperty",
but now in combination with "isEnumerable". No guarantee there, but
should be within epsilon (some current or future crap added to the
object instances, potentially remaining an issue).

../rh

Jul 23 '05 #23

rh wrote:

Richard Cornford wrote: <snip>
... ECMA 262 doesn't explicate forbid the possibility ... <snip> Try:-

var t = {};
alert(
t.hasOwnProperty('__proto__')+'\n'+
t.hasOwnProperty('__parent__')+'\n'+
'');

- in a Mozilla/Gecko browser and see two properties of an
object instance that were never explicitly created by
script code.

<snip> Interesting, and how dastardly of them :-(! So in your
interpretation of ECMA-262/3:

[15.2.5 Properties of Object Instances

Object instances have no special properties beyond those
inherited from the Object prototype object.]

are you saying because the word "special" is there, that
brower manufacturer's implementations can add properties
to Object instances, as long as they're not "special", and
remain in conformance with the standard?
No, I am referring to:-

<quote cite="ECMA 262 3rd edition: Section 2 "Conformance",
3rd paragraph">
| A conforming implementation of ECMAScript is permitted to
| provide additional types, values, objects, properties, and
| functions beyond those described in this specification. In
| particular, a conforming implementation of ECMAScript is
| permitted to provide properties not described in this
| specification, and values for those properties, for objects
| that are described in this specification.
</quote>

- Which implies that Mozilla/Gecko javascript implementations are fully
conformant with ECMA 262 in this respect.
Surely, anything added by the language implementation that
affects the usage behaviour of an object instance is
"special". <snip>

__proto__ and __parent__ are very 'special' properties, without any
doubt, but they don't appear to be ruled out by the specification.
And further, these properties are not enumerable. That also
makes them "special".

Clearly it's a transgression of the standard!
My reading of ECMA 262 suggests that they are allowed.

<snip> However, it should be kept in mind that the problem of key
conflicts doesn't just affect the presumption of "associative
arrays" at the language level. It affects all Object usage
in ECMAScript. The fact that you may assign a key/value (such
as the key __proto__, or some other yet to be revealed key)
and have nothing happen is a matter for some concern.
The fact that objects may have unspecified and unexpected properties
certainly should be taken into account. However, the implementers of
ECMAScirpt do not appear to be suicidal in the property names they add.
Generally, a normal camel-case property name will not prove problematic,
it seems only necessary to avoid certain unusual character combinations
such as those starting and ending with '__' or '[[' and ']]'. Which is
why the problem becomes significant when ECMAScript objects are to be
used to store values with truly arbitrary name/key strings.
So, facing certain realities, that now leaves the question
of how to determine which keys are going to be problematic,
in the event you actually want to test. I'd still be inclined
to use "hasOwnProperty", but now in combination with
"isEnumerable". No guarantee there, but should be within
epsilon (some current or future crap added to the object
instances, potentially remaining an issue).

I still prefer the other strategy.

Richard.

Jul 23 '05 #24

Richard Cornford wrote:

rh wrote:
Richard Cornford wrote: <...>
No, I am referring to:-

<quote cite="ECMA 262 3rd edition: Section 2 "Conformance",
3rd paragraph">
| A conforming implementation of ECMAScript is permitted to
| provide additional types, values, objects, properties, and
| functions beyond those described in this specification. In
| particular, a conforming implementation of ECMAScript is
| permitted to provide properties not described in this
| specification, and values for those properties, for objects
| that are described in this specification.
</quote>

- Which implies that Mozilla/Gecko javascript implementations are fully conformant with ECMA 262 in this respect.

Ah, but I think great care is required in interpretation of the
specification. Yes, the above says implementers of the language can add
properties/values to all objects. But some objects, not all, are
restricted by the body of the specification. In particular, 15.2.5,
says that if an implementer cannot add properties/values directly to an
Object object -- that can only be done through additions to the Object
prototype.

In other words, both must apply. Any other interpretation, it seems to
me, throws the standard into contradiction, because there's nothing
that says one has precedence over the other.

Therefore my continued contention would be that Mozilla/Gecko
javascript implementations **are not** in conformance with ECMA 262
with respect to __proto__ and __parent__.

[Non-special objects can't be added to an Object object by the
implementer because the built-in --> native object specification
doesn't allow for it (although my check here is at best cursory).]
Surely, anything added by the language implementation that
affects the usage behaviour of an object instance is
"special".

<snip>

<...> <snip>
<...>
The fact that objects may have unspecified and unexpected properties
certainly should be taken into account. However, the implementers of
ECMAScirpt do not appear to be suicidal in the property names they add. Generally, a normal camel-case property name will not prove problematic, it seems only necessary to avoid certain unusual character combinations such as those starting and ending with '__' or '[[' and ']]'. Which is why the problem becomes significant when ECMAScript objects are to be
used to store values with truly arbitrary name/key strings.

They may not be suicidal -- they remain a bunch of dastards in my book
:-).

So, facing certain realities, that now leaves the question
of how to determine which keys are going to be problematic,
in the event you actually want to test. I'd still be inclined
to use "hasOwnProperty", but now in combination with
"isEnumerable". No guarantee there, but should be within
epsilon (some current or future crap added to the object
instances, potentially remaining an issue).

Given that propertyIsEnumerable doesn't venture into the prototype
chain, a hasOwnProperty check would seem to redundant. So my later
suggestion would be to simply replace the hasOwnProperty with a
propertyIsEnumerable check;
I still prefer the other strategy.

Well everone gets to choose their preference, but I haven't seen much
of a case for a more complex solution.

../rh

Jul 23 '05 #25

On 23 Jan 2005 10:35:44 -0800, rh <co********@yahoo.ca> wrote:

[snip]

A fundamental definition of associative array (at least mine) doesn't
include enumeration
I know, which is why I didn't say enumeration was part of the definition.
I remember the previous debate well. However, it seems there is a common
desire to enumerate them and this may be unreliable unless you take the
operation into your own hands.
So the question, it seems to me, is whether you can reliably do lookup.
Yes, provided that supporting code is used to perform it. However, I'd
argue that this necessity clearly means that "associative arrays" cannot
be deemed part of the language.

[snip]
The following demonstrates the battle you're waging is likely lost:
I'm certain that there is a number of sites masquerading as references
which "teach" this topic in a misleading way. That in itself would already
signal the battle is lost.
<url:http://en.wikipedia.org/wiki/Associative_array#JavaScript>
I wouldn't say that's particularly devastating. It even mentions that a
prototype will interfere affect the properties available, however it would
probably take some careful thinking for the reader to realise what the
implications are.
The good news, perhaps, is that you can edit it. :-)

If the aim was to actively teach the concept, perhaps I might (though I
wouldn't feel particularly comfortable doing so).

Mike

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

Jul 23 '05 #26

Michael Winter wrote:

On 23 Jan 2005 10:35:44 -0800, rh <co********@yahoo.ca> wrote:

[snip]

<...>

So the question, it seems to me, is whether you can reliably do lookup.
Yes, provided that supporting code is used to perform it. However, I'd argue that this necessity clearly means that "associative arrays" cannot be deemed part of the language.

"deemed part of the language" is too strong. It has more to do with
availability of very useful functionality that is relatively
widely-known as a part of basic computing.

In the context of the language itself, the volume of material that you
are producing in expounding upon the absence of "associative arrays"
from the language, is really testimony to tremendous missed opportunity
of having string-based associative arrays native to the language --
there should be, but there is not, a way to turn off an object's (at
the very least an Object object's) prototype chain search.
[snip]
The following demonstrates the battle you're waging is likely lost:
I'm certain that there is a number of sites masquerading as

references which "teach" this topic in a misleading way. That in itself would already signal the battle is lost.

But there are many that talk about "Objects as Associative Arrays"
(including early versions of javascript: The Definitive Guide -- I
don't know about later editions). They don't say objects are
"associative arrays" -- they speak of their use as such.

It's true, however, that rarely is appropriate qualification on use
(the pitfalls) is given.
<url:http://en.wikipedia.org/wiki/Associative_array#JavaScript>

I wouldn't say that's particularly devastating.

There was no intention that it be devastating. It was just a reminder
that it can be difficult to ride a high horse, when the hordes
surround.
It even mentions that a
prototype will interfere affect the properties available, however it would probably take some careful thinking for the reader to realise what the implications are.

But perhaps not as much careful thinking for a reader to wade through
the reasons being given for never, ever thinking of Javascript objects
as providing "associative array" functionality. ;-)

Regards,

../rh

Jul 23 '05 #27

Robert

In article <11**********************@c13g2000cwb.googlegroups .com>,
"rh" <co********@yahoo.ca> wrote:

Given that propertyIsEnumerable doesn't venture into the prototype
chain, a hasOwnProperty check would seem to redundant. So my later
suggestion would be to simply replace the hasOwnProperty with a
propertyIsEnumerable check;

I put together a test page. Had a curious result when attempting to set
the __proto__ property of an array and object... Variable not set and
not error message. Strange deal indeed... if I got it right.

Robert

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Associative tests</title>
<script type="text/javascript">

function smallString(myInput)
{
if (typeof myInput == "undefined" )
{ return myInput; }
else
{
var alpha = myInput.toString();
alpha = alpha.split("{")[0];
return alpha;
}
}

function checkArray(myInput)
{
var myDel = typeof myInput == "string"? "'" : " ";
document.write( "<tr>" +
"<td>myArray[" + myDel + myInput + myDel + "]</td>" +
"<td>" + smallString(myArray[myInput]) + "</td>" +
"<td>" +
(myArray.hasOwnProperty?myArray.hasOwnProperty(myI nput):" ")+
"</td>" +
"<td>" +

(myArray.propertyIsEnumerable?myArray.propertyIsEn umerable(myInput):"&nbs
p;")+
"</td>" +
"<td>" +

(myArray.isPrototypeOf?Array.prototype.propertyIsE numerable(myInput):"&nb
sp;")+
"</td>" +
"<tr>");
}

function checkObject(myInput)
{
var myDel = typeof myInput == "string"? "'" : " ";
document.write( "<tr>" +
"<td>myObject[" + myDel + myInput + myDel + "]</td>" +
"<td>" + smallString(myObject[myInput]) + "</td>" +
"<td>" +

(myObject.hasOwnProperty?myObject.hasOwnProperty(m yInput):" ")+
"</td>" +
"<td>" +

(myObject.propertyIsEnumerable?myObject.propertyIs Enumerable(myInput):"&n
bsp;")+
"</td>" +
"<td>" +

(myObject.isPrototypeOf?Object.prototype.propertyI sEnumerable(myInput):"&
nbsp;")+
"</td>" +
"<tr>");
}

</script>
</head>
<body>
<p>See the results of hasOwnProperty, and propertyIsEnumerable
for an <b>Array</b>.
</p>
<table>
<thead>
<th>
variable
</th>
<th>
value<br>trimmed
</th>
<th>
myArray.<br>has<br>Own<br>Property
</th>

<th>myArray.<br>property<br>Is<br>Enumerable
</th>
<th>
Array.<br>prototype.<br>property<br>Is<br>Enumerab le
</th>
</thead>
<tbody>
<script type="text/javascript">

var myArray = ['zero'];

myArray[2] = 'thing';
Array.prototype.pi = 3.14159;
myArray['myIndex'] = 'something';

checkArray(2);
checkArray('2');
checkArray('myIndex');
checkArray('pop');
checkArray('toString');
checkArray('pi');
checkArray('noIndex');
checkArray('hasOwnProperty');
checkArray('__proto__');

</script>
</table>
<br>
<p>
Using join() the data in the array is:
<script type="text/javascript">
document.write(myArray.join());
document.write(" and has " + myArray.length + " elements with numeric
indexes.");
</script>
</p><p>Using in the list in indexes for myArray is:
<script type="text/javascript">
var accum;
var begun = false;
for (var i in myArray)
{
if ( begun == true )
{ accum += ", " + i }
else
{ accum = i;
begun = true; }
}
document.write(accum);
</script>
</p>
<br>
<p>See the results of hasOwnProperty, and propertyIsEnumerable
for an <b>Object</b>.
</p>
<table>
<thead>
<th>
variable
</th>
<th>
value<br>trimmed
</th>
<th>
myArray.<br>has<br>Own<br>Property
</th>

<th>myArray.<br>property<br>Is<br>Enumerable
</th>
<th>
Array.<br>prototype.<br>property<br>Is<br>Enumerab le
</th>
</thead>
<script type="text/javascript">
var myObject = {'declared': 'data'};

myObject[2] = 'thing';
Object.prototype.pi = 3.14159;
myObject['myIndex'] = 'something';

checkObject(2);
checkObject('2');
checkObject('myIndex');
checkObject('declared');
checkObject('pop');
checkObject('toString');
checkObject('toLocaleString');
checkObject('pi');
checkObject('noIndex');
checkObject('hasOwnProperty');
checkObject('__proto__');

</script>
</table>
<br>
<p>Using in the list in indexes for myObject is:
<script type="text/javascript">
var accum;
var begun = false;
for (var i in myObject)
{
if ( begun == true )
{ accum += ", " + i }
else
{ accum = i;
begun = true; }
}
document.write(accum);
</script>
</p>
<p>Assign new values to <b>myArray</b>.
<table>
<thead>
<th>
variable
</th>
<th>
value<br>trimmed
</th>
<th>
myArray.<br>has<br>Own<br>Property
</th>

<th>myArray.<br>property<br>Is<br>Enumerable
</th>
<th>
Array.<br>prototype.<br>property<br>Is<br>Enumerab le
</th>
</thead>
<tbody>
<script type="text/javascript">

myArray['pop'] = 'something';
myArray['__proto__'] = "my thing";

checkArray('pop');
checkArray('__proto__');
</script>
</table>
<p>
Using join() the data in the array is:
<script type="text/javascript">
document.write(myArray.join());
document.write(" and has " + myArray.length + " elements with numeric
indexes.");
</script>
</p><p>Using in the list in indexes for myArray is:
<script type="text/javascript">
var accum;
var begun = false;
for (var i in myArray)
{
if ( begun == true )
{ accum += ", " + i }
else
{ accum = i;
begun = true; }
}
document.write(accum);
</script>
</p>
<br>
<br>
<p>Assign some more values to <b>myObject</b>.
</p>
<table>
<thead>
<th>
variable
</th>
<th>
value<br>trimmed
</th>
<th>
myArray.<br>has<br>Own<br>Property
</th>

<th>myArray.<br>property<br>Is<br>Enumerable
</th>
<th>
Array.<br>prototype.<br>property<br>Is<br>Enumerab le
</th>
</thead>
<script type="text/javascript">
myObject['toLocaleString'] = 'something';
myObject['__proto__'] = 'my something';
checkObject('toLocaleString');
checkObject('__proto__');

</script>
</table>
<br>
<p>Using in the list in indexes for myObject is:
<script type="text/javascript">
var accum;
var begun = false;
for (var i in myObject)
{
if ( begun == true )
{ accum += ", " + i }
else
{ accum = i;
begun = true; }
}
document.write(accum);
</script>
</p>

<br>
<p>
<script type="application/x-javascript">
document.write(navigator.userAgent);
</script>
</body>
</html>

Jul 23 '05 #28

Robert wrote:

In article <11**********************@c13g2000cwb.googlegroups .com>,
"rh" <co********@yahoo.ca> wrote:
Given that propertyIsEnumerable doesn't venture into the prototype
chain, a hasOwnProperty check would seem to redundant. So my later
suggestion would be to simply replace the hasOwnProperty with a
propertyIsEnumerable check;
I put together a test page. Had a curious result when attempting to

set the __proto__ property of an array and object... Variable not set and not error message.
Mentioned that "little" anomaly in an earlier post, although it should
have contained the word "attempt":

'Moreover, if you make an assignment to these properties, no assignment
is made. That makes these properties "special".'
Strange deal indeed... if I got it right.

Yes, unfortunately.

../rh

Jul 23 '05 #29

Robert

I got the info about __proto__ from your ealier post. Didn't know that
I wouldn't get an error message.

Robert

Jul 23 '05 #30

Mighty Krell

"Douglas Crockford" <no****@covad.net> wrote in message
news:3d*************************@msgid.meganewsser vers.com...

It is incorrect to use an array when the keys are non-integers.

I think this is too strong of a statement since the array declaration
supports string values as references.

Wrong is wrong even if you do not understand the difference.

You're full of crap. JS allows string indices on purpose. It's quite
intentional, even if you don't like it.

MK

Jul 23 '05 #31

Mighty Krell wrote:

Douglas Crockford wrote:
It is incorrect to use an array when the keys are
non-integers.
I think this is too strong of a statement since the
array declaration supports string values as references.

Wrong is wrong even if you do not understand the difference.

You're full of crap.

?
JS allows string indices on purpose.
"indices" is a potentially misleading term to use in this context, with
its connotations of numeric indices as used in Arrays.

Javascript supports bracket notation property accessors for a reason,
but that reason is mostly related to accessing the properties of Objects
with dynamically determined property names.
It's quite intentional, even if you don't like it.

There is no implication in Douglas's posts that he doesn't like bracket
notation property accessors. He is impugning the appropriateness of
using an objet specialised as an Array in circumstances where only the
general behaviour of Objects is desired.

Richard.

Jul 23 '05 #32

Robert

In article <ct*******************@news.demon.co.uk>,
"Richard Cornford" <Ri*****@litotes.demon.co.uk> wrote:

JS allows string indices on purpose.
"indices" is a potentially misleading term to use in this context, with
its connotations of numeric indices as used in Arrays.

But we know that javascript allows arrays to have string indexes.

from: http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?index
index

(Plural "indices" or "indexes")

1. <programming> A number used to select an element of a list, vector,
array or other sequence. Such indices are nearly always non-negative
integers but see associative array.

2. <database> See inverted index. [Other kinds?]

3. <World-Wide Web> A search engine.

4. <World-Wide Web> A subject index.

4. <jargon> See coefficient of X.

associative array

<programming> An array where the indices are not just integers but may
be arbitrary strings.

awk and its descendants (e.g. Perl) have associative arrays which are
implemented using hash coding.

from: http://en.wikipedia.org/wiki/Indices

In information technology

In computer science, an index is usually used for expressing an nth
element. Indices are usually expressed as integers.

These two definition acknowledge that people are using the term indices
to include non numeric values but these folks are in the minority. It
seems the direction is to use the term indices even if the array allow
string indexes.

I think that interpretive languages blur the distinction between numeric
only indexes to arrays and string based access to data object. The
distinction is more related to a language like C not a language like
Javascript.

I have done a lot a programming in languages with associative arrays as
the underlaying data structure used to access data. It's not a big deal
to me to use string indexes in arrays since I am used to this being the
only way to access the data.
Javascript supports bracket notation property accessors for a reason,
but that reason is mostly related to accessing the properties of Objects
with dynamically determined property names.
It's quite intentional, even if you don't like it.

There is no implication in Douglas's posts that he doesn't like bracket
notation property accessors. He is impugning the appropriateness of
using an objet specialised as an Array in circumstances where only the
general behaviour of Objects is desired.

This is a little to strong. Douglas objected twice to my earlier posts
when I pointed out that you could have a string index in a Javascript
array.

It seems to me that the underlaying data saving method in Javascript is
an associative array. There are two ways of accessing the data in the
associative array. One in the array syntax and the other the object
syntax.

Considering that array indices are saved as a strings, there seems to be
too much hand waving over how bad it is to use a string as an index with
an array. Also, I associate the bracket notation with array access, so
it is interesting some find it perfectly normal to use bracket notation
with an object but unacceptable to use a string an an index in an array.

Javascript aren't C so let's not apply the C language conventions to
object like arrays in Javascript.

Robert

Jul 23 '05 #33

Douglas Crockford

> It seems to me that the underlaying data saving method in Javascript is

an associative array. There are two ways of accessing the data in the
associative array. One in the array syntax and the other the object
syntax.

The underlying structure is the object. In JavaScript, the object is the
associative array. The JavaScript array is a specialization of the
object with special features for handling numeric subscripts.

The dot notation and subscript notation both work with objects, and
since arrays are, deep down, object, both notations work with arrays, too.

It is possible to use non-numeric subscripts with arrays, but that
usually indicates a lack of understanding. Fortunately, such a lack is
easily remedied. See for example
http://www.crockford.com/javascript/survey.html

Jul 23 '05 #34