# 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.

    -- file: skiplist.lua

    --[[------------------------------------------------------------------
    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.
    --]]------------------------------------------------------------------

    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 tostring = function (self)
    	local t = {}
    	for k,v in self:ipairs() do table.insert(t,v) end
    	return "( "..table.concat(t,", ").. " )"
    end

    local islMT = {
    	__index = function(self,i)
    		if type(i) ~= "number" then return end
    		if i > self.size then return end
    		local node = self.head

    		for level=self.maxLevel, 1, -1 do
    			while node.width[level] <= i do
    				i = i - node.width[level]
    				node = node.next[level]
    			end
    		end
    		return node.value
    	end,
    	__tostring=tostring
    }

    local ipairs = 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

    local function new (expected_size)
    	local size = expected_size or 16
    	if not expected_size then
    		expected_size = 16
    	end

    	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,
    		ipairs=ipairs,
    		pop = pop
    		}, islMT
    	)
    end

    return {
    	new=new
    }

## 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

Category:

- Snippets