skiplist.go

package skip_list

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	Max = 32

	p = 0.25
)

type node struct {
	forward []*node
	value   interface{}
}

func newNode(value interface{}, level int) *node {
	return &node{
		value:   value,
		forward: make([]*node, level),
	}
}

type SkipList struct {
	level   int
	head    *node
	compare func(a, b interface{}) int
}

func NewList(compare func(a, b interface{}) int) *SkipList {
	return &SkipList{
		level:   1,
		head:    newNode(nil, Max),
		compare: compare,
	}
}

func (list *SkipList) randLevel() (level int) {
	rand.Seed(time.Now().UnixNano())
	for level = 1; rand.Float32() < p && level < Max; level++ {
	}
	return
}

func (list *SkipList) Insert(value interface{}) {
	current := list.head
	update := make([]*node, Max)
	for i := list.level - 1; i >= 0; i-- {
		if current.forward[i] == nil || list.compare(current.forward[i].value, value) > 0 {
			update[i] = current
			continue
		}
		for current.forward[i] != nil && list.compare(current.forward[i].value, value) < 0 {
			current = current.forward[i]
		}
		update[i] = current
	}
	level := list.randLevel()
	if level > list.level {
		for i := list.level; i < level; i++ {
			update[i] = list.head
		}
		list.level = level
	}
	node := newNode(value, level)
	for i := 0; i < level; i++ {
		node.forward[i] = update[i].forward[i]
		update[i].forward[i] = node
	}
}

func (list *SkipList) Delete(value interface{}) {
	current := list.head
	for i := list.level - 1; i >= 0; i-- {
		for current.forward[i] != nil {
			if list.compare(current.forward[i].value, value) == 0 {
				temp := current.forward[i]
				current.forward[i] = temp.forward[i]
				temp.forward[i] = nil
			} else if list.compare(current.forward[i].value, value) > 0 {
				break
			} else {
				current = current.forward[i]
			}
		}
	}
}

func (list *SkipList) String() (str string) {
	for i := list.level - 1; i >= 0; i-- {
		current := list.head
		str += fmt.Sprintf("L %d :\t", i+1)
		for current.forward[i] != nil {
			current = current.forward[i]
			str += fmt.Sprint(current.value, "  ")
		}
		str += "\n"
	}
	return
}