I'm enclosing the draft for the Map class. Please comment.
--lars
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: YES
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.
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>
{
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 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 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 on Map.
NOTE There is no requirement that the values
returned from
hashcode for two unequal keys must be different.
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 = hashcode
, 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
creates a new Map object from EnumerableId
to *,
populating the new Map object with the own properties of
object.
Returns
The Map class object
called as a function returns a new
Map 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 instances
size ( )
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 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 } …
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 the Map.
informative function insert(key: K, value: V): void …
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;
}
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 …
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: 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 the Map:
informative function allElements(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)
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
