package main

import (
	"errors"
	"math/rand"
)

type Node struct {
	key   int
	value int
	isDelete bool
	next  *Node
	down  *Node
}

type SkipList struct {
	top *Node
	maxLevel int = 12
	skipRate int = 4
}

func NewSkipList() SkipList {
	var sl SkipList
	sl.top = &Node{}
	prev := sl.top
	for i := 0; i < sl.maxLevel; i++ {
		node := &Node{}
		prev.down = node
		prev = node
	}
	return sl
}

func (sl *SkipList) Get(key int) (int, error) {
	curr := sl.top
	for curr != nil {
		if curr.next == nil {
			curr = curr.down
			continue
		}
		if curr.next.key == key {
			return curr.next.value, nil
		} else if curr.next.key < key {
			curr = curr.next
		} else {
			curr = curr.down
		}
	}
	return 0, errors.New("Not found")
}

func (sl *SkipList) Insert(key, value int) {
	level := sl.randomLevel()
	for 
}

func (sl *SkipList) randomLevel() int {
	lv := 1
	for i := rand.Intn(sl.skipRate); i == 0 && lv < sl.maxLevel; i = rand.Intn(sl.skipRate) {
		lv++
	}
	return lv
}

func main() {

}