sortedset

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 27, 2026 License: Apache-2.0 Imports: 5 Imported by: 0

README

SortedSet

Algorithm to effectively work with ordered data set. Make possible to get result by rank. Work much effectively versus orderedmap in case of large dataset. Thread-safe implementation.

Documentation

Overview

Package sortedset provides a sorted set backed by a skip list.

NOT safe for concurrent use. Callers must synchronize access externally.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Dump 

type Dump struct {
	Data    map[string]interface{}
	KeyType string
}

Dump represents a JSON-serializable snapshot of a SortedSet.

type GetByKeyRangeOptions 

type GetByKeyRangeOptions struct {
	Limit        int  // limit the max nodes to return
	ExcludeStart bool // exclude start value, so it search in interval (start, end] or (start, end)
	ExcludeEnd   bool // exclude end value, so it search in interval [start, end) or (start, end)
	Remove       bool
}

GetByKeyRangeOptions configures the behavior of GetByKeyRange queries.

type Level 

type Level[K comparable, V comparable] struct {
	// contains filtered or unexported fields
}

Level represents a single skip list level, holding a forward pointer and span.

type Node 

type Node[K comparable, V comparable] struct {
	// contains filtered or unexported fields
}

Node is an element in the sorted set, holding a key for ordering and an associated value.

func (*Node[K, V]) Key 

func (s *Node[K, V]) Key() K

Key returns the node's ordering key.

func (*Node[K, V]) Value 

func (s *Node[K, V]) Value() V

Value returns the node's associated data.

type SafeSortedSet 

type SafeSortedSet[K comparable, V comparable] struct {
	// contains filtered or unexported fields
}

SafeSortedSet is a thread-safe wrapper around SortedSet. All methods are protected by a read-write mutex.

func NewSafeSortedSet 

func NewSafeSortedSet[K comparable, V comparable](c comparator.Comparator) *SafeSortedSet[K, V]

NewSafeSortedSet creates a thread-safe sorted set.

func (*SafeSortedSet[K, V]) Contains 

func (s *SafeSortedSet[K, V]) Contains(value V) bool

Contains delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) Dump 

func (s *SafeSortedSet[K, V]) Dump(makeDump func(key K, value V) (string, string, error)) (string, error)

Dump delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) FindRank 

func (s *SafeSortedSet[K, V]) FindRank(value V) int

FindRank delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) GetByKeyRange 

func (s *SafeSortedSet[K, V]) GetByKeyRange(start K, end K, options *GetByKeyRangeOptions) []*Node[K, V]

GetByKeyRange delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) GetByRank 

func (s *SafeSortedSet[K, V]) GetByRank(rank int, remove bool) *Node[K, V]

GetByRank delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) GetByRankRange 

func (s *SafeSortedSet[K, V]) GetByRankRange(start int, end int, remove bool) []*Node[K, V]

GetByRankRange delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) GetByValue 

func (s *SafeSortedSet[K, V]) GetByValue(value V) *Node[K, V]

GetByValue delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) GetRTop 

func (s *SafeSortedSet[K, V]) GetRTop(count int, remove bool) []*Node[K, V]

GetRTop delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) GetTop 

func (s *SafeSortedSet[K, V]) GetTop(count int, remove bool) []*Node[K, V]

GetTop delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) GetUntilKey 

func (s *SafeSortedSet[K, V]) GetUntilKey(untilKey K, remove bool) []any

GetUntilKey delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) Len 

func (s *SafeSortedSet[K, V]) Len() int

Len delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) PeekMax 

func (s *SafeSortedSet[K, V]) PeekMax() *Node[K, V]

PeekMax delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) PeekMin 

func (s *SafeSortedSet[K, V]) PeekMin() *Node[K, V]

PeekMin delegates to the underlying SortedSet under a read lock.

func (*SafeSortedSet[K, V]) PopMax 

func (s *SafeSortedSet[K, V]) PopMax() *Node[K, V]

PopMax delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) PopMin 

func (s *SafeSortedSet[K, V]) PopMin() *Node[K, V]

PopMin delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) Remove 

func (s *SafeSortedSet[K, V]) Remove(value V) *Node[K, V]

Remove delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) Restore 

func (s *SafeSortedSet[K, V]) Restore(keyRestore func(key string, values []string) (K, []V, error), dump string) error

Restore delegates to the underlying SortedSet under a write lock.

func (*SafeSortedSet[K, V]) Upsert 

func (s *SafeSortedSet[K, V]) Upsert(key K, value V) bool

Upsert delegates to the underlying SortedSet under a write lock.

type SortedSet 

type SortedSet[K comparable, V comparable] struct {
	// contains filtered or unexported fields
}

SortedSet is a skip-list-backed sorted set with O(log N) insert, delete, and lookup.

func NewSortedSet 

func NewSortedSet[K comparable, V comparable](c comparator.Comparator) *SortedSet[K, V]

NewSortedSet creates a new empty sorted set using the given comparator for key ordering.

Example 
package main

import (
	"fmt"

	"github.com/FrogoAI/memory/comparator"
	"github.com/FrogoAI/memory/sortedset"
)

func main() {
	ss := sortedset.NewSortedSet[int, string](comparator.IntComparator)

	ss.Upsert(10, "alice")
	ss.Upsert(20, "bob")
	ss.Upsert(30, "charlie")

	fmt.Println(ss.Len())
}

Output:
3

func (*SortedSet[K, V]) Contains 

func (s *SortedSet[K, V]) Contains(value V) bool

Contains reports whether the given value exists in the sorted set.

Example 
package main

import (
	"fmt"

	"github.com/FrogoAI/memory/comparator"
	"github.com/FrogoAI/memory/sortedset"
)

func main() {
	ss := sortedset.NewSortedSet[int, string](comparator.IntComparator)

	ss.Upsert(10, "alice")

	fmt.Println(ss.Contains("alice"))
	fmt.Println(ss.Contains("bob"))
}

Output:
true
false

func (*SortedSet[K, V]) Copy 

func (s *SortedSet[K, V]) Copy() *SortedSet[K, V]

Copy returns a deep copy of the sorted set. The new set has independent storage but shares the same key and value references. Element order and scores are preserved.

func (*SortedSet[K, V]) Dump 

func (s *SortedSet[K, V]) Dump(makeDump func(key K, value V) (string, string, error)) (string, error)

Dump serializes the sorted set to a JSON string using the provided conversion function.

func (*SortedSet[K, V]) FindRank 

func (s *SortedSet[K, V]) FindRank(value V) int

FindRank find the rank of the node specified by key Note that the rank is 1-based integer. Rank 1 means the first node If the node is not found, 0 is returned. Otherwise rank(> 0) is returned Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) GetByKeyRange 

func (s *SortedSet[K, V]) GetByKeyRange(start K, end K, options *GetByKeyRangeOptions) []*Node[K, V]

GetByKeyRange get the nodes whose key within the specific range If options is nil, it `searches` in interval [start, end] without any limit by default Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) GetByRank 

func (s *SortedSet[K, V]) GetByRank(rank int, remove bool) *Node[K, V]

GetByRank get node by rank. Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node; If remove is true, the returned nodes are removed If node is not found at specific rank, nil is returned Time complexity of this method is : O(log(N))

Example 
package main

import (
	"fmt"

	"github.com/FrogoAI/memory/comparator"
	"github.com/FrogoAI/memory/sortedset"
)

func main() {
	ss := sortedset.NewSortedSet[int, string](comparator.IntComparator)

	ss.Upsert(30, "charlie")
	ss.Upsert(10, "alice")
	ss.Upsert(20, "bob")

	node := ss.GetByRank(1, false) // lowest key
	fmt.Println(node.Key(), node.Value())

	node = ss.GetByRank(-1, false) // highest key
	fmt.Println(node.Key(), node.Value())
}

Output:
10 alice
30 charlie

func (*SortedSet[K, V]) GetByRankRange 

func (s *SortedSet[K, V]) GetByRankRange(start int, end int, remove bool) []*Node[K, V]

GetByRankRange get nodes within specific rank range [start, end] Note that the rank is 1-based integer. Rank 1 means the first node; Rank -1 means the last node; If start is greater than end, the returned array is in reserved order If remove is true, the returned nodes are removed Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) GetByValue 

func (s *SortedSet[K, V]) GetByValue(value V) *Node[K, V]

GetByValue get node by value If node is not found, nil is returned Time complexity : O(1)

func (*SortedSet[K, V]) GetRTop 

func (s *SortedSet[K, V]) GetRTop(count int, remove bool) (result []*Node[K, V])

GetRTop return top from end data

func (*SortedSet[K, V]) GetTop 

func (s *SortedSet[K, V]) GetTop(count int, remove bool) (result []*Node[K, V])

GetTop return top data

func (*SortedSet[K, V]) GetUntilKey 

func (s *SortedSet[K, V]) GetUntilKey(untilKey K, remove bool) []any

GetUntilKey get all values until given key

func (*SortedSet[K, V]) Len 

func (s *SortedSet[K, V]) Len() int

Len returns the number of elements in the sorted set.

func (*SortedSet[K, V]) PeekMax 

func (s *SortedSet[K, V]) PeekMax() *Node[K, V]

PeekMax get the element with maximum key, nil if the set is empty Time Complexity : O(1)

func (*SortedSet[K, V]) PeekMin 

func (s *SortedSet[K, V]) PeekMin() *Node[K, V]

PeekMin get the element with minimum key, nil if the set is empty Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) PopMax 

func (s *SortedSet[K, V]) PopMax() *Node[K, V]

PopMax get and remove the element with maximum key, nil if the set is empty Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) PopMin 

func (s *SortedSet[K, V]) PopMin() *Node[K, V]

PopMin get and remove the element with minimal key, nil if the set is empty Time complexity of this method is : O(log(N))

func (*SortedSet[K, V]) Remove 

func (s *SortedSet[K, V]) Remove(value V) *Node[K, V]

Remove delete element specified by key Time complexity of this method is : O(log(N))

Example 
package main

import (
	"fmt"

	"github.com/FrogoAI/memory/comparator"
	"github.com/FrogoAI/memory/sortedset"
)

func main() {
	ss := sortedset.NewSortedSet[int, string](comparator.IntComparator)

	ss.Upsert(10, "alice")
	ss.Upsert(20, "bob")

	ss.Remove("alice")

	fmt.Println(ss.Len())
	fmt.Println(ss.Contains("alice"))
}

Output:
1
false

func (*SortedSet[K, V]) Restore 

func (s *SortedSet[K, V]) Restore(keyRestore func(key string, values []string) (K, []V, error), dump string) error

Restore populates the sorted set from a JSON dump string using the provided conversion function.

func (*SortedSet[K, V]) Upsert 

func (s *SortedSet[K, V]) Upsert(key K, value V) bool

Upsert add an element into the sorted set with specific key / value / key. if the element is added, this method returns true; otherwise false means updated Time complexity of this method is : O(log(N))

Example 
package main

import (
	"fmt"

	"github.com/FrogoAI/memory/comparator"
	"github.com/FrogoAI/memory/sortedset"
)

func main() {
	ss := sortedset.NewSortedSet[int, string](comparator.IntComparator)

	added := ss.Upsert(10, "alice")
	fmt.Println("added:", added)

	updated := ss.Upsert(20, "alice") // same value, new key — updates
	fmt.Println("added:", updated)
}

Output:
added: true
added: false

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.