Documentation
¶
Overview ¶
Package skipset implements a sorted set based on skip lists.
SkipSet is a collection type that stores unique elements in a skip list structure, providing ordered iteration and efficient set operations. All operations run in O(log n) average time. Internally, SkipSet is implemented using SkipMap with empty structs as values.
Time Complexity ¶
- Insert: O(log n) average
- Delete: O(log n) average
- Contains: O(log n) average
- Union/Intersection/Difference: O(m log(m+n)) average where m, n are set sizes
- Traversal: O(n)
Features ¶
- Ordered storage with sorted element iteration (IterAsc, IterDesc)
- Efficient range queries with configurable boundaries (RangeAsc, RangeDesc)
- Standard set operations: Union, Intersection, Difference, SymmetricDifference
- Subset/superset checks: IsSubsetOf, IsSupersetOf
- Generic type support for any cmp.Ordered element type
- Simpler implementation compared to BTreeSet
Usage ¶
SkipSet is simpler than BTreeSet and often faster for smaller datasets:
// For cmp.Ordered elements (recommended)
s := skipset.NewOrdered[string]()
s.Insert("apple")
s.Insert("banana")
// Check existence
if s.Contains("apple") {
fmt.Println("Found apple")
}
Set Operations ¶
SkipSet provides rich set operations:
set1 := skipset.NewOrdered[int]()
set1.Insert(1, 2, 3)
set2 := skipset.NewOrdered[int]()
set2.Insert(2, 3, 4)
union := set1.Union(set2) // {1, 2, 3, 4}
intersection := set1.Intersection(set2) // {2, 3}
difference := set1.Difference(set2) // {1}
Index ¶
- type SkipSet
- func (ss *SkipSet[E]) Clear()
- func (ss *SkipSet[E]) Clone() *SkipSet[E]
- func (ss *SkipSet[E]) Contains(key E) bool
- func (ss *SkipSet[E]) Difference(other *SkipSet[E]) *SkipSet[E]
- func (ss *SkipSet[E]) Equal(other *SkipSet[E]) bool
- func (ss *SkipSet[E]) Extend(it iter.Seq[E])
- func (ss *SkipSet[E]) First() (E, bool)
- func (ss *SkipSet[E]) Insert(key E) bool
- func (ss *SkipSet[E]) Intersection(other *SkipSet[E]) *SkipSet[E]
- func (ss *SkipSet[E]) IsDisjoint(other *SkipSet[E]) bool
- func (ss *SkipSet[E]) IsEmpty() bool
- func (ss *SkipSet[E]) IsSubset(other *SkipSet[E]) bool
- func (ss *SkipSet[E]) IsSuperset(other *SkipSet[E]) bool
- func (ss *SkipSet[E]) IterAsc() iter.Seq[E]
- func (ss *SkipSet[E]) IterDesc() iter.Seq[E]
- func (ss *SkipSet[E]) Last() (E, bool)
- func (ss *SkipSet[E]) Len() int
- func (ss *SkipSet[E]) PopFirst() (E, bool)
- func (ss *SkipSet[E]) PopLast() (E, bool)
- func (ss *SkipSet[E]) RangeAsc(bounds bound.RangeBounds[E]) iter.Seq[E]
- func (ss *SkipSet[E]) RangeDesc(bounds bound.RangeBounds[E]) iter.Seq[E]
- func (ss *SkipSet[E]) Remove(key E) bool
- func (ss *SkipSet[E]) SymmetricDifference(other *SkipSet[E]) *SkipSet[E]
- func (ss *SkipSet[E]) Union(other *SkipSet[E]) *SkipSet[E]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SkipSet ¶
type SkipSet[E any] struct { // contains filtered or unexported fields }
func New ¶
New creates a new empty SkipSet using the specified key comparison function. Parameters:
- comparator: Function for comparing keys, must not be nil. Should return a negative number when a < b, 0 when a == b, and a positive number when a > b.
Returns:
- Pointer to the newly created SkipSet
func NewOrdered ¶
NewOrdered creates a new empty SkipSet for element types that support ordered comparison. This is a convenience function that uses cmp.Compare as the comparator. Type Parameters:
- E: Element type, must implement the cmp.Ordered interface
Returns:
- Pointer to the newly created SkipSet
func (*SkipSet[E]) Clear ¶
func (ss *SkipSet[E]) Clear()
Clear removes all elements from the set, making it empty.
func (*SkipSet[E]) Clone ¶
Clone creates a deep copy of the set. Returns:
- A new SkipSet containing all the same elements
func (*SkipSet[E]) Contains ¶
Contains checks if the set contains the specified element. Parameters:
- key: The element to check
Returns:
- true if the element exists, false otherwise
func (*SkipSet[E]) Difference ¶
Difference computes the difference between the current set and another set, returning a new set containing elements in the current set but not in the other set. Parameters:
- other: Another SkipSet
Returns:
- New SkipSet containing elements that exist in the current set but not in the other set
func (*SkipSet[E]) Equal ¶
Equal checks if the current set is equal to another set (contains the same elements). Parameters:
- other: Another SkipSet
Returns:
- true if the two sets contain the same elements
- false otherwise
func (*SkipSet[E]) Extend ¶
Extend inserts all elements from the iterator into the set.
Parameters:
- it: An iterator yielding elements to insert.
func (*SkipSet[E]) First ¶
First returns the first (smallest) element in the set. Returns:
- The element and true if the set is not empty
- Zero value and false if the set is empty
func (*SkipSet[E]) Insert ¶
Insert adds an element to the set. Parameters:
- key: The element to add
Returns:
- true if the element was newly added (didn't exist before)
- false if the element already existed
func (*SkipSet[E]) Intersection ¶
Intersection computes the intersection of the current set and another set, returning a new set containing only elements present in both sets. Parameters:
- other: Another SkipSet
Returns:
- New SkipSet containing elements that exist in both the current set and the other set
func (*SkipSet[E]) IsDisjoint ¶
IsDisjoint checks if the current set and another set are disjoint (have no elements in common). Parameters:
- other: Another SkipSet
Returns:
- true if the two sets have no common elements
- false otherwise
func (*SkipSet[E]) IsEmpty ¶
IsEmpty checks if the set is empty (contains no elements). Returns:
- true if the set is empty, false otherwise
func (*SkipSet[E]) IsSubset ¶
IsSubset checks if the current set is a subset of another set. Parameters:
- other: Another SkipSet
Returns:
- true if all elements of the current set are in the other set
- false otherwise
func (*SkipSet[E]) IsSuperset ¶
IsSuperset checks if the current set is a superset of another set. Parameters:
- other: Another SkipSet
Returns:
- true if all elements of the other set are in the current set
- false otherwise
func (*SkipSet[E]) IterAsc ¶
IterAsc returns an iterator over all elements in ascending order.
Returns:
- An iter.Seq[E] that yields elements in ascending order.
Time Complexity: O(n)
func (*SkipSet[E]) IterDesc ¶
IterDesc returns an iterator over all elements in descending order.
Returns:
- An iter.Seq[E] that yields elements in descending order.
Time Complexity: O(n)
func (*SkipSet[E]) Last ¶
Last returns the last (largest) element in the set. Returns:
- The element and true if the set is not empty
- Zero value and false if the set is empty
func (*SkipSet[E]) Len ¶
Len returns the number of elements in the set. Returns:
- The number of elements in the set
func (*SkipSet[E]) PopFirst ¶
PopFirst removes and returns the first (smallest) element in the set. Returns:
- The removed element and true if the set is not empty
- Zero value and false if the set is empty
func (*SkipSet[E]) PopLast ¶
PopLast removes and returns the last (largest) element in the set. Returns:
- The removed element and true if the set is not empty
- Zero value and false if the set is empty
func (*SkipSet[E]) RangeAsc ¶
func (ss *SkipSet[E]) RangeAsc(bounds bound.RangeBounds[E]) iter.Seq[E]
RangeAsc returns an iterator over elements within the given bounds in ascending order.
Parameters:
- bounds: The range bounds specifying the lower and upper limits.
Returns:
- An iter.Seq[E] that yields elements in ascending order within the bounds.
Time Complexity: O(log n + k) where k is the number of elements in the range.
func (*SkipSet[E]) RangeDesc ¶
func (ss *SkipSet[E]) RangeDesc(bounds bound.RangeBounds[E]) iter.Seq[E]
RangeDesc returns an iterator over elements within the given bounds in descending order.
Parameters:
- bounds: The range bounds specifying the lower and upper limits.
Returns:
- An iter.Seq[E] that yields elements in descending order within the bounds.
Time Complexity: O(log n + k) where k is the number of elements in the range.
func (*SkipSet[E]) Remove ¶
Remove removes the specified element from the set. Parameters:
- key: The element to remove
Returns:
- true if the element existed and was removed
- false if the element didn't exist
func (*SkipSet[E]) SymmetricDifference ¶
SymmetricDifference computes the symmetric difference between the current set and another set, returning a new set containing elements that are in either set but not in both. Parameters:
- other: Another SkipSet
Returns:
- New SkipSet containing elements that are in either set but not in both sets simultaneously
Source Files