skiplist

README

skiplist

reference from redis zskiplist

Usage

package main

import (
	"fmt"
	"github.com/gansidui/skiplist"
	"log"
)

type User struct {
	score float64
	id    string
}

func (u *User) Less(other interface{}) bool {
	if u.score > other.(*User).score {
		return true
	}
	if u.score == other.(*User).score && len(u.id) > len(other.(*User).id) {
		return true
	}
	return false
}

func main() {
	us := make([]*User, 7)
	us[0] = &User{6.6, "hi"}
	us[1] = &User{4.4, "hello"}
	us[2] = &User{2.2, "world"}
	us[3] = &User{3.3, "go"}
	us[4] = &User{1.1, "skip"}
	us[5] = &User{2.2, "list"}
	us[6] = &User{3.3, "lang"}

	// insert
	sl := skiplist.New()
	for i := 0; i < len(us); i++ {
		sl.Insert(us[i])
	}

	// traverse
	for e := sl.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value.(*User).id, "-->", e.Value.(*User).score)
	}
	fmt.Println()

	// rank
	rank1 := sl.GetRank(&User{2.2, "list"})
	rank2 := sl.GetRank(&User{6.6, "hi"})
	if rank1 != 6 || rank2 != 1 {
		log.Fatal()
	}
	if e := sl.GetElementByRank(2); e.Value.(*User).score != 4.4 || e.Value.(*User).id != "hello" {
		log.Fatal()
	}
}

/* output:

hi --> 6.6
hello --> 4.4
lang --> 3.3
go --> 3.3
world --> 2.2
list --> 2.2
skip --> 1.1

*/

License

MIT

Documentation

Index

• Constants
• type Element
  • func (e *Element) Next() *Element
  • func (e *Element) Prev() *Element
• type Interface
• type SkipList
  • func New() *SkipList
  • func (sl *SkipList) Back() *Element
  • func (sl *SkipList) Delete(v Interface) interface{}
  • func (sl *SkipList) Find(v Interface) *Element
  • func (sl *SkipList) Front() *Element
  • func (sl *SkipList) GetElementByRank(rank int) *Element
  • func (sl *SkipList) GetRank(v Interface) int
  • func (sl *SkipList) Init() *SkipList
  • func (sl *SkipList) Insert(v Interface) *Element
  • func (sl *SkipList) Len() int
  • func (sl *SkipList) Remove(e *Element) interface{}

Constants

const SKIPLIST_BRANCH = 4

const SKIPLIST_MAXLEVEL = 32

Types

type Element

type Element struct {
	Value Interface
	// contains filtered or unexported fields
}

func (*Element) Next

func (e *Element) Next() *Element

Next returns the next skiplist element or nil.

func (*Element) Prev

func (e *Element) Prev() *Element

Prev returns the previous skiplist element of nil.

type Interface

type Interface interface {
	Less(other interface{}) bool
}

type SkipList

type SkipList struct {
	// contains filtered or unexported fields
}

func New

func New() *SkipList

New returns an initialized skiplist.

func (*SkipList) Back

func (sl *SkipList) Back() *Element

Back returns the last elements of skiplist sl or nil.

func (*SkipList) Delete

func (sl *SkipList) Delete(v Interface) interface{}

Delete deletes an element e that e.Value == v, and returns e.Value or nil.

func (*SkipList) Find

func (sl *SkipList) Find(v Interface) *Element

Find finds an element e that e.Value == v, and returns e or nil.

func (*SkipList) Front

func (sl *SkipList) Front() *Element

Front returns the first elements of skiplist sl or nil.

func (*SkipList) GetElementByRank

func (sl *SkipList) GetElementByRank(rank int) *Element

GetElementByRank finds an element by ites rank. The rank argument needs bo be 1-based. Note that is the first element e that GetRank(e.Value) == rank, and returns e or nil.

func (*SkipList) GetRank

func (sl *SkipList) GetRank(v Interface) int

GetRank finds the rank for an element e that e.Value == v, Returns 0 when the element cannot be found, rank otherwise. Note that the rank is 1-based due to the span of sl.header to the first element.

func (*SkipList) Init

func (sl *SkipList) Init() *SkipList

Init initializes or clears skiplist sl.

func (*SkipList) Insert

func (sl *SkipList) Insert(v Interface) *Element

Insert inserts v, increments sl.length, and returns a new element of wrap v.

func (*SkipList) Len

func (sl *SkipList) Len() int

Len returns the numbler of elements of skiplist sl.

func (*SkipList) Remove

func (sl *SkipList) Remove(e *Element) interface{}

Remove removes e from sl if e is an element of skiplist sl. It returns the element value e.Value.