Source file src/github.com/benbjohnson/immutable/immutable_test.go

Documentation: github.com/benbjohnson/immutable

     1  package immutable
     2  
     3  import (
     4  	"flag"
     5  	"fmt"
     6  	"math/rand"
     7  	"sort"
     8  	"testing"
     9  
    10  	"golang.org/x/exp/constraints"
    11  )
    12  
    13  var (
    14  	veryVerbose = flag.Bool("vv", false, "very verbose")
    15  	randomN     = flag.Int("random.n", 100, "number of RunRandom() iterations")
    16  )
    17  
    18  func TestList(t *testing.T) {
    19  	t.Run("Empty", func(t *testing.T) {
    20  		if size := NewList[string]().Len(); size != 0 {
    21  			t.Fatalf("unexpected size: %d", size)
    22  		}
    23  	})
    24  
    25  	t.Run("Shallow", func(t *testing.T) {
    26  		list := NewList[string]()
    27  		list = list.Append("foo")
    28  		if v := list.Get(0); v != "foo" {
    29  			t.Fatalf("unexpected value: %v", v)
    30  		}
    31  
    32  		other := list.Append("bar")
    33  		if v := other.Get(0); v != "foo" {
    34  			t.Fatalf("unexpected value: %v", v)
    35  		} else if v := other.Get(1); v != "bar" {
    36  			t.Fatalf("unexpected value: %v", v)
    37  		}
    38  
    39  		if v := list.Len(); v != 1 {
    40  			t.Fatalf("unexpected value: %v", v)
    41  		}
    42  	})
    43  
    44  	t.Run("Deep", func(t *testing.T) {
    45  		list := NewList[int]()
    46  		var array []int
    47  		for i := 0; i < 100000; i++ {
    48  			list = list.Append(i)
    49  			array = append(array, i)
    50  		}
    51  
    52  		if got, exp := len(array), list.Len(); got != exp {
    53  			t.Fatalf("List.Len()=%d, exp %d", got, exp)
    54  		}
    55  		for j := range array {
    56  			if got, exp := list.Get(j), array[j]; got != exp {
    57  				t.Fatalf("%d. List.Get(%d)=%d, exp %d", len(array), j, got, exp)
    58  			}
    59  		}
    60  	})
    61  
    62  	t.Run("Set", func(t *testing.T) {
    63  		list := NewList[string]()
    64  		list = list.Append("foo")
    65  		list = list.Append("bar")
    66  
    67  		if v := list.Get(0); v != "foo" {
    68  			t.Fatalf("unexpected value: %v", v)
    69  		}
    70  
    71  		list = list.Set(0, "baz")
    72  		if v := list.Get(0); v != "baz" {
    73  			t.Fatalf("unexpected value: %v", v)
    74  		} else if v := list.Get(1); v != "bar" {
    75  			t.Fatalf("unexpected value: %v", v)
    76  		}
    77  	})
    78  
    79  	t.Run("GetBelowRange", func(t *testing.T) {
    80  		var r string
    81  		func() {
    82  			defer func() { r = recover().(string) }()
    83  			l := NewList[string]()
    84  			l = l.Append("foo")
    85  			l.Get(-1)
    86  		}()
    87  		if r != `immutable.List.Get: index -1 out of bounds` {
    88  			t.Fatalf("unexpected panic: %q", r)
    89  		}
    90  	})
    91  
    92  	t.Run("GetAboveRange", func(t *testing.T) {
    93  		var r string
    94  		func() {
    95  			defer func() { r = recover().(string) }()
    96  			l := NewList[string]()
    97  			l = l.Append("foo")
    98  			l.Get(1)
    99  		}()
   100  		if r != `immutable.List.Get: index 1 out of bounds` {
   101  			t.Fatalf("unexpected panic: %q", r)
   102  		}
   103  	})
   104  
   105  	t.Run("SetOutOfRange", func(t *testing.T) {
   106  		var r string
   107  		func() {
   108  			defer func() { r = recover().(string) }()
   109  			l := NewList[string]()
   110  			l = l.Append("foo")
   111  			l.Set(1, "bar")
   112  		}()
   113  		if r != `immutable.List.Set: index 1 out of bounds` {
   114  			t.Fatalf("unexpected panic: %q", r)
   115  		}
   116  	})
   117  
   118  	t.Run("SliceStartOutOfRange", func(t *testing.T) {
   119  		var r string
   120  		func() {
   121  			defer func() { r = recover().(string) }()
   122  			l := NewList[string]()
   123  			l = l.Append("foo")
   124  			l.Slice(2, 3)
   125  		}()
   126  		if r != `immutable.List.Slice: start index 2 out of bounds` {
   127  			t.Fatalf("unexpected panic: %q", r)
   128  		}
   129  	})
   130  
   131  	t.Run("SliceEndOutOfRange", func(t *testing.T) {
   132  		var r string
   133  		func() {
   134  			defer func() { r = recover().(string) }()
   135  			l := NewList[string]()
   136  			l = l.Append("foo")
   137  			l.Slice(1, 3)
   138  		}()
   139  		if r != `immutable.List.Slice: end index 3 out of bounds` {
   140  			t.Fatalf("unexpected panic: %q", r)
   141  		}
   142  	})
   143  
   144  	t.Run("SliceInvalidIndex", func(t *testing.T) {
   145  		var r string
   146  		func() {
   147  			defer func() { r = recover().(string) }()
   148  			l := NewList[string]()
   149  			l = l.Append("foo")
   150  			l = l.Append("bar")
   151  			l.Slice(2, 1)
   152  		}()
   153  		if r != `immutable.List.Slice: invalid slice index: [2:1]` {
   154  			t.Fatalf("unexpected panic: %q", r)
   155  		}
   156  	})
   157  
   158  	t.Run("SliceBeginning", func(t *testing.T) {
   159  		l := NewList[string]()
   160  		l = l.Append("foo")
   161  		l = l.Append("bar")
   162  		l = l.Slice(1, 2)
   163  		if got, exp := l.Len(), 1; got != exp {
   164  			t.Fatalf("List.Len()=%d, exp %d", got, exp)
   165  		} else if got, exp := l.Get(0), "bar"; got != exp {
   166  			t.Fatalf("List.Get(0)=%v, exp %v", got, exp)
   167  		}
   168  	})
   169  
   170  	t.Run("IteratorSeekOutOfBounds", func(t *testing.T) {
   171  		var r string
   172  		func() {
   173  			defer func() { r = recover().(string) }()
   174  			l := NewList[string]()
   175  			l = l.Append("foo")
   176  			l.Iterator().Seek(-1)
   177  		}()
   178  		if r != `immutable.ListIterator.Seek: index -1 out of bounds` {
   179  			t.Fatalf("unexpected panic: %q", r)
   180  		}
   181  	})
   182  
   183  	t.Run("TestSliceFreesReferences", func(t *testing.T) {
   184  		/* Test that the leaf node in a sliced list contains zero'ed entries at
   185  		 * the correct positions. To do this we directly access the internal
   186  		 * tree structure of the list.
   187  		 */
   188  		l := NewList[*int]()
   189  		var ints [5]int
   190  		for i := 0; i < 5; i++ {
   191  			l = l.Append(&ints[i])
   192  		}
   193  		sl := l.Slice(2, 4)
   194  
   195  		var findLeaf func(listNode[*int]) *listLeafNode[*int]
   196  		findLeaf = func(n listNode[*int]) *listLeafNode[*int] {
   197  			switch n := n.(type) {
   198  			case *listBranchNode[*int]:
   199  				if n.children[0] == nil {
   200  					t.Fatal("Failed to find leaf node due to nil child")
   201  				}
   202  				return findLeaf(n.children[0])
   203  			case *listLeafNode[*int]:
   204  				return n
   205  			default:
   206  				panic("Unexpected case")
   207  			}
   208  		}
   209  
   210  		leaf := findLeaf(sl.root)
   211  		if leaf.occupied != 0b1100 {
   212  			t.Errorf("Expected occupied to be 1100, was %032b", leaf.occupied)
   213  		}
   214  
   215  		for i := 0; i < listNodeSize; i++ {
   216  			if 2 <= i && i < 4 {
   217  				if leaf.children[i] != &ints[i] {
   218  					t.Errorf("Position %v does not contain the right pointer?", i)
   219  				}
   220  			} else if leaf.children[i] != nil {
   221  				t.Errorf("Expected position %v to be cleared, was %v", i, leaf.children[i])
   222  			}
   223  		}
   224  	})
   225  
   226  	t.Run("AppendImmutable", func(t *testing.T) {
   227  		outer_l := NewList[int]()
   228  		for N := 0; N < 1_000; N++ {
   229  			l1 := outer_l.Append(0)
   230  			outer_l.Append(1)
   231  			if actual := l1.Get(N); actual != 0 {
   232  				t.Fatalf("Append mutates list with %d elements. Got %d instead of 0", N, actual)
   233  			}
   234  
   235  			outer_l = outer_l.Append(0)
   236  		}
   237  	})
   238  
   239  	RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
   240  		l := NewTList()
   241  		for i := 0; i < 100000; i++ {
   242  			rnd := rand.Intn(70)
   243  			switch {
   244  			case rnd == 0: // slice
   245  				start, end := l.ChooseSliceIndices(rand)
   246  				l.Slice(start, end)
   247  			case rnd < 10: // set
   248  				if l.Len() > 0 {
   249  					l.Set(l.ChooseIndex(rand), rand.Intn(10000))
   250  				}
   251  			case rnd < 30: // prepend
   252  				l.Prepend(rand.Intn(10000))
   253  			default: // append
   254  				l.Append(rand.Intn(10000))
   255  			}
   256  		}
   257  		if err := l.Validate(); err != nil {
   258  			t.Fatal(err)
   259  		}
   260  	})
   261  }
   262  
   263  // TList represents a list that operates on a standard Go slice & immutable list.
   264  type TList struct {
   265  	im, prev *List[int]
   266  	builder  *ListBuilder[int]
   267  	std      []int
   268  }
   269  
   270  // NewTList returns a new instance of TList.
   271  func NewTList() *TList {
   272  	return &TList{
   273  		im:      NewList[int](),
   274  		builder: NewListBuilder[int](),
   275  	}
   276  }
   277  
   278  // Len returns the size of the list.
   279  func (l *TList) Len() int {
   280  	return len(l.std)
   281  }
   282  
   283  // ChooseIndex returns a randomly chosen, valid index from the standard slice.
   284  func (l *TList) ChooseIndex(rand *rand.Rand) int {
   285  	if len(l.std) == 0 {
   286  		return -1
   287  	}
   288  	return rand.Intn(len(l.std))
   289  }
   290  
   291  // ChooseSliceIndices returns randomly chosen, valid indices for slicing.
   292  func (l *TList) ChooseSliceIndices(rand *rand.Rand) (start, end int) {
   293  	if len(l.std) == 0 {
   294  		return 0, 0
   295  	}
   296  	start = rand.Intn(len(l.std))
   297  	end = rand.Intn(len(l.std)-start) + start
   298  	return start, end
   299  }
   300  
   301  // Append adds v to the end of slice and List.
   302  func (l *TList) Append(v int) {
   303  	l.prev = l.im
   304  	l.im = l.im.Append(v)
   305  	l.builder.Append(v)
   306  	l.std = append(l.std, v)
   307  }
   308  
   309  // Prepend adds v to the beginning of the slice and List.
   310  func (l *TList) Prepend(v int) {
   311  	l.prev = l.im
   312  	l.im = l.im.Prepend(v)
   313  	l.builder.Prepend(v)
   314  	l.std = append([]int{v}, l.std...)
   315  }
   316  
   317  // Set updates the value at index i to v in the slice and List.
   318  func (l *TList) Set(i, v int) {
   319  	l.prev = l.im
   320  	l.im = l.im.Set(i, v)
   321  	l.builder.Set(i, v)
   322  	l.std[i] = v
   323  }
   324  
   325  // Slice contracts the slice and List to the range of start/end indices.
   326  func (l *TList) Slice(start, end int) {
   327  	l.prev = l.im
   328  	l.im = l.im.Slice(start, end)
   329  	l.builder.Slice(start, end)
   330  	l.std = l.std[start:end]
   331  }
   332  
   333  // Validate returns an error if the slice and List are different.
   334  func (l *TList) Validate() error {
   335  	if got, exp := l.im.Len(), len(l.std); got != exp {
   336  		return fmt.Errorf("Len()=%v, expected %d", got, exp)
   337  	} else if got, exp := l.builder.Len(), len(l.std); got != exp {
   338  		return fmt.Errorf("Len()=%v, expected %d", got, exp)
   339  	}
   340  
   341  	for i := range l.std {
   342  		if got, exp := l.im.Get(i), l.std[i]; got != exp {
   343  			return fmt.Errorf("Get(%d)=%v, expected %v", i, got, exp)
   344  		} else if got, exp := l.builder.Get(i), l.std[i]; got != exp {
   345  			return fmt.Errorf("Builder.List/Get(%d)=%v, expected %v", i, got, exp)
   346  		}
   347  	}
   348  
   349  	if err := l.validateForwardIterator("basic", l.im.Iterator()); err != nil {
   350  		return err
   351  	} else if err := l.validateBackwardIterator("basic", l.im.Iterator()); err != nil {
   352  		return err
   353  	}
   354  
   355  	if err := l.validateForwardIterator("builder", l.builder.Iterator()); err != nil {
   356  		return err
   357  	} else if err := l.validateBackwardIterator("builder", l.builder.Iterator()); err != nil {
   358  		return err
   359  	}
   360  	return nil
   361  }
   362  
   363  func (l *TList) validateForwardIterator(typ string, itr *ListIterator[int]) error {
   364  	for i := range l.std {
   365  		if j, v := itr.Next(); i != j || l.std[i] != v {
   366  			return fmt.Errorf("ListIterator.Next()=<%v,%v>, expected <%v,%v> [%s]", j, v, i, l.std[i], typ)
   367  		}
   368  
   369  		done := i == len(l.std)-1
   370  		if v := itr.Done(); v != done {
   371  			return fmt.Errorf("ListIterator.Done()=%v, expected %v [%s]", v, done, typ)
   372  		}
   373  	}
   374  	if i, v := itr.Next(); i != -1 || v != 0 {
   375  		return fmt.Errorf("ListIterator.Next()=<%v,%v>, expected DONE [%s]", i, v, typ)
   376  	}
   377  	return nil
   378  }
   379  
   380  func (l *TList) validateBackwardIterator(typ string, itr *ListIterator[int]) error {
   381  	itr.Last()
   382  	for i := len(l.std) - 1; i >= 0; i-- {
   383  		if j, v := itr.Prev(); i != j || l.std[i] != v {
   384  			return fmt.Errorf("ListIterator.Prev()=<%v,%v>, expected <%v,%v> [%s]", j, v, i, l.std[i], typ)
   385  		}
   386  
   387  		done := i == 0
   388  		if v := itr.Done(); v != done {
   389  			return fmt.Errorf("ListIterator.Done()=%v, expected %v [%s]", v, done, typ)
   390  		}
   391  	}
   392  	if i, v := itr.Prev(); i != -1 || v != 0 {
   393  		return fmt.Errorf("ListIterator.Prev()=<%v,%v>, expected DONE [%s]", i, v, typ)
   394  	}
   395  	return nil
   396  }
   397  
   398  func BenchmarkList_Append(b *testing.B) {
   399  	b.ReportAllocs()
   400  	l := NewList[int]()
   401  	for i := 0; i < b.N; i++ {
   402  		l = l.Append(i)
   403  	}
   404  }
   405  
   406  func BenchmarkList_Prepend(b *testing.B) {
   407  	b.ReportAllocs()
   408  	l := NewList[int]()
   409  	for i := 0; i < b.N; i++ {
   410  		l = l.Prepend(i)
   411  	}
   412  }
   413  
   414  func BenchmarkList_Set(b *testing.B) {
   415  	const n = 10000
   416  
   417  	l := NewList[int]()
   418  	for i := 0; i < 10000; i++ {
   419  		l = l.Append(i)
   420  	}
   421  	b.ReportAllocs()
   422  	b.ResetTimer()
   423  
   424  	for i := 0; i < b.N; i++ {
   425  		l = l.Set(i%n, i*10)
   426  	}
   427  }
   428  
   429  func BenchmarkList_Iterator(b *testing.B) {
   430  	const n = 10000
   431  	l := NewList[int]()
   432  	for i := 0; i < 10000; i++ {
   433  		l = l.Append(i)
   434  	}
   435  	b.ReportAllocs()
   436  	b.ResetTimer()
   437  
   438  	b.Run("Forward", func(b *testing.B) {
   439  		itr := l.Iterator()
   440  		for i := 0; i < b.N; i++ {
   441  			if i%n == 0 {
   442  				itr.First()
   443  			}
   444  			itr.Next()
   445  		}
   446  	})
   447  
   448  	b.Run("Reverse", func(b *testing.B) {
   449  		itr := l.Iterator()
   450  		for i := 0; i < b.N; i++ {
   451  			if i%n == 0 {
   452  				itr.Last()
   453  			}
   454  			itr.Prev()
   455  		}
   456  	})
   457  }
   458  
   459  func BenchmarkBuiltinSlice_Append(b *testing.B) {
   460  	b.Run("Int", func(b *testing.B) {
   461  		b.ReportAllocs()
   462  		var a []int
   463  		for i := 0; i < b.N; i++ {
   464  			a = append(a, i)
   465  		}
   466  	})
   467  	b.Run("Interface", func(b *testing.B) {
   468  		b.ReportAllocs()
   469  		var a []interface{}
   470  		for i := 0; i < b.N; i++ {
   471  			a = append(a, i)
   472  		}
   473  	})
   474  }
   475  
   476  func BenchmarkListBuilder_Append(b *testing.B) {
   477  	b.ReportAllocs()
   478  	builder := NewListBuilder[int]()
   479  	for i := 0; i < b.N; i++ {
   480  		builder.Append(i)
   481  	}
   482  }
   483  
   484  func BenchmarkListBuilder_Prepend(b *testing.B) {
   485  	b.ReportAllocs()
   486  	builder := NewListBuilder[int]()
   487  	for i := 0; i < b.N; i++ {
   488  		builder.Prepend(i)
   489  	}
   490  }
   491  
   492  func BenchmarkListBuilder_Set(b *testing.B) {
   493  	const n = 10000
   494  
   495  	builder := NewListBuilder[int]()
   496  	for i := 0; i < 10000; i++ {
   497  		builder.Append(i)
   498  	}
   499  	b.ReportAllocs()
   500  	b.ResetTimer()
   501  
   502  	for i := 0; i < b.N; i++ {
   503  		builder.Set(i%n, i*10)
   504  	}
   505  }
   506  
   507  func ExampleList_Append() {
   508  	l := NewList[string]()
   509  	l = l.Append("foo")
   510  	l = l.Append("bar")
   511  	l = l.Append("baz")
   512  
   513  	fmt.Println(l.Get(0))
   514  	fmt.Println(l.Get(1))
   515  	fmt.Println(l.Get(2))
   516  	// Output:
   517  	// foo
   518  	// bar
   519  	// baz
   520  }
   521  
   522  func ExampleList_Prepend() {
   523  	l := NewList[string]()
   524  	l = l.Prepend("foo")
   525  	l = l.Prepend("bar")
   526  	l = l.Prepend("baz")
   527  
   528  	fmt.Println(l.Get(0))
   529  	fmt.Println(l.Get(1))
   530  	fmt.Println(l.Get(2))
   531  	// Output:
   532  	// baz
   533  	// bar
   534  	// foo
   535  }
   536  
   537  func ExampleList_Set() {
   538  	l := NewList[string]()
   539  	l = l.Append("foo")
   540  	l = l.Append("bar")
   541  	l = l.Set(1, "baz")
   542  
   543  	fmt.Println(l.Get(0))
   544  	fmt.Println(l.Get(1))
   545  	// Output:
   546  	// foo
   547  	// baz
   548  }
   549  
   550  func ExampleList_Slice() {
   551  	l := NewList[string]()
   552  	l = l.Append("foo")
   553  	l = l.Append("bar")
   554  	l = l.Append("baz")
   555  	l = l.Slice(1, 3)
   556  
   557  	fmt.Println(l.Get(0))
   558  	fmt.Println(l.Get(1))
   559  	// Output:
   560  	// bar
   561  	// baz
   562  }
   563  
   564  func ExampleList_Iterator() {
   565  	l := NewList[string]()
   566  	l = l.Append("foo")
   567  	l = l.Append("bar")
   568  	l = l.Append("baz")
   569  
   570  	itr := l.Iterator()
   571  	for !itr.Done() {
   572  		i, v := itr.Next()
   573  		fmt.Println(i, v)
   574  	}
   575  	// Output:
   576  	// 0 foo
   577  	// 1 bar
   578  	// 2 baz
   579  }
   580  
   581  func ExampleList_Iterator_reverse() {
   582  	l := NewList[string]()
   583  	l = l.Append("foo")
   584  	l = l.Append("bar")
   585  	l = l.Append("baz")
   586  
   587  	itr := l.Iterator()
   588  	itr.Last()
   589  	for !itr.Done() {
   590  		i, v := itr.Prev()
   591  		fmt.Println(i, v)
   592  	}
   593  	// Output:
   594  	// 2 baz
   595  	// 1 bar
   596  	// 0 foo
   597  }
   598  
   599  func ExampleListBuilder_Append() {
   600  	b := NewListBuilder[string]()
   601  	b.Append("foo")
   602  	b.Append("bar")
   603  	b.Append("baz")
   604  
   605  	l := b.List()
   606  	fmt.Println(l.Get(0))
   607  	fmt.Println(l.Get(1))
   608  	fmt.Println(l.Get(2))
   609  	// Output:
   610  	// foo
   611  	// bar
   612  	// baz
   613  }
   614  
   615  func ExampleListBuilder_Prepend() {
   616  	b := NewListBuilder[string]()
   617  	b.Prepend("foo")
   618  	b.Prepend("bar")
   619  	b.Prepend("baz")
   620  
   621  	l := b.List()
   622  	fmt.Println(l.Get(0))
   623  	fmt.Println(l.Get(1))
   624  	fmt.Println(l.Get(2))
   625  	// Output:
   626  	// baz
   627  	// bar
   628  	// foo
   629  }
   630  
   631  func ExampleListBuilder_Set() {
   632  	b := NewListBuilder[string]()
   633  	b.Append("foo")
   634  	b.Append("bar")
   635  	b.Set(1, "baz")
   636  
   637  	l := b.List()
   638  	fmt.Println(l.Get(0))
   639  	fmt.Println(l.Get(1))
   640  	// Output:
   641  	// foo
   642  	// baz
   643  }
   644  
   645  func ExampleListBuilder_Slice() {
   646  	b := NewListBuilder[string]()
   647  	b.Append("foo")
   648  	b.Append("bar")
   649  	b.Append("baz")
   650  	b.Slice(1, 3)
   651  
   652  	l := b.List()
   653  	fmt.Println(l.Get(0))
   654  	fmt.Println(l.Get(1))
   655  	// Output:
   656  	// bar
   657  	// baz
   658  }
   659  
   660  // Ensure node can support overwrites as it expands.
   661  func TestInternal_mapNode_Overwrite(t *testing.T) {
   662  	const n = 1000
   663  	var h defaultHasher[int]
   664  	var node mapNode[int, int] = &mapArrayNode[int, int]{}
   665  	for i := 0; i < n; i++ {
   666  		var resized bool
   667  		node = node.set(i, i, 0, h.Hash(i), &h, false, &resized)
   668  		if !resized {
   669  			t.Fatal("expected resize")
   670  		}
   671  
   672  		// Overwrite every node.
   673  		for j := 0; j <= i; j++ {
   674  			var resized bool
   675  			node = node.set(j, i*j, 0, h.Hash(j), &h, false, &resized)
   676  			if resized {
   677  				t.Fatalf("expected no resize: i=%d, j=%d", i, j)
   678  			}
   679  		}
   680  
   681  		// Verify not found at each branch type.
   682  		if _, ok := node.get(1000000, 0, h.Hash(1000000), &h); ok {
   683  			t.Fatal("expected no value")
   684  		}
   685  	}
   686  
   687  	// Verify all key/value pairs in map.
   688  	for i := 0; i < n; i++ {
   689  		if v, ok := node.get(i, 0, h.Hash(i), &h); !ok || v != i*(n-1) {
   690  			t.Fatalf("get(%d)=<%v,%v>", i, v, ok)
   691  		}
   692  	}
   693  }
   694  
   695  func TestInternal_mapArrayNode(t *testing.T) {
   696  	// Ensure 8 or fewer elements stays in an array node.
   697  	t.Run("Append", func(t *testing.T) {
   698  		var h defaultHasher[int]
   699  		n := &mapArrayNode[int, int]{}
   700  		for i := 0; i < 8; i++ {
   701  			var resized bool
   702  			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode[int, int])
   703  			if !resized {
   704  				t.Fatal("expected resize")
   705  			}
   706  
   707  			for j := 0; j < i; j++ {
   708  				if v, ok := n.get(j*10, 0, h.Hash(j*10), &h); !ok || v != j {
   709  					t.Fatalf("get(%d)=<%v,%v>", j, v, ok)
   710  				}
   711  			}
   712  		}
   713  	})
   714  
   715  	// Ensure 8 or fewer elements stays in an array node when inserted in reverse.
   716  	t.Run("Prepend", func(t *testing.T) {
   717  		var h defaultHasher[int]
   718  		n := &mapArrayNode[int, int]{}
   719  		for i := 7; i >= 0; i-- {
   720  			var resized bool
   721  			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode[int, int])
   722  			if !resized {
   723  				t.Fatal("expected resize")
   724  			}
   725  
   726  			for j := i; j <= 7; j++ {
   727  				if v, ok := n.get(j*10, 0, h.Hash(j*10), &h); !ok || v != j {
   728  					t.Fatalf("get(%d)=<%v,%v>", j, v, ok)
   729  				}
   730  			}
   731  		}
   732  	})
   733  
   734  	// Ensure array can transition between node types.
   735  	t.Run("Expand", func(t *testing.T) {
   736  		var h defaultHasher[int]
   737  		var n mapNode[int, int] = &mapArrayNode[int, int]{}
   738  		for i := 0; i < 100; i++ {
   739  			var resized bool
   740  			n = n.set(i, i, 0, h.Hash(i), &h, false, &resized)
   741  			if !resized {
   742  				t.Fatal("expected resize")
   743  			}
   744  
   745  			for j := 0; j < i; j++ {
   746  				if v, ok := n.get(j, 0, h.Hash(j), &h); !ok || v != j {
   747  					t.Fatalf("get(%d)=<%v,%v>", j, v, ok)
   748  				}
   749  			}
   750  		}
   751  	})
   752  
   753  	// Ensure deleting elements returns the correct new node.
   754  	RunRandom(t, "Delete", func(t *testing.T, rand *rand.Rand) {
   755  		var h defaultHasher[int]
   756  		var n mapNode[int, int] = &mapArrayNode[int, int]{}
   757  		for i := 0; i < 8; i++ {
   758  			var resized bool
   759  			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized)
   760  		}
   761  
   762  		for _, i := range rand.Perm(8) {
   763  			var resized bool
   764  			n = n.delete(i*10, 0, h.Hash(i*10), &h, false, &resized)
   765  		}
   766  		if n != nil {
   767  			t.Fatal("expected nil rand")
   768  		}
   769  	})
   770  }
   771  
   772  func TestInternal_mapValueNode(t *testing.T) {
   773  	t.Run("Simple", func(t *testing.T) {
   774  		var h defaultHasher[int]
   775  		n := newMapValueNode(h.Hash(2), 2, 3)
   776  		if v, ok := n.get(2, 0, h.Hash(2), &h); !ok {
   777  			t.Fatal("expected ok")
   778  		} else if v != 3 {
   779  			t.Fatalf("unexpected value: %v", v)
   780  		}
   781  	})
   782  
   783  	t.Run("KeyEqual", func(t *testing.T) {
   784  		var h defaultHasher[int]
   785  		var resized bool
   786  		n := newMapValueNode(h.Hash(2), 2, 3)
   787  		other := n.set(2, 4, 0, h.Hash(2), &h, false, &resized).(*mapValueNode[int, int])
   788  		if other == n {
   789  			t.Fatal("expected new node")
   790  		} else if got, exp := other.keyHash, h.Hash(2); got != exp {
   791  			t.Fatalf("keyHash=%v, expected %v", got, exp)
   792  		} else if got, exp := other.key, 2; got != exp {
   793  			t.Fatalf("key=%v, expected %v", got, exp)
   794  		} else if got, exp := other.value, 4; got != exp {
   795  			t.Fatalf("value=%v, expected %v", got, exp)
   796  		} else if resized {
   797  			t.Fatal("unexpected resize")
   798  		}
   799  	})
   800  
   801  	t.Run("KeyHashEqual", func(t *testing.T) {
   802  		h := &mockHasher[int]{
   803  			hash:  func(value int) uint32 { return 1 },
   804  			equal: func(a, b int) bool { return a == b },
   805  		}
   806  		var resized bool
   807  		n := newMapValueNode(h.Hash(2), 2, 3)
   808  		other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapHashCollisionNode[int, int])
   809  		if got, exp := other.keyHash, h.Hash(2); got != exp {
   810  			t.Fatalf("keyHash=%v, expected %v", got, exp)
   811  		} else if got, exp := len(other.entries), 2; got != exp {
   812  			t.Fatalf("entries=%v, expected %v", got, exp)
   813  		} else if !resized {
   814  			t.Fatal("expected resize")
   815  		}
   816  		if got, exp := other.entries[0].key, 2; got != exp {
   817  			t.Fatalf("key[0]=%v, expected %v", got, exp)
   818  		} else if got, exp := other.entries[0].value, 3; got != exp {
   819  			t.Fatalf("value[0]=%v, expected %v", got, exp)
   820  		}
   821  		if got, exp := other.entries[1].key, 4; got != exp {
   822  			t.Fatalf("key[1]=%v, expected %v", got, exp)
   823  		} else if got, exp := other.entries[1].value, 5; got != exp {
   824  			t.Fatalf("value[1]=%v, expected %v", got, exp)
   825  		}
   826  	})
   827  
   828  	t.Run("MergeNode", func(t *testing.T) {
   829  		// Inserting into a node with a different index in the mask should split into a bitmap node.
   830  		t.Run("NoConflict", func(t *testing.T) {
   831  			var h defaultHasher[int]
   832  			var resized bool
   833  			n := newMapValueNode(h.Hash(2), 2, 3)
   834  			other := n.set(4, 5, 0, h.Hash(4), &h, false, &resized).(*mapBitmapIndexedNode[int, int])
   835  			if got, exp := other.bitmap, uint32(0x14); got != exp {
   836  				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
   837  			} else if got, exp := len(other.nodes), 2; got != exp {
   838  				t.Fatalf("nodes=%v, expected %v", got, exp)
   839  			} else if !resized {
   840  				t.Fatal("expected resize")
   841  			}
   842  			if node, ok := other.nodes[0].(*mapValueNode[int, int]); !ok {
   843  				t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
   844  			} else if got, exp := node.key, 2; got != exp {
   845  				t.Fatalf("key[0]=%v, expected %v", got, exp)
   846  			} else if got, exp := node.value, 3; got != exp {
   847  				t.Fatalf("value[0]=%v, expected %v", got, exp)
   848  			}
   849  			if node, ok := other.nodes[1].(*mapValueNode[int, int]); !ok {
   850  				t.Fatalf("node[1]=%T, unexpected type", other.nodes[1])
   851  			} else if got, exp := node.key, 4; got != exp {
   852  				t.Fatalf("key[1]=%v, expected %v", got, exp)
   853  			} else if got, exp := node.value, 5; got != exp {
   854  				t.Fatalf("value[1]=%v, expected %v", got, exp)
   855  			}
   856  
   857  			// Ensure both values can be read.
   858  			if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v != 3 {
   859  				t.Fatalf("Get(2)=<%v,%v>", v, ok)
   860  			} else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v != 5 {
   861  				t.Fatalf("Get(4)=<%v,%v>", v, ok)
   862  			}
   863  		})
   864  
   865  		// Reversing the nodes from NoConflict should yield the same result.
   866  		t.Run("NoConflictReverse", func(t *testing.T) {
   867  			var h defaultHasher[int]
   868  			var resized bool
   869  			n := newMapValueNode(h.Hash(4), 4, 5)
   870  			other := n.set(2, 3, 0, h.Hash(2), &h, false, &resized).(*mapBitmapIndexedNode[int, int])
   871  			if got, exp := other.bitmap, uint32(0x14); got != exp {
   872  				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
   873  			} else if got, exp := len(other.nodes), 2; got != exp {
   874  				t.Fatalf("nodes=%v, expected %v", got, exp)
   875  			} else if !resized {
   876  				t.Fatal("expected resize")
   877  			}
   878  			if node, ok := other.nodes[0].(*mapValueNode[int, int]); !ok {
   879  				t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
   880  			} else if got, exp := node.key, 2; got != exp {
   881  				t.Fatalf("key[0]=%v, expected %v", got, exp)
   882  			} else if got, exp := node.value, 3; got != exp {
   883  				t.Fatalf("value[0]=%v, expected %v", got, exp)
   884  			}
   885  			if node, ok := other.nodes[1].(*mapValueNode[int, int]); !ok {
   886  				t.Fatalf("node[1]=%T, unexpected type", other.nodes[1])
   887  			} else if got, exp := node.key, 4; got != exp {
   888  				t.Fatalf("key[1]=%v, expected %v", got, exp)
   889  			} else if got, exp := node.value, 5; got != exp {
   890  				t.Fatalf("value[1]=%v, expected %v", got, exp)
   891  			}
   892  
   893  			// Ensure both values can be read.
   894  			if v, ok := other.get(2, 0, h.Hash(2), &h); !ok || v != 3 {
   895  				t.Fatalf("Get(2)=<%v,%v>", v, ok)
   896  			} else if v, ok := other.get(4, 0, h.Hash(4), &h); !ok || v != 5 {
   897  				t.Fatalf("Get(4)=<%v,%v>", v, ok)
   898  			}
   899  		})
   900  
   901  		// Inserting a node with the same mask index should nest an additional level of bitmap nodes.
   902  		t.Run("Conflict", func(t *testing.T) {
   903  			h := &mockHasher[int]{
   904  				hash:  func(value int) uint32 { return uint32(value << 5) },
   905  				equal: func(a, b int) bool { return a == b },
   906  			}
   907  			var resized bool
   908  			n := newMapValueNode(h.Hash(2), 2, 3)
   909  			other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapBitmapIndexedNode[int, int])
   910  			if got, exp := other.bitmap, uint32(0x01); got != exp { // mask is zero, expect first slot.
   911  				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
   912  			} else if got, exp := len(other.nodes), 1; got != exp {
   913  				t.Fatalf("nodes=%v, expected %v", got, exp)
   914  			} else if !resized {
   915  				t.Fatal("expected resize")
   916  			}
   917  			child, ok := other.nodes[0].(*mapBitmapIndexedNode[int, int])
   918  			if !ok {
   919  				t.Fatalf("node[0]=%T, unexpected type", other.nodes[0])
   920  			}
   921  
   922  			if node, ok := child.nodes[0].(*mapValueNode[int, int]); !ok {
   923  				t.Fatalf("node[0]=%T, unexpected type", child.nodes[0])
   924  			} else if got, exp := node.key, 2; got != exp {
   925  				t.Fatalf("key[0]=%v, expected %v", got, exp)
   926  			} else if got, exp := node.value, 3; got != exp {
   927  				t.Fatalf("value[0]=%v, expected %v", got, exp)
   928  			}
   929  			if node, ok := child.nodes[1].(*mapValueNode[int, int]); !ok {
   930  				t.Fatalf("node[1]=%T, unexpected type", child.nodes[1])
   931  			} else if got, exp := node.key, 4; got != exp {
   932  				t.Fatalf("key[1]=%v, expected %v", got, exp)
   933  			} else if got, exp := node.value, 5; got != exp {
   934  				t.Fatalf("value[1]=%v, expected %v", got, exp)
   935  			}
   936  
   937  			// Ensure both values can be read.
   938  			if v, ok := other.get(2, 0, h.Hash(2), h); !ok || v != 3 {
   939  				t.Fatalf("Get(2)=<%v,%v>", v, ok)
   940  			} else if v, ok := other.get(4, 0, h.Hash(4), h); !ok || v != 5 {
   941  				t.Fatalf("Get(4)=<%v,%v>", v, ok)
   942  			} else if v, ok := other.get(10, 0, h.Hash(10), h); ok {
   943  				t.Fatalf("Get(10)=<%v,%v>, expected no value", v, ok)
   944  			}
   945  		})
   946  	})
   947  }
   948  
   949  func TestMap_Get(t *testing.T) {
   950  	t.Run("Empty", func(t *testing.T) {
   951  		m := NewMap[int, string](nil)
   952  		if v, ok := m.Get(100); ok {
   953  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
   954  		}
   955  	})
   956  }
   957  
   958  func TestMap_Set(t *testing.T) {
   959  	t.Run("Simple", func(t *testing.T) {
   960  		m := NewMap[int, string](nil)
   961  		itr := m.Iterator()
   962  		if !itr.Done() {
   963  			t.Fatal("MapIterator.Done()=true, expected false")
   964  		} else if k, v, ok := itr.Next(); ok {
   965  			t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
   966  		}
   967  	})
   968  
   969  	t.Run("Simple", func(t *testing.T) {
   970  		m := NewMap[int, string](nil)
   971  		m = m.Set(100, "foo")
   972  		if v, ok := m.Get(100); !ok || v != "foo" {
   973  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
   974  		}
   975  	})
   976  
   977  	t.Run("Multi", func(t *testing.T) {
   978  		m := NewMapOf(nil, map[int]string{1: "foo"})
   979  		itr := m.Iterator()
   980  		if itr.Done() {
   981  			t.Fatal("MapIterator.Done()=false, expected true")
   982  		}
   983  		if k, v, ok := itr.Next(); !ok {
   984  			t.Fatalf("MapIterator.Next()!=ok, expected ok")
   985  		} else if k != 1 || v != "foo" {
   986  			t.Fatalf("MapIterator.Next()=<%v,%v>, expected <1, \"foo\">", k, v)
   987  		}
   988  		if k, v, ok := itr.Next(); ok {
   989  			t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
   990  		}
   991  	})
   992  
   993  	t.Run("VerySmall", func(t *testing.T) {
   994  		const n = 6
   995  		m := NewMap[int, int](nil)
   996  		for i := 0; i < n; i++ {
   997  			m = m.Set(i, i+1)
   998  		}
   999  		for i := 0; i < n; i++ {
  1000  			if v, ok := m.Get(i); !ok || v != i+1 {
  1001  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1002  			}
  1003  		}
  1004  
  1005  		// NOTE: Array nodes store entries in insertion order.
  1006  		itr := m.Iterator()
  1007  		for i := 0; i < n; i++ {
  1008  			if k, v, ok := itr.Next(); !ok || k != i || v != i+1 {
  1009  				t.Fatalf("MapIterator.Next()=<%v,%v>, exp <%v,%v>", k, v, i, i+1)
  1010  			}
  1011  		}
  1012  		if !itr.Done() {
  1013  			t.Fatal("expected iterator done")
  1014  		}
  1015  	})
  1016  
  1017  	t.Run("Small", func(t *testing.T) {
  1018  		const n = 1000
  1019  		m := NewMap[int, int](nil)
  1020  		for i := 0; i < n; i++ {
  1021  			m = m.Set(i, i+1)
  1022  		}
  1023  		for i := 0; i < n; i++ {
  1024  			if v, ok := m.Get(i); !ok || v != i+1 {
  1025  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1026  			}
  1027  		}
  1028  	})
  1029  
  1030  	t.Run("Large", func(t *testing.T) {
  1031  		if testing.Short() {
  1032  			t.Skip("skipping: short")
  1033  		}
  1034  
  1035  		const n = 1000000
  1036  		m := NewMap[int, int](nil)
  1037  		for i := 0; i < n; i++ {
  1038  			m = m.Set(i, i+1)
  1039  		}
  1040  		for i := 0; i < n; i++ {
  1041  			if v, ok := m.Get(i); !ok || v != i+1 {
  1042  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1043  			}
  1044  		}
  1045  	})
  1046  
  1047  	t.Run("StringKeys", func(t *testing.T) {
  1048  		m := NewMap[string, string](nil)
  1049  		m = m.Set("foo", "bar")
  1050  		m = m.Set("baz", "bat")
  1051  		m = m.Set("", "EMPTY")
  1052  		if v, ok := m.Get("foo"); !ok || v != "bar" {
  1053  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1054  		} else if v, ok := m.Get("baz"); !ok || v != "bat" {
  1055  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1056  		} else if v, ok := m.Get(""); !ok || v != "EMPTY" {
  1057  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1058  		}
  1059  		if v, ok := m.Get("no_such_key"); ok {
  1060  			t.Fatalf("expected no value: <%v,%v>", v, ok)
  1061  		}
  1062  	})
  1063  
  1064  	RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
  1065  		m := NewTestMap()
  1066  		for i := 0; i < 10000; i++ {
  1067  			switch rand.Intn(2) {
  1068  			case 1: // overwrite
  1069  				m.Set(m.ExistingKey(rand), rand.Intn(10000))
  1070  			default: // set new key
  1071  				m.Set(m.NewKey(rand), rand.Intn(10000))
  1072  			}
  1073  		}
  1074  		if err := m.Validate(); err != nil {
  1075  			t.Fatal(err)
  1076  		}
  1077  	})
  1078  }
  1079  
  1080  // Ensure map can support overwrites as it expands.
  1081  func TestMap_Overwrite(t *testing.T) {
  1082  	if testing.Short() {
  1083  		t.Skip("short mode")
  1084  	}
  1085  
  1086  	const n = 10000
  1087  	m := NewMap[int, int](nil)
  1088  	for i := 0; i < n; i++ {
  1089  		// Set original value.
  1090  		m = m.Set(i, i)
  1091  
  1092  		// Overwrite every node.
  1093  		for j := 0; j <= i; j++ {
  1094  			m = m.Set(j, i*j)
  1095  		}
  1096  	}
  1097  
  1098  	// Verify all key/value pairs in map.
  1099  	for i := 0; i < n; i++ {
  1100  		if v, ok := m.Get(i); !ok || v != i*(n-1) {
  1101  			t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
  1102  		}
  1103  	}
  1104  
  1105  	t.Run("Simple", func(t *testing.T) {
  1106  		m := NewMap[int, string](nil)
  1107  		itr := m.Iterator()
  1108  		if !itr.Done() {
  1109  			t.Fatal("MapIterator.Done()=true, expected false")
  1110  		} else if k, v, ok := itr.Next(); ok {
  1111  			t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v)
  1112  		}
  1113  	})
  1114  }
  1115  
  1116  func TestMap_Delete(t *testing.T) {
  1117  	t.Run("Empty", func(t *testing.T) {
  1118  		m := NewMap[string, int](nil)
  1119  		other := m.Delete("foo")
  1120  		if m != other {
  1121  			t.Fatal("expected same map")
  1122  		}
  1123  	})
  1124  
  1125  	t.Run("Simple", func(t *testing.T) {
  1126  		m := NewMap[int, string](nil)
  1127  		m = m.Set(100, "foo")
  1128  		if v, ok := m.Get(100); !ok || v != "foo" {
  1129  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1130  		}
  1131  	})
  1132  
  1133  	t.Run("Small", func(t *testing.T) {
  1134  		const n = 1000
  1135  		m := NewMap[int, int](nil)
  1136  		for i := 0; i < n; i++ {
  1137  			m = m.Set(i, i+1)
  1138  		}
  1139  		for i := range rand.New(rand.NewSource(0)).Perm(n) {
  1140  			m = m.Delete(i)
  1141  		}
  1142  		if m.Len() != 0 {
  1143  			t.Fatalf("expected no elements, got %d", m.Len())
  1144  		}
  1145  	})
  1146  
  1147  	t.Run("Large", func(t *testing.T) {
  1148  		if testing.Short() {
  1149  			t.Skip("skipping: short")
  1150  		}
  1151  		const n = 1000000
  1152  		m := NewMap[int, int](nil)
  1153  		for i := 0; i < n; i++ {
  1154  			m = m.Set(i, i+1)
  1155  		}
  1156  		for i := range rand.New(rand.NewSource(0)).Perm(n) {
  1157  			m = m.Delete(i)
  1158  		}
  1159  		if m.Len() != 0 {
  1160  			t.Fatalf("expected no elements, got %d", m.Len())
  1161  		}
  1162  	})
  1163  
  1164  	RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
  1165  		m := NewTestMap()
  1166  		for i := 0; i < 10000; i++ {
  1167  			switch rand.Intn(8) {
  1168  			case 0: // overwrite
  1169  				m.Set(m.ExistingKey(rand), rand.Intn(10000))
  1170  			case 1: // delete existing key
  1171  				m.Delete(m.ExistingKey(rand))
  1172  			case 2: // delete non-existent key.
  1173  				m.Delete(m.NewKey(rand))
  1174  			default: // set new key
  1175  				m.Set(m.NewKey(rand), rand.Intn(10000))
  1176  			}
  1177  		}
  1178  
  1179  		// Delete all and verify they are gone.
  1180  		keys := make([]int, len(m.keys))
  1181  		copy(keys, m.keys)
  1182  
  1183  		for _, key := range keys {
  1184  			m.Delete(key)
  1185  		}
  1186  		if err := m.Validate(); err != nil {
  1187  			t.Fatal(err)
  1188  		}
  1189  	})
  1190  }
  1191  
  1192  // Ensure map works even with hash conflicts.
  1193  func TestMap_LimitedHash(t *testing.T) {
  1194  	if testing.Short() {
  1195  		t.Skip("skipping: short")
  1196  	}
  1197  
  1198  	t.Run("Immutable", func(t *testing.T) {
  1199  		h := mockHasher[int]{
  1200  			hash:  func(value int) uint32 { return hashUint64(uint64(value)) % 0xFF },
  1201  			equal: func(a, b int) bool { return a == b },
  1202  		}
  1203  		m := NewMap[int, int](&h)
  1204  
  1205  		rand := rand.New(rand.NewSource(0))
  1206  		keys := rand.Perm(100000)
  1207  		for _, i := range keys {
  1208  			m = m.Set(i, i) // initial set
  1209  		}
  1210  		for i := range keys {
  1211  			m = m.Set(i, i*2) // overwrite
  1212  		}
  1213  		if m.Len() != len(keys) {
  1214  			t.Fatalf("unexpected len: %d", m.Len())
  1215  		}
  1216  
  1217  		// Verify all key/value pairs in map.
  1218  		for i := 0; i < m.Len(); i++ {
  1219  			if v, ok := m.Get(i); !ok || v != i*2 {
  1220  				t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
  1221  			}
  1222  		}
  1223  
  1224  		// Verify iteration.
  1225  		itr := m.Iterator()
  1226  		for !itr.Done() {
  1227  			if k, v, ok := itr.Next(); !ok || v != k*2 {
  1228  				t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k*2)
  1229  			}
  1230  		}
  1231  
  1232  		// Verify not found works.
  1233  		if _, ok := m.Get(10000000); ok {
  1234  			t.Fatal("expected no value")
  1235  		}
  1236  
  1237  		// Verify delete non-existent key works.
  1238  		if other := m.Delete(10000000 + 1); m != other {
  1239  			t.Fatal("expected no change")
  1240  		}
  1241  
  1242  		// Remove all keys.
  1243  		for _, key := range keys {
  1244  			m = m.Delete(key)
  1245  		}
  1246  		if m.Len() != 0 {
  1247  			t.Fatalf("unexpected size: %d", m.Len())
  1248  		}
  1249  	})
  1250  
  1251  	t.Run("Builder", func(t *testing.T) {
  1252  		h := mockHasher[int]{
  1253  			hash:  func(value int) uint32 { return hashUint64(uint64(value)) },
  1254  			equal: func(a, b int) bool { return a == b },
  1255  		}
  1256  		b := NewMapBuilder[int, int](&h)
  1257  
  1258  		rand := rand.New(rand.NewSource(0))
  1259  		keys := rand.Perm(100000)
  1260  		for _, i := range keys {
  1261  			b.Set(i, i) // initial set
  1262  		}
  1263  		for i := range keys {
  1264  			b.Set(i, i*2) // overwrite
  1265  		}
  1266  		if b.Len() != len(keys) {
  1267  			t.Fatalf("unexpected len: %d", b.Len())
  1268  		}
  1269  
  1270  		// Verify all key/value pairs in map.
  1271  		for i := 0; i < b.Len(); i++ {
  1272  			if v, ok := b.Get(i); !ok || v != i*2 {
  1273  				t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
  1274  			}
  1275  		}
  1276  
  1277  		// Verify iteration.
  1278  		itr := b.Iterator()
  1279  		for !itr.Done() {
  1280  			if k, v, ok := itr.Next(); !ok || v != k*2 {
  1281  				t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k*2)
  1282  			}
  1283  		}
  1284  
  1285  		// Verify not found works.
  1286  		if _, ok := b.Get(10000000); ok {
  1287  			t.Fatal("expected no value")
  1288  		}
  1289  
  1290  		// Remove all keys.
  1291  		for _, key := range keys {
  1292  			b.Delete(key)
  1293  		}
  1294  		if b.Len() != 0 {
  1295  			t.Fatalf("unexpected size: %d", b.Len())
  1296  		}
  1297  	})
  1298  }
  1299  
  1300  // TMap represents a combined immutable and stdlib map.
  1301  type TMap struct {
  1302  	im, prev *Map[int, int]
  1303  	builder  *MapBuilder[int, int]
  1304  	std      map[int]int
  1305  	keys     []int
  1306  }
  1307  
  1308  func NewTestMap() *TMap {
  1309  	return &TMap{
  1310  		im:      NewMap[int, int](nil),
  1311  		builder: NewMapBuilder[int, int](nil),
  1312  		std:     make(map[int]int),
  1313  	}
  1314  }
  1315  
  1316  func (m *TMap) NewKey(rand *rand.Rand) int {
  1317  	for {
  1318  		k := rand.Int()
  1319  		if _, ok := m.std[k]; !ok {
  1320  			return k
  1321  		}
  1322  	}
  1323  }
  1324  
  1325  func (m *TMap) ExistingKey(rand *rand.Rand) int {
  1326  	if len(m.keys) == 0 {
  1327  		return 0
  1328  	}
  1329  	return m.keys[rand.Intn(len(m.keys))]
  1330  }
  1331  
  1332  func (m *TMap) Set(k, v int) {
  1333  	m.prev = m.im
  1334  	m.im = m.im.Set(k, v)
  1335  	m.builder.Set(k, v)
  1336  
  1337  	_, exists := m.std[k]
  1338  	if !exists {
  1339  		m.keys = append(m.keys, k)
  1340  	}
  1341  	m.std[k] = v
  1342  }
  1343  
  1344  func (m *TMap) Delete(k int) {
  1345  	m.prev = m.im
  1346  	m.im = m.im.Delete(k)
  1347  	m.builder.Delete(k)
  1348  	delete(m.std, k)
  1349  
  1350  	for i := range m.keys {
  1351  		if m.keys[i] == k {
  1352  			m.keys = append(m.keys[:i], m.keys[i+1:]...)
  1353  			break
  1354  		}
  1355  	}
  1356  }
  1357  
  1358  func (m *TMap) Validate() error {
  1359  	for _, k := range m.keys {
  1360  		if v, ok := m.im.Get(k); !ok {
  1361  			return fmt.Errorf("key not found: %d", k)
  1362  		} else if v != m.std[k] {
  1363  			return fmt.Errorf("key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
  1364  		}
  1365  		if v, ok := m.builder.Get(k); !ok {
  1366  			return fmt.Errorf("builder key not found: %d", k)
  1367  		} else if v != m.std[k] {
  1368  			return fmt.Errorf("builder key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
  1369  		}
  1370  	}
  1371  	if err := m.validateIterator(m.im.Iterator()); err != nil {
  1372  		return fmt.Errorf("basic: %s", err)
  1373  	} else if err := m.validateIterator(m.builder.Iterator()); err != nil {
  1374  		return fmt.Errorf("builder: %s", err)
  1375  	}
  1376  	return nil
  1377  }
  1378  
  1379  func (m *TMap) validateIterator(itr *MapIterator[int, int]) error {
  1380  	other := make(map[int]int)
  1381  	for !itr.Done() {
  1382  		k, v, _ := itr.Next()
  1383  		other[k] = v
  1384  	}
  1385  	if len(other) != len(m.std) {
  1386  		return fmt.Errorf("map iterator size mismatch: %v!=%v", len(m.std), len(other))
  1387  	}
  1388  	for k, v := range m.std {
  1389  		if v != other[k] {
  1390  			return fmt.Errorf("map iterator mismatch: key=%v, %v!=%v", k, v, other[k])
  1391  		}
  1392  	}
  1393  	if k, v, ok := itr.Next(); ok {
  1394  		return fmt.Errorf("map iterator returned key/value after done: <%v/%v>", k, v)
  1395  	}
  1396  	return nil
  1397  }
  1398  
  1399  func BenchmarkBuiltinMap_Set(b *testing.B) {
  1400  	b.ReportAllocs()
  1401  	m := make(map[int]int)
  1402  	for i := 0; i < b.N; i++ {
  1403  		m[i] = i
  1404  	}
  1405  }
  1406  
  1407  func BenchmarkBuiltinMap_Delete(b *testing.B) {
  1408  	const n = 10000000
  1409  
  1410  	m := make(map[int]int)
  1411  	for i := 0; i < n; i++ {
  1412  		m[i] = i
  1413  	}
  1414  	b.ReportAllocs()
  1415  	b.ResetTimer()
  1416  
  1417  	for i := 0; i < b.N; i++ {
  1418  		delete(m, i%n)
  1419  	}
  1420  }
  1421  
  1422  func BenchmarkMap_Set(b *testing.B) {
  1423  	b.ReportAllocs()
  1424  	m := NewMap[int, int](nil)
  1425  	for i := 0; i < b.N; i++ {
  1426  		m = m.Set(i, i)
  1427  	}
  1428  }
  1429  
  1430  func BenchmarkMap_Delete(b *testing.B) {
  1431  	const n = 10000000
  1432  
  1433  	builder := NewMapBuilder[int, int](nil)
  1434  	for i := 0; i < n; i++ {
  1435  		builder.Set(i, i)
  1436  	}
  1437  	b.ReportAllocs()
  1438  	b.ResetTimer()
  1439  
  1440  	m := builder.Map()
  1441  	for i := 0; i < b.N; i++ {
  1442  		m.Delete(i % n) // Do not update map, always operate on original
  1443  	}
  1444  }
  1445  
  1446  func BenchmarkMap_Iterator(b *testing.B) {
  1447  	const n = 10000
  1448  	m := NewMap[int, int](nil)
  1449  	for i := 0; i < 10000; i++ {
  1450  		m = m.Set(i, i)
  1451  	}
  1452  	b.ReportAllocs()
  1453  	b.ResetTimer()
  1454  
  1455  	b.Run("Forward", func(b *testing.B) {
  1456  		itr := m.Iterator()
  1457  		for i := 0; i < b.N; i++ {
  1458  			if i%n == 0 {
  1459  				itr.First()
  1460  			}
  1461  			itr.Next()
  1462  		}
  1463  	})
  1464  }
  1465  
  1466  func BenchmarkMapBuilder_Set(b *testing.B) {
  1467  	b.ReportAllocs()
  1468  	builder := NewMapBuilder[int, int](nil)
  1469  	for i := 0; i < b.N; i++ {
  1470  		builder.Set(i, i)
  1471  	}
  1472  }
  1473  
  1474  func BenchmarkMapBuilder_Delete(b *testing.B) {
  1475  	const n = 10000000
  1476  
  1477  	builder := NewMapBuilder[int, int](nil)
  1478  	for i := 0; i < n; i++ {
  1479  		builder.Set(i, i)
  1480  	}
  1481  	b.ReportAllocs()
  1482  	b.ResetTimer()
  1483  
  1484  	for i := 0; i < b.N; i++ {
  1485  		builder.Delete(i % n)
  1486  	}
  1487  }
  1488  
  1489  func ExampleMap_Set() {
  1490  	m := NewMap[string, any](nil)
  1491  	m = m.Set("foo", "bar")
  1492  	m = m.Set("baz", 100)
  1493  
  1494  	v, ok := m.Get("foo")
  1495  	fmt.Println("foo", v, ok)
  1496  
  1497  	v, ok = m.Get("baz")
  1498  	fmt.Println("baz", v, ok)
  1499  
  1500  	v, ok = m.Get("bat") // does not exist
  1501  	fmt.Println("bat", v, ok)
  1502  	// Output:
  1503  	// foo bar true
  1504  	// baz 100 true
  1505  	// bat <nil> false
  1506  }
  1507  
  1508  func ExampleMap_Delete() {
  1509  	m := NewMap[string, any](nil)
  1510  	m = m.Set("foo", "bar")
  1511  	m = m.Set("baz", 100)
  1512  	m = m.Delete("baz")
  1513  
  1514  	v, ok := m.Get("foo")
  1515  	fmt.Println("foo", v, ok)
  1516  
  1517  	v, ok = m.Get("baz")
  1518  	fmt.Println("baz", v, ok)
  1519  	// Output:
  1520  	// foo bar true
  1521  	// baz <nil> false
  1522  }
  1523  
  1524  func ExampleMap_Iterator() {
  1525  	m := NewMap[string, int](nil)
  1526  	m = m.Set("apple", 100)
  1527  	m = m.Set("grape", 200)
  1528  	m = m.Set("kiwi", 300)
  1529  	m = m.Set("mango", 400)
  1530  	m = m.Set("orange", 500)
  1531  	m = m.Set("peach", 600)
  1532  	m = m.Set("pear", 700)
  1533  	m = m.Set("pineapple", 800)
  1534  	m = m.Set("strawberry", 900)
  1535  
  1536  	itr := m.Iterator()
  1537  	for !itr.Done() {
  1538  		k, v, _ := itr.Next()
  1539  		fmt.Println(k, v)
  1540  	}
  1541  	// Output:
  1542  	// mango 400
  1543  	// pear 700
  1544  	// pineapple 800
  1545  	// grape 200
  1546  	// orange 500
  1547  	// strawberry 900
  1548  	// kiwi 300
  1549  	// peach 600
  1550  	// apple 100
  1551  }
  1552  
  1553  func ExampleMapBuilder_Set() {
  1554  	b := NewMapBuilder[string, any](nil)
  1555  	b.Set("foo", "bar")
  1556  	b.Set("baz", 100)
  1557  
  1558  	m := b.Map()
  1559  	v, ok := m.Get("foo")
  1560  	fmt.Println("foo", v, ok)
  1561  
  1562  	v, ok = m.Get("baz")
  1563  	fmt.Println("baz", v, ok)
  1564  
  1565  	v, ok = m.Get("bat") // does not exist
  1566  	fmt.Println("bat", v, ok)
  1567  	// Output:
  1568  	// foo bar true
  1569  	// baz 100 true
  1570  	// bat <nil> false
  1571  }
  1572  
  1573  func ExampleMapBuilder_Delete() {
  1574  	b := NewMapBuilder[string, any](nil)
  1575  	b.Set("foo", "bar")
  1576  	b.Set("baz", 100)
  1577  	b.Delete("baz")
  1578  
  1579  	m := b.Map()
  1580  	v, ok := m.Get("foo")
  1581  	fmt.Println("foo", v, ok)
  1582  
  1583  	v, ok = m.Get("baz")
  1584  	fmt.Println("baz", v, ok)
  1585  	// Output:
  1586  	// foo bar true
  1587  	// baz <nil> false
  1588  }
  1589  
  1590  func TestInternalSortedMapLeafNode(t *testing.T) {
  1591  	RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
  1592  		var cmpr defaultComparer[int]
  1593  		var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
  1594  		var keys []int
  1595  		for _, i := range rand.Perm(32) {
  1596  			var resized bool
  1597  			var splitNode sortedMapNode[int, int]
  1598  			node, splitNode = node.set(i, i*10, &cmpr, false, &resized)
  1599  			if !resized {
  1600  				t.Fatal("expected resize")
  1601  			} else if splitNode != nil {
  1602  				t.Fatal("expected split")
  1603  			}
  1604  			keys = append(keys, i)
  1605  
  1606  			// Verify not found at each size.
  1607  			if _, ok := node.get(rand.Int()+32, &cmpr); ok {
  1608  				t.Fatal("expected no value")
  1609  			}
  1610  
  1611  			// Verify min key is always the lowest.
  1612  			sort.Ints(keys)
  1613  			if got, exp := node.minKey(), keys[0]; got != exp {
  1614  				t.Fatalf("minKey()=%d, expected %d", got, exp)
  1615  			}
  1616  		}
  1617  
  1618  		// Verify all key/value pairs in node.
  1619  		for i := range keys {
  1620  			if v, ok := node.get(i, &cmpr); !ok || v != i*10 {
  1621  				t.Fatalf("get(%d)=<%v,%v>", i, v, ok)
  1622  			}
  1623  		}
  1624  	})
  1625  
  1626  	RunRandom(t, "Overwrite", func(t *testing.T, rand *rand.Rand) {
  1627  		var cmpr defaultComparer[int]
  1628  		var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
  1629  
  1630  		for _, i := range rand.Perm(32) {
  1631  			var resized bool
  1632  			node, _ = node.set(i, i*2, &cmpr, false, &resized)
  1633  		}
  1634  		for _, i := range rand.Perm(32) {
  1635  			var resized bool
  1636  			node, _ = node.set(i, i*3, &cmpr, false, &resized)
  1637  			if resized {
  1638  				t.Fatal("expected no resize")
  1639  			}
  1640  		}
  1641  
  1642  		// Verify all overwritten key/value pairs in node.
  1643  		for i := 0; i < 32; i++ {
  1644  			if v, ok := node.get(i, &cmpr); !ok || v != i*3 {
  1645  				t.Fatalf("get(%d)=<%v,%v>", i, v, ok)
  1646  			}
  1647  		}
  1648  	})
  1649  
  1650  	t.Run("Split", func(t *testing.T) {
  1651  		// Fill leaf node.		var cmpr defaultComparer[int]
  1652  		var cmpr defaultComparer[int]
  1653  		var node sortedMapNode[int, int] = &sortedMapLeafNode[int, int]{}
  1654  		for i := 0; i < 32; i++ {
  1655  			var resized bool
  1656  			node, _ = node.set(i, i*10, &cmpr, false, &resized)
  1657  		}
  1658  
  1659  		// Add one more and expect split.
  1660  		var resized bool
  1661  		newNode, splitNode := node.set(32, 320, &cmpr, false, &resized)
  1662  
  1663  		// Verify node contents.
  1664  		newLeafNode, ok := newNode.(*sortedMapLeafNode[int, int])
  1665  		if !ok {
  1666  			t.Fatalf("unexpected node type: %T", newLeafNode)
  1667  		} else if n := len(newLeafNode.entries); n != 16 {
  1668  			t.Fatalf("unexpected node len: %d", n)
  1669  		}
  1670  		for i := range newLeafNode.entries {
  1671  			if entry := newLeafNode.entries[i]; entry.key != i || entry.value != i*10 {
  1672  				t.Fatalf("%d. unexpected entry: %v=%v", i, entry.key, entry.value)
  1673  			}
  1674  		}
  1675  
  1676  		// Verify split node contents.
  1677  		splitLeafNode, ok := splitNode.(*sortedMapLeafNode[int, int])
  1678  		if !ok {
  1679  			t.Fatalf("unexpected split node type: %T", splitLeafNode)
  1680  		} else if n := len(splitLeafNode.entries); n != 17 {
  1681  			t.Fatalf("unexpected split node len: %d", n)
  1682  		}
  1683  		for i := range splitLeafNode.entries {
  1684  			if entry := splitLeafNode.entries[i]; entry.key != (i+16) || entry.value != (i+16)*10 {
  1685  				t.Fatalf("%d. unexpected split node entry: %v=%v", i, entry.key, entry.value)
  1686  			}
  1687  		}
  1688  	})
  1689  }
  1690  
  1691  func TestInternalSortedMapBranchNode(t *testing.T) {
  1692  	RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
  1693  		keys := make([]int, 32*16)
  1694  		for i := range keys {
  1695  			keys[i] = rand.Intn(10000)
  1696  		}
  1697  		keys = uniqueIntSlice(keys)
  1698  		sort.Ints(keys[:2]) // ensure first two keys are sorted for initial insert.
  1699  
  1700  		// Initialize branch with two leafs.
  1701  		var cmpr defaultComparer[int]
  1702  		leaf0 := &sortedMapLeafNode[int, int]{entries: []mapEntry[int, int]{{key: keys[0], value: keys[0] * 10}}}
  1703  		leaf1 := &sortedMapLeafNode[int, int]{entries: []mapEntry[int, int]{{key: keys[1], value: keys[1] * 10}}}
  1704  		var node sortedMapNode[int, int] = newSortedMapBranchNode[int, int](leaf0, leaf1)
  1705  
  1706  		sort.Ints(keys)
  1707  		for _, i := range rand.Perm(len(keys)) {
  1708  			key := keys[i]
  1709  
  1710  			var resized bool
  1711  			var splitNode sortedMapNode[int, int]
  1712  			node, splitNode = node.set(key, key*10, &cmpr, false, &resized)
  1713  			if key == leaf0.entries[0].key || key == leaf1.entries[0].key {
  1714  				if resized {
  1715  					t.Fatalf("expected no resize: key=%d", key)
  1716  				}
  1717  			} else {
  1718  				if !resized {
  1719  					t.Fatalf("expected resize: key=%d", key)
  1720  				}
  1721  			}
  1722  			if splitNode != nil {
  1723  				t.Fatal("unexpected split")
  1724  			}
  1725  		}
  1726  
  1727  		// Verify all key/value pairs in node.
  1728  		for _, key := range keys {
  1729  			if v, ok := node.get(key, &cmpr); !ok || v != key*10 {
  1730  				t.Fatalf("get(%d)=<%v,%v>", key, v, ok)
  1731  			}
  1732  		}
  1733  
  1734  		// Verify min key is the lowest key.
  1735  		if got, exp := node.minKey(), keys[0]; got != exp {
  1736  			t.Fatalf("minKey()=%d, expected %d", got, exp)
  1737  		}
  1738  	})
  1739  
  1740  	t.Run("Split", func(t *testing.T) {
  1741  		// Generate leaf nodes.
  1742  		var cmpr defaultComparer[int]
  1743  		children := make([]sortedMapNode[int, int], 32)
  1744  		for i := range children {
  1745  			leaf := &sortedMapLeafNode[int, int]{entries: make([]mapEntry[int, int], 32)}
  1746  			for j := range leaf.entries {
  1747  				leaf.entries[j] = mapEntry[int, int]{key: (i * 32) + j, value: ((i * 32) + j) * 100}
  1748  			}
  1749  			children[i] = leaf
  1750  		}
  1751  		var node sortedMapNode[int, int] = newSortedMapBranchNode(children...)
  1752  
  1753  		// Add one more and expect split.
  1754  		var resized bool
  1755  		newNode, splitNode := node.set((32 * 32), (32*32)*100, &cmpr, false, &resized)
  1756  
  1757  		// Verify node contents.
  1758  		var idx int
  1759  		newBranchNode, ok := newNode.(*sortedMapBranchNode[int, int])
  1760  		if !ok {
  1761  			t.Fatalf("unexpected node type: %T", newBranchNode)
  1762  		} else if n := len(newBranchNode.elems); n != 16 {
  1763  			t.Fatalf("unexpected child elems len: %d", n)
  1764  		}
  1765  		for i, elem := range newBranchNode.elems {
  1766  			child, ok := elem.node.(*sortedMapLeafNode[int, int])
  1767  			if !ok {
  1768  				t.Fatalf("unexpected child type")
  1769  			}
  1770  			for j, entry := range child.entries {
  1771  				if entry.key != idx || entry.value != idx*100 {
  1772  					t.Fatalf("%d/%d. unexpected entry: %v=%v", i, j, entry.key, entry.value)
  1773  				}
  1774  				idx++
  1775  			}
  1776  		}
  1777  
  1778  		// Verify split node contents.
  1779  		splitBranchNode, ok := splitNode.(*sortedMapBranchNode[int, int])
  1780  		if !ok {
  1781  			t.Fatalf("unexpected split node type: %T", splitBranchNode)
  1782  		} else if n := len(splitBranchNode.elems); n != 17 {
  1783  			t.Fatalf("unexpected split node elem len: %d", n)
  1784  		}
  1785  		for i, elem := range splitBranchNode.elems {
  1786  			child, ok := elem.node.(*sortedMapLeafNode[int, int])
  1787  			if !ok {
  1788  				t.Fatalf("unexpected split node child type")
  1789  			}
  1790  			for j, entry := range child.entries {
  1791  				if entry.key != idx || entry.value != idx*100 {
  1792  					t.Fatalf("%d/%d. unexpected split node entry: %v=%v", i, j, entry.key, entry.value)
  1793  				}
  1794  				idx++
  1795  			}
  1796  		}
  1797  	})
  1798  }
  1799  
  1800  func TestSortedMap_Get(t *testing.T) {
  1801  	t.Run("Empty", func(t *testing.T) {
  1802  		m := NewSortedMap[int, int](nil)
  1803  		if v, ok := m.Get(100); ok {
  1804  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1805  		}
  1806  	})
  1807  }
  1808  
  1809  func TestSortedMap_Set(t *testing.T) {
  1810  	t.Run("Simple", func(t *testing.T) {
  1811  		m := NewSortedMap[int, string](nil)
  1812  		m = m.Set(100, "foo")
  1813  		if v, ok := m.Get(100); !ok || v != "foo" {
  1814  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1815  		} else if got, exp := m.Len(), 1; got != exp {
  1816  			t.Fatalf("SortedMap.Len()=%d, exp %d", got, exp)
  1817  		}
  1818  	})
  1819  
  1820  	t.Run("Small", func(t *testing.T) {
  1821  		const n = 1000
  1822  		m := NewSortedMap[int, int](nil)
  1823  		for i := 0; i < n; i++ {
  1824  			m = m.Set(i, i+1)
  1825  		}
  1826  		for i := 0; i < n; i++ {
  1827  			if v, ok := m.Get(i); !ok || v != i+1 {
  1828  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1829  			}
  1830  		}
  1831  	})
  1832  
  1833  	t.Run("Large", func(t *testing.T) {
  1834  		if testing.Short() {
  1835  			t.Skip("skipping: short")
  1836  		}
  1837  
  1838  		const n = 1000000
  1839  		m := NewSortedMap[int, int](nil)
  1840  		for i := 0; i < n; i++ {
  1841  			m = m.Set(i, i+1)
  1842  		}
  1843  		for i := 0; i < n; i++ {
  1844  			if v, ok := m.Get(i); !ok || v != i+1 {
  1845  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1846  			}
  1847  		}
  1848  	})
  1849  
  1850  	t.Run("StringKeys", func(t *testing.T) {
  1851  		m := NewSortedMap[string, string](nil)
  1852  		m = m.Set("foo", "bar")
  1853  		m = m.Set("baz", "bat")
  1854  		m = m.Set("", "EMPTY")
  1855  		if v, ok := m.Get("foo"); !ok || v != "bar" {
  1856  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1857  		} else if v, ok := m.Get("baz"); !ok || v != "bat" {
  1858  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1859  		} else if v, ok := m.Get(""); !ok || v != "EMPTY" {
  1860  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1861  		}
  1862  		if v, ok := m.Get("no_such_key"); ok {
  1863  			t.Fatalf("expected no value: <%v,%v>", v, ok)
  1864  		}
  1865  	})
  1866  
  1867  	t.Run("NoDefaultComparer", func(t *testing.T) {
  1868  		var r string
  1869  		func() {
  1870  			defer func() { r = recover().(string) }()
  1871  			m := NewSortedMap[float64, string](nil)
  1872  			m = m.Set(float64(100), "bar")
  1873  		}()
  1874  		if r != `immutable.NewComparer: must set comparer for float64 type` {
  1875  			t.Fatalf("unexpected panic: %q", r)
  1876  		}
  1877  	})
  1878  
  1879  	RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
  1880  		m := NewTSortedMap()
  1881  		for j := 0; j < 10000; j++ {
  1882  			switch rand.Intn(2) {
  1883  			case 1: // overwrite
  1884  				m.Set(m.ExistingKey(rand), rand.Intn(10000))
  1885  			default: // set new key
  1886  				m.Set(m.NewKey(rand), rand.Intn(10000))
  1887  			}
  1888  		}
  1889  		if err := m.Validate(); err != nil {
  1890  			t.Fatal(err)
  1891  		}
  1892  	})
  1893  }
  1894  
  1895  // Ensure map can support overwrites as it expands.
  1896  func TestSortedMap_Overwrite(t *testing.T) {
  1897  	const n = 1000
  1898  	m := NewSortedMap[int, int](nil)
  1899  	for i := 0; i < n; i++ {
  1900  		// Set original value.
  1901  		m = m.Set(i, i)
  1902  
  1903  		// Overwrite every node.
  1904  		for j := 0; j <= i; j++ {
  1905  			m = m.Set(j, i*j)
  1906  		}
  1907  	}
  1908  
  1909  	// Verify all key/value pairs in map.
  1910  	for i := 0; i < n; i++ {
  1911  		if v, ok := m.Get(i); !ok || v != i*(n-1) {
  1912  			t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
  1913  		}
  1914  	}
  1915  }
  1916  
  1917  func TestSortedMap_Delete(t *testing.T) {
  1918  	t.Run("Empty", func(t *testing.T) {
  1919  		m := NewSortedMap[int, int](nil)
  1920  		m = m.Delete(100)
  1921  		if n := m.Len(); n != 0 {
  1922  			t.Fatalf("SortedMap.Len()=%d, expected 0", n)
  1923  		}
  1924  	})
  1925  
  1926  	t.Run("Simple", func(t *testing.T) {
  1927  		m := NewSortedMap[int, string](nil)
  1928  		m = m.Set(100, "foo")
  1929  		if v, ok := m.Get(100); !ok || v != "foo" {
  1930  			t.Fatalf("unexpected value: <%v,%v>", v, ok)
  1931  		}
  1932  		m = m.Delete(100)
  1933  		if v, ok := m.Get(100); ok {
  1934  			t.Fatalf("unexpected no value: <%v,%v>", v, ok)
  1935  		}
  1936  	})
  1937  
  1938  	t.Run("Small", func(t *testing.T) {
  1939  		const n = 1000
  1940  		m := NewSortedMap[int, int](nil)
  1941  		for i := 0; i < n; i++ {
  1942  			m = m.Set(i, i+1)
  1943  		}
  1944  		for i := 0; i < n; i++ {
  1945  			if v, ok := m.Get(i); !ok || v != i+1 {
  1946  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1947  			}
  1948  		}
  1949  
  1950  		for i := 0; i < n; i++ {
  1951  			m = m.Delete(i)
  1952  		}
  1953  		for i := 0; i < n; i++ {
  1954  			if v, ok := m.Get(i); ok {
  1955  				t.Fatalf("expected no value for key=%v: <%v,%v>", i, v, ok)
  1956  			}
  1957  		}
  1958  	})
  1959  
  1960  	t.Run("Large", func(t *testing.T) {
  1961  		if testing.Short() {
  1962  			t.Skip("skipping: short")
  1963  		}
  1964  
  1965  		const n = 1000000
  1966  		m := NewSortedMap[int, int](nil)
  1967  		for i := 0; i < n; i++ {
  1968  			m = m.Set(i, i+1)
  1969  		}
  1970  		for i := 0; i < n; i++ {
  1971  			if v, ok := m.Get(i); !ok || v != i+1 {
  1972  				t.Fatalf("unexpected value for key=%v: <%v,%v>", i, v, ok)
  1973  			}
  1974  		}
  1975  
  1976  		for i := 0; i < n; i++ {
  1977  			m = m.Delete(i)
  1978  		}
  1979  		for i := 0; i < n; i++ {
  1980  			if v, ok := m.Get(i); ok {
  1981  				t.Fatalf("unexpected no value for key=%v: <%v,%v>", i, v, ok)
  1982  			}
  1983  		}
  1984  	})
  1985  
  1986  	RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
  1987  		m := NewTSortedMap()
  1988  		for j := 0; j < 10000; j++ {
  1989  			switch rand.Intn(8) {
  1990  			case 0: // overwrite
  1991  				m.Set(m.ExistingKey(rand), rand.Intn(10000))
  1992  			case 1: // delete existing key
  1993  				m.Delete(m.ExistingKey(rand))
  1994  			case 2: // delete non-existent key.
  1995  				m.Delete(m.NewKey(rand))
  1996  			default: // set new key
  1997  				m.Set(m.NewKey(rand), rand.Intn(10000))
  1998  			}
  1999  		}
  2000  		if err := m.Validate(); err != nil {
  2001  			t.Fatal(err)
  2002  		}
  2003  
  2004  		// Delete all keys.
  2005  		keys := make([]int, len(m.keys))
  2006  		copy(keys, m.keys)
  2007  		for _, k := range keys {
  2008  			m.Delete(k)
  2009  		}
  2010  		if err := m.Validate(); err != nil {
  2011  			t.Fatal(err)
  2012  		}
  2013  	})
  2014  }
  2015  
  2016  func TestSortedMap_Iterator(t *testing.T) {
  2017  	t.Run("Empty", func(t *testing.T) {
  2018  		t.Run("First", func(t *testing.T) {
  2019  			itr := NewSortedMap[int, int](nil).Iterator()
  2020  			itr.First()
  2021  			if k, v, ok := itr.Next(); ok {
  2022  				t.Fatalf("SortedMapIterator.Next()=<%v,%v>, expected nil", k, v)
  2023  			}
  2024  		})
  2025  
  2026  		t.Run("Last", func(t *testing.T) {
  2027  			itr := NewSortedMap[int, int](nil).Iterator()
  2028  			itr.Last()
  2029  			if k, v, ok := itr.Prev(); ok {
  2030  				t.Fatalf("SortedMapIterator.Prev()=<%v,%v>, expected nil", k, v)
  2031  			}
  2032  		})
  2033  
  2034  		t.Run("Seek", func(t *testing.T) {
  2035  			itr := NewSortedMap[string, int](nil).Iterator()
  2036  			itr.Seek("foo")
  2037  			if k, v, ok := itr.Next(); ok {
  2038  				t.Fatalf("SortedMapIterator.Next()=<%v,%v>, expected nil", k, v)
  2039  			}
  2040  		})
  2041  	})
  2042  
  2043  	t.Run("Seek", func(t *testing.T) {
  2044  		const n = 100
  2045  		m := NewSortedMap[string, int](nil)
  2046  		for i := 0; i < n; i += 2 {
  2047  			m = m.Set(fmt.Sprintf("%04d", i), i)
  2048  		}
  2049  
  2050  		t.Run("Exact", func(t *testing.T) {
  2051  			itr := m.Iterator()
  2052  			for i := 0; i < n; i += 2 {
  2053  				itr.Seek(fmt.Sprintf("%04d", i))
  2054  				for j := i; j < n; j += 2 {
  2055  					if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", j) {
  2056  						t.Fatalf("%d/%d. SortedMapIterator.Next()=%v, expected key %04d", i, j, k, j)
  2057  					}
  2058  				}
  2059  				if !itr.Done() {
  2060  					t.Fatalf("SortedMapIterator.Done()=true, expected false")
  2061  				}
  2062  			}
  2063  		})
  2064  
  2065  		t.Run("Miss", func(t *testing.T) {
  2066  			itr := m.Iterator()
  2067  			for i := 1; i < n-2; i += 2 {
  2068  				itr.Seek(fmt.Sprintf("%04d", i))
  2069  				for j := i + 1; j < n; j += 2 {
  2070  					if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", j) {
  2071  						t.Fatalf("%d/%d. SortedMapIterator.Next()=%v, expected key %04d", i, j, k, j)
  2072  					}
  2073  				}
  2074  				if !itr.Done() {
  2075  					t.Fatalf("SortedMapIterator.Done()=true, expected false")
  2076  				}
  2077  			}
  2078  		})
  2079  
  2080  		t.Run("BeforeFirst", func(t *testing.T) {
  2081  			itr := m.Iterator()
  2082  			itr.Seek("")
  2083  			for i := 0; i < n; i += 2 {
  2084  				if k, _, ok := itr.Next(); !ok || k != fmt.Sprintf("%04d", i) {
  2085  					t.Fatalf("%d. SortedMapIterator.Next()=%v, expected key %04d", i, k, i)
  2086  				}
  2087  			}
  2088  			if !itr.Done() {
  2089  				t.Fatalf("SortedMapIterator.Done()=true, expected false")
  2090  			}
  2091  		})
  2092  		t.Run("AfterLast", func(t *testing.T) {
  2093  			itr := m.Iterator()
  2094  			itr.Seek("1000")
  2095  			if k, _, ok := itr.Next(); ok {
  2096  				t.Fatalf("0. SortedMapIterator.Next()=%v, expected nil key", k)
  2097  			} else if !itr.Done() {
  2098  				t.Fatalf("SortedMapIterator.Done()=true, expected false")
  2099  			}
  2100  		})
  2101  	})
  2102  }
  2103  
  2104  func TestNewHasher(t *testing.T) {
  2105  	t.Run("builtin", func(t *testing.T) {
  2106  		t.Run("int", func(t *testing.T) { testNewHasher(t, int(100)) })
  2107  		t.Run("int8", func(t *testing.T) { testNewHasher(t, int8(100)) })
  2108  		t.Run("int16", func(t *testing.T) { testNewHasher(t, int16(100)) })
  2109  		t.Run("int32", func(t *testing.T) { testNewHasher(t, int32(100)) })
  2110  		t.Run("int64", func(t *testing.T) { testNewHasher(t, int64(100)) })
  2111  
  2112  		t.Run("uint", func(t *testing.T) { testNewHasher(t, uint(100)) })
  2113  		t.Run("uint8", func(t *testing.T) { testNewHasher(t, uint8(100)) })
  2114  		t.Run("uint16", func(t *testing.T) { testNewHasher(t, uint16(100)) })
  2115  		t.Run("uint32", func(t *testing.T) { testNewHasher(t, uint32(100)) })
  2116  		t.Run("uint64", func(t *testing.T) { testNewHasher(t, uint64(100)) })
  2117  
  2118  		t.Run("string", func(t *testing.T) { testNewHasher(t, "foo") })
  2119  		//t.Run("byteSlice", func(t *testing.T) { testNewHasher(t, []byte("foo")) })
  2120  	})
  2121  
  2122  	t.Run("reflection", func(t *testing.T) {
  2123  		type Int int
  2124  		t.Run("int", func(t *testing.T) { testNewHasher(t, Int(100)) })
  2125  
  2126  		type Uint uint
  2127  		t.Run("uint", func(t *testing.T) { testNewHasher(t, Uint(100)) })
  2128  
  2129  		type String string
  2130  		t.Run("string", func(t *testing.T) { testNewHasher(t, String("foo")) })
  2131  	})
  2132  }
  2133  
  2134  func testNewHasher[V constraints.Ordered](t *testing.T, v V) {
  2135  	t.Helper()
  2136  	h := NewHasher(v)
  2137  	h.Hash(v)
  2138  	if !h.Equal(v, v) {
  2139  		t.Fatal("expected hash equality")
  2140  	}
  2141  }
  2142  
  2143  func TestNewComparer(t *testing.T) {
  2144  	t.Run("builtin", func(t *testing.T) {
  2145  		t.Run("int", func(t *testing.T) { testNewComparer(t, int(100), int(101)) })
  2146  		t.Run("int8", func(t *testing.T) { testNewComparer(t, int8(100), int8(101)) })
  2147  		t.Run("int16", func(t *testing.T) { testNewComparer(t, int16(100), int16(101)) })
  2148  		t.Run("int32", func(t *testing.T) { testNewComparer(t, int32(100), int32(101)) })
  2149  		t.Run("int64", func(t *testing.T) { testNewComparer(t, int64(100), int64(101)) })
  2150  
  2151  		t.Run("uint", func(t *testing.T) { testNewComparer(t, uint(100), uint(101)) })
  2152  		t.Run("uint8", func(t *testing.T) { testNewComparer(t, uint8(100), uint8(101)) })
  2153  		t.Run("uint16", func(t *testing.T) { testNewComparer(t, uint16(100), uint16(101)) })
  2154  		t.Run("uint32", func(t *testing.T) { testNewComparer(t, uint32(100), uint32(101)) })
  2155  		t.Run("uint64", func(t *testing.T) { testNewComparer(t, uint64(100), uint64(101)) })
  2156  
  2157  		t.Run("string", func(t *testing.T) { testNewComparer(t, "bar", "foo") })
  2158  		//t.Run("byteSlice", func(t *testing.T) { testNewComparer(t, []byte("bar"), []byte("foo")) })
  2159  	})
  2160  
  2161  	t.Run("reflection", func(t *testing.T) {
  2162  		type Int int
  2163  		t.Run("int", func(t *testing.T) { testNewComparer(t, Int(100), Int(101)) })
  2164  
  2165  		type Uint uint
  2166  		t.Run("uint", func(t *testing.T) { testNewComparer(t, Uint(100), Uint(101)) })
  2167  
  2168  		type String string
  2169  		t.Run("string", func(t *testing.T) { testNewComparer(t, String("bar"), String("foo")) })
  2170  	})
  2171  }
  2172  
  2173  func testNewComparer[T constraints.Ordered](t *testing.T, x, y T) {
  2174  	t.Helper()
  2175  	c := NewComparer(x)
  2176  	if c.Compare(x, y) != -1 {
  2177  		t.Fatal("expected comparer LT")
  2178  	} else if c.Compare(x, x) != 0 {
  2179  		t.Fatal("expected comparer EQ")
  2180  	} else if c.Compare(y, x) != 1 {
  2181  		t.Fatal("expected comparer GT")
  2182  	}
  2183  }
  2184  
  2185  // TSortedMap represents a combined immutable and stdlib sorted map.
  2186  type TSortedMap struct {
  2187  	im, prev *SortedMap[int, int]
  2188  	builder  *SortedMapBuilder[int, int]
  2189  	std      map[int]int
  2190  	keys     []int
  2191  }
  2192  
  2193  func NewTSortedMap() *TSortedMap {
  2194  	return &TSortedMap{
  2195  		im:      NewSortedMap[int, int](nil),
  2196  		builder: NewSortedMapBuilder[int, int](nil),
  2197  		std:     make(map[int]int),
  2198  	}
  2199  }
  2200  
  2201  func (m *TSortedMap) NewKey(rand *rand.Rand) int {
  2202  	for {
  2203  		k := rand.Int()
  2204  		if _, ok := m.std[k]; !ok {
  2205  			return k
  2206  		}
  2207  	}
  2208  }
  2209  
  2210  func (m *TSortedMap) ExistingKey(rand *rand.Rand) int {
  2211  	if len(m.keys) == 0 {
  2212  		return 0
  2213  	}
  2214  	return m.keys[rand.Intn(len(m.keys))]
  2215  }
  2216  
  2217  func (m *TSortedMap) Set(k, v int) {
  2218  	m.prev = m.im
  2219  	m.im = m.im.Set(k, v)
  2220  	m.builder.Set(k, v)
  2221  
  2222  	if _, ok := m.std[k]; !ok {
  2223  		m.keys = append(m.keys, k)
  2224  		sort.Ints(m.keys)
  2225  	}
  2226  	m.std[k] = v
  2227  }
  2228  
  2229  func (m *TSortedMap) Delete(k int) {
  2230  	m.prev = m.im
  2231  	m.im = m.im.Delete(k)
  2232  	m.builder.Delete(k)
  2233  	delete(m.std, k)
  2234  
  2235  	for i := range m.keys {
  2236  		if m.keys[i] == k {
  2237  			m.keys = append(m.keys[:i], m.keys[i+1:]...)
  2238  			break
  2239  		}
  2240  	}
  2241  }
  2242  
  2243  func (m *TSortedMap) Validate() error {
  2244  	for _, k := range m.keys {
  2245  		if v, ok := m.im.Get(k); !ok {
  2246  			return fmt.Errorf("key not found: %d", k)
  2247  		} else if v != m.std[k] {
  2248  			return fmt.Errorf("key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
  2249  		}
  2250  		if v, ok := m.builder.Get(k); !ok {
  2251  			return fmt.Errorf("builder key not found: %d", k)
  2252  		} else if v != m.std[k] {
  2253  			return fmt.Errorf("builder key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
  2254  		}
  2255  	}
  2256  
  2257  	if got, exp := m.builder.Len(), len(m.std); got != exp {
  2258  		return fmt.Errorf("SortedMapBuilder.Len()=%d, expected %d", got, exp)
  2259  	}
  2260  
  2261  	sort.Ints(m.keys)
  2262  	if err := m.validateForwardIterator(m.im.Iterator()); err != nil {
  2263  		return fmt.Errorf("basic: %s", err)
  2264  	} else if err := m.validateBackwardIterator(m.im.Iterator()); err != nil {
  2265  		return fmt.Errorf("basic: %s", err)
  2266  	}
  2267  
  2268  	if err := m.validateForwardIterator(m.builder.Iterator()); err != nil {
  2269  		return fmt.Errorf("basic: %s", err)
  2270  	} else if err := m.validateBackwardIterator(m.builder.Iterator()); err != nil {
  2271  		return fmt.Errorf("basic: %s", err)
  2272  	}
  2273  	return nil
  2274  }
  2275  
  2276  func (m *TSortedMap) validateForwardIterator(itr *SortedMapIterator[int, int]) error {
  2277  	for i, k0 := range m.keys {
  2278  		v0 := m.std[k0]
  2279  		if k1, v1, ok := itr.Next(); !ok || k0 != k1 || v0 != v1 {
  2280  			return fmt.Errorf("%d. SortedMapIterator.Next()=<%v,%v>, expected <%v,%v>", i, k1, v1, k0, v0)
  2281  		}
  2282  
  2283  		done := i == len(m.keys)-1
  2284  		if v := itr.Done(); v != done {
  2285  			return fmt.Errorf("%d. SortedMapIterator.Done()=%v, expected %v", i, v, done)
  2286  		}
  2287  	}
  2288  	if k, v, ok := itr.Next(); ok {
  2289  		return fmt.Errorf("SortedMapIterator.Next()=<%v,%v>, expected nil after done", k, v)
  2290  	}
  2291  	return nil
  2292  }
  2293  
  2294  func (m *TSortedMap) validateBackwardIterator(itr *SortedMapIterator[int, int]) error {
  2295  	itr.Last()
  2296  	for i := len(m.keys) - 1; i >= 0; i-- {
  2297  		k0 := m.keys[i]
  2298  		v0 := m.std[k0]
  2299  		if k1, v1, ok := itr.Prev(); !ok || k0 != k1 || v0 != v1 {
  2300  			return fmt.Errorf("%d. SortedMapIterator.Prev()=<%v,%v>, expected <%v,%v>", i, k1, v1, k0, v0)
  2301  		}
  2302  
  2303  		done := i == 0
  2304  		if v := itr.Done(); v != done {
  2305  			return fmt.Errorf("%d. SortedMapIterator.Done()=%v, expected %v", i, v, done)
  2306  		}
  2307  	}
  2308  	if k, v, ok := itr.Prev(); ok {
  2309  		return fmt.Errorf("SortedMapIterator.Prev()=<%v,%v>, expected nil after done", k, v)
  2310  	}
  2311  	return nil
  2312  }
  2313  
  2314  func BenchmarkSortedMap_Set(b *testing.B) {
  2315  	b.ReportAllocs()
  2316  	m := NewSortedMap[int, int](nil)
  2317  	for i := 0; i < b.N; i++ {
  2318  		m = m.Set(i, i)
  2319  	}
  2320  }
  2321  
  2322  func BenchmarkSortedMap_Delete(b *testing.B) {
  2323  	const n = 10000
  2324  
  2325  	m := NewSortedMap[int, int](nil)
  2326  	for i := 0; i < n; i++ {
  2327  		m = m.Set(i, i)
  2328  	}
  2329  	b.ReportAllocs()
  2330  	b.ResetTimer()
  2331  
  2332  	for i := 0; i < b.N; i++ {
  2333  		m.Delete(i % n) // Do not update map, always operate on original
  2334  	}
  2335  }
  2336  
  2337  func BenchmarkSortedMap_Iterator(b *testing.B) {
  2338  	const n = 10000
  2339  	m := NewSortedMap[int, int](nil)
  2340  	for i := 0; i < 10000; i++ {
  2341  		m = m.Set(i, i)
  2342  	}
  2343  	b.ReportAllocs()
  2344  	b.ResetTimer()
  2345  
  2346  	b.Run("Forward", func(b *testing.B) {
  2347  		itr := m.Iterator()
  2348  		for i := 0; i < b.N; i++ {
  2349  			if i%n == 0 {
  2350  				itr.First()
  2351  			}
  2352  			itr.Next()
  2353  		}
  2354  	})
  2355  
  2356  	b.Run("Reverse", func(b *testing.B) {
  2357  		itr := m.Iterator()
  2358  		for i := 0; i < b.N; i++ {
  2359  			if i%n == 0 {
  2360  				itr.Last()
  2361  			}
  2362  			itr.Prev()
  2363  		}
  2364  	})
  2365  }
  2366  
  2367  func BenchmarkSortedMapBuilder_Set(b *testing.B) {
  2368  	b.ReportAllocs()
  2369  	builder := NewSortedMapBuilder[int, int](nil)
  2370  	for i := 0; i < b.N; i++ {
  2371  		builder.Set(i, i)
  2372  	}
  2373  }
  2374  
  2375  func BenchmarkSortedMapBuilder_Delete(b *testing.B) {
  2376  	const n = 1000000
  2377  
  2378  	builder := NewSortedMapBuilder[int, int](nil)
  2379  	for i := 0; i < n; i++ {
  2380  		builder.Set(i, i)
  2381  	}
  2382  	b.ReportAllocs()
  2383  	b.ResetTimer()
  2384  
  2385  	for i := 0; i < b.N; i++ {
  2386  		builder.Delete(i % n)
  2387  	}
  2388  }
  2389  
  2390  func ExampleSortedMap_Set() {
  2391  	m := NewSortedMap[string, any](nil)
  2392  	m = m.Set("foo", "bar")
  2393  	m = m.Set("baz", 100)
  2394  
  2395  	v, ok := m.Get("foo")
  2396  	fmt.Println("foo", v, ok)
  2397  
  2398  	v, ok = m.Get("baz")
  2399  	fmt.Println("baz", v, ok)
  2400  
  2401  	v, ok = m.Get("bat") // does not exist
  2402  	fmt.Println("bat", v, ok)
  2403  	// Output:
  2404  	// foo bar true
  2405  	// baz 100 true
  2406  	// bat <nil> false
  2407  }
  2408  
  2409  func ExampleSortedMap_Delete() {
  2410  	m := NewSortedMap[string, any](nil)
  2411  	m = m.Set("foo", "bar")
  2412  	m = m.Set("baz", 100)
  2413  	m = m.Delete("baz")
  2414  
  2415  	v, ok := m.Get("foo")
  2416  	fmt.Println("foo", v, ok)
  2417  
  2418  	v, ok = m.Get("baz")
  2419  	fmt.Println("baz", v, ok)
  2420  	// Output:
  2421  	// foo bar true
  2422  	// baz <nil> false
  2423  }
  2424  
  2425  func ExampleSortedMap_Iterator() {
  2426  	m := NewSortedMap[string, any](nil)
  2427  	m = m.Set("strawberry", 900)
  2428  	m = m.Set("kiwi", 300)
  2429  	m = m.Set("apple", 100)
  2430  	m = m.Set("pear", 700)
  2431  	m = m.Set("pineapple", 800)
  2432  	m = m.Set("peach", 600)
  2433  	m = m.Set("orange", 500)
  2434  	m = m.Set("grape", 200)
  2435  	m = m.Set("mango", 400)
  2436  
  2437  	itr := m.Iterator()
  2438  	for !itr.Done() {
  2439  		k, v, _ := itr.Next()
  2440  		fmt.Println(k, v)
  2441  	}
  2442  	// Output:
  2443  	// apple 100
  2444  	// grape 200
  2445  	// kiwi 300
  2446  	// mango 400
  2447  	// orange 500
  2448  	// peach 600
  2449  	// pear 700
  2450  	// pineapple 800
  2451  	// strawberry 900
  2452  }
  2453  
  2454  func ExampleSortedMapBuilder_Set() {
  2455  	b := NewSortedMapBuilder[string, any](nil)
  2456  	b.Set("foo", "bar")
  2457  	b.Set("baz", 100)
  2458  
  2459  	m := b.Map()
  2460  	v, ok := m.Get("foo")
  2461  	fmt.Println("foo", v, ok)
  2462  
  2463  	v, ok = m.Get("baz")
  2464  	fmt.Println("baz", v, ok)
  2465  
  2466  	v, ok = m.Get("bat") // does not exist
  2467  	fmt.Println("bat", v, ok)
  2468  	// Output:
  2469  	// foo bar true
  2470  	// baz 100 true
  2471  	// bat <nil> false
  2472  }
  2473  
  2474  func ExampleSortedMapBuilder_Delete() {
  2475  	b := NewSortedMapBuilder[string, any](nil)
  2476  	b.Set("foo", "bar")
  2477  	b.Set("baz", 100)
  2478  	b.Delete("baz")
  2479  
  2480  	m := b.Map()
  2481  	v, ok := m.Get("foo")
  2482  	fmt.Println("foo", v, ok)
  2483  
  2484  	v, ok = m.Get("baz")
  2485  	fmt.Println("baz", v, ok)
  2486  	// Output:
  2487  	// foo bar true
  2488  	// baz <nil> false
  2489  }
  2490  
  2491  // RunRandom executes fn multiple times with a different rand.
  2492  func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand)) {
  2493  	if testing.Short() {
  2494  		t.Skip("short mode")
  2495  	}
  2496  	t.Run(name, func(t *testing.T) {
  2497  		for i := 0; i < *randomN; i++ {
  2498  			i := i
  2499  			t.Run(fmt.Sprintf("%08d", i), func(t *testing.T) {
  2500  				t.Parallel()
  2501  				fn(t, rand.New(rand.NewSource(int64(i))))
  2502  			})
  2503  		}
  2504  	})
  2505  }
  2506  
  2507  func uniqueIntSlice(a []int) []int {
  2508  	m := make(map[int]struct{})
  2509  	other := make([]int, 0, len(a))
  2510  	for _, v := range a {
  2511  		if _, ok := m[v]; ok {
  2512  			continue
  2513  		}
  2514  		m[v] = struct{}{}
  2515  		other = append(other, v)
  2516  	}
  2517  	return other
  2518  }
  2519  
  2520  // mockHasher represents a mock implementation of immutable.Hasher.
  2521  type mockHasher[K constraints.Ordered] struct {
  2522  	hash  func(value K) uint32
  2523  	equal func(a, b K) bool
  2524  }
  2525  
  2526  // Hash executes the mocked HashFn function.
  2527  func (h *mockHasher[K]) Hash(value K) uint32 {
  2528  	return h.hash(value)
  2529  }
  2530  
  2531  // Equal executes the mocked EqualFn function.
  2532  func (h *mockHasher[K]) Equal(a, b K) bool {
  2533  	return h.equal(a, b)
  2534  }
  2535  
  2536  // mockComparer represents a mock implementation of immutable.Comparer.
  2537  type mockComparer[K constraints.Ordered] struct {
  2538  	compare func(a, b K) int
  2539  }
  2540  
  2541  // Compare executes the mocked CompreFn function.
  2542  func (h *mockComparer[K]) Compare(a, b K) int {
  2543  	return h.compare(a, b)
  2544  }
  2545  

View as plain text