package zset

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

const (
	ZSKIPLIST_MAXLEVEL = 64
	ZSKIPLIST_P        = 0xFFFF >> 2
)

/* type zset struct {
	dict      map[string]*zskiplistNode
	zskiplist *zskiplist
} */
type zskiplistNode struct {
	score    int64            //分值参与排序
	ele      string           //memeber
	level    []zskiplistLevel //索引数组
	backward *zskiplistNode   //上一个node
}
type zskiplistLevel struct {
	forward *zskiplistNode //下一个node
	span    uint           //这个指针到下一个节点的个数，不包括本身
}
type zskiplist struct {
	header *zskiplistNode
	tail   *zskiplistNode
	length int64
	level  int
}

func (z *zskiplist) ZslInsert(score int64, ele string) {
	x := z.header
	rank := [ZSKIPLIST_MAXLEVEL]int{}              //等级
	update := [ZSKIPLIST_MAXLEVEL]*zskiplistNode{} //需要更新的node
	for i := z.level - 1; i > -1; i-- {
		if rank[i] == z.level-1 {
			rank[i] = 0
		} else {
			rank[i] = rank[i+1]
		}
		//正序排列，查找插入位置，更新到数组
		for x.level[i].forward != nil && (score > x.level[i].forward.score || (x.level[i].forward.score == score && ele > x.level[i].forward.ele)) {
			rank[i] += int(x.level[i].span) //当前节点的span
			x = x.level[i].forward
		}
		update[i] = x
	}
	//获取插入层数
	level := z.zslRandomLevel()
	if level > z.level {
		for i := z.level; i < level; i++ {
			rank[i] = 0
			update[i] = z.header
			update[i].level[i].span = uint(z.length)
		}
		z.level = level
	}

	zslNode := zslCreateNode(score, ele, level)
	for i := 0; i < level; i++ {
		zslNode.level[i].forward = update[i].level[i].forward
		update[i].level[i].forward = zslNode
		zslNode.level[i].span = update[i].level[i].span - uint(rank[0]-rank[i])
		update[i].level[i].span = uint(rank[0]-rank[i]) + 1
	}
	//更新大于插入层的span
	for i := level; i < z.level; i++ {
		update[i].level[i].span++
	}
	if update[0] != z.header {
		zslNode.backward = update[0]
	}
	//更新tail节点、根链表backward节点
	if zslNode.level[0].forward != nil {
		zslNode.level[0].forward.backward = zslNode
	} else {
		z.tail = zslNode
	}
	z.length++
}

func (z *zskiplist) ZslRangeByScore(min, max int64) (memeberList []string) {
	if min > max || z.length == 0 || z.tail.score < min || z.header.level[0].forward.score > max {
		return
	}
	x := z.header

	for i := z.level - 1; i > -1; i-- {
		for x.level[i].forward != nil && x.level[i].forward.score <= min {
			x = x.level[i].forward
		}
	}
	//查找上一个节点是否相等
	for x != nil && x.backward.score >= min {
		x = x.backward
	}
	if x.score < min {
		x = x.level[0].forward
	}
	for x != nil {
		memeberList = append(memeberList, x.ele)
		x = x.level[0].forward
	}
	return
}

func (z *zskiplist) zslRandomLevel() int {
	level := 1
	rander := rand.New(rand.NewSource(time.Now().UnixNano()))
	for rander.Intn(0xFFFF)&0xFFFF < ZSKIPLIST_P {
		level++
	}
	if level > ZSKIPLIST_MAXLEVEL {
		level = ZSKIPLIST_MAXLEVEL
	}
	return level
}
func (z *zskiplist) Print() {
	printStack := make([]string, 0, z.level)
	eleMap := make(map[string]int)
	for i := 0; i < z.level; i++ {
		node := z.header.level[i].forward
		str := fmt.Sprintf("BEGIN[%s,%d],%d ", "header", z.header.score, z.header.level[i].span)
		ext := "-> END"
		for node != nil {
			if node.level[i].forward == nil {
				if i == 0 {
					eleMap[node.ele] = len(str)
					str += fmt.Sprintf("-> [%s,%d],%d ", node.ele, node.score, node.level[i].span)
					eleMap["END"] = len(str)
					str += ext
				} else {
					index := len(str)
					for index < eleMap[node.ele] {
						str += "-"
						index++
					}
					str += fmt.Sprintf("-> [%s,%d],%d ", node.ele, node.score, node.level[i].span)
					index = len(str)
					for index < eleMap["END"] {
						str += "-"
						index++
					}
					str += ext
				}
			} else {
				if i == 0 {
					eleMap[node.ele] = len(str)
				} else {
					index := len(str)
					for index < eleMap[node.ele] {
						str += "-"
						index++
					}
				}
				str += fmt.Sprintf("-> [%s,%d],%d ", node.ele, node.score, node.level[i].span)
			}
			node = node.level[i].forward
		}
		printStack = append(printStack, str)
	}
	for i := z.level - 1; i > -1; i-- {
		fmt.Println(printStack[i])
	}
	fmt.Println()
}
func ZslCreate() *zskiplist {
	zsl := &zskiplist{
		header: zslCreateNode(0, "", ZSKIPLIST_MAXLEVEL),
		tail:   nil,
		length: 0,
		level:  1,
	}
	for i := 0; i < ZSKIPLIST_MAXLEVEL; i++ {
		zsl.header.level[i] = zskiplistLevel{}
	}
	return zsl
}
func zslCreateNode(score int64, ele string, level int) *zskiplistNode {
	if level < 0 {
		level = 1
	}
	return &zskiplistNode{
		score: score,
		ele:   ele,
		level: make([]zskiplistLevel, level),
	}
}