Vector
FILE: spec/library/Vector.html
DRAFT STATUS: DRAFT 1 - ROUGH - 2008-03-03
IMPLEMENTATION STATUS: ES4 RI
REVIEWED AGAINST ES3: N/A
REVIEWED AGAINST ERRATA: N/A
REVIEWED AGAINST BASE DOC: N/A
REVIEWED AGAINST PROPOSALS: NO
REVIEWED AGAINST CODE: NO
KNOWN DISCREPANCIES AGAINST PROPOSALS
* Proposals call for a method 'setSlice' supposedly specified in
JS1.8. But the JS1.8 docs do not define it.
OPEN ISSUES
* Should 'filter', 'map', and 'slice' return a vector whose 'fixed'
property is true if the 'fixed' property of the vector they were
generated from is true?
NOTES
* The proposal uses the phrase "default value appropriate to the
base type T" in a few places. This is the value 0 for numeric
types; the empty string for string types; false for boolean types;
undefined for the undefined type; and null for all other types.
A function that takes a type object and computes the correct
default value is expressible in ES4 and may be incorporated
into the library spec later.
* No namespaces are explicitly opened in the scope surrounding the
definition of Vector. If the normative fragments do not show an
explicit qualification on a name then the name referenced is the
public one.
* As a general rule, when invoking methods on objects passed as
arguments, the Vector methods (like other methods in the library)
invoke public methods on the received objects. For example, the
'toLocaleString' method is careful to call the public
'toLocaleString' method on its arguments, and 'every', 'filter',
'forEach', 'map', and so on call the public 'call' methods on
their function arguments.
The class Vector is a parameterized, dynamic, direct subclass
of Object. It represents dense, typed, 0-based, one-dimensional
arrays with bounds checking and optionally fixed length.
The class Vector provides two benefits. One is optimization:
the restrictions placed on the class---denseness and a predefined
iteration order---make it possible for ECMAScript implementations to
implement it particularly efficiently. The other is error checking:
Vector provides stronger type checking and bounds checking than
Array.
COMPATIBILITY NOTE The class Vector is new in the 4th Edition of this
Standard.
The class Vector provides a method suite that is largely
compatible with the class Array.
NOTE It is likely that many current uses of Array can be
switched over to Vector without much work, and programs that can
be switched will receive the benefits of stronger type and bounds
checking.
The type parameter of the Vector is called its base type.
As the Vector class is dynamic, new properties can be added to
its instances but any property whose name is a number (an instance of
any class in the union type AnyNumber) is handled specially.
These properties are called indexed properties.
Only indexed properties named by nonnegative integers less than
the value of the property length are defined, and only indexed
properties named by nonnegative integers less than 232-1
can be defined.
Any attempt to read an undefined indexed property results in a RangeError exception being thrown.
Any attempt to write an undefined indexed property results in a
RangeError being thrown unless the index is equal to the current
value of length, the current value of length is not
232-1, and the value of the property fixed is not
true.
The property fixed is a flag that determines whether the
vector has fixed length or not. Any attempt to update the value of
length fails if the fixed property has the value true.
NOTE If v is a Vector then reading and writing v[3.14]
or v[-3] will always fail, though reading and writing
v["3.14"] or v["-3"] will succeed.
This behavior deviates from the 3rd Edition, where
strings and numbers are interchangeable as property names. But that's
no longer quite true in 4th Edition anyway, which has have namespaces
and Name objects.
Most attempts to set or get properties that are named
by numbers that are not valid array indices are probably errors,
especially if the object is an Array. Most attempts to read beyond
the end of an Array are probably errors. And in a number of cases,
attempts to write beyond the end of an Array are probably errors too.
The Vector class makes it possible to discover these errors.
All indexed properties named by nonnegative integers less than
length are always defined.
NOTE As a consequence, a Vector does not have "holes" in its
index range in the way an Array does.
The class Vector provides the following interface:
__ES4__ dynamic class Vector.<T>
{
public function Vector(length: uint=0, fixed: boolean=false) …
static meta function invoke(object) …
static const length = 2;
override intrinsic function toString() …
override intrinsic function toLocaleString() …
intrinsic function concat(...items): Vector.<T> …
intrinsic function every(checker: Checker, thisObj: Object=null): boolean …
intrinsic function filter(checker: Checker, thisObj: Object=null): Vector.<T> …
intrinsic function forEach(eacher: Eacher, thisObj: Object=null): void …
intrinsic function indexOf(value: T, from: AnyNumber=0): AnyNumber …
intrinsic function join(separator: string=","): string …
intrinsic function lastIndexOf(value: T, from: AnyNumber=Infinity): AnyNumber …
intrinsic function map(mapper:Mapper, thisObj:Object=null) …
intrinsic function pop(): T …
intrinsic function push(...items): uint …
intrinsic function reduce(reducer/*: function*/, initialValue:(T|None)=NONE ): T …
intrinsic function reduceRight(reducer/*: function*/, initialValue:(T|None)=NONE ): T …
intrinsic function reverse(): Vector.<T> …
intrinsic function shift(): T …
intrinsic function slice(start: AnyNumber=0, end: AnyNumber=Infinity, step: AnyNumber=1): Vector.<T> …
intrinsic function some(checker: Checker, thisObj: Object=null): boolean …
intrinsic function sort(comparefn: function(T, T): AnyNumber): Vector.<T> …
intrinsic function splice(start: AnyNumber, deleteCount: AnyNumber, ...items): Vector.<T> …
intrinsic function unshift(...items): uint …
iterator function get(deep: boolean = false) : iterator::IteratorType.<uint> …
iterator function getKeys(deep: boolean = false) : iterator::IteratorType.<uint> …
iterator function getValues(deep: boolean = false) : iterator::IteratorType.<T> …
iterator function getItems(deep: boolean = false) : iterator::IteratorType.<[uint,T]> …
public var fixed: boolean …
public final function get length() …
public final function set length(len: AnyNumber) …
meta final function get(name): T …
meta final function set(name, v): void …
meta final function has(name) …
meta final function delete(name) …
}
The types Checker, Eacher, and Mapper are as for the Array class
(see class Array).
The Vector prototype object provides these direct properties:
toString: function () …
toLocaleString: function () …
concat: function (...items) …
every: function (checker, thisObj) …
filter: function (checker, thisObj) …
forEach: function (eacher, thisObj) …
indexOf: function (value, from) …
join: function (separator) …
lastIndexOf: function (value, from) …
map: function (mapper, thisObj) …
pop: function () …
push: function (...items) …
reduce: function (callback, initialValue) …
reduceRight: function (callback, initialValue) …
reverse: function () …
shift: function () …
slice: function (start, end) …
some: function (checker, thisObj) …
sort: function (comparefn) …
splice: function (start, deleteCount, ...items) …
unshift: function (...items) …
Vector class objectDescription
The Vector constructor initializes a new Vector object.
Length is the inital value of the length property. Its
default value is zero. Every indexed element of the new vector below
length is initialized to a default value that is appropriate to
the base type T.
Fixed is the initial value of the fixed property. Its
default value is false.
Implementation
The Vector constructor is implementation-defined.
Description
When the Vector class object is called as a function, it
creates a new variable-length Vector object of type *, giving
it the initial length of the length property of object and
initial element values extracted from object between indices 0
and object.length.
Returns
The Vector class object called as a function returns a new
Vector object.
Implementation
static meta function invoke(object) {
if (object is Vector.<*>)
return object;
let length = uint(object.length);
let result = new Vector.<*>(length);
for ( let i=0 ; i < length ; i++ )
result[i] = object[i];
return result;
}
Vector instancesDescription
The intrinsic toString method converts the vector to a string.
It has the same effect as if the join method were invoked for this
object with no argument.
Returns
The toString method returns a string.
Implementation
override intrinsic function toString()
intrinsic::join();
Description
The intrinsic toLocaleString method converts the Vector
to a string in the following manner.
Elements of this Vector are converted to strings using their
public toLocaleString methods, and these strings are then
concatenated, separated by occurrences of a separator string that has
been derived in an implementation-defined locale-specific way. The
result of calling this function is intended to be analogous to the
result of toString, except that the result of this function is
intended to be locale-specific.
Returns
The toLocaleString method returns a string.
Implementation
override intrinsic function toLocaleString() {
let limit = length;
let separator = informative::localeSpecificSeparatorString();
let s = "";
let i = 0;
while (true) {
let x = this[i];
if (x !== undefined && x !== null)
s += x.toLocaleString();
if (++i == limit)
break;
s += separator;
}
return s;
}
NOTE The first parameter to this method is likely to be used in a future version of this standard; it is recommended that implementations do not use this parameter position for anything else.
Description
The intrinsic concat method collects the vector elements
from this followed by the vector elements from the additional
items, in order, into a new Vector object. All the items
must be Vector instances whose base types are subtypes of the base
type of this.
Returns
The concat method returns a new Vector object with the
same base type as this.
Implementation
intrinsic function concat(...items): Vector.<T>
helper::concat(items);
helper function concat(items) {
let v = new Vector.<T>;
let k = 0;
for ( let i=0, limit=length ; i < limit ; i++ )
v[k++] = this[i];
for ( let j=0 ; j < items.length ; j++ ) {
let item = items[j] cast Vector.<T>;
for ( let i=0, limit=item.length ; i < limit ; i++ )
v[k++] = item[i];
}
return v;
}
FIXME Need to check a detail of the type system, namely whether
Vector.<T> is a subtype of Vector.<U> if T is a
subtype of U and U is not *.
Description
The intrinsic every method calls checker on every
vector element of this in increasing index order, stopping as soon
as any call returns false.
Checker is called with three arguments: the vector element
value, the vector element index, and this. ThisObj is used as
the this object in the call.
Returns
The every method returns true if all the calls to
checker returned true values, otherwise it returns false.
Implementation
intrinsic function every(checker: Checker, thisObj: Object=null): boolean {
for ( let i=0, limit=length ; i < limit ; i++ )
if (!checker.call(thisObj, this[i], i, this))
return false;
return true;
}
Description
The intrinsic filter method calls checker on every
vector element of this in increasing index order, collecting all
the vector elements for which checker returns a true value.
Checker is called with three arguments: the vector element
value, the vector element index, and this. ThisObj is used as
the this object in the call.
Returns
The filter method returns a new Vector object with the
same base type as this, containing the elements that were
collected, in the order they were collected. The length of the new
Vector is equal to the number of values that were collected.
Implementation
intrinsic function filter(checker: Checker, thisObj: Object=null): Vector.<T> {
var result = new Vector.<T>;
for ( let i=0, limit=length ; i < limit ; i++ )
if (checker.call(thisObj, this[i], i, this))
result[result.length] = this[i];
return result;
}
Description
The intrinsic forEach method calls eacher on every
vector element of this in increasing index order, discarding any
return value of eacher.
Eacher is called with three arguments: the vector element
value, the vector element index, and this. ThisObj is used as
the this object in the call.
Returns
The forEach method does not return a value.
Implementation
intrinsic function forEach(eacher: Eacher, thisObj: Object=null): void {
for ( let i=0, limit=length ; i < limit ; i++ )
eacher.call(thisObj, this[i], i, this);
}
The helper function clamp performs clamping of from to the
length of this Vector.
helper function clamp(val: AnyNumber, len: uint): uint {
val = helper::toInteger(val);
if (val < 0)
val += len;
return uint( Math.min( Math.max( val, 0 ), len ) );
}
NOTE The helper function toInteger, used by clamp, is
described elsewhere; it performs the ToInteger operation of the
3rd Edition.
Description
The intrinsic indexOf method compares value with every
vector element of this in increasing index order, starting at the
index from, stopping when a vector element is equal to value
by the === operator.
If from is negative, it is treated as
this.length+from.
Returns
The static indexOf method returns the vector index the first
time value is equal to an element, or -1 if no such element is
found.
Implementation
intrinsic function indexOf(value: T, from: AnyNumber=0): AnyNumber {
let start = helper::clamp( from, length );
for ( let i=start, limit=length ; i < limit ; i++ )
if (this[i] === value)
return i;
return -1;
}
Description
The intrinsic join method concatenates the string
representations of the vector elements of this in increasing index
order, separating the individual strings by occurrences of
separator.
Returns
The join method returns the concatenated string.
Implementation
intrinsic function join(separator: string=","): string {
let limit = length;
let s = "";
let i = 0;
for (let i = 0; i < limit; i++) {
let x = this[i];
if (i != 0)
s += separator;
if (x !== undefined && x !== null)
s += string(x);
}
return s;
}
Description
The intrinsic lastIndexOf method compares value with every
vector element of this in decreasing numerical index order,
starting at the index from, stopping when a vector element is
equal to value by the === operator.
If from is negative, it is treated as
this.length+from.
Returns
The lastIndexOf method returns the vector index the first
time value is equal to an element, or -1 if no such element is
found.
Implementation
intrinsic function lastIndexOf(value: T, from: AnyNumber=Infinity): AnyNumber {
let start = helper::clamp( from, length );
for ( let i=start ; i >= 0 ; i-- )
if (this[i] === value)
return i;
return -1;
}
Description
The intrinsic map method calls mapper on each vector
element of this in increasing numerical index order, collecting
the return values from mapper.
Mapper is called with three arguments: the vector element
value, the vector element index, and this. ThisObj is used as
the this object in the call.
Returns
The map method returns a new Vector object of the same
base type and length as this Vector. The element at index i
in the new vector is the value collected from the call to mapper
on this[i].
Implementation
intrinsic function map(mapper:Mapper, thisObj:Object=null) {
var result = new Vector.<T>(length);
for ( let i=0, limit=length ; i < limit ; i++ )
result[i] = mapper.call(thisObj, this[i], i, this);
return result;
}
Description
The intrinsic pop method extracts the last vector element
from this and removes it by decreasing the value of the length
property of this by 1.
Returns
The pop method returns the removed element, or the
appropriate default value for the base type of this if there are
no elements.
Implementation
intrinsic function pop(): T {
if (length == 0)
return undefined;
let v = this[length-1];
length--;
return v;
}
Description
The intrinsic push method appends the values in items
to this Vector, in the order in which they appear in items.
The length property of this Vector will be incremented by the
length of items.
Returns
The push method returns the new value of the length
property of this Vector.
Implementation
intrinsic function push(...items): uint
helper::push(items);
helper function push(items) {
for ( let i=0, limit=items.length ; i < limit ; i++ )
this[length] = items[i];
return length;
}
Description
The intrinsic reverse method rearranges the vector elements of
this so as to reverse their order. The length property of
this remains unchanged.
Returns
The reverse method returns this.
Implementation
intrinsic function reverse(): Vector.<T> {
for ( let i=0, j=length-1 ; i < j ; i++, j-- )
[this[i], this[j]] = [this[j], this[i]];
return this;
}
Description
The intrinsic shift method removes the element called 0 in
this, moves the element at index i+1 to index i, and
decrements the length property of this by 1.
Returns
The shift method returns the element that was removed.
Implementation
intrinsic function shift(): T {
if (length == 0)
return undefined;
let v = this[0];
for ( let i=1, limit=length ; i < limit ; i++ )
this[i-1] = this[i];
length--;
return v;
}
Description
The intrinsic slice method extracts the subrange of array
elements from this between start (inclusive) and end
(exclusive) into a new Array. Each step element is taken.
The default value of start is 0. If it is negative, it is
treated as object.length+start.
The default value of end is Infinity. If it is negative, it
is treated as object.length+end.
The default value of step is 1. If it is 0, it is set to 1.
Returns
The slice method returns a new Vector object with the
same base type as this, containing the extracted vector elements.
Implementation
intrinsic function slice(start: AnyNumber=0, end: AnyNumber=Infinity, step: AnyNumber=1): Vector.<T> {
step = helper::toInteger(step);
if (step == 0)
step = 1;
start = helper::clamp(start, length);
end = helper::clamp(end, length);
let result = new Vector.<T>;
if (step > 0)
for (let i=start; i < end ; i += step)
result[result.length] = this[i];
else
for (let i=start; i > end ; i += step)
result[result.length] = this[i];
return result;
}
Description
The intrinsic some method calls checker on every vector
element in this in increasing index order, stopping as soon as
checker returns a true value.
Checker is called with three arguments: the vector element
value, the vector element index, and this. ThisObj is used as
the this object in the call.
Returns
The some method returns true when checker returns a
true value, otherwise returns false if all the calls to
checker return false values.
Implementation
intrinsic function some(checker: Checker, thisObj: Object=null): boolean {
for ( let i=0, limit=length ; i < limit ; i++ )
if (checker.call(thisObj, this[i], i, this))
return true;
return false;
}
Description
The intrinsic::sort method sorts the vector elements of
this according to the ordering defined by comparefn.
The sort is not necessarily stable (that is, elements that compare
equal do not necessarily remain in their original order).
Comparefn must be a consistent (see sorting-logic)
function that accepts two arguments x and y of the base type
of this and returns a negative value if x < y, zero if x
= y, or a positive value if x > y.
COMPATIBILITY NOTE Unlike the case for Array, the comparefn is a required argument.
FIXME (Ticket #197.) Should we provide a default comparator?
Returns
The sort method returns this.
Implementation
The sort method calls on the generic sorting engine, passing a
function to compare elements of this.
intrinsic function sort(comparefn: function(T, T): AnyNumber): Vector.<T> {
let object = this;
informative::sortEngine(object,
0,
length-1,
(function (j, k) comparefn(object[j], object[k])));
}
NOTE For a description of the informative sortEngine method, see
sorting-logic.
FIXME The signature of comparefn is probably too constraining,
it will require the client to pass a strongly-typed function.
Description
The intrinsic splice method replaces the deleteCount vector
elements of this starting at index start with values
from the items.
Returns
The splice method returns a new Vector object of the
same base type as this, containing the vector elements that were
removed from this, in order.
Implementation
intrinsic function splice(start: AnyNumber, deleteCount: AnyNumber, ...items): Vector.<T>
helper::splice(start, deleteCount, items);
helper function splice(start, deleteCount, items) {
let first = helper::clamp( start, length );
let delcnt = helper::clamp( deleteCount, length-first );
let result = new Vector.<T>;
for ( let n=0, i=first ; n < delcnt ; n++, i++ )
result[result.length] = this[i];
if (items.length < delcnt) {
let shift = delcnt - items.length;
for ( let n=0, i=first; n < shift ; n++, i++ )
this[i] = this[i+shift];
length -= shift;
}
else {
let shift = items.length - delcnt;
for ( let n=shift-1, i=first+shift; n >= 0 ; n--, i-- )
this[i] = this[i-shift];
}
for ( let n=0, i=first ; n < items.length ; n++, i++ )
this[i] = items[n];
return result;
}
Description
The instrinsic unshift method inserts the values in
items as new vector elements at the start of this, such that
their order within the vector elements of this is the same as the
order in which they appear in items. Existing vector elements in
this are shifted upward in the index range, and the length
property of this is updated.
Returns
The unshift method returns the new value of the
length property of this.
Implementation
intrinsic function unshift(...items): uint
helper::unshift(items);
helper function unshift(items) {
let numitems = items.length;
let oldlimit = length;
let newlimit = oldlimit + numitems;
for ( let i=0 ; i < numitems ; i++ )
this[newlimit-i] = this[oldlimit-i];
for ( let i=0 ; i < numitems ; i++ )
this[i] = items[i];
return newlength;
}
Vector instances Iterators are defined on the Vector such that for-in
and for each-in loops always iterate across the vector from
low indices toward high indices. Only indexed properties defined on
directly on the vector object are visited.
Implementation
iterator function get(deep: boolean = false) : iterator::IteratorType.<uint>
getKeys(deep);
iterator function getKeys(deep: boolean = false) : iterator::IteratorType.<uint> {
let i = 0;
let a = this;
return {
const next:
function () : uint {
if (i < a.length)
return i++;
throw iterator::StopIteration;
}
} : iterator::IteratorType.<uint>;
}
iterator function getValues(deep: boolean = false) : iterator::IteratorType.<T> {
let i = 0;
let a = this;
return {
const next:
function () : T {
if (i < a.length)
return a[i++];
throw iterator::StopIteration;
}
} : iterator::IteratorType.<T>;
}
iterator function getItems(deep: boolean = false) : iterator::IteratorType.<[uint,T]> {
let i = 0;
let a = this;
return {
const next:
function () : T {
if (i === a.length)
return [i,a[i++]];
throw iterator::StopIteration;
}
} : iterator::IteratorType.<[uint,T]>;
}
Vector instances The property length determines the range of valid indices into
the Vector. Indices up to but not including length are always
defined.
When length is given a new value that is smaller than its old
value then the elements in the vector at the new length and beyond are
removed from the vector.
When length is given a new value that is greater than its old
value then the elements in the vector at the old length and beyond are
given a default value that is appropriate to the base type T.
If an attempt is made to set length when the fixed property
is true then a RangeError is thrown.
If an attempt is made to set length to any value that is not a
nonnegative integer less than 232 then a RangeError is
thrown.
The boolean property fixed determines whether the Vector
has fixed length.
If fixed has the value true then any attempt to change
length will result in in a RangeError being thrown.
The value of fixed is not constant, so vectors can be of fixed
length and variable length at different times.
A Vector contains all properties whose names are nonnegative
integers below the value of the Vector's length property.
If an attempt is made to read a property whose name is a number that
is not a nonnegative integer below length then a RangeError is thrown.
If an attempt is made to write a property whose name is a number that is not
a nonnegative integer below length then one of two things happen:
fixed property has the value true, or if the
number is not a nonnegative integer, or if the number is nonnegative but
not the same value as the value of length, or if length is
already 232-1, then a RangeError is thrown.
length property is incremented by 1.
Vector prototype objectDescription
The methods on the Vector prototype object perform a small
amount of type conversion and delegate to the corresponding intrinsic
methods.
Returns
The methods on the Vector prototype object return what their
corresponding intrinsic methods return.
Implementation
prototype function toString(this:Vector.<*>)
this.intrinsic::toString();
prototype function toLocaleString(this:Vector.<*>)
this.intrinsic::toLocaleString();
prototype function concat(this:Vector.<*>, ...items)
this.helper::concat(items);
prototype function every(this:Vector.<*>, checker, thisObj=undefined)
(this.intrinsic::every(checker, thisObj is Object) ? thisObj : null);
prototype function filter(this:Vector.<*>, checker, thisObj=undefined)
(this.intrinsic::filter(checker, thisObj is Object) ? thisObj : null);
prototype function forEach(this:Vector.<*>, eacher, thisObj=undefined)
(this.intrinsic::forEach(checker, thisObj is Object) ? thisObj : null);
prototype function indexOf(this:Vector.<*>, value, from=undefined)
this.intrinsic::indexOf(value, Number(from));
prototype function join(this:Vector.<*>, separator=undefined)
this.intrinsic::join(separator == undefined ? "," : string(separator));
prototype function lastIndexOf(this:Vector.<*>, value, from=undefined)
this.intrinsic::indexOf(value, from == undefined ? Infinity : Number(from));
prototype function map(this:Vector.<*>, mapper, thisObj=undefined)
(this.intrinsic::map(mapper, thisObj is Object) ? thisObj : null);
prototype function pop(this:Vector.<*>)
this.intrinsic::pop();
prototype function push(this:Vector.<*>, ...items)
this.helper::push(items);
prototype function reverse(this:Vector.<*>)
this.intrinsic::reverse();
prototype function shift(this:Vector.<*>)
this.intrinsic::shift();
prototype function slice(this:Vector.<*>, start, end, step)
this.intrinsic::slice(Number(start), Number(end), Number(step));
prototype function some(this:Vector.<*>, checker, thisObj=undefined)
(this.intrinsic::some(checker, thisObj is Object) ? thisObj : null);
prototype function sort(this:Vector.<*>, comparefn)
this.intrinsic::sort(comparefn);
prototype function splice(this:Vector.<*>, start, deleteCount, ...items)
this.helper::splice(Number(start), Number(deleteCount), items);
prototype function unshift(this:Vector.<*>, ...items)
this.helper::unshift(items);