Skip list

The skip list is a nifty tool to implement a time line, a Z-index for sprites or other tasks where a data structure with fast insert and delete operations is needed, rather than one with fast random access.

Warning, hardcore paragraph: an (indexable) skip list is an ordered, probabilistic data structure with O(log(n)) insertions, deletions and search, and O(n*log(n)) space usage. Their main advantage over binary trees is that they're very easy to implement ~= 150 LOC in Lua.

The only restriction is that, since it's an ordered data structure, its elements have to be comparable with < and <=.

Here's a Lua implementation based on this python version.

-- Redacted due to bugs! See https://pastebin.com/XFBtL9MH

The API by example:

local skiplist = require"skiplist"

math.randomseed(os.time())

-- Creation:

insdel = skiplist.new(8) -- you must pass an estimation of the length of the list to get optimal performance.

-- insertions
s = "YeeHoyeE" 
for i=1,#s do
	 insdel:insert(s:sub(i,i)) 
	print(insdel) 
end
print()

--  indexing
print(insdel[4])
print(insdel[8])
print(insdel[12]) -- out of bounds --> nil
print()

-- iterate over the list.
for k,v in insdel:ipairs() do 
	print(k,v) 
end
print()

-- remove elements
print(insdel:delete"Z") --> not found

for i=1,#s do 
	insdel:delete(s:sub(i,i)) 
	print(insdel) 
end

-- alternate insertion syntax, pop() and first()
insdel:insert("e")
insdel[0]=("g")

print( insdel:first() ) -- returns the first element.
print( insdel:pop() ) -- returns the first element and removes it from the list
print( insdel:first() )
print( insdel.size )
print( insdel:pop() )
print( insdel:pop() ) -- attempt to pop an empty list --> nil + error message.
print()

-------------------------------
-- ASCII representation of the structure:

-- Uncomment the _End assignment at the penultimate line 
-- of the previous code section for this to work.

-- This is required because the following code goes 
-- under the hood to show the inner structure of the list.
-- This isn't needed for normal use of the library.


l = skiplist.new(9)
s = "SweetLOVE"

for i=1,#s do local e = s:sub(i,i) l:insert(e) end

for level = l.maxLevel, 1, -1 do
	local line='Level '..level..": "
	node = l.head

	while node.value ~= _End do
		line=line..node.value..node.width[level].." "
		for i=1,node.width[level]-1 do line=line.."   " end
		node = node.next[level]
	end
	print(line.."NIL")
end

Output:

( Y )
( Y, e )
( Y, e, e )
( H, Y, e, e )
( H, Y, e, e, o )
( H, Y, e, e, o, y )
( H, Y, e, e, e, o, y )
( E, H, Y, e, e, e, o, y )

e
y
nil

1       E
2       H
3       Y
4       e
5       e
6       e
7       o
8       y

nil     value not found: Z
( E, H, e, e, e, o, y )
( E, H, e, e, o, y )
( E, H, e, o, y )
( E, e, o, y )
( E, e, y )
( E, e )
( E )
(  )
e
e
g
1
g       
nil     Trying to pop an empty list


Level 3: HEAD4          S6                NIL
Level 2: HEAD1 E3       S1 V2    e2    w1 NIL
Level 1: HEAD1 E1 L1 O1 S1 V1 e1 e1 t1 w1 NIL