skiplist.go

package main

import (
	"fmt"
	"math/rand"

	"golang.org/x/exp/constraints"
)

type SkipList[K constraints.Ordered] struct {
	rand rand.Rand
	next []*Node[K]
}

type Node[K constraints.Ordered] struct {
	next  []*Node[K]
	key   K
	value any
}

func Create[K constraints.Ordered](rand rand.Rand) *SkipList[K] {
	return &SkipList[K]{
		rand,
		make([]*Node[K], 0),
	}
}

func (this *SkipList[K]) FindFirst(key K) *Node[K] {
	next := &this.next
	for level := len(*next) - 1; level >= 0; level-- {
		for (*next)[level] != nil && (*next)[level].key < key {
			next = &(*next)[level].next
		}
	}
	return (*next)[0]
}

func (this *SkipList[K]) Insert(key K, value any) {
	parents := this.traceParents(key)

	node := &Node[K]{
		make([]*Node[K], 0),
		key,
		value,
	}

	for level := 0; this.rand.Float64() > 0.5; level++ {
		if level < len(this.next) {
			node.next = append(node.next, (*parents[level])[level])
			(*parents[level])[level] = node
		} else {
			node.next = append(node.next, nil)
			this.next = append(this.next, node)
		}
	}
}

func (this *SkipList[K]) Delete(key K) {
	parents := this.traceParents(key)

	for level := 0; level < len(this.next); level++ {
		for (*parents[level])[level] != nil && (*parents[level])[level].key == key {
			(*parents[level])[level] = (*parents[level])[level].next[level]
		}
	}

	for len(this.next) > 0 && this.next[len(this.next)-1] == nil {
		this.next = this.next[:len(this.next)-1]
	}
}

func (this *SkipList[K]) traceParents(key K) []*[]*Node[K] {
	next := &this.next
	parents := make([]*[]*Node[K], len(*next))
	for level := len(*next) - 1; level >= 0; level-- {
		for (*next)[level] != nil && (*next)[level].key < key {
			parents[level] = next
			next = &(*next)[level].next
		}
	}
	return parents
}

func main() {
	fmt.Println("Hello, World!")
}