RustyNail

パッケージ skiptable

import (
	"math/rand"
	"time"
)

func init() {
	rand.Seed(time.Now().UnixNano())
}

// New 新しいテーブルを取得します
func New(maxLevel int) *SkipTable {
	st := SkipTable{}
	st.init(maxLevel)
	return &st
}

// ノード
type node struct {
	Level int
	Key   string
	Value interface{}

	Next []*node
}

// SkipTable テーブル
type SkipTable struct {
	MaxLevel int
	Size     int
	Head     *node
	Tail     *node
}

// PrintTable このテーブルを表示します
func (st *SkipTable) PrintTable() {
	i := st.MaxLevel - 1
	for i >= 0 {
		c := st.Head
		if c == st.Head {
			print("[")
		}
		for c != st.Tail {
			print(c.Key, "-")
			c = c.Next[i]
		}
		if c == st.Tail {
			print("]")
		}
		i = i - 1
		println()
	}
}

func (st *SkipTable) init(maxLevel int) {
	st.MaxLevel = maxLevel
	st.Tail = &node{
		// Key: "tail"
	}
	st.Head = &node{
		// Key:   "head",
		Level: 0,
		Next:  make([]*node, maxLevel),
	}
	a := 0
	for a < len(st.Head.Next) {
		st.Head.Next[a] = st.Tail
		a = a + 1
	}
}

// Put データを追加します
func (st *SkipTable) Put(key string, value interface{}) {
	pre := make([]*node, st.MaxLevel)
	curr := st.Head
	a := st.MaxLevel - 1
	for a >= 0 {
		if curr.Next[a] == st.Tail || curr.Next[a].Key > key {
			pre[a] = curr
		} else {
			for curr.Next[a] != st.Tail && curr.Next[a].Key < key {
				curr = curr.Next[a]
			}
			// equal
			if curr.Next[a] != st.Tail && curr.Next[a].Key == key {
				curr.Next[a].Value = value
				return
			}
			pre[a] = curr
		}
		a = a - 1
	}
	level := getLevel(st.MaxLevel)

	temp := &node{
		Key:   key,
		Value: value,
		Level: level,
		Next:  make([]*node, level),
	}
	a = 0
	for a < level {
		temp.Next[a] = pre[a].Next[a]
		pre[a].Next[a] = temp
		a = a + 1
	}

	st.Size = st.Size + 1

}

// Del キーによって値を削除します
func (st *SkipTable) Del(key string) {
	pre := make([]*node, st.MaxLevel)
	curr := st.Head
	top := st.MaxLevel - 1
	for top >= 0 {
		if curr.Next[top] == st.Tail || curr.Next[top].Key > key {
			pre[top] = nil
		} else {
			for curr.Next[top] != st.Tail && curr.Next[top].Key < key {
				curr = curr.Next[top]
			}
			if curr.Next[top] != st.Tail && curr.Next[top].Key == key {
				pre[top] = curr
			} else {
				pre[top] = nil
			}
		}

		top = top - 1
	}

	top = st.MaxLevel - 1
	for top >= 0 {
		if pre[top] != nil {
			println("pre[top].Next[top]-->", pre[top].Next[top].Key)
			pre[top].Next[top] = pre[top].Next[top].Next[top]
		}
		top = top - 1
	}

}

// Get キーによって値を取得します
func (st *SkipTable) Get(key string) interface{} {
	curr := st.Head
	top := st.MaxLevel - 1
	for top >= 0 {
		for curr.Next[top] != st.Tail && curr.Next[top].Key < key {
			curr = curr.Next[top]
		}
		if curr.Next[top].Key == key {
			return curr.Next[top].Value
		}
		top = top - 1
	}
	return nil
}

func getLevel(max int) int {
	level := 1
	for {
		temp := rand.Int()
		if temp%2 == 0 && level < max {
			level = level + 1
		} else {
			break
		}
	}
	return level
}