SkipVector

Overview

Skip-list implementation of a general purpose vector.

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:

add, remove, get, set, splice, and join all have worst case O(lg(size)) performance. However, the vector maintains search 'fingers' into the structure, so that the time complexity for get and set operations is O(lg(k)), where k is the distance from the most recently accessed element. E.g., for the access pattern 1,2,3..n, get/set will both run in O(1).

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.

Summary

makeCreates and returns a new instance of self containing the elements passed in as vararg params.
getReturns the element currently stored at position index in this SkipVector, defaulting to the last element.
__eqReturns true if both vectors are of the same size and contain the same elements in the same order.
addAdds val to the end of this vector, or, if index is specified, inserts val AFTER index.
spliceRemoves the range [start,stop] from this vector and returns it as a SkipVector.
getReturns the element currently stored at position index in this SkipVector, defaulting to the last element.
iterReturns an iterator over the elements at indices [start..finish] in this vector.
joinSplices vec2 into this list AFTER position index.
removeRemoves the element at the supplied index, or, the range [index..stopIndex] and returns the result as a SkipVector.
replaceReplaces the range [start,stop] with the elements in iterable.
reverseIterReturns a reverse iterator over the elements in this vector, starting from start (inclusive) and moving backward to finish (inclusive).
setSets the element at index to val and returns the previous element stored.
sizeReturns the number of elements in this vector.
testUnit test.
toStringReturns a string representation of sequence.
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

SkipVector:new()

Creates and returns a new, empty SkipVector

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.

SkipVector:get([index])

Returns the element currently stored at position index in this SkipVector, defaulting to the last element.

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)

Returns true if both vectors are of the same size and contain the same elements in the same order.

SkipVector:add(val [,index])

Adds val to the end of this vector, or, if index is specified, inserts val AFTER 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])

Removes the range [start,stop] from this vector and returns it as a SkipVector.

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])

Returns the element currently stored at position index in this SkipVector, defaulting to the last element.

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] ])

Returns an iterator over the elements at indices [start..finish] in this vector.

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])

Splices vec2 into this list AFTER position 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])

Removes the element at the supplied index, or, the range [index..stopIndex] and returns the result as a SkipVector. If no parameters are specified, the last element is removed and returned. Negative indices can also be used.

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)

Replaces the range [start,stop] with the elements in 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)

Returns a reverse iterator over the elements in this vector, starting from start (inclusive) and moving backward to finish (inclusive). param finish: in +/-[1,size()], defaults to 1

param start: in +/-[1,size()], defaults to size()

SkipVector:set(index, val)

Sets the element at index to val and returns the previous element stored.

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()

Returns the number of elements in this vector.

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

SkipVector: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.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.