aboutsummaryrefslogtreecommitdiff
path: root/tests/pds.go
diff options
context:
space:
mode:
Diffstat (limited to 'tests/pds.go')
-rw-r--r--tests/pds.go827
1 files changed, 107 insertions, 720 deletions
diff --git a/tests/pds.go b/tests/pds.go
index ad74531..b1df034 100644
--- a/tests/pds.go
+++ b/tests/pds.go
@@ -5,8 +5,10 @@ import (
"flag"
"fmt"
"math/rand"
+ "os"
"sort"
"testing"
+ "testing/internal/testdeps"
)
var (
@@ -43,7 +45,8 @@ func TestList(t *testing.T) {
t.Run("Deep", func(t *testing.T) {
list := NewList[int]()
var array []int
- for i := 0; i < 100000; i++ {
+ const n = 1000 // FIXME: 100000 was too slow
+ for i := 0; i < n; i++ {
list = list.Append(i)
array = append(array, i)
}
@@ -236,8 +239,9 @@ func TestList(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- l := NewTList()
- for i := 0; i < 100000; i++ {
+ const n = 100 // FIXME: 100000 was too slow
+ l := newTList()
+ for i := 0; i < n; i++ {
rnd := rand.Intn(70)
switch {
case rnd == 0: // slice
@@ -260,27 +264,27 @@ func TestList(t *testing.T) {
}
// TList represents a list that operates on a standard Go slice & immutable list.
-type TList struct {
+type tList struct {
im, prev *List[int]
builder *ListBuilder[int]
std []int
}
-// NewTList returns a new instance of TList.
-func NewTList() *TList {
- return &TList{
+// newTList returns a new instance of tList.
+func newTList() *tList {
+ return &tList{
im: NewList[int](),
builder: NewListBuilder[int](),
}
}
// Len returns the size of the list.
-func (l *TList) Len() int {
+func (l *tList) Len() int {
return len(l.std)
}
// ChooseIndex returns a randomly chosen, valid index from the standard slice.
-func (l *TList) ChooseIndex(rand *rand.Rand) int {
+func (l *tList) ChooseIndex(rand *rand.Rand) int {
if len(l.std) == 0 {
return -1
}
@@ -288,7 +292,7 @@ func (l *TList) ChooseIndex(rand *rand.Rand) int {
}
// ChooseSliceIndices returns randomly chosen, valid indices for slicing.
-func (l *TList) ChooseSliceIndices(rand *rand.Rand) (start, end int) {
+func (l *tList) ChooseSliceIndices(rand *rand.Rand) (start, end int) {
if len(l.std) == 0 {
return 0, 0
}
@@ -298,7 +302,7 @@ func (l *TList) ChooseSliceIndices(rand *rand.Rand) (start, end int) {
}
// Append adds v to the end of slice and List.
-func (l *TList) Append(v int) {
+func (l *tList) Append(v int) {
l.prev = l.im
l.im = l.im.Append(v)
l.builder.Append(v)
@@ -306,7 +310,7 @@ func (l *TList) Append(v int) {
}
// Prepend adds v to the beginning of the slice and List.
-func (l *TList) Prepend(v int) {
+func (l *tList) Prepend(v int) {
l.prev = l.im
l.im = l.im.Prepend(v)
l.builder.Prepend(v)
@@ -314,7 +318,7 @@ func (l *TList) Prepend(v int) {
}
// Set updates the value at index i to v in the slice and List.
-func (l *TList) Set(i, v int) {
+func (l *tList) Set(i, v int) {
l.prev = l.im
l.im = l.im.Set(i, v)
l.builder.Set(i, v)
@@ -322,7 +326,7 @@ func (l *TList) Set(i, v int) {
}
// Slice contracts the slice and List to the range of start/end indices.
-func (l *TList) Slice(start, end int) {
+func (l *tList) Slice(start, end int) {
l.prev = l.im
l.im = l.im.Slice(start, end)
l.builder.Slice(start, end)
@@ -330,7 +334,7 @@ func (l *TList) Slice(start, end int) {
}
// Validate returns an error if the slice and List are different.
-func (l *TList) Validate() error {
+func (l *tList) Validate() error {
if got, exp := l.im.Len(), len(l.std); got != exp {
return fmt.Errorf("Len()=%v, expected %d", got, exp)
} else if got, exp := l.builder.Len(), len(l.std); got != exp {
@@ -359,7 +363,7 @@ func (l *TList) Validate() error {
return nil
}
-func (l *TList) validateForwardIterator(typ string, itr *ListIterator[int]) error {
+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)
@@ -376,7 +380,7 @@ func (l *TList) validateForwardIterator(typ string, itr *ListIterator[int]) erro
return nil
}
-func (l *TList) validateBackwardIterator(typ string, itr *ListIterator[int]) error {
+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 {
@@ -394,271 +398,9 @@ func (l *TList) validateBackwardIterator(typ string, itr *ListIterator[int]) err
return nil
}
-func BenchmarkList_Append(b *testing.B) {
- b.ReportAllocs()
- l := NewList[int]()
- for i := 0; i < b.N; i++ {
- l = l.Append(i)
- }
-}
-
-func BenchmarkList_Prepend(b *testing.B) {
- b.ReportAllocs()
- l := NewList[int]()
- for i := 0; i < b.N; i++ {
- l = l.Prepend(i)
- }
-}
-
-func BenchmarkList_Set(b *testing.B) {
- const n = 10000
-
- l := NewList[int]()
- for i := 0; i < 10000; i++ {
- l = l.Append(i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- l = l.Set(i%n, i*10)
- }
-}
-
-func BenchmarkList_Iterator(b *testing.B) {
- const n = 10000
- l := NewList[int]()
- for i := 0; i < 10000; i++ {
- l = l.Append(i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- b.Run("Forward", func(b *testing.B) {
- itr := l.Iterator()
- for i := 0; i < b.N; i++ {
- if i%n == 0 {
- itr.First()
- }
- itr.Next()
- }
- })
-
- b.Run("Reverse", func(b *testing.B) {
- itr := l.Iterator()
- for i := 0; i < b.N; i++ {
- if i%n == 0 {
- itr.Last()
- }
- itr.Prev()
- }
- })
-}
-
-func BenchmarkBuiltinSlice_Append(b *testing.B) {
- b.Run("Int", func(b *testing.B) {
- b.ReportAllocs()
- var a []int
- for i := 0; i < b.N; i++ {
- a = append(a, i)
- }
- })
- b.Run("Interface", func(b *testing.B) {
- b.ReportAllocs()
- var a []interface{}
- for i := 0; i < b.N; i++ {
- a = append(a, i)
- }
- })
-}
-
-func BenchmarkListBuilder_Append(b *testing.B) {
- b.ReportAllocs()
- builder := NewListBuilder[int]()
- for i := 0; i < b.N; i++ {
- builder.Append(i)
- }
-}
-
-func BenchmarkListBuilder_Prepend(b *testing.B) {
- b.ReportAllocs()
- builder := NewListBuilder[int]()
- for i := 0; i < b.N; i++ {
- builder.Prepend(i)
- }
-}
-
-func BenchmarkListBuilder_Set(b *testing.B) {
- const n = 10000
-
- builder := NewListBuilder[int]()
- for i := 0; i < 10000; i++ {
- builder.Append(i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- builder.Set(i%n, i*10)
- }
-}
-
-func ExampleList_Append() {
- l := NewList[string]()
- l = l.Append("foo")
- l = l.Append("bar")
- l = l.Append("baz")
-
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- fmt.Println(l.Get(2))
- // Output:
- // foo
- // bar
- // baz
-}
-
-func ExampleList_Prepend() {
- l := NewList[string]()
- l = l.Prepend("foo")
- l = l.Prepend("bar")
- l = l.Prepend("baz")
-
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- fmt.Println(l.Get(2))
- // Output:
- // baz
- // bar
- // foo
-}
-
-func ExampleList_Set() {
- l := NewList[string]()
- l = l.Append("foo")
- l = l.Append("bar")
- l = l.Set(1, "baz")
-
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- // Output:
- // foo
- // baz
-}
-
-func ExampleList_Slice() {
- l := NewList[string]()
- l = l.Append("foo")
- l = l.Append("bar")
- l = l.Append("baz")
- l = l.Slice(1, 3)
-
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- // Output:
- // bar
- // baz
-}
-
-func ExampleList_Iterator() {
- l := NewList[string]()
- l = l.Append("foo")
- l = l.Append("bar")
- l = l.Append("baz")
-
- itr := l.Iterator()
- for !itr.Done() {
- i, v := itr.Next()
- fmt.Println(i, v)
- }
- // Output:
- // 0 foo
- // 1 bar
- // 2 baz
-}
-
-func ExampleList_Iterator_reverse() {
- l := NewList[string]()
- l = l.Append("foo")
- l = l.Append("bar")
- l = l.Append("baz")
-
- itr := l.Iterator()
- itr.Last()
- for !itr.Done() {
- i, v := itr.Prev()
- fmt.Println(i, v)
- }
- // Output:
- // 2 baz
- // 1 bar
- // 0 foo
-}
-
-func ExampleListBuilder_Append() {
- b := NewListBuilder[string]()
- b.Append("foo")
- b.Append("bar")
- b.Append("baz")
-
- l := b.List()
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- fmt.Println(l.Get(2))
- // Output:
- // foo
- // bar
- // baz
-}
-
-func ExampleListBuilder_Prepend() {
- b := NewListBuilder[string]()
- b.Prepend("foo")
- b.Prepend("bar")
- b.Prepend("baz")
-
- l := b.List()
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- fmt.Println(l.Get(2))
- // Output:
- // baz
- // bar
- // foo
-}
-
-func ExampleListBuilder_Set() {
- b := NewListBuilder[string]()
- b.Append("foo")
- b.Append("bar")
- b.Set(1, "baz")
-
- l := b.List()
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- // Output:
- // foo
- // baz
-}
-
-func ExampleListBuilder_Slice() {
- b := NewListBuilder[string]()
- b.Append("foo")
- b.Append("bar")
- b.Append("baz")
- b.Slice(1, 3)
-
- l := b.List()
- fmt.Println(l.Get(0))
- fmt.Println(l.Get(1))
- // Output:
- // bar
- // baz
-}
-
// Ensure node can support overwrites as it expands.
func TestInternal_mapNode_Overwrite(t *testing.T) {
- const n = 1000
+ const n = 100 // FIXME: 1000 was too slow
var h defaultHasher[int]
var node mapNode[int, int] = &mapArrayNode[int, int]{}
for i := 0; i < n; i++ {
@@ -1014,7 +756,7 @@ func TestMap_Set(t *testing.T) {
})
t.Run("Small", func(t *testing.T) {
- const n = 1000
+ const n = 100
m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1027,11 +769,7 @@ func TestMap_Set(t *testing.T) {
})
t.Run("Large", func(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping: short")
- }
-
- const n = 1000000
+ const n = 1000 // FIXME: 1000000 was too slow
m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1061,8 +799,9 @@ func TestMap_Set(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTestMap()
- for i := 0; i < 10000; i++ {
+ const n = 100 // FIXME: 10000 was too slow
+ m := newTMap()
+ for i := 0; i < n; i++ {
switch rand.Intn(2) {
case 1: // overwrite
m.Set(m.ExistingKey(rand), rand.Intn(10000))
@@ -1078,11 +817,7 @@ 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
+ const n = 100 // FIXME: 10000 was too slow
m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
// Set original value.
@@ -1130,7 +865,7 @@ func TestMap_Delete(t *testing.T) {
})
t.Run("Small", func(t *testing.T) {
- const n = 1000
+ const n = 100
m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1144,10 +879,7 @@ func TestMap_Delete(t *testing.T) {
})
t.Run("Large", func(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping: short")
- }
- const n = 1000000
+ const n = 1000 // FIXME: 1000000 was too slow
m := NewMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1161,8 +893,9 @@ func TestMap_Delete(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTestMap()
- for i := 0; i < 10000; i++ {
+ const n = 100 // FIXME: 10000 was too slow
+ m := newTMap()
+ for i := 0; i < n; i++ {
switch rand.Intn(8) {
case 0: // overwrite
m.Set(m.ExistingKey(rand), rand.Intn(10000))
@@ -1190,10 +923,6 @@ 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[int]{
hash: func(value int) uint32 { return hashUint64(uint64(value)) % 0xFF },
@@ -1201,8 +930,9 @@ func TestMap_LimitedHash(t *testing.T) {
}
m := NewMap[int, int](&h)
+ const n = 1000 // FIXME: 100000 was too slow
rand := rand.New(rand.NewSource(0))
- keys := rand.Perm(100000)
+ keys := rand.Perm(n)
for _, i := range keys {
m = m.Set(i, i) // initial set
}
@@ -1254,8 +984,9 @@ func TestMap_LimitedHash(t *testing.T) {
}
b := NewMapBuilder[int, int](&h)
+ const n = 10000 // FIXME: 100000 was too slow
rand := rand.New(rand.NewSource(0))
- keys := rand.Perm(100000)
+ keys := rand.Perm(n)
for _, i := range keys {
b.Set(i, i) // initial set
}
@@ -1296,23 +1027,23 @@ func TestMap_LimitedHash(t *testing.T) {
})
}
-// TMap represents a combined immutable and stdlib map.
-type TMap struct {
+// tMap represents a combined immutable and stdlib map.
+type tMap struct {
im, prev *Map[int, int]
builder *MapBuilder[int, int]
std map[int]int
keys []int
}
-func NewTestMap() *TMap {
- return &TMap{
+func newTMap() *tMap {
+ return &tMap{
im: NewMap[int, int](nil),
builder: NewMapBuilder[int, int](nil),
std: make(map[int]int),
}
}
-func (m *TMap) NewKey(rand *rand.Rand) int {
+func (m *tMap) NewKey(rand *rand.Rand) int {
for {
k := rand.Int()
if _, ok := m.std[k]; !ok {
@@ -1321,14 +1052,14 @@ func (m *TMap) NewKey(rand *rand.Rand) int {
}
}
-func (m *TMap) ExistingKey(rand *rand.Rand) int {
+func (m *tMap) ExistingKey(rand *rand.Rand) int {
if len(m.keys) == 0 {
return 0
}
return m.keys[rand.Intn(len(m.keys))]
}
-func (m *TMap) Set(k, v int) {
+func (m *tMap) Set(k, v int) {
m.prev = m.im
m.im = m.im.Set(k, v)
m.builder.Set(k, v)
@@ -1340,7 +1071,7 @@ func (m *TMap) Set(k, v int) {
m.std[k] = v
}
-func (m *TMap) Delete(k int) {
+func (m *tMap) Delete(k int) {
m.prev = m.im
m.im = m.im.Delete(k)
m.builder.Delete(k)
@@ -1354,7 +1085,7 @@ func (m *TMap) Delete(k int) {
}
}
-func (m *TMap) Validate() error {
+func (m *tMap) Validate() error {
for _, k := range m.keys {
if v, ok := m.im.Get(k); !ok {
return fmt.Errorf("key not found: %d", k)
@@ -1375,7 +1106,7 @@ func (m *TMap) Validate() error {
return nil
}
-func (m *TMap) validateIterator(itr *MapIterator[int, int]) error {
+func (m *tMap) validateIterator(itr *MapIterator[int, int]) error {
other := make(map[int]int)
for !itr.Done() {
k, v, _ := itr.Next()
@@ -1395,197 +1126,6 @@ func (m *TMap) validateIterator(itr *MapIterator[int, int]) error {
return nil
}
-func BenchmarkBuiltinMap_Set(b *testing.B) {
- b.ReportAllocs()
- m := make(map[int]int)
- for i := 0; i < b.N; i++ {
- m[i] = i
- }
-}
-
-func BenchmarkBuiltinMap_Delete(b *testing.B) {
- const n = 10000000
-
- m := make(map[int]int)
- for i := 0; i < n; i++ {
- m[i] = i
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- delete(m, i%n)
- }
-}
-
-func BenchmarkMap_Set(b *testing.B) {
- b.ReportAllocs()
- m := NewMap[int, int](nil)
- for i := 0; i < b.N; i++ {
- m = m.Set(i, i)
- }
-}
-
-func BenchmarkMap_Delete(b *testing.B) {
- const n = 10000000
-
- builder := NewMapBuilder[int, int](nil)
- for i := 0; i < n; i++ {
- builder.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- m := builder.Map()
- for i := 0; i < b.N; i++ {
- m.Delete(i % n) // Do not update map, always operate on original
- }
-}
-
-func BenchmarkMap_Iterator(b *testing.B) {
- const n = 10000
- m := NewMap[int, int](nil)
- for i := 0; i < 10000; i++ {
- m = m.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- b.Run("Forward", func(b *testing.B) {
- itr := m.Iterator()
- for i := 0; i < b.N; i++ {
- if i%n == 0 {
- itr.First()
- }
- itr.Next()
- }
- })
-}
-
-func BenchmarkMapBuilder_Set(b *testing.B) {
- b.ReportAllocs()
- builder := NewMapBuilder[int, int](nil)
- for i := 0; i < b.N; i++ {
- builder.Set(i, i)
- }
-}
-
-func BenchmarkMapBuilder_Delete(b *testing.B) {
- const n = 10000000
-
- builder := NewMapBuilder[int, int](nil)
- for i := 0; i < n; i++ {
- builder.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- builder.Delete(i % n)
- }
-}
-
-func ExampleMap_Set() {
- m := NewMap[string, any](nil)
- m = m.Set("foo", "bar")
- m = m.Set("baz", 100)
-
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
-
- v, ok = m.Get("bat") // does not exist
- fmt.Println("bat", v, ok)
- // Output:
- // foo bar true
- // baz 100 true
- // bat <nil> false
-}
-
-func ExampleMap_Delete() {
- m := NewMap[string, any](nil)
- m = m.Set("foo", "bar")
- m = m.Set("baz", 100)
- m = m.Delete("baz")
-
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
- // Output:
- // foo bar true
- // baz <nil> false
-}
-
-func ExampleMap_Iterator() {
- m := NewMap[string, int](nil)
- m = m.Set("apple", 100)
- m = m.Set("grape", 200)
- m = m.Set("kiwi", 300)
- m = m.Set("mango", 400)
- m = m.Set("orange", 500)
- m = m.Set("peach", 600)
- m = m.Set("pear", 700)
- m = m.Set("pineapple", 800)
- m = m.Set("strawberry", 900)
-
- itr := m.Iterator()
- for !itr.Done() {
- k, v, _ := itr.Next()
- fmt.Println(k, v)
- }
- // Output:
- // mango 400
- // pear 700
- // pineapple 800
- // grape 200
- // orange 500
- // strawberry 900
- // kiwi 300
- // peach 600
- // apple 100
-}
-
-func ExampleMapBuilder_Set() {
- b := NewMapBuilder[string, any](nil)
- b.Set("foo", "bar")
- b.Set("baz", 100)
-
- m := b.Map()
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
-
- v, ok = m.Get("bat") // does not exist
- fmt.Println("bat", v, ok)
- // Output:
- // foo bar true
- // baz 100 true
- // bat <nil> false
-}
-
-func ExampleMapBuilder_Delete() {
- b := NewMapBuilder[string, any](nil)
- b.Set("foo", "bar")
- b.Set("baz", 100)
- b.Delete("baz")
-
- m := b.Map()
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
- // Output:
- // foo bar true
- // baz <nil> false
-}
-
func TestInternalSortedMapLeafNode(t *testing.T) {
RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
var cmpr defaultComparer[int]
@@ -1689,7 +1229,8 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
func TestInternalSortedMapBranchNode(t *testing.T) {
RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
- keys := make([]int, 32*16)
+ const n = 16*16 // FIXME: 32*16 was too slow
+ keys := make([]int, n)
for i := range keys {
keys[i] = rand.Intn(10000)
}
@@ -1817,7 +1358,7 @@ func TestSortedMap_Set(t *testing.T) {
})
t.Run("Small", func(t *testing.T) {
- const n = 1000
+ const n = 100
m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1830,11 +1371,7 @@ func TestSortedMap_Set(t *testing.T) {
})
t.Run("Large", func(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping: short")
- }
-
- const n = 1000000
+ const n = 1000 // FIXME: 1000000 was too slow
m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1876,8 +1413,9 @@ func TestSortedMap_Set(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTSortedMap()
- for j := 0; j < 10000; j++ {
+ const n = 100 // FIXME: 10000 was too slow
+ m := newTSortedMap()
+ for j := 0; j < n; j++ {
switch rand.Intn(2) {
case 1: // overwrite
m.Set(m.ExistingKey(rand), rand.Intn(10000))
@@ -1893,7 +1431,7 @@ func TestSortedMap_Set(t *testing.T) {
// Ensure map can support overwrites as it expands.
func TestSortedMap_Overwrite(t *testing.T) {
- const n = 1000
+ const n = 100 // FIXME: 1000 was too slow
m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
// Set original value.
@@ -1935,7 +1473,7 @@ func TestSortedMap_Delete(t *testing.T) {
})
t.Run("Small", func(t *testing.T) {
- const n = 1000
+ const n = 100
m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1957,11 +1495,7 @@ func TestSortedMap_Delete(t *testing.T) {
})
t.Run("Large", func(t *testing.T) {
- if testing.Short() {
- t.Skip("skipping: short")
- }
-
- const n = 1000000
+ const n = 1000 // FIXME: 1000000 was too slow
m := NewSortedMap[int, int](nil)
for i := 0; i < n; i++ {
m = m.Set(i, i+1)
@@ -1983,8 +1517,9 @@ func TestSortedMap_Delete(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTSortedMap()
- for j := 0; j < 10000; j++ {
+ const n = 100 // FIXME: 10000 was too slow
+ m := newTSortedMap()
+ for j := 0; j < n; j++ {
switch rand.Intn(8) {
case 0: // overwrite
m.Set(m.ExistingKey(rand), rand.Intn(10000))
@@ -2181,23 +1716,23 @@ func testNewComparer[T cmp.Ordered](t *testing.T, x, y T) {
}
}
-// TSortedMap represents a combined immutable and stdlib sorted map.
-type TSortedMap struct {
+// tSortedMap represents a combined immutable and stdlib sorted map.
+type tSortedMap struct {
im, prev *SortedMap[int, int]
builder *SortedMapBuilder[int, int]
std map[int]int
keys []int
}
-func NewTSortedMap() *TSortedMap {
- return &TSortedMap{
+func newTSortedMap() *tSortedMap {
+ return &tSortedMap{
im: NewSortedMap[int, int](nil),
builder: NewSortedMapBuilder[int, int](nil),
std: make(map[int]int),
}
}
-func (m *TSortedMap) NewKey(rand *rand.Rand) int {
+func (m *tSortedMap) NewKey(rand *rand.Rand) int {
for {
k := rand.Int()
if _, ok := m.std[k]; !ok {
@@ -2206,14 +1741,14 @@ func (m *TSortedMap) NewKey(rand *rand.Rand) int {
}
}
-func (m *TSortedMap) ExistingKey(rand *rand.Rand) int {
+func (m *tSortedMap) ExistingKey(rand *rand.Rand) int {
if len(m.keys) == 0 {
return 0
}
return m.keys[rand.Intn(len(m.keys))]
}
-func (m *TSortedMap) Set(k, v int) {
+func (m *tSortedMap) Set(k, v int) {
m.prev = m.im
m.im = m.im.Set(k, v)
m.builder.Set(k, v)
@@ -2225,7 +1760,7 @@ func (m *TSortedMap) Set(k, v int) {
m.std[k] = v
}
-func (m *TSortedMap) Delete(k int) {
+func (m *tSortedMap) Delete(k int) {
m.prev = m.im
m.im = m.im.Delete(k)
m.builder.Delete(k)
@@ -2239,7 +1774,7 @@ func (m *TSortedMap) Delete(k int) {
}
}
-func (m *TSortedMap) Validate() error {
+func (m *tSortedMap) Validate() error {
for _, k := range m.keys {
if v, ok := m.im.Get(k); !ok {
return fmt.Errorf("key not found: %d", k)
@@ -2272,7 +1807,7 @@ func (m *TSortedMap) Validate() error {
return nil
}
-func (m *TSortedMap) validateForwardIterator(itr *SortedMapIterator[int, int]) error {
+func (m *tSortedMap) validateForwardIterator(itr *SortedMapIterator[int, int]) error {
for i, k0 := range m.keys {
v0 := m.std[k0]
if k1, v1, ok := itr.Next(); !ok || k0 != k1 || v0 != v1 {
@@ -2290,7 +1825,7 @@ func (m *TSortedMap) validateForwardIterator(itr *SortedMapIterator[int, int]) e
return nil
}
-func (m *TSortedMap) validateBackwardIterator(itr *SortedMapIterator[int, int]) error {
+func (m *tSortedMap) validateBackwardIterator(itr *SortedMapIterator[int, int]) error {
itr.Last()
for i := len(m.keys) - 1; i >= 0; i-- {
k0 := m.keys[i]
@@ -2310,188 +1845,8 @@ func (m *TSortedMap) validateBackwardIterator(itr *SortedMapIterator[int, int])
return nil
}
-func BenchmarkSortedMap_Set(b *testing.B) {
- b.ReportAllocs()
- m := NewSortedMap[int, int](nil)
- for i := 0; i < b.N; i++ {
- m = m.Set(i, i)
- }
-}
-
-func BenchmarkSortedMap_Delete(b *testing.B) {
- const n = 10000
-
- m := NewSortedMap[int, int](nil)
- for i := 0; i < n; i++ {
- m = m.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- m.Delete(i % n) // Do not update map, always operate on original
- }
-}
-
-func BenchmarkSortedMap_Iterator(b *testing.B) {
- const n = 10000
- m := NewSortedMap[int, int](nil)
- for i := 0; i < 10000; i++ {
- m = m.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- b.Run("Forward", func(b *testing.B) {
- itr := m.Iterator()
- for i := 0; i < b.N; i++ {
- if i%n == 0 {
- itr.First()
- }
- itr.Next()
- }
- })
-
- b.Run("Reverse", func(b *testing.B) {
- itr := m.Iterator()
- for i := 0; i < b.N; i++ {
- if i%n == 0 {
- itr.Last()
- }
- itr.Prev()
- }
- })
-}
-
-func BenchmarkSortedMapBuilder_Set(b *testing.B) {
- b.ReportAllocs()
- builder := NewSortedMapBuilder[int, int](nil)
- for i := 0; i < b.N; i++ {
- builder.Set(i, i)
- }
-}
-
-func BenchmarkSortedMapBuilder_Delete(b *testing.B) {
- const n = 1000000
-
- builder := NewSortedMapBuilder[int, int](nil)
- for i := 0; i < n; i++ {
- builder.Set(i, i)
- }
- b.ReportAllocs()
- b.ResetTimer()
-
- for i := 0; i < b.N; i++ {
- builder.Delete(i % n)
- }
-}
-
-func ExampleSortedMap_Set() {
- m := NewSortedMap[string, any](nil)
- m = m.Set("foo", "bar")
- m = m.Set("baz", 100)
-
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
-
- v, ok = m.Get("bat") // does not exist
- fmt.Println("bat", v, ok)
- // Output:
- // foo bar true
- // baz 100 true
- // bat <nil> false
-}
-
-func ExampleSortedMap_Delete() {
- m := NewSortedMap[string, any](nil)
- m = m.Set("foo", "bar")
- m = m.Set("baz", 100)
- m = m.Delete("baz")
-
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
- // Output:
- // foo bar true
- // baz <nil> false
-}
-
-func ExampleSortedMap_Iterator() {
- m := NewSortedMap[string, any](nil)
- m = m.Set("strawberry", 900)
- m = m.Set("kiwi", 300)
- m = m.Set("apple", 100)
- m = m.Set("pear", 700)
- m = m.Set("pineapple", 800)
- m = m.Set("peach", 600)
- m = m.Set("orange", 500)
- m = m.Set("grape", 200)
- m = m.Set("mango", 400)
-
- itr := m.Iterator()
- for !itr.Done() {
- k, v, _ := itr.Next()
- fmt.Println(k, v)
- }
- // Output:
- // apple 100
- // grape 200
- // kiwi 300
- // mango 400
- // orange 500
- // peach 600
- // pear 700
- // pineapple 800
- // strawberry 900
-}
-
-func ExampleSortedMapBuilder_Set() {
- b := NewSortedMapBuilder[string, any](nil)
- b.Set("foo", "bar")
- b.Set("baz", 100)
-
- m := b.Map()
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
-
- v, ok = m.Get("bat") // does not exist
- fmt.Println("bat", v, ok)
- // Output:
- // foo bar true
- // baz 100 true
- // bat <nil> false
-}
-
-func ExampleSortedMapBuilder_Delete() {
- b := NewSortedMapBuilder[string, any](nil)
- b.Set("foo", "bar")
- b.Set("baz", 100)
- b.Delete("baz")
-
- m := b.Map()
- v, ok := m.Get("foo")
- fmt.Println("foo", v, ok)
-
- v, ok = m.Get("baz")
- fmt.Println("baz", v, ok)
- // Output:
- // foo bar true
- // baz <nil> false
-}
-
// RunRandom executes fn multiple times with a different rand.
func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand)) {
- if testing.Short() {
- t.Skip("short mode")
- }
t.Run(name, func(t *testing.T) {
for i := 0; i < *randomN; i++ {
i := i
@@ -2561,8 +1916,8 @@ func TestSetsPut(t *testing.T) {
itr := s2.Iterator()
counter := 0
for !itr.Done() {
- i, v := itr.Next()
- t.Log(i, v)
+ itr.Next()
+ // t.Log(i, v)
counter++
}
if counter != 1 {
@@ -2607,8 +1962,8 @@ func TestSortedSetsPut(t *testing.T) {
itr := s2.Iterator()
counter := 0
for !itr.Done() {
- i, v := itr.Next()
- t.Log(i, v)
+ i, _ := itr.Next()
+ // t.Log(i, v)
if counter == 0 && i != "0" {
t.Fatalf("sort did not work for first el")
}
@@ -2666,4 +2021,36 @@ func TestSortedSetBuilder(t *testing.T) {
func MainTest() {
+ tests := []testing.InternalTest{
+ { "TestList", TestList },
+ { "TestInternal_mapNode_Overwrite", TestInternal_mapNode_Overwrite },
+ { "TestInternal_mapArrayNode", TestInternal_mapArrayNode },
+ { "TestInternal_mapValueNode", TestInternal_mapValueNode },
+ { "TestMap_Get", TestMap_Get },
+ { "TestMap_Set", TestMap_Set },
+ { "TestMap_Overwrite", TestMap_Overwrite },
+ { "TestMap_Delete", TestMap_Delete },
+ { "TestMap_LimitedHash", TestMap_LimitedHash },
+ { "TestInternalSortedMapLeafNode", TestInternalSortedMapLeafNode },
+ { "TestInternalSortedMapBranchNode", TestInternalSortedMapBranchNode },
+ { "TestSortedMap_Get", TestSortedMap_Get },
+ { "TestSortedMap_Set", TestSortedMap_Set },
+ { "TestSortedMap_Overwrite", TestSortedMap_Overwrite },
+ { "TestSortedMap_Delete", TestSortedMap_Delete },
+ { "TestSortedMap_Iterator", TestSortedMap_Iterator },
+ { "TestNewHasher", TestNewHasher },
+ { "TestNewComparer", TestNewComparer },
+ { "TestSetsPut", TestSetsPut },
+ { "TestSetsDelete", TestSetsDelete },
+ { "TestSortedSetsPut", TestSortedSetsPut },
+ { "TestSortedSetsDelete", TestSortedSetsDelete },
+ { "TestSortedSetBuilder", TestSortedSetBuilder },
+ }
+
+ deps := testdeps.TestDeps{}
+ benchmarks := []testing.InternalBenchmark {}
+ fuzzTargets := []testing.InternalFuzzTarget{}
+ examples := []testing.InternalExample {}
+ m := testing.MainStart(deps, tests, benchmarks, fuzzTargets, examples)
+ os.Exit(m.Run())
}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-21 17:58:09 +0000