diff options
Diffstat (limited to 'immutable.go')
| -rw-r--r-- | immutable.go | 1312 |
1 files changed, 489 insertions, 823 deletions
diff --git a/immutable.go b/immutable.go index c8da568..b189612 100644 --- a/immutable.go +++ b/immutable.go @@ -42,50 +42,51 @@ package immutable import ( - "bytes" "fmt" "math/bits" "reflect" "sort" "strings" + + "golang.org/x/exp/constraints" ) // List is a dense, ordered, indexed collections. They are analogous to slices // in Go. They can be updated by appending to the end of the list, prepending // values to the beginning of the list, or updating existing indexes in the // list. -type List struct { - root listNode // root node - origin int // offset to zero index element - size int // total number of elements in use +type List[T comparable] struct { + root listNode[T] // root node + origin int // offset to zero index element + size int // total number of elements in use } // NewList returns a new empty instance of List. -func NewList() *List { - return &List{ - root: &listLeafNode{}, +func NewList[T comparable]() *List[T] { + return &List[T]{ + root: &listLeafNode[T]{}, } } // clone returns a copy of the list. -func (l *List) clone() *List { +func (l *List[T]) clone() *List[T] { other := *l return &other } // Len returns the number of elements in the list. -func (l *List) Len() int { +func (l *List[T]) Len() int { return l.size } // cap returns the total number of possible elements for the current depth. -func (l *List) cap() int { +func (l *List[T]) cap() int { return 1 << (l.root.depth() * listNodeBits) } // Get returns the value at the given index. Similar to slices, this method will // panic if index is below zero or is greater than or equal to the list size. -func (l *List) Get(index int) interface{} { +func (l *List[T]) Get(index int) T { if index < 0 || index >= l.size { panic(fmt.Sprintf("immutable.List.Get: index %d out of bounds", index)) } @@ -95,11 +96,11 @@ func (l *List) Get(index int) interface{} { // Set returns a new list with value set at index. Similar to slices, this // method will panic if index is below zero or if the index is greater than // or equal to the list size. -func (l *List) Set(index int, value interface{}) *List { +func (l *List[T]) Set(index int, value T) *List[T] { return l.set(index, value, false) } -func (l *List) set(index int, value interface{}, mutable bool) *List { +func (l *List[T]) set(index int, value T, mutable bool) *List[T] { if index < 0 || index >= l.size { panic(fmt.Sprintf("immutable.List.Set: index %d out of bounds", index)) } @@ -112,11 +113,11 @@ func (l *List) set(index int, value interface{}, mutable bool) *List { } // Append returns a new list with value added to the end of the list. -func (l *List) Append(value interface{}) *List { +func (l *List[T]) Append(value T) *List[T] { return l.append(value, false) } -func (l *List) append(value interface{}, mutable bool) *List { +func (l *List[T]) append(value T, mutable bool) *List[T] { other := l if !mutable { other = l.clone() @@ -124,7 +125,7 @@ func (l *List) append(value interface{}, mutable bool) *List { // Expand list to the right if no slots remain. if other.size+other.origin >= l.cap() { - newRoot := &listBranchNode{d: other.root.depth() + 1} + newRoot := &listBranchNode[T]{d: other.root.depth() + 1} newRoot.children[0] = other.root other.root = newRoot } @@ -136,11 +137,11 @@ func (l *List) append(value interface{}, mutable bool) *List { } // Prepend returns a new list with value added to the beginning of the list. -func (l *List) Prepend(value interface{}) *List { +func (l *List[T]) Prepend(value T) *List[T] { return l.prepend(value, false) } -func (l *List) prepend(value interface{}, mutable bool) *List { +func (l *List[T]) prepend(value T, mutable bool) *List[T] { other := l if !mutable { other = l.clone() @@ -148,7 +149,7 @@ func (l *List) prepend(value interface{}, mutable bool) *List { // Expand list to the left if no slots remain. if other.origin == 0 { - newRoot := &listBranchNode{d: other.root.depth() + 1} + newRoot := &listBranchNode[T]{d: other.root.depth() + 1} newRoot.children[listNodeSize-1] = other.root other.root = newRoot other.origin += (listNodeSize - 1) << (other.root.depth() * listNodeBits) @@ -168,11 +169,11 @@ func (l *List) prepend(value interface{}, mutable bool) *List { // // Unlike Go slices, references to inaccessible elements will be automatically // removed so they can be garbage collected. -func (l *List) Slice(start, end int) *List { +func (l *List[T]) Slice(start, end int) *List[T] { return l.slice(start, end, false) } -func (l *List) slice(start, end int, mutable bool) *List { +func (l *List[T]) slice(start, end int, mutable bool) *List[T] { // Panics similar to Go slices. if start < 0 || start > l.size { panic(fmt.Sprintf("immutable.List.Slice: start index %d out of bounds", start)) @@ -207,7 +208,7 @@ func (l *List) slice(start, end int, mutable bool) *List { // Replace the current root with the single child & update origin offset. other.origin -= i << (other.root.depth() * listNodeBits) - other.root = other.root.(*listBranchNode).children[i] + other.root = other.root.(*listBranchNode[T]).children[i] } // Ensure all references are removed before start & after end. @@ -218,25 +219,25 @@ func (l *List) slice(start, end int, mutable bool) *List { } // Iterator returns a new iterator for this list positioned at the first index. -func (l *List) Iterator() *ListIterator { - itr := &ListIterator{list: l} +func (l *List[T]) Iterator() *ListIterator[T] { + itr := &ListIterator[T]{list: l} itr.First() return itr } // ListBuilder represents an efficient builder for creating new Lists. -type ListBuilder struct { - list *List // current state +type ListBuilder[T comparable] struct { + list *List[T] // current state } // NewListBuilder returns a new instance of ListBuilder. -func NewListBuilder() *ListBuilder { - return &ListBuilder{list: NewList()} +func NewListBuilder[T comparable]() *ListBuilder[T] { + return &ListBuilder[T]{list: NewList[T]()} } // List returns the current copy of the list. // The builder should not be used again after the list after this call. -func (b *ListBuilder) List() *List { +func (b *ListBuilder[T]) List() *List[T] { assert(b.list != nil, "immutable.ListBuilder.List(): duplicate call to fetch list") list := b.list b.list = nil @@ -244,14 +245,14 @@ func (b *ListBuilder) List() *List { } // Len returns the number of elements in the underlying list. -func (b *ListBuilder) Len() int { +func (b *ListBuilder[T]) Len() int { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") return b.list.Len() } // Get returns the value at the given index. Similar to slices, this method will // panic if index is below zero or is greater than or equal to the list size. -func (b *ListBuilder) Get(index int) interface{} { +func (b *ListBuilder[T]) Get(index int) T { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") return b.list.Get(index) } @@ -259,32 +260,32 @@ func (b *ListBuilder) Get(index int) interface{} { // Set updates the value at the given index. Similar to slices, this method will // panic if index is below zero or if the index is greater than or equal to the // list size. -func (b *ListBuilder) Set(index int, value interface{}) { +func (b *ListBuilder[T]) Set(index int, value T) { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") b.list = b.list.set(index, value, true) } // Append adds value to the end of the list. -func (b *ListBuilder) Append(value interface{}) { +func (b *ListBuilder[T]) Append(value T) { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") b.list = b.list.append(value, true) } // Prepend adds value to the beginning of the list. -func (b *ListBuilder) Prepend(value interface{}) { +func (b *ListBuilder[T]) Prepend(value T) { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") b.list = b.list.prepend(value, true) } // Slice updates the list with a sublist of elements between start and end index. // See List.Slice() for more details. -func (b *ListBuilder) Slice(start, end int) { +func (b *ListBuilder[T]) Slice(start, end int) { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") b.list = b.list.slice(start, end, true) } // Iterator returns a new iterator for the underlying list. -func (b *ListBuilder) Iterator() *ListIterator { +func (b *ListBuilder[T]) Iterator() *ListIterator[T] { assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation") return b.list.Iterator() } @@ -297,53 +298,53 @@ const ( ) // listNode represents either a branch or leaf node in a List. -type listNode interface { +type listNode[T comparable] interface { depth() uint - get(index int) interface{} - set(index int, v interface{}, mutable bool) listNode + get(index int) T + set(index int, v T, mutable bool) listNode[T] containsBefore(index int) bool containsAfter(index int) bool - deleteBefore(index int, mutable bool) listNode - deleteAfter(index int, mutable bool) listNode + deleteBefore(index int, mutable bool) listNode[T] + deleteAfter(index int, mutable bool) listNode[T] } // newListNode returns a leaf node for depth zero, otherwise returns a branch node. -func newListNode(depth uint) listNode { +func newListNode[T comparable](depth uint) listNode[T] { if depth == 0 { - return &listLeafNode{} + return &listLeafNode[T]{} } - return &listBranchNode{d: depth} + return &listBranchNode[T]{d: depth} } // listBranchNode represents a branch of a List tree at a given depth. -type listBranchNode struct { +type listBranchNode[T comparable] struct { d uint // depth - children [listNodeSize]listNode + children [listNodeSize]listNode[T] } // depth returns the depth of this branch node from the leaf. -func (n *listBranchNode) depth() uint { return n.d } +func (n *listBranchNode[T]) depth() uint { return n.d } // get returns the child node at the segment of the index for this depth. -func (n *listBranchNode) get(index int) interface{} { +func (n *listBranchNode[T]) get(index int) T { idx := (index >> (n.d * listNodeBits)) & listNodeMask return n.children[idx].get(index) } // set recursively updates the value at index for each lower depth from the node. -func (n *listBranchNode) set(index int, v interface{}, mutable bool) listNode { +func (n *listBranchNode[T]) set(index int, v T, mutable bool) listNode[T] { idx := (index >> (n.d * listNodeBits)) & listNodeMask // Find child for the given value in the branch. Create new if it doesn't exist. child := n.children[idx] if child == nil { - child = newListNode(n.depth() - 1) + child = newListNode[T](n.depth() - 1) } // Return a copy of this branch with the new child. - var other *listBranchNode + var other *listBranchNode[T] if mutable { other = n } else { @@ -355,7 +356,7 @@ func (n *listBranchNode) set(index int, v interface{}, mutable bool) listNode { } // containsBefore returns true if non-nil values exists between [0,index). -func (n *listBranchNode) containsBefore(index int) bool { +func (n *listBranchNode[T]) containsBefore(index int) bool { idx := (index >> (n.d * listNodeBits)) & listNodeMask // Quickly check if any direct children exist before this segment of the index. @@ -373,7 +374,7 @@ func (n *listBranchNode) containsBefore(index int) bool { } // containsAfter returns true if non-nil values exists between (index,listNodeSize). -func (n *listBranchNode) containsAfter(index int) bool { +func (n *listBranchNode[T]) containsAfter(index int) bool { idx := (index >> (n.d * listNodeBits)) & listNodeMask // Quickly check if any direct children exist after this segment of the index. @@ -391,7 +392,7 @@ func (n *listBranchNode) containsAfter(index int) bool { } // deleteBefore returns a new node with all elements before index removed. -func (n *listBranchNode) deleteBefore(index int, mutable bool) listNode { +func (n *listBranchNode[T]) deleteBefore(index int, mutable bool) listNode[T] { // Ignore if no nodes exist before the given index. if !n.containsBefore(index) { return n @@ -400,14 +401,14 @@ func (n *listBranchNode) deleteBefore(index int, mutable bool) listNode { // Return a copy with any nodes prior to the index removed. idx := (index >> (n.d * listNodeBits)) & listNodeMask - var other *listBranchNode + var other *listBranchNode[T] if mutable { other = n for i := 0; i < idx; i++ { n.children[i] = nil } } else { - other = &listBranchNode{d: n.d} + other = &listBranchNode[T]{d: n.d} copy(other.children[idx:][:], n.children[idx:][:]) } @@ -418,7 +419,7 @@ func (n *listBranchNode) deleteBefore(index int, mutable bool) listNode { } // deleteBefore returns a new node with all elements before index removed. -func (n *listBranchNode) deleteAfter(index int, mutable bool) listNode { +func (n *listBranchNode[T]) deleteAfter(index int, mutable bool) listNode[T] { // Ignore if no nodes exist after the given index. if !n.containsAfter(index) { return n @@ -427,14 +428,14 @@ func (n *listBranchNode) deleteAfter(index int, mutable bool) listNode { // Return a copy with any nodes after the index removed. idx := (index >> (n.d * listNodeBits)) & listNodeMask - var other *listBranchNode + var other *listBranchNode[T] if mutable { other = n for i := idx + 1; i < len(n.children); i++ { n.children[i] = nil } } else { - other = &listBranchNode{d: n.d} + other = &listBranchNode[T]{d: n.d} copy(other.children[:idx+1], n.children[:idx+1]) } @@ -445,22 +446,22 @@ func (n *listBranchNode) deleteAfter(index int, mutable bool) listNode { } // listLeafNode represents a leaf node in a List. -type listLeafNode struct { - children [listNodeSize]interface{} +type listLeafNode[T comparable] struct { + children [listNodeSize]T } // depth always returns 0 for leaf nodes. -func (n *listLeafNode) depth() uint { return 0 } +func (n *listLeafNode[T]) depth() uint { return 0 } // get returns the value at the given index. -func (n *listLeafNode) get(index int) interface{} { +func (n *listLeafNode[T]) get(index int) T { return n.children[index&listNodeMask] } // set returns a copy of the node with the value at the index updated to v. -func (n *listLeafNode) set(index int, v interface{}, mutable bool) listNode { +func (n *listLeafNode[T]) set(index int, v T, mutable bool) listNode[T] { idx := index & listNodeMask - var other *listLeafNode + var other *listLeafNode[T] if mutable { other = n } else { @@ -468,14 +469,17 @@ func (n *listLeafNode) set(index int, v interface{}, mutable bool) listNode { other = &tmp } other.children[idx] = v - return other + var otherLN listNode[T] + otherLN = other + return otherLN } // containsBefore returns true if non-nil values exists between [0,index). -func (n *listLeafNode) containsBefore(index int) bool { +func (n *listLeafNode[T]) containsBefore(index int) bool { idx := index & listNodeMask + var empty T for i := 0; i < idx; i++ { - if n.children[i] != nil { + if n.children[i] != empty { return true } } @@ -483,10 +487,11 @@ func (n *listLeafNode) containsBefore(index int) bool { } // containsAfter returns true if non-nil values exists between (index,listNodeSize). -func (n *listLeafNode) containsAfter(index int) bool { +func (n *listLeafNode[T]) containsAfter(index int) bool { idx := index & listNodeMask + var empty T for i := idx + 1; i < len(n.children); i++ { - if n.children[i] != nil { + if n.children[i] != empty { return true } } @@ -494,62 +499,64 @@ func (n *listLeafNode) containsAfter(index int) bool { } // deleteBefore returns a new node with all elements before index removed. -func (n *listLeafNode) deleteBefore(index int, mutable bool) listNode { +func (n *listLeafNode[T]) deleteBefore(index int, mutable bool) listNode[T] { if !n.containsBefore(index) { return n } idx := index & listNodeMask - var other *listLeafNode + var other *listLeafNode[T] if mutable { other = n + var empty T for i := 0; i < idx; i++ { - other.children[i] = nil + other.children[i] = empty } } else { - other = &listLeafNode{} + other = &listLeafNode[T]{} copy(other.children[idx:][:], n.children[idx:][:]) } return other } // deleteBefore returns a new node with all elements before index removed. -func (n *listLeafNode) deleteAfter(index int, mutable bool) listNode { +func (n *listLeafNode[T]) deleteAfter(index int, mutable bool) listNode[T] { if !n.containsAfter(index) { return n } idx := index & listNodeMask - var other *listLeafNode + var other *listLeafNode[T] if mutable { other = n + var empty T for i := idx + 1; i < len(n.children); i++ { - other.children[i] = nil + other.children[i] = empty } } else { - other = &listLeafNode{} + other = &listLeafNode[T]{} copy(other.children[:idx+1][:], n.children[:idx+1][:]) } return other } // ListIterator represents an ordered iterator over a list. -type ListIterator struct { - list *List // source list - index int // current index position +type ListIterator[T comparable] struct { + list *List[T] // source list + index int // current index position - stack [32]listIteratorElem // search stack - depth int // stack depth + stack [32]listIteratorElem[T] // search stack + depth int // stack depth } // Done returns true if no more elements remain in the iterator. -func (itr *ListIterator) Done() bool { +func (itr *ListIterator[T]) Done() bool { return itr.index < 0 || itr.index >= itr.list.Len() } // First positions the iterator on the first index. // If source list is empty then no change is made. -func (itr *ListIterator) First() { +func (itr *ListIterator[T]) First() { if itr.list.Len() != 0 { itr.Seek(0) } @@ -557,7 +564,7 @@ func (itr *ListIterator) First() { // Last positions the iterator on the last index. // If source list is empty then no change is made. -func (itr *ListIterator) Last() { +func (itr *ListIterator[T]) Last() { if n := itr.list.Len(); n != 0 { itr.Seek(n - 1) } @@ -566,7 +573,7 @@ func (itr *ListIterator) Last() { // Seek moves the iterator position to the given index in the list. // Similar to Go slices, this method will panic if index is below zero or if // the index is greater than or equal to the list size. -func (itr *ListIterator) Seek(index int) { +func (itr *ListIterator[T]) Seek(index int) { // Panic similar to Go slices. if index < 0 || index >= itr.list.Len() { panic(fmt.Sprintf("immutable.ListIterator.Seek: index %d out of bounds", index)) @@ -574,22 +581,23 @@ func (itr *ListIterator) Seek(index int) { itr.index = index // Reset to the bottom of the stack at seek to the correct position. - itr.stack[0] = listIteratorElem{node: itr.list.root} + itr.stack[0] = listIteratorElem[T]{node: itr.list.root} itr.depth = 0 itr.seek(index) } // Next returns the current index and its value & moves the iterator forward. // Returns an index of -1 if the there are no more elements to return. -func (itr *ListIterator) Next() (index int, value interface{}) { +func (itr *ListIterator[T]) Next() (index int, value T) { // Exit immediately if there are no elements remaining. + var empty T if itr.Done() { - return -1, nil + return -1, empty } // Retrieve current index & value. elem := &itr.stack[itr.depth] - index, value = itr.index, elem.node.(*listLeafNode).children[elem.index] + index, value = itr.index, elem.node.(*listLeafNode[T]).children[elem.index] // Increase index. If index is at the end then return immediately. itr.index++ @@ -609,15 +617,16 @@ func (itr *ListIterator) Next() (index int, value interface{}) { // Prev returns the current index and value and moves the iterator backward. // Returns an index of -1 if the there are no more elements to return. -func (itr *ListIterator) Prev() (index int, value interface{}) { +func (itr *ListIterator[T]) Prev() (index int, value T) { // Exit immediately if there are no elements remaining. + var empty T if itr.Done() { - return -1, nil + return -1, empty } // Retrieve current index & value. elem := &itr.stack[itr.depth] - index, value = itr.index, elem.node.(*listLeafNode).children[elem.index] + index, value = itr.index, elem.node.(*listLeafNode[T]).children[elem.index] // Decrease index. If index is past the beginning then return immediately. itr.index-- @@ -637,26 +646,26 @@ func (itr *ListIterator) Prev() (index int, value interface{}) { // seek positions the stack to the given index from the current depth. // Elements and indexes below the current depth are assumed to be correct. -func (itr *ListIterator) seek(index int) { +func (itr *ListIterator[T]) seek(index int) { // Iterate over each level until we reach a leaf node. for { elem := &itr.stack[itr.depth] elem.index = ((itr.list.origin + index) >> (elem.node.depth() * listNodeBits)) & listNodeMask switch node := elem.node.(type) { - case *listBranchNode: + case *listBranchNode[T]: child := node.children[elem.index] - itr.stack[itr.depth+1] = listIteratorElem{node: child} + itr.stack[itr.depth+1] = listIteratorElem[T]{node: child} itr.depth++ - case *listLeafNode: + case *listLeafNode[T]: return } } } // listIteratorElem represents the node and it's child index within the stack. -type listIteratorElem struct { - node listNode +type listIteratorElem[T comparable] struct { + node listNode[T] index int } @@ -677,28 +686,28 @@ const ( // to generate hashes and check for equality of key values. // // It is implemented as an Hash Array Mapped Trie. -type Map struct { - size int // total number of key/value pairs - root mapNode // root node of trie - hasher Hasher // hasher implementation +type Map[K constraints.Ordered, 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. -func NewMap(hasher Hasher) *Map { - return &Map{ +func NewMap[K constraints.Ordered, V any](hasher Hasher[K]) *Map[K, V] { + return &Map[K, V]{ hasher: hasher, } } // Len returns the number of elements in the map. -func (m *Map) Len() int { +func (m *Map[K, V]) Len() int { return m.size } // clone returns a shallow copy of m. -func (m *Map) clone() *Map { +func (m *Map[K, V]) clone() *Map[K, V] { other := *m return &other } @@ -706,9 +715,10 @@ func (m *Map) clone() *Map { // Get returns the value for a given key and a flag indicating whether the // key exists. This flag distinguishes a nil value set on a key versus a // non-existent key in the map. -func (m *Map) Get(key interface{}) (value interface{}, ok bool) { +func (m *Map[K, V]) Get(key K) (value V, ok bool) { + var empty V if m.root == nil { - return nil, false + return empty, false } keyHash := m.hasher.Hash(key) return m.root.get(key, 0, keyHash, m.hasher) @@ -718,11 +728,11 @@ func (m *Map) Get(key interface{}) (value interface{}, ok bool) { // // This function will return a new map even if the updated value is the same as // the existing value because Map does not track value equality. -func (m *Map) Set(key, value interface{}) *Map { +func (m *Map[K, V]) Set(key K, value V) *Map[K, V] { return m.set(key, value, false) } -func (m *Map) set(key, value interface{}, mutable bool) *Map { +func (m *Map[K, V]) set(key K, value V, mutable bool) *Map[K, V] { // Set a hasher on the first value if one does not already exist. hasher := m.hasher if hasher == nil { @@ -739,7 +749,7 @@ func (m *Map) set(key, value interface{}, mutable bool) *Map { // If the map is empty, initialize with a simple array node. if m.root == nil { other.size = 1 - other.root = &mapArrayNode{entries: []mapEntry{{key: key, value: value}}} + other.root = &mapArrayNode[K, V]{entries: []mapEntry[K, V]{{key: key, value: value}}} return other } @@ -755,11 +765,11 @@ func (m *Map) set(key, value interface{}, mutable bool) *Map { // Delete returns a map with the given key removed. // Removing a non-existent key will cause this method to return the same map. -func (m *Map) Delete(key interface{}) *Map { +func (m *Map[K, V]) Delete(key K) *Map[K, V] { return m.delete(key, false) } -func (m *Map) delete(key interface{}, mutable bool) *Map { +func (m *Map[K, V]) delete(key K, mutable bool) *Map[K, V] { // Return original map if no keys exist. if m.root == nil { return m @@ -785,25 +795,25 @@ func (m *Map) delete(key interface{}, mutable bool) *Map { } // Iterator returns a new iterator for the map. -func (m *Map) Iterator() *MapIterator { - itr := &MapIterator{m: m} +func (m *Map[K, V]) Iterator() *MapIterator[K, V] { + itr := &MapIterator[K, V]{m: m} itr.First() return itr } // MapBuilder represents an efficient builder for creating Maps. -type MapBuilder struct { - m *Map // current state +type MapBuilder[K constraints.Ordered, V any] struct { + m *Map[K, V] // current state } // NewMapBuilder returns a new instance of MapBuilder. -func NewMapBuilder(hasher Hasher) *MapBuilder { - return &MapBuilder{m: NewMap(hasher)} +func NewMapBuilder[K constraints.Ordered, V any](hasher Hasher[K]) *MapBuilder[K, V] { + return &MapBuilder[K, V]{m: NewMap[K, V](hasher)} } // Map returns the underlying map. Only call once. // Builder is invalid after call. Will panic on second invocation. -func (b *MapBuilder) Map() *Map { +func (b *MapBuilder[K, V]) Map() *Map[K, V] { assert(b.m != nil, "immutable.SortedMapBuilder.Map(): duplicate call to fetch map") m := b.m b.m = nil @@ -811,66 +821,66 @@ func (b *MapBuilder) Map() *Map { } // Len returns the number of elements in the underlying map. -func (b *MapBuilder) Len() int { +func (b *MapBuilder[K, V]) Len() int { assert(b.m != nil, "immutable.MapBuilder: builder invalid after Map() invocation") return b.m.Len() } // Get returns the value for the given key. -func (b *MapBuilder) Get(key interface{}) (value interface{}, ok bool) { +func (b *MapBuilder[K, V]) Get(key K) (value V, ok bool) { assert(b.m != nil, "immutable.MapBuilder: builder invalid after Map() invocation") return b.m.Get(key) } // Set sets the value of the given key. See Map.Set() for additional details. -func (b *MapBuilder) Set(key, value interface{}) { +func (b *MapBuilder[K, V]) Set(key K, value V) { assert(b.m != nil, "immutable.MapBuilder: builder invalid after Map() invocation") b.m = b.m.set(key, value, true) } // Delete removes the given key. See Map.Delete() for additional details. -func (b *MapBuilder) Delete(key interface{}) { +func (b *MapBuilder[K, V]) Delete(key K) { assert(b.m != nil, "immutable.MapBuilder: builder invalid after Map() invocation") b.m = b.m.delete(key, true) } // Iterator returns a new iterator for the underlying map. -func (b *MapBuilder) Iterator() *MapIterator { +func (b *MapBuilder[K, V]) Iterator() *MapIterator[K, V] { assert(b.m != nil, "immutable.MapBuilder: builder invalid after Map() invocation") return b.m.Iterator() } // mapNode represents any node in the map tree. -type mapNode interface { - get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) - set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode - delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode +type mapNode[K constraints.Ordered, 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 = (*mapArrayNode)(nil) -var _ mapNode = (*mapBitmapIndexedNode)(nil) -var _ mapNode = (*mapHashArrayNode)(nil) -var _ mapNode = (*mapValueNode)(nil) -var _ mapNode = (*mapHashCollisionNode)(nil) +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 interface { - mapNode +type mapLeafNode[K constraints.Ordered, V any] interface { + mapNode[K, V] keyHashValue() uint32 } -var _ mapLeafNode = (*mapValueNode)(nil) -var _ mapLeafNode = (*mapHashCollisionNode)(nil) +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 struct { - entries []mapEntry +type mapArrayNode[K constraints.Ordered, 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) indexOf(key interface{}, h Hasher) int { +func (n *mapArrayNode[K, V]) indexOf(key K, h Hasher[K]) int { for i := range n.entries { if h.Equal(n.entries[i].key, key) { return i @@ -880,17 +890,17 @@ func (n *mapArrayNode) indexOf(key interface{}, h Hasher) int { } // get returns the value for the given key. -func (n *mapArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { +func (n *mapArrayNode[K, V]) get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) { i := n.indexOf(key, h) if i == -1 { - return nil, false + return value, false } return n.entries[i].value, true } // set inserts or updates the value for a given key. If the key is inserted and // the new size crosses the max size threshold, a bitmap indexed node is returned. -func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapArrayNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { idx := n.indexOf(key, h) // Mark as resized if the key doesn't exist. @@ -901,7 +911,7 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h // If we are adding and it crosses the max size threshold, expand the node. // We do this by continually setting the entries to a value node and expanding. if idx == -1 && len(n.entries) >= maxArrayMapSize { - var node mapNode = newMapValueNode(h.Hash(key), key, value) + var node mapNode[K, V] = newMapValueNode(h.Hash(key), key, value) for _, entry := range n.entries { node = node.set(entry.key, entry.value, 0, h.Hash(entry.key), h, false, resized) } @@ -911,31 +921,31 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h // Update in-place if mutable. if mutable { if idx != -1 { - n.entries[idx] = mapEntry{key, value} + n.entries[idx] = mapEntry[K, V]{key, value} } else { - n.entries = append(n.entries, mapEntry{key, value}) + n.entries = append(n.entries, mapEntry[K, V]{key, value}) } return n } // Update existing entry if a match is found. // Otherwise append to the end of the element list if it doesn't exist. - var other mapArrayNode + var other mapArrayNode[K, V] if idx != -1 { - other.entries = make([]mapEntry, len(n.entries)) + other.entries = make([]mapEntry[K, V], len(n.entries)) copy(other.entries, n.entries) - other.entries[idx] = mapEntry{key, value} + other.entries[idx] = mapEntry[K, V]{key, value} } else { - other.entries = make([]mapEntry, len(n.entries)+1) + other.entries = make([]mapEntry[K, V], len(n.entries)+1) copy(other.entries, n.entries) - other.entries[len(other.entries)-1] = mapEntry{key, value} + other.entries[len(other.entries)-1] = mapEntry[K, V]{key, value} } return &other } // delete removes the given key from the node. Returns the same node if key does // not exist. Returns a nil node when removing the last entry. -func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapArrayNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { idx := n.indexOf(key, h) // Return original node if key does not exist. @@ -952,13 +962,13 @@ func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Has // Update in-place, if mutable. if mutable { copy(n.entries[idx:], n.entries[idx+1:]) - n.entries[len(n.entries)-1] = mapEntry{} + n.entries[len(n.entries)-1] = mapEntry[K, V]{} n.entries = n.entries[:len(n.entries)-1] return n } // Otherwise create a copy with the given entry removed. - other := &mapArrayNode{entries: make([]mapEntry, len(n.entries)-1)} + other := &mapArrayNode[K, V]{entries: make([]mapEntry[K, V], len(n.entries)-1)} copy(other.entries[:idx], n.entries[:idx]) copy(other.entries[idx:], n.entries[idx+1:]) return other @@ -967,16 +977,16 @@ func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Has // 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 struct { +type mapBitmapIndexedNode[K constraints.Ordered, V any] struct { bitmap uint32 - nodes []mapNode + nodes []mapNode[K, V] } // get returns the value for the given key. -func (n *mapBitmapIndexedNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { +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) if (n.bitmap & bit) == 0 { - return nil, false + return value, false } child := n.nodes[bits.OnesCount32(n.bitmap&(bit-1))] return child.get(key, shift+mapNodeBits, keyHash, h) @@ -984,7 +994,7 @@ func (n *mapBitmapIndexedNode) get(key interface{}, shift uint, keyHash uint32, // set inserts or updates the value for the given key. If a new key is inserted // and the size crosses the max size threshold then a hash array node is returned. -func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapBitmapIndexedNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { // Extract the index for the bit segment of the key hash. keyHashFrag := (keyHash >> shift) & mapNodeMask @@ -1002,17 +1012,17 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u // If the node already exists, delegate set operation to it. // If the node doesn't exist then create a simple value leaf node. - var newNode mapNode + var newNode mapNode[K, V] if exists { newNode = n.nodes[idx].set(key, value, shift+mapNodeBits, keyHash, h, mutable, resized) } else { - newNode = newMapValueNode(keyHash, key, value) + newNode = newMapValueNode[K, V](keyHash, key, value) } // Convert to a hash-array node once we exceed the max bitmap size. // Copy each node based on their bit position within the bitmap. if !exists && len(n.nodes) > maxBitmapIndexedSize { - var other mapHashArrayNode + var other mapHashArrayNode[K, V] for i := uint(0); i < uint(len(other.nodes)); i++ { if n.bitmap&(uint32(1)<<i) != 0 { other.nodes[i] = n.nodes[other.count] @@ -1039,13 +1049,13 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u // If node exists at given slot then overwrite it with new node. // Otherwise expand the node list and insert new node into appropriate position. - other := &mapBitmapIndexedNode{bitmap: n.bitmap | bit} + other := &mapBitmapIndexedNode[K, V]{bitmap: n.bitmap | bit} if exists { - other.nodes = make([]mapNode, len(n.nodes)) + other.nodes = make([]mapNode[K, V], len(n.nodes)) copy(other.nodes, n.nodes) other.nodes[idx] = newNode } else { - other.nodes = make([]mapNode, len(n.nodes)+1) + other.nodes = make([]mapNode[K, V], len(n.nodes)+1) copy(other.nodes, n.nodes[:idx]) other.nodes[idx] = newNode copy(other.nodes[idx+1:], n.nodes[idx:]) @@ -1056,7 +1066,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u // delete removes the key from the tree. If the key does not exist then the // original node is returned. If removing the last child node then a nil is // returned. Note that shrinking the node will not convert it to an array node. -func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapBitmapIndexedNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { bit := uint32(1) << ((keyHash >> shift) & mapNodeMask) // Return original node if key does not exist. @@ -1093,7 +1103,7 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 } // Return copy with bit removed from bitmap and node removed from node list. - other := &mapBitmapIndexedNode{bitmap: n.bitmap ^ bit, nodes: make([]mapNode, len(n.nodes)-1)} + other := &mapBitmapIndexedNode[K, V]{bitmap: n.bitmap ^ bit, nodes: make([]mapNode[K, V], len(n.nodes)-1)} copy(other.nodes[:idx], n.nodes[:idx]) copy(other.nodes[idx:], n.nodes[idx+1:]) return other @@ -1102,7 +1112,7 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 // Generate copy, if necessary. other := n if !mutable { - other = &mapBitmapIndexedNode{bitmap: n.bitmap, nodes: make([]mapNode, len(n.nodes))} + other = &mapBitmapIndexedNode[K, V]{bitmap: n.bitmap, nodes: make([]mapNode[K, V], len(n.nodes))} copy(other.nodes, n.nodes) } @@ -1113,34 +1123,34 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 // 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 struct { - count uint // number of set nodes - nodes [mapNodeSize]mapNode // child node slots, may contain empties +type mapHashArrayNode[K constraints.Ordered, 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) clone() *mapHashArrayNode { +func (n *mapHashArrayNode[K, V]) clone() *mapHashArrayNode[K, V] { other := *n return &other } // get returns the value for the given key. -func (n *mapHashArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { +func (n *mapHashArrayNode[K, V]) get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) { node := n.nodes[(keyHash>>shift)&mapNodeMask] if node == nil { - return nil, false + return value, false } return node.get(key, shift+mapNodeBits, keyHash, h) } // set returns a node with the value set for the given key. -func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapHashArrayNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { idx := (keyHash >> shift) & mapNodeMask node := n.nodes[idx] // If node at index doesn't exist, create a simple value leaf node. // Otherwise delegate set to child node. - var newNode mapNode + var newNode mapNode[K, V] if node == nil { *resized = true newNode = newMapValueNode(keyHash, key, value) @@ -1165,7 +1175,7 @@ func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint3 // delete returns a node with the given key removed. Returns the same node if // the key does not exist. If node shrinks to within bitmap-indexed size then // converts to a bitmap-indexed node. -func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapHashArrayNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { idx := (keyHash >> shift) & mapNodeMask node := n.nodes[idx] @@ -1182,7 +1192,7 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h // If we remove a node and drop below a threshold, convert back to bitmap indexed node. if newNode == nil && n.count <= maxBitmapIndexedSize { - other := &mapBitmapIndexedNode{nodes: make([]mapNode, 0, n.count-1)} + other := &mapBitmapIndexedNode[K, V]{nodes: make([]mapNode[K, V], 0, n.count-1)} for i, child := range n.nodes { if child != nil && uint32(i) != idx { other.bitmap |= 1 << uint(i) @@ -1209,15 +1219,15 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h // 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 struct { +type mapValueNode[K constraints.Ordered, V any] struct { keyHash uint32 - key interface{} - value interface{} + key K + value V } // newMapValueNode returns a new instance of mapValueNode. -func newMapValueNode(keyHash uint32, key, value interface{}) *mapValueNode { - return &mapValueNode{ +func newMapValueNode[K constraints.Ordered, V any](keyHash uint32, key K, value V) *mapValueNode[K, V] { + return &mapValueNode[K, V]{ keyHash: keyHash, key: key, value: value, @@ -1225,14 +1235,14 @@ func newMapValueNode(keyHash uint32, key, value interface{}) *mapValueNode { } // keyHashValue returns the key hash for this node. -func (n *mapValueNode) keyHashValue() uint32 { +func (n *mapValueNode[K, V]) keyHashValue() uint32 { return n.keyHash } // get returns the value for the given key. -func (n *mapValueNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { +func (n *mapValueNode[K, V]) get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) { if !h.Equal(n.key, key) { - return nil, false + return value, false } return n.value, true } @@ -1241,7 +1251,7 @@ func (n *mapValueNode) get(key interface{}, shift uint, keyHash uint32, h Hasher // the node's key then a new value node is returned. If key is not equal to the // node's key but has the same hash then a hash collision node is returned. // Otherwise the nodes are merged into a branch node. -func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapValueNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { // If the keys match then return a new value node overwriting the value. if h.Equal(n.key, key) { // Update in-place if mutable. @@ -1257,18 +1267,18 @@ func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h // Recursively merge nodes together if key hashes are different. if n.keyHash != keyHash { - return mergeIntoNode(n, shift, keyHash, key, value) + return mergeIntoNode[K, V](n, shift, keyHash, key, value) } // Merge into collision node if hash matches. - return &mapHashCollisionNode{keyHash: keyHash, entries: []mapEntry{ + return &mapHashCollisionNode[K, V]{keyHash: keyHash, entries: []mapEntry[K, V]{ {key: n.key, value: n.value}, {key: key, value: value}, }} } // delete returns nil if the key matches the node's key. Otherwise returns the original node. -func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapValueNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { // Return original node if the keys do not match. if !h.Equal(n.key, key) { return n @@ -1281,19 +1291,19 @@ func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Has // 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 struct { +type mapHashCollisionNode[K constraints.Ordered, V any] struct { keyHash uint32 // key hash for all entries - entries []mapEntry + entries []mapEntry[K, V] } // keyHashValue returns the key hash for all entries on the node. -func (n *mapHashCollisionNode) keyHashValue() uint32 { +func (n *mapHashCollisionNode[K, V]) keyHashValue() uint32 { return n.keyHash } // indexOf returns the index of the entry for the given key. // Returns -1 if the key does not exist in the node. -func (n *mapHashCollisionNode) indexOf(key interface{}, h Hasher) int { +func (n *mapHashCollisionNode[K, V]) indexOf(key K, h Hasher[K]) int { for i := range n.entries { if h.Equal(n.entries[i].key, key) { return i @@ -1303,46 +1313,46 @@ func (n *mapHashCollisionNode) indexOf(key interface{}, h Hasher) int { } // get returns the value for the given key. -func (n *mapHashCollisionNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { +func (n *mapHashCollisionNode[K, V]) get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) { for i := range n.entries { if h.Equal(n.entries[i].key, key) { return n.entries[i].value, true } } - return nil, false + return value, false } // set returns a copy of the node with key set to the given value. -func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapHashCollisionNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { // Merge node with key/value pair if this is not a hash collision. if n.keyHash != keyHash { *resized = true - return mergeIntoNode(n, shift, keyHash, key, value) + return mergeIntoNode[K, V](n, shift, keyHash, key, value) } // Update in-place if mutable. if mutable { if idx := n.indexOf(key, h); idx == -1 { *resized = true - n.entries = append(n.entries, mapEntry{key, value}) + n.entries = append(n.entries, mapEntry[K, V]{key, value}) } else { - n.entries[idx] = mapEntry{key, value} + n.entries[idx] = mapEntry[K, V]{key, value} } return n } // Append to end of node if key doesn't exist & mark resized. // Otherwise copy nodes and overwrite at matching key index. - other := &mapHashCollisionNode{keyHash: n.keyHash} + other := &mapHashCollisionNode[K, V]{keyHash: n.keyHash} if idx := n.indexOf(key, h); idx == -1 { *resized = true - other.entries = make([]mapEntry, len(n.entries)+1) + other.entries = make([]mapEntry[K, V], len(n.entries)+1) copy(other.entries, n.entries) - other.entries[len(other.entries)-1] = mapEntry{key, value} + other.entries[len(other.entries)-1] = mapEntry[K, V]{key, value} } else { - other.entries = make([]mapEntry, len(n.entries)) + other.entries = make([]mapEntry[K, V], len(n.entries)) copy(other.entries, n.entries) - other.entries[idx] = mapEntry{key, value} + other.entries[idx] = mapEntry[K, V]{key, value} } return other } @@ -1350,7 +1360,7 @@ func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash u // delete returns a node with the given key deleted. Returns the same node if // the key does not exist. If removing the key would shrink the node to a single // entry then a value node is returned. -func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { +func (n *mapHashCollisionNode[K, V]) delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] { idx := n.indexOf(key, h) // Return original node if key is not found. @@ -1363,7 +1373,7 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3 // Convert to value node if we move to one entry. if len(n.entries) == 2 { - return &mapValueNode{ + return &mapValueNode[K, V]{ keyHash: n.keyHash, key: n.entries[idx^1].key, value: n.entries[idx^1].value, @@ -1373,13 +1383,13 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3 // Remove entry in-place if mutable. if mutable { copy(n.entries[idx:], n.entries[idx+1:]) - n.entries[len(n.entries)-1] = mapEntry{} + n.entries[len(n.entries)-1] = mapEntry[K, V]{} n.entries = n.entries[:len(n.entries)-1] return n } // Return copy without entry if immutable. - other := &mapHashCollisionNode{keyHash: n.keyHash, entries: make([]mapEntry, len(n.entries)-1)} + other := &mapHashCollisionNode[K, V]{keyHash: n.keyHash, entries: make([]mapEntry[K, V], len(n.entries)-1)} copy(other.entries[:idx], n.entries[:idx]) copy(other.entries[idx:], n.entries[idx+1:]) return other @@ -1387,46 +1397,46 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3 // mergeIntoNode merges a key/value pair into an existing node. // Caller must verify that node's keyHash is not equal to keyHash. -func mergeIntoNode(node mapLeafNode, shift uint, keyHash uint32, key, value interface{}) mapNode { +func mergeIntoNode[K constraints.Ordered, V any](node mapLeafNode[K, V], shift uint, keyHash uint32, key K, value V) mapNode[K, V] { idx1 := (node.keyHashValue() >> shift) & mapNodeMask idx2 := (keyHash >> shift) & mapNodeMask // Recursively build branch nodes to combine the node and its key. - other := &mapBitmapIndexedNode{bitmap: (1 << idx1) | (1 << idx2)} + other := &mapBitmapIndexedNode[K, V]{bitmap: (1 << idx1) | (1 << idx2)} if idx1 == idx2 { - other.nodes = []mapNode{mergeIntoNode(node, shift+mapNodeBits, keyHash, key, value)} + other.nodes = []mapNode[K, V]{mergeIntoNode(node, shift+mapNodeBits, keyHash, key, value)} } else { if newNode := newMapValueNode(keyHash, key, value); idx1 < idx2 { - other.nodes = []mapNode{node, newNode} + other.nodes = []mapNode[K, V]{node, newNode} } else { - other.nodes = []mapNode{newNode, node} + other.nodes = []mapNode[K, V]{newNode, node} } } return other } // mapEntry represents a single key/value pair. -type mapEntry struct { - key interface{} - value interface{} +type mapEntry[K constraints.Ordered, 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 struct { - m *Map // source map +type MapIterator[K constraints.Ordered, V any] struct { + m *Map[K, V] // source map - stack [32]mapIteratorElem // search stack - depth int // stack depth + 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) Done() bool { +func (itr *MapIterator[K, V]) Done() bool { return itr.depth == -1 } // First resets the iterator to the first key/value pair. -func (itr *MapIterator) First() { +func (itr *MapIterator[K, V]) First() { // Exit immediately if the map is empty. if itr.m.root == nil { itr.depth = -1 @@ -1434,27 +1444,27 @@ func (itr *MapIterator) First() { } // Initialize the stack to the left most element. - itr.stack[0] = mapIteratorElem{node: itr.m.root} + itr.stack[0] = mapIteratorElem[K, V]{node: itr.m.root} itr.depth = 0 itr.first() } // Next returns the next key/value pair. Returns a nil key when no elements remain. -func (itr *MapIterator) Next() (key, value interface{}) { +func (itr *MapIterator[K, V]) Next() (key K, value V, ok bool) { // Return nil key if iteration is done. if itr.Done() { - return nil, nil + return key, value, false } // Retrieve current index & value. Current node is always a leaf. elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *mapArrayNode: + case *mapArrayNode[K, V]: entry := &node.entries[elem.index] key, value = entry.key, entry.value - case *mapValueNode: + case *mapValueNode[K, V]: key, value = node.key, node.value - case *mapHashCollisionNode: + case *mapHashCollisionNode[K, V]: entry := &node.entries[elem.index] key, value = entry.key, entry.value } @@ -1462,22 +1472,22 @@ func (itr *MapIterator) Next() (key, value interface{}) { // Move up stack until we find a node that has remaining position ahead // and move that element forward by one. itr.next() - return key, value + return key, value, true } // next moves to the next available key. -func (itr *MapIterator) next() { +func (itr *MapIterator[K, V]) next() { for ; itr.depth >= 0; itr.depth-- { elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *mapArrayNode: + case *mapArrayNode[K, V]: if elem.index < len(node.entries)-1 { elem.index++ return } - case *mapBitmapIndexedNode: + case *mapBitmapIndexedNode[K, V]: if elem.index < len(node.nodes)-1 { elem.index++ itr.stack[itr.depth+1].node = node.nodes[elem.index] @@ -1486,7 +1496,7 @@ func (itr *MapIterator) next() { return } - case *mapHashArrayNode: + case *mapHashArrayNode[K, V]: for i := elem.index + 1; i < len(node.nodes); i++ { if node.nodes[i] != nil { elem.index = i @@ -1497,10 +1507,10 @@ func (itr *MapIterator) next() { } } - case *mapValueNode: + case *mapValueNode[K, V]: continue // always the last value, traverse up - case *mapHashCollisionNode: + case *mapHashCollisionNode[K, V]: if elem.index < len(node.entries)-1 { elem.index++ return @@ -1511,16 +1521,16 @@ func (itr *MapIterator) next() { // first positions the stack left most index. // Elements and indexes at and below the current depth are assumed to be correct. -func (itr *MapIterator) first() { +func (itr *MapIterator[K, V]) first() { for ; ; itr.depth++ { elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *mapBitmapIndexedNode: + case *mapBitmapIndexedNode[K, V]: elem.index = 0 itr.stack[itr.depth+1].node = node.nodes[0] - case *mapHashArrayNode: + case *mapHashArrayNode[K, V]: for i := 0; i < len(node.nodes); i++ { if node.nodes[i] != nil { // find first node elem.index = i @@ -1537,8 +1547,8 @@ func (itr *MapIterator) first() { } // mapIteratorElem represents a node/index pair in the MapIterator stack. -type mapIteratorElem struct { - node mapNode +type mapIteratorElem[K constraints.Ordered, V any] struct { + node mapNode[K, V] index int } @@ -1551,45 +1561,46 @@ const ( // is determined by the Comparer used by the map. // // This map is implemented as a B+tree. -type SortedMap struct { - size int // total number of key/value pairs - root sortedMapNode // root of b+tree - comparer Comparer +type SortedMap[K constraints.Ordered, 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. -func NewSortedMap(comparer Comparer) *SortedMap { - return &SortedMap{ +func NewSortedMap[K constraints.Ordered, V any](comparer Comparer[K]) *SortedMap[K, V] { + return &SortedMap[K, V]{ comparer: comparer, } } // Len returns the number of elements in the sorted map. -func (m *SortedMap) Len() int { +func (m *SortedMap[K, V]) Len() int { return m.size } // Get returns the value for a given key and a flag indicating if the key is set. // The flag can be used to distinguish between a nil-set key versus an unset key. -func (m *SortedMap) Get(key interface{}) (interface{}, bool) { +func (m *SortedMap[K, V]) Get(key K) (V, bool) { if m.root == nil { - return nil, false + var v V + return v, false } return m.root.get(key, m.comparer) } // Set returns a copy of the map with the key set to the given value. -func (m *SortedMap) Set(key, value interface{}) *SortedMap { +func (m *SortedMap[K, V]) Set(key K, value V) *SortedMap[K, V] { return m.set(key, value, false) } -func (m *SortedMap) set(key, value interface{}, mutable bool) *SortedMap { +func (m *SortedMap[K, V]) set(key K, value V, mutable bool) *SortedMap[K, V] { // Set a comparer on the first value if one does not already exist. comparer := m.comparer if comparer == nil { - comparer = NewComparer(key) + comparer = NewComparer[K](key) } // Create copy, if necessary. @@ -1602,7 +1613,7 @@ func (m *SortedMap) set(key, value interface{}, mutable bool) *SortedMap { // If no values are set then initialize with a leaf node. if m.root == nil { other.size = 1 - other.root = &sortedMapLeafNode{entries: []mapEntry{{key: key, value: value}}} + other.root = &sortedMapLeafNode[K, V]{entries: []mapEntry[K, V]{{key: key, value: value}}} return other } @@ -1625,11 +1636,11 @@ func (m *SortedMap) set(key, value interface{}, mutable bool) *SortedMap { // Delete returns a copy of the map with the key removed. // Returns the original map if key does not exist. -func (m *SortedMap) Delete(key interface{}) *SortedMap { +func (m *SortedMap[K, V]) Delete(key K) *SortedMap[K, V] { return m.delete(key, false) } -func (m *SortedMap) delete(key interface{}, mutable bool) *SortedMap { +func (m *SortedMap[K, V]) delete(key K, mutable bool) *SortedMap[K, V] { // Return original map if no keys exist. if m.root == nil { return m @@ -1655,31 +1666,31 @@ func (m *SortedMap) delete(key interface{}, mutable bool) *SortedMap { } // clone returns a shallow copy of m. -func (m *SortedMap) clone() *SortedMap { +func (m *SortedMap[K, V]) clone() *SortedMap[K, V] { other := *m return &other } // Iterator returns a new iterator for this map positioned at the first key. -func (m *SortedMap) Iterator() *SortedMapIterator { - itr := &SortedMapIterator{m: m} +func (m *SortedMap[K, V]) Iterator() *SortedMapIterator[K, V] { + itr := &SortedMapIterator[K, V]{m: m} itr.First() return itr } // SortedMapBuilder represents an efficient builder for creating sorted maps. -type SortedMapBuilder struct { - m *SortedMap // current state +type SortedMapBuilder[K constraints.Ordered, V any] struct { + m *SortedMap[K, V] // current state } // NewSortedMapBuilder returns a new instance of SortedMapBuilder. -func NewSortedMapBuilder(comparer Comparer) *SortedMapBuilder { - return &SortedMapBuilder{m: NewSortedMap(comparer)} +func NewSortedMapBuilder[K constraints.Ordered, V any](comparer Comparer[K]) *SortedMapBuilder[K, V] { + return &SortedMapBuilder[K, V]{m: NewSortedMap[K, V](comparer)} } // SortedMap returns the current copy of the map. // The returned map is safe to use even if after the builder continues to be used. -func (b *SortedMapBuilder) Map() *SortedMap { +func (b *SortedMapBuilder[K, V]) Map() *SortedMap[K, V] { assert(b.m != nil, "immutable.SortedMapBuilder.Map(): duplicate call to fetch map") m := b.m b.m = nil @@ -1687,73 +1698,73 @@ func (b *SortedMapBuilder) Map() *SortedMap { } // Len returns the number of elements in the underlying map. -func (b *SortedMapBuilder) Len() int { +func (b *SortedMapBuilder[K, V]) Len() int { assert(b.m != nil, "immutable.SortedMapBuilder: builder invalid after Map() invocation") return b.m.Len() } // Get returns the value for the given key. -func (b *SortedMapBuilder) Get(key interface{}) (value interface{}, ok bool) { +func (b *SortedMapBuilder[K, V]) Get(key K) (value V, ok bool) { assert(b.m != nil, "immutable.SortedMapBuilder: builder invalid after Map() invocation") return b.m.Get(key) } // Set sets the value of the given key. See SortedMap.Set() for additional details. -func (b *SortedMapBuilder) Set(key, value interface{}) { +func (b *SortedMapBuilder[K, V]) Set(key K, value V) { assert(b.m != nil, "immutable.SortedMapBuilder: builder invalid after Map() invocation") b.m = b.m.set(key, value, true) } // Delete removes the given key. See SortedMap.Delete() for additional details. -func (b *SortedMapBuilder) Delete(key interface{}) { +func (b *SortedMapBuilder[K, V]) Delete(key K) { assert(b.m != nil, "immutable.SortedMapBuilder: builder invalid after Map() invocation") b.m = b.m.delete(key, true) } // Iterator returns a new iterator for the underlying map positioned at the first key. -func (b *SortedMapBuilder) Iterator() *SortedMapIterator { +func (b *SortedMapBuilder[K, V]) Iterator() *SortedMapIterator[K, V] { assert(b.m != nil, "immutable.SortedMapBuilder: builder invalid after Map() invocation") return b.m.Iterator() } // sortedMapNode represents a branch or leaf node in the sorted map. -type sortedMapNode interface { - minKey() interface{} - indexOf(key interface{}, c Comparer) int - get(key interface{}, c Comparer) (value interface{}, ok bool) - set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode) - delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode +type sortedMapNode[K constraints.Ordered, 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 = (*sortedMapBranchNode)(nil) -var _ sortedMapNode = (*sortedMapLeafNode)(nil) +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 struct { - elems []sortedMapBranchElem +type sortedMapBranchNode[K constraints.Ordered, V any] struct { + elems []sortedMapBranchElem[K, V] } // newSortedMapBranchNode returns a new branch node with the given child nodes. -func newSortedMapBranchNode(children ...sortedMapNode) *sortedMapBranchNode { +func newSortedMapBranchNode[K constraints.Ordered, V any](children ...sortedMapNode[K, V]) *sortedMapBranchNode[K, V] { // Fetch min keys for every child. - elems := make([]sortedMapBranchElem, len(children)) + elems := make([]sortedMapBranchElem[K, V], len(children)) for i, child := range children { - elems[i] = sortedMapBranchElem{ + elems[i] = sortedMapBranchElem[K, V]{ key: child.minKey(), node: child, } } - return &sortedMapBranchNode{elems: elems} + return &sortedMapBranchNode[K, V]{elems: elems} } // minKey returns the lowest key stored in this node's tree. -func (n *sortedMapBranchNode) minKey() interface{} { +func (n *sortedMapBranchNode[K, V]) minKey() K { return n.elems[0].node.minKey() } // indexOf returns the index of the key within the child nodes. -func (n *sortedMapBranchNode) indexOf(key interface{}, c Comparer) int { +func (n *sortedMapBranchNode[K, V]) indexOf(key K, c Comparer[K]) int { if idx := sort.Search(len(n.elems), func(i int) bool { return c.Compare(n.elems[i].key, key) == 1 }); idx > 0 { return idx - 1 } @@ -1761,13 +1772,13 @@ func (n *sortedMapBranchNode) indexOf(key interface{}, c Comparer) int { } // get returns the value for the given key. -func (n *sortedMapBranchNode) get(key interface{}, c Comparer) (value interface{}, ok bool) { +func (n *sortedMapBranchNode[K, V]) get(key K, c Comparer[K]) (value V, ok bool) { idx := n.indexOf(key, c) return n.elems[idx].node.get(key, c) } // set returns a copy of the node with the key set to the given value. -func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode) { +func (n *sortedMapBranchNode[K, V]) set(key K, value V, c Comparer[K], mutable bool, resized *bool) (sortedMapNode[K, V], sortedMapNode[K, V]) { idx := n.indexOf(key, c) // Delegate insert to child node. @@ -1775,18 +1786,18 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bo // Update in-place, if mutable. if mutable { - n.elems[idx] = sortedMapBranchElem{key: newNode.minKey(), node: newNode} + n.elems[idx] = sortedMapBranchElem[K, V]{key: newNode.minKey(), node: newNode} if splitNode != nil { - n.elems = append(n.elems, sortedMapBranchElem{}) + n.elems = append(n.elems, sortedMapBranchElem[K, V]{}) copy(n.elems[idx+1:], n.elems[idx:]) - n.elems[idx+1] = sortedMapBranchElem{key: splitNode.minKey(), node: splitNode} + n.elems[idx+1] = sortedMapBranchElem[K, V]{key: splitNode.minKey(), node: splitNode} } // If the child splits and we have no more room then we split too. if len(n.elems) > sortedMapNodeSize { splitIdx := len(n.elems) / 2 - newNode := &sortedMapBranchNode{elems: n.elems[:splitIdx:splitIdx]} - splitNode := &sortedMapBranchNode{elems: n.elems[splitIdx:]} + newNode := &sortedMapBranchNode[K, V]{elems: n.elems[:splitIdx:splitIdx]} + splitNode := &sortedMapBranchNode[K, V]{elems: n.elems[splitIdx:]} return newNode, splitNode } return n, nil @@ -1794,23 +1805,23 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bo // If no split occurs, copy branch and update keys. // If the child splits, insert new key/child into copy of branch. - var other sortedMapBranchNode + var other sortedMapBranchNode[K, V] if splitNode == nil { - other.elems = make([]sortedMapBranchElem, len(n.elems)) + other.elems = make([]sortedMapBranchElem[K, V], len(n.elems)) copy(other.elems, n.elems) - other.elems[idx] = sortedMapBranchElem{ + other.elems[idx] = sortedMapBranchElem[K, V]{ key: newNode.minKey(), node: newNode, } } else { - other.elems = make([]sortedMapBranchElem, len(n.elems)+1) + other.elems = make([]sortedMapBranchElem[K, V], len(n.elems)+1) copy(other.elems[:idx], n.elems[:idx]) copy(other.elems[idx+1:], n.elems[idx:]) - other.elems[idx] = sortedMapBranchElem{ + other.elems[idx] = sortedMapBranchElem[K, V]{ key: newNode.minKey(), node: newNode, } - other.elems[idx+1] = sortedMapBranchElem{ + other.elems[idx+1] = sortedMapBranchElem[K, V]{ key: splitNode.minKey(), node: splitNode, } @@ -1819,8 +1830,8 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bo // If the child splits and we have no more room then we split too. if len(other.elems) > sortedMapNodeSize { splitIdx := len(other.elems) / 2 - newNode := &sortedMapBranchNode{elems: other.elems[:splitIdx:splitIdx]} - splitNode := &sortedMapBranchNode{elems: other.elems[splitIdx:]} + newNode := &sortedMapBranchNode[K, V]{elems: other.elems[:splitIdx:splitIdx]} + splitNode := &sortedMapBranchNode[K, V]{elems: other.elems[splitIdx:]} return newNode, splitNode } @@ -1830,7 +1841,7 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bo // delete returns a node with the key removed. Returns the same node if the key // does not exist. Returns nil if all child nodes are removed. -func (n *sortedMapBranchNode) delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode { +func (n *sortedMapBranchNode[K, V]) delete(key K, c Comparer[K], mutable bool, resized *bool) sortedMapNode[K, V] { idx := n.indexOf(key, c) // Return original node if child has not changed. @@ -1849,13 +1860,13 @@ func (n *sortedMapBranchNode) delete(key interface{}, c Comparer, mutable bool, // If mutable, update in-place. if mutable { copy(n.elems[idx:], n.elems[idx+1:]) - n.elems[len(n.elems)-1] = sortedMapBranchElem{} + n.elems[len(n.elems)-1] = sortedMapBranchElem[K, V]{} n.elems = n.elems[:len(n.elems)-1] return n } // Return a copy without the given node. - other := &sortedMapBranchNode{elems: make([]sortedMapBranchElem, len(n.elems)-1)} + other := &sortedMapBranchNode[K, V]{elems: make([]sortedMapBranchElem[K, V], len(n.elems)-1)} copy(other.elems[:idx], n.elems[:idx]) copy(other.elems[idx:], n.elems[idx+1:]) return other @@ -1863,49 +1874,49 @@ func (n *sortedMapBranchNode) delete(key interface{}, c Comparer, mutable bool, // If mutable, update in-place. if mutable { - n.elems[idx] = sortedMapBranchElem{key: newNode.minKey(), node: newNode} + n.elems[idx] = sortedMapBranchElem[K, V]{key: newNode.minKey(), node: newNode} return n } // Return a copy with the updated node. - other := &sortedMapBranchNode{elems: make([]sortedMapBranchElem, len(n.elems))} + other := &sortedMapBranchNode[K, V]{elems: make([]sortedMapBranchElem[K, V], len(n.elems))} copy(other.elems, n.elems) - other.elems[idx] = sortedMapBranchElem{ + other.elems[idx] = sortedMapBranchElem[K, V]{ key: newNode.minKey(), node: newNode, } return other } -type sortedMapBranchElem struct { - key interface{} - node sortedMapNode +type sortedMapBranchElem[K constraints.Ordered, V any] struct { + key K + node sortedMapNode[K, V] } // sortedMapLeafNode represents a leaf node in the sorted map. -type sortedMapLeafNode struct { - entries []mapEntry +type sortedMapLeafNode[K constraints.Ordered, V any] struct { + entries []mapEntry[K, V] } // minKey returns the first key stored in this node. -func (n *sortedMapLeafNode) minKey() interface{} { +func (n *sortedMapLeafNode[K, V]) minKey() K { return n.entries[0].key } // indexOf returns the index of the given key. -func (n *sortedMapLeafNode) indexOf(key interface{}, c Comparer) int { +func (n *sortedMapLeafNode[K, V]) indexOf(key K, c Comparer[K]) int { return sort.Search(len(n.entries), func(i int) bool { return c.Compare(n.entries[i].key, key) != -1 // GTE }) } // get returns the value of the given key. -func (n *sortedMapLeafNode) get(key interface{}, c Comparer) (value interface{}, ok bool) { +func (n *sortedMapLeafNode[K, V]) get(key K, c Comparer[K]) (value V, ok bool) { idx := n.indexOf(key, c) // If the index is beyond the entry count or the key is not equal then return 'not found'. if idx == len(n.entries) || c.Compare(n.entries[idx].key, key) != 0 { - return nil, false + return value, false } // If the key matches then return its value. @@ -1914,7 +1925,7 @@ func (n *sortedMapLeafNode) get(key interface{}, c Comparer) (value interface{}, // set returns a copy of node with the key set to the given value. If the update // causes the node to grow beyond the maximum size then it is split in two. -func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode) { +func (n *sortedMapLeafNode[K, V]) set(key K, value V, c Comparer[K], mutable bool, resized *bool) (sortedMapNode[K, V], sortedMapNode[K, V]) { // Find the insertion index for the key. idx := n.indexOf(key, c) exists := idx < len(n.entries) && c.Compare(n.entries[idx].key, key) == 0 @@ -1923,16 +1934,16 @@ func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, mutable bool if mutable { if !exists { *resized = true - n.entries = append(n.entries, mapEntry{}) + n.entries = append(n.entries, mapEntry[K, V]{}) copy(n.entries[idx+1:], n.entries[idx:]) } - n.entries[idx] = mapEntry{key: key, value: value} + n.entries[idx] = mapEntry[K, V]{key: key, value: value} // If the key doesn't exist and we exceed our max allowed values then split. if len(n.entries) > sortedMapNodeSize { splitIdx := len(n.entries) / 2 - newNode := &sortedMapLeafNode{entries: n.entries[:splitIdx:splitIdx]} - splitNode := &sortedMapLeafNode{entries: n.entries[splitIdx:]} + newNode := &sortedMapLeafNode[K, V]{entries: n.entries[:splitIdx:splitIdx]} + splitNode := &sortedMapLeafNode[K, V]{entries: n.entries[splitIdx:]} return newNode, splitNode } return n, nil @@ -1940,34 +1951,34 @@ func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, mutable bool // If the key matches then simply return a copy with the entry overridden. // If there is no match then insert new entry and mark as resized. - var newEntries []mapEntry + var newEntries []mapEntry[K, V] if exists { - newEntries = make([]mapEntry, len(n.entries)) + newEntries = make([]mapEntry[K, V], len(n.entries)) copy(newEntries, n.entries) - newEntries[idx] = mapEntry{key: key, value: value} + newEntries[idx] = mapEntry[K, V]{key: key, value: value} } else { *resized = true - newEntries = make([]mapEntry, len(n.entries)+1) + newEntries = make([]mapEntry[K, V], len(n.entries)+1) copy(newEntries[:idx], n.entries[:idx]) - newEntries[idx] = mapEntry{key: key, value: value} + newEntries[idx] = mapEntry[K, V]{key: key, value: value} copy(newEntries[idx+1:], n.entries[idx:]) } // If the key doesn't exist and we exceed our max allowed values then split. if len(newEntries) > sortedMapNodeSize { splitIdx := len(newEntries) / 2 - newNode := &sortedMapLeafNode{entries: newEntries[:splitIdx:splitIdx]} - splitNode := &sortedMapLeafNode{entries: newEntries[splitIdx:]} + newNode := &sortedMapLeafNode[K, V]{entries: newEntries[:splitIdx:splitIdx]} + splitNode := &sortedMapLeafNode[K, V]{entries: newEntries[splitIdx:]} return newNode, splitNode } // Otherwise return the new leaf node with the updated entry. - return &sortedMapLeafNode{entries: newEntries}, nil + return &sortedMapLeafNode[K, V]{entries: newEntries}, nil } // delete returns a copy of node with key removed. Returns the original node if // the key does not exist. Returns nil if the removed key is the last remaining key. -func (n *sortedMapLeafNode) delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode { +func (n *sortedMapLeafNode[K, V]) delete(key K, c Comparer[K], mutable bool, resized *bool) sortedMapNode[K, V] { idx := n.indexOf(key, c) // Return original node if key is not found. @@ -1984,13 +1995,13 @@ func (n *sortedMapLeafNode) delete(key interface{}, c Comparer, mutable bool, re // Update in-place, if mutable. if mutable { copy(n.entries[idx:], n.entries[idx+1:]) - n.entries[len(n.entries)-1] = mapEntry{} + n.entries[len(n.entries)-1] = mapEntry[K, V]{} n.entries = n.entries[:len(n.entries)-1] return n } // Return copy of node with entry removed. - other := &sortedMapLeafNode{entries: make([]mapEntry, len(n.entries)-1)} + other := &sortedMapLeafNode[K, V]{entries: make([]mapEntry[K, V], len(n.entries)-1)} copy(other.entries[:idx], n.entries[:idx]) copy(other.entries[idx:], n.entries[idx+1:]) return other @@ -1998,36 +2009,36 @@ func (n *sortedMapLeafNode) delete(key interface{}, c Comparer, mutable bool, re // 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 struct { - m *SortedMap // source map +type SortedMapIterator[K constraints.Ordered, V any] struct { + m *SortedMap[K, V] // source map - stack [32]sortedMapIteratorElem // search stack - depth int // stack depth + 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) Done() bool { +func (itr *SortedMapIterator[K, V]) Done() bool { return itr.depth == -1 } // First moves the iterator to the first key/value pair. -func (itr *SortedMapIterator) First() { +func (itr *SortedMapIterator[K, V]) First() { if itr.m.root == nil { itr.depth = -1 return } - itr.stack[0] = sortedMapIteratorElem{node: itr.m.root} + itr.stack[0] = sortedMapIteratorElem[K, V]{node: itr.m.root} itr.depth = 0 itr.first() } // Last moves the iterator to the last key/value pair. -func (itr *SortedMapIterator) Last() { +func (itr *SortedMapIterator[K, V]) Last() { if itr.m.root == nil { itr.depth = -1 return } - itr.stack[0] = sortedMapIteratorElem{node: itr.m.root} + itr.stack[0] = sortedMapIteratorElem[K, V]{node: itr.m.root} itr.depth = 0 itr.last() } @@ -2035,27 +2046,27 @@ func (itr *SortedMapIterator) Last() { // Seek moves the iterator position to the given key in the map. // If the key does not exist then the next key is used. If no more keys exist // then the iteartor is marked as done. -func (itr *SortedMapIterator) Seek(key interface{}) { +func (itr *SortedMapIterator[K, V]) Seek(key K) { if itr.m.root == nil { itr.depth = -1 return } - itr.stack[0] = sortedMapIteratorElem{node: itr.m.root} + itr.stack[0] = sortedMapIteratorElem[K, V]{node: itr.m.root} itr.depth = 0 itr.seek(key) } // Next returns the current key/value pair and moves the iterator forward. // Returns a nil key if the there are no more elements to return. -func (itr *SortedMapIterator) Next() (key, value interface{}) { +func (itr *SortedMapIterator[K, V]) Next() (key K, value V, ok bool) { // Return nil key if iteration is complete. if itr.Done() { - return nil, nil + return key, value, false } // Retrieve current key/value pair. leafElem := &itr.stack[itr.depth] - leafNode := leafElem.node.(*sortedMapLeafNode) + leafNode := leafElem.node.(*sortedMapLeafNode[K, V]) leafEntry := &leafNode.entries[leafElem.index] key, value = leafEntry.key, leafEntry.value @@ -2063,21 +2074,21 @@ func (itr *SortedMapIterator) Next() (key, value interface{}) { itr.next() // Only occurs when iterator is done. - return key, value + return key, value, true } // next moves to the next key. If no keys are after then depth is set to -1. -func (itr *SortedMapIterator) next() { +func (itr *SortedMapIterator[K, V]) next() { for ; itr.depth >= 0; itr.depth-- { elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *sortedMapLeafNode: + case *sortedMapLeafNode[K, V]: if elem.index < len(node.entries)-1 { elem.index++ return } - case *sortedMapBranchNode: + case *sortedMapBranchNode[K, V]: if elem.index < len(node.elems)-1 { elem.index++ itr.stack[itr.depth+1].node = node.elems[elem.index].node @@ -2091,34 +2102,34 @@ func (itr *SortedMapIterator) next() { // Prev returns the current key/value pair and moves the iterator backward. // Returns a nil key if the there are no more elements to return. -func (itr *SortedMapIterator) Prev() (key, value interface{}) { +func (itr *SortedMapIterator[K, V]) Prev() (key K, value V, ok bool) { // Return nil key if iteration is complete. if itr.Done() { - return nil, nil + return key, value, false } // Retrieve current key/value pair. leafElem := &itr.stack[itr.depth] - leafNode := leafElem.node.(*sortedMapLeafNode) + leafNode := leafElem.node.(*sortedMapLeafNode[K, V]) leafEntry := &leafNode.entries[leafElem.index] key, value = leafEntry.key, leafEntry.value itr.prev() - return key, value + return key, value, true } // prev moves to the previous key. If no keys are before then depth is set to -1. -func (itr *SortedMapIterator) prev() { +func (itr *SortedMapIterator[K, V]) prev() { for ; itr.depth >= 0; itr.depth-- { elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *sortedMapLeafNode: + case *sortedMapLeafNode[K, V]: if elem.index > 0 { elem.index-- return } - case *sortedMapBranchNode: + case *sortedMapBranchNode[K, V]: if elem.index > 0 { elem.index-- itr.stack[itr.depth+1].node = node.elems[elem.index].node @@ -2132,16 +2143,16 @@ func (itr *SortedMapIterator) prev() { // first positions the stack to the leftmost key from the current depth. // Elements and indexes below the current depth are assumed to be correct. -func (itr *SortedMapIterator) first() { +func (itr *SortedMapIterator[K, V]) first() { for { elem := &itr.stack[itr.depth] elem.index = 0 switch node := elem.node.(type) { - case *sortedMapBranchNode: - itr.stack[itr.depth+1] = sortedMapIteratorElem{node: node.elems[elem.index].node} + case *sortedMapBranchNode[K, V]: + itr.stack[itr.depth+1] = sortedMapIteratorElem[K, V]{node: node.elems[elem.index].node} itr.depth++ - case *sortedMapLeafNode: + case *sortedMapLeafNode[K, V]: return } } @@ -2149,16 +2160,16 @@ func (itr *SortedMapIterator) first() { // last positions the stack to the rightmost key from the current depth. // Elements and indexes below the current depth are assumed to be correct. -func (itr *SortedMapIterator) last() { +func (itr *SortedMapIterator[K, V]) last() { for { elem := &itr.stack[itr.depth] switch node := elem.node.(type) { - case *sortedMapBranchNode: + case *sortedMapBranchNode[K, V]: elem.index = len(node.elems) - 1 - itr.stack[itr.depth+1] = sortedMapIteratorElem{node: node.elems[elem.index].node} + itr.stack[itr.depth+1] = sortedMapIteratorElem[K, V]{node: node.elems[elem.index].node} itr.depth++ - case *sortedMapLeafNode: + case *sortedMapLeafNode[K, V]: elem.index = len(node.entries) - 1 return } @@ -2167,16 +2178,16 @@ func (itr *SortedMapIterator) last() { // seek positions the stack to the given key from the current depth. // Elements and indexes below the current depth are assumed to be correct. -func (itr *SortedMapIterator) seek(key interface{}) { +func (itr *SortedMapIterator[K, V]) seek(key K) { for { elem := &itr.stack[itr.depth] elem.index = elem.node.indexOf(key, itr.m.comparer) switch node := elem.node.(type) { - case *sortedMapBranchNode: - itr.stack[itr.depth+1] = sortedMapIteratorElem{node: node.elems[elem.index].node} + case *sortedMapBranchNode[K, V]: + itr.stack[itr.depth+1] = sortedMapIteratorElem[K, V]{node: node.elems[elem.index].node} itr.depth++ - case *sortedMapLeafNode: + case *sortedMapLeafNode[K, V]: if elem.index == len(node.entries) { itr.next() } @@ -2186,59 +2197,33 @@ func (itr *SortedMapIterator) seek(key interface{}) { } // sortedMapIteratorElem represents node/index pair in the SortedMapIterator stack. -type sortedMapIteratorElem struct { - node sortedMapNode +type sortedMapIteratorElem[K constraints.Ordered, V any] struct { + node sortedMapNode[K, V] index int } // Hasher hashes keys and checks them for equality. -type Hasher interface { - // Computes a 32-bit hash for key. - Hash(key interface{}) uint32 +type Hasher[K constraints.Ordered] interface { + // Computes a hash for key. + Hash(key K) uint32 // Returns true if a and b are equal. - Equal(a, b interface{}) bool + Equal(a, b K) bool } // NewHasher returns the built-in hasher for a given key type. -func NewHasher(key interface{}) Hasher { +func NewHasher[K constraints.Ordered](key K) Hasher[K] { // Attempt to use non-reflection based hasher first. - switch key.(type) { - case int: - return &intHasher{} - case int8: - return &int8Hasher{} - case int16: - return &int16Hasher{} - case int32: - return &int32Hasher{} - case int64: - return &int64Hasher{} - case uint: - return &uintHasher{} - case uint8: - return &uint8Hasher{} - case uint16: - return &uint16Hasher{} - case uint32: - return &uint32Hasher{} - case uint64: - return &uint64Hasher{} - case string: - return &stringHasher{} - case []byte: - return &byteSliceHasher{} + switch (any(key)).(type) { + case int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, string: + return &defaultHasher[K]{} } // Fallback to reflection-based hasher otherwise. // This is used when caller wraps a type around a primitive type. switch reflect.TypeOf(key).Kind() { - case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: - return &reflectIntHasher{} - case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64: - return &reflectUintHasher{} - case reflect.String: - return &reflectStringHasher{} + case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr, reflect.String: + return &reflectHasher[K]{} } // If no hashers match then panic. @@ -2246,227 +2231,49 @@ func NewHasher(key interface{}) Hasher { panic(fmt.Sprintf("immutable.NewHasher: must set hasher for %T type", key)) } -// intHasher implements Hasher for int keys. -type intHasher struct{} - -// Hash returns a hash for key. -func (h *intHasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(int))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not ints. -func (h *intHasher) Equal(a, b interface{}) bool { - return a.(int) == b.(int) -} - -// int8Hasher implements Hasher for int8 keys. -type int8Hasher struct{} - -// Hash returns a hash for key. -func (h *int8Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(int8))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not int8s. -func (h *int8Hasher) Equal(a, b interface{}) bool { - return a.(int8) == b.(int8) -} - -// int16Hasher implements Hasher for int16 keys. -type int16Hasher struct{} - -// Hash returns a hash for key. -func (h *int16Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(int16))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not int16s. -func (h *int16Hasher) Equal(a, b interface{}) bool { - return a.(int16) == b.(int16) -} - -// int32Hasher implements Hasher for int32 keys. -type int32Hasher struct{} - -// Hash returns a hash for key. -func (h *int32Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(int32))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not int32s. -func (h *int32Hasher) Equal(a, b interface{}) bool { - return a.(int32) == b.(int32) -} - -// int64Hasher implements Hasher for int64 keys. -type int64Hasher struct{} - -// Hash returns a hash for key. -func (h *int64Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(int64))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not int64s. -func (h *int64Hasher) Equal(a, b interface{}) bool { - return a.(int64) == b.(int64) -} - -// uintHasher implements Hasher for uint keys. -type uintHasher struct{} - -// Hash returns a hash for key. -func (h *uintHasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(uint))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not uints. -func (h *uintHasher) Equal(a, b interface{}) bool { - return a.(uint) == b.(uint) -} - -// uint8Hasher implements Hasher for uint8 keys. -type uint8Hasher struct{} - -// Hash returns a hash for key. -func (h *uint8Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(uint8))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not uint8s. -func (h *uint8Hasher) Equal(a, b interface{}) bool { - return a.(uint8) == b.(uint8) -} - -// uint16Hasher implements Hasher for uint16 keys. -type uint16Hasher struct{} - -// Hash returns a hash for key. -func (h *uint16Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(uint16))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not uint16s. -func (h *uint16Hasher) Equal(a, b interface{}) bool { - return a.(uint16) == b.(uint16) -} - -// uint32Hasher implements Hasher for uint32 keys. -type uint32Hasher struct{} - -// Hash returns a hash for key. -func (h *uint32Hasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(key.(uint32))) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not uint32s. -func (h *uint32Hasher) Equal(a, b interface{}) bool { - return a.(uint32) == b.(uint32) -} - -// uint64Hasher implements Hasher for uint64 keys. -type uint64Hasher struct{} - -// Hash returns a hash for key. -func (h *uint64Hasher) Hash(key interface{}) uint32 { - return hashUint64(key.(uint64)) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not uint64s. -func (h *uint64Hasher) Equal(a, b interface{}) bool { - return a.(uint64) == b.(uint64) -} - -// stringHasher implements Hasher for string keys. -type stringHasher struct{} - -// Hash returns a hash for value. -func (h *stringHasher) Hash(value interface{}) uint32 { - var hash uint32 - for i, value := 0, value.(string); i < len(value); i++ { - hash = 31*hash + uint32(value[i]) - } - return hash -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not strings. -func (h *stringHasher) Equal(a, b interface{}) bool { - return a.(string) == b.(string) -} - -// byteSliceHasher implements Hasher for byte slice keys. -type byteSliceHasher struct{} - // Hash returns a hash for value. -func (h *byteSliceHasher) Hash(value interface{}) uint32 { +func hashString(value string) uint32 { var hash uint32 - for i, value := 0, value.([]byte); i < len(value); i++ { + for i, value := 0, value; i < len(value); i++ { hash = 31*hash + uint32(value[i]) } return hash } -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not byte slices. -func (h *byteSliceHasher) Equal(a, b interface{}) bool { - return bytes.Equal(a.([]byte), b.([]byte)) -} - // reflectIntHasher implements a reflection-based Hasher for int keys. -type reflectIntHasher struct{} +type reflectHasher[K constraints.Ordered] struct{} // Hash returns a hash for key. -func (h *reflectIntHasher) Hash(key interface{}) uint32 { - return hashUint64(uint64(reflect.ValueOf(key).Int())) -} - -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not ints. -func (h *reflectIntHasher) Equal(a, b interface{}) bool { - return reflect.ValueOf(a).Int() == reflect.ValueOf(b).Int() -} - -// reflectUintHasher implements a reflection-based Hasher for uint keys. -type reflectUintHasher struct{} - -// Hash returns a hash for key. -func (h *reflectUintHasher) Hash(key interface{}) uint32 { - return hashUint64(reflect.ValueOf(key).Uint()) +func (h *reflectHasher[K]) Hash(key K) uint32 { + switch reflect.TypeOf(key).Kind() { + case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: + return hashUint64(uint64(reflect.ValueOf(key).Int())) + case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: + return hashUint64(reflect.ValueOf(key).Uint()) + case reflect.String: + var hash uint32 + s := reflect.ValueOf(key).String() + for i := 0; i < len(s); i++ { + hash = 31*hash + uint32(s[i]) + } + return hash + } + panic(fmt.Sprintf("immutable.reflectHasher.Hash: reflectHasher does not support %T type", key)) } // Equal returns true if a is equal to b. Otherwise returns false. // Panics if a and b are not ints. -func (h *reflectUintHasher) Equal(a, b interface{}) bool { - return reflect.ValueOf(a).Uint() == reflect.ValueOf(b).Uint() -} - -// reflectStringHasher implements a refletion-based Hasher for string keys. -type reflectStringHasher struct{} - -// Hash returns a hash for value. -func (h *reflectStringHasher) Hash(value interface{}) uint32 { - var hash uint32 - s := reflect.ValueOf(value).String() - for i := 0; i < len(s); i++ { - hash = 31*hash + uint32(s[i]) +func (h *reflectHasher[K]) Equal(a, b K) bool { + switch reflect.TypeOf(a).Kind() { + case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: + return reflect.ValueOf(a).Int() == reflect.ValueOf(b).Int() + case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: + return reflect.ValueOf(a).Uint() == reflect.ValueOf(b).Uint() + case reflect.String: + return reflect.ValueOf(a).String() == reflect.ValueOf(b).String() } - return hash -} + panic(fmt.Sprintf("immutable.reflectHasher.Equal: reflectHasher does not support %T type", a)) -// Equal returns true if a is equal to b. Otherwise returns false. -// Panics if a and b are not strings. -func (h *reflectStringHasher) Equal(a, b interface{}) bool { - return reflect.ValueOf(a).String() == reflect.ValueOf(b).String() } // hashUint64 returns a 32-bit hash for a 64-bit value. @@ -2479,192 +2286,79 @@ func hashUint64(value uint64) uint32 { return uint32(hash) } -// Comparer allows the comparison of two keys for the purpose of sorting. -type Comparer 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 interface{}) int -} +// defaultHasher implements Hasher. +type defaultHasher[K constraints.Ordered] struct{} -// NewComparer returns the built-in comparer for a given key type. -func NewComparer(key interface{}) Comparer { - // Attempt to use non-reflection based comparer first. - switch key.(type) { +// Hash returns a hash for key. +func (h *defaultHasher[K]) Hash(key K) uint32 { + // Attempt to use non-reflection based hasher first. + switch x := (any(key)).(type) { case int: - return &intComparer{} + return hashUint64(uint64(x)) case int8: - return &int8Comparer{} + return hashUint64(uint64(x)) case int16: - return &int16Comparer{} + return hashUint64(uint64(x)) case int32: - return &int32Comparer{} + return hashUint64(uint64(x)) case int64: - return &int64Comparer{} + return hashUint64(uint64(x)) case uint: - return &uintComparer{} + return hashUint64(uint64(x)) case uint8: - return &uint8Comparer{} + return hashUint64(uint64(x)) case uint16: - return &uint16Comparer{} + return hashUint64(uint64(x)) case uint32: - return &uint32Comparer{} + return hashUint64(uint64(x)) case uint64: - return &uint64Comparer{} + return hashUint64(uint64(x)) + case uintptr: + return hashUint64(uint64(x)) case string: - return &stringComparer{} - case []byte: - return &byteSliceComparer{} + return hashString(x) } + panic(fmt.Sprintf("immutable.defaultHasher.Hash: must set comparer for %T type", key)) +} + +// Equal returns true if a is equal to b. Otherwise returns false. +// Panics if a and b are not ints. +func (h *defaultHasher[K]) Equal(a, b K) bool { + return a == b +} +// Comparer allows the comparison of two keys for the purpose of sorting. +type Comparer[K constraints.Ordered] 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. +func NewComparer[K constraints.Ordered](key K) Comparer[K] { + // Attempt to use non-reflection based comparer first. + switch (any(key)).(type) { + case int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, string: + return &defaultComparer[K]{} + } // Fallback to reflection-based comparer otherwise. // This is used when caller wraps a type around a primitive type. switch reflect.TypeOf(key).Kind() { - case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: - return &reflectIntComparer{} - case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64: - return &reflectUintComparer{} - case reflect.String: - return &reflectStringComparer{} + case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr, reflect.String: + return &reflectComparer[K]{} } - // If no comparers match then panic. // This is a compile time issue so it should not return an error. panic(fmt.Sprintf("immutable.NewComparer: must set comparer for %T type", key)) } -// intComparer compares two integers. Implements Comparer. -type intComparer struct{} +// defaultComparer compares two integers. Implements Comparer. +type defaultComparer[K constraints.Ordered] 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. -func (c *intComparer) Compare(a, b interface{}) int { - if i, j := a.(int), b.(int); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// int8Comparer compares two int8 values. Implements Comparer. -type int8Comparer 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 int8. -func (c *int8Comparer) Compare(a, b interface{}) int { - if i, j := a.(int8), b.(int8); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// int16Comparer compares two int16 values. Implements Comparer. -type int16Comparer 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 int16. -func (c *int16Comparer) Compare(a, b interface{}) int { - if i, j := a.(int16), b.(int16); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// int32Comparer compares two int32 values. Implements Comparer. -type int32Comparer 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 int32. -func (c *int32Comparer) Compare(a, b interface{}) int { - if i, j := a.(int32), b.(int32); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// int64Comparer compares two int64 values. Implements Comparer. -type int64Comparer 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 int64. -func (c *int64Comparer) Compare(a, b interface{}) int { - if i, j := a.(int64), b.(int64); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// uintComparer compares two uint values. Implements Comparer. -type uintComparer 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 uint. -func (c *uintComparer) Compare(a, b interface{}) int { - if i, j := a.(uint), b.(uint); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// uint8Comparer compares two uint8 values. Implements Comparer. -type uint8Comparer 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 uint8. -func (c *uint8Comparer) Compare(a, b interface{}) int { - if i, j := a.(uint8), b.(uint8); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// uint16Comparer compares two uint16 values. Implements Comparer. -type uint16Comparer 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 uint16. -func (c *uint16Comparer) Compare(a, b interface{}) int { - if i, j := a.(uint16), b.(uint16); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// uint32Comparer compares two uint32 values. Implements Comparer. -type uint32Comparer 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 uint32. -func (c *uint32Comparer) Compare(a, b interface{}) int { - if i, j := a.(uint32), b.(uint32); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// uint64Comparer compares two uint64 values. Implements Comparer. -type uint64Comparer 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 uint64. -func (c *uint64Comparer) Compare(a, b interface{}) int { - if i, j := a.(uint64), b.(uint64); i < j { +func (c *defaultComparer[K]) Compare(i K, j K) int { + if i < j { return -1 } else if i > j { return 1 @@ -2672,59 +2366,31 @@ func (c *uint64Comparer) Compare(a, b interface{}) int { return 0 } -// stringComparer compares two strings. Implements Comparer. -type stringComparer 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. -func (c *stringComparer) Compare(a, b interface{}) int { - return strings.Compare(a.(string), b.(string)) -} - -// byteSliceComparer compares two byte slices. Implements Comparer. -type byteSliceComparer 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 byte slice. -func (c *byteSliceComparer) Compare(a, b interface{}) int { - return bytes.Compare(a.([]byte), b.([]byte)) -} - // reflectIntComparer compares two int values using reflection. Implements Comparer. -type reflectIntComparer struct{} +type reflectComparer[K constraints.Ordered] 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. -func (c *reflectIntComparer) Compare(a, b interface{}) int { - if i, j := reflect.ValueOf(a).Int(), reflect.ValueOf(b).Int(); i < j { - return -1 - } else if i > j { - return 1 - } - return 0 -} - -// reflectUintComparer compares two uint values using reflection. Implements Comparer. -type reflectUintComparer 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. -func (c *reflectUintComparer) Compare(a, b interface{}) int { - if i, j := reflect.ValueOf(a).Uint(), reflect.ValueOf(b).Uint(); i < j { - return -1 - } else if i > j { - return 1 +func (c *reflectComparer[K]) Compare(a, b K) int { + switch reflect.TypeOf(a).Kind() { + case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: + if i, j := reflect.ValueOf(a).Int(), reflect.ValueOf(b).Int(); i < j { + return -1 + } else if i > j { + return 1 + } + return 0 + case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: + if i, j := reflect.ValueOf(a).Uint(), reflect.ValueOf(b).Uint(); i < j { + return -1 + } else if i > j { + return 1 + } + return 0 + case reflect.String: + return strings.Compare(reflect.ValueOf(a).String(), reflect.ValueOf(b).String()) } - return 0 -} - -// reflectStringComparer compares two string values using reflection. Implements Comparer. -type reflectStringComparer 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. -func (c *reflectStringComparer) Compare(a, b interface{}) int { - return strings.Compare(reflect.ValueOf(a).String(), reflect.ValueOf(b).String()) + panic(fmt.Sprintf("immutable.reflectComparer.Compare: must set comparer for %T type", a)) } func assert(condition bool, message string) { |