Documentation
¶
Overview ¶
Package ds provides generic data structure implementations. All containers are non-concurrent-safe; use external synchronization when sharing across goroutines.
OrderedMap[K,V] preserves insertion order with O(1) access and zero-allocation iteration. Set[T] offers set algebra (union, intersection, difference) and relation checks (subset, disjoint). BiMap[K,V] provides bidirectional O(1) lookup. Stack[T] and Heap[T] offer LIFO and priority-queue semantics respectively. SortedMap[K,V] combines O(1) random access by key with O(log n) ordered iteration; the sort key and the map lookup key can be different fields of V.
Index ¶
- type BiMap
- func (m *BiMap[K, V]) All() iter.Seq2[K, V]
- func (m *BiMap[K, V]) Clear()
- func (m *BiMap[K, V]) Clone() *BiMap[K, V]
- func (m *BiMap[K, V]) DeleteByKey(key K) bool
- func (m *BiMap[K, V]) DeleteByValue(value V) bool
- func (m *BiMap[K, V]) GetByKey(key K) (V, bool)
- func (m *BiMap[K, V]) GetByValue(value V) (K, bool)
- func (m *BiMap[K, V]) Keys() []K
- func (m *BiMap[K, V]) Len() int
- func (m *BiMap[K, V]) Set(key K, value V)
- func (m *BiMap[K, V]) Values() []V
- type Heap
- type OrderedMap
- func (m *OrderedMap[K, V]) All() iter.Seq2[K, V]
- func (m *OrderedMap[K, V]) Backward() iter.Seq2[K, V]
- func (m *OrderedMap[K, V]) Clear()
- func (m *OrderedMap[K, V]) Clone() *OrderedMap[K, V]
- func (m *OrderedMap[K, V]) Delete(key K) bool
- func (m *OrderedMap[K, V]) Get(key K) (V, bool)
- func (m *OrderedMap[K, V]) Has(key K) bool
- func (m *OrderedMap[K, V]) Keys() []K
- func (m *OrderedMap[K, V]) Len() int
- func (m *OrderedMap[K, V]) Set(key K, value V) bool
- func (m *OrderedMap[K, V]) Values() []V
- type Set
- func (s *Set[T]) Add(val T) bool
- func (s *Set[T]) All() iter.Seq[T]
- func (s *Set[T]) Clear()
- func (s *Set[T]) Clone() *Set[T]
- func (s *Set[T]) Difference(other *Set[T]) *Set[T]
- func (s *Set[T]) Equal(other *Set[T]) bool
- func (s *Set[T]) Has(val T) bool
- func (s *Set[T]) Intersect(other *Set[T]) *Set[T]
- func (s *Set[T]) IsSubset(other *Set[T]) bool
- func (s *Set[T]) IsSuperset(other *Set[T]) bool
- func (s *Set[T]) Len() int
- func (s *Set[T]) Remove(val T) bool
- func (s *Set[T]) SymmetricDifference(other *Set[T]) *Set[T]
- func (s *Set[T]) ToSlice() []T
- func (s *Set[T]) Union(other *Set[T]) *Set[T]
- type SortedMap
- func (m *SortedMap[K, V]) Ascend() iter.Seq[V]
- func (m *SortedMap[K, V]) AscendAfter(pivot V) iter.Seq[V]
- func (m *SortedMap[K, V]) AscendFrom(pivot V) iter.Seq[V]
- func (m *SortedMap[K, V]) Clear()
- func (m *SortedMap[K, V]) Delete(key K) bool
- func (m *SortedMap[K, V]) Descend() iter.Seq[V]
- func (m *SortedMap[K, V]) DescendBefore(pivot V) iter.Seq[V]
- func (m *SortedMap[K, V]) DescendFrom(pivot V) iter.Seq[V]
- func (m *SortedMap[K, V]) Get(key K) (V, bool)
- func (m *SortedMap[K, V]) Has(key K) bool
- func (m *SortedMap[K, V]) Len() int
- func (m *SortedMap[K, V]) Set(val V) bool
- type Stack
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BiMap ¶
type BiMap[K comparable, V comparable] struct { // contains filtered or unexported fields }
BiMap is a bidirectional map with O(1) lookup in both directions. Each key maps to exactly one value and each value maps to exactly one key. It is not safe for concurrent use.
func NewBiMapWithCapacity ¶
func NewBiMapWithCapacity[K, V comparable](n int) *BiMap[K, V]
NewBiMapWithCapacity creates a BiMap with pre-allocated capacity. Panics if n is negative.
func (*BiMap[K, V]) Clear ¶
func (m *BiMap[K, V]) Clear()
Clear removes all mappings, keeping the underlying map storage.
func (*BiMap[K, V]) DeleteByKey ¶
DeleteByKey removes the mapping for key. Returns true if the key existed.
func (*BiMap[K, V]) DeleteByValue ¶
DeleteByValue removes the mapping for value. Returns true if the value existed.
func (*BiMap[K, V]) GetByValue ¶
GetByValue returns the key associated with value.
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap is a binary heap ordered by the compare function. compare(a, b) < 0 means a has higher priority (min-heap default). It is not safe for concurrent use.
func NewHeap ¶
NewHeap creates an empty heap with the given compare function. Panics if compare is nil.
func NewHeapFrom ¶
NewHeapFrom creates a heap from an existing slice in O(n) time. The slice ownership is transferred to the heap. Panics if compare is nil.
func NewMaxHeap ¶
NewMaxHeap creates a max-heap for ordered types.
func NewMinHeap ¶
NewMinHeap creates a min-heap for ordered types using cmp.Compare.
func (*Heap[T]) All ¶
All returns an iterator over all elements in arbitrary order. Does not modify the heap.
func (*Heap[T]) Drain ¶
Drain returns an iterator that pops elements in sorted order until the heap is empty.
func (*Heap[T]) Peek ¶
Peek returns the top element without removing it. Returns (zero, false) if empty.
type OrderedMap ¶
type OrderedMap[K comparable, V any] struct { // contains filtered or unexported fields }
OrderedMap maintains key-value pairs in insertion order. Lookup, insert, and delete are all O(1). Iteration is zero-allocation. It is not safe for concurrent use.
func NewOrderedMap ¶
func NewOrderedMap[K comparable, V any]() *OrderedMap[K, V]
NewOrderedMap creates an empty OrderedMap.
func NewOrderedMapWithCapacity ¶
func NewOrderedMapWithCapacity[K comparable, V any](capacity int) *OrderedMap[K, V]
NewOrderedMapWithCapacity creates an OrderedMap with pre-allocated map capacity. Panics if capacity is negative.
func (*OrderedMap[K, V]) All ¶
func (m *OrderedMap[K, V]) All() iter.Seq2[K, V]
All returns an iterator over key-value pairs in insertion order.
func (*OrderedMap[K, V]) Backward ¶
func (m *OrderedMap[K, V]) Backward() iter.Seq2[K, V]
Backward returns an iterator over key-value pairs in reverse insertion order.
func (*OrderedMap[K, V]) Clear ¶
func (m *OrderedMap[K, V]) Clear()
Clear removes all key-value pairs, keeping the underlying map storage.
func (*OrderedMap[K, V]) Clone ¶
func (m *OrderedMap[K, V]) Clone() *OrderedMap[K, V]
Clone returns a shallow copy of the map. The insertion order is preserved.
func (*OrderedMap[K, V]) Delete ¶
func (m *OrderedMap[K, V]) Delete(key K) bool
Delete removes the key. It returns true if the key was present.
func (*OrderedMap[K, V]) Get ¶
func (m *OrderedMap[K, V]) Get(key K) (V, bool)
Get returns the value associated with key, or the zero value with false if not found.
func (*OrderedMap[K, V]) Has ¶
func (m *OrderedMap[K, V]) Has(key K) bool
Has reports whether the key exists.
func (*OrderedMap[K, V]) Keys ¶
func (m *OrderedMap[K, V]) Keys() []K
Keys returns all keys in insertion order.
func (*OrderedMap[K, V]) Len ¶
func (m *OrderedMap[K, V]) Len() int
Len returns the number of key-value pairs.
func (*OrderedMap[K, V]) Set ¶
func (m *OrderedMap[K, V]) Set(key K, value V) bool
Set stores the key-value pair. It returns true if the key was newly inserted, false if an existing key's value was updated (position unchanged).
func (*OrderedMap[K, V]) Values ¶
func (m *OrderedMap[K, V]) Values() []V
Values returns all values in insertion order.
type Set ¶
type Set[T comparable] struct { // contains filtered or unexported fields }
Set is an unordered collection of unique elements. It is not safe for concurrent use.
func NewSet ¶
func NewSet[T comparable](vals ...T) *Set[T]
NewSet creates a Set initialized with the given values. Duplicates are ignored. Accepting initial values as variadic arguments is intentional — sets are commonly constructed from a known collection of elements.
func NewSetWithCapacity ¶
func NewSetWithCapacity[T comparable](n int) *Set[T]
NewSetWithCapacity creates an empty Set with pre-allocated capacity. Panics if n is negative.
func (*Set[T]) Difference ¶
Difference returns a new Set containing elements in s but not in other.
func (*Set[T]) Intersect ¶
Intersect returns a new Set containing elements present in both s and other.
func (*Set[T]) IsSuperset ¶
IsSuperset reports whether all elements of other are in s.
func (*Set[T]) SymmetricDifference ¶
SymmetricDifference returns a new Set containing elements in s or other but not both.
type SortedMap ¶ added in v0.3.0
type SortedMap[K comparable, V any] struct { // contains filtered or unexported fields }
SortedMap maintains values sorted by a caller-defined order. Backed by a hash map for O(1) random access and a B-tree for O(log n) ordered ops. The sort key and the map lookup key can be different fields of V. It is not safe for concurrent use.
V is stored by value in both the hash map and the B-tree nodes. When V is a large struct, each Set/Delete incurs a value copy inside the B-tree. In that case, prefer using SortedMap[K, *V] to avoid the copy overhead.
SortedMap does not provide Clone(), Keys(), or Values() because the sort key is extracted from V via a caller-supplied function, making generic cloning ambiguous (should the B-tree be rebuilt?), and ordered slices are better obtained via the Ascend/Descend iterators.
func NewSortedMap ¶ added in v0.3.0
func NewSortedMap[K comparable, V any](key func(V) K, less func(V, V) bool) *SortedMap[K, V]
NewSortedMap creates a SortedMap. key extracts the map lookup key from V; less defines the B-tree sort order. Both key and less must not be nil.
func (*SortedMap[K, V]) Ascend ¶ added in v0.3.0
Ascend returns an iterator over all values in ascending order.
func (*SortedMap[K, V]) AscendAfter ¶ added in v0.3.0
AscendAfter returns an iterator over values > pivot in ascending order.
func (*SortedMap[K, V]) AscendFrom ¶ added in v0.3.0
AscendFrom returns an iterator over values >= pivot in ascending order.
func (*SortedMap[K, V]) Clear ¶ added in v0.3.0
func (m *SortedMap[K, V]) Clear()
Clear removes all entries.
func (*SortedMap[K, V]) Delete ¶ added in v0.3.0
Delete removes the entry with the given key. Returns true if the entry existed.
func (*SortedMap[K, V]) Descend ¶ added in v0.3.0
Descend returns an iterator over all values in descending order.
func (*SortedMap[K, V]) DescendBefore ¶ added in v0.3.0
DescendBefore returns an iterator over values < pivot in descending order.
func (*SortedMap[K, V]) DescendFrom ¶ added in v0.3.0
DescendFrom returns an iterator over values <= pivot in descending order.
func (*SortedMap[K, V]) Get ¶ added in v0.3.0
Get returns the value associated with key and whether it was found. If key is not present, it returns the zero value of V and false.
type Stack ¶
type Stack[T any] struct { // contains filtered or unexported fields }
Stack is a LIFO stack backed by a dynamic array. It is not safe for concurrent use.
func NewStackWithCapacity ¶
NewStackWithCapacity creates a Stack with pre-allocated capacity. Panics if n is negative.
func (*Stack[T]) Clear ¶
func (s *Stack[T]) Clear()
Clear removes all elements, keeping the underlying slice storage.
func (*Stack[T]) Peek ¶
Peek returns the top element without removing it. Returns (zero, false) if empty.
Source Files