Draft 3 enclosed. Changelog near the top; the only significant change is fixing the bug Erik noted in the prototype get and put methods.
Please note one open issue; the current design is probably OK but I would appreciate comments. --lars > -----Original Message----- > From: Lars Hansen > Sent: 3. mars 2008 02:03 > To: Lars Hansen; es4-discuss@mozilla.org > Subject: RE: ES4 draft: Map > > Draft 2 enclosed (changelog near the top). > > --lars > > > -----Original Message----- > > From: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] On Behalf Of Lars Hansen > > Sent: 29. februar 2008 11:34 > > To: es4-discuss@mozilla.org > > Subject: ES4 draft: Map > > > > I'm enclosing the draft for the Map class. Please comment. > > > > --lars > >Title: The class "Map"
The class Map
NAME: "The class 'Map'"
FILE: spec/library/Map.html
CATEGORY: Pre-defined classes (E262-3 Chapter 15)
SOURCES: REFERENCES [1], [2], [3]
SPEC AUTHOR: Lars
DRAFT STATUS: DRAFT 3 - 2008-03-11
REVIEWED AGAINST ES3: N/A
REVIEWED AGAINST ERRATA: N/A
REVIEWED AGAINST BASE DOC: N/A
REVIEWED AGAINST PROPOSALS: YES
REVIEWED AGAINST CODE: YES
REVIEWED AGAINST TICKETS: YES
IMPLEMENTATION STATUS: ES4 RI
TEST CASE STATUS: Unknown
OPEN ISSUES
* 'intrinsic::clear' uses 'iterator::get' and 'intrinsic::remove' to
perform removal. That is by design (it allows overridden methods
that observe or modify iteration and removal to work during
clearing as well). But is it desirable?
CHANGES SINCE DRAFT 2 (2008-03-03)
* The prototype 'get' and 'put' methods also accept a 'notfound'
parameter.
* Presentation:
- section headers for intrinsic methods now use the syntax
'intrinsic::foo()' instead of just 'foo'.
- compatibility note ("new in 4th edition")
- added an explicit "extends Object" clause.
- the informative method 'allElements' was renamed as 'allItems'.
- corrected a typo
- common fields in the status block above
CHANGES SINCE DRAFT 1 (2008-02-29)
* The value returned by 'hashcode' is constrained to be a number and
is always explicitly converted to uint
* Map(x) returns x if x is a Map
* 'get' and 'put' have (V|undefined) return types
* 'get' and 'put' accept an optional value (defaulting to undefined)
which is returned if the association was not found in the map
* There is a new method 'clear' to clear the map
* The object returned from helper::iterate has been annotated with
an explicit type, fixing the next field.
NOTES
* Informative methods:
Informative methods on Map do not call program-visible (i.e.,
public, protected, intrinsic, reflect, meta, iterator, or
prototype) methods on their 'this' object except as explicitly
specified in this document.
(The above clarification belongs in a general preface to the
library.)
* Subtyping for parameterized classes: We've agreed that for a
parameterized type Cls and type T, Cls.<T> is a subtype of
Cls.<*>. That has yet to be fully formalized. The Map
class relies on that subtyping rule for its 'this' constraints on
prototype methods, and for type testing in the static
'meta::invoke' method.
REFERENCES
[1] http://wiki.ecmascript.org/doku.php?id=proposals:dictionary
[2] http://bugs.ecmascript.org/ticket/146
[3] http://bugs.ecmascript.org/ticket/203
The class Map is a parameterized, dynamic, non-final, direct
subclass of Object that provides a reliable, efficient, mutable,
and iterable map from keys to values. Keys and values may be of
arbitrary types.
COMPATIBILITY NOTE The class Map is new in the 4th Edition of this Standard.
A Map is realized as a hash table. When the Map is
constructed the caller may provide specialized functions that compare
keys and compute hash values for keys.
Synopsis
The class Map provides the following interface:
__ES4__ dynamic class Map.<K,V> extends Object
{
public function Map(equals: function = (function(a,b) a === b),
hashcode: function = intrinsic::hashcode) …
static meta function invoke(object: Object): Map.<EnumerableId,*> …
static public const length = 2;
intrinsic function size() : uint …
intrinsic function get(key: K, notfound: (V|undefined)=undefined) : (V|undefined) …
intrinsic function put(key: K, value: V, notfound: (V|undefined)=undefined) : (V|undefined) …
intrinsic function has(key:K) : boolean …
intrinsic function remove(key:K) : boolean …
intrinsic function clear() : void …
iterator function get(deep: boolean = false) : iterator::IteratorType.<K> …
iterator function getKeys(deep: boolean = false) : iterator::IteratorType.<K> …
iterator function getValues(deep: boolean = false) : iterator::IteratorType.<V> …
iterator function getItems(deep: boolean = false) : iterator::IteratorType.<[K,V]> …
private const equals : function = …
private const hashcode : function = …
private var population : uint = …
}
The Map prototype object provides these direct properties:
size: function () …
get: function (key, notfound) …
put: function (key, value, notfound) …
has: function (key) …
remove: function (key) …
clear: function () …
Methods on the Map class object
new Map.<K,V>( equals=…, hashcode=… )
Description
The Map constructor creates a new map for key type K
and value type V.
The optional equals argument is a function that compares two
keys and returns true if they are equal and false if they are
not. This function must implement a reflexive, transitive, and
symmetric relation, and equals(k1,k2) must be constant for any two
actual keys k1 and k2. The default value for equals is a
function that compares the two keys using the === operator.
The optional hashcode argument is a function that takes a key
and returns a numeric value for it; this key is converted to a uint
hash value for the key. The hash value may be used to find
associations more quickly in the map. Two calls to hashcode on
the same key value must always result in the same hash value, and a
call to hashcode must always result in the same hash value for two
key values that compare equal by the equals function. The default
value for hashcode is the intrinsic global function hashcode.
NOTE The constraint that equals and hashcode return
constant values does not apply to key values that are not in a Map
nor referenced from an activation of any method on Map.
NOTE There is no requirement that the values returned from hashcode for two unequal keys must be different.
NOTE The operator == is not a valid comparator for the global
intrinsic function hashcode because == will consider some
values to be equal for which hashcode returns different hash
values.
Implementation
The Map constructor initializes the Map object by
saving its parameters in private storage and initializing the count of
the number of associations in the table to zero.
public function Map(equals /*: function*/ = (function (x,y) x === y),
hashcode /*: function*/ = intrinsic::hashcode)
: equals = equals
, hashcode = function (k) uint(hashcode(k) cast AnyNumber)
, population = 0
{
}
FIXME (Ticket #153) The parameters to the Map constructor should
be constrained to be function, but not any more than that (because
that would be bad UI for scripts). Currently the RI does not support
function as a type annotation, so the current implementation of
the constructor is unconstrained.
Map( object )
Description
When the Map class object is called as a function, it
returns a Map object. If object is already a Map object
of any type then it is returned. Otherwise, a new Map object from
EnumerableId to * is created and is populated with the own
properties of object.
Returns
The Map class object called as a function returns a Map
object.
Implementation
static meta function invoke(object: Object): Map.<EnumerableId,*> {
if (object is Map.<*,*>)
return object;
let d = new Map.<EnumerableId,*>;
for (let n in object)
if (object.intrinsic::hasOwnProperty(n))
d.put(n, object[n]);
return d;
}
FIXME (Tickets #247, #289, and e-mail discussion.) This method will
change if we change the meaning of statics in parameterized classes:
the map would be from K to V instead of from EnumerableId to *.
Methods on Map instances
intrinsic::size ( )
Returns
The intrinsic method size returns the number of associations in the map.
Implementation
intrinsic function size() : uint
population;
intrinsic::get ( key, notfound=… )
Returns
The intrinsic method get returns the value associated with
key, or notfound if there is no such association.
Implementation
intrinsic function get(key: K, notfound: (V|undefined)=undefined) : (V|undefined) {
let probe = informative::find(key);
return probe ? probe.value : notfound;
}
The informative function find searches for key in the
Map and returns an object containing at least the properties
key and value if the association was found, or otherwise
null. (The returned object is part of the Map data structure,
and writing to it updates the association in the Map.)
informative function find(key: K): like { key: K, value: V } …
intrinsic::put ( key, value, notfound=… )
Description
The intrinsic method put creates an association between
key and value, or overwrites an existing association if there
is one.
Returns
The put method returns the old value of the association if
there was one, otherwise it returns notfound.
Implementation
intrinsic function put(key: K, value: V, notfound: (V|undefined)=undefined) : (V|undefined) {
let oldvalue = notfound;
let probe = informative::find(key);
if (probe) {
oldvalue = probe.value;
probe.value = value;
}
else {
++population;
informative::insert(key, value);
}
return oldvalue;
}
The informative function insert adds a new association between
key and value to the Map.
informative function insert(key: K, value: V): void …
intrinsic::has ( key )
Returns
The intrinsic method has returns true if there exists
an association for key, or false otherwise.
Implementation
intrinsic function has(key:K) : boolean {
let probe = informative::find(key);
return probe ? true : false;
}
intrinsic::remove ( key )
Description
The intrinsic method remove removes any association for key.
Returns
The remove method returns true if there was an association for key,
or false otherwise.
Implementation
intrinsic function remove(key:K) : boolean {
let probe = informative::find(key);
if (probe) {
--population;
informative::eject(probe);
return true;
}
return false;
}
The informative function eject removes the association for
key from the Map.
informative function eject(box: like { key: K, value: V }): void …
intrinsic::clear ( )
Description
The intrinsic method clear removes all associations from the map.
Returns
The clear method returns nothing.
Implementation
intrinsic function clear() : void {
for (let k in this)
intrinsic::remove(k);
}
Iteration protocol on Map instances
The iterator protocol makes use of a helper method iterate
which first collects the values that will be returned by the iterator
methods and then returns an object that provides the correct next
method:
helper function iterate.<T>(f) {
let a = [];
informative::allItems(function (k,v) { f(a,k,v) });
return {
const next:
let (i=0, limit=a.length)
function () : T {
if (i < limit)
return a[i++];
throw iterator::StopIteration;
}
} : iterator::IteratorType.<T>;
}
The informative function allItems calls its function
argument on every key/value pair in the Map:
informative function allItems(fn: function): void …
The iterator methods getKeys, getValues, and getItems
return iterator objects that iterate over keys, values, and key/value
pairs, respectively. The iterator method get iterates over keys
(like getKeys).
Implementation
iterator function getKeys(deep: boolean = false) : iterator::IteratorType.<K>
helper::iterate.<K>(function (a,k,v) { a.push(k) });
iterator function getValues(deep: boolean = false) : iterator::IteratorType.<V>
helper::iterate.<V>(function (a,k,v) { a.push(v) });
iterator function getItems(deep: boolean = false) : iterator::IteratorType.<[K,V]>
helper::iterate.<[K,V]>(function (a,k,v) { a.push([k,v]) });
iterator function get(deep: boolean = false) : iterator::IteratorType.<K>
iterator::getKeys(deep);
Methods on the Map prototype object
The methods on the Map prototype object are constrained to
being called on instances of Map. They all delegate to the
corresponding intrinsic method on their this object.
prototype function size(this: Map.<*,*>)
this.intrinsic::size();
prototype function get(this: Map.<*,*>, key, notfound)
this.intrinsic::get(key, notfound);
prototype function put(this: Map.<*,*>, key, value, notfound)
this.intrinsic::put(key, value, notfound);
prototype function has(this: Map.<*,*>, key)
this.intrinsic::has(key);
prototype function remove(this: Map.<*,*>, key)
this.intrinsic::remove(key);
prototype function clear(this: Map.<*,*>)
this.intrinsic::clear();
_______________________________________________ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss
