skiplist

Documentation

Index

• func Equals[T comparable](a, b T) bool
• func Less[T Ordered](a, b T) bool
• func OrderedCompare[T Ordered](a, b T) int
• type CompareFn
• type Container
• type Float
• type HashFn
• type Integer
• type Iterator
• type LessFn
• type Map
• type MapIterator
• type Numeric
• type Ordered
• type Set
• type Signed
• type SkipList
  • func NewSkipList[K Ordered, V any]() *SkipList[K, V]
  • func NewSkipListFromMap[K Ordered, V any](m map[K]V) *SkipList[K, V]
  • func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V]
  • func (sl *SkipList[K, V]) Clear()
  • func (sl *SkipList[K, V]) Find(key K) *V
  • func (sl *SkipList[K, V]) FindRange(first, last K) MapIterator[K, V]
  • func (sl *SkipList[K, V]) ForEach(op func(K, V))
  • func (sl *SkipList[K, V]) ForEachIf(op func(K, V) bool)
  • func (sl *SkipList[K, V]) ForEachMutable(op func(K, *V))
  • func (sl *SkipList[K, V]) ForEachMutableIf(op func(K, *V) bool)
  • func (sl *SkipList[K, V]) Has(key K) bool
  • func (sl *SkipList[K, V]) Insert(key K, value V)
  • func (sl *SkipList[K, V]) IsEmpty() bool
  • func (sl *SkipList[K, V]) Iterate() MapIterator[K, V]
  • func (sl *SkipList[K, V]) Len() int
  • func (sl *SkipList[K, V]) LowerBound(key K) MapIterator[K, V]
  • func (sl *SkipList[K, V]) Remove(key K) bool
  • func (sl *SkipList[K, V]) UpperBound(key K) MapIterator[K, V]
• type Unsigned

Functions

func Equals

func Equals[T comparable](a, b T) bool

Equals wraps the '==' operator for comparable types.

func Less

func Less[T Ordered](a, b T) bool

Less wraps the '<' operator for ordered types.

func OrderedCompare

func OrderedCompare[T Ordered](a, b T) int

OrderedCompare provide default CompareFn for ordered types.

Types

type CompareFn

type CompareFn[T any] func(a, b T) int

CompareFn is a 3 way compare function that returns 1 if a > b, returns 0 if a == b, returns -1 if a < b.

type Container

type Container interface {
	IsEmpty() bool // IsEmpty checks if the container has no elements.
	Len() int      // Len returns the number of elements in the container.
	Clear()        // Clear erases all elements from the container. After this call, Len() returns zero.
}

Container is a holder object that stores a collection of other objects.

type Float

type Float interface {
	~float32 | ~float64
}

Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.

type HashFn

type HashFn[T any] func(t T) uint64

HashFn is a function that returns the hash of 't'.

type Integer

type Integer interface {
	Signed | Unsigned
}

Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.

type Iterator

type Iterator[T any] interface {
	IsNotEnd() bool // Whether it is point to the end of the range.
	MoveToNext()    // Let it point to the next element.
	Value() T       // Return the value of current element.
}

Iterator is the interface for container's iterator.

type LessFn

type LessFn[T any] func(a, b T) bool

LessFn is a function that returns whether 'a' is less than 'b'.

type Map

type Map[K any, V any] interface {
	Container
	Has(K) bool                        // Checks whether the container contains element with specific key.
	Find(K) *V                         // Finds element with specific key.
	Insert(K, V)                       // Inserts a key-value pair in to the container or replace existing value.
	Remove(K) bool                     // Remove element with specific key.
	ForEach(func(K, V))                // Iterate the container.
	ForEachIf(func(K, V) bool)         // Iterate the container, stops when the callback returns false.
	ForEachMutable(func(K, *V))        // Iterate the container, *V is mutable.
	ForEachMutableIf(func(K, *V) bool) // Iterate the container, *V is mutable, stops when the callback returns false.
}

Map is a associative container that contains key-value pairs with unique keys.

type MapIterator

type MapIterator[K any, V any] interface {
	Iterator[V]
	Key() K // The key of the element
}

MapIterator is the interface for map's iterator.

type Numeric

type Numeric interface {
	Integer | Float
}

Numeric is a constraint that permits any numeric type.

type Ordered

type Ordered interface {
	Integer | Float | ~string
}

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

type Set

type Set[K any] interface {
	Container
	Has(K) bool             // Checks whether the container contains element with specific key.
	Insert(K)               // Inserts a key-value pair in to the container or replace existing value.
	InsertN(...K)           // Inserts multiple key-value pairs in to the container or replace existing value.
	Remove(K) bool          // Remove element with specific key.
	RemoveN(...K)           // Remove multiple elements with specific keys.
	ForEach(func(K))        // Iterate the container.
	ForEachIf(func(K) bool) // Iterate the container, stops when the callback returns false.
}

Set is a containers that store unique elements.

type Signed

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.

type SkipList

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

SkipList is a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

See https://en.wikipedia.org/wiki/Skip_list for more details.

func NewSkipList

func NewSkipList[K Ordered, V any]() *SkipList[K, V]

NewSkipList creates a new SkipList for Ordered key type.

func NewSkipListFromMap

func NewSkipListFromMap[K Ordered, V any](m map[K]V) *SkipList[K, V]

NewSkipListFromMap creates a new SkipList from a map.

func NewSkipListFunc

func NewSkipListFunc[K any, V any](keyCmp CompareFn[K]) *SkipList[K, V]

NewSkipListFunc creates a new SkipList with specified compare function keyCmp.

func (*SkipList[K, V]) Clear

func (sl *SkipList[K, V]) Clear()

Clear implements the Container interface.

func (*SkipList[K, V]) Find

func (sl *SkipList[K, V]) Find(key K) *V

Find returns the value associated with the passed key if the key is in the skiplist, otherwise returns nil.

func (*SkipList[K, V]) FindRange

func (sl *SkipList[K, V]) FindRange(first, last K) MapIterator[K, V]

FindRange returns an iterator in range [first, last) (last is not includeed).

func (*SkipList[K, V]) ForEach

func (sl *SkipList[K, V]) ForEach(op func(K, V))

ForEach implements the Map interface.

func (*SkipList[K, V]) ForEachIf

func (sl *SkipList[K, V]) ForEachIf(op func(K, V) bool)

ForEachIf implements the Map interface.

func (*SkipList[K, V]) ForEachMutable

func (sl *SkipList[K, V]) ForEachMutable(op func(K, *V))

ForEachMutable implements the Map interface.

func (*SkipList[K, V]) ForEachMutableIf

func (sl *SkipList[K, V]) ForEachMutableIf(op func(K, *V) bool)

ForEachMutableIf implements the Map interface.

func (*SkipList[K, V]) Has

func (sl *SkipList[K, V]) Has(key K) bool

Has implement the Map interface.

func (*SkipList[K, V]) Insert

func (sl *SkipList[K, V]) Insert(key K, value V)

Insert inserts a key-value pair into the skiplist. If the key is already in the skip list, it's value will be updated.

func (*SkipList[K, V]) IsEmpty

func (sl *SkipList[K, V]) IsEmpty() bool

IsEmpty implements the Container interface.

func (*SkipList[K, V]) Iterate

func (sl *SkipList[K, V]) Iterate() MapIterator[K, V]

Iterate return an iterator to the skiplist.

func (*SkipList[K, V]) Len

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

Len implements the Container interface.

func (*SkipList[K, V]) LowerBound

func (sl *SkipList[K, V]) LowerBound(key K) MapIterator[K, V]

LowerBound returns an iterator to the first element in the skiplist that does not satisfy element < value (i.e. greater or equal to), or a end itetator if no such element is found.

func (*SkipList[K, V]) Remove

func (sl *SkipList[K, V]) Remove(key K) bool

Remove removes the key-value pair associated with the passed key and returns true if the key is in the skiplist, otherwise returns false.

func (*SkipList[K, V]) UpperBound

func (sl *SkipList[K, V]) UpperBound(key K) MapIterator[K, V]

UpperBound returns an iterator to the first element in the skiplist that does not satisfy value < element (i.e. strictly greater), or a end itetator if no such element is found.

type Unsigned

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Unsigned is a constraint that permits any unsigned integer type. If future releases of Go add new predeclared unsigned integer types, this constraint will be modified to include them.