Documentation
¶
Overview ¶
Package skipset implements a sorted set based on skip lists. SkipSet provides efficient member checking, insertion, and deletion operations with time complexity close to O(log n). Thread safety depends on the usage scenario; concurrent safety is not guaranteed by default. SkipSet is implemented based on skipmap, internally using SkipMap to store elements with an empty struct as the value type.
Example:
// Create a new set for string elements
s := skipset.NewOrdered[string]()
// Insert an element
added := s.Insert("apple")
fmt.Println(added) // true, because it's newly inserted
// Insert the same element again
added = s.Insert("apple")
fmt.Println(added) // false, because the element already exists
// Check if an element exists
exists := s.Contains("apple")
fmt.Println(exists) // true
// Iterate through all elements (in order)
for val := range s.Iter() {
fmt.Println(val)
}
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]) Iter() 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]) Range(lowerBound, upperBound *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 adds another iterable collection of elements to the current set. Parameters:
- it: Iterator providing elements
Behavior:
- For each element, it is only added if it is not already in the current set
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]) Iter ¶
Iter returns an iterator for all elements in the set, sorted in ascending order of elements. Returns:
- Element iterator of type iter.Seq
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]) Range ¶
Range returns an iterator for elements in the set that fall within the [lowerBound, upperBound) range. Parameters:
- lowerBound: Lower bound of the range (inclusive), nil for no lower bound
- upperBound: Upper bound of the range (exclusive), nil for no upper bound
Returns:
- Iterator for elements in the specified range, sorted in ascending order
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