Documentation
¶
Overview ¶
Package skipmap implements ordered key-value mapping based on skip lists. This file implements the Entry API, providing Rust-like entry operations for conditional key-value manipulation.
Package skipmap implements ordered key-value mapping based on skip lists. SkipMap provides ordered operations and efficient query performance with time complexity approaching O(log n). Thread safety for all operations depends on usage scenarios; no concurrency safety is guaranteed by default.
Example:
// Create a new string-to-integer map
m := skipmap.NewOrdered[string, int]()
// Insert a key-value pair
_, updated := m.Insert("apple", 5)
fmt.Println(updated) // false, because it's a new insertion
// Update an existing key
oldValue, updated := m.Insert("apple", 10)
fmt.Println(oldValue, updated) // 5 true
// Get a value
val, found := m.Get("apple")
if found {
fmt.Println(val) // 10
}
// Iterate over all key-value pairs (sorted by key)
for k, v := range m.Iter() {
fmt.Printf("%s: %d\n", k, v)
}
Index ¶
- type Entry
- type SkipMap
- func (sm *SkipMap[K, V]) Clear()
- func (sm *SkipMap[K, V]) Clone() *SkipMap[K, V]
- func (sm *SkipMap[K, V]) ContainsKey(key K) bool
- func (sm *SkipMap[K, V]) Entry(key K) Entry[K, V]
- func (m *SkipMap[K, V]) Extend(it iter.Seq2[K, V])
- func (sm *SkipMap[K, V]) First() (k K, v V, found bool)
- func (sm *SkipMap[K, V]) Get(key K) (V, bool)
- func (sm *SkipMap[K, V]) GetComparator() func(K, K) int
- func (sm *SkipMap[K, V]) GetKeyValue(key K) (k K, v V, found bool)
- func (sm *SkipMap[K, V]) GetMut(key K) (*V, bool)
- func (sm *SkipMap[K, V]) Insert(key K, value V) (V, bool)
- func (sm *SkipMap[K, V]) IsEmpty() bool
- func (m *SkipMap[K, V]) Iter() iter.Seq2[K, V]
- func (m *SkipMap[K, V]) IterBack() iter.Seq2[K, V]
- func (m *SkipMap[K, V]) IterBackMut() iter.Seq2[K, *V]
- func (m *SkipMap[K, V]) IterMut() iter.Seq2[K, *V]
- func (m *SkipMap[K, V]) Keys() iter.Seq[K]
- func (m *SkipMap[K, V]) KeysBack() iter.Seq[K]
- func (sm *SkipMap[K, V]) Last() (k K, v V, found bool)
- func (sm *SkipMap[K, V]) Len() int
- func (sm *SkipMap[K, V]) PopFirst() (k K, v V, found bool)
- func (sm *SkipMap[K, V]) PopLast() (k K, v V, found bool)
- func (m *SkipMap[K, V]) Range(lowerBound, upperBound *K) iter.Seq2[K, V]
- func (m *SkipMap[K, V]) RangeMut(lowerBound, upperBound *K) iter.Seq2[K, *V]
- func (sm *SkipMap[K, V]) Remove(key K) (V, bool)
- func (m *SkipMap[K, V]) Values() iter.Seq[V]
- func (m *SkipMap[K, V]) ValuesBack() iter.Seq[V]
- func (m *SkipMap[K, V]) ValuesBackMut() iter.Seq[*V]
- func (m *SkipMap[K, V]) ValuesMut() iter.Seq[*V]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entry ¶
type Entry[K, V any] struct { // contains filtered or unexported fields }
func (Entry[K, V]) AndModify ¶
AndModify applies the specified modification function to the value if the key exists; if the key does not exist, no operation is performed. Parameters:
- modifyFn: Function used to modify the existing value
Returns:
- The same Entry, allowing for chained calls to other methods
func (Entry[K, V]) Get ¶
Get retrieves the value associated with the key (if it exists). Returns:
- If the key exists, returns a reference to the value and true
- If the key does not exist, returns nil and false
func (Entry[K, V]) Insert ¶
Insert unconditionally inserts or updates the key-value pair. Parameters:
- value: The value to insert or update
Returns:
- If the key already existed, returns the old value and true
- If the key did not exist, returns the zero value and false
func (Entry[K, V]) OrInsert ¶
func (e Entry[K, V]) OrInsert(value V) *V
OrInsert inserts the specified value if the key does not exist and returns a reference to the value; if the key already exists, it returns a reference to the existing value without performing insertion. Parameters:
- value: The value to insert if the key does not exist
Returns:
- A pointer to the existing value or the newly inserted value
func (Entry[K, V]) OrInsertWith ¶
func (e Entry[K, V]) OrInsertWith(f func() V) *V
OrInsertWith uses the provided function to generate a value and inserts it if the key does not exist, then returns a reference to the value; if the key already exists, it returns a reference to the existing value without performing insertion. This is useful when generating the value might be expensive, as it avoids unnecessary computation. Parameters:
- f: Function used to generate the value if the key does not exist
Returns:
- A pointer to the existing value or the newly generated value
func (Entry[K, V]) OrInsertWithKey ¶
func (e Entry[K, V]) OrInsertWithKey(f func(K) V) *V
OrInsertWithKey uses the provided function and the key to generate a value and inserts it if the key does not exist, then returns a reference to the value; if the key already exists, it returns a reference to the existing value without performing insertion. This is useful when the value needs to be generated based on the key. Parameters:
- f: Function used to generate the value if the key does not exist, taking the key as an argument
Returns:
- A pointer to the existing value or the newly generated value
type SkipMap ¶
type SkipMap[K, V any] struct { // contains filtered or unexported fields }
SkipMap implements an ordered map based on skip lists. A skip list is a data structure that allows for fast lookups, functioning as a multi-level linked list, where each level is ordered and upper levels are subsets of lower levels, used to accelerate the lookup process. It provides key-ordered iteration and efficient range queries. Key ordering is achieved through a custom comparison function provided during construction.
func New ¶
New creates a new empty SkipMap using the specified key comparison function. Parameters:
- comparator: Function for comparing keys, cannot be nil. Should return a negative number if a < b, zero if a == b, and a positive number if a > b.
Returns:
- Pointer to the newly created SkipMap
func NewFromMap ¶
NewFromMap creates a new SkipMap instance from an existing map. Parameters:
- m: The map to copy key-value pairs from
Type Parameters:
- K: Key type, must be comparable
- V: Value type
- M: Map type, must be a map with comparable keys and any value type
Returns:
- Pointer to the newly created SkipMap
func NewOrdered ¶
NewOrdered creates a new empty SkipMap for key types that support ordered comparison. This is a convenience function that uses cmp.Compare as the comparator. Type parameters:
- K: Key type, must implement cmp.Ordered interface
- V: Value type, can be any type
Returns:
- Pointer to the newly created SkipMap
func (*SkipMap[K, V]) Clear ¶
func (sm *SkipMap[K, V]) Clear()
Clear removes all key-value pairs from the map, making it empty.
func (*SkipMap[K, V]) Clone ¶
Clone creates a deep copy of the map. Returns:
- A new SkipMap containing all the same key-value pairs
Note: The clone operation copies all key-value pairs, but does not deep copy the keys and values themselves.
func (*SkipMap[K, V]) ContainsKey ¶
ContainsKey checks if the map contains the specified key. Parameters:
- key: The key to check for
Returns:
- true if the key exists, false otherwise
func (*SkipMap[K, V]) Entry ¶
Entry gets an Entry object for the specified key, used for conditionally inserting or updating values. Similar to Rust's entry API, it provides more flexible key-value operations. Parameters:
- key: The key to operate on
Returns:
- An Entry object for the key, which can be used to perform various conditional operations
func (*SkipMap[K, V]) Extend ¶
Extend adds another iterable collection of key-value pairs to the current map. Parameters:
- it: An iterator providing key-value pairs
Behavior:
- For each key-value pair, updates the value if the key already exists, otherwise adds a new key-value pair
func (*SkipMap[K, V]) First ¶
First returns the first (smallest) key-value pair in the map. Returns:
- If the map is empty, returns zero value key, zero value value, and false
- Otherwise returns the smallest key, corresponding value, and true
func (*SkipMap[K, V]) Get ¶
Get retrieves the value associated with the specified key. Parameters:
- key: The key to look up
Returns:
- If the key exists, returns the associated value and true
- If the key does not exist, returns the zero value and false
func (*SkipMap[K, V]) GetComparator ¶
GetComparator returns the key comparison function used by the map. Returns:
- Function for comparing keys
func (*SkipMap[K, V]) GetKeyValue ¶
GetKeyValue returns the key, value, and existence flag. Parameters:
- key: The key to look up
Returns:
- If the key exists, returns the key, associated value, and true
- If the key does not exist, returns zero value key, zero value value, and false
func (*SkipMap[K, V]) GetMut ¶
GetMut retrieves a mutable reference to the value associated with the specified key, allowing in-place modification. Parameters:
- key: The key to look up
Returns:
- If the key exists, returns a pointer to the value and true
- If the key does not exist, returns nil and false
func (*SkipMap[K, V]) Insert ¶
Insert inserts or updates a key-value pair. Parameters:
- key: The key to insert or update
- value: The value to associate with the key
Returns:
- If the key existed, returns the old value and true
- If the key did not exist, returns the zero value and false
func (*SkipMap[K, V]) IsEmpty ¶
IsEmpty checks if the map is empty (contains no key-value pairs). Returns:
- true if the map is empty, false otherwise
func (*SkipMap[K, V]) Iter ¶
Iter returns an iterator over all key/value pairs in the SkipMap in ascending key order.
It returns an `iter.Seq2[K, V]` that yields each (key, value) pair.
func (*SkipMap[K, V]) IterBack ¶
IterBack returns a reverse iterator that yields key/value pairs from largest to smallest key.
It returns an `iter.Seq2[K, V]` that produces pairs in descending key order.
func (*SkipMap[K, V]) IterBackMut ¶
IterBackMut returns a mutable reverse iterator that yields (key, *value) pairs from largest to smallest key.
It returns an `iter.Seq2[K, *V]` for in-place modification while iterating.
func (*SkipMap[K, V]) IterMut ¶
IterMut returns a mutable iterator over all key/value pairs in the SkipMap.
It returns an `iter.Seq2[K, *V]` that yields (key, *value) pairs for in-place modification.
func (*SkipMap[K, V]) Keys ¶
Keys returns an iterator over all keys in the SkipMap in ascending order.
It returns an `iter.Seq[K]` that yields each key.
func (*SkipMap[K, V]) KeysBack ¶
KeysBack returns an iterator over keys in descending order.
It returns an `iter.Seq[K]` that yields keys from largest to smallest.
func (*SkipMap[K, V]) Last ¶
Last returns the last (largest) key-value pair in the map. Returns:
- If the map is empty, returns zero value key, zero value value, and false
- Otherwise returns the largest key, corresponding value, and true
func (*SkipMap[K, V]) Len ¶
Len returns the number of key-value pairs in the map. Returns:
- The number of elements in the map
func (*SkipMap[K, V]) PopFirst ¶
PopFirst removes and returns the first (smallest) key-value pair. Returns:
- If the map is empty, returns zero value key, zero value value, and false
- Otherwise returns the removed key, corresponding value, and true
func (*SkipMap[K, V]) PopLast ¶
PopLast removes and returns the last (largest) key-value pair. Returns:
- If the map is empty, returns zero value key, zero value value, and false
- Otherwise returns the removed key, corresponding value, and true
func (*SkipMap[K, V]) Range ¶
Range returns an iterator over key/value pairs whose keys fall in [lower, upper).
The `lower` bound is inclusive and the `upper` bound is exclusive. A nil bound indicates no limit on that side.
It returns an `iter.Seq2[K, V]` that yields all pairs in ascending key order within the range.
func (*SkipMap[K, V]) RangeMut ¶
RangeMut returns a mutable range iterator over key/value pairs whose keys are in [lower, upper).
It returns an `iter.Seq2[K, *V]` that yields (key, *value) pairs, allowing modification of values.
func (*SkipMap[K, V]) Remove ¶
Remove deletes the key-value pair for the specified key. Parameters:
- key: The key to delete
Returns:
- If the key existed, returns the deleted value and true
- If the key did not exist, returns the zero value and false
func (*SkipMap[K, V]) Values ¶
Values returns an iterator over all values in the SkipMap in ascending key order.
It returns an `iter.Seq[V]` that yields each value.
func (*SkipMap[K, V]) ValuesBack ¶
ValuesBack returns an iterator over values in descending key order.
It returns an `iter.Seq[V]` that yields values corresponding to keys from largest to smallest.
func (*SkipMap[K, V]) ValuesBackMut ¶
ValuesBackMut returns a mutable reverse iterator over values in descending key order.
It returns an `iter.Seq[*V]` that yields pointers to values for in-place modification.
Source Files