diff options
author | EuAndreh <eu@euandre.org> | 2025-05-19 05:19:22 -0300 |
---|---|---|
committer | EuAndreh <eu@euandre.org> | 2025-05-19 05:22:59 -0300 |
commit | 702955e62a5ad4e46fc851934159cdfd52b6b2ed (patch) | |
tree | 530b5a67ea38dfcc2fb323c910fa3658284a8007 /src/pds.go | |
parent | src/pds.go: Add leading slash on package comment (diff) | |
download | pds-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.go | 579 |
1 files changed, 291 insertions, 288 deletions
@@ -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} |