go 跳表实现

var table *jobScheduleTable

type jobNode struct {
    forward []*jobNode
    data    int
}

type jobScheduleTable struct {
    head  *jobNode
    level int
}

func initJobSchelduleTable() {
    table = &jobScheduleTable{
        head:  &jobNode{forward: make([]*jobNode, MaxLevel)},
        level: 1,
    }
}

func newJobNode(data int, level int) *jobNode {
    return &jobNode{forward: make([]*jobNode, level), data: data}
}

func (t *jobScheduleTable) Insert(data int) {
    level := randLevel()
    if level > t.level {
        level = t.level + 1
        t.level = level
    }
    current := t.head
    before := make([]*jobNode, level)
    after := make([]*jobNode, level)
    for i := level; i >= 1; i-- {
        if current.forward[i-1] == nil || current.forward[i-1].data > data {
            after[i-1] = current.forward[i-1]
            before[i-1] = current
        } else {
            for current.forward[i-1] != nil && current.forward[i-1].data < data {
                current = current.forward[i-1]
            }
            before[i-1] = current
            after[i-1] = current.forward[i-1]
        }
    }

    node := newJobNode(data, level)
    for i := 0; i < level; i++ {
        node.forward[i] = after[i]
        before[i].forward[i] = node
    }
}

func (t *jobScheduleTable) Search(data int) {
    current := t.head
    for i := t.level; i >= 1; i-- {
        if current.forward[i-1] == nil || current.forward[i-1].data > data {
            continue
        } else {
            for current.forward[i-1] != nil && current.forward[i-1].data < data {
                current = current.forward[i-1]
                fmt.Println(current.data)
            }
            if current.forward[i-1] != nil {
                if current.forward[i-1].data == data {
                    fmt.Println(data, i)
                    return
                }
            }

        }
    }
}


func(t *jobScheduleTable)Delete(data int){
    current := t.head
    for i:= t.level;i>=1;i-- {
        for current.forward[i-1] != nil {
            if current.forward[i-1].data == data{
                tmp := current.forward[i-1]
                current.forward[i-1] = tmp.forward[i-1]
                tmp.forward[i-1] = nil
                break
            }else if current.forward[i-1].data > data{
                break
            }else {
                current = current.forward[i-1]
            }
        }
    }
}

func(t *jobScheduleTable)Pop()int{
    d := t.head.forward[0].data
    t.Delete(d)
    return d
}

func (t *jobScheduleTable) Print() {

    for i := t.level; i >= 1; i-- {
        current := t.head
        for {
            if current.forward[i-1] == nil {
                break
            }
            fmt.Printf("%d ", current.forward[i-1].data)
            current = current.forward[i-1]
        }
        fmt.Printf("***************** Level %d \n", i)
    }
}

func randLevel() int {
    rand.Seed(time.Now().UnixNano())
    var level = 1
    for {
        if rand.Float64() > 0.25 || level >= MaxLevel {
            break
        }
        level++
    }
    return level
}