New Upstream Release - golang-github-benbjohnson-immutable
Ready changes
Summary
Merged new upstream version: 0.4.3 (was: 0.2.0).
Resulting package
Built on 2023-07-14T01:35 (took 12m15s)
The resulting binary packages can be installed (if you have the apt repository enabled) by running one of:
apt install -t fresh-releases golang-github-benbjohnson-immutable-dev
Lintian Result
Diff
diff --git a/.circleci/config.yml b/.circleci/config.yml
deleted file mode 100644
index da2ca69..0000000
--- a/.circleci/config.yml
+++ /dev/null
@@ -1,13 +0,0 @@
-version: 2
-jobs:
- build:
- docker:
- - image: circleci/golang:1.12
-
- steps:
- - checkout
-
- - run: go test -v -covermode=atomic -coverprofile=coverage.txt .
-
- - run: bash <(curl -s https://codecov.io/bash)
-
diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
new file mode 100644
index 0000000..400912e
--- /dev/null
+++ b/.github/workflows/test.yml
@@ -0,0 +1,29 @@
+on: [pull_request]
+name: test
+jobs:
+ short:
+ strategy:
+ matrix:
+ os: [ubuntu-latest, windows-latest]
+ runs-on: ${{ matrix.os }}
+ steps:
+ - name: Install Go
+ uses: actions/setup-go@v2
+ with:
+ go-version: 1.18.x
+ - name: Checkout code
+ uses: actions/checkout@v2
+ - name: Short test
+ run: go test -short .
+
+ full:
+ runs-on: ubuntu-latest
+ steps:
+ - name: Install Go
+ uses: actions/setup-go@v2
+ with:
+ go-version: 1.18.x
+ - name: Checkout code
+ uses: actions/checkout@v2
+ - name: Test
+ run: go test -parallel 10 .
diff --git a/README.md b/README.md
index 5e7925f..177d37d 100644
--- a/README.md
+++ b/README.md
@@ -1,8 +1,8 @@
-Immutable ![release](https://img.shields.io/github/release/benbjohnson/immutable.svg?style=flat-square) ![CircleCI](https://img.shields.io/circleci/project/github/benbjohnson/immutable/master.svg?style=flat-square) ![coverage](https://img.shields.io/codecov/c/github/benbjohnson/immutable/master.svg?style=flat-square) ![license](https://img.shields.io/github/license/benbjohnson/immutable.svg?style=flat-square)
+Immutable ![release](https://img.shields.io/github/release/benbjohnson/immutable.svg) ![test](https://github.com/benbjohnson/immutable/workflows/test/badge.svg) ![coverage](https://img.shields.io/codecov/c/github/benbjohnson/immutable/master.svg) ![license](https://img.shields.io/github/license/benbjohnson/immutable.svg)
=========
-This repository contains immutable collection types for Go. It includes
-`List`, `Map`, and `SortedMap` implementations. Immutable collections can
+This repository contains *generic* immutable collection types for Go. It includes
+`List`, `Map`, `SortedMap`, `Set` and `SortedSet` implementations. Immutable collections can
provide efficient, lock free sharing of data by requiring that edits to the
collections return new collections.
@@ -34,7 +34,7 @@ prepending is as efficient as appending.
```go
// Create a list with 3 elements.
-l := immutable.NewList()
+l := immutable.NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Prepend("baz")
@@ -46,7 +46,7 @@ fmt.Println(l.Get(2)) // "bar"
```
Note that each change to the list results in a new list being created. These
-lists are all snapshots at that point in time and cannot be changed so they
+lists are all snapshots at that point in time and cannot be changed so they
are safe to share between multiple goroutines.
### Updating list elements
@@ -57,7 +57,7 @@ new list to a new variable. You can see that our old `l` variable retains a
snapshot of the original value.
```go
-l := immutable.NewList()
+l := immutable.NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
newList := l.Set(2, "baz")
@@ -95,7 +95,7 @@ Below is an example of iterating over all elements of our list from above:
```go
itr := l.Iterator()
for !itr.Done() {
- index, value := itr.Next()
+ index, value, _ := itr.Next()
fmt.Printf("Index %d equals %v\n", index, value)
}
@@ -115,7 +115,7 @@ a list in-place until you are ready to use it. This can improve bulk list
building by 10x or more.
```go
-b := immutable.NewListBuilder(immutable.NewList())
+b := immutable.NewListBuilder[string]()
b.Append("foo")
b.Append("bar")
b.Set(2, "baz")
@@ -125,8 +125,7 @@ fmt.Println(l.Get(0)) // "foo"
fmt.Println(l.Get(1)) // "baz"
```
-Lists are safe to use even after you continue to use the builder. It is also
-safe to build on top of existing lists.
+Builders are invalid after the call to `List()`.
## Map
@@ -136,9 +135,9 @@ is implemented to act similarly to the built-in Go `map` type. It is implemented
as a [Hash-Array Mapped Trie](https://lampwww.epfl.ch/papers/idealhashtrees.pdf).
Maps require a `Hasher` to hash keys and check for equality. There are built-in
-hasher implementations for `int`, `string`, and `[]byte` keys. You may pass in
-a `nil` hasher to `NewMap()` if you are using one of these key types.
-
+hasher implementations for most primitive types such as `int`, `uint`, and
+`string` keys. You may pass in a `nil` hasher to `NewMap()` if you are using
+one of these key types.
### Setting map key/value pairs
@@ -151,7 +150,7 @@ the value as well as a flag indicating if the key existed. The flag is useful
to check if a `nil` value was set for a key versus a key did not exist.
```go
-m := immutable.NewMap(nil)
+m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)
m = m.Set("jane", 300) // overwrite
@@ -175,7 +174,7 @@ Keys may be removed from the map by using the `Delete()` method. If the key does
not exist then the original map is returned instead of a new one.
```go
-m := immutable.NewMap(nil)
+m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Delete("jane")
@@ -193,7 +192,7 @@ pairs in the collection. Unlike Go maps, iterators are deterministic when
iterating over key/value pairs.
```go
-m := immutable.NewMap(nil)
+m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)
@@ -215,11 +214,11 @@ keys generate the same hash.
### Efficiently building maps
If you are executing multiple mutations on a map, it can be much more efficient
-to use the `MapBuilder`. It uses nearly the same API as `Map` except that it
-updates a map in-place until you are ready to use it.
+to use the `MapBuilder`. It uses nearly the same API as `Map` except that it
+updates a map in-place until you are ready to use it.
```go
-b := immutable.NewMapBuilder(immutable.NewMap(nil))
+b := immutable.NewMapBuilder[string,int](nil)
b.Set("foo", 100)
b.Set("bar", 200)
b.Set("foo", 300)
@@ -229,13 +228,12 @@ fmt.Println(m.Get("foo")) // "300"
fmt.Println(m.Get("bar")) // "200"
```
-Maps are safe to use even after you continue to use the builder. You can
-also build on top of existing maps too.
+Builders are invalid after the call to `Map()`.
### Implementing a custom Hasher
-If you need to use a key type besides `int`, `string`, or `[]byte` then you'll
+If you need to use a key type besides `int`, `uint`, or `string` then you'll
need to create a custom `Hasher` implementation and pass it to `NewMap()` on
creation.
@@ -243,13 +241,14 @@ Hashers are fairly simple. They only need to generate hashes for a given key
and check equality given two keys.
```go
-type Hasher interface {
- Hash(key interface{}) uint32
- Equal(a, b interface{}) bool
+type Hasher[K any] interface {
+ Hash(key K) uint32
+ Equal(a, b K) bool
}
```
-Please see the internal `intHasher`, `stringHasher`, and `byteSliceHasher` for examples.
+Please see the internal `intHasher`, `uintHasher`, `stringHasher`, and
+`byteSliceHasher` for examples.
## Sorted Map
@@ -259,8 +258,8 @@ Unlike the `Map`, however, keys can be iterated over in-order. It is implemented
as a B+tree.
Sorted maps require a `Comparer` to sort keys and check for equality. There are
-built-in comparer implementations for `int`, `string`, and `[]byte` keys. You
-may pass a `nil` comparer to `NewSortedMap()` if you are using one of these key
+built-in comparer implementations for `int`, `uint`, and `string` keys. You may
+pass a `nil` comparer to `NewSortedMap()` if you are using one of these key
types.
The API is identical to the `Map` implementation. The sorted map also has a
@@ -269,7 +268,7 @@ companion `SortedMapBuilder` for more efficiently building maps.
### Implementing a custom Comparer
-If you need to use a key type besides `int`, `string`, or `[]byte` then you'll
+If you need to use a key type besides `int`, `uint`, or `string` or derived types, then you'll
need to create a custom `Comparer` implementation and pass it to
`NewSortedMap()` on creation.
@@ -278,13 +277,36 @@ Comparers on have one method—`Compare()`. It works the same as the
`1` if a is greater than `b`, and returns `0` if `a` is equal to `b`.
```go
-type Comparer interface {
- Compare(a, b interface{}) int
+type Comparer[K any] interface {
+ Compare(a, b K) int
}
```
-Please see the internal `intComparer`, `stringComparer`, and `byteSliceComparer` for examples.
+Please see the internal `defaultComparer` for an example, bearing in mind that it works for several types.
+
+## Set
+
+The `Set` represents a collection of unique values, and it is implemented as a
+wrapper around a `Map[T, struct{}]`.
+
+Like Maps, Sets require a `Hasher` to hash keys and check for equality. There are built-in
+hasher implementations for most primitive types such as `int`, `uint`, and
+`string` keys. You may pass in a `nil` hasher to `NewMap()` if you are using
+one of these key types.
+
+
+## Sorted Set
+
+The `SortedSet` represents a sorted collection of unique values.
+Unlike the `Set`, however, keys can be iterated over in-order. It is implemented
+as a B+tree.
+
+Sorted sets require a `Comparer` to sort values and check for equality. There are
+built-in comparer implementations for `int`, `uint`, and `string` keys. You may
+pass a `nil` comparer to `NewSortedSet()` if you are using one of these key
+types.
+The API is identical to the `Set` implementation.
## Contributing
diff --git a/debian/changelog b/debian/changelog
index 280a586..96775ab 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,9 +1,10 @@
-golang-github-benbjohnson-immutable (0.2.0-3) UNRELEASED; urgency=low
+golang-github-benbjohnson-immutable (0.4.3-1) UNRELEASED; urgency=low
* Set upstream metadata fields: Bug-Database, Bug-Submit, Repository,
Repository-Browse.
+ * New upstream release.
- -- Debian Janitor <janitor@jelmer.uk> Tue, 08 Sep 2020 01:30:36 -0000
+ -- Debian Janitor <janitor@jelmer.uk> Fri, 14 Jul 2023 01:23:38 -0000
golang-github-benbjohnson-immutable (0.2.0-2) unstable; urgency=medium
diff --git a/go.mod b/go.mod
index ea97e54..4de8d58 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,7 @@
module github.com/benbjohnson/immutable
-go 1.12
+go 1.18
+
+require golang.org/x/exp v0.0.0-20220518171630-0b5c67f07fdf // indirect
+
+retract v0.4.2
diff --git a/go.sum b/go.sum
index e69de29..a35495c 100644
--- a/go.sum
+++ b/go.sum
@@ -0,0 +1,2 @@
+golang.org/x/exp v0.0.0-20220518171630-0b5c67f07fdf h1:oXVg4h2qJDd9htKxb5SCpFBHLipW6hXmL3qpUixS2jw=
+golang.org/x/exp v0.0.0-20220518171630-0b5c67f07fdf/go.mod h1:yh0Ynu2b5ZUe3MQfp2nM0ecK7wsgouWTDN0FNeJuIys=
diff --git a/immutable.go b/immutable.go
index c1a8aef..1642de3 100644
--- a/immutable.go
+++ b/immutable.go
@@ -1,6 +1,6 @@
// Package immutable provides immutable collection types.
//
-// Introduction
+// # Introduction
//
// Immutable collections provide an efficient, safe way to share collections
// of data while minimizing locks. The collections in this package provide
@@ -14,7 +14,7 @@
// with Go's built-in collection types so please evaluate for your specific
// use.
//
-// Collection Types
+// # Collection Types
//
// The List type provides an API similar to Go slices. They allow appending,
// prepending, and updating of elements. Elements can also be fetched by index
@@ -28,7 +28,7 @@
// provides iteration over unsorted keys. Maps improved performance and memory
// usage as compared to SortedMaps.
//
-// Hashing and Sorting
+// # Hashing and Sorting
//
// Map types require the use of a Hasher implementation to calculate hashes for
// their keys and check for key equality. SortedMaps require the use of a
@@ -42,49 +42,55 @@
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 any] 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 any](values ...T) *List[T] {
+ l := &List[T]{
+ root: &listLeafNode[T]{},
+ }
+ for _, value := range values {
+ l.append(value, true)
}
+ return l
}
// 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))
}
@@ -94,11 +100,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))
}
@@ -111,11 +117,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()
@@ -123,7 +129,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
}
@@ -134,12 +140,12 @@ func (l *List) append(value interface{}, mutable bool) *List {
return other
}
-// Prepend returns a new list with value added to the beginning of the list.
-func (l *List) Prepend(value interface{}) *List {
+// Prepend returns a new list with value(s) added to the beginning of the 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()
@@ -147,7 +153,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)
@@ -167,11 +173,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))
@@ -206,7 +212,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.
@@ -217,71 +223,75 @@ 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 Lists.
-//
-// Lists returned from the builder are safe to use even after you continue to
-// use the builder. However, for efficiency, you should only retrieve your list
-// after you have completed building it.
-type ListBuilder struct {
- list *List // current state
- mutable bool // if true, next mutation will operate in-place.
+// ListBuilder represents an efficient builder for creating new Lists.
+type ListBuilder[T any] struct {
+ list *List[T] // current state
}
-// NewListBuilder returns a new instance of ListBuilder to build on a base list.
-func NewListBuilder(list *List) *ListBuilder {
- return &ListBuilder{list: list}
+// NewListBuilder returns a new instance of ListBuilder.
+func NewListBuilder[T any]() *ListBuilder[T] {
+ return &ListBuilder[T]{list: NewList[T]()}
}
// List returns the current copy of the list.
-// The returned list is safe to use even if after the builder continues to be used.
-func (b *ListBuilder) List() *List {
+// The builder should not be used again after the list after this call.
+func (b *ListBuilder[T]) List() *List[T] {
+ assert(b.list != nil, "immutable.ListBuilder.List(): duplicate call to fetch list")
list := b.list
- b.mutable = false
+ b.list = nil
return 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)
}
// 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{}) {
- b.list = b.list.set(index, value, b.mutable)
- b.mutable = true
+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{}) {
- b.list = b.list.append(value, b.mutable)
- b.mutable = true
+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{}) {
- b.list = b.list.prepend(value, b.mutable)
- b.mutable = true
+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) {
- b.list = b.list.slice(start, end, b.mutable)
- b.mutable = true
+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[T]) Iterator() *ListIterator[T] {
+ assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
+ return b.list.Iterator()
}
// Constants for bit shifts used for levels in the List trie.
@@ -292,53 +302,53 @@ const (
)
// listNode represents either a branch or leaf node in a List.
-type listNode interface {
+type listNode[T any] 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 any](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 any] 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 {
@@ -350,7 +360,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.
@@ -368,7 +378,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.
@@ -386,7 +396,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
@@ -395,14 +405,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:][:])
}
@@ -413,7 +423,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
@@ -422,14 +432,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])
}
@@ -440,22 +450,24 @@ 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 any] struct {
+ children [listNodeSize]T
+ // bitset with ones at occupied positions, position 0 is the LSB
+ occupied uint32
}
// 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 {
@@ -463,88 +475,86 @@ func (n *listLeafNode) set(index int, v interface{}, mutable bool) listNode {
other = &tmp
}
other.children[idx] = v
+ other.occupied |= 1 << idx
return other
}
// 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
- for i := 0; i < idx; i++ {
- if n.children[i] != nil {
- return true
- }
- }
- return false
+ return bits.TrailingZeros32(n.occupied) < idx
}
// 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
- for i := idx + 1; i < len(n.children); i++ {
- if n.children[i] != nil {
- return true
- }
- }
- return false
+ lastSetPos := 31 - bits.LeadingZeros32(n.occupied)
+ return lastSetPos > idx
}
// 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]{occupied: n.occupied}
copy(other.children[idx:][:], n.children[idx:][:])
}
+ // Set the first idx bits to 0.
+ other.occupied &= ^((1 << idx) - 1)
return other
}
-// deleteBefore returns a new node with all elements before index removed.
-func (n *listLeafNode) deleteAfter(index int, mutable bool) listNode {
+// deleteAfter returns a new node with all elements after index removed.
+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]{occupied: n.occupied}
copy(other.children[:idx+1][:], n.children[:idx+1][:])
}
+ // Set bits after idx to 0. idx < 31 because n.containsAfter(index) == true.
+ other.occupied &= (1 << (idx + 1)) - 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 any] 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)
}
@@ -552,7 +562,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)
}
@@ -561,7 +571,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))
@@ -569,22 +579,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++
@@ -604,15 +615,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--
@@ -632,26 +644,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 any] struct {
+ node listNode[T]
index int
}
@@ -672,28 +684,42 @@ 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, 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, V any](hasher Hasher[K]) *Map[K, V] {
+ return &Map[K, V]{
+ hasher: hasher,
+ }
+}
+
+// NewMapOf returns a new instance of Map, containing a map of provided entries.
+//
+// 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 NewMapOf[K comparable, V any](hasher Hasher[K], entries map[K]V) *Map[K, V] {
+ m := &Map[K, V]{
hasher: hasher,
}
+ for k, v := range entries {
+ m.set(k, v, true)
+ }
+ return m
}
// 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
}
@@ -701,9 +727,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)
@@ -713,24 +740,15 @@ 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 {
- switch key.(type) {
- case int:
- hasher = &intHasher{}
- case string:
- hasher = &stringHasher{}
- case []byte:
- hasher = &byteSliceHasher{}
- default:
- panic(fmt.Sprintf("immutable.Map.Set: must set hasher for %T type", key))
- }
+ hasher = NewHasher(key)
}
// Generate copy if necessary.
@@ -743,7 +761,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
}
@@ -759,11 +777,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
@@ -789,88 +807,92 @@ 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.
-//
-// Maps returned from the builder are safe to use even after you continue to
-// use the builder. However, for efficiency, you should only retrieve your map
-// after you have completed building it.
-type MapBuilder struct {
- m *Map // current state
- mutable bool // if true, next mutation will operate in-place.
+type MapBuilder[K, V any] struct {
+ m *Map[K, V] // current state
}
-// NewMapBuilder returns a new instance of MapBuilder to build on a base map.
-func NewMapBuilder(m *Map) *MapBuilder {
- return &MapBuilder{m: m}
+// NewMapBuilder returns a new instance of MapBuilder.
+func NewMapBuilder[K, V any](hasher Hasher[K]) *MapBuilder[K, V] {
+ return &MapBuilder[K, V]{m: NewMap[K, V](hasher)}
}
-// Map 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 *MapBuilder) Map() *Map {
+// Map returns the underlying map. Only call once.
+// Builder is invalid after call. Will panic on second invocation.
+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.mutable = false
+ b.m = nil
return m
}
// 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{}) {
- b.m = b.m.set(key, value, b.mutable)
- b.mutable = true
+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{}) {
- b.m = b.m.delete(key, b.mutable)
- b.mutable = true
+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[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, 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, 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, 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 +902,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 +923,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 +933,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 +974,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 +989,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, 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 +1006,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,7 +1024,7 @@ 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 {
@@ -1012,7 +1034,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u
// 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 +1061,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 +1078,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 +1115,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 +1124,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 +1135,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, 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 +1187,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 +1204,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 +1231,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, 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, V any](keyHash uint32, key K, value V) *mapValueNode[K, V] {
+ return &mapValueNode[K, V]{
keyHash: keyHash,
key: key,
value: value,
@@ -1225,14 +1247,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 +1263,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 +1279,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 +1303,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, 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 +1325,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 +1372,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 +1385,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 +1395,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 +1409,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, 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, 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, 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 +1456,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 +1484,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 +1508,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 +1519,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 +1533,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 +1559,8 @@ func (itr *MapIterator) first() {
}
// mapIteratorElem represents a node/index pair in the MapIterator stack.
-type mapIteratorElem struct {
- node mapNode
+type mapIteratorElem[K, V any] struct {
+ node mapNode[K, V]
index int
}
@@ -1551,54 +1573,60 @@ 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, 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, V any](comparer Comparer[K]) *SortedMap[K, V] {
+ return &SortedMap[K, V]{
+ comparer: comparer,
+ }
+}
+
+// NewSortedMapOf returns a new instance of SortedMap, containing a map of provided entries.
+//
+// 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 NewSortedMapOf[K comparable, V any](comparer Comparer[K], entries map[K]V) *SortedMap[K, V] {
+ m := &SortedMap[K, V]{
comparer: comparer,
}
+ for k, v := range entries {
+ m.set(k, v, true)
+ }
+ return m
}
// 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 {
- switch key.(type) {
- case int:
- comparer = &intComparer{}
- case string:
- comparer = &stringComparer{}
- case []byte:
- comparer = &byteSliceComparer{}
- default:
- panic(fmt.Sprintf("immutable.SortedMap.Set: must set comparer for %T type", key))
- }
+ comparer = NewComparer(key)
}
// Create copy, if necessary.
@@ -1611,7 +1639,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
}
@@ -1634,11 +1662,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
@@ -1664,101 +1692,105 @@ 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.
-//
-// Maps returned from the builder are safe to use even after you continue to
-// use the builder. However, for efficiency, you should only retrieve your map
-// after you have completed building it.
-type SortedMapBuilder struct {
- m *SortedMap // current state
- mutable bool // if true, next mutation will operate in-place.
+type SortedMapBuilder[K, V any] struct {
+ m *SortedMap[K, V] // current state
}
-// NewSortedMapBuilder returns a new instance of SortedMapBuilder to build on a base map.
-func NewSortedMapBuilder(m *SortedMap) *SortedMapBuilder {
- return &SortedMapBuilder{m: m}
+// NewSortedMapBuilder returns a new instance of SortedMapBuilder.
+func NewSortedMapBuilder[K, V any](comparer Comparer[K]) *SortedMapBuilder[K, V] {
+ return &SortedMapBuilder[K, V]{m: NewSortedMap[K, V](comparer)}
}
// 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.mutable = false
+ b.m = nil
return m
}
// 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{}) {
- b.m = b.m.set(key, value, b.mutable)
- b.mutable = true
+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{}) {
- b.m = b.m.delete(key, b.mutable)
- b.mutable = true
+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[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, 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, 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, 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
}
@@ -1766,13 +1798,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.
@@ -1780,18 +1812,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
@@ -1799,23 +1831,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,
}
@@ -1824,8 +1856,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
}
@@ -1835,7 +1867,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.
@@ -1854,13 +1886,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
@@ -1868,49 +1900,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, 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, 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.
@@ -1919,7 +1951,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
@@ -1928,16 +1960,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
@@ -1945,34 +1977,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.
@@ -1989,13 +2021,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
@@ -2003,36 +2035,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, 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()
}
@@ -2040,27 +2072,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
@@ -2068,21 +2100,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
@@ -2096,34 +2128,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
@@ -2137,16 +2169,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
}
}
@@ -2154,16 +2186,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
}
@@ -2172,16 +2204,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()
}
@@ -2191,68 +2223,83 @@ func (itr *SortedMapIterator) seek(key interface{}) {
}
// sortedMapIteratorElem represents node/index pair in the SortedMapIterator stack.
-type sortedMapIteratorElem struct {
- node sortedMapNode
+type sortedMapIteratorElem[K, 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 any] 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
}
-// intHasher implements Hasher for int keys.
-type intHasher struct{}
+// NewHasher returns the built-in hasher for a given key type.
+func NewHasher[K any](key K) Hasher[K] {
+ // Attempt to use non-reflection based hasher first.
+ switch (any(key)).(type) {
+ case int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, string:
+ return &defaultHasher[K]{}
+ }
-// Hash returns a hash for key.
-func (h *intHasher) Hash(key interface{}) uint32 {
- return hashUint64(uint64(key.(int)))
-}
+ // 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, reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr, reflect.String:
+ return &reflectHasher[K]{}
+ }
-// 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)
+ // If no hashers match then panic.
+ // This is a compile time issue so it should not return an error.
+ panic(fmt.Sprintf("immutable.NewHasher: must set hasher for %T type", key))
}
-// stringHasher implements Hasher for string keys.
-type stringHasher struct{}
-
// Hash returns a hash for value.
-func (h *stringHasher) Hash(value interface{}) uint32 {
+func hashString(value string) uint32 {
var hash uint32
- for i, value := 0, value.(string); 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 strings.
-func (h *stringHasher) Equal(a, b interface{}) bool {
- return a.(string) == b.(string)
-}
+// reflectIntHasher implements a reflection-based Hasher for keys.
+type reflectHasher[K any] struct{}
-// byteSliceHasher implements Hasher for string keys.
-type byteSliceHasher struct{}
-
-// Hash returns a hash for value.
-func (h *byteSliceHasher) Hash(value interface{}) uint32 {
- var hash uint32
- for i, value := 0, value.([]byte); i < len(value); i++ {
- hash = 31*hash + uint32(value[i])
+// Hash returns a hash for key.
+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
}
- 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 byte slices.
-func (h *byteSliceHasher) Equal(a, b interface{}) bool {
- return bytes.Equal(a.([]byte), b.([]byte))
+// Panics if a and b are not int-ish or string-ish.
+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()
+ }
+ panic(fmt.Sprintf("immutable.reflectHasher.Equal: reflectHasher does not support %T type", a))
+
}
// hashUint64 returns a 32-bit hash for a 64-bit value.
@@ -2265,20 +2312,112 @@ func hashUint64(value uint64) uint32 {
return uint32(hash)
}
+// defaultHasher implements Hasher.
+type defaultHasher[K any] struct{}
+
+// Hash returns a hash for key.
+func (h *defaultHasher[K]) Hash(key K) uint32 {
+ switch x := (any(key)).(type) {
+ case int:
+ return hashUint64(uint64(x))
+ case int8:
+ return hashUint64(uint64(x))
+ case int16:
+ return hashUint64(uint64(x))
+ case int32:
+ return hashUint64(uint64(x))
+ case int64:
+ return hashUint64(uint64(x))
+ case uint:
+ return hashUint64(uint64(x))
+ case uint8:
+ return hashUint64(uint64(x))
+ case uint16:
+ return hashUint64(uint64(x))
+ case uint32:
+ return hashUint64(uint64(x))
+ case uint64:
+ return hashUint64(uint64(x))
+ case uintptr:
+ return hashUint64(uint64(x))
+ case string:
+ 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 comparable.
+func (h *defaultHasher[K]) Equal(a, b K) bool {
+ return any(a) == any(b)
+}
+
// Comparer allows the comparison of two keys for the purpose of sorting.
-type Comparer interface {
+type Comparer[K any] interface {
// Returns -1 if a is less than b, returns 1 if a is greater than b,
// and returns 0 if a is equal to b.
- Compare(a, b interface{}) int
+ Compare(a, b K) int
}
-// intComparer compares two integers. Implements Comparer.
-type intComparer struct{}
+// NewComparer returns the built-in comparer for a given key type.
+// Note that only int-ish and string-ish types are supported, despite the 'comparable' constraint.
+// Attempts to use other types will result in a panic - users should define their own Comparers for these cases.
+func NewComparer[K any](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, 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))
+}
+
+// defaultComparer compares two values (int-ish and string-ish types are supported). Implements Comparer.
+type defaultComparer[K any] struct{}
// Compare returns -1 if a is less than b, returns 1 if a is greater than b, and
-// returns 0 if a is equal to b. Panic if a or b is not an int.
-func (c *intComparer) Compare(a, b interface{}) int {
- if i, j := a.(int), b.(int); i < j {
+// returns 0 if a is equal to b. Panic if a or b is not a string or int* type
+func (c *defaultComparer[K]) Compare(i K, j K) int {
+ switch x := (any(i)).(type) {
+ case int:
+ return defaultCompare(x, (any(j)).(int))
+ case int8:
+ return defaultCompare(x, (any(j)).(int8))
+ case int16:
+ return defaultCompare(x, (any(j)).(int16))
+ case int32:
+ return defaultCompare(x, (any(j)).(int32))
+ case int64:
+ return defaultCompare(x, (any(j)).(int64))
+ case uint:
+ return defaultCompare(x, (any(j)).(uint))
+ case uint8:
+ return defaultCompare(x, (any(j)).(uint8))
+ case uint16:
+ return defaultCompare(x, (any(j)).(uint16))
+ case uint32:
+ return defaultCompare(x, (any(j)).(uint32))
+ case uint64:
+ return defaultCompare(x, (any(j)).(uint64))
+ case uintptr:
+ return defaultCompare(x, (any(j)).(uintptr))
+ case string:
+ return defaultCompare(x, (any(j)).(string))
+ }
+ panic(fmt.Sprintf("immutable.defaultComparer: must set comparer for %T type", i))
+}
+
+// defaultCompare only operates on constraints.Ordered.
+// For other types, users should bring their own comparers
+func defaultCompare[K constraints.Ordered](i, j K) int {
+ if i < j {
return -1
} else if i > j {
return 1
@@ -2286,20 +2425,35 @@ func (c *intComparer) Compare(a, b interface{}) int {
return 0
}
-// stringComparer compares two strings. Implements Comparer.
-type stringComparer struct{}
+// reflectIntComparer compares two values using reflection. Implements Comparer.
+type reflectComparer[K any] struct{}
// Compare returns -1 if a is less than b, returns 1 if a is greater than b, and
-// returns 0 if a is equal to b. Panic if a or b is not a string.
-func (c *stringComparer) Compare(a, b interface{}) int {
- return strings.Compare(a.(string), b.(string))
+// returns 0 if a is equal to b. Panic if a or b is not an int-ish or string-ish type.
+func (c *reflectComparer[K]) Compare(a, b K) int {
+ 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())
+ }
+ panic(fmt.Sprintf("immutable.reflectComparer.Compare: must set comparer for %T type", a))
}
-// 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))
+func assert(condition bool, message string) {
+ if !condition {
+ panic(message)
+ }
}
diff --git a/immutable_test.go b/immutable_test.go
index c6dfc13..581d4d8 100644
--- a/immutable_test.go
+++ b/immutable_test.go
@@ -6,6 +6,8 @@ import (
"math/rand"
"sort"
"testing"
+
+ "golang.org/x/exp/constraints"
)
var (
@@ -15,13 +17,13 @@ var (
func TestList(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
- if size := NewList().Len(); size != 0 {
+ if size := NewList[string]().Len(); size != 0 {
t.Fatalf("unexpected size: %d", size)
}
})
t.Run("Shallow", func(t *testing.T) {
- list := NewList()
+ list := NewList[string]()
list = list.Append("foo")
if v := list.Get(0); v != "foo" {
t.Fatalf("unexpected value: %v", v)
@@ -40,7 +42,7 @@ func TestList(t *testing.T) {
})
t.Run("Deep", func(t *testing.T) {
- list := NewList()
+ list := NewList[int]()
var array []int
for i := 0; i < 100000; i++ {
list = list.Append(i)
@@ -51,14 +53,14 @@ func TestList(t *testing.T) {
t.Fatalf("List.Len()=%d, exp %d", got, exp)
}
for j := range array {
- if got, exp := list.Get(j).(int), array[j]; got != exp {
+ if got, exp := list.Get(j), array[j]; got != exp {
t.Fatalf("%d. List.Get(%d)=%d, exp %d", len(array), j, got, exp)
}
}
})
t.Run("Set", func(t *testing.T) {
- list := NewList()
+ list := NewList[string]()
list = list.Append("foo")
list = list.Append("bar")
@@ -78,7 +80,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Get(-1)
}()
@@ -91,7 +93,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Get(1)
}()
@@ -104,7 +106,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Set(1, "bar")
}()
@@ -117,7 +119,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Slice(2, 3)
}()
@@ -130,7 +132,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Slice(1, 3)
}()
@@ -143,7 +145,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l.Slice(2, 1)
@@ -154,7 +156,7 @@ func TestList(t *testing.T) {
})
t.Run("SliceBeginning", func(t *testing.T) {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Slice(1, 2)
@@ -169,7 +171,7 @@ func TestList(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l.Iterator().Seek(-1)
}()
@@ -178,6 +180,62 @@ func TestList(t *testing.T) {
}
})
+ t.Run("TestSliceFreesReferences", func(t *testing.T) {
+ /* Test that the leaf node in a sliced list contains zero'ed entries at
+ * the correct positions. To do this we directly access the internal
+ * tree structure of the list.
+ */
+ l := NewList[*int]()
+ var ints [5]int
+ for i := 0; i < 5; i++ {
+ l = l.Append(&ints[i])
+ }
+ sl := l.Slice(2, 4)
+
+ var findLeaf func(listNode[*int]) *listLeafNode[*int]
+ findLeaf = func(n listNode[*int]) *listLeafNode[*int] {
+ switch n := n.(type) {
+ case *listBranchNode[*int]:
+ if n.children[0] == nil {
+ t.Fatal("Failed to find leaf node due to nil child")
+ }
+ return findLeaf(n.children[0])
+ case *listLeafNode[*int]:
+ return n
+ default:
+ panic("Unexpected case")
+ }
+ }
+
+ leaf := findLeaf(sl.root)
+ if leaf.occupied != 0b1100 {
+ t.Errorf("Expected occupied to be 1100, was %032b", leaf.occupied)
+ }
+
+ for i := 0; i < listNodeSize; i++ {
+ if 2 <= i && i < 4 {
+ if leaf.children[i] != &ints[i] {
+ t.Errorf("Position %v does not contain the right pointer?", i)
+ }
+ } else if leaf.children[i] != nil {
+ t.Errorf("Expected position %v to be cleared, was %v", i, leaf.children[i])
+ }
+ }
+ })
+
+ t.Run("AppendImmutable", func(t *testing.T) {
+ outer_l := NewList[int]()
+ for N := 0; N < 1_000; N++ {
+ l1 := outer_l.Append(0)
+ outer_l.Append(1)
+ if actual := l1.Get(N); actual != 0 {
+ t.Fatalf("Append mutates list with %d elements. Got %d instead of 0", N, actual)
+ }
+
+ outer_l = outer_l.Append(0)
+ }
+ })
+
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
l := NewTList()
for i := 0; i < 100000; i++ {
@@ -204,16 +262,16 @@ func TestList(t *testing.T) {
// TList represents a list that operates on a standard Go slice & immutable list.
type TList struct {
- im, prev *List
- builder *ListBuilder
+ im, prev *List[int]
+ builder *ListBuilder[int]
std []int
}
// NewTList returns a new instance of TList.
func NewTList() *TList {
return &TList{
- im: NewList(),
- builder: NewListBuilder(NewList()),
+ im: NewList[int](),
+ builder: NewListBuilder[int](),
}
}
@@ -280,33 +338,29 @@ func (l *TList) Validate() error {
return fmt.Errorf("Len()=%v, expected %d", got, exp)
}
- bl := l.builder.List()
for i := range l.std {
if got, exp := l.im.Get(i), l.std[i]; got != exp {
return fmt.Errorf("Get(%d)=%v, expected %v", i, got, exp)
} else if got, exp := l.builder.Get(i), l.std[i]; got != exp {
- return fmt.Errorf("Builder.Get(%d)=%v, expected %v", i, got, exp)
- } else if got, exp := bl.Get(i), l.std[i]; got != exp {
return fmt.Errorf("Builder.List/Get(%d)=%v, expected %v", i, got, exp)
}
}
- if err := l.validateForwardIterator("basic", l.im); err != nil {
+ if err := l.validateForwardIterator("basic", l.im.Iterator()); err != nil {
return err
- } else if err := l.validateBackwardIterator("basic", l.im); err != nil {
+ } else if err := l.validateBackwardIterator("basic", l.im.Iterator()); err != nil {
return err
}
- if err := l.validateForwardIterator("builder", bl); err != nil {
+ if err := l.validateForwardIterator("builder", l.builder.Iterator()); err != nil {
return err
- } else if err := l.validateBackwardIterator("builder", bl); err != nil {
+ } else if err := l.validateBackwardIterator("builder", l.builder.Iterator()); err != nil {
return err
}
return nil
}
-func (l *TList) validateForwardIterator(typ string, list *List) error {
- itr := list.Iterator()
+func (l *TList) validateForwardIterator(typ string, itr *ListIterator[int]) error {
for i := range l.std {
if j, v := itr.Next(); i != j || l.std[i] != v {
return fmt.Errorf("ListIterator.Next()=<%v,%v>, expected <%v,%v> [%s]", j, v, i, l.std[i], typ)
@@ -317,14 +371,13 @@ func (l *TList) validateForwardIterator(typ string, list *List) error {
return fmt.Errorf("ListIterator.Done()=%v, expected %v [%s]", v, done, typ)
}
}
- if i, v := itr.Next(); i != -1 || v != nil {
+ if i, v := itr.Next(); i != -1 || v != 0 {
return fmt.Errorf("ListIterator.Next()=<%v,%v>, expected DONE [%s]", i, v, typ)
}
return nil
}
-func (l *TList) validateBackwardIterator(typ string, list *List) error {
- itr := list.Iterator()
+func (l *TList) validateBackwardIterator(typ string, itr *ListIterator[int]) error {
itr.Last()
for i := len(l.std) - 1; i >= 0; i-- {
if j, v := itr.Prev(); i != j || l.std[i] != v {
@@ -336,7 +389,7 @@ func (l *TList) validateBackwardIterator(typ string, list *List) error {
return fmt.Errorf("ListIterator.Done()=%v, expected %v [%s]", v, done, typ)
}
}
- if i, v := itr.Prev(); i != -1 || v != nil {
+ if i, v := itr.Prev(); i != -1 || v != 0 {
return fmt.Errorf("ListIterator.Prev()=<%v,%v>, expected DONE [%s]", i, v, typ)
}
return nil
@@ -344,7 +397,7 @@ func (l *TList) validateBackwardIterator(typ string, list *List) error {
func BenchmarkList_Append(b *testing.B) {
b.ReportAllocs()
- l := NewList()
+ l := NewList[int]()
for i := 0; i < b.N; i++ {
l = l.Append(i)
}
@@ -352,7 +405,7 @@ func BenchmarkList_Append(b *testing.B) {
func BenchmarkList_Prepend(b *testing.B) {
b.ReportAllocs()
- l := NewList()
+ l := NewList[int]()
for i := 0; i < b.N; i++ {
l = l.Prepend(i)
}
@@ -361,7 +414,7 @@ func BenchmarkList_Prepend(b *testing.B) {
func BenchmarkList_Set(b *testing.B) {
const n = 10000
- l := NewList()
+ l := NewList[int]()
for i := 0; i < 10000; i++ {
l = l.Append(i)
}
@@ -375,7 +428,7 @@ func BenchmarkList_Set(b *testing.B) {
func BenchmarkList_Iterator(b *testing.B) {
const n = 10000
- l := NewList()
+ l := NewList[int]()
for i := 0; i < 10000; i++ {
l = l.Append(i)
}
@@ -422,7 +475,7 @@ func BenchmarkBuiltinSlice_Append(b *testing.B) {
func BenchmarkListBuilder_Append(b *testing.B) {
b.ReportAllocs()
- builder := NewListBuilder(NewList())
+ builder := NewListBuilder[int]()
for i := 0; i < b.N; i++ {
builder.Append(i)
}
@@ -430,7 +483,7 @@ func BenchmarkListBuilder_Append(b *testing.B) {
func BenchmarkListBuilder_Prepend(b *testing.B) {
b.ReportAllocs()
- builder := NewListBuilder(NewList())
+ builder := NewListBuilder[int]()
for i := 0; i < b.N; i++ {
builder.Prepend(i)
}
@@ -439,7 +492,7 @@ func BenchmarkListBuilder_Prepend(b *testing.B) {
func BenchmarkListBuilder_Set(b *testing.B) {
const n = 10000
- builder := NewListBuilder(NewList())
+ builder := NewListBuilder[int]()
for i := 0; i < 10000; i++ {
builder.Append(i)
}
@@ -452,7 +505,7 @@ func BenchmarkListBuilder_Set(b *testing.B) {
}
func ExampleList_Append() {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Append("baz")
@@ -467,7 +520,7 @@ func ExampleList_Append() {
}
func ExampleList_Prepend() {
- l := NewList()
+ l := NewList[string]()
l = l.Prepend("foo")
l = l.Prepend("bar")
l = l.Prepend("baz")
@@ -482,7 +535,7 @@ func ExampleList_Prepend() {
}
func ExampleList_Set() {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Set(1, "baz")
@@ -495,7 +548,7 @@ func ExampleList_Set() {
}
func ExampleList_Slice() {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Append("baz")
@@ -509,7 +562,7 @@ func ExampleList_Slice() {
}
func ExampleList_Iterator() {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Append("baz")
@@ -526,7 +579,7 @@ func ExampleList_Iterator() {
}
func ExampleList_Iterator_reverse() {
- l := NewList()
+ l := NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Append("baz")
@@ -544,7 +597,7 @@ func ExampleList_Iterator_reverse() {
}
func ExampleListBuilder_Append() {
- b := NewListBuilder(NewList())
+ b := NewListBuilder[string]()
b.Append("foo")
b.Append("bar")
b.Append("baz")
@@ -560,7 +613,7 @@ func ExampleListBuilder_Append() {
}
func ExampleListBuilder_Prepend() {
- b := NewListBuilder(NewList())
+ b := NewListBuilder[string]()
b.Prepend("foo")
b.Prepend("bar")
b.Prepend("baz")
@@ -576,7 +629,7 @@ func ExampleListBuilder_Prepend() {
}
func ExampleListBuilder_Set() {
- b := NewListBuilder(NewList())
+ b := NewListBuilder[string]()
b.Append("foo")
b.Append("bar")
b.Set(1, "baz")
@@ -590,7 +643,7 @@ func ExampleListBuilder_Set() {
}
func ExampleListBuilder_Slice() {
- b := NewListBuilder(NewList())
+ b := NewListBuilder[string]()
b.Append("foo")
b.Append("bar")
b.Append("baz")
@@ -607,8 +660,8 @@ func ExampleListBuilder_Slice() {
// Ensure node can support overwrites as it expands.
func TestInternal_mapNode_Overwrite(t *testing.T) {
const n = 1000
- var h intHasher
- var node mapNode = &mapArrayNode{}
+ var h defaultHasher[int]
+ var node mapNode[int, int] = &mapArrayNode[int, int]{}
for i := 0; i < n; i++ {
var resized bool
node = node.set(i, i, 0, h.Hash(i), &h, false, &resized)
@@ -642,11 +695,11 @@ func TestInternal_mapNode_Overwrite(t *testing.T) {
func TestInternal_mapArrayNode(t *testing.T) {
// Ensure 8 or fewer elements stays in an array node.
t.Run("Append", func(t *testing.T) {
- var h intHasher
- n := &mapArrayNode{}
+ var h defaultHasher[int]
+ n := &mapArrayNode[int, int]{}
for i := 0; i < 8; i++ {
var resized bool
- n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode)
+ n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode[int, int])
if !resized {
t.Fatal("expected resize")
}
@@ -661,11 +714,11 @@ func TestInternal_mapArrayNode(t *testing.T) {
// Ensure 8 or fewer elements stays in an array node when inserted in reverse.
t.Run("Prepend", func(t *testing.T) {
- var h intHasher
- n := &mapArrayNode{}
+ var h defaultHasher[int]
+ n := &mapArrayNode[int, int]{}
for i := 7; i >= 0; i-- {
var resized bool
- n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode)
+ n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode[int, int])
if !resized {
t.Fatal("expected resize")
}
@@ -680,8 +733,8 @@ func TestInternal_mapArrayNode(t *testing.T) {
// Ensure array can transition between node types.
t.Run("Expand", func(t *testing.T) {
- var h intHasher
- var n mapNode = &mapArrayNode{}
+ var h defaultHasher[int]
+ var n mapNode[int, int] = &mapArrayNode[int, int]{}
for i := 0; i < 100; i++ {
var resized bool
n = n.set(i, i, 0, h.Hash(i), &h, false, &resized)
@@ -699,8 +752,8 @@ func TestInternal_mapArrayNode(t *testing.T) {
// Ensure deleting elements returns the correct new node.
RunRandom(t, "Delete", func(t *testing.T, rand *rand.Rand) {
- var h intHasher
- var n mapNode = &mapArrayNode{}
+ var h defaultHasher[int]
+ var n mapNode[int, int] = &mapArrayNode[int, int]{}
for i := 0; i < 8; i++ {
var resized bool
n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized)
@@ -718,7 +771,7 @@ func TestInternal_mapArrayNode(t *testing.T) {
func TestInternal_mapValueNode(t *testing.T) {
t.Run("Simple", func(t *testing.T) {
- var h intHasher
+ var h defaultHasher[int]
n := newMapValueNode(h.Hash(2), 2, 3)
if v, ok := n.get(2, 0, h.Hash(2), &h); !ok {
t.Fatal("expected ok")
@@ -728,10 +781,10 @@ func TestInternal_mapValueNode(t *testing.T) {
})
t.Run("KeyEqual", func(t *testing.T) {
- var h intHasher
+ var h defaultHasher[int]
var resized bool
n := newMapValueNode(h.Hash(2), 2, 3)
- other := n.set(2, 4, 0, h.Hash(2), &h, false, &resized).(*mapValueNode)
+ other := n.set(2, 4, 0, h.Hash(2), &h, false, &resized).(*mapValueNode[int, int])
if other == n {
t.Fatal("expected new node")
} else if got, exp := other.keyHash, h.Hash(2); got != exp {
@@ -746,13 +799,13 @@ func TestInternal_mapValueNode(t *testing.T) {
})
t.Run("KeyHashEqual", func(t *testing.T) {
- h := &mockHasher{
- hash: func(value interface{}) uint32 { return 1 },
- equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+ h := &mockHasher[int]{
+ hash: func(value int) uint32 { return 1 },
+ equal: func(a, b int) bool { return a == b },
}
var resized bool
n := newMapValueNode(h.Hash(2), 2, 3)
- other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapHashCollisionNode)
+ other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapHashCollisionNode[int, int])
if got, exp := other.keyHash, h.Hash(2); got != exp {
t.Fatalf("keyHash=%v, expected %v", got, exp)
} else if got, exp := len(other.entries), 2; got != exp {
@@ -775,10 +828,10 @@ func TestInternal_mapValueNode(t *testing.T) {
t.Run("MergeNode", func(t *testing.T) {
// Inserting into a node with a different index in the mask should split into a bitmap node.
t.Run("NoConflict", func(t *testing.T) {
- var h intHasher
+ var h defaultHasher[int]
var resized bool
n := newMapValueNode(h.Hash(2), 2, 3)
- other := n.set(4, 5, 0, h.Hash(4), &h, false, &resized).(*mapBitmapIndexedNode)
+ other := n.set(4, 5, 0, h.Hash(4), &h, false, &resized).(*mapBitmapIndexedNode[int, int])
if got, exp := other.bitmap, uint32(0x14); got != exp {
t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
} else if got, exp := len(other.nodes), 2; got != exp {
@@ -786,14 +839,14 @@ func TestInternal_mapValueNode(t *testing.T) {
} else if !resized {
t.Fatal("expected resize")
}
- if node, ok := other.nodes[0].(*mapValueNode); !ok {
+ if node, ok := other.nodes[0].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
} else if got, exp := node.key, 2; got != exp {
t.Fatalf("key[0]=%v, expected %v", got, exp)
} else if got, exp := node.value, 3; got != exp {
t.Fatalf("value[0]=%v, expected %v", got, exp)
}
- if node, ok := other.nodes[1].(*mapValueNode); !ok {
+ if node, ok := other.nodes[1].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[1]=%T, unexpected type", other.nodes[1])
} else if got, exp := node.key, 4; got != exp {
t.Fatalf("key[1]=%v, expected %v", got, exp)
@@ -802,19 +855,19 @@ func TestInternal_mapValueNode(t *testing.T) {
}
// Ensure both values can be read.
- if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v.(int) != 3 {
+ if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v != 3 {
t.Fatalf("Get(2)=<%v,%v>", v, ok)
- } else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v.(int) != 5 {
+ } else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v != 5 {
t.Fatalf("Get(4)=<%v,%v>", v, ok)
}
})
// Reversing the nodes from NoConflict should yield the same result.
t.Run("NoConflictReverse", func(t *testing.T) {
- var h intHasher
+ var h defaultHasher[int]
var resized bool
n := newMapValueNode(h.Hash(4), 4, 5)
- other := n.set(2, 3, 0, h.Hash(2), &h, false, &resized).(*mapBitmapIndexedNode)
+ other := n.set(2, 3, 0, h.Hash(2), &h, false, &resized).(*mapBitmapIndexedNode[int, int])
if got, exp := other.bitmap, uint32(0x14); got != exp {
t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
} else if got, exp := len(other.nodes), 2; got != exp {
@@ -822,14 +875,14 @@ func TestInternal_mapValueNode(t *testing.T) {
} else if !resized {
t.Fatal("expected resize")
}
- if node, ok := other.nodes[0].(*mapValueNode); !ok {
+ if node, ok := other.nodes[0].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
} else if got, exp := node.key, 2; got != exp {
t.Fatalf("key[0]=%v, expected %v", got, exp)
} else if got, exp := node.value, 3; got != exp {
t.Fatalf("value[0]=%v, expected %v", got, exp)
}
- if node, ok := other.nodes[1].(*mapValueNode); !ok {
+ if node, ok := other.nodes[1].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[1]=%T, unexpected type", other.nodes[1])
} else if got, exp := node.key, 4; got != exp {
t.Fatalf("key[1]=%v, expected %v", got, exp)
@@ -838,22 +891,22 @@ func TestInternal_mapValueNode(t *testing.T) {
}
// Ensure both values can be read.
- if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v.(int) != 3 {
+ if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v != 3 {
t.Fatalf("Get(2)=<%v,%v>", v, ok)
- } else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v.(int) != 5 {
+ } else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v != 5 {
t.Fatalf("Get(4)=<%v,%v>", v, ok)
}
})
// Inserting a node with the same mask index should nest an additional level of bitmap nodes.
t.Run("Conflict", func(t *testing.T) {
- h := &mockHasher{
- hash: func(value interface{}) uint32 { return uint32(value.(int)) << 5 },
- equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+ h := &mockHasher[int]{
+ hash: func(value int) uint32 { return uint32(value << 5) },
+ equal: func(a, b int) bool { return a == b },
}
var resized bool
n := newMapValueNode(h.Hash(2), 2, 3)
- other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapBitmapIndexedNode)
+ other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapBitmapIndexedNode[int, int])
if got, exp := other.bitmap, uint32(0x01); got != exp { // mask is zero, expect first slot.
t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
} else if got, exp := len(other.nodes), 1; got != exp {
@@ -861,19 +914,19 @@ func TestInternal_mapValueNode(t *testing.T) {
} else if !resized {
t.Fatal("expected resize")
}
- child, ok := other.nodes[0].(*mapBitmapIndexedNode)
+ child, ok := other.nodes[0].(*mapBitmapIndexedNode[int, int])
if !ok {
t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
}
- if node, ok := child.nodes[0].(*mapValueNode); !ok {
+ if node, ok := child.nodes[0].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[0]=%T, unexpected type", child.nodes[0])
} else if got, exp := node.key, 2; got != exp {
t.Fatalf("key[0]=%v, expected %v", got, exp)
} else if got, exp := node.value, 3; got != exp {
t.Fatalf("value[0]=%v, expected %v", got, exp)
}
- if node, ok := child.nodes[1].(*mapValueNode); !ok {
+ if node, ok := child.nodes[1].(*mapValueNode[int, int]); !ok {
t.Fatalf("node[1]=%T, unexpected type", child.nodes[1])
} else if got, exp := node.key, 4; got != exp {
t.Fatalf("key[1]=%v, expected %v", got, exp)
@@ -882,9 +935,9 @@ func TestInternal_mapValueNode(t *testing.T) {
}
// Ensure both values can be read.
- if v, ok := other.get(2, 0, h.Hash(2), h); !ok || v.(int) != 3 {
+ if v, ok := other.get(2, 0, h.Hash(2), h); !ok || v != 3 {
t.Fatalf("Get(2)=<%v,%v>", v, ok)
- } else if v, ok := other.get(4, 0, h.Hash(4), h); !ok || v.(int) != 5 {
+ } else if v, ok := other.get(4, 0, h.Hash(4), h); !ok || v != 5 {
t.Fatalf("Get(4)=<%v,%v>", v, ok)
} else if v, ok := other.get(10, 0, h.Hash(10), h); ok {
t.Fatalf("Get(10)=<%v,%v>, expected no value", v, ok)
@@ -895,8 +948,8 @@ func TestInternal_mapValueNode(t *testing.T) {
func TestMap_Get(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
- m := NewMap(nil)
- if v, ok := m.Get(100); ok || v != nil {
+ m := NewMap[int, string](nil)
+ if v, ok := m.Get(100); ok {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
}
})
@@ -904,26 +957,42 @@ func TestMap_Get(t *testing.T) {
func TestMap_Set(t *testing.T) {
t.Run("Simple", func(t *testing.T) {
- m := NewMap(nil)
+ m := NewMap[int, string](nil)
itr := m.Iterator()
if !itr.Done() {
t.Fatal("MapIterator.Done()=true, expected false")
- } else if k, v := itr.Next(); k != nil || v != nil {
+ } else if k, v, ok := itr.Next(); ok {
t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
}
})
t.Run("Simple", func(t *testing.T) {
- m := NewMap(nil)
+ m := NewMap[int, string](nil)
m = m.Set(100, "foo")
if v, ok := m.Get(100); !ok || v != "foo" {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
}
})
+ t.Run("Multi", func(t *testing.T) {
+ m := NewMapOf(nil, map[int]string{1: "foo"})
+ itr := m.Iterator()
+ if itr.Done() {
+ t.Fatal("MapIterator.Done()=false, expected true")
+ }
+ if k, v, ok := itr.Next(); !ok {
+ t.Fatalf("MapIterator.Next()!=ok, expected ok")
+ } else if k != 1 || v != "foo" {
+ t.Fatalf("MapIterator.Next()=<%v,%v>, expected <1, \"foo\">", k, v)
+ }
+ if k, v, ok := itr.Next(); ok {
+ t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
+ }
+ })
+
t.Run("VerySmall", func(t *testing.T) {
const n = 6
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -936,7 +1005,7 @@ func TestMap_Set(t *testing.T) {
// NOTE: Array nodes store entries in insertion order.
itr := m.Iterator()
for i := 0; i < n; i++ {
- if k, v := itr.Next(); k != i || v != i+1 {
+ if k, v, ok := itr.Next(); !ok || k != i || v != i+1 {
t.Fatalf("MapIterator.Next()=<%v,%v>, exp <%v,%v>", k, v, i, i+1)
}
}
@@ -947,7 +1016,7 @@ func TestMap_Set(t *testing.T) {
t.Run("Small", func(t *testing.T) {
const n = 1000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -964,7 +1033,7 @@ func TestMap_Set(t *testing.T) {
}
const n = 1000000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -976,7 +1045,7 @@ func TestMap_Set(t *testing.T) {
})
t.Run("StringKeys", func(t *testing.T) {
- m := NewMap(nil)
+ m := NewMap[string, string](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", "bat")
m = m.Set("", "EMPTY")
@@ -992,35 +1061,6 @@ func TestMap_Set(t *testing.T) {
}
})
- t.Run("ByteSliceKeys", func(t *testing.T) {
- m := NewMap(nil)
- m = m.Set([]byte("foo"), "bar")
- m = m.Set([]byte("baz"), "bat")
- m = m.Set([]byte(""), "EMPTY")
- if v, ok := m.Get([]byte("foo")); !ok || v != "bar" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- } else if v, ok := m.Get([]byte("baz")); !ok || v != "bat" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- } else if v, ok := m.Get([]byte("")); !ok || v != "EMPTY" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- }
- if v, ok := m.Get([]byte("no_such_key")); ok {
- t.Fatalf("expected no value: <%v,%v>", v, ok)
- }
- })
-
- t.Run("NoDefaultHasher", func(t *testing.T) {
- var r string
- func() {
- defer func() { r = recover().(string) }()
- m := NewMap(nil)
- m = m.Set(uint64(100), "bar")
- }()
- if r != `immutable.Map.Set: must set hasher for uint64 type` {
- t.Fatalf("unexpected panic: %q", r)
- }
- })
-
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
m := NewTestMap()
for i := 0; i < 10000; i++ {
@@ -1039,8 +1079,12 @@ func TestMap_Set(t *testing.T) {
// Ensure map can support overwrites as it expands.
func TestMap_Overwrite(t *testing.T) {
+ if testing.Short() {
+ t.Skip("short mode")
+ }
+
const n = 10000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
// Set original value.
m = m.Set(i, i)
@@ -1057,11 +1101,21 @@ func TestMap_Overwrite(t *testing.T) {
t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
}
}
+
+ t.Run("Simple", func(t *testing.T) {
+ m := NewMap[int, string](nil)
+ itr := m.Iterator()
+ if !itr.Done() {
+ t.Fatal("MapIterator.Done()=true, expected false")
+ } else if k, v, ok := itr.Next(); ok {
+ t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
+ }
+ })
}
func TestMap_Delete(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
- m := NewMap(nil)
+ m := NewMap[string, int](nil)
other := m.Delete("foo")
if m != other {
t.Fatal("expected same map")
@@ -1069,7 +1123,7 @@ func TestMap_Delete(t *testing.T) {
})
t.Run("Simple", func(t *testing.T) {
- m := NewMap(nil)
+ m := NewMap[int, string](nil)
m = m.Set(100, "foo")
if v, ok := m.Get(100); !ok || v != "foo" {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
@@ -1078,7 +1132,7 @@ func TestMap_Delete(t *testing.T) {
t.Run("Small", func(t *testing.T) {
const n = 1000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1095,7 +1149,7 @@ func TestMap_Delete(t *testing.T) {
t.Skip("skipping: short")
}
const n = 1000000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1121,9 +1175,6 @@ func TestMap_Delete(t *testing.T) {
m.Set(m.NewKey(rand), rand.Intn(10000))
}
}
- if err := m.Validate(); err != nil {
- t.Fatal(err)
- }
// Delete all and verify they are gone.
keys := make([]int, len(m.keys))
@@ -1140,12 +1191,16 @@ func TestMap_Delete(t *testing.T) {
// Ensure map works even with hash conflicts.
func TestMap_LimitedHash(t *testing.T) {
+ if testing.Short() {
+ t.Skip("skipping: short")
+ }
+
t.Run("Immutable", func(t *testing.T) {
- h := mockHasher{
- hash: func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF },
- equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+ h := mockHasher[int]{
+ hash: func(value int) uint32 { return hashUint64(uint64(value)) % 0xFF },
+ equal: func(a, b int) bool { return a == b },
}
- m := NewMap(&h)
+ m := NewMap[int, int](&h)
rand := rand.New(rand.NewSource(0))
keys := rand.Perm(100000)
@@ -1169,8 +1224,8 @@ func TestMap_LimitedHash(t *testing.T) {
// Verify iteration.
itr := m.Iterator()
for !itr.Done() {
- if k, v := itr.Next(); v != k.(int)*2 {
- t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2)
+ if k, v, ok := itr.Next(); !ok || v != k*2 {
+ t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k*2)
}
}
@@ -1194,11 +1249,11 @@ func TestMap_LimitedHash(t *testing.T) {
})
t.Run("Builder", func(t *testing.T) {
- h := mockHasher{
- hash: func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF },
- equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+ h := mockHasher[int]{
+ hash: func(value int) uint32 { return hashUint64(uint64(value)) },
+ equal: func(a, b int) bool { return a == b },
}
- b := NewMapBuilder(NewMap(&h))
+ b := NewMapBuilder[int, int](&h)
rand := rand.New(rand.NewSource(0))
keys := rand.Perm(100000)
@@ -1220,10 +1275,10 @@ func TestMap_LimitedHash(t *testing.T) {
}
// Verify iteration.
- itr := b.Map().Iterator()
+ itr := b.Iterator()
for !itr.Done() {
- if k, v := itr.Next(); v != k.(int)*2 {
- t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2)
+ if k, v, ok := itr.Next(); !ok || v != k*2 {
+ t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k*2)
}
}
@@ -1232,12 +1287,6 @@ func TestMap_LimitedHash(t *testing.T) {
t.Fatal("expected no value")
}
- // Verify delete non-existent key works.
- m := b.Map()
- if b.Delete(10000000 + 1); m != b.Map() {
- t.Fatal("expected no change")
- }
-
// Remove all keys.
for _, key := range keys {
b.Delete(key)
@@ -1250,16 +1299,16 @@ func TestMap_LimitedHash(t *testing.T) {
// TMap represents a combined immutable and stdlib map.
type TMap struct {
- im, prev *Map
- builder *MapBuilder
+ im, prev *Map[int, int]
+ builder *MapBuilder[int, int]
std map[int]int
keys []int
}
func NewTestMap() *TMap {
return &TMap{
- im: NewMap(nil),
- builder: NewMapBuilder(NewMap(nil)),
+ im: NewMap[int, int](nil),
+ builder: NewMapBuilder[int, int](nil),
std: make(map[int]int),
}
}
@@ -1319,20 +1368,19 @@ func (m *TMap) Validate() error {
return fmt.Errorf("builder key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
}
}
- if err := m.validateIterator(m.im); err != nil {
+ if err := m.validateIterator(m.im.Iterator()); err != nil {
return fmt.Errorf("basic: %s", err)
- } else if err := m.validateIterator(m.builder.Map()); err != nil {
+ } else if err := m.validateIterator(m.builder.Iterator()); err != nil {
return fmt.Errorf("builder: %s", err)
}
return nil
}
-func (m *TMap) validateIterator(mm *Map) error {
+func (m *TMap) validateIterator(itr *MapIterator[int, int]) error {
other := make(map[int]int)
- itr := mm.Iterator()
for !itr.Done() {
- k, v := itr.Next()
- other[k.(int)] = v.(int)
+ k, v, _ := itr.Next()
+ other[k] = v
}
if len(other) != len(m.std) {
return fmt.Errorf("map iterator size mismatch: %v!=%v", len(m.std), len(other))
@@ -1342,7 +1390,7 @@ func (m *TMap) validateIterator(mm *Map) error {
return fmt.Errorf("map iterator mismatch: key=%v, %v!=%v", k, v, other[k])
}
}
- if k, v := itr.Next(); k != nil || v != nil {
+ if k, v, ok := itr.Next(); ok {
return fmt.Errorf("map iterator returned key/value after done: <%v/%v>", k, v)
}
return nil
@@ -1373,7 +1421,7 @@ func BenchmarkBuiltinMap_Delete(b *testing.B) {
func BenchmarkMap_Set(b *testing.B) {
b.ReportAllocs()
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < b.N; i++ {
m = m.Set(i, i)
}
@@ -1382,7 +1430,7 @@ func BenchmarkMap_Set(b *testing.B) {
func BenchmarkMap_Delete(b *testing.B) {
const n = 10000000
- builder := NewMapBuilder(NewMap(nil))
+ builder := NewMapBuilder[int, int](nil)
for i := 0; i < n; i++ {
builder.Set(i, i)
}
@@ -1397,7 +1445,7 @@ func BenchmarkMap_Delete(b *testing.B) {
func BenchmarkMap_Iterator(b *testing.B) {
const n = 10000
- m := NewMap(nil)
+ m := NewMap[int, int](nil)
for i := 0; i < 10000; i++ {
m = m.Set(i, i)
}
@@ -1417,7 +1465,7 @@ func BenchmarkMap_Iterator(b *testing.B) {
func BenchmarkMapBuilder_Set(b *testing.B) {
b.ReportAllocs()
- builder := NewMapBuilder(NewMap(nil))
+ builder := NewMapBuilder[int, int](nil)
for i := 0; i < b.N; i++ {
builder.Set(i, i)
}
@@ -1426,7 +1474,7 @@ func BenchmarkMapBuilder_Set(b *testing.B) {
func BenchmarkMapBuilder_Delete(b *testing.B) {
const n = 10000000
- builder := NewMapBuilder(NewMap(nil))
+ builder := NewMapBuilder[int, int](nil)
for i := 0; i < n; i++ {
builder.Set(i, i)
}
@@ -1439,7 +1487,7 @@ func BenchmarkMapBuilder_Delete(b *testing.B) {
}
func ExampleMap_Set() {
- m := NewMap(nil)
+ m := NewMap[string, any](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", 100)
@@ -1458,7 +1506,7 @@ func ExampleMap_Set() {
}
func ExampleMap_Delete() {
- m := NewMap(nil)
+ m := NewMap[string, any](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", 100)
m = m.Delete("baz")
@@ -1474,7 +1522,7 @@ func ExampleMap_Delete() {
}
func ExampleMap_Iterator() {
- m := NewMap(nil)
+ m := NewMap[string, int](nil)
m = m.Set("apple", 100)
m = m.Set("grape", 200)
m = m.Set("kiwi", 300)
@@ -1487,7 +1535,7 @@ func ExampleMap_Iterator() {
itr := m.Iterator()
for !itr.Done() {
- k, v := itr.Next()
+ k, v, _ := itr.Next()
fmt.Println(k, v)
}
// Output:
@@ -1503,7 +1551,7 @@ func ExampleMap_Iterator() {
}
func ExampleMapBuilder_Set() {
- b := NewMapBuilder(NewMap(nil))
+ b := NewMapBuilder[string, any](nil)
b.Set("foo", "bar")
b.Set("baz", 100)
@@ -1523,7 +1571,7 @@ func ExampleMapBuilder_Set() {
}
func ExampleMapBuilder_Delete() {
- b := NewMapBuilder(NewMap(nil))
+ b := NewMapBuilder[string, any](nil)
b.Set("foo", "bar")
b.Set("baz", 100)
b.Delete("baz")
@@ -1541,12 +1589,12 @@ func ExampleMapBuilder_Delete() {
func TestInternalSortedMapLeafNode(t *testing.T) {
RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
- var cmpr intComparer
- var node sortedMapNode = &sortedMapLeafNode{}
+ var cmpr defaultComparer[int]
+ var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
var keys []int
for _, i := range rand.Perm(32) {
var resized bool
- var splitNode sortedMapNode
+ var splitNode sortedMapNode[int, int]
node, splitNode = node.set(i, i*10, &cmpr, false, &resized)
if !resized {
t.Fatal("expected resize")
@@ -1576,8 +1624,9 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
})
RunRandom(t, "Overwrite", func(t *testing.T, rand *rand.Rand) {
- var cmpr intComparer
- var node sortedMapNode = &sortedMapLeafNode{}
+ var cmpr defaultComparer[int]
+ var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
+
for _, i := range rand.Perm(32) {
var resized bool
node, _ = node.set(i, i*2, &cmpr, false, &resized)
@@ -1599,9 +1648,9 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
})
t.Run("Split", func(t *testing.T) {
- // Fill leaf node.
- var cmpr intComparer
- var node sortedMapNode = &sortedMapLeafNode{}
+ // Fill leaf node. var cmpr defaultComparer[int]
+ var cmpr defaultComparer[int]
+ var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
for i := 0; i < 32; i++ {
var resized bool
node, _ = node.set(i, i*10, &cmpr, false, &resized)
@@ -1612,7 +1661,7 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
newNode, splitNode := node.set(32, 320, &cmpr, false, &resized)
// Verify node contents.
- newLeafNode, ok := newNode.(*sortedMapLeafNode)
+ newLeafNode, ok := newNode.(*sortedMapLeafNode[int, int])
if !ok {
t.Fatalf("unexpected node type: %T", newLeafNode)
} else if n := len(newLeafNode.entries); n != 16 {
@@ -1625,7 +1674,7 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
}
// Verify split node contents.
- splitLeafNode, ok := splitNode.(*sortedMapLeafNode)
+ splitLeafNode, ok := splitNode.(*sortedMapLeafNode[int, int])
if !ok {
t.Fatalf("unexpected split node type: %T", splitLeafNode)
} else if n := len(splitLeafNode.entries); n != 17 {
@@ -1649,17 +1698,17 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
sort.Ints(keys[:2]) // ensure first two keys are sorted for initial insert.
// Initialize branch with two leafs.
- var cmpr intComparer
- leaf0 := &sortedMapLeafNode{entries: []mapEntry{{key: keys[0], value: keys[0] * 10}}}
- leaf1 := &sortedMapLeafNode{entries: []mapEntry{{key: keys[1], value: keys[1] * 10}}}
- var node sortedMapNode = newSortedMapBranchNode(leaf0, leaf1)
+ var cmpr defaultComparer[int]
+ leaf0 := &sortedMapLeafNode[int, int]{entries: []mapEntry[int, int]{{key: keys[0], value: keys[0] * 10}}}
+ leaf1 := &sortedMapLeafNode[int, int]{entries: []mapEntry[int, int]{{key: keys[1], value: keys[1] * 10}}}
+ var node sortedMapNode[int, int] = newSortedMapBranchNode[int, int](leaf0, leaf1)
sort.Ints(keys)
for _, i := range rand.Perm(len(keys)) {
key := keys[i]
var resized bool
- var splitNode sortedMapNode
+ var splitNode sortedMapNode[int, int]
node, splitNode = node.set(key, key*10, &cmpr, false, &resized)
if key == leaf0.entries[0].key || key == leaf1.entries[0].key {
if resized {
@@ -1690,16 +1739,16 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
t.Run("Split", func(t *testing.T) {
// Generate leaf nodes.
- var cmpr intComparer
- children := make([]sortedMapNode, 32)
+ var cmpr defaultComparer[int]
+ children := make([]sortedMapNode[int, int], 32)
for i := range children {
- leaf := &sortedMapLeafNode{entries: make([]mapEntry, 32)}
+ leaf := &sortedMapLeafNode[int, int]{entries: make([]mapEntry[int, int], 32)}
for j := range leaf.entries {
- leaf.entries[j] = mapEntry{key: (i * 32) + j, value: ((i * 32) + j) * 100}
+ leaf.entries[j] = mapEntry[int, int]{key: (i * 32) + j, value: ((i * 32) + j) * 100}
}
children[i] = leaf
}
- var node sortedMapNode = newSortedMapBranchNode(children...)
+ var node sortedMapNode[int, int] = newSortedMapBranchNode(children...)
// Add one more and expect split.
var resized bool
@@ -1707,14 +1756,14 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
// Verify node contents.
var idx int
- newBranchNode, ok := newNode.(*sortedMapBranchNode)
+ newBranchNode, ok := newNode.(*sortedMapBranchNode[int, int])
if !ok {
t.Fatalf("unexpected node type: %T", newBranchNode)
} else if n := len(newBranchNode.elems); n != 16 {
t.Fatalf("unexpected child elems len: %d", n)
}
for i, elem := range newBranchNode.elems {
- child, ok := elem.node.(*sortedMapLeafNode)
+ child, ok := elem.node.(*sortedMapLeafNode[int, int])
if !ok {
t.Fatalf("unexpected child type")
}
@@ -1727,14 +1776,14 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
}
// Verify split node contents.
- splitBranchNode, ok := splitNode.(*sortedMapBranchNode)
+ splitBranchNode, ok := splitNode.(*sortedMapBranchNode[int, int])
if !ok {
t.Fatalf("unexpected split node type: %T", splitBranchNode)
} else if n := len(splitBranchNode.elems); n != 17 {
t.Fatalf("unexpected split node elem len: %d", n)
}
for i, elem := range splitBranchNode.elems {
- child, ok := elem.node.(*sortedMapLeafNode)
+ child, ok := elem.node.(*sortedMapLeafNode[int, int])
if !ok {
t.Fatalf("unexpected split node child type")
}
@@ -1750,8 +1799,8 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
func TestSortedMap_Get(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
- m := NewSortedMap(nil)
- if v, ok := m.Get(100); ok || v != nil {
+ m := NewSortedMap[int, int](nil)
+ if v, ok := m.Get(100); ok {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
}
})
@@ -1759,7 +1808,7 @@ func TestSortedMap_Get(t *testing.T) {
func TestSortedMap_Set(t *testing.T) {
t.Run("Simple", func(t *testing.T) {
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, string](nil)
m = m.Set(100, "foo")
if v, ok := m.Get(100); !ok || v != "foo" {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
@@ -1770,7 +1819,7 @@ func TestSortedMap_Set(t *testing.T) {
t.Run("Small", func(t *testing.T) {
const n = 1000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1787,7 +1836,7 @@ func TestSortedMap_Set(t *testing.T) {
}
const n = 1000000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1799,7 +1848,7 @@ func TestSortedMap_Set(t *testing.T) {
})
t.Run("StringKeys", func(t *testing.T) {
- m := NewSortedMap(nil)
+ m := NewSortedMap[string, string](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", "bat")
m = m.Set("", "EMPTY")
@@ -1815,31 +1864,14 @@ func TestSortedMap_Set(t *testing.T) {
}
})
- t.Run("ByteSliceKeys", func(t *testing.T) {
- m := NewSortedMap(nil)
- m = m.Set([]byte("foo"), "bar")
- m = m.Set([]byte("baz"), "bat")
- m = m.Set([]byte(""), "EMPTY")
- if v, ok := m.Get([]byte("foo")); !ok || v != "bar" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- } else if v, ok := m.Get([]byte("baz")); !ok || v != "bat" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- } else if v, ok := m.Get([]byte("")); !ok || v != "EMPTY" {
- t.Fatalf("unexpected value: <%v,%v>", v, ok)
- }
- if v, ok := m.Get([]byte("no_such_key")); ok {
- t.Fatalf("expected no value: <%v,%v>", v, ok)
- }
- })
-
t.Run("NoDefaultComparer", func(t *testing.T) {
var r string
func() {
defer func() { r = recover().(string) }()
- m := NewSortedMap(nil)
- m = m.Set(uint64(100), "bar")
+ m := NewSortedMap[float64, string](nil)
+ m = m.Set(float64(100), "bar")
}()
- if r != `immutable.SortedMap.Set: must set comparer for uint64 type` {
+ if r != `immutable.NewComparer: must set comparer for float64 type` {
t.Fatalf("unexpected panic: %q", r)
}
})
@@ -1863,7 +1895,7 @@ func TestSortedMap_Set(t *testing.T) {
// Ensure map can support overwrites as it expands.
func TestSortedMap_Overwrite(t *testing.T) {
const n = 1000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
// Set original value.
m = m.Set(i, i)
@@ -1884,7 +1916,7 @@ func TestSortedMap_Overwrite(t *testing.T) {
func TestSortedMap_Delete(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
m = m.Delete(100)
if n := m.Len(); n != 0 {
t.Fatalf("SortedMap.Len()=%d, expected 0", n)
@@ -1892,7 +1924,7 @@ func TestSortedMap_Delete(t *testing.T) {
})
t.Run("Simple", func(t *testing.T) {
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, string](nil)
m = m.Set(100, "foo")
if v, ok := m.Get(100); !ok || v != "foo" {
t.Fatalf("unexpected value: <%v,%v>", v, ok)
@@ -1905,7 +1937,7 @@ func TestSortedMap_Delete(t *testing.T) {
t.Run("Small", func(t *testing.T) {
const n = 1000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1931,7 +1963,7 @@ func TestSortedMap_Delete(t *testing.T) {
}
const n = 1000000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
}
@@ -1984,25 +2016,25 @@ func TestSortedMap_Delete(t *testing.T) {
func TestSortedMap_Iterator(t *testing.T) {
t.Run("Empty", func(t *testing.T) {
t.Run("First", func(t *testing.T) {
- itr := NewSortedMap(nil).Iterator()
+ itr := NewSortedMap[int, int](nil).Iterator()
itr.First()
- if k, v := itr.Next(); k != nil || v != nil {
+ if k, v, ok := itr.Next(); ok {
t.Fatalf("SortedMapIterator.Next()=<%v,%v>, expected nil", k, v)
}
})
t.Run("Last", func(t *testing.T) {
- itr := NewSortedMap(nil).Iterator()
+ itr := NewSortedMap[int, int](nil).Iterator()
itr.Last()
- if k, v := itr.Prev(); k != nil || v != nil {
+ if k, v, ok := itr.Prev(); ok {
t.Fatalf("SortedMapIterator.Prev()=<%v,%v>, expected nil", k, v)
}
})
t.Run("Seek", func(t *testing.T) {
- itr := NewSortedMap(nil).Iterator()
+ itr := NewSortedMap[string, int](nil).Iterator()
itr.Seek("foo")
- if k, v := itr.Next(); k != nil || v != nil {
+ if k, v, ok := itr.Next(); ok {
t.Fatalf("SortedMapIterator.Next()=<%v,%v>, expected nil", k, v)
}
})
@@ -2010,7 +2042,7 @@ func TestSortedMap_Iterator(t *testing.T) {
t.Run("Seek", func(t *testing.T) {
const n = 100
- m := NewSortedMap(nil)
+ m := NewSortedMap[string, int](nil)
for i := 0; i < n; i += 2 {
m = m.Set(fmt.Sprintf("%04d", i), i)
}
@@ -2020,7 +2052,7 @@ func TestSortedMap_Iterator(t *testing.T) {
for i := 0; i < n; i += 2 {
itr.Seek(fmt.Sprintf("%04d", i))
for j := i; j < n; j += 2 {
- if k, _ := itr.Next(); k != fmt.Sprintf("%04d", j) {
+ if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", j) {
t.Fatalf("%d/%d. SortedMapIterator.Next()=%v, expected key %04d", i, j, k, j)
}
}
@@ -2035,7 +2067,7 @@ func TestSortedMap_Iterator(t *testing.T) {
for i := 1; i < n-2; i += 2 {
itr.Seek(fmt.Sprintf("%04d", i))
for j := i + 1; j < n; j += 2 {
- if k, _ := itr.Next(); k != fmt.Sprintf("%04d", j) {
+ if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", j) {
t.Fatalf("%d/%d. SortedMapIterator.Next()=%v, expected key %04d", i, j, k, j)
}
}
@@ -2049,7 +2081,7 @@ func TestSortedMap_Iterator(t *testing.T) {
itr := m.Iterator()
itr.Seek("")
for i := 0; i < n; i += 2 {
- if k, _ := itr.Next(); k != fmt.Sprintf("%04d", i) {
+ if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", i) {
t.Fatalf("%d. SortedMapIterator.Next()=%v, expected key %04d", i, k, i)
}
}
@@ -2060,7 +2092,7 @@ func TestSortedMap_Iterator(t *testing.T) {
t.Run("AfterLast", func(t *testing.T) {
itr := m.Iterator()
itr.Seek("1000")
- if k, _ := itr.Next(); k != nil {
+ if k, _, ok := itr.Next(); ok {
t.Fatalf("0. SortedMapIterator.Next()=%v, expected nil key", k)
} else if !itr.Done() {
t.Fatalf("SortedMapIterator.Done()=true, expected false")
@@ -2069,18 +2101,99 @@ func TestSortedMap_Iterator(t *testing.T) {
})
}
+func TestNewHasher(t *testing.T) {
+ t.Run("builtin", func(t *testing.T) {
+ t.Run("int", func(t *testing.T) { testNewHasher(t, int(100)) })
+ t.Run("int8", func(t *testing.T) { testNewHasher(t, int8(100)) })
+ t.Run("int16", func(t *testing.T) { testNewHasher(t, int16(100)) })
+ t.Run("int32", func(t *testing.T) { testNewHasher(t, int32(100)) })
+ t.Run("int64", func(t *testing.T) { testNewHasher(t, int64(100)) })
+
+ t.Run("uint", func(t *testing.T) { testNewHasher(t, uint(100)) })
+ t.Run("uint8", func(t *testing.T) { testNewHasher(t, uint8(100)) })
+ t.Run("uint16", func(t *testing.T) { testNewHasher(t, uint16(100)) })
+ t.Run("uint32", func(t *testing.T) { testNewHasher(t, uint32(100)) })
+ t.Run("uint64", func(t *testing.T) { testNewHasher(t, uint64(100)) })
+
+ t.Run("string", func(t *testing.T) { testNewHasher(t, "foo") })
+ //t.Run("byteSlice", func(t *testing.T) { testNewHasher(t, []byte("foo")) })
+ })
+
+ t.Run("reflection", func(t *testing.T) {
+ type Int int
+ t.Run("int", func(t *testing.T) { testNewHasher(t, Int(100)) })
+
+ type Uint uint
+ t.Run("uint", func(t *testing.T) { testNewHasher(t, Uint(100)) })
+
+ type String string
+ t.Run("string", func(t *testing.T) { testNewHasher(t, String("foo")) })
+ })
+}
+
+func testNewHasher[V constraints.Ordered](t *testing.T, v V) {
+ t.Helper()
+ h := NewHasher(v)
+ h.Hash(v)
+ if !h.Equal(v, v) {
+ t.Fatal("expected hash equality")
+ }
+}
+
+func TestNewComparer(t *testing.T) {
+ t.Run("builtin", func(t *testing.T) {
+ t.Run("int", func(t *testing.T) { testNewComparer(t, int(100), int(101)) })
+ t.Run("int8", func(t *testing.T) { testNewComparer(t, int8(100), int8(101)) })
+ t.Run("int16", func(t *testing.T) { testNewComparer(t, int16(100), int16(101)) })
+ t.Run("int32", func(t *testing.T) { testNewComparer(t, int32(100), int32(101)) })
+ t.Run("int64", func(t *testing.T) { testNewComparer(t, int64(100), int64(101)) })
+
+ t.Run("uint", func(t *testing.T) { testNewComparer(t, uint(100), uint(101)) })
+ t.Run("uint8", func(t *testing.T) { testNewComparer(t, uint8(100), uint8(101)) })
+ t.Run("uint16", func(t *testing.T) { testNewComparer(t, uint16(100), uint16(101)) })
+ t.Run("uint32", func(t *testing.T) { testNewComparer(t, uint32(100), uint32(101)) })
+ t.Run("uint64", func(t *testing.T) { testNewComparer(t, uint64(100), uint64(101)) })
+
+ t.Run("string", func(t *testing.T) { testNewComparer(t, "bar", "foo") })
+ //t.Run("byteSlice", func(t *testing.T) { testNewComparer(t, []byte("bar"), []byte("foo")) })
+ })
+
+ t.Run("reflection", func(t *testing.T) {
+ type Int int
+ t.Run("int", func(t *testing.T) { testNewComparer(t, Int(100), Int(101)) })
+
+ type Uint uint
+ t.Run("uint", func(t *testing.T) { testNewComparer(t, Uint(100), Uint(101)) })
+
+ type String string
+ t.Run("string", func(t *testing.T) { testNewComparer(t, String("bar"), String("foo")) })
+ })
+}
+
+func testNewComparer[T constraints.Ordered](t *testing.T, x, y T) {
+ t.Helper()
+ c := NewComparer(x)
+ if c.Compare(x, y) != -1 {
+ t.Fatal("expected comparer LT")
+ } else if c.Compare(x, x) != 0 {
+ t.Fatal("expected comparer EQ")
+ } else if c.Compare(y, x) != 1 {
+ t.Fatal("expected comparer GT")
+ }
+}
+
// TSortedMap represents a combined immutable and stdlib sorted map.
type TSortedMap struct {
- im, prev *SortedMap
- builder *SortedMapBuilder
+ im, prev *SortedMap[int, int]
+ builder *SortedMapBuilder[int, int]
std map[int]int
keys []int
}
func NewTSortedMap() *TSortedMap {
return &TSortedMap{
- im: NewSortedMap(nil),
- builder: NewSortedMapBuilder(NewSortedMap(nil)),
+ im: NewSortedMap[int, int](nil),
+ builder: NewSortedMapBuilder[int, int](nil),
std: make(map[int]int),
}
}
@@ -2146,25 +2259,24 @@ func (m *TSortedMap) Validate() error {
}
sort.Ints(m.keys)
- if err := m.validateForwardIterator(m.im); err != nil {
+ if err := m.validateForwardIterator(m.im.Iterator()); err != nil {
return fmt.Errorf("basic: %s", err)
- } else if err := m.validateBackwardIterator(m.im); err != nil {
+ } else if err := m.validateBackwardIterator(m.im.Iterator()); err != nil {
return fmt.Errorf("basic: %s", err)
}
- if err := m.validateForwardIterator(m.builder.Map()); err != nil {
+ if err := m.validateForwardIterator(m.builder.Iterator()); err != nil {
return fmt.Errorf("basic: %s", err)
- } else if err := m.validateBackwardIterator(m.builder.Map()); err != nil {
+ } else if err := m.validateBackwardIterator(m.builder.Iterator()); err != nil {
return fmt.Errorf("basic: %s", err)
}
return nil
}
-func (m *TSortedMap) validateForwardIterator(mm *SortedMap) error {
- itr := mm.Iterator()
+func (m *TSortedMap) validateForwardIterator(itr *SortedMapIterator[int, int]) error {
for i, k0 := range m.keys {
v0 := m.std[k0]
- if k1, v1 := itr.Next(); k0 != k1 || v0 != v1 {
+ if k1, v1, ok := itr.Next(); !ok || k0 != k1 || v0 != v1 {
return fmt.Errorf("%d. SortedMapIterator.Next()=<%v,%v>, expected <%v,%v>", i, k1, v1, k0, v0)
}
@@ -2173,19 +2285,18 @@ func (m *TSortedMap) validateForwardIterator(mm *SortedMap) error {
return fmt.Errorf("%d. SortedMapIterator.Done()=%v, expected %v", i, v, done)
}
}
- if k, v := itr.Next(); k != nil || v != nil {
+ if k, v, ok := itr.Next(); ok {
return fmt.Errorf("SortedMapIterator.Next()=<%v,%v>, expected nil after done", k, v)
}
return nil
}
-func (m *TSortedMap) validateBackwardIterator(mm *SortedMap) error {
- itr := mm.Iterator()
+func (m *TSortedMap) validateBackwardIterator(itr *SortedMapIterator[int, int]) error {
itr.Last()
for i := len(m.keys) - 1; i >= 0; i-- {
k0 := m.keys[i]
v0 := m.std[k0]
- if k1, v1 := itr.Prev(); k0 != k1 || v0 != v1 {
+ if k1, v1, ok := itr.Prev(); !ok || k0 != k1 || v0 != v1 {
return fmt.Errorf("%d. SortedMapIterator.Prev()=<%v,%v>, expected <%v,%v>", i, k1, v1, k0, v0)
}
@@ -2194,7 +2305,7 @@ func (m *TSortedMap) validateBackwardIterator(mm *SortedMap) error {
return fmt.Errorf("%d. SortedMapIterator.Done()=%v, expected %v", i, v, done)
}
}
- if k, v := itr.Prev(); k != nil || v != nil {
+ if k, v, ok := itr.Prev(); ok {
return fmt.Errorf("SortedMapIterator.Prev()=<%v,%v>, expected nil after done", k, v)
}
return nil
@@ -2202,7 +2313,7 @@ func (m *TSortedMap) validateBackwardIterator(mm *SortedMap) error {
func BenchmarkSortedMap_Set(b *testing.B) {
b.ReportAllocs()
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < b.N; i++ {
m = m.Set(i, i)
}
@@ -2211,7 +2322,7 @@ func BenchmarkSortedMap_Set(b *testing.B) {
func BenchmarkSortedMap_Delete(b *testing.B) {
const n = 10000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i)
}
@@ -2225,7 +2336,7 @@ func BenchmarkSortedMap_Delete(b *testing.B) {
func BenchmarkSortedMap_Iterator(b *testing.B) {
const n = 10000
- m := NewSortedMap(nil)
+ m := NewSortedMap[int, int](nil)
for i := 0; i < 10000; i++ {
m = m.Set(i, i)
}
@@ -2255,7 +2366,7 @@ func BenchmarkSortedMap_Iterator(b *testing.B) {
func BenchmarkSortedMapBuilder_Set(b *testing.B) {
b.ReportAllocs()
- builder := NewSortedMapBuilder(NewSortedMap(nil))
+ builder := NewSortedMapBuilder[int, int](nil)
for i := 0; i < b.N; i++ {
builder.Set(i, i)
}
@@ -2264,7 +2375,7 @@ func BenchmarkSortedMapBuilder_Set(b *testing.B) {
func BenchmarkSortedMapBuilder_Delete(b *testing.B) {
const n = 1000000
- builder := NewSortedMapBuilder(NewSortedMap(nil))
+ builder := NewSortedMapBuilder[int, int](nil)
for i := 0; i < n; i++ {
builder.Set(i, i)
}
@@ -2277,7 +2388,7 @@ func BenchmarkSortedMapBuilder_Delete(b *testing.B) {
}
func ExampleSortedMap_Set() {
- m := NewSortedMap(nil)
+ m := NewSortedMap[string, any](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", 100)
@@ -2296,7 +2407,7 @@ func ExampleSortedMap_Set() {
}
func ExampleSortedMap_Delete() {
- m := NewSortedMap(nil)
+ m := NewSortedMap[string, any](nil)
m = m.Set("foo", "bar")
m = m.Set("baz", 100)
m = m.Delete("baz")
@@ -2312,7 +2423,7 @@ func ExampleSortedMap_Delete() {
}
func ExampleSortedMap_Iterator() {
- m := NewSortedMap(nil)
+ m := NewSortedMap[string, any](nil)
m = m.Set("strawberry", 900)
m = m.Set("kiwi", 300)
m = m.Set("apple", 100)
@@ -2325,7 +2436,7 @@ func ExampleSortedMap_Iterator() {
itr := m.Iterator()
for !itr.Done() {
- k, v := itr.Next()
+ k, v, _ := itr.Next()
fmt.Println(k, v)
}
// Output:
@@ -2341,7 +2452,7 @@ func ExampleSortedMap_Iterator() {
}
func ExampleSortedMapBuilder_Set() {
- b := NewSortedMapBuilder(NewSortedMap(nil))
+ b := NewSortedMapBuilder[string, any](nil)
b.Set("foo", "bar")
b.Set("baz", 100)
@@ -2361,7 +2472,7 @@ func ExampleSortedMapBuilder_Set() {
}
func ExampleSortedMapBuilder_Delete() {
- b := NewSortedMapBuilder(NewSortedMap(nil))
+ b := NewSortedMapBuilder[string, any](nil)
b.Set("foo", "bar")
b.Set("baz", 100)
b.Delete("baz")
@@ -2384,6 +2495,7 @@ func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand)
}
t.Run(name, func(t *testing.T) {
for i := 0; i < *randomN; i++ {
+ i := i
t.Run(fmt.Sprintf("%08d", i), func(t *testing.T) {
t.Parallel()
fn(t, rand.New(rand.NewSource(int64(i))))
@@ -2406,27 +2518,27 @@ func uniqueIntSlice(a []int) []int {
}
// mockHasher represents a mock implementation of immutable.Hasher.
-type mockHasher struct {
- hash func(value interface{}) uint32
- equal func(a, b interface{}) bool
+type mockHasher[K constraints.Ordered] struct {
+ hash func(value K) uint32
+ equal func(a, b K) bool
}
// Hash executes the mocked HashFn function.
-func (h *mockHasher) Hash(value interface{}) uint32 {
+func (h *mockHasher[K]) Hash(value K) uint32 {
return h.hash(value)
}
// Equal executes the mocked EqualFn function.
-func (h *mockHasher) Equal(a, b interface{}) bool {
+func (h *mockHasher[K]) Equal(a, b K) bool {
return h.equal(a, b)
}
// mockComparer represents a mock implementation of immutable.Comparer.
-type mockComparer struct {
- compare func(a, b interface{}) int
+type mockComparer[K constraints.Ordered] struct {
+ compare func(a, b K) int
}
// Compare executes the mocked CompreFn function.
-func (h *mockComparer) Compare(a, b interface{}) int {
+func (h *mockComparer[K]) Compare(a, b K) int {
return h.compare(a, b)
}
diff --git a/sets.go b/sets.go
new file mode 100644
index 0000000..c8ce39f
--- /dev/null
+++ b/sets.go
@@ -0,0 +1,233 @@
+package immutable
+
+// Set represents a collection of unique values. The set uses a Hasher
+// to generate hashes and check for equality of key values.
+//
+// Internally, the Set stores values as keys of a Map[T,struct{}]
+type Set[T any] struct {
+ m *Map[T, struct{}]
+}
+
+// NewSet returns a new instance of Set.
+//
+// If hasher is nil, a default hasher implementation will automatically be chosen based on the first key added.
+// Default hasher implementations only exist for int, string, and byte slice types.
+// NewSet can also take some initial values as varargs.
+func NewSet[T any](hasher Hasher[T], values ...T) Set[T] {
+ m := NewMap[T, struct{}](hasher)
+ for _, value := range values {
+ m = m.set(value, struct{}{}, true)
+ }
+ return Set[T]{m}
+}
+
+// Add returns a set containing the new value.
+//
+// This function will return a new set even if the set already contains the value.
+func (s Set[T]) Add(value T) Set[T] {
+ return Set[T]{s.m.Set(value, struct{}{})}
+}
+
+// Delete returns a set with the given key removed.
+func (s Set[T]) Delete(value T) Set[T] {
+ return Set[T]{s.m.Delete(value)}
+}
+
+// Has returns true when the set contains the given value
+func (s Set[T]) Has(val T) bool {
+ _, ok := s.m.Get(val)
+ return ok
+}
+
+// Len returns the number of elements in the underlying map.
+func (s Set[K]) Len() int {
+ return s.m.Len()
+}
+
+// Items returns a slice of the items inside the set
+func (s Set[T]) Items() []T {
+ r := make([]T, 0, s.Len())
+ itr := s.Iterator()
+ for !itr.Done() {
+ v, _ := itr.Next()
+ r = append(r, v)
+ }
+ return r
+}
+
+// Iterator returns a new iterator for this set positioned at the first value.
+func (s Set[T]) Iterator() *SetIterator[T] {
+ itr := &SetIterator[T]{mi: s.m.Iterator()}
+ itr.mi.First()
+ return itr
+}
+
+// SetIterator represents an iterator over a set.
+// Iteration can occur in natural or reverse order based on use of Next() or Prev().
+type SetIterator[T any] struct {
+ mi *MapIterator[T, struct{}]
+}
+
+// Done returns true if no more values remain in the iterator.
+func (itr *SetIterator[T]) Done() bool {
+ return itr.mi.Done()
+}
+
+// First moves the iterator to the first value.
+func (itr *SetIterator[T]) First() {
+ itr.mi.First()
+}
+
+// Next moves the iterator to the next value.
+func (itr *SetIterator[T]) Next() (val T, ok bool) {
+ val, _, ok = itr.mi.Next()
+ return
+}
+
+type SetBuilder[T any] struct {
+ s Set[T]
+}
+
+func NewSetBuilder[T any](hasher Hasher[T]) *SetBuilder[T] {
+ return &SetBuilder[T]{s: NewSet(hasher)}
+}
+
+func (s SetBuilder[T]) Set(val T) {
+ s.s.m = s.s.m.set(val, struct{}{}, true)
+}
+
+func (s SetBuilder[T]) Delete(val T) {
+ s.s.m = s.s.m.delete(val, true)
+}
+
+func (s SetBuilder[T]) Has(val T) bool {
+ return s.s.Has(val)
+}
+
+func (s SetBuilder[T]) Len() int {
+ return s.s.Len()
+}
+
+type SortedSet[T any] struct {
+ m *SortedMap[T, struct{}]
+}
+
+// NewSortedSet returns a new instance of SortedSet.
+//
+// If comparer is nil then
+// a default comparer is set after the first key is inserted. Default comparers
+// exist for int, string, and byte slice keys.
+// NewSortedSet can also take some initial values as varargs.
+func NewSortedSet[T any](comparer Comparer[T], values ...T) SortedSet[T] {
+ m := NewSortedMap[T, struct{}](comparer)
+ for _, value := range values {
+ m = m.set(value, struct{}{}, true)
+ }
+ return SortedSet[T]{m}
+}
+
+// Add returns a set containing the new value.
+//
+// This function will return a new set even if the set already contains the value.
+func (s SortedSet[T]) Add(value T) SortedSet[T] {
+ return SortedSet[T]{s.m.Set(value, struct{}{})}
+}
+
+// Delete returns a set with the given key removed.
+func (s SortedSet[T]) Delete(value T) SortedSet[T] {
+ return SortedSet[T]{s.m.Delete(value)}
+}
+
+// Has returns true when the set contains the given value
+func (s SortedSet[T]) Has(val T) bool {
+ _, ok := s.m.Get(val)
+ return ok
+}
+
+// Len returns the number of elements in the underlying map.
+func (s SortedSet[K]) Len() int {
+ return s.m.Len()
+}
+
+// Items returns a slice of the items inside the set
+func (s SortedSet[T]) Items() []T {
+ r := make([]T, 0, s.Len())
+ itr := s.Iterator()
+ for !itr.Done() {
+ v, _ := itr.Next()
+ r = append(r, v)
+ }
+ return r
+}
+
+// Iterator returns a new iterator for this set positioned at the first value.
+func (s SortedSet[T]) Iterator() *SortedSetIterator[T] {
+ itr := &SortedSetIterator[T]{mi: s.m.Iterator()}
+ itr.mi.First()
+ return itr
+}
+
+// SortedSetIterator represents an iterator over a sorted set.
+// Iteration can occur in natural or reverse order based on use of Next() or Prev().
+type SortedSetIterator[T any] struct {
+ mi *SortedMapIterator[T, struct{}]
+}
+
+// Done returns true if no more values remain in the iterator.
+func (itr *SortedSetIterator[T]) Done() bool {
+ return itr.mi.Done()
+}
+
+// First moves the iterator to the first value.
+func (itr *SortedSetIterator[T]) First() {
+ itr.mi.First()
+}
+
+// Last moves the iterator to the last value.
+func (itr *SortedSetIterator[T]) Last() {
+ itr.mi.Last()
+}
+
+// Next moves the iterator to the next value.
+func (itr *SortedSetIterator[T]) Next() (val T, ok bool) {
+ val, _, ok = itr.mi.Next()
+ return
+}
+
+// Next moves the iterator to the previous value.
+func (itr *SortedSetIterator[T]) Prev() (val T, ok bool) {
+ val, _, ok = itr.mi.Prev()
+ return
+}
+
+// Next moves the iterator to the given value.
+//
+// If the value does not exist then the next value is used. If no more keys exist
+// then the iterator is marked as done.
+func (itr *SortedSetIterator[T]) Seek(val T) {
+ itr.mi.Seek(val)
+}
+
+type SortedSetBuilder[T any] struct {
+ s SortedSet[T]
+}
+
+func NewSortedSetBuilder[T any](comparer Comparer[T]) *SortedSetBuilder[T] {
+ return &SortedSetBuilder[T]{s: NewSortedSet(comparer)}
+}
+
+func (s SortedSetBuilder[T]) Set(val T) {
+ s.s.m = s.s.m.set(val, struct{}{}, true)
+}
+
+func (s SortedSetBuilder[T]) Delete(val T) {
+ s.s.m = s.s.m.delete(val, true)
+}
+
+func (s SortedSetBuilder[T]) Has(val T) bool {
+ return s.s.Has(val)
+}
+
+func (s SortedSetBuilder[T]) Len() int {
+ return s.s.Len()
+}
diff --git a/sets_test.go b/sets_test.go
new file mode 100644
index 0000000..ca3aa3d
--- /dev/null
+++ b/sets_test.go
@@ -0,0 +1,103 @@
+package immutable
+
+import (
+ "testing"
+)
+
+func TestSetsPut(t *testing.T) {
+ s := NewSet[string](nil)
+ s2 := s.Add("1").Add("1")
+ s2.Add("2")
+ if s.Len() != 0 {
+ t.Fatalf("Unexpected mutation of set")
+ }
+ if s.Has("1") {
+ t.Fatalf("Unexpected set element")
+ }
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ itr := s2.Iterator()
+ counter := 0
+ for !itr.Done() {
+ i, v := itr.Next()
+ t.Log(i, v)
+ counter++
+ }
+ if counter != 1 {
+ t.Fatalf("iterator wrong length")
+ }
+}
+
+func TestSetsDelete(t *testing.T) {
+ s := NewSet[string](nil)
+ s2 := s.Add("1")
+ s3 := s.Delete("1")
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ if s3.Len() != 0 {
+ t.Fatalf("Unexpected set length after delete")
+ }
+ if s3.Has("1") {
+ t.Fatalf("Unexpected set element after delete")
+ }
+}
+
+func TestSortedSetsPut(t *testing.T) {
+ s := NewSortedSet[string](nil)
+ s2 := s.Add("1").Add("1").Add("0")
+ if s.Len() != 0 {
+ t.Fatalf("Unexpected mutation of set")
+ }
+ if s.Has("1") {
+ t.Fatalf("Unexpected set element")
+ }
+ if s2.Len() != 2 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+
+ itr := s2.Iterator()
+ counter := 0
+ for !itr.Done() {
+ i, v := itr.Next()
+ t.Log(i, v)
+ if counter == 0 && i != "0" {
+ t.Fatalf("sort did not work for first el")
+ }
+ if counter == 1 && i != "1" {
+ t.Fatalf("sort did not work for second el")
+ }
+ counter++
+ }
+ if counter != 2 {
+ t.Fatalf("iterator wrong length")
+ }
+}
+
+func TestSortedSetsDelete(t *testing.T) {
+ s := NewSortedSet[string](nil)
+ s2 := s.Add("1")
+ s3 := s.Delete("1")
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ if s3.Len() != 0 {
+ t.Fatalf("Unexpected set length after delete")
+ }
+ if s3.Has("1") {
+ t.Fatalf("Unexpected set element after delete")
+ }
+}
Debdiff
[The following lists of changes regard files as different if they have different names, permissions or owners.]
Files in second set of .debs but not in first
-rw-r--r-- root/root /usr/share/gocode/src/github.com/benbjohnson/immutable/sets.go -rw-r--r-- root/root /usr/share/gocode/src/github.com/benbjohnson/immutable/sets_test.go
No differences were encountered in the control files