Documentation
¶
Index ¶
- func IntAscending(a, b int) int
- func IntDescending(a, b int) int
- type Comparator
- type Node
- type SkipList
- func (sl *SkipList[K, V]) Ascend(fn func(key K, value V) bool)
- func (sl *SkipList[K, V]) AscendFrom(start K, fn func(key K, value V) bool)
- func (sl *SkipList[K, V]) Delete(key K) (V, bool)
- func (sl *SkipList[K, V]) Get(key K) (V, bool)
- func (sl *SkipList[K, V]) Head(n int) []Node[K, V]
- func (sl *SkipList[K, V]) Len() int
- func (sl *SkipList[K, V]) Max() (K, V, bool)
- func (sl *SkipList[K, V]) Min() (K, V, bool)
- func (sl *SkipList[K, V]) Seed(seed int64)
- func (sl *SkipList[K, V]) Set(key K, value V) (V, bool)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func IntAscending ¶
IntAscending is a default comparator for int Keys in ascending order. Returns -1 if a < b, 0 if a == b, +1 if a > b. Usage:
sl := skiplist.New[int, V](skiplist.IntAscending)
Example ¶
ExampleIntAscending demonstrates creating a SkipList with int keys in ascending order using the provided IntAscending comparator.
sl := New[int, string](IntAscending)
// Insert keys out of order
sl.Set(3, "c")
sl.Set(1, "a")
sl.Set(2, "b")
// Iterate in ascending numeric order of keys: 1, 2, 3
sl.Ascend(func(k int, v string) bool {
fmt.Printf("%d:%s\n", k, v)
return true
})
Output: 1:a 2:b 3:c
func IntDescending ¶
IntDescending is a default comparator for int Keys in descending order. Returns -1 if a > b, 0 if a == b, +1 if a < b. Usage:
sl := skiplist.New[int, V](skiplist.IntDescending)
Example ¶
ExampleIntDescending demonstrates creating a SkipList with int keys in descending order using the provided IntDescending comparator.
sl := New[int, string](IntDescending)
// Insert keys out of order
sl.Set(3, "c")
sl.Set(1, "a")
sl.Set(2, "b")
// Iterate in descending numeric order of keys: 3, 2, 1
sl.Ascend(func(k int, v string) bool { // Ascend follows the list order defined by the comparator
fmt.Printf("%d:%s\n", k, v)
return true
})
Output: 3:c 2:b 1:a
Types ¶
type SkipList ¶
SkipList is a generic skip list implementation that supports custom Key/Value types and customizable per-level segment lengths that control Node height probabilities.
Segment lengths define the probability to advance to the next level when generating a Node height. At level i (0-based), the promotion probability is approximately 1/segmentLengths[i]. If no segment lengths are provided, a default geometric distribution with factor 2 is used.
func New ¶
func New[K any, V any](cmp Comparator[K], segmentLengths ...int) *SkipList[K, V]
New creates a new SkipList with the provided comparator and optional per-level segment lengths. The number of segment lengths controls the maximum level; each Value should be >= 2. If segmentLengths is empty, a default of 32 levels with segment length 2 is used.
func (*SkipList[K, V]) Ascend ¶
Ascend iterates over all Key-Value pairs in ascending Key order. The iteration stops if fn returns false.
func (*SkipList[K, V]) AscendFrom ¶
AscendFrom iterates from the first element with Key >= start.
func (*SkipList[K, V]) Delete ¶
Delete removes the Key from the skip list, returning its Value and true if present.
func (*SkipList[K, V]) Head ¶
Head returns up to the first n elements in ascending Key order as Node values. The returned Node values are copies that expose only Key and Value; the internal linkage (next) is not exported and is left nil in returned values. If n <= 0 or the list is empty, it returns an empty slice. If n >= Len(), it returns all elements.
Source Files