src/pds.go: Hoist type definitions, constants and global variables

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}