跳表实现

手写跳表，有点丑陋，亟待优化，不过是一遍过。先纪念下

package skin_list

import (
    "fmt"
    "math"
    "math/bits"
    "math/rand"
    "time"
)
// 自己想的实现方法 可以查询和删除

const (
    MaxLevel = 4
)
var MaxRangeNum int

func init(){
    MaxRangeNum = int(math.Pow(2,MaxLevel))
    rand.Seed(time.Now().Unix()) // 全局和局部都可
}
func randomLevel() int16 {
    total := uint64(1)<<uint64(MaxLevel+1) - 1
    k := rand.Uint64() % total
    return MaxLevel+1 - int16(bits.Len64(k+1)) + 1
}
// randLevel1 1/2概率返回1 1/4概率返回2 1/8概率返回3 以此类推
func randLevel1()int  {
    var n int
    for n==0{
        n = rand.Intn(MaxRangeNum)
    }
    count := MaxLevel
    for ;n>0;n=n/2{
        count--
    }
    return count+1
}

func randLevelmock(score int)int  {
    switch score {
    case 1:
        return 3
    case 5:
        return 1
    case 11:
        return 3
    case 20:
        return 2
    case 60:
        return 1
    case 78:
        return 2
    default:
        return 0
    }
}


type SkipList1 struct {
    root *Node1
}

type Node1 struct {
    Val interface{}
    Score int
    Level []*Node1 // 每层的下一个节点
    Next *Node1
}

func (s *SkipList1)Search(score int)[]*Node1 {
    if s.root==nil{
        return nil
    }
    if score==s.root.Score{
        return GetAllEquel(s.root)
    }
    if score<s.root.Score{
        return nil
    }
    curL := s.root
    l := len(curL.Level) -1 //保证这里最长
    for ;l>=0;{
        if curL.Level[l]!=nil{
            right := curL.Level[l]
            if right==nil{
                l--
                continue
            }else {
                if score>curL.Score&&score<right.Score{
                    l--
                    continue
                }else if score==right.Score{
                    return GetAllEquel(right)
                }else{
                    curL = right
                    continue
                }
            }
        }else{
            //fmt.Println("waring:", curL.Score)
            l--
        }
    }
    // 到达链表
    for ;curL!=nil;curL=curL.Next{
        if score==curL.Score{
            return GetAllEquel(curL)
        }else if curL.Score<score{
            continue
        }else{
            break
        }
    }
    return nil
}


func (s *SkipList1)Insert(score int, val interface{})error{
    if val==nil{
        // todo 空interface特殊情况
        return nil
    }
    if s.root==nil{
        level := make([]*Node1, MaxLevel , MaxLevel) // 刚好需要全是nil
        s.root=&Node1{
            Val: val,
            Score: score,
            Level: level, // 每层的下一个节点
            Next: nil,
        }
        return nil
    }
    if score<s.root.Score{
        //todo
    }


    newLevelLen := randLevel1()-1
    //newLevelLen := randLevelmock(score)-1
    fmt.Println("newLevelLen:",newLevelLen)
    newLevel := make([]*Node1,newLevelLen,newLevelLen)
    NewNode := &Node1{
        Val: val,
        Level: newLevel,
        Score: score,
    }

    curL := s.root
    l := len(curL.Level) -1 //保证这里最长
    for ;l>=0;{
        if curL.Level[l]!=nil{
            right := curL.Level[l]
            if right==nil{
                if l<newLevelLen{
                    NewNode.Level[l] = curL.Level[l]
                    curL.Level[l] = NewNode
                }
                l--
                continue
            }else {
                if score>curL.Score&&score<right.Score{
                    if l<newLevelLen{
                        NewNode.Level[l] = curL.Level[l]
                        curL.Level[l] = NewNode
                    }
                    l--
                    continue
                }else if score==curL.Score{
                    if l<newLevelLen{
                        NewNode.Level[l] = curL.Level[l]
                        curL.Level[l] = NewNode
                    }
                    l--
                    continue
                }else if score==right.Score{
                    curL = right
                    continue
                }else{
                    curL = right
                    continue
                }
            }
        }else{
            //fmt.Println("waring:", curL.Score)
            if l<newLevelLen{
                NewNode.Level[l] = curL.Level[l]
                curL.Level[l] = NewNode
            }
            l--
        }
    }

    if curL.Next==nil{
        curL.Next = NewNode
    }else{
        for ;curL.Next!=nil&&curL.Next.Score<=score;{
            curL = curL.Next
        }
        NewNode.Next = curL.Next
        curL.Next = NewNode
    }
    return nil
}

func GetAllEquel(node *Node1)[]*Node1 { // 考虑并发
    // todo 所有相同的值
    return []*Node1{node}
}