ES4 draft: Map

Lars T Hansen lth at acm.org
Fri Feb 29 11:48:23 PST 2008


Sorry that this was unclear in the meta message. The helper function
is normative in the sense that it defines the functionality, eg in the
order of operations on a data structure. But it is not visible, not
part of the api, and a real implementation does not reserve the helper
namespace. Ditto for informative functions but their prose description
gives the implementation more room for variation. --lars

On 2/29/08, Michael O'Brien <mob at mbedthis.com> wrote:
> A general spec question about helper methods and the informative namespace?
>
> My presumption that both these are not part of the normative spec.
> Implementations may choose to implement the functionality without a helper
> method and without the specific informative elements. Is this correct?
>
> If so, then reading:
>
> "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: "
>
> really means that an implementation could use the helper method iterate as
> the RI does. If not, it must provide equivalent functionality.
>
> Am I reading the meaning of helper and informative correctly?
>
> Michael
>
>
> Lars Hansen wrote:
> I'm enclosing the draft for the Map class.  Please comment.
>
> --lars
>
> ________________________________
>
> 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 at mozilla.org
> https://mail.mozilla.org/listinfo/es4-discuss
>



More information about the Es4-discuss mailing list