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.

The MIT License

Original Python version Copyright (c) 2009 Raymond Hettinger 
see http://code.activestate.com/recipes/576930/

Lua conversion + extensions Copyright (c) 2010 Pierre-Yves Gérardy

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.


do 
local log, floor, ceil, min, random 
= math.log, math.floor, math.ceil, math.min, math.random

local makeNode = function(value,size)
	return {
		value=value, 
		next={}, 
		width={}, 
		size=size
	}
end
local End ={}
local NIL = makeNode(End,0)

local insert = function(self,value)
	local node, chain, stepsAtLevel = self.head, {}, {}
	for i=1, self.maxLevel do stepsAtLevel[i]=0 end
	for level = self.maxLevel, 1, -1 do
		while node.next[level] ~= NIL and node.next[level].value <= value do
			stepsAtLevel[level] = ( stepsAtLevel[level] or 0 ) + node.width[level]
			node = node.next[level]
			--print(level, stepsAtLevel[level],value)
		end
		chain[level]=node
	end

	local nodeLevel = min( self.maxLevel, - floor(log(random()) / log(2) ) )
	local newNode = makeNode( value,  nodeLevel)
	local steps, prevNode = 0
	for level= 1, nodeLevel do
		prevNode = chain[level]
		newNode.next[level] = prevNode.next[level]
		prevNode.next[level] = newNode
		newNode.width[level] = prevNode.width[level] - steps
		prevNode.width[level] = steps + 1
		steps = steps + stepsAtLevel[level]
	end
	for level = nodeLevel + 1, self.maxLevel do
		chain[level].width[level] = chain[level].width[level] +1
	end
	self.size = self.size + 1
end

local delete = function(self,value)
	-- find first node on each level where node.next[levels].value >= value

	node, chain = self.head, {}
	for level = self.maxLevel, 1, -1 do
		while node.next[level] ~= NIL and node.next[level].value < value do
			node = node.next[level]
		end
		chain[level] = node
	end
	if value ~= chain[1].next[1].value then
		return nil, "value not found: "..value
	end

	-- remove one link at each level
	nodeLevel = chain[1].next[1].size
	for level = 1, nodeLevel do
		prevnode = chain[level]
		prevnode.width[level] = prevnode.width[level] + prevnode.next[level].width[level] - 1
		prevnode.next[level] = prevnode.next[level].next[level]
	end
	for level = nodeLevel+1, self.maxLevel do
		chain[level].width[level] = chain[level].width[level] - 1
	end
	self.size = self.size - 1
	return true --success
end


local first = function(self)
	return self.head.next[1].value
end

local pop=function (self)
	if self.size == 0 then return nil, "Trying to pop an empty list" end
	
	local node, head = self.head.next[1], self.head
	for level = 1, node.size do
		head.next[level]=node.next[level]
		head.width[level]=node.width[level]
	end
	for level = node.size + 1, self.maxLevel do
		head.width[level] = head.width[level] -1
	end
	self.size = self.size - 1
	return node.value
end

-- get the value of the node at index i ( O( log( n ) ) )

local islMT = {
	__index = function(self,i)
		if i > self.size then return end
		local node = self.head
		for level=self.maxLevel, 1, -1 do
			-- print(node.width[level],i)
			while node.width[level] <= i do
				i = i - node.width[level]
				node = node.next[level]
			end
		end
	return node.value
	end,
	__newindex = function(self,k,v) 
		if k==0 then self:insert(v)
		else error("use SkipList[0]=el or SkipList:insert(el)")
		end
	end,
	}

local tostring = function (self)
	local t = {}
	for k,v in self:iter() do table.insert(t,v) end
	return "( "..table.concat(t,", ").. " )"
end

local iter = function (self)
	local node, size = self.head.next[1] , self.size
	count = 0
	return function()
		value=node.value
		node = node.next[1]
		count = count+1
		return count <= size and count or nil, value 
	end
end

function makeSkipList(expected_size)
	local maxLevel = floor( log(expected_size) / log(2) ) 
	local head = makeNode("HEAD",maxLevel)
	for i=1,maxLevel do 
		head.next[i] = NIL
		head.width[i] = 1
	end
	
	return setmetatable( {
		size = 0,
		head = head,
		maxLevel = maxLevel,
		insert = insert,
		delete = delete,
		first = first,
		tostring = tostring,
		iter=iter,
		pop = pop
		}, islMT )
end

-- _End = End
end

The API by example:

math.randomseed(os.time())

-- Creation:

insdel = makeSkipList(8) -- you must pass an estimation of the length of the list for better performance.

-- insertions
s = "YeeHoyeE" 
for i=1,#s do
	 insdel:insert(s:sub(i,i)) 
	print(insdel:tostring()) 
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:iter() 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:tostring()) 
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 = makeSkipList(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