Array as hash tables

Alexis Nikichine wrote:

It is common knowledge that arrays can be used as hashtables:

var color = [];

color["red"] = 0xFF0000;
color["blue"] = 0x0000FF;
With this, I can check whether a string identifies a color, or not:

function isColor(string)
{
return color[string] == undefined;
}

My only concern is that

isColor("pop") == true

and that will hold true for quite a few annoying, parasitic,
"keywords" ("constructor", "length", etc...)

I finally came to use the following as a naked object, to use as a
hashtable:

function HashTable() { this.constructor = undefined; }

// example of use:
var color = new HashTable;
color["red"] = 0xFF0000
Question for experts: won't then there be other unexpected, hardcoded,
keywords stalking my strings in the dark, and returning obscure,
native, js objects, where I expected plain numbers ?

Any help appreciated,

If the indexes are not integers, then use an Object, not an Array.

var color = {};

If the subscript is an identifier (and not a reserved word), you can use
the stylish dot notation.

color.red = 0xFF0000;
color.blue = 0x0000FF;

In HTML applications, it may be better to keep color values as strings.
That way you won't get a false negative on black.

color.red = "#FF0000";
color.blue = "#0000FF";
color.black = "#000000";

If you use a little type discipline, then it is eay to distinguish your
values from Object methods.

function isColor(string) {
return typeof color[string] == "string";
}

The hashtable constructor above is silly. If it doesn't have methods,
then it is better to use a plain Object. Even better, you can use the
object literal notation.

color = {red: "#FF0000", blue: "#0000FF", black: "#000000"};

http://www.JSON.org

Jul 23 '05 #2

Alexis Nikichine

Douglas Crockford wrote:

If the indexes are not integers, then use an Object, not an Array.

var color = {};

If the subscript is an identifier (and not a reserved word), you can use the stylish dot notation.

color.red = 0xFF0000;
color.blue = 0x0000FF;

In HTML applications, it may be better to keep color [snip>

The color example was just a gratuitous one. I was worrying about
arbitrary strings typed in by users. One day, I had reports of "pop art"
request failing. "pop" yielded a function (instead of an expected
integer).
If you use a little type discipline, then it is eay to distinguish your values from Object methods.

function isColor(string) {
return typeof color[string] == "string";
}
When I first met the, I used type discipline, and made sure that the
returned value was an integer.
The hashtable constructor above is silly. If it doesn't have methods,
then it is better to use a plain Object. Even better, you can use the
object literal notation.

Unfortunately, I can't rely on type discipline, now, since (in another
urelated case) I need an hash (and don't call me a perl boob :-)
returning hash, integers.

With a plain Object, I will get an unexpected result on "constructor".

Which is why I am asking: is my HashTable a really really empty
Object/Function, once the "constructor" member has been blanked ?

Alexis

--
some domain is free (and btw, everything I know, I learned from your
site; thank you :-)

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

Jul 23 '05 #3

>>If the indexes are not integers, then use an Object, not an Array.

var color = {};

If the subscript is an identifier (and not a reserved word), you can

use
the stylish dot notation.

color.red = 0xFF0000;
color.blue = 0x0000FF;

In HTML applications, it may be better to keep color

[snip>

The color example was just a gratuitous one. I was worrying about
arbitrary strings typed in by users. One day, I had reports of "pop art"
request failing. "pop" yielded a function (instead of an expected
integer).

If you use a little type discipline, then it is eay to distinguish

your
values from Object methods.

function isColor(string) {
return typeof color[string] == "string";
}

When I first met the, I used type discipline, and made sure that the
returned value was an integer.

The hashtable constructor above is silly. If it doesn't have methods,
then it is better to use a plain Object. Even better, you can use the
object literal notation.

Unfortunately, I can't rely on type discipline, now, since (in another
urelated case) I need an hash (and don't call me a perl boob :-)
returning hash, integers.

With a plain Object, I will get an unexpected result on "constructor".

Which is why I am asking: is my HashTable a really really empty
Object/Function, once the "constructor" member has been blanked ?

Yes and no. A new object is empty, but it inherits values from its
prototype chain. Clobbering the constructor does not change that.

If the values in your object (or for the boobs, hash) are anything but
functions, you can use

(typeof color[string] != 'function')

to discriminate your values from the Object methods.

By the way, I think this was a design error in JavaScript. The
appearance of those methods complicates the use of objects as collections.

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

Jul 23 '05 #4

Alexis Nikichine

> > With a plain Object, I will get an unexpected result on

"constructor".

Which is why I am asking: is my HashTable a really really empty
Object/Function, once the "constructor" member has been blanked ?
Yes and no. A new object is empty, but it inherits values from its
prototype chain. Clobbering the constructor does not change that.

Oups; you've left me far behind on this one. What should I expect to be
inherited by this simple as bread'n butter object :

function plainStuff(){}

... code ...

a = new plainStuff

?

Should I be concerned that in the ... code ... part, someone may have
augmented the plainStuff prototype ?
If the values in your object (or for the boobs, hash) are anything
but functions, you can use

(typeof color[string] != 'function')

to discriminate your values from the Object methods.

By the way, I think this was a design error in JavaScript. The
appearance of those methods complicates the use of objects as
collections.

I wonder too. Was not the dontEnum attribute a last minute and
incomplete workaround for this ?

May I suggest my definitive and foolprooh hash. Call it Collection, for
VB boobs:

function Collection()
{
this.constructor = undefined;
Collection.prototype = undefined;
}

Is it enough clobbering ?
Alexis

--
some domain is free

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

Jul 23 '05 #5

al**************@free.fr (Alexis Nikichine) writes:

It is common knowledge that arrays can be used as hashtables:

var color = [];

color["red"] = 0xFF0000;
color["blue"] = 0x0000FF;
It is less common knowledge that arrays are overkill for this, and
that plain objects are better suited:

var color = {}; // or: new Object();
color["red"] = 0xff0000;
color["blue"] = 0x0000ff;
With this, I can check whether a string identifies a color, or not:

function isColor(string)
{
return color[string] == undefined;
That would be better as:
return color[string] === undefined;
or, for browsers where "undefined" is not defined (the irony!) you
can define it as:
window.undefined = window.undefined;
or you could use
return (typeof color[string]) == "undefined";
My only concern is that

isColor("pop") == true

and that will hold true for quite a few annoying, parasitic,
"keywords" ("constructor", "length", etc...)
Fewer if using objects instead of arrays, but still some (e.g. toString).
I finally came to use the following as a naked object, to use as a
hashtable:

function HashTable() { this.constructor = undefined; }

// example of use:
var color = new HashTable;
color["red"] = 0xFF0000
Yes. That's just a plain object as well, with no properties except
those inherited from Object.prototype (and even with "constructor"
removed).
Question for experts: won't then there be other unexpected, hardcoded,
keywords stalking my strings in the dark, and returning obscure,
native, js objects, where I expected plain numbers ?
According to ECMA 262 v3 section 5.2.4:
toString, toLocaleString, valueOf, hasOwnProperty, isPrototypeOf,
propertyIsEnumerable.
(you overwrote "constructor", otherwise it would be there too).
Any help appreciated,

All these properties are functions. All your stored values are
numbers. Try:

function isColor(string){
return (typeof color[string])=="number";
}

In recent versions of browsers, you can also use:

function isColor(string) {
return color.hasOwnProperty(string);
}

That only counts the properties of the object itself, not its
prototypes. In any case, you can just use "new Object()" instead
of "new HashTable()".

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #6

Douglas Crockford <no****@covad.net> writes:

functions, you can use

(typeof color[string] != 'function')

to discriminate your values from the Object methods.

By the way, I think this was a design error in JavaScript. The
appearance of those methods complicates the use of objects as
collections.

It has been somehow mitigated by later additions to, of all things,
Object.prototype :).

All the properties of Object.prototype are non-enumerable, so you
can test against non-original properties as:

propName in objectRef && !objectRef.propertyIsEnumerable(propName)

(or, if only adding to one object an not inheriting from it:
objectRef.hasOwnProperty(propName)
)
/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #7

Alexis Nikichine wrote:
<snip>

The color example was just a gratuitous one. I was worrying
about arbitrary strings typed in by users. One day, I had
reports of "pop art" request failing. "pop" yielded a
function (instead of an expected integer).

<snip>

If you want to store key/value pairs without any restrictions to the
names perhaps you need to implement an object for that storage. Maybe in
a Java style with - get - and - put - (and maybe - remove -) methods.
With an internal naming system that allows referencing by key but does
not directly use that key as a property name. You could genuinely hash
the keys to a number and then represent that number as a string property
name, but that would be quite an overhead to add to each reference. A
satisfactory indirect use of the key might be to append a space
character to the front of it, producing a property name that will never
conflict with any prototype inherited property of an object. A simple
implementation might go:-

function SafeHash(){
var safeName = [' '];
var values = {};
this.get = function(key){
safeName[1] = key;
return values[safeName.join('')]
};
this.put = function(key, value){
safeName[1] = key;
values[safeName.join('')] = value;
};
this.remove = function(key){
safeName[1] = key;
delete values[safeName.join('')];
};
}

A more complex version, implementing most of the pertinent methods form
the Java Hashtable, and returning Enumerator (and Iterator) Interfaces
for keys and values, might go:-

var Hashtable = (function(){
var keyAdj = [' '];
/* This private static Object constructor is used to implement
a Java style Enumerator (and Iterator) Interface:-
*/
function Enumeration(arrNm, activeEnum, keysToIndex){
var lastIndex = null;
var enumIndex = 0;
while(typeof activeEnum[enumIndex] == 'number'){enumIndex++;}
activeEnum[enumIndex] = 0;
this.hasNext = this.hasMoreElements = function(){
if(activeEnum[enumIndex] < keysToIndex.tableLength){
return true;
}else{
if(typeof activeEnum[enumIndex] == 'number'){
activeEnum[enumIndex] = null;
}
return false;
}
};
this.next = this.nextElement = function(){
if(this.hasNext()){
lastIndex = activeEnum[enumIndex];
return keysToIndex[arrNm][activeEnum[enumIndex]++];
}else{
return null;
}
};
this.remove = function(){
if(typeof lastIndex == 'number'){
removeItem(keysToIndex._indexToKeys[lastIndex],
keysToIndex, activeEnum);
lastIndex = null;
}
};
};
function removeItem(key, keysToIndex, activeEnum){
keyAdj[1] = key;
key = keyAdj.join('');
var remIndex = keysToIndex[key];
if(typeof remIndex == 'number'){
delete keysToIndex[key];
keysToIndex.tableLength--;
for(var c = remIndex;c < keysToIndex.tableLength;c++){
keysToIndex._indexToValue[c] =
keysToIndex._indexToValue[c+1];
keyAdj[1] = (keysToIndex._indexToKeys[c] =
keysToIndex._indexToKeys[c+1]);
keysToIndex[keyAdj.join('')] = c;
}
keysToIndex._indexToValue.length = keysToIndex.tableLength;
for(var c = activeEnum.length;c--;){
if((activeEnum[c])&&(remIndex < activeEnum[c])){
activeEnum[c]--;
}
}
}
}
/* Hashtable object constructor fuction:-
*/
function HTable(){
var keysToIndex ={_indexToValue:[],_indexToKeys:[],tableLength:0};
var activeEnum = [];
this.get = function(key){
keyAdj[1] = key;
key = keyAdj.join('');
if(typeof keysToIndex[key] == 'number'){
return keysToIndex._indexToValue[keysToIndex[key]];
}else{
return null;
}
};
this.put = function(key, value){
keyAdj[1] = key;
var sKey = keyAdj.join('');
if(typeof keysToIndex[sKey] == 'number'){
keysToIndex._indexToValue[keysToIndex[sKey]] = value;
}else{
keysToIndex[sKey] = keysToIndex.tableLength;
keysToIndex._indexToValue[keysToIndex.tableLength] = value;
keysToIndex._indexToKeys[keysToIndex.tableLength++] = key;
}
};
this.remove = function(key){
removeItem(key, keysToIndex, activeEnum);
};
this.containsKey = function(key){
keyAdj[1] = key;
return (typeof keysToIndex[keyAdj.join('')] == 'number');
};
this.size = function(){return keysToIndex.tableLength;};
this.elements = function(){
return new Enumeration('_indexToValue',activeEnum, keysToIndex);
};
this.keys = function(){
return new Enumeration('_indexToKeys', activeEnum, keysToIndex);
};
}
HTable.prototype.clear = function(){
var e = this.keys();
while(e.hasNext()){
this.remove(e.next());
}
};
HTable.prototype.toString = function(){
var k,e = this.keys();
var st = '';
while(e.hasNext()){
k = e.next();
st += k+' = '+this.get(k)+'\n';
}
return st;
};
HTable.prototype.containsValue =
(HTable.prototype.contains = function(testVal){
var v,e = this.elements();
while(e.hasNext()){
v = e.next();
if(v === testVal){
//if((v == testVal)&&(typeof v == typeof testVal)){
return true;
}
}
return false;
});
HTable.prototype.isEmpty = function(){
return (this.size() == 0);
};
HTable.prototype.putAll = function(hTable){
if((typeof hTable == 'object')&&
(hTable.constructor == HTable)){
var n,e = hTable.keys();
while(e.hasNext()){
n = e.next();
this.put(n, hTable.get(n));
}
}
return this;
};
HTable.prototype.clone = function(){
return new HTable().putAll(this);
};
HTable.prototype.equals = function(o){
return (o == this);
};
return HTable; //return the Hashtable object constructor.
})();

The optimum functionality for your application will probably lye
somewhere in-between the two.

Richard.

Jul 23 '05 #8

>>If the values in your object (or for the boobs, hash) are anything

but functions, you can use

(typeof color[string] != 'function')

to discriminate your values from the Object methods.

By the way, I think this was a design error in JavaScript. The
appearance of those methods complicates the use of objects as
collections.

I wonder too. Was not the dontEnum attribute a last minute and
incomplete workaround for this ?

The problem with dontEnum is that it didn't make it into the language;
it is only in the implementation. It only controls the results of
for..in, so it does not help you in this case, anyway.
May I suggest my definitive and foolproof hash. Call it Collection, for
VB boobs:

function Collection()
{
this.constructor = undefined;
Collection.prototype = undefined;
}

Is it enough clobbering ?

No. The [[prototype]] property is the key one, and it is still there.
Clobbering is not effective. You will still see the Object methods (but
there are fewer of them than there are Array methods).

Something that might work is

function Collection() {}
Collection.prototype = {constructor: null, toString: null,
prototype: null};

http://www.crockford.com/#javascript

Jul 23 '05 #9

Douglas Crockford <no****@covad.net> writes:

Something that might work is

function Collection() {}
Collection.prototype = {constructor: null, toString: null,
prototype: null};

A new object created from "new Collection()" will not have a "prototype"
property, so "prototype: null" is not needed.

The full monty would be:
---
function Collection(){}
Collection.prototype = {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnumerable: undefined
};
---
However, there is no need for the Collection *constructor* then. When
you just need an empty collection, you can create a new one directly:

---
function createCollection() {
return {
constructor: undefined,
toString : undefined,
toLocaleString : undefined,
valueOf : undefined,
hasOwnProperty: undefined,
isPropertyOf: undefined,
propertyIsEnumerable: undefined
};
}
---

(Ofcourse, some implementations might have other, non-standard,
properties on Object.prototype :)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #10

John G Harris

In article <95**************************@posting.google.com >, Alexis
Nikichine <al**************@free.fr> writes

<snip>

I finally came to use the following as a naked object, to use as a
hashtable:

<snip>

Why do you call it a hashtable? It could just as easily be a balanced
tree or even a simple list. You wouldn't be able to tell the difference.

If you want to be posh, and accurate too, call it an associative array.
If you want to be less posh you could call it a map.

John
--
John Harris

Jul 23 '05 #11

Lasse Reichstein Nielsen wrote:
<snip>

(Ofcourse, some implementations might have other,
non-standard, properties on Object.prototype :)

Such as Mozilla:-

__defineGetter__
__defineSetter__
__parent__
__proto__
eval
toSource
unwatch
watch

Richard.

Jul 23 '05 #12

>>I finally came to use the following as a naked object, to use as a

hashtable
Why do you call it a hashtable? It could just as easily be a balanced
tree or even a simple list. You wouldn't be able to tell the difference.

If you want to be posh, and accurate too, call it an associative array.
If you want to be less posh you could call it a map.

And if you want to be understood in a JavaScript forum, you would call
it an object.

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

Jul 23 '05 #13

Yann-Erwan Perio

Richard Cornford wrote:

(Ofcourse, some implementations might have other,
non-standard, properties on Object.prototype :)

Such as Mozilla:-

__defineGetter__
__defineSetter__
__parent__
__proto__
eval
toSource
unwatch
watch

JFTR <URL:http://lxr.mozilla.org/seamonkey/source/js/src/jsobj.c#1535>
provides the last two methods : __lookupGetter__ and __lookupSetter__.
Regards,
Yep.

Jul 23 '05 #14

"Richard Cornford" wrote:

Alexis Nikichine wrote:
<snip>
The color example was just a gratuitous one. I was worrying
about arbitrary strings typed in by users. One day, I had
reports of "pop art" request failing. "pop" yielded a
function (instead of an expected integer).

<snip>

If you want to store key/value pairs without any restrictions to the
names perhaps you need to implement an object for that storage.

That's unfortunate. Truthfully, this is a name-scope conflict with
genesis imbedded as a deficiency of the language (a statement made
notwithstanding the fact that JavaScript remains, by far, my favourite
progamming language). It should be possible to obtain a basic object
that is entirely clear of such name conflicts.

Given that, and ever seemingly the contrarian, I don't believe that
Alexis is that far off track in attempting to remedy the deficiency
through removal of pre-definded values in the object. The latter day
"propertyIsEnumerable" mentioned by Lasse, it seems, is a rather late,
lame fix to the language.

../rh

Jul 23 '05 #15

rh wrote:

"Richard Cornford" wrote:

<snip>

If you want to store key/value pairs without any restrictions to the
names perhaps you need to implement an object for that storage.

That's unfortunate. Truthfully, this is a name-scope conflict with
genesis imbedded as a deficiency of the language (a statement made
notwithstanding the fact that JavaScript remains, by far, my favourite
progamming language). It should be possible to obtain a basic object
that is entirely clear of such name conflicts.

Given that, and ever seemingly the contrarian, I don't believe that
Alexis is that far off track in attempting to remedy the deficiency
through removal of pre-definded values in the object. ...

We have seen that Mozilla is admitting to adding some non-standard
properties to its JS objects. I am fairly sure that I have also seen
some similar non-standard properties on Konqueror objects, as apparently
exposed implementation details (I don't have time to re-check right
now). That makes relying on blanking a list of expected properties
unsatisfactory, as it would be difficult to guarantee that the list was
comprehensive across JS implementations.

Adding a space to the front of the property names is not guaranteed to
be absolutely safe either, but the chances of coincidence are lower and
programmers are unlikely to make JS implementations that used space
prefixed property names (not least because most other languages would
not allow it).

Richard.

Jul 23 '05 #16

John G Harris

In article <d3***************************@msgid.meganewsserve rs.com>,
Douglas Crockford <no****@covad.net> writes

I finally came to use the following as a naked object, to use as a
hashtable

Why do you call it a hashtable? It could just as easily be a balanced
tree or even a simple list. You wouldn't be able to tell the difference.
If you want to be posh, and accurate too, call it an associative
array.
If you want to be less posh you could call it a map.

And if you want to be understood in a JavaScript forum, you would call
it an object.

But I thought the whole point of this thread was that a javascript
object isn't good enough to be an any name in, correct value out kind of
thing, or map as we might call it.

Also I'm surprised no-one has suggested prefixing each name with
something unlikely, such as "TQ7_".

John
--
John Harris

Jul 23 '05 #17

"Richard Cornford" wrote:

rh wrote:
"Richard Cornford" wrote:
<..> We have seen that Mozilla is admitting to adding some non-standard
properties to its JS objects. I am fairly sure that I have also seen
some similar non-standard properties on Konqueror objects, as apparently
exposed implementation details (I don't have time to re-check right
now).
I wasn't aware of that, but it does go right to the heart of the
design problem that exists. Under the current model of objects having
a single namespace, it isn't possible to extend native properties of
the JS object without potentially breaking existing programs.

Of course, given prototype inheritance, the single namespace is far
more a blessing than a curse.
That makes relying on blanking a list of expected properties
unsatisfactory, as it would be difficult to guarantee that the list was
comprehensive across JS implementations.

Yes, so now I want to be provided with a native method that will
return a list of property names that manifest through the prototype
chain :).

Or perhaps, to obtain a completely unencumbered object, I just want to
be able to turn off the prototype chain processing?

../rh

Jul 23 '05 #18

John G Harris <jo**@nospam.demon.co.uk> writes:

But I thought the whole point of this thread was that a javascript
object isn't good enough to be an any name in, correct value out kind of
thing, or map as we might call it.
It works fine for that. The problem is that it doesn't start out empty,
but wnything you put in, you get out again fine.
Also I'm surprised no-one has suggested prefixing each name with
something unlikely, such as "TQ7_".

Richard did. He suggested a single space IIRC.
Ok, an associative array implementation that isn't fooled by standard
or non-standard values:
---
function Map() {
this.map = {};
}
Map.Value = function Value(v) {
this.value = v;
}
Map.prototype.containsKey = function containsKey(k) {
return (this.map[k]) instanceof Map.Value;
}
Map.prototype.put = function put(k,v) {
this.map[k] = new Map.Value(v);
};
Map.prototype.get = function get(k) {
var v = this.map[k];
if (v instanceof Map.Value) {
return v.value;
}
};
Map.prototype.remove = function remove(k) {
delete this.map[k]
};
---

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #19

rh wrote:

Richard Cornford wrote: <snip> Or perhaps, to obtain a completely unencumbered object, I just
want to be able to turn off the prototype chain processing?

The implication in the ECMA specified [[construct]] method is that
either an object must be assigned to the internal [[prototype]] property
of a newly created object or the original Object.prototype will be used
(not even the current Object.prototype). I don't see any way of
acquiring a reference to an object with less than one object on its
prototype chain.

Richard.

Jul 23 '05 #20

"Richard Cornford" <Ri*****@litotes.demon.co.uk> writes:

I don't see any way of acquiring a reference to an object with less
than one object on its prototype chain.

Object.prototype :)
But apart from that, no.
/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #21

Lasse Reichstein Nielsen wrote:

Richard Cornford writes:
I don't see any way of acquiring a reference to an
object with less than one object on its prototype chain.

Object.prototype :)
But apart from that, no.

Good point. That is one object with a null [[prototype]] property.
Unfortunately it will also feature the list of specified properties and
any implementation dependent properties from the outset so it doesn't
help in this context.

Richard.

Jul 23 '05 #22

Lasse Reichstein Nielsen wrote:

John G Harris <jo**@nospam.demon.co.uk> writes:
But I thought the whole point of this thread was that a javascript
object isn't good enough to be an any name in, correct value out kind of
thing, or map as we might call it.
It works fine for that. The problem is that it doesn't start out empty,
but wnything you put in, you get out again fine.

With the exception of built-in properties, see below.

Also I'm surprised no-one has suggested prefixing each name with
something unlikely, such as "TQ7_".

Richard did. He suggested a single space IIRC.
Ok, an associative array implementation that isn't fooled by standard

^^^^^^^^^^^^^^^^^^^^^^^^ or non-standard values: ^^^^^^^^^^^^^^^^^^^^^^
What is this supposed to mean?
---
function Map() {
this.map = {};
}
Map.Value = function Value(v) {
this.value = v;
}
Map.prototype.containsKey = function containsKey(k) {
return (this.map[k]) instanceof Map.Value;
It does not make sense to put the operand of `instanceof' in parantheses.
It would make more sense to put the entire return value in parantheses
although this would not be required as `instanceof' has precedence over
`return'.
}
Map.prototype.put = function put(k,v) {
this.map[k] = new Map.Value(v);
};
Map.prototype.get = function get(k) {
var v = this.map[k];
if (v instanceof Map.Value) { ^^^^^^^^^^^^^^^^^^^^^^
Would it not be wise to use this.contains(v) here?
return v.value;
}
};
Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!) and thus assignment to objectReference[k] (here:
this.map[k]) must not be allowed for those values of k. Encapsulating
the value in another (prototyped) object (twice) does not really help
here, and if the used object contains _only_ a value property this
approach is merely a waste of memory. Only a suitable transparent
modification of the passed property name (suffix, prefix, infix; while
one the former to should be used) will solve that problem. A single
space indeed seems to be viable as internal prefix, yet the prototype
could be implemented more flexible in the case the space is not enough:

function Map() {}

Map.prototype.prefix = " ";
Map.prototype.suffix = "";

Map.prototype.containsKey = function map_containsKey(k)
{
return !!(this[this.prefix + k + this.suffix]);
}

Map.prototype.put = function map_put(k, v)
{
this[this.prefix + k + this.suffix] = v;
};

Map.prototype.get = function map_get(k)
{
return this[this.prefix + k + this.suffix];
};

Map.prototype.remove = function map_remove(k)
{
delete this[this.prefix + k + this.suffix];
};
PointedEars

Jul 23 '05 #23

Thomas 'PointedEars' Lahn wrote:

Lasse Reichstein Nielsen wrote:
Map.prototype.containsKey = function containsKey(k) {
return (this.map[k]) instanceof Map.Value;

[...]
}
Map.prototype.put = function put(k,v) {
this.map[k] = new Map.Value(v);
};
Map.prototype.get = function get(k) {
var v = this.map[k];
if (v instanceof Map.Value) {

^^^^^^^^^^^^^^^^^^^^^^
Would it not be wise to use this.contains(v) here?

No, it would not, and this.containsKey(k) would result in another
unnessary lookup which is not reasonable. Forget about this.
PointedEars

Jul 23 '05 #24

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:

Lasse Reichstein Nielsen wrote:
Ok, an associative array implementation that isn't fooled by standard ^^^^^^^^^^^^^^^^^^^^^^^^
or non-standard values:

^^^^^^^^^^^^^^^^^^^^^^
What is this supposed to mean?

Hmm ... should be: fooled by existing standard or non-standard
properties.

Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!)

Absolutely. I'm depending on them being overwritable.
and thus assignment to objectReference[k] (here: this.map[k]) must
not be allowed for those values of k.
Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.

If the properties are "magic", like, e.g., innerHTML on DOM nodes, or
"length" on Arrays, then even overwriting is a problem.

However, that would be a violation of ECMA 262, since an object is
created using "new Constructor", where "Constructor" is a user defined
function, can not be a host object.

What you might be thinking of, is that deleting existing properties
should not be allowed, which is true (no "delete Object.prototype.toString").
So, "delete" should be:

Map.prototype.remove = function remove(k) {
if (this.containsKey(k)) {
delete this.map[k]
}
};
Encapsulating the value in another (prototyped) object (twice) does
not really help here, and if the used object contains _only_ a value
property this approach is merely a waste of memory.
No, the point of wrapping in an instance of Map.Value is that no
preexisting property is an instance of Map.Value. That allows us to
distinguish properties that we put in the map from those already
there, no matter what type they might be (including objects or
arrays).

The "containsKey" and "get" methods (and the correct "delete") test
that the property value is an instance of Map.Value, i.e., that it's
something put there using the "put" method.

(I'm not considering someone deliberatly messing with the "this.map"
property, only the problem of avoiding mistakin existing properties
for elements of the map)
Only a suitable transparent modification of the passed property name
(suffix, prefix, infix; while one the former to should be used) will
solve that problem.

This solves it for correct ECMA262 implementations.

Modifying the property name blindly will not be absolutely safe, since
you might hit another preexisting property name with the modified name
as well (who knows, maybe some day, an ECMAScript impelentation will
have a hidden method called " hiddenMethod " on Object prototype).

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #25

Grant Wagner

Lasse Reichstein Nielsen wrote:

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Only a suitable transparent modification of the passed property name
(suffix, prefix, infix; while one the former to should be used) will
solve that problem.

This solves it for correct ECMA262 implementations.

Modifying the property name blindly will not be absolutely safe, since
you might hit another preexisting property name with the modified name
as well (who knows, maybe some day, an ECMAScript impelentation will
have a hidden method called " hiddenMethod " on Object prototype).

How about defining the prefix/suffix combination by some millisecond time stamp /
psuedo-random value at run time. This would reduce the chances of a conflict to
zero[1]:

<script type="text/javascript">
function Map() {}
Map.prototype.prefix = (new Date()).getTime();
Map.prototype.suffix = Math.floor(Map.prototype.prefix * Math.random()) + "_";
Map.prototype.prefix = "_" + prefix;
Map.prototype.uniqueId = prefix + suffix;
// or one of the endless variations on this concept
// ... etc ...
</script>

Doing it this way would also guarantee that you could uniquely[2] identify each
Map(), although I'm not sure there's any value in that.

[1] - almost zero. It's certainly possible, however unlikely, that a user agent
or future ECMAScript implementation might have an Object property called
"_1092061591623toString1026459394798_" or
"_1092061887384constructor527875481827_".
[2] - almost unique. Due to system clock synchronizing software, it would be
possible, however unlikely, for two Map()s to have the same prefix and randomly
generate the same suffix.

--
Grant Wagner <gw*****@agricoreunited.com>
comp.lang.javascript FAQ - http://jibbering.com/faq

Jul 23 '05 #26

Lasse Reichstein Nielsen wrote:

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
Ok, an associative array implementation that isn't fooled by standard ^^^^^^^^^^^^^^^^^^^^^^^^
or non-standard values:

^^^^^^^^^^^^^^^^^^^^^^
What is this supposed to mean?

Hmm ... should be: fooled by existing standard or non-standard
properties.

Well, it can still be fooled.

Map.prototype.remove = function remove(k) {
delete this.map[k]
};

Your implementation is still missing the point: Objects have built-in
properties that are often not enumerable but could still be overwritten
(including methods!)

Absolutely. I'm depending on them being overwritable.

But some properties are read-only.

and thus assignment to objectReference[k] (here: this.map[k]) must
not be allowed for those values of k.

Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.

If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

And if not, you would have saved nothing in your "hash table". That
does not sound like a (reasonable/viable) solution.
If the properties are "magic", like, e.g., innerHTML on DOM nodes, or
"length" on Arrays, then even overwriting is a problem.

However, that would be a violation of ECMA 262, since an object is
created using "new Constructor", where "Constructor" is a user defined
function, can not be a host object.
This is not about host objects, it is about core properties *every*
object has.
What you might be thinking of, is that deleting existing properties
should not be allowed,
No, although that would be useful.
which is true (no "delete Object.prototype.toString").
You would effectively overlay Object.prototype.toString if you would try
to add a "toString" hash table entry and cause to property cease to work
as supposed. Or consider a "valueOf" hash table entry. Or "constructor".
Or ...

Encapsulating the value in another (prototyped) object (twice) does
not really help here, and if the used object contains _only_ a value
property this approach is merely a waste of memory.

No, the point of wrapping in an instance of Map.Value is that no
preexisting property is an instance of Map.Value.

Even your Map and Map.Value instances have preexisting properties
inherited from Object. They may not be enumerable but they still
exist. There is no, I repeat, *no* object that has no "preexisting
properties".
That allows us to distinguish properties that we put in the map from those
already there, no matter what type they might be (including objects or
arrays).

I won't debate that you can distinguish between added and built-in
properties and I did not. The point is that your implementation does
not prevent overlaying or overwriting built-in properties. You control
the read, but not the write process (yet).

Only a suitable transparent modification of the passed property name
(suffix, prefix, infix; while one the former to should be used) will
solve that problem.

This solves it for correct ECMA262 implementations.

No, it does not, because of

,-[ECMA 262 Edition 3, 2000-03-24]
|
| 2 Conformance
|
| [...]
| 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.

And unfortunately(?), we are not living in a perfect standardized world.
Implementations make use of the opportunity described above, there is
escape(), unescape(), __proto__ and *much* more out there.

Exactly ECMA-262 and the prototype chain presents the reason why your
hash table implementation "as is" is flawed.
PointedEars

Jul 23 '05 #27

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:

Absolutely. I'm depending on them being overwritable.
But some properties are read-only.

But they exist on the prototype, not on the object itself. They can be
overwritten on the inheriting object.

Assume o is an object and o.ro is a read-only, don't delete,
etc. property. Then
---
function C(){};
C.prototype = o;
var c = new C();
c.ro = 42;
---
will work and set "c.ro" to 42. It isn't affected by the read-only
property of the prototype. The prototype's property is just what you
read if you haven't created that property on the object itself.

Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.

If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

No unexpected behavior will happen, as long as the object is only used
to look up properties in. No "core property" affects how [[Get]] and
[[Put]] works.

Unexpected behavior might happen if I overwrite the "toString"
property *and* tries to convert the object to a string, but I never do
that.
And if not, you would have saved nothing in your "hash table". That
does not sound like a (reasonable/viable) solution.
Not understood.
This is not about host objects, it is about core properties *every*
object has.
That every object's *prototype* has. The object itself has no
properties.

Doing
new Object()
creates a new native ECMAScript object. It has no visible properties
itself, only the ones inherited from its [[Prototype]], Object.prototype.
You would effectively overlay Object.prototype.toString if you would try
to add a "toString" hash table entry and cause to property cease to work
as supposed.
Deliberatly. That's why I don't use the map for anything except property
lookup.
Or consider a "valueOf" hash table entry. Or "constructor".
Or ...
It is not a problem.

No, the point of wrapping in an instance of Map.Value is that no
preexisting property is an instance of Map.Value.

Even your Map and Map.Value instances have preexisting properties
inherited from Object. They may not be enumerable but they still
exist. There is no, I repeat, *no* object that has no "preexisting
properties".

Absolutely. What I was saying is that no preexisting property of the
object used as a map would be an instance of "Map.Value". That means
that any property of the map object can be tested for being an
instance of "Map.Value", and if it is, it's something I put there,
otherwise it should be ignored.
I won't debate that you can distinguish between added and built-in
properties and I did not. The point is that your implementation does
not prevent overlaying or overwriting built-in properties.
Agree completely. It depends on doing just that.
You control the read, but not the write process (yet).
Sure I do, unless the implementation is pathologically flawed.
No, it does not, because of

,-[ECMA 262 Edition 3, 2000-03-24]
|
| 2 Conformance And unfortunately(?), we are not living in a perfect standardized world.
Implementations make use of the opportunity described above, there is
escape(), unescape(), __proto__ and *much* more out there.
As long as a *new* object has no properties itself (not counting the ones
inherited from its prototype) that are read-only or don't-delete, then
it will work.

An implementation that makes a new object have a read-only or
don't-delete property that cannot be overwritten is asking for
trouble. Imagine

var x = new Object();
x.xyzzy = 42; // bang! "xyzzy" is read-only. Not a good idea!
Exactly ECMA-262 and the prototype chain presents the reason why your
hash table implementation "as is" is flawed.

No, the prototype chain guarantees that the read-only or don't-delete
properties of the prototype can be overwritten in the inheriting
object.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #28

Lasse Reichstein Nielsen wrote:

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Yes it must. The object used as a map here (this.map) is *only* used
for this purpose. Any property that it has inherited should be ignore,
and can safely be overwritten. That is, *if* they can be overwritten.
If so, you would overlay core properties leading to unexpected behavior
because the respective prototype property will not be accessed anymore.

No unexpected behavior will happen, as long as the object is only used
to look up properties in. No "core property" affects how [[Get]] and
[[Put]] works.

Unexpected behavior might happen if I overwrite the "toString"
property *and* tries to convert the object to a string, but I never do
that.

A toString() method, e.g., is really a nice-to-have for such hash tables
or collections, so I will try not to allow overlaying prototype properties
in my implementation (Collection in collection.js, available soon.)

And if not, you would have saved nothing in your "hash table". That
does not sound like a (reasonable/viable) solution.

Not understood.

Does not matter anymore.

This is not about host objects, it is about core properties *every*
object has.

That every object's *prototype* has. The object itself has no
properties.

Doing
new Object()
creates a new native ECMAScript object. It has no visible properties
itself, only the ones inherited from its [[Prototype]], Object.prototype.

ACK

You control the read, but not the write process (yet). ^^^^^ Sure I do, unless the implementation is pathologically flawed.
I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.
As long as a *new* object has no properties itself (not counting the ones
inherited from its prototype) that are read-only or don't-delete, then
it will work.
Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?
An implementation that makes a new object have a read-only or
don't-delete property that cannot be overwritten is asking for
trouble. Imagine

var x = new Object();
x.xyzzy = 42; // bang! "xyzzy" is read-only. Not a good idea!

Not a good idea for Object objects. Perfectly reasonable for others.
Exactly ECMA-262 and the prototype chain presents the reason why your
hash table implementation "as is" is flawed.

No, the prototype chain guarantees that the read-only or don't-delete
properties of the prototype can be overwritten in the inheriting
object.

ACK, but I would refrain from overlaying prototype properties anyway here.
PointedEars

Jul 23 '05 #29

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:

I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.
Correct. It shouldn't matter, though.
Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?
No. The "prototype" property is only relevant on function objects, and
the map object ("this.map") is just a normal object. It probably
doesn't have a property called "prototype", and if it does, it doesn't
do anything (not to be confuzed with the internal "[[Prototype]]"
property).

An implementation that makes a new object have a read-only or
don't-delete property that cannot be overwritten is asking for
trouble.

.... Not a good idea for Object objects. Perfectly reasonable for others.
Absolutely. Other types of Object, like those created by Array, will
have properties inherent to the specific object (e.g. "length"). Those
will be on the object itself, not its prototype, and can easily be
on-overwritable.
ACK, but I would refrain from overlaying prototype properties anyway here.

Out of curiosity: Why?

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Jul 23 '05 #30

Lasse Reichstein Nielsen wrote:

Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
I meant that you do not check if there is a prototype
property (yet) before over*writing*/overlaying it.

Correct. It shouldn't matter, though.

Hmmm.

Hmmm. If you overlay `prototype', you would destroy
(the possibility of) inheritance, would you not?

No. The "prototype" property is only relevant on function objects, and
the map object ("this.map") is just a normal object. [...]

Of course (oh my, it is really *hot* weather here!!1 :-)).
I meant `constructor' (and the like). Can you think of
overlaying one of them to interfere with normal operation
(toString() aside, which is obvious)?

ACK, but I would refrain from overlaying prototype properties anyway
here.

Out of curiosity: Why?

AFAIS it makes the implementation less flexible and thus restricts
the freedom of the users to apply it to their needs, effectively
making it less attractive to them.
PointedEars

Jul 23 '05 #31