Documentation
¶
Index ¶
- type Node
- type Option
- type SkipList
- func New[K comparable, V any](cmp func(K, K) int, ops ...Option[K, V]) (*SkipList[K, V], error)
- func NewFromMap[K comparable, V any](cmp func(K, K) int, m map[K]V, ops ...Option[K, V]) (*SkipList[K, V], error)
- func NewFromOrderedMap[K cmp.Ordered, V any](m map[K]V, ops ...Option[K, V]) (*SkipList[K, V], error)
- func NewOrdered[K cmp.Ordered, V any](ops ...Option[K, V]) (*SkipList[K, V], error)
- func (sl *SkipList[K, V]) Ceiling(key K) (k K, v V, found bool)
- func (sl *SkipList[K, V]) Clear()
- func (sl *SkipList[K, V]) Clone() *SkipList[K, V]
- func (sl *SkipList[K, V]) Delete(key K) (v V, found bool)
- func (sl *SkipList[K, V]) Floor(key K) (k K, v V, found bool)
- func (sl *SkipList[K, V]) Get(key K) (v V, found bool)
- func (sl *SkipList[K, V]) IsEmpty() bool
- func (sl *SkipList[K, V]) Keys() []K
- func (sl *SkipList[K, V]) Len() int
- func (sl *SkipList[K, V]) MarshalJSON() ([]byte, error)
- func (sl *SkipList[K, V]) Max() (k K, v V, found bool)
- func (sl *SkipList[K, V]) Min() (k K, v V, found bool)
- func (sl *SkipList[K, V]) Put(key K, value V)
- func (sl *SkipList[K, V]) Range(fn func(K, V) bool)
- func (sl *SkipList[K, V]) String() string
- func (sl *SkipList[K, V]) UnmarshalJSON(data []byte) error
- func (sl *SkipList[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K comparable, V any] struct { Key K // Key of the node Value V // Associated value of the node // contains filtered or unexported fields }
Node represents an element in the SkipList, storing a key-value pair and multiple level pointers.
type Option ¶
type Option[K comparable, V any] func(*SkipList[K, V]) error
Option is a function type that can be used to configure skiplist.
func WithMaxLevel ¶
func WithMaxLevel[K comparable, V any](maxLevel int) Option[K, V]
WithMaxLevel creates an Option to set the maximum level for the skiplist. The max level must be greater than 0.
func WithNodeFormatter ¶
func WithNodeFormatter[K comparable, V any](fn func(k K, v V) string) Option[K, V]
WithNodeFormatter creates an Option to set the node formatter for the skiplist. Affects method: String().
func WithProbability ¶
func WithProbability[K comparable, V any](p float64) Option[K, V]
WithProbability creates an Option to set the probability factor for the skiplist. The probability must be in the range (0,1).
func WithSafe ¶
func WithSafe[K comparable, V any]() Option[K, V]
WithSafe creates a Option to configures the skiplist to be thread-safe.
type SkipList ¶
type SkipList[K comparable, V any] struct { // contains filtered or unexported fields }
SkipList represents a probabilistic balanced data structure for fast lookups, insertions, and deletions. It maintains multiple levels of linked lists, allowing logarithmic time complexity (O(log n)) for operations.
func NewFromMap ¶
func NewFromMap[K comparable, V any](cmp func(K, K) int, m map[K]V, ops ...Option[K, V]) (*SkipList[K, V], error)
NewFromMap creates a new skiplist from the given map.
func NewFromOrderedMap ¶
func NewFromOrderedMap[K cmp.Ordered, V any](m map[K]V, ops ...Option[K, V]) (*SkipList[K, V], error)
NewFromOrderedMap is a convenience function of NewFromMap that uses cmp.Ordered as the comparison function.
func NewOrdered ¶
NewOrdered is a convenience function of New that uses cmp.Ordered as the comparison function.
func (*SkipList[K, V]) Ceiling ¶
Ceiling find the smallest key greater than or equal to the given key. Returns the key-value pair and true if found, zero value and false if not found.
func (*SkipList[K, V]) Clear ¶
func (sl *SkipList[K, V]) Clear()
Clear removes all keys-value pairs from the skiplist.
func (*SkipList[K, V]) Delete ¶
Delete removes a key-value pair from the skiplist. Returns the delted value and true if it exists, zero value and false otherwise.
func (*SkipList[K, V]) Floor ¶
Floor find the largest key less than or equal to the given key. Returns the key-value pair and true if found, zero value and false if not found.
func (*SkipList[K, V]) Get ¶
Get searches for a key in the SkipList and returns its associated value. If the key is found, it returns the value and true; otherwise, it returns the zero value and false.
func (*SkipList[K, V]) Keys ¶
func (sl *SkipList[K, V]) Keys() []K
Keys returns all keys in the skiplist. Returns empty slice(not nil) if the skiplist is empty
func (*SkipList[K, V]) MarshalJSON ¶
MarshalJSON implements the json.Marshaler interface.
func (*SkipList[K, V]) Max ¶
Max returns the maximum key-value pair in the skiplist. Returns zero value and false if the skiplist is empty.
func (*SkipList[K, V]) Min ¶
Min returns the minimum key-value pair in the skiplist. Returns zero value and false if the skiplist is empty.
func (*SkipList[K, V]) Put ¶
func (sl *SkipList[K, V]) Put(key K, value V)
Put inserts a key-value pair into the skip list. If the key already exists, its value is updated.
func (*SkipList[K, V]) Range ¶
Range iterates over all key-value pairs in the SkipList in ascending order. The function `fn` is called for each key-value pair. If `fn` returns false, iteration stops early.
func (*SkipList[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface.
Source Files