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:               LAST CALL - 2008-03-20
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


LAST CALL NOTES

  * (Tickets #247, #289, and e-mail discussion.) The meta::invoke
    method will change when we change the meaning of statics in
    parameterized classes.  Concrete types 'K' and 'V' will have to be
    used in the invocation, and the returned 'Map' instance will be
    from 'K' to 'V' instead of from 'EnumerableId' to '*', like this:

       Map.<string,int>( { x: 10, y: 20 } )

  * Should the WG adopt some proposal for default type parameters for
    ES4 (not very likely) then the default values for 'K' and 'V' will
    be 'EnumerableId' and '*'.

  * The WG has agreed that for a parameterized type Cls and type T,
    Cls.<T> is a subtype of Cls.<*>.  That has yet to be
    fully formalized, but it is used here.


CHANGES SINCE DRAFT 3 (2008-03-11)

  * The type previously known as 'function' is now known as 'Callable'

  * Cleaned out FIXME comments in the text.


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.


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:   Callable = (function(a,b) a === b),
                        hashcode: Callable = intrinsic::hashcode) …

    static meta function invoke(object: Object=null): 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   : Callable = …
    private const hashcode : Callable = …
    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   : Callable = (function (x,y) x === y),
                    hashcode : Callable = intrinsic::hashcode)
    : equals = equals
    , hashcode = function (k) uint(hashcode(k) cast AnyNumber)
    , population = 0
{
}

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=null): Map.<EnumerableId,*> {
    if (object != null && 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;
}

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();