I'm enclosing the draft for the Map class. Please comment. --larsTitle: The class "Map"
The class Map
FILE: spec/library/Map.html DRAFT STATUS: DRAFT 1 - 2008-02-29 IMPLEMENTATION STATUS: ES4 RI TEST CASE STATUS: Unknown REVIEWED AGAINST ES3: N/A REVIEWED AGAINST ERRATA: N/A REVIEWED AGAINST BASE DOC: N/A REVIEWED AGAINST PROPOSALS: YES REVIEWED AGAINST CODE: YESThe class
Map
is a parameterized, dynamic, non-final, direct subclass ofObject
that provides a reliable, efficient, mutable, and iterable map from keys to values. Keys and values may be of arbitrary types.A
Map
is realized as a hash table. When theMap
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> { 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) : V intrinsic function put(key:K, value:V) : void intrinsic function has(key:K) : boolean intrinsic function remove(key:K) : boolean 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) put: function (key, value) has: function (key) remove: function (key)Methods on the
Map
class objectnew 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 code for it. This code may be used to find associations more quickly in the map. Two calls to the hashcode function on the same key value must return the same numeric code, and the hashcode function must always return the same numeric code for two objects 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 onMap
.NOTE There is no requirement that the values returned from hashcode for two unequal keys must be different.
Implementation
The
Map
constructor initializes theMap
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 = hashcode , population = 0 { }FIXME (Ticket #153) The parameters to the
Map
constructor should be constrained to befunction
, but not any more than that (because that would be bad UI for scripts). Currently the RI does not supportfunction
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 creates a newMap
object fromEnumerableId
to*
, populating the newMap
object with the own properties of object.Returns
The
Map
class object called as a function returns a newMap
object.Implementation
static meta function invoke(object: Object): Map.<EnumerableId,*> { 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 may change if we change the meaning of statics in parameterized classes: the map would be to the type
V
instead of to*
.Methods on
Map
instancessize ( )
Returns
The intrinsic method
size
returns the number of associations in the map.Implementation
intrinsic function size() : uint population;get ( key )
Returns
The intrinsic method
get
returns the value associated with key, or null if there is no such association.Implementation
intrinsic function get(key: K) : V { let probe = informative::find(key); return probe ? probe.value : null; }The informative function
find
searches for key in theMap
and returns an object containing at least the propertieskey
andvalue
if the association was found, or otherwise null. (The returned object is part of theMap
data structure, and writing to it updates the association in theMap
.)informative function find(key: K): like { key: K, value: V }put ( key, value )
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 nothing.Implementation
intrinsic function put(key:K, value:V) : void { let probe = informative::find(key); if (probe) probe.value = value; else { ++population; informative::insert(key, value); } }The informative function
insert
adds a new association between key and value to theMap
.informative function insert(key: K, value: V): voidhas ( 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; }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 theMap
.informative function eject(box: like { key: K, value: V }): voidIteration protocol on
Map
instancesThe 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 correctnext
method:helper function iterate.<T>(f: function(*,*,*):*) { let a = []; informative::allElements(function (k,v) { f(a,k,v) }); return { next: let (i=0, limit=a.length) function () : T { if (i < limit) return a[i++]; throw iterator::StopIteration; } }; }The informative function
allElements
calls its function argument on every key/value pair in theMap
:informative function allElements(fn: function): voidThe iterator methods
getKeys
,getValues
, andgetItems
return iterator objects that iterate over keys, values, and key/value pairs, respectively. The iterator methodget
iterates over keys (likegetKeys
).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 objectThe methods on the
Map
prototype object are constrained to being called on instances ofMap
. They all delegate to the corresponding intrinsic method on theirthis
object.prototype function size(this: Map.<*,*>) this.intrinsic::size(); prototype function get(this: Map.<*,*>, key) this.intrinsic::get(key); prototype function put(this: Map.<*,*>, key, value) this.intrinsic::put(key, value); prototype function has(this: Map.<*,*>, key) this.intrinsic::has(key); prototype function remove(this: Map.<*,*>, key) this.intrinsic::remove(key);_______________________________________________ Es4-discuss mailing list Es4-discuss@mozilla.org https://mail.mozilla.org/listinfo/es4-discuss