Documentation
¶
Overview ¶
Package btreeset implements a B-tree based ordered set data structure.
BTreeSet is an ordered collection type where elements are arranged according to a defined order, and each element appears at most once in the set.
Features:
- Ordered storage with support for sequential element traversal
- Efficient insertion, deletion, and lookup operations with O(log n) time complexity
- Support for set operations (union, intersection, difference, etc.)
- Support for range queries
Example usage:
// Create a new ordered set for integers
set := btreeset.NewOrdered[int]()
// Insert elements
set.Insert(5)
set.Insert(3)
set.Insert(7)
// Check if an element exists
exists := set.Contains(5) // true
// Iterate through elements (in order)
for val := range set.Iter() {
fmt.Println(val) // Output: 3, 5, 7
}
// Set operations
otherSet := btreeset.NewOrdered[int]()
otherSet.Insert(5)
otherSet.Insert(10)
union := set.Union(otherSet) // {3, 5, 7, 10}
intersection := set.Intersection(otherSet) // {5}
Index ¶
- type BTreeSet
- func (s *BTreeSet[T]) Clear()
- func (s *BTreeSet[T]) Clone() *BTreeSet[T]
- func (s *BTreeSet[T]) Contains(value T) bool
- func (s *BTreeSet[T]) Difference(other *BTreeSet[T]) *BTreeSet[T]
- func (s *BTreeSet[T]) Extend(it iter.Seq[T])
- func (s *BTreeSet[T]) First() (T, bool)
- func (s *BTreeSet[T]) Insert(value T) bool
- func (s *BTreeSet[T]) Intersection(other *BTreeSet[T]) *BTreeSet[T]
- func (s *BTreeSet[T]) IsDisjoint(other *BTreeSet[T]) bool
- func (s *BTreeSet[T]) IsEmpty() bool
- func (s *BTreeSet[T]) IsSubset(other *BTreeSet[T]) bool
- func (s *BTreeSet[T]) IsSuperset(other *BTreeSet[T]) bool
- func (s *BTreeSet[T]) Iter() iter.Seq[T]
- func (s *BTreeSet[T]) IterBack() iter.Seq[T]
- func (s *BTreeSet[T]) Last() (T, bool)
- func (s *BTreeSet[T]) Len() int
- func (s *BTreeSet[T]) PopFirst() (T, bool)
- func (s *BTreeSet[T]) PopLast() (T, bool)
- func (s *BTreeSet[T]) Range(lowerBound, upperBound *T) iter.Seq[T]
- func (s *BTreeSet[T]) Remove(value T) bool
- func (s *BTreeSet[T]) SymmetricDifference(other *BTreeSet[T]) *BTreeSet[T]
- func (s *BTreeSet[T]) Union(other *BTreeSet[T]) *BTreeSet[T]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTreeSet ¶
type BTreeSet[T any] struct { // contains filtered or unexported fields }
func New ¶
New creates a new BTreeSet instance suitable for elements of any type.
Parameters:
comparator: Function used to compare elements. Returns negative when a < b, zero when a == b,
and positive when a > b.
Returns:
A pointer to the newly created BTreeSet
Time complexity: O(1)
func NewOrdered ¶
NewOrdered creates a new ordered BTreeSet suitable for types implementing the cmp.Ordered interface (such as int, string, etc.).
Returns:
A pointer to the newly created BTreeSet
Time complexity: O(1)
func (*BTreeSet[T]) Clear ¶
func (s *BTreeSet[T]) Clear()
Clear empties the set, removing all elements.
After this operation, Len() will return 0.
Time complexity: O(1)
func (*BTreeSet[T]) Clone ¶
Clone creates a deep copy of the set.
Returns:
A new BTreeSet instance containing all elements from the original set
Note: This method performs a deep copy of the set structure, but elements are copied by value (if elements are pointers, the pointers are copied).
Time complexity: O(n)
func (*BTreeSet[T]) Contains ¶
Contains checks if the set contains the specified element.
Parameters:
value: The element value to check
Returns:
true if the set contains the element; false otherwise
Time complexity: O(log n)
func (*BTreeSet[T]) Difference ¶
Difference creates a new set containing elements present in the current set but not in another set (difference).
Parameters:
other: The other set to compute the difference against
Returns:
A new set containing elements that belong to the current set but not to the other set
Mathematical definition: A \ B = {x | x ∈ A and x ∉ B}
Time complexity: O(n * log m), where n is the size of the current set and m is the size of the other set
func (*BTreeSet[T]) Extend ¶
Extend adds all elements from another iterable collection to the current set.
Parameters:
iter: Iterator providing elements to add
For each element in the iterator, it is added only if it does not already exist in the current set.
func (*BTreeSet[T]) First ¶
First returns the first (smallest) element in the set.
Returns:
The smallest element in the set and a boolean indicating if the set is non-empty If the set is empty, returns the zero value of the element type and false
Time complexity: O(log n)
func (*BTreeSet[T]) Insert ¶
Insert adds an element to the set.
Parameters:
value: The element value to insert
Returns:
true if the element was not present and was successfully inserted; false if the element was already present
Time complexity: O(log n)
func (*BTreeSet[T]) Intersection ¶
Intersection creates a new set containing elements that are present in both the current set and another set (intersection).
Parameters:
other: The other set to intersect with the current set
Returns:
A new set containing elements that exist in both sets
Mathematical definition: A ∩ B = {x | x ∈ A and x ∈ B}
Time complexity: O(min(n, m) * log(max(n, m))), where n and m are the sizes of the two sets
func (*BTreeSet[T]) IsDisjoint ¶
IsDisjoint checks if the current set and another set are disjoint (have no elements in common).
Parameters:
other: The other set to check against
Returns:
true if the two sets have no elements in common; false otherwise
Mathematical definition: A and B are disjoint ⇨ A ∩ B = ∅
Time complexity: O(min(n, m) * log(max(n, m))), where n and m are the sizes of the two sets
func (*BTreeSet[T]) IsEmpty ¶
IsEmpty checks if the set is empty.
Returns:
true if the set is empty (contains no elements); false otherwise
Time complexity: O(1)
func (*BTreeSet[T]) IsSubset ¶
IsSubset checks if the current set is a subset of another set.
Parameters:
other: The parent set to check against
Returns:
true if all elements of the current set are present in the other set; false otherwise
Mathematical definition: A ⊆ B ⇨ for all x ∈ A, x ∈ B
Time complexity: O(n * log m), where n is the size of the current set and m is the size of the other set
func (*BTreeSet[T]) IsSuperset ¶
IsSuperset checks if the current set is a superset of another set.
Parameters:
other: The subset to check against
Returns:
true if all elements of the other set are present in the current set; false otherwise
Mathematical definition: A ⊇ B ⇨ for all x ∈ B, x ∈ A
Time complexity: O(m * log n), where m is the size of the other set and n is the size of the current set
func (*BTreeSet[T]) Iter ¶
Iter returns an iterator that traverses all elements in the set in ascending order.
Returns:
An iterator that generates all elements in the set, ordered in ascending order
Note: Modifying the set (inserting or deleting) during iteration may cause undefined behavior.
Time complexity: O(n) for a full traversal, with an amortized O(1) time complexity for individual Next operations
func (*BTreeSet[T]) IterBack ¶
IterBack returns an iterator that traverses all elements in the set in descending order.
Returns:
An iterator that generates all elements in the set, ordered in descending order
Note: Modifying the set (inserting or deleting) during iteration may cause undefined behavior.
Time complexity: O(n) for a full traversal, with an amortized O(1) time complexity for individual Next operations
func (*BTreeSet[T]) Last ¶
Last returns the last (largest) element in the set.
Returns:
The largest element in the set and a boolean indicating if the set is non-empty If the set is empty, returns the zero value of the element type and false
Time complexity: O(log n)
func (*BTreeSet[T]) Len ¶
Len returns the number of elements in the set.
Returns:
The count of elements in the set
Time complexity: O(1)
func (*BTreeSet[T]) PopFirst ¶
PopFirst removes and returns the first (smallest) element from the set.
Returns:
The removed smallest element and a boolean indicating if the operation was successful If the set is empty, returns the zero value of the element type and false
Time complexity: O(log n)
func (*BTreeSet[T]) PopLast ¶
PopLast removes and returns the last (largest) element from the set.
Returns:
The removed largest element and a boolean indicating if the operation was successful If the set is empty, returns the zero value of the element type and false
Time complexity: O(log n)
func (*BTreeSet[T]) Range ¶
Range returns an iterator over elements in the set that fall within the range [lowerBound, upperBound).
Parameters:
lowerBound: The lower bound of the range, or nil for no lower bound upperBound: The upper bound of the range, or nil for no upper bound
Returns:
An iterator that generates all elements within the specified range, ordered in ascending order
func (*BTreeSet[T]) Remove ¶
Remove removes the specified element from the set.
Parameters:
value: The element value to remove
Returns:
true if the element was present and successfully removed; false if the element was not present
Time complexity: O(log n)
func (*BTreeSet[T]) SymmetricDifference ¶
SymmetricDifference creates a new set containing elements that are present in either the current set or another set but not both (symmetric difference).
Parameters:
other: The other set to compute the symmetric difference against
Returns:
A new set containing elements that belong to either the current set or the other set but not both
Mathematical definition: A △ B = (A \ B) ∪ (B \ A) = {x | x ∈ A XOR x ∈ B}
Time complexity: O(n * log m + m * log n), where n and m are the sizes of the two sets
func (*BTreeSet[T]) Union ¶
Union creates a new set containing all elements from both the current set and another set (union).
Parameters:
other: The other set to union with the current set
Returns:
A new set containing all distinct elements from both sets
Mathematical definition: A ∪ B = {x | x ∈ A or x ∈ B}
Time complexity: O(n + m), where n and m are the sizes of the two sets
Source Files