skiplists

Documentation

Overview

Package skiplists implements a skip list. A skip list can be used as an alternative to a balanced tree, and as a priority queue. Skip lists have the same expected time bounds as balanced trees but are simpler, faster, and use less space. They also provide additional fast random access methods.

The implementation is based on A Skip List Cookbook.

Example

package main

import (
	"fmt"

	"github.com/houz42/abstract/skiplists"
)

func main() {
	list := skiplists.New[int]()

	list.Insert(3)
	list.Insert(2)
	list.Insert(4)
	list.Insert(1)

	list.Delete(2)

	for i := 1; i <= 5; i++ {
		fmt.Println(list.Search(i))
	}

}

Output:

1 true
0 false
3 true
4 true
0 false

Example (PriorityQueue)

package main

import (
	"cmp"
	"fmt"

	"github.com/houz42/abstract/skiplists"
)

func main() {

	type process struct {
		pid      int
		niceness int
	}

	queue := skiplists.NewFunc[process](func(a, b process) int {
		return cmp.Compare(a.niceness, b.niceness)
	})

	queue.Insert(process{pid: 1, niceness: -20})
	queue.Insert(process{pid: 2, niceness: 0})
	queue.Insert(process{pid: 3, niceness: 10})
	queue.Insert(process{pid: 4, niceness: -1})

	for queue.Len() > 0 {
		p := queue.At(0)
		fmt.Printf("start process %d with niceness %d\n", p.pid, p.niceness)
		queue.DeleteAt(0)
	}

}

Output:

start process 1 with niceness -20
start process 4 with niceness -1
start process 2 with niceness 0
start process 3 with niceness 10

Index

• type SkipList
  • func New[V cmp.Ordered]() *SkipList[V]
  • func NewFunc[V any](cmp func(a, b V) int) *SkipList[V]
  • func (sl *SkipList[V]) At(i int) V
  • func (sl *SkipList[V]) Delete(val V)
  • func (sl *SkipList[V]) DeleteAt(i int)
  • func (sl *SkipList[V]) Insert(val V)
  • func (sl *SkipList[V]) Len() int
  • func (sl *SkipList[V]) Reverse() *SkipList[V]
  • func (sl *SkipList[V]) Search(val V) (V, bool)
  • func (sl *SkipList[V]) UpdateAt(i int, val V)

Examples

• Package
• Package (PriorityQueue)
• NewFunc
• SkipList.At
• SkipList.UpdateAt

Types

type SkipList

type SkipList[V any] struct {
	// contains filtered or unexported fields
}

SkipList is a probabilistic data structure logically represents an ordered sequence of elements that allows $O(\log n)$ average complexity for search and insertion, as well as random accesses.

A SkipList is not safe for concurrent use by multiple goroutines.

func New

func New[V cmp.Ordered]() *SkipList[V]

New returns a SkipList of any ordered elements

func NewFunc

func NewFunc[V any](cmp func(a, b V) int) *SkipList[V]

NewFunc returns a SkipList of any type when a custom cmp function is provided. The `cmp` function should return:

• -1 if a is less than b,
• 0 if a equals b,
• +1 if a is greater than b.

NewFunc is intended to be used for types that cannot be ordered by the cmp.Ordered interface or for ordered types with a custom comparison operation (e.g., comparing floats within an approximate epsilon).

Example

package main

import (
	"cmp"
	"fmt"
	"strings"

	"github.com/houz42/abstract/skiplists"
)

func main() {
	list := skiplists.NewFunc[string](func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})

	list.Insert("Hello")
	list.Insert("gopher")
	list.Insert("Go")
	list.Insert("is")
	list.Insert("fun")

	for i := 0; i < 5; i++ {
		fmt.Println(list.At(i))
	}

}

Output:

fun
Go
gopher
Hello
is

func (*SkipList[V]) At

func (sl *SkipList[V]) At(i int) V

At returns the i-th element in the SkipList. It panics if i is not valid, just like accessing slice element with an out-of-range index.

Example

package main

import (
	"fmt"

	"github.com/houz42/abstract/skiplists"
)

func main() {
	list := skiplists.New[int]()

	list.Insert(3)
	list.Insert(5)
	list.Insert(2)
	list.Insert(4)
	list.Insert(1)
	fmt.Println(list.At(2))

	list.Delete(2)
	fmt.Println(list.At(2))

	list.DeleteAt(2)
	fmt.Println(list.At(2))

}

Output:

3
4
5

func (*SkipList[V]) Delete

func (sl *SkipList[V]) Delete(val V)

Delete deletes an element from the SkipList. If the value is not found, nothing happens.

func (*SkipList[V]) DeleteAt

func (sl *SkipList[V]) DeleteAt(i int)

DeleteAt deletes i-th element in the SkipList. It panics if i is not valid, just like accessing slice element with an out-of-range index.

func (*SkipList[V]) Insert

func (sl *SkipList[V]) Insert(val V)

Insert inserts an element into the SkipList. If the element is already in, the element will be overwritten with the input value.

func (*SkipList[V]) Len

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

Len returns number of elements in the SkipList

func (*SkipList[V]) Reverse

func (sl *SkipList[V]) Reverse() *SkipList[V]

Reverse returns a new SkipList which sort the elements in reversed order.

func (*SkipList[V]) Search

func (sl *SkipList[V]) Search(val V) (V, bool)

Search returns an element and true if it is in the SkipList, otherwise zero value of type V and false. The returned value is useful when V is a custom type and the provided `cmp` method may return 0 (means equal) for different values, e.g. `cmp` only compares one field of a struct.

func (*SkipList[V]) UpdateAt

func (sl *SkipList[V]) UpdateAt(i int, val V)

UpdateAt updates the value at the specified index in the SkipList. It panics with a runtime error if the index is out of range.

Example

package main

import (
	"cmp"
	"fmt"
	"strings"

	"github.com/houz42/abstract/skiplists"
)

func main() {
	list := skiplists.NewFunc[string](func(a, b string) int {
		return cmp.Compare(strings.ToLower(a), strings.ToLower(b))
	})

	list.Insert("Hello")
	list.Insert("gopher")
	list.Insert("Go")
	list.Insert("is")
	list.Insert("fun")

	list.UpdateAt(2, "gophers")

	for i := 0; i < 5; i++ {
		fmt.Println(list.At(i))
	}

}

Output:

fun
Go
gophers
Hello
is