Provides worst-case logarithmic random access, constant time sequential access, and logarithmic time inserts or removals at ANY position. Also provides functions for splicing and concatenating, and joining other SkipVectors.
The basic functions are:
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 SkipVector, 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.
Implementation is based heavily on: 'A Skip List Cookbook', William Pugh, 1990.
make | Creates and returns a new instance of self containing the elements passed in as vararg params. |
get | Returns the element currently stored at position index in this SkipVector, defaulting to the last element. |
__eq | Returns true if both vectors are of the same size and contain the same elements in the same order. |
add | Adds val to the end of this vector, or, if index is specified, inserts val AFTER index. |
splice | Removes the range [start,stop] from this vector and returns it as a SkipVector. |
get | Returns the element currently stored at position index in this SkipVector, defaulting to the last element. |
iter | Returns an iterator over the elements at indices [start..finish] in this vector. |
join | Splices vec2 into this list AFTER position index. |
remove | Removes the element at the supplied index, or, the range [index..stopIndex] and returns the result as a SkipVector. |
replace | Replaces the range [start,stop] with the elements in iterable. |
reverseIter | Returns a reverse iterator over the elements in this vector, starting from start (inclusive) and moving backward to finish (inclusive). |
set | Sets the element at index to val and returns the previous element stored. |
size | Returns the number of elements in this vector. |
test | Unit test. |
toString | Returns a string representation of sequence. |
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. |
SkipVector:new()
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.
SkipVector:get([index])Indices start at 1 and 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.
param index: in +/-[1,size()]
example:
[a,b,c]:get(-1) == c, [a,b,c]:get(1) == a time complexity: O(lg(k)), where k is the distance from the most recent get/set
SkipVector:__eq(other)
SkipVector:add(val [,index])Negative indices can be used.
param index: in +/-[0,size()] (0 inserts before the first element)
time complexity: O(lg(size())
example:
[1,2,3]:add(a, 1) results in [1,a,2,3]
SkipVector:splice(start [,stop])If omitted, the stop parameter defaults to the end of the vector. The call splice(s1,s2) is equivalent to the call remove(s1,s2). Negative indices can also be used.
param start,stop: in +/-[1,size()]
time complexity: O(lg(size()))
example:
['a','b','c',1,2,3]:splice(2,4) returns ['b','c',1], and the original list becomes ['a',2,3]
SkipVector:get([index])Indices start at 1 and 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.
param index: in +/-[1,size()]
example:
[a,b,c]:get(-1) == c, [a,b,c]:get(1) == a time complexity: O(lg(k)), where k is the distance from the most recent get/set
SkipVector:iter([start [,finish] ])If no finish is specified, the iteration is from start (inclusive) to the end of the vector; if no start is specified, the iteration is over all elements in this vector. Negative indices can be used when specifying the range. If start > finish, a reverse iteration over the range [finish,start],-1 is returned.
param start,finish: in +/-[1,size()]
time complexity: advancing to the next element in the iteration is a constant-time operation.
Examples:
for i in [1,2,3,4,5]:iter(3) do print(i) end --> 3,4,5 for i in [1,2,3,4,5]:iter(1,-2) do print(i) end --> 1,2,3,4
SkipVector:join(vec2 [, index])vec2 is destroyed as a result of this call. If the index parameter is omitted, vec2 is concatenated onto the end of this vector.
time complexity: O(lg(size())).
param: index in +/-[0,size()] the index after which to insert vec2
examples:
[1,2,3]:join([a,b,c],2) results in [1,2,a,b,c,3] [1,2,3,4,5]:join([a,b,c],-2) results in [1,2,3,4,a,b,c,5]
SkipVector:remove(index [,stopIndex])param index, stopIndex: in +/-[1,size()]
time complexity: 0(lg(size())), for either operation.
examples:
[1,2,3]:remove(-2) results in [1,3] [1,2,3,4]:remove(2,3) results in [1,4] [1,2,3,4]:remove()==4 and results in [1,2,3]
SkipVector:replace(start,stop,iterable)If the range being replaced has the close to the same number of elements as the iteration, this function runs in roughly linear time. Otherwise, the time complexity can be no worse than O(k*lg(size)), where k is the number of elements in iterable.
param start,stop: in +/-[1,size()]
time complexity: min(k,r) + abs(k-r)*lg(size), where k is the number of elements in iterable and r is the number of elements in the range (start, stop)
example:
[a,b,c,d,e]:replace(2,5,{1,2}) results in [a,1,2]
SkipVector:reverseIter(start, finish)param start: in +/-[1,size()], defaults to size()
SkipVector:set(index, val)param index: in +/-[1,size()]
time complexity: O(lg(k)), where k is the distance from the most recent get/set
example:
[1,2,3,4]:set(2,"a") results in [1,"a",3,4] and returns 2
SkipVector:size()This is also the largest valid index for a call to get().
SkipVector: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.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)