skipLinkedList

skipLinkedList.go

package main

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

/*
有序map 使用跳表实现，按key从小到大排序
跳表：有索引的双向链表

操作方式为：
sl := NewSkipList()
sl.Insert(value, score)
sl.Delete(value, score)
sl.First(score)
sl.Find(value, score)
http://media.gusibi.mobi/bZxFcrI52I5ZhtXJRHV03eAWrUjH20FT0QesxUR5lf30RoC71sI8Dm0uN4EQQQFl
*/

const (
	// 最大层数
	MaxLevel = 16
)

// SkipListNode 跳跃表节点定义
type SkipListNode struct {
	data     interface{}     // 节点数据
	score    int             // 排序值
	level    int             // 索引层数
	forwards []*SkipListNode // 跳表节点每一层的下一个节点
}

func newSkipListNode(data interface{}, score, level int) *SkipListNode {
	return &SkipListNode{
		data:     data,
		score:    score,
		forwards: make([]*SkipListNode, level, level),
		level:    level,
	}
}

// SkipList 跳跃表定义
type SkipList struct {
	header *SkipListNode // 头节点
	level  int           // 表内节点最大层数
	length int           // 节点数量
}

// NewSkipList create SkipList
func NewSkipList() *SkipList {
	//头结点，便于操作
	header := newSkipListNode(0, math.MinInt32, MaxLevel)
	return &SkipList{header, 1, 0}
}

// Set SkipList 将一个包含给定 score 和 member 的新节点添加到跳跃表中
func (sl *SkipList) Insert(data interface{}, score int) int {
	// return:
	// 数据错误，return 1
	// 数据重复，return 2
	// 插入成功，return 0
	// data: 数据, score: 排序值
	if data == nil { // 如果数据为空
		return 1
	}
	// 1. 查找插入位置
	cur := sl.header
	// 每一层的路径
	update := [MaxLevel]*SkipListNode{}
	i := MaxLevel - 1
	for ; i >= 0; i-- {
		for cur.forwards[i] != nil {
			if cur.forwards[i].data == data {
				// 如果值相同，说明找到了数据
				return 2
			}
			if cur.forwards[i].score > score {
				// 如果「当前节点的下一个节点」排序分大于要插入的节点
				update[i] = cur
				break
			}
			// 向下一层
			cur = cur.forwards[i]
		}
		if nil == cur.forwards[i] {
			update[i] = cur
		}
	}
	// fmt.Println("update: ", update)
	// 通过随机算法获取该节点层数
	level := 1
	for i := 1; i < MaxLevel; i++ {
		if rand.Int31()%7 == 1 { // 随机16次，显得更随机一点
			level++
		}
	}
	// 创建一个新的跳表节点
	newNode := newSkipListNode(data, score, level)

	// 此跳表节点与原有跳表节点连接
	for i := 0; i <= level-1; i++ {
		// i 代表的是这一层
		next := update[i].forwards[i]
		// update[i] 就是当前节点
		update[i].forwards[i] = newNode
		newNode.forwards[i] = next
	}

	// 如果当前节点的层数大于之前跳表的层数，更新当前跳表的层数
	if level > sl.level {
		sl.level = level
	}
	// 更新跳表的长度
	sl.length++
	return 0
}

// First 查找 找到第一个 >= score 的数据
func (sl SkipList) First(score int) *SkipListNode {
	if sl.length == 0 {
		return nil
	}
	if sl.length == 1 {
		return sl.header.forwards[0]
	}
	cur := sl.header
	update := [MaxLevel]*SkipListNode{} // 每一层的路径
	for i := sl.level - 1; i >= 0; i-- {
		for cur.forwards[i] != nil {
			// 如果当前节点的下一个节点不为空，判断大小
			if cur.forwards[i].score == score {
				// 分数相同
				return cur.forwards[i]
			} else if cur.forwards[i].score > score {
				// 如果下一个节点分数大于当前要查的节点 去下一层
				update[i] = cur
				break
			}
			cur = cur.forwards[i]
		}
	}
	// 当前节点的下一个节点
	return update[0].forwards[0]
}

// Find 查找 找到第一个 >= score 的数据
func (sl SkipList) Find(data interface{}, score int) *SkipListNode {
	if data == nil || sl.length == 0 {
		return nil
	}
	// fmt.Printf("find: %+v\n", data)
	cur := sl.header
	for i := sl.level - 1; i >= 0; i-- {
		for cur.forwards[i] != nil {
			// 如果当前节点的下一个节点不为空，判断大小
			if cur.forwards[i].score == score && cur.forwards[i].data == data {
				// 分数相同 数据一致
				return cur.forwards[i]
			} else if cur.forwards[i].score > score {
				// 如果下一个节点分数大于当前要查的节点 去下一层
				break
			}
			cur = cur.forwards[i]
		}
	}
	return nil
}

func (sl *SkipList) Iterator() func() (*SkipListNode, bool) {
	header := sl.header
	return func() (item *SkipListNode, ok bool) {
		if header == nil {
			return header, false
		}
		item, ok = header, true
		header = header.forwards[0]
		return item, ok
	}
}

func (sl *SkipList) Range(score int) func() (*SkipListNode, bool) {
	header := sl.First(score)
	return func() (item *SkipListNode, ok bool) {
		if header == nil {
			return header, false
		}
		item, ok = header, true
		header = header.forwards[0]
		return item, ok
	}
}

// Delete delete a key
func (sl *SkipList) Delete(v interface{}, score int) int {
	// 记录查询路径
	// 遍历查询路径，如果节点cur 的下一个节点是cur.forwards[0]要删除的节点， cur.forwords[i] = cur.forwards[i].forwards[i]
	if nil == v {
		return 1
	}

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

	cur = update[0].forwards[0]
	for i := cur.level - 1; i >= 0; i-- {
		if update[i] == sl.header && 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
}

// Clear delete all keys
func (sl *SkipList) Clear() error {
	return nil
}

func (sl *SkipList) String() string {
	return fmt.Sprintf("SkipList Level:%+v, Length:%+v", sl.level, sl.length)
}

// OrderedDict 有序map 使用跳表和map实现
// 数据存储到map，通过key 取值，从map 中直接获取，如果没有对应的key，取<key，并且和key 最接近的
type OrderedDict struct {
	dataMap   map[int]interface{}
	dataIndex *SkipList
}

func NewOrderedDict() *OrderedDict {
	data := make(map[int]interface{})
	index := NewSkipList()
	return &OrderedDict{dataMap: data, dataIndex: index}
}

func (od *OrderedDict) Set(key int, value interface{}) int {
	// return:
	// 插入成功，return 0
	// 数据重复，return 2
	// 数据错误，return 1
	dataMap := od.dataMap
	_, ok := dataMap[key]
	if ok {
		return 2
	}
	dataMap[key] = value
	od.dataIndex.Insert(value, key)
	return 1
}

func (od *OrderedDict) Get(key int) (interface{}, bool) {
	// 返回 <= key 中第一个
	dataMap := od.dataMap
	value, ok := dataMap[key]
	if ok {
		return value, ok
	}
	index := od.dataIndex
	node := index.First(key)
	if node == nil {
		return nil, false
	}
	return node.data, true
}

func (od *OrderedDict) Update(key int, value interface{}) int {
	// return:
	// 插入成功，return 0
	// 数据重复，return 2
	// 数据错误，return 1
	dataMap := od.dataMap
	v, ok := dataMap[key]
	if ok && v == value {
		return 2
	} else if !ok {
		dataMap[key] = value
		od.dataIndex.Insert(value, key)
		return 0
	} else if ok && v != value {
		dataMap[key] = value
		return 0
	}
	return 1
}

func (od *OrderedDict) Delete(key int) int {
	// return:
	// 插入成功，return 0
	// 数据不存在，return 1
	dataMap := od.dataMap
	value, ok := dataMap[key]
	if !ok {
		return 1
	}
	delete(od.dataMap, key)
	od.dataIndex.Delete(value, key)
	return 0
}

func test3() {
	orderDict := NewOrderedDict()
	fmt.Println(">>>>>>>>>>>>添加 hello 1")
	orderDict.Set(1, "hello 1")
	fmt.Println(orderDict.dataMap)
	fmt.Print("这里应该是返回 hello 1：")
	fmt.Println(orderDict.Get(1))
	fmt.Print("这里应该是返回 hello 1：")
	fmt.Println(orderDict.Get(2))
	fmt.Println(">>>>>>>>>>>>>>添加 hello 8")
	orderDict.Set(8, "hello 8")
	fmt.Println(orderDict.dataMap)
	fmt.Print("这里应该是返回hello 1：")
	fmt.Println(orderDict.Get(0))
	fmt.Println(orderDict.dataIndex.First(0))
	fmt.Print("这里应该是返回hello 8：")
	fmt.Println(orderDict.Get(7))
	fmt.Print("这里应该是返回hello 8：")
	fmt.Println(orderDict.Get(8))
	orderDict.Set(10, "hello 10")
	orderDict.Delete(8)
	fmt.Print("这里应该是返回hello 10：")
	fmt.Println(orderDict.Get(8))
}

func test() {
	sl := NewSkipList()
	fmt.Println("sl address %p: ", &sl)
	for i := 3; i < 10; i++ {
		value := fmt.Sprintf("hello:%d", i)
		sl.Insert(value, i*10)
	}
	fmt.Println("first item", sl.header.forwards[0])
	fmt.Println("Find item", sl.Find("hello:4", 40))

	sl.Delete("hello:5", 50)
	fmt.Println("Find item 3 应该存在", sl.Find("hello:3", 30))
	fmt.Println("Find item 5 不应该存在", sl.Find("hello:5", 50))
	fmt.Println("First item 5 应该存在 6", sl.First(50))
	fmt.Println("First item 6 应该存在 6", sl.Find("hello:6", 60))
	fmt.Println(sl.header)
	item := sl.header
	fmt.Println("<<<开始遍历>>>")
	for {
		if item == nil {
			break
		}
		fmt.Println("<<<>>>", item, item.score, item.data)
		item = item.forwards[0]
		// time.Sleep(1000 * time.Millisecond)
	}
}

func test2() {
	sl := NewSkipList()
	fmt.Println("sl address %p: ", &sl)
	sl.Insert("jack", 80)
	fmt.Println(sl.header.forwards[0])
	fmt.Println("这里只能是80", sl.First(100))
	sl.Insert("leo", 95)
	fmt.Println(sl.header.forwards[0].forwards[0])
	sl.Insert("lily", 100)
	fmt.Println(sl.header.forwards[0].forwards[0].forwards[0])
	sl.Delete("leo", 95)
	fmt.Println(sl.header.forwards[0].forwards[0])
	fmt.Println(">>>>>>>>>>>>>>>>>>>>>>>>")
	fmt.Println("这里只能是100", sl.First(100))
	items := sl.Iterator()
	for {
		item, ok := items()
		if !ok {
			break
		}
		fmt.Println("<<<>>>", item, item.score, item.data)
	}
	fmt.Println("100 > 80", 100 > 80)
}

func main() {
	// test()
	// test2()
	test3()
}