Documentation
¶
Index ¶
- Constants
- func WithLevelFunc[K cmp.Ordered, V any](levelFunc LevelFunc) skipListOption[K, V]
- func WithMaxLevel[K cmp.Ordered, V any](maxLevel int) skipListOption[K, V]
- func WithProbability[K cmp.Ordered, V any](prob float64) skipListOption[K, V]
- type LevelFunc
- type Node
- type SkipList
- func (s *SkipList[K, V]) First() *Node[K, V]
- func (s *SkipList[K, V]) Get(key K) (*Node[K, V], int)
- func (s *SkipList[K, V]) GetByPos(k int) *Node[K, V]
- func (s *SkipList[K, V]) Level() int
- func (s *SkipList[K, V]) Remove(key K) (*Node[K, V], int)
- func (s *SkipList[K, V]) RemoveByPos(k int) *Node[K, V]
- func (s *SkipList[K, V]) Set(key K, value V) (*Node[K, V], int, bool)
- func (s *SkipList[K, V]) Size() int
- func (s *SkipList[K, V]) String() string
Examples ¶
Constants ¶
const DefaultMaxLevel = 64
const DefaultProbability = 0.5
const InvalidPos = -1
InvalidPos is returned, when an element is not found within the skip list.
const MaxLevel = 512
Variables ¶
This section is empty.
Functions ¶
func WithLevelFunc ¶
WithLevelFunc adds a custom function for generating the level of each inserted element in the list.
func WithMaxLevel ¶
WithMaxLevel overrides the DefaultMaxLevel.
Types ¶
type Node ¶
type Node[K cmp.Ordered, V any] struct { Value V // Value is the payload within an element node. // contains filtered or unexported fields }
Node holds an element within the SkipList with a unique key `key`.
type SkipList ¶
SkipList is a structure implementing the skip list of William Pugh. It allows in addition to the standard key operations SkipList.Set(), SkipList.Get(), and SkipList.Remove() the indexed linear list operations SkipList.GetByPos() and SkipList.RemoveByPos(). There are two generic parameters K is the key, which must be cmp.Ordered policy, and the value V can be of any type.
func NewSkipList ¶
NewSkipList creates a new empty SkipList object.
Example ¶
package main
import (
"fmt"
"github.com/andremueller/goskiplist/pkg/skiplist"
)
func main() {
// creates a skip list with key type `int` and value type `string`
s := skiplist.NewSkipList[int, string]()
s.Set(1, "cat")
s.Set(2, "dog")
x, _ := s.Get(1)
fmt.Printf("Value: %s", x.Value)
// Output "Value: cat"
}
Output:
func (*SkipList[K, V]) First ¶
First returns the first node of a skip list or nil if the list is empty. With the Node.Next() function the list can be iterated.
func (*SkipList[K, V]) Get ¶
Get returns the node matching the searched key or nil if it was not found. The second return argument is the position 0...n-1 of the key or InvalidPos if the element was not found.
func (*SkipList[K, V]) GetByPos ¶
GetByPos returns the kth element of the skip list where k must be in the interval [0, Size()). This operation is performed in O(log(n)) steps in the average due to the maintenance of the distance vectors within each element. Returns a node pointer to the element.
func (*SkipList[K, V]) Remove ¶
Remove removes an element with key `key` from the skip list. Returns a reference to the removed element and its position 0...n-1 before it was removed.
func (*SkipList[K, V]) RemoveByPos ¶
Remove removes an element at position k [0, Size()) from the skip list. Returns a reference to the removed element.
func (*SkipList[K, V]) Set ¶
Set sets the value `value` of a key `key` within the skip list. Replaces the value if the key was already added to the set or inserts the key if not. Returns a reference to the node and its current position 0...n-1 within the skip list. The bool value is true, if a new node was created and false if the value was overridden.
Example ¶
package main
import (
"fmt"
"github.com/andremueller/goskiplist/pkg/skiplist"
)
func main() {
// creates a skip list with key type `int` and value type `string`
s := skiplist.NewSkipList[int, string]()
// sets keys
s.Set(1, "cat")
s.Set(2, "dog")
// overrides the first key
s.Set(1, "worm")
x, _ := s.Get(1)
fmt.Printf("Value: %s", x.Value)
// Output "Value: worm"
}
Output:
Source Files