aboutsummaryrefslogtreecommitdiff
path: root/src/pds.go
diff options
context:
space:
mode:
authorEuAndreh <eu@euandre.org>2025-05-19 05:19:22 -0300
committerEuAndreh <eu@euandre.org>2025-05-19 05:22:59 -0300
commit702955e62a5ad4e46fc851934159cdfd52b6b2ed (patch)
tree530b5a67ea38dfcc2fb323c910fa3658284a8007 /src/pds.go
parentsrc/pds.go: Add leading slash on package comment (diff)
downloadpds-702955e62a5ad4e46fc851934159cdfd52b6b2ed.tar.gz
pds-702955e62a5ad4e46fc851934159cdfd52b6b2ed.tar.xz
src/pds.go: Hoist type definitions, constants and global variables
Diffstat (limited to 'src/pds.go')
-rw-r--r--src/pds.go579
1 files changed, 291 insertions, 288 deletions
diff --git a/src/pds.go b/src/pds.go
index 7eecfa5..7092463 100644
--- a/src/pds.go
+++ b/src/pds.go
@@ -54,16 +54,303 @@ import (
-// Vector is a dense, ordered, indexed collections. They are analogous to slices
-// in Go. They can be updated by appending to the end of the vector, prepending
-// values to the beginning of the vector, or updating existing indexes in the
-// vector.
+
+
+// vectorNode represents either a branch or leaf node in a Vector.
+type vectorNode[T any] interface {
+ depth() uint
+ get(index int) T
+ set(index int, v T, mutable bool) vectorNode[T]
+
+ containsBefore(index int) bool
+ containsAfter(index int) bool
+
+ deleteBefore(index int, mutable bool) vectorNode[T]
+ deleteAfter(index int, mutable bool) vectorNode[T]
+}
+
+/// Vector is a dense, ordered, indexed collections. They are analogous to slices
+/// in Go. They can be updated by appending to the end of the vector, prepending
+/// values to the beginning of the vector, or updating existing indexes in the
+/// vector.
type Vector[T any] struct {
root vectorNode[T] // root node
origin int // offset to zero index element
size int // total number of elements in use
}
+// VectorBuilder represents an efficient builder for creating new Vectors.
+type VectorBuilder[T any] struct {
+ vector *Vector[T] // current state
+}
+
+// vectorBranchNode represents a branch of a Vector tree at a given depth.
+type vectorBranchNode[T any] struct {
+ d uint // depth
+ children [vectorNodeSize]vectorNode[T]
+}
+
+// vectorLeafNode represents a leaf node in a Vector.
+type vectorLeafNode[T any] struct {
+ children [vectorNodeSize]T
+ // bitset with ones at occupied positions, position 0 is the LSB
+ occupied uint32
+}
+
+// VectorIterator represents an ordered iterator over a vector.
+type VectorIterator[T any] struct {
+ vector *Vector[T] // source vector
+ index int // current index position
+
+ stack [32]vectorIteratorElem[T] // search stack
+ depth int // stack depth
+}
+
+// vectorIteratorElem represents the node and it's child index within the stack.
+type vectorIteratorElem[T any] struct {
+ node vectorNode[T]
+ index int
+}
+
+// Map represents an immutable hash map implementation. The map uses a Hasher
+// to generate hashes and check for equality of key values.
+//
+// It is implemented as an Hash Array Mapped Trie.
+type Map[K, V any] struct {
+ size int // total number of key/value pairs
+ root mapNode[K, V] // root node of trie
+ hasher Hasher[K] // hasher implementation
+}
+
+// MapBuilder represents an efficient builder for creating Maps.
+type MapBuilder[K, V any] struct {
+ m *Map[K, V] // current state
+}
+
+// mapNode represents any node in the map tree.
+type mapNode[K, V any] interface {
+ get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool)
+ set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V]
+ delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V]
+}
+
+// mapLeafNode represents a node that stores a single key hash at the leaf of the map tree.
+type mapLeafNode[K, V any] interface {
+ mapNode[K, V]
+ keyHashValue() uint32
+}
+
+// mapArrayNode is a map node that stores key/value pairs in a slice.
+// Entries are stored in insertion order. An array node expands into a bitmap
+// indexed node once a given threshold size is crossed.
+type mapArrayNode[K, V any] struct {
+ entries []mapEntry[K, V]
+}
+
+// mapBitmapIndexedNode represents a map branch node with a variable number of
+// node slots and indexed using a bitmap. Indexes for the node slots are
+// calculated by counting the number of set bits before the target bit using popcount.
+type mapBitmapIndexedNode[K, V any] struct {
+ bitmap uint32
+ nodes []mapNode[K, V]
+}
+
+// mapHashArrayNode is a map branch node that stores nodes in a fixed length
+// array. Child nodes are indexed by their index bit segment for the current depth.
+type mapHashArrayNode[K, V any] struct {
+ count uint // number of set nodes
+ nodes [mapNodeSize]mapNode[K, V] // child node slots, may contain empties
+}
+
+// mapValueNode represents a leaf node with a single key/value pair.
+// A value node can be converted to a hash collision leaf node if a different
+// key with the same keyHash is inserted.
+type mapValueNode[K, V any] struct {
+ keyHash uint32
+ key K
+ value V
+}
+
+// mapHashCollisionNode represents a leaf node that contains two or more key/value
+// pairs with the same key hash. Single pairs for a hash are stored as value nodes.
+type mapHashCollisionNode[K, V any] struct {
+ keyHash uint32 // key hash for all entries
+ entries []mapEntry[K, V]
+}
+
+// mapEntry represents a single key/value pair.
+type mapEntry[K, V any] struct {
+ key K
+ value V
+}
+
+// MapIterator represents an iterator over a map's key/value pairs. Although
+// map keys are not sorted, the iterator's order is deterministic.
+type MapIterator[K, V any] struct {
+ m *Map[K, V] // source map
+
+ stack [32]mapIteratorElem[K, V] // search stack
+ depth int // stack depth
+}
+
+// mapIteratorElem represents a node/index pair in the MapIterator stack.
+type mapIteratorElem[K, V any] struct {
+ node mapNode[K, V]
+ index int
+}
+
+// SortedMap represents a map of key/value pairs sorted by key. The sort order
+// is determined by the Comparer used by the map.
+//
+// This map is implemented as a B+tree.
+type SortedMap[K, V any] struct {
+ size int // total number of key/value pairs
+ root sortedMapNode[K, V] // root of b+tree
+ comparer Comparer[K]
+}
+
+// SortedMapBuilder represents an efficient builder for creating sorted maps.
+type SortedMapBuilder[K, V any] struct {
+ m *SortedMap[K, V] // current state
+}
+
+// sortedMapNode represents a branch or leaf node in the sorted map.
+type sortedMapNode[K, V any] interface {
+ minKey() K
+ indexOf(key K, c Comparer[K]) int
+ get(key K, c Comparer[K]) (value V, ok bool)
+ set(key K, value V, c Comparer[K], mutable bool, resized *bool) (sortedMapNode[K, V], sortedMapNode[K, V])
+ delete(key K, c Comparer[K], mutable bool, resized *bool) sortedMapNode[K, V]
+}
+
+// sortedMapBranchNode represents a branch in the sorted map.
+type sortedMapBranchNode[K, V any] struct {
+ elems []sortedMapBranchElem[K, V]
+}
+
+type sortedMapBranchElem[K, V any] struct {
+ key K
+ node sortedMapNode[K, V]
+}
+
+// sortedMapLeafNode represents a leaf node in the sorted map.
+type sortedMapLeafNode[K, V any] struct {
+ entries []mapEntry[K, V]
+}
+
+// SortedMapIterator represents an iterator over a sorted map.
+// Iteration can occur in natural or reverse order based on use of Next() or Prev().
+type SortedMapIterator[K, V any] struct {
+ m *SortedMap[K, V] // source map
+
+ stack [32]sortedMapIteratorElem[K, V] // search stack
+ depth int // stack depth
+}
+
+// sortedMapIteratorElem represents node/index pair in the SortedMapIterator stack.
+type sortedMapIteratorElem[K, V any] struct {
+ node sortedMapNode[K, V]
+ index int
+}
+
+// Hasher hashes keys and checks them for equality.
+type Hasher[K any] interface {
+ // Computes a hash for key.
+ Hash(key K) uint32
+
+ // Returns true if a and b are equal.
+ Equal(a, b K) bool
+}
+
+// reflectIntHasher implements a reflection-based Hasher for keys.
+type reflectHasher[K any] struct{}
+
+// defaultHasher implements Hasher.
+type defaultHasher[K any] struct{}
+
+// Comparer allows the comparison of two keys for the purpose of sorting.
+type Comparer[K any] interface {
+ // Returns -1 if a is less than b, returns 1 if a is greater than b,
+ // and returns 0 if a is equal to b.
+ Compare(a, b K) int
+}
+
+// defaultComparer compares two values (int-ish and string-ish types are supported). Implements Comparer.
+type defaultComparer[K any] struct{}
+
+// reflectIntComparer compares two values using reflection. Implements Comparer.
+type reflectComparer[K any] struct{}
+
+// Set represents a collection of unique values. The set uses a Hasher
+// to generate hashes and check for equality of key values.
+//
+// Internally, the Set stores values as keys of a Map[T,struct{}]
+type Set[T any] struct {
+ m *Map[T, struct{}]
+}
+
+// SetIterator represents an iterator over a set.
+// Iteration can occur in natural or reverse order based on use of Next() or Prev().
+type SetIterator[T any] struct {
+ mi *MapIterator[T, struct{}]
+}
+
+type SetBuilder[T any] struct {
+ s Set[T]
+}
+
+type SortedSet[T any] struct {
+ m *SortedMap[T, struct{}]
+}
+
+// SortedSetIterator represents an iterator over a sorted set.
+// Iteration can occur in natural or reverse order based on use of Next() or Prev().
+type SortedSetIterator[T any] struct {
+ mi *SortedMapIterator[T, struct{}]
+}
+
+type SortedSetBuilder[T any] struct {
+ s *SortedSet[T]
+}
+
+
+
+const (
+ /// Constants for bit shifts used for levels in the Vector trie.
+ vectorNodeBits = 5
+ vectorNodeSize = 1 << vectorNodeBits
+ vectorNodeMask = vectorNodeSize - 1
+
+ /// Size thresholds for each type of branch node.
+ maxArrayMapSize = 8
+ maxBitmapIndexedSize = 16
+
+ /// Segment bit shifts within the map tree.
+ mapNodeBits = 5
+ mapNodeSize = 1 << mapNodeBits
+ mapNodeMask = mapNodeSize - 1
+
+ /// Sorted map child node limit size.
+ sortedMapNodeSize = 32
+)
+
+
+var (
+ _ mapNode[string, any] = (*mapArrayNode[string, any])(nil)
+ _ mapNode[string, any] = (*mapBitmapIndexedNode[string, any])(nil)
+ _ mapNode[string, any] = (*mapHashArrayNode[string, any])(nil)
+ _ mapNode[string, any] = (*mapValueNode[string, any])(nil)
+ _ mapNode[string, any] = (*mapHashCollisionNode[string, any])(nil)
+
+ _ mapLeafNode[string, any] = (*mapValueNode[string, any])(nil)
+ _ mapLeafNode[string, any] = (*mapHashCollisionNode[string, any])(nil)
+
+ _ sortedMapNode[string, any] = (*sortedMapBranchNode[string, any])(nil)
+ _ sortedMapNode[string, any] = (*sortedMapLeafNode[string, any])(nil)
+)
+
+
+
// NewVector returns a new empty instance of Vector.
func NewVector[T any](values ...T) *Vector[T] {
l := &Vector[T]{
@@ -256,11 +543,6 @@ func (l *Vector[T]) Iterator() *VectorIterator[T] {
return itr
}
-// VectorBuilder represents an efficient builder for creating new Vectors.
-type VectorBuilder[T any] struct {
- vector *Vector[T] // current state
-}
-
// NewVectorBuilder returns a new instance of VectorBuilder.
func NewVectorBuilder[T any]() *VectorBuilder[T] {
return &VectorBuilder[T]{vector: NewVector[T]()}
@@ -322,26 +604,6 @@ func (b *VectorBuilder[T]) Iterator() *VectorIterator[T] {
return b.vector.Iterator()
}
-// Constants for bit shifts used for levels in the Vector trie.
-const (
- vectorNodeBits = 5
- vectorNodeSize = 1 << vectorNodeBits
- vectorNodeMask = vectorNodeSize - 1
-)
-
-// vectorNode represents either a branch or leaf node in a Vector.
-type vectorNode[T any] interface {
- depth() uint
- get(index int) T
- set(index int, v T, mutable bool) vectorNode[T]
-
- containsBefore(index int) bool
- containsAfter(index int) bool
-
- deleteBefore(index int, mutable bool) vectorNode[T]
- deleteAfter(index int, mutable bool) vectorNode[T]
-}
-
// newVectorNode returns a leaf node for depth zero, otherwise returns a branch
// node.
func newVectorNode[T any](depth uint) vectorNode[T] {
@@ -351,12 +613,6 @@ func newVectorNode[T any](depth uint) vectorNode[T] {
return &vectorBranchNode[T]{d: depth}
}
-// vectorBranchNode represents a branch of a Vector tree at a given depth.
-type vectorBranchNode[T any] struct {
- d uint // depth
- children [vectorNodeSize]vectorNode[T]
-}
-
// depth returns the depth of this branch node from the leaf.
func (n *vectorBranchNode[T]) depth() uint { return n.d }
@@ -480,13 +736,6 @@ func (n *vectorBranchNode[T]) deleteAfter(index int, mutable bool) vectorNode[T]
return other
}
-// vectorLeafNode represents a leaf node in a Vector.
-type vectorLeafNode[T any] struct {
- children [vectorNodeSize]T
- // bitset with ones at occupied positions, position 0 is the LSB
- occupied uint32
-}
-
// depth always returns 0 for leaf nodes.
func (n *vectorLeafNode[T]) depth() uint { return 0 }
@@ -569,15 +818,6 @@ func (n *vectorLeafNode[T]) deleteAfter(index int, mutable bool) vectorNode[T] {
return other
}
-// VectorIterator represents an ordered iterator over a vector.
-type VectorIterator[T any] struct {
- vector *Vector[T] // source vector
- index int // current index position
-
- stack [32]vectorIteratorElem[T] // search stack
- depth int // stack depth
-}
-
// Done returns true if no more elements remain in the iterator.
func (itr *VectorIterator[T]) Done() bool {
return itr.index < 0 || itr.index >= itr.vector.Len()
@@ -692,35 +932,6 @@ func (itr *VectorIterator[T]) seek(index int) {
}
}
-// vectorIteratorElem represents the node and it's child index within the stack.
-type vectorIteratorElem[T any] struct {
- node vectorNode[T]
- index int
-}
-
-// Size thresholds for each type of branch node.
-const (
- maxArrayMapSize = 8
- maxBitmapIndexedSize = 16
-)
-
-// Segment bit shifts within the map tree.
-const (
- mapNodeBits = 5
- mapNodeSize = 1 << mapNodeBits
- mapNodeMask = mapNodeSize - 1
-)
-
-// Map represents an immutable hash map implementation. The map uses a Hasher
-// to generate hashes and check for equality of key values.
-//
-// It is implemented as an Hash Array Mapped Trie.
-type Map[K, V any] struct {
- size int // total number of key/value pairs
- root mapNode[K, V] // root node of trie
- hasher Hasher[K] // hasher implementation
-}
-
// NewMap returns a new instance of Map. If hasher is nil, a default hasher
// implementation will automatically be chosen based on the first key added.
// Default hasher implementations only exist for int, string, and byte slice types.
@@ -846,11 +1057,6 @@ func (m *Map[K, V]) Iterator() *MapIterator[K, V] {
return itr
}
-// MapBuilder represents an efficient builder for creating Maps.
-type MapBuilder[K, V any] struct {
- m *Map[K, V] // current state
-}
-
// NewMapBuilder returns a new instance of MapBuilder.
func NewMapBuilder[K, V any](hasher Hasher[K]) *MapBuilder[K, V] {
return &MapBuilder[K, V]{m: NewMap[K, V](hasher)}
@@ -895,35 +1101,6 @@ func (b *MapBuilder[K, V]) Iterator() *MapIterator[K, V] {
return b.m.Iterator()
}
-// mapNode represents any node in the map tree.
-type mapNode[K, V any] interface {
- get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool)
- set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V]
- delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V]
-}
-
-var _ mapNode[string, any] = (*mapArrayNode[string, any])(nil)
-var _ mapNode[string, any] = (*mapBitmapIndexedNode[string, any])(nil)
-var _ mapNode[string, any] = (*mapHashArrayNode[string, any])(nil)
-var _ mapNode[string, any] = (*mapValueNode[string, any])(nil)
-var _ mapNode[string, any] = (*mapHashCollisionNode[string, any])(nil)
-
-// mapLeafNode represents a node that stores a single key hash at the leaf of the map tree.
-type mapLeafNode[K, V any] interface {
- mapNode[K, V]
- keyHashValue() uint32
-}
-
-var _ mapLeafNode[string, any] = (*mapValueNode[string, any])(nil)
-var _ mapLeafNode[string, any] = (*mapHashCollisionNode[string, any])(nil)
-
-// mapArrayNode is a map node that stores key/value pairs in a slice.
-// Entries are stored in insertion order. An array node expands into a bitmap
-// indexed node once a given threshold size is crossed.
-type mapArrayNode[K, V any] struct {
- entries []mapEntry[K, V]
-}
-
// indexOf returns the entry index of the given key. Returns -1 if key not found.
func (n *mapArrayNode[K, V]) indexOf(key K, h Hasher[K]) int {
for i := range n.entries {
@@ -1019,14 +1196,6 @@ func (n *mapArrayNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[
return other
}
-// mapBitmapIndexedNode represents a map branch node with a variable number of
-// node slots and indexed using a bitmap. Indexes for the node slots are
-// calculated by counting the number of set bits before the target bit using popcount.
-type mapBitmapIndexedNode[K, V any] struct {
- bitmap uint32
- nodes []mapNode[K, V]
-}
-
// get returns the value for the given key.
func (n *mapBitmapIndexedNode[K, V]) get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) {
bit := uint32(1) << ((keyHash >> shift) & mapNodeMask)
@@ -1166,13 +1335,6 @@ func (n *mapBitmapIndexedNode[K, V]) delete(key K, shift uint, keyHash uint32, h
return other
}
-// mapHashArrayNode is a map branch node that stores nodes in a fixed length
-// array. Child nodes are indexed by their index bit segment for the current depth.
-type mapHashArrayNode[K, V any] struct {
- count uint // number of set nodes
- nodes [mapNodeSize]mapNode[K, V] // child node slots, may contain empties
-}
-
// clone returns a shallow copy of n.
func (n *mapHashArrayNode[K, V]) clone() *mapHashArrayNode[K, V] {
other := *n
@@ -1261,15 +1423,6 @@ func (n *mapHashArrayNode[K, V]) delete(key K, shift uint, keyHash uint32, h Has
return other
}
-// mapValueNode represents a leaf node with a single key/value pair.
-// A value node can be converted to a hash collision leaf node if a different
-// key with the same keyHash is inserted.
-type mapValueNode[K, V any] struct {
- keyHash uint32
- key K
- value V
-}
-
// newMapValueNode returns a new instance of mapValueNode.
func newMapValueNode[K, V any](keyHash uint32, key K, value V) *mapValueNode[K, V] {
return &mapValueNode[K, V]{
@@ -1334,13 +1487,6 @@ func (n *mapValueNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[
return nil
}
-// mapHashCollisionNode represents a leaf node that contains two or more key/value
-// pairs with the same key hash. Single pairs for a hash are stored as value nodes.
-type mapHashCollisionNode[K, V any] struct {
- keyHash uint32 // key hash for all entries
- entries []mapEntry[K, V]
-}
-
// keyHashValue returns the key hash for all entries on the node.
func (n *mapHashCollisionNode[K, V]) keyHashValue() uint32 {
return n.keyHash
@@ -1460,21 +1606,6 @@ func mergeIntoNode[K, V any](node mapLeafNode[K, V], shift uint, keyHash uint32,
return other
}
-// mapEntry represents a single key/value pair.
-type mapEntry[K, V any] struct {
- key K
- value V
-}
-
-// MapIterator represents an iterator over a map's key/value pairs. Although
-// map keys are not sorted, the iterator's order is deterministic.
-type MapIterator[K, V any] struct {
- m *Map[K, V] // source map
-
- stack [32]mapIteratorElem[K, V] // search stack
- depth int // stack depth
-}
-
// Done returns true if no more elements remain in the iterator.
func (itr *MapIterator[K, V]) Done() bool {
return itr.depth == -1
@@ -1591,27 +1722,6 @@ func (itr *MapIterator[K, V]) first() {
}
}
-// mapIteratorElem represents a node/index pair in the MapIterator stack.
-type mapIteratorElem[K, V any] struct {
- node mapNode[K, V]
- index int
-}
-
-// Sorted map child node limit size.
-const (
- sortedMapNodeSize = 32
-)
-
-// SortedMap represents a map of key/value pairs sorted by key. The sort order
-// is determined by the Comparer used by the map.
-//
-// This map is implemented as a B+tree.
-type SortedMap[K, V any] struct {
- size int // total number of key/value pairs
- root sortedMapNode[K, V] // root of b+tree
- comparer Comparer[K]
-}
-
// NewSortedMap returns a new instance of SortedMap. If comparer is nil then
// a default comparer is set after the first key is inserted. Default comparers
// exist for int, string, and byte slice keys.
@@ -1737,11 +1847,6 @@ func (m *SortedMap[K, V]) Iterator() *SortedMapIterator[K, V] {
return itr
}
-// SortedMapBuilder represents an efficient builder for creating sorted maps.
-type SortedMapBuilder[K, V any] struct {
- m *SortedMap[K, V] // current state
-}
-
// NewSortedMapBuilder returns a new instance of SortedMapBuilder.
func NewSortedMapBuilder[K, V any](comparer Comparer[K]) *SortedMapBuilder[K, V] {
return &SortedMapBuilder[K, V]{m: NewSortedMap[K, V](comparer)}
@@ -1786,23 +1891,6 @@ func (b *SortedMapBuilder[K, V]) Iterator() *SortedMapIterator[K, V] {
return b.m.Iterator()
}
-// sortedMapNode represents a branch or leaf node in the sorted map.
-type sortedMapNode[K, V any] interface {
- minKey() K
- indexOf(key K, c Comparer[K]) int
- get(key K, c Comparer[K]) (value V, ok bool)
- set(key K, value V, c Comparer[K], mutable bool, resized *bool) (sortedMapNode[K, V], sortedMapNode[K, V])
- delete(key K, c Comparer[K], mutable bool, resized *bool) sortedMapNode[K, V]
-}
-
-var _ sortedMapNode[string, any] = (*sortedMapBranchNode[string, any])(nil)
-var _ sortedMapNode[string, any] = (*sortedMapLeafNode[string, any])(nil)
-
-// sortedMapBranchNode represents a branch in the sorted map.
-type sortedMapBranchNode[K, V any] struct {
- elems []sortedMapBranchElem[K, V]
-}
-
// newSortedMapBranchNode returns a new branch node with the given child nodes.
func newSortedMapBranchNode[K, V any](children ...sortedMapNode[K, V]) *sortedMapBranchNode[K, V] {
// Fetch min keys for every child.
@@ -1947,16 +2035,6 @@ func (n *sortedMapBranchNode[K, V]) delete(key K, c Comparer[K], mutable bool, r
return other
}
-type sortedMapBranchElem[K, V any] struct {
- key K
- node sortedMapNode[K, V]
-}
-
-// sortedMapLeafNode represents a leaf node in the sorted map.
-type sortedMapLeafNode[K, V any] struct {
- entries []mapEntry[K, V]
-}
-
// minKey returns the first key stored in this node.
func (n *sortedMapLeafNode[K, V]) minKey() K {
return n.entries[0].key
@@ -2066,15 +2144,6 @@ func (n *sortedMapLeafNode[K, V]) delete(key K, c Comparer[K], mutable bool, res
return other
}
-// SortedMapIterator represents an iterator over a sorted map.
-// Iteration can occur in natural or reverse order based on use of Next() or Prev().
-type SortedMapIterator[K, V any] struct {
- m *SortedMap[K, V] // source map
-
- stack [32]sortedMapIteratorElem[K, V] // search stack
- depth int // stack depth
-}
-
// Done returns true if no more key/value pairs remain in the iterator.
func (itr *SortedMapIterator[K, V]) Done() bool {
return itr.depth == -1
@@ -2255,21 +2324,6 @@ func (itr *SortedMapIterator[K, V]) seek(key K) {
}
}
-// sortedMapIteratorElem represents node/index pair in the SortedMapIterator stack.
-type sortedMapIteratorElem[K, V any] struct {
- node sortedMapNode[K, V]
- index int
-}
-
-// Hasher hashes keys and checks them for equality.
-type Hasher[K any] interface {
- // Computes a hash for key.
- Hash(key K) uint32
-
- // Returns true if a and b are equal.
- Equal(a, b K) bool
-}
-
// NewHasher returns the built-in hasher for a given key type.
func NewHasher[K any](key K) Hasher[K] {
// Attempt to use non-reflection based hasher first.
@@ -2299,9 +2353,6 @@ func hashString(value string) uint32 {
return hash
}
-// reflectIntHasher implements a reflection-based Hasher for keys.
-type reflectHasher[K any] struct{}
-
// Hash returns a hash for key.
func (h *reflectHasher[K]) Hash(key K) uint32 {
switch reflect.TypeOf(key).Kind() {
@@ -2345,9 +2396,6 @@ func hashUint64(value uint64) uint32 {
return uint32(hash)
}
-// defaultHasher implements Hasher.
-type defaultHasher[K any] struct{}
-
// Hash returns a hash for key.
func (h *defaultHasher[K]) Hash(key K) uint32 {
switch x := (any(key)).(type) {
@@ -2385,13 +2433,6 @@ func (h *defaultHasher[K]) Equal(a, b K) bool {
return any(a) == any(b)
}
-// Comparer allows the comparison of two keys for the purpose of sorting.
-type Comparer[K any] interface {
- // Returns -1 if a is less than b, returns 1 if a is greater than b,
- // and returns 0 if a is equal to b.
- Compare(a, b K) int
-}
-
// NewComparer returns the built-in comparer for a given key type.
// Note that only int-ish and string-ish types are supported, despite the 'comparable' constraint.
// Attempts to use other types will result in a panic - users should define their own Comparers for these cases.
@@ -2412,9 +2453,6 @@ func NewComparer[K any](key K) Comparer[K] {
panic(fmt.Sprintf("immutable.NewComparer: must set comparer for %T type", key))
}
-// defaultComparer compares two values (int-ish and string-ish types are supported). Implements Comparer.
-type defaultComparer[K any] struct{}
-
// Compare returns -1 if a is less than b, returns 1 if a is greater than b, and
// returns 0 if a is equal to b. Panic if a or b is not a string or int* type
func (c *defaultComparer[K]) Compare(i K, j K) int {
@@ -2458,9 +2496,6 @@ func defaultCompare[K cmp.Ordered](i, j K) int {
return 0
}
-// reflectIntComparer compares two values using reflection. Implements Comparer.
-type reflectComparer[K any] struct{}
-
// Compare returns -1 if a is less than b, returns 1 if a is greater than b, and
// returns 0 if a is equal to b. Panic if a or b is not an int-ish or string-ish type.
func (c *reflectComparer[K]) Compare(a, b K) int {
@@ -2491,14 +2526,6 @@ func assert(condition bool, message string) {
}
}
-// Set represents a collection of unique values. The set uses a Hasher
-// to generate hashes and check for equality of key values.
-//
-// Internally, the Set stores values as keys of a Map[T,struct{}]
-type Set[T any] struct {
- m *Map[T, struct{}]
-}
-
// NewSet returns a new instance of Set.
//
// If hasher is nil, a default hasher implementation will automatically be chosen based on the first key added.
@@ -2553,12 +2580,6 @@ func (s Set[T]) Iterator() *SetIterator[T] {
return itr
}
-// SetIterator represents an iterator over a set.
-// Iteration can occur in natural or reverse order based on use of Next() or Prev().
-type SetIterator[T any] struct {
- mi *MapIterator[T, struct{}]
-}
-
// Done returns true if no more values remain in the iterator.
func (itr *SetIterator[T]) Done() bool {
return itr.mi.Done()
@@ -2575,10 +2596,6 @@ func (itr *SetIterator[T]) Next() (val T, ok bool) {
return
}
-type SetBuilder[T any] struct {
- s Set[T]
-}
-
func NewSetBuilder[T any](hasher Hasher[T]) *SetBuilder[T] {
return &SetBuilder[T]{s: NewSet(hasher)}
}
@@ -2599,10 +2616,6 @@ func (s SetBuilder[T]) Len() int {
return s.s.Len()
}
-type SortedSet[T any] struct {
- m *SortedMap[T, struct{}]
-}
-
// NewSortedSet returns a new instance of SortedSet.
//
// If comparer is nil then
@@ -2658,12 +2671,6 @@ func (s SortedSet[T]) Iterator() *SortedSetIterator[T] {
return itr
}
-// SortedSetIterator represents an iterator over a sorted set.
-// Iteration can occur in natural or reverse order based on use of Next() or Prev().
-type SortedSetIterator[T any] struct {
- mi *SortedMapIterator[T, struct{}]
-}
-
// Done returns true if no more values remain in the iterator.
func (itr *SortedSetIterator[T]) Done() bool {
return itr.mi.Done()
@@ -2699,10 +2706,6 @@ func (itr *SortedSetIterator[T]) Seek(val T) {
itr.mi.Seek(val)
}
-type SortedSetBuilder[T any] struct {
- s *SortedSet[T]
-}
-
func NewSortedSetBuilder[T any](comparer Comparer[T]) *SortedSetBuilder[T] {
s := NewSortedSet(comparer)
return &SortedSetBuilder[T]{s: &s}