// 跳表 https://blog.csdn.net/rxbook/article/details/130915996
package main

import (
	"fmt"
	"math/rand"
)

const (
	MAX_LEVEL = 3 //最高层数
)

// 跳表节点结构体
type skipListNode struct {
	v        interface{}     //跳表保存的值
	score    int             //用于排序的分数
	level    int             //层高
	forwards []*skipListNode //每层前进指针,递归
}

// 新建跳表节点
func newSkipListNode(v interface{}, score, level int) *skipListNode {
	return &skipListNode{
		v:        v,
		score:    score,
		forwards: make([]*skipListNode, level, level),
		level:    level,
	}
}

// 跳表结构体
type SkipList struct {
	head   *skipListNode //跳表头结点
	level  int           //跳表当前层高
	length int           //跳表长度
}

// 实例化跳表对象
func NewSkipList() *SkipList {
	// 初始化头结点数据
	head := newSkipListNode(0, 0, MAX_LEVEL) //&{0 0 3 [<nil> <nil> <nil>]}
	return &SkipList{head, 1, 0}
}

// 给跳表中插入元素和索引
func (sl *SkipList) Insert(v interface{}, score int) int {
	if nil == v {
		return 1
	}
	cur := sl.head                       //当前需要插入的位置,也就是头结点信息
	update := [MAX_LEVEL]*skipListNode{} //每一层需要更新的数据,组成一个数组

	i := MAX_LEVEL - 1
	for ; i >= 0; i-- {
		for nil != cur.forwards[i] {
			if cur.forwards[i].v == v {
				return 2
			}
			if cur.forwards[i].score > score {
				update[i] = cur
				break
			}
			cur = cur.forwards[i]
		}
		if nil == cur.forwards[i] {
			update[i] = cur
		}
	}

	//通过随机算法获取该节点层数
	level := 1
	for i := 1; i < MAX_LEVEL; i++ {
		if rand.Int31()%7 == 1 {
			level++
		}
	}

	//创建一个新的跳表节点
	newNode := newSkipListNode(v, score, level)

	//原有节点连接
	for i := 0; i <= level-1; i++ {
		next := update[i].forwards[i]
		update[i].forwards[i] = newNode
		newNode.forwards[i] = next
	}

	//如果当前节点的层数大于之前跳表的层数
	//更新当前跳表层数
	if level > sl.level {
		sl.level = level
	}

	//更新跳表长度
	sl.length++

	return 0
}

// 查找跳表中的元素
func (sl *SkipList) Find(v interface{}, score int) *skipListNode {
	if nil == v || sl.length == 0 {
		return nil
	}

	cur := sl.head
	for i := sl.level - 1; i >= 0; i-- {
		for nil != cur.forwards[i] {
			if cur.forwards[i].score == score && cur.forwards[i].v == v {
				return cur.forwards[i]
			} else if cur.forwards[i].score > score {
				break
			}
			cur = cur.forwards[i]
		}
	}

	return nil
}

// 删除跳表中的元素和索引
func (sl *SkipList) Delete(v interface{}, score int) int {
	if nil == v {
		return 1
	}

	//查找前驱节点
	cur := sl.head
	//记录前驱路径
	update := [MAX_LEVEL]*skipListNode{}
	for i := sl.level - 1; i >= 0; i-- {
		update[i] = sl.head
		for nil != cur.forwards[i] {
			if cur.forwards[i].score == score && cur.forwards[i].v == v {
				update[i] = cur
				break
			}
			cur = cur.forwards[i]
		}
	}

	cur = update[0].forwards[0]
	for i := cur.level - 1; i >= 0; i-- {
		if update[i] == sl.head && cur.forwards[i] == nil {
			sl.level = i
		}

		if nil == update[i].forwards[i] {
			update[i].forwards[i] = nil
		} else {
			update[i].forwards[i] = update[i].forwards[i].forwards[i]
		}
	}

	sl.length--

	return 0
}

func (sl *SkipList) String() string {
	return fmt.Sprintf("跳表层高: %v, 跳表长度: %v", sl.level, sl.length)
}

func main() {
	sl := NewSkipList()
	sl.Insert("zhangsan", 95)
	fmt.Println(sl.head.forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0])
	fmt.Println(sl)

	sl.Insert("lisi", 88)
	fmt.Println(sl.head.forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0].forwards[0])
	fmt.Println(sl)

	sl.Insert("wangwu", 100)
	fmt.Println(sl.head.forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0].forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0].forwards[0].forwards[0])
	fmt.Println(sl)

	fmt.Println(sl.Find("lisi", 88))

	sl.Delete("zhaoliu", 95)
	fmt.Println(sl.head.forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0])
	fmt.Println(sl.head.forwards[0].forwards[0].forwards[0])
	fmt.Println(sl)

}