跳跃表Golang版本

跳跃表

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

type Node struct {
	key                   int
	value                 interface{}
	up, down, left, right *Node
	level                 int
}

func newNode(k int, v interface{}) *Node {
	return &Node{
		key:   k,
		value: v,
	}
}

func (n *Node) equals(node *Node) bool {
	if node == nil {
		return false
	}
	if n.key != node.key {

		return false
	}
	if n.value != node.value {

		return false
	}
	if n.level != node.level {
		return false
	}
	return true
}

// 实现跳跃表
type jumpTable struct {
	header *Node
	r      *rand.Rand
}

func New() *jumpTable {
	return &jumpTable{
		r:      rand.New(rand.NewSource(time.Now().UnixNano())),
		header: newNode(-int(^uint(0)>>1), nil),
	}
}

func println(input string) {
	return fmt.Println(input)
}

func (jt *jumpTable) Search(k int) *Node {
	println("walkPreviousNode")
	node, count := walkPreviousNode(jt.header, k)
	println("共需要", count, "步")
	return node
}

func (jt *jumpTable) Insert(k int, v interface{}) {
	sn := jt.header
	newN := newNode(k, v)
	node, _ := walkPreviousNode(sn, k)
	if node.key == k {

		node.value = v
		return
	}
	currentLevel := 0
	newN.level = currentLevel
	jt.setNode(newN, node)
	lowNode := newN
	for jt.isPromotion() {
		println("isPromotion")
		currentLevel++
		upNewN := setUpNewDownNode(currentLevel, k, newN)
		if jt.header.level < currentLevel {
			updateHeader(jt, upNewN)
		}
		leftUpNode := findLeftUpNode(lowNode, upNewN)
		if leftUpNode != nil {
			jt.setNode(upNewN, leftUpNode)
		}
		newN = upNewN
	}
}

func updateHeader(jt *jumpTable, upNew *Node) {
	jt.header = upNew
}

func setUpNewDownNode(level int, k int, v interface{}, newN *Node) *Node {
	upNew := newNode(k, v)
	upNew.level = level
	newN.up = upNew
	upNew.down = newN
	return upNew
}

func findLeftUpNode(newN *Node, upNew *Node) *Node {
	var leftUpNode *Node
	leftNewNode := newN.left
leftBreak:
	for leftNewNode != nil {
		leftNewUpNode := leftNewNode.up
		for leftNewUpNode != nil {
			if leftNewUpNode.level == upNew.level {

				leftUpNode = leftNewUpNode
				break leftBreak
			}
			leftNewNode = leftNewNode.left
		}
	}
	return leftUpNode
}

func (jt *jumpTable) setNode(q *Node, p *Node) {
	q.left = p
	if p.right != nil {
		q.right = p.right
		p.right.left = q
	}
	p.right = q
}

func walkPreviousNode(curNode *Node, k int) (*Node, int) {
	println("k:", k, " level", curNode.level)
	count := 0
	for curNode.key < k {
		count++
		if curNode.right == nil {
			break
		}
		println("curNode.key < k ", curNode.key, "-->", curNode.right.key)
		curNode = curNode.right
	}
	for curNode.key > k {
		count++
		if curNode.left == nil {
			break
		}
		println("curNode.key > k ", curNode.key, "-->", curNode.left.key)
		curNode = curNode.left
	}
	if curNode.down != nil {
		var newCount int
		println("curNode.down ", curNode.key, "-->", curNode.down.key)
		curNode, newCount = walkPreviousNode(curNode.down, k)
		count += newCount
	}
	return curNode, count
}

func (jt *jumpTable) isPromotion() bool {
	n := jt.r.Intn(2)
	if n == 0 {
		return false
	}
	return true
}