QueueVector

Overview

Table-based vector implementation with efficient (amortized O(1)) inserts and removals at both the start and end of the vector.

Indicies of a QueueVector, q run from 1 to q:size() and can be negative, where q:get(-1) retrieves the last element, q:get(-2) the second to last element, and q:get(-q:size()) and q:get(1) both retrieve the first element.

Elements can be nil, with the caveat that the iter method will halt prematurely at these elements if the iterator is not wrapped in an enumeration.

Example uses:

> q = QueueVector:make(1,2,3,4,5)
> print(q)
[1, 2, 3, 4, 5]
> print(q:remove()) -- O(1), remove removes first element by default
1
> q:add("hello", 0) -- O(1), adds "hello" after index 0 (prepends it)
> print(q)
[hello, 2, 3, 4, 5]
> q:add("goodbye"); print(q)
[hello, 2, 3, 4, 5, goodbye]

Summary

newCreates a new, empty QueueVector.
makeCreates and returns a new instance of self containing the elements passed in as vararg params.
getReturns the ind'th element of this queue.
__eqReturns true if both QueueVector objects are the same size and contain the same elements in the same order.
addAdds the value, val, AFTER position ind in this QueueVector.
getReturns the ind'th element of this queue.
iterReturns an iterator over the elements in the index range [start..stop].
removeRemoves and returns the element at index ind (default 1) from this vector.
setSets the value at index ind equal to val and returns the previous value.
sizeReturns the number of elements in this queue.
testUnit test.
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

QueueVector:new(obj)

Creates a new, empty QueueVector.

collections.make(self, ...)

Creates and returns a new instance of self containing the elements passed in as vararg params.

If #args is 1, the argument is assumed to be iterable and its elements are added to the Collection.

Example, assuming Collection is a sequence type:

> print( Collection:make(1,2,3,4) )
[1, 2, 3, 4]
> print( Collection:make(iter.count(4) )
[1, 2, 3, 4]
> v = Collection:make(1,2,3,4); print( Collection:make(v) )
[1, 2, 3, 4]

This method is used as the make method for LinkedList, SkipVector, HashSet, SkipSet, QueueVector, and PairingHeap. It assumes that self has new() and addAll() methods.

QueueVector:get(ind)

Returns the ind'th element of this queue.

Indicies are in +/-[1..size]. Negative indices count backward from the end of the queue: the -1'th element is the last element, the -2'th element is the second to last element, and the -size'th is the first element.

param ind: in +/-[1..size] default=1

error: if ind not in valid range

synonym: __call

QueueVector:__eq(other)

Returns true if both QueueVector objects are the same size and contain the same elements in the same order.

QueueVector:add(val,ind)

Adds the value, val, AFTER position ind in this QueueVector.

ind defaults to the end of the vector. 0 inserts at the head of the vector. Values can be nil, with the caveat that the iter method will halt prematurely at these values if not wrapped in an enumeration.

param ind: in +/-[0..size] error: if ind not in valid range returns: true (fulfills general contract of collections.add)

QueueVector:get(ind)

Returns the ind'th element of this queue.

Indicies are in +/-[1..size]. Negative indices count backward from the end of the queue: the -1'th element is the last element, the -2'th element is the second to last element, and the -size'th is the first element.

param ind: in +/-[1..size] default=1

error: if ind not in valid range

synonym: __call

QueueVector:iter(start, stop)

Returns an iterator over the elements in the index range [start..stop].

Example uses:

> q = QueueVector:make(1,2,3)
> for e in q:iter() do print(e) end
1
2
3
> q:set(2,nil)
> for ind,e in iter.enum(q:iter(),q:size()) do print(ind,e) end
11
1nil
22
> q:addAll{"a","b","c"}; q:set(2,2); print(q)
[1, 2, 3, a, b, c]
> q2 = QueueVector:make(q:iter(2,4)); print(q2)
[2, 3, a]

QueueVector:remove(ind)

Removes and returns the element at index ind (default 1) from this vector.

If ind is 1 or the size of the vector, this runs in constant time; otherwise the elements to the left of the removed element are shifted over to fill the hole created.

param ind: in +/-[1..size], default=1 error: if ind not in valid range returns: the removed element

QueueVector:set(ind, val)

Sets the value at index ind equal to val and returns the previous value.

param ind: in +/-[1..size] returns: the previous value stored at index ind

QueueVector:size()

Returns the number of elements in this queue.

This is also the largest valid index for a call to get().

QueueVector:test()

Unit test.

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.