Vector

Overview

Table implementation of a general purpose vector. Provides constant time random access and worst-case linear time insertions and deletions in the middle of the list.

Indices in the vector start at 1 go to size(), and can be negative. Negative indices count backward from the end of the vector: get(-1) returns the last element, get(-2) returns the second to last element, get(-size()) returns the first element, etc. Any method that accepts index arguments can use negative indexing. Indexing modes can be mixed in the same call, i.e. iter(1,-2) will iterate from the first element to the second to last element.

nil values can be stored in a Vector, although nil values will cause the iterators returned by this class to halt prematurely, since Lua interprets nil being returned as signaling the end of the iteration.

Note that the elements of a Vector are stored directly in the Vector object itself, so a Vector can be treated like a vanilla Lua table. For example, the following code is all valid:

> v = Vector:make(1,2,3,4,5,6); v:shuffle(); print(v)
[1, 2, 6, 4, 3, 5]
> table.sort(v); print(v)
[1, 2, 3, 4, 5, 6]
> for _,e in ipairs(v) do print(e) end                                    
1
2
3
4
5
6
> -- raw indexing - no range checking or negative index translation
> print(v[1], v[-1])
1       nil

Summary

makeCreates and returns a new Vector containing the elements passed as varargs to this method.
newCreates a new Vector from array or returns an empty Vector if array is nil.
getReturns the element at the 1-based position index in the Vector.
__eqReturns true if self and other are the same size and both contain the same elements in the same order.
addInserts value AFTER position index, or appends it onto the end of the Vector if index is not specified.
asStringConcatenates all elements of the Vector into a string and returns it.
getReturns the element at the 1-based position index in the Vector.
iterReturns an iterator over the range [start..stop] (inclusive on both ends) with the step size defaulting to +1.
removeRemoves and returns the element at index or the last element of the Vector if no index is specified.
setSets the element at the 1-based position index equal to value and returns the previous value stored there.
sizeReturns the number of elements in this Vector.
testUnit test.
unpackReturns all of the elements of this Vector.
toStringReturns a string representation of sequence.
addAllCalls collection:add(e) for each e in iter(iterable).
containsReturns true if element exists in collection.
containsAllReturns true iff collection:contains(e) for e in iter(iterable).
containsAnyReturns true if for collection:contains(e) for some e in iter(iterable).
enumDecorates another iteration to return the index of each element returned from the decorated iteration.
firstReturns the first element of the sequence, or nil if the sequence is empty.
lastReturns the last element of the sequence, or nil if the sequence is emtpty.
removeAllCalls sequence:removeElement(e) for e in iter(elements).
removeElementRemoves the first instance of element from sequence and returns it, or if not found, nil.
shufflePermutes the input sequence in place, using the optionally supplied rng (by default math.random).
sortSorts the sequence in place using the built-in table.sort function and the ordering specified (default is increasing order).
swapExchanges the elements stored in sequence at the two supplied indices.

Detail

Vector:make(...)

Creates and returns a new Vector containing the elements passed as varargs to this method.

If only one argument is specified, it is assumed to be iterable and the elements of the iteration are added to a newly constructed Vector. Otherwise, if there is more than one argument, each argument is added to a newly constructed Vector.

Thus, Vector:make(1,2,3) == Vector:make{1,2,3}.

Vector:new(array)

Creates a new Vector from array or returns an empty Vector if array is nil.

Vector:get(index)

Returns the element at the 1-based position index in the Vector.

Indices may be negative, with -1 retrieving the last element, -2 the second-to-last element, and -size() retrieving the first element. param index: in +/-[1..size()] error: if index not in valid range

Vector:__eq(other)

Returns true if self and other are the same size and both contain the same elements in the same order.

Vector:add(value, [index])

Inserts value AFTER position index, or appends it onto the end of the Vector if index is not specified.

param index: in +/-[0..size()]

Example:

> v = Vector:make(1,2,3,4)
> v:add(-1, 0); v:add(5, -1); print(v)
[-1, 1, 2, 3, 4, 5]
> v:add(2.5, 3); print(v)
[-1, 1, 2, 2.5, 3, 4, 5]

Vector:asString(separator)

Concatenates all elements of the Vector into a string and returns it.

Vectors can thus be used as string buffers. This method just wraps table.concat().

Vector:get(index)

Returns the element at the 1-based position index in the Vector.

Indices may be negative, with -1 retrieving the last element, -2 the second-to-last element, and -size() retrieving the first element. param index: in +/-[1..size()] error: if index not in valid range

Vector:iter([start, [stop, [step] ])

Returns an iterator over the range [start..stop] (inclusive on both ends) with the step size defaulting to +1.

This method uses iter.count(start, stop, step) to count off the indices being iterated over. Thus:

Examples:
> v = Vector:make(1,2,3,4,5)
> print( Vector:make(v:iter()) )
[1, 2, 3, 4, 5]
> print( Vector:make(v:iter(-1,1,-1)) )
[5, 4, 3, 2, 1]
> print( Vector:make(v:iter(2,4) )
[2, 3, 4]
> print( Vector:make(v:iter(-1, 2, -2) )
[5, 3]
> print( Vector:make(v:iter(4, 3)) ) -- empty ranges are allowed
[]

Vector:remove([index])

Removes and returns the element at index or the last element of the Vector if no index is specified.

Vector:set(index, value)

Sets the element at the 1-based position index equal to value and returns the previous value stored there. Indices may be negative, with -1 setting the last element, -2 the second-to-last element, and -size() the first element. param index: in +/-[1..size()]

Example:

> v = Vector:make(1,2,3,4)
> print(v:set(2, "hello world!"))
2
> print(v)
[1, hello world!, 3, 4]

Vector:size()

Returns the number of elements in this Vector.

This is also the largest valid index for calls to get, set.

Vector:test()

Unit test.

Vector:unpack()

Returns all of the elements of this Vector.

This method just wraps the built-in function unpack.

sequences.toString(sequence)

Returns a string representation of sequence.

This method is used for the __tostring metamethod of Vector, SkipVector, QueueVector, and LinkedList. Example:

> print(SkipVector:make(1,2,3,4,5))
[1, 2, 3, 4, 5]

collections.addAll(collection, iterable)

Calls collection:add(e) for each e in iter(iterable).

collections.contains(collection, element)

Returns true if element exists in collection.

This involves iterating through the entire collection and takes expected linear time.

collections.containsAll(collection, elements)

Returns true iff collection:contains(e) for e in iter(iterable).

collections.containsAny(collection, iterable)

Returns true if for collection:contains(e) for some e in iter(iterable).

iter.enum(iterable [, size, stop, step])

Decorates another iteration to return the index of each element returned from the decorated iteration.

If iterable is an object with a size() method, or if size is explicitly specified, the iteration will halt after iterable:size() steps. Otherwise, the iteration halts as soon as iter(iterable) halts (this may be undesireable if the iteration is expected to contain nil values)

If 2 args are given the indices will range from 1 to arg[2]. If 3 args are given the second and third arguments are interpreted as a counting range for the enumeration; If a 4th argument is specified, args 2 and 3 specify the counting range, and arg 4 specifies the step increment.

Examples:

> for ind,v in vector("abcd"):enum() do print(ind,v) end
1       a
2       b
3       c
4       d
> vec = vector("abc"); vec:add(nil)
> for ind,v in vec:enum() do print(ind, v) end
1       a
2       b
3       c
4       nil

sequences.first(sequence)

Returns the first element of the sequence, or nil if the sequence is empty.

sequences.last(sequence)

Returns the last element of the sequence, or nil if the sequence is emtpty.

sequences.removeAll(sequence, elements)

Calls sequence:removeElement(e) for e in iter(elements).

sequences.removeElement(sequence, element)

Removes the first instance of element from sequence and returns it, or if not found, nil.

sequences.shuffle(sequence [,rng])

Permutes the input sequence in place, using the optionally supplied rng (by default math.random).

rng can be any function which can takes two integer arguments a,b and returns a random integer in the range [a..b] (inclusive on both sides).

The algorithm runs in linear time and generates all permutations with equal probability, assuming the rng is perfectly uniform. It is implemented using an algorithm proposed by Knuth, see http://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms

Sequence:sort([orderFn])

Sorts the sequence in place using the built-in table.sort function and the ordering specified (default is increasing order).

If seq is a Vector or Tuple, no auxilliary table is created for the sort. If seq is any other collection, a copy of seq is created, sorted, and the results copied back to seq.

sequences.swap(sequence, index1, index2)

Exchanges the elements stored in sequence at the two supplied indices.