go-skiplist example

skiplist.go

package main

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

type SkipListNode struct {
    level int
    value interface{}

    next []*SkipListNode
    prev *SkipListNode
}

const MAX_SKIPLIST_LEVEL = 4

func (o *SkipListNode) Init(level int) *SkipListNode {
    o.level = level
    o.next = make([]*SkipListNode, level)
    o.prev = nil

    for i := 0; i < level; i++ {
        o.next[i] = nil
    }

    return o
}

type SkipList struct {
    head *SkipListNode
    lessThan func(l, r interface{}) bool
}

func (o *SkipList) Init(lessThan func(l, r interface{}) bool) *SkipList {
    return &SkipList{
        head: new(SkipListNode).Init(MAX_SKIPLIST_LEVEL),
        lessThan: lessThan,
    }
}

func (o *SkipList) createNewNode(value interface{}) *SkipListNode {
    node := new(SkipListNode).Init(getRandomLevel(MAX_SKIPLIST_LEVEL))
    node.value = value
    fmt.Println(node.level)
    return node
}

func (o *SkipList) Add(v interface{}) {
    newNode := o.createNewNode(v)
    o.AddNode(newNode)
}

func (o *SkipList)IsEmpty() bool {
    ret := false
    if o.head.next[0] == nil {
        ret = true
    }

    return ret
}

func (o *SkipList)FindBackwardNode(value interface{}, backward []*SkipListNode) *SkipListNode {
    level := o.head.level
    node := o.head

    for ;level > 0;level-- {
        l := level - 1

        backward[l] = node
        for ;node.next[l] != nil; node = node.next[l] {
            if o.lessThan(node.next[l].value, value) == true{
                backward[l] = node.next[l]
            } else {
                break
            }
        }

        fmt.Println("level: ", level, " value: ", backward[l].value)
    }

    fmt.Println("node: ", node)
    return node
}

func (o *SkipListNode) addFromBackward(backward []*SkipListNode) {
    for i := 0; i < o.level; i++ {
        o.next[i] = backward[i].next[i]
        backward[i].next[i] = o
    }
}

func (o *SkipList) AddNode(newNode *SkipListNode) {
    backward := make([]*SkipListNode, MAX_SKIPLIST_LEVEL)
    for i := 0; i < MAX_SKIPLIST_LEVEL; i++ {
        backward[i] = nil
    }
    o.FindBackwardNode(newNode.value, backward)
    newNode.addFromBackward(backward)
}

func getRandomLevel(max_level int) int {
    level := 1
    for level < max_level &&
          (rand.Int() & 0xFFFF) < (16384) {
        level++
    }

    return level
}

func main() {
    rand.Seed(time.Now().UTC().UnixNano())
    fmt.Println("Hello, 世界")

    IntLessThan := func (l, r interface{}) bool {
        fmt.Println("l: ", l.(int), " r: ", r.(int), " ret: ", l.(int) < r.(int) )
        return l.(int) < r.(int)
    }

    listMgr := new(SkipList).Init(IntLessThan)
    fmt.Println("IsEmpty:", listMgr.IsEmpty())
    listMgr.Add(10)
    fmt.Println("IsEmpty:", listMgr.IsEmpty())
    listMgr.Add(20)
    fmt.Println("IsEmpty:", listMgr.IsEmpty())
    listMgr.Add(30)
    fmt.Println("IsEmpty:", listMgr.IsEmpty())
    listMgr.Add(5)
    fmt.Println("IsEmpty:", listMgr.IsEmpty())
    for l := 0; l < MAX_SKIPLIST_LEVEL; l++ {
        fmt.Println("Level: ", l)
        for pos := listMgr.head.next[l]; pos != nil; pos = pos.next[l] {
            fmt.Println(pos.value, ":", pos.level)
        }
    }
}