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]
new | Creates a new, empty QueueVector. |
make | Creates and returns a new instance of self containing the elements passed in as vararg params. |
get | Returns the ind'th element of this queue. |
__eq | Returns true if both QueueVector objects are the same size and contain the same elements in the same order. |
add | Adds the value, val, AFTER position ind in this QueueVector. |
get | Returns the ind'th element of this queue. |
iter | Returns an iterator over the elements in the index range [start..stop]. |
remove | Removes and returns the element at index ind (default 1) from this vector. |
set | Sets the value at index ind equal to val and returns the previous value. |
size | Returns the number of elements in this queue. |
test | Unit test. |
toString | Returns a string representation of sequence. |
addAll | Calls collection:add(e) for each e in iter(iterable). |
contains | Returns true if element exists in collection. |
containsAll | Returns true iff collection:contains(e) for e in iter(iterable). |
containsAny | Returns true if for collection:contains(e) for some e in iter(iterable). |
enum | Decorates another iteration to return the index of each element returned from the decorated iteration. |
first | Returns the first element of the sequence, or nil if the sequence is empty. |
last | Returns the last element of the sequence, or nil if the sequence is emtpty. |
removeAll | Calls sequence:removeElement(e) for e in iter(elements). |
removeElement | Removes the first instance of element from sequence and returns it, or if not found, nil. |
shuffle | Permutes the input sequence in place, using the optionally supplied rng (by default math.random). |
sort | Sorts the sequence in place using the built-in table.sort function and the ordering specified (default is increasing order). |
swap | Exchanges the elements stored in sequence at the two supplied indices. |
QueueVector:new(obj)
collections.make(self, ...)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)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)
QueueVector:add(val,ind)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)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)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)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)param ind: in +/-[1..size] returns: the previous value stored at index ind
QueueVector:size()This is also the largest valid index for a call to get().
QueueVector:test()
sequences.toString(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)
collections.contains(collection, element)This involves iterating through the entire collection and takes expected linear time.
collections.containsAll(collection, elements)
collections.containsAny(collection, iterable)
iter.enum(iterable [, size, stop, step])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)
sequences.last(sequence)
sequences.removeAll(sequence, elements)
sequences.removeElement(sequence, element)
sequences.shuffle(sequence [,rng])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])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)