skiplist

README

skiplist

reference from redis zskiplist

Usage

package main

import (
	"fmt"
	"log"

	"github.com/gansidui/skiplist"
)

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[T]) Next() *Element[T]
  • func (e *Element[T]) Prev() *Element[T]
• type Interface
• type SkipList
  • func New[T Interface[T]]() *SkipList[T]
  • func (sl *SkipList[T]) Back() *Element[T]
  • func (sl *SkipList[T]) Delete(v T) (res T)
  • func (sl *SkipList[T]) Find(v T) *Element[T]
  • func (sl *SkipList[T]) Front() *Element[T]
  • func (sl *SkipList[T]) GetElementByRank(rank int) *Element[T]
  • func (sl *SkipList[T]) GetRank(v T) int
  • func (sl *SkipList[T]) Init() *SkipList[T]
  • func (sl *SkipList[T]) Insert(v T) *Element[T]
  • func (sl *SkipList[T]) Len() int
  • func (sl *SkipList[T]) Remove(e *Element[T]) (res T)

Constants

const SKIPLIST_BRANCH = 4

const SKIPLIST_MAXLEVEL = 32

Types

type Element

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

func (*Element[T]) Next

func (e *Element[T]) Next() *Element[T]

Next returns the next skiplist element or nil.

func (*Element[T]) Prev

func (e *Element[T]) Prev() *Element[T]

Prev returns the previous skiplist element of nil.

type Interface

type Interface[T any] interface {
	Less(other T) bool
}

type SkipList

type SkipList[T Interface[T]] struct {
	// contains filtered or unexported fields
}

func New

func New[T Interface[T]]() *SkipList[T]

New returns an initialized skiplist.

func (*SkipList[T]) Back

func (sl *SkipList[T]) Back() *Element[T]

Back returns the last elements of skiplist sl or nil.

func (*SkipList[T]) Delete

func (sl *SkipList[T]) Delete(v T) (res T)

Delete deletes an element e that e.Value == v, and returns e.Value or zero T value.

func (*SkipList[T]) Find

func (sl *SkipList[T]) Find(v T) *Element[T]

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

func (*SkipList[T]) Front

func (sl *SkipList[T]) Front() *Element[T]

Front returns the first elements of skiplist sl or nil.

func (*SkipList[T]) GetElementByRank

func (sl *SkipList[T]) GetElementByRank(rank int) *Element[T]

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[T]) GetRank

func (sl *SkipList[T]) GetRank(v T) 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[T]) Init

func (sl *SkipList[T]) Init() *SkipList[T]

Init initializes or clears skiplist sl.

func (*SkipList[T]) Insert

func (sl *SkipList[T]) Insert(v T) *Element[T]

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

func (*SkipList[T]) Len

func (sl *SkipList[T]) Len() int

Len returns the numbler of elements of skiplist sl.

func (*SkipList[T]) Remove

func (sl *SkipList[T]) Remove(e *Element[T]) (res T)

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