README
¶
Immutable 
A collection of fast, general-purpose immutable data structures.
This package has been used in production at multiple companies, is stable, and is probably feature-complete.
Data Structures
All data structures are fully persistent and safe for concurrent use. Unless otherwise noted, time complexities are worst-case (not amortized).
- Stack: Last in, first out. Constant time operations.
- Queue: First in, first out. Constant time operations.
- Ordered Map: Map with in-order iteration. Logarithmic time operations.
Documentation
¶
Index ¶
- type OrderedMap
- func (m *OrderedMap[K, V]) Delete(key K) *OrderedMap[K, V]
- func (m *OrderedMap[K, V]) Empty() bool
- func (m *OrderedMap[K, V]) Get(key K) (v V, exists bool)
- func (m *OrderedMap[K, V]) Len() int
- func (m *OrderedMap[K, V]) Max() *OrderedMapElement[K, V]
- func (m *OrderedMap[K, V]) MaxBefore(key K) *OrderedMapElement[K, V]
- func (m *OrderedMap[K, V]) Min() *OrderedMapElement[K, V]
- func (m *OrderedMap[K, V]) MinAfter(key K) *OrderedMapElement[K, V]
- func (m *OrderedMap[K, V]) Set(key K, value V) *OrderedMap[K, V]
- type OrderedMapElement
- func (e *OrderedMapElement[K, V]) CountGreater() int
- func (e *OrderedMapElement[K, V]) CountLess() int
- func (e *OrderedMapElement[K, V]) Key() K
- func (e *OrderedMapElement[K, V]) Next() *OrderedMapElement[K, V]
- func (e *OrderedMapElement[K, V]) Prev() *OrderedMapElement[K, V]
- func (e *OrderedMapElement[K, V]) Value() V
- type Queue
- type Stack
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type OrderedMap ¶
type OrderedMap[K constraints.Ordered, V any] struct { // contains filtered or unexported fields }
OrderedMap implements an ordered map.
Nil and the zero value for OrderedMap are both empty maps.
func (*OrderedMap[K, V]) Delete ¶
func (m *OrderedMap[K, V]) Delete(key K) *OrderedMap[K, V]
Delete removes a key from the map.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) Empty ¶
func (m *OrderedMap[K, V]) Empty() bool
Empty returns true if the map is empty.
Complexity: O(1) worst-case
func (*OrderedMap[K, V]) Get ¶
func (m *OrderedMap[K, V]) Get(key K) (v V, exists bool)
Get returns the value associated with the given key if set.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) Len ¶
func (m *OrderedMap[K, V]) Len() int
Len returns the number of elements in the map.
Complexity: O(1) worst-case
func (*OrderedMap[K, V]) Max ¶
func (m *OrderedMap[K, V]) Max() *OrderedMapElement[K, V]
Max returns the maximum element in the map.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) MaxBefore ¶
func (m *OrderedMap[K, V]) MaxBefore(key K) *OrderedMapElement[K, V]
MaxBefore returns the maximum element in the map that is less than the given key.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) Min ¶
func (m *OrderedMap[K, V]) Min() *OrderedMapElement[K, V]
Min returns the minimum element in the map.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) MinAfter ¶
func (m *OrderedMap[K, V]) MinAfter(key K) *OrderedMapElement[K, V]
MinAfter returns the minimum element in the map that is greater than the given key.
Complexity: O(log n) worst-case
func (*OrderedMap[K, V]) Set ¶
func (m *OrderedMap[K, V]) Set(key K, value V) *OrderedMap[K, V]
Set associates a value with the given key.
Only the built-in types may be used as keys. Once a value is set within a map, all subsequent operations must use the same key type.
Complexity: O(log n) worst-case
type OrderedMapElement ¶
type OrderedMapElement[K constraints.Ordered, V any] struct { // contains filtered or unexported fields }
OrderedMapElement represents a key-value pair and can be used to iterate over elements in a map.
func (*OrderedMapElement[K, V]) CountGreater ¶
func (e *OrderedMapElement[K, V]) CountGreater() int
CountGreater returns the number of elements that are greater than this element.
Complexity: O(log n) worst-case
func (*OrderedMapElement[K, V]) CountLess ¶
func (e *OrderedMapElement[K, V]) CountLess() int
CountLess returns the number of elements that are less than this element.
Complexity: O(log n) worst-case
func (*OrderedMapElement[K, V]) Key ¶
func (e *OrderedMapElement[K, V]) Key() K
Key returns the key of the represented element.
func (*OrderedMapElement[K, V]) Next ¶
func (e *OrderedMapElement[K, V]) Next() *OrderedMapElement[K, V]
Next returns the next element in the map.
Complexity: O(log n) worst-case, amortized O(1) if iterating over the entire map
func (*OrderedMapElement[K, V]) Prev ¶
func (e *OrderedMapElement[K, V]) Prev() *OrderedMapElement[K, V]
Prev returns the previous element in the map.
Complexity: O(log n) worst-case, amortized O(1) if iterating over an entire map
func (*OrderedMapElement[K, V]) Value ¶
func (e *OrderedMapElement[K, V]) Value() V
Value returns the value of the represented element.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
Queue implements a first in, first out container.
Nil and the zero value for Queue are both empty queues.
func (*Queue[T]) Front ¶
func (q *Queue[T]) Front() T
Front returns the item at the front of the queue.
Complexity: O(1) worst-case
type Stack ¶
type Stack[T any] struct { // contains filtered or unexported fields }
Stack implements a last in, first out container.
Nil and the zero value for Stack are both empty stacks.
func (*Stack[T]) Peek ¶
func (s *Stack[T]) Peek() T
Peek returns the top item on the stack.
Complexity: O(1) worst-case
Source Files