From 8e1383ea6a9561610e00b8c7f401bca1257f9001 Mon Sep 17 00:00:00 2001 From: Oskar Haarklou Veileborg Date: Mon, 9 Jan 2023 20:28:08 +0100 Subject: Ensure immutability of sets (and maps with SetMany) --- README.md | 4 ++-- immutable.go | 10 ++++------ sets.go | 32 ++++++++++---------------------- sets_test.go | 1 + 4 files changed, 17 insertions(+), 30 deletions(-) diff --git a/README.md b/README.md index ed771c6..c547383 100644 --- a/README.md +++ b/README.md @@ -286,8 +286,8 @@ Please see the internal `defaultComparer` for an example, bearing in mind that i ## Set -The `Set` represents a collection of unique values. It uses a `map[T]struct{}`, so it carries over some characteristics from the built-in Go `map` type. -Values neeed to be `comparable`. +The `Set` represents a collection of unique values, and it is implemented as a +wrapper around a `Map[T, struct{}]`. Like Maps, Sets require a `Hasher` to hash keys and check for equality. There are built-in hasher implementations for most primitive types such as `int`, `uint`, and diff --git a/immutable.go b/immutable.go index b3d7dcb..4a42e33 100644 --- a/immutable.go +++ b/immutable.go @@ -757,11 +757,10 @@ func (m *Map[K, V]) Set(key K, value V) *Map[K, V] { // This function will return a new map even if the updated value is the same as // the existing value because Map does not track value equality. func (m *Map[K, V]) SetMany(entries map[K]V) *Map[K, V] { - n := m.clone() for k, v := range entries { - n.set(k, v, true) + m = m.Set(k, v) } - return n + return m } func (m *Map[K, V]) set(key K, value V, mutable bool) *Map[K, V] { @@ -1644,11 +1643,10 @@ func (m *SortedMap[K, V]) Set(key K, value V) *SortedMap[K, V] { // SetMany returns a map with the keys set to the new values. func (m *SortedMap[K, V]) SetMany(entries map[K]V) *SortedMap[K, V] { - n := m.clone() for k, v := range entries { - n.set(k, v, true) + m = m.Set(k, v) } - return n + return m } func (m *SortedMap[K, V]) set(key K, value V, mutable bool) *SortedMap[K, V] { diff --git a/sets.go b/sets.go index fc30ffb..28f888d 100644 --- a/sets.go +++ b/sets.go @@ -18,7 +18,7 @@ func NewSet[T comparable](hasher Hasher[T], values ...T) Set[T] { m: NewMap[T, struct{}](hasher), } for _, value := range values { - s.m.set(value, struct{}{}, true) + s.m = s.m.set(value, struct{}{}, true) } return s } @@ -27,24 +27,18 @@ func NewSet[T comparable](hasher Hasher[T], values ...T) Set[T] { // // This function will return a new set even if the set already contains the value. func (s Set[T]) Set(values ...T) Set[T] { - n := Set[T]{ - m: s.m.clone(), - } for _, value := range values { - n.m.set(value, struct{}{}, true) + s.m = s.m.Set(value, struct{}{}) } - return n + return s } // Delete returns a set with the given key removed. func (s Set[T]) Delete(values ...T) Set[T] { - n := Set[T]{ - m: s.m.clone(), - } for _, value := range values { - n.m.delete(value, true) + s.m = s.m.Delete(value) } - return n + return s } // Has returns true when the set contains the given value @@ -137,7 +131,7 @@ func NewSortedSet[T comparable](comparer Comparer[T], values ...T) SortedSet[T] m: NewSortedMap[T, struct{}](comparer), } for _, value := range values { - s.m.set(value, struct{}{}, true) + s.m = s.m.set(value, struct{}{}, true) } return s } @@ -146,24 +140,18 @@ func NewSortedSet[T comparable](comparer Comparer[T], values ...T) SortedSet[T] // // This function will return a new set even if the set already contains the value. func (s SortedSet[T]) Set(values ...T) SortedSet[T] { - n := SortedSet[T]{ - m: s.m.clone(), - } for _, value := range values { - n.m.set(value, struct{}{}, true) + s.m = s.m.Set(value, struct{}{}) } - return n + return s } // Delete returns a set with the given key removed. func (s SortedSet[T]) Delete(values ...T) SortedSet[T] { - n := SortedSet[T]{ - m: s.m.clone(), - } for _, value := range values { - n.m.delete(value, true) + s.m = s.m.Delete(value) } - return n + return s } // Has returns true when the set contains the given value diff --git a/sets_test.go b/sets_test.go index b3900fc..5a83eb9 100644 --- a/sets_test.go +++ b/sets_test.go @@ -7,6 +7,7 @@ import ( func TestSetsPut(t *testing.T) { s := NewSet[string](nil) s2 := s.Set("1").Set("1") + s2.Set("2") if s.Len() != 0 { t.Fatalf("Unexpected mutation of set") } -- cgit v1.2.3 From a74b83e3f275e44f686066081c7fdb665180ff9e Mon Sep 17 00:00:00 2001 From: Oskar Haarklou Veileborg Date: Thu, 12 Jan 2023 10:22:46 +0100 Subject: sets & maps: remove varargs APIs & SetMany variants The implementation behind the API is not more efficient than manually looping over a data structure and inserting elements one-by-one. --- immutable.go | 19 ------------------- sets.go | 48 ++++++++++++++++-------------------------------- sets_test.go | 10 +++++----- 3 files changed, 21 insertions(+), 56 deletions(-) diff --git a/immutable.go b/immutable.go index 4a42e33..e43bc70 100644 --- a/immutable.go +++ b/immutable.go @@ -752,17 +752,6 @@ func (m *Map[K, V]) Set(key K, value V) *Map[K, V] { return m.set(key, value, false) } -// SetMany returns a map with the keys set to the new values. nil values are allowed. -// -// This function will return a new map even if the updated value is the same as -// the existing value because Map does not track value equality. -func (m *Map[K, V]) SetMany(entries map[K]V) *Map[K, V] { - for k, v := range entries { - m = m.Set(k, v) - } - return m -} - func (m *Map[K, V]) set(key K, value V, mutable bool) *Map[K, V] { // Set a hasher on the first value if one does not already exist. hasher := m.hasher @@ -1641,14 +1630,6 @@ func (m *SortedMap[K, V]) Set(key K, value V) *SortedMap[K, V] { return m.set(key, value, false) } -// SetMany returns a map with the keys set to the new values. -func (m *SortedMap[K, V]) SetMany(entries map[K]V) *SortedMap[K, V] { - for k, v := range entries { - m = m.Set(k, v) - } - return m -} - func (m *SortedMap[K, V]) set(key K, value V, mutable bool) *SortedMap[K, V] { // Set a comparer on the first value if one does not already exist. comparer := m.comparer diff --git a/sets.go b/sets.go index 28f888d..d610c15 100644 --- a/sets.go +++ b/sets.go @@ -14,31 +14,23 @@ type Set[T comparable] struct { // Default hasher implementations only exist for int, string, and byte slice types. // NewSet can also take some initial values as varargs. func NewSet[T comparable](hasher Hasher[T], values ...T) Set[T] { - s := Set[T]{ - m: NewMap[T, struct{}](hasher), - } + m := NewMap[T, struct{}](hasher) for _, value := range values { - s.m = s.m.set(value, struct{}{}, true) + m = m.set(value, struct{}{}, true) } - return s + return Set[T]{m} } -// Set returns a set containing the new value. +// Add returns a set containing the new value. // // This function will return a new set even if the set already contains the value. -func (s Set[T]) Set(values ...T) Set[T] { - for _, value := range values { - s.m = s.m.Set(value, struct{}{}) - } - return s +func (s Set[T]) Add(value T) Set[T] { + return Set[T]{s.m.Set(value, struct{}{})} } // Delete returns a set with the given key removed. -func (s Set[T]) Delete(values ...T) Set[T] { - for _, value := range values { - s.m = s.m.Delete(value) - } - return s +func (s Set[T]) Delete(value T) Set[T] { + return Set[T]{s.m.Delete(value)} } // Has returns true when the set contains the given value @@ -127,31 +119,23 @@ type SortedSet[T comparable] struct { // exist for int, string, and byte slice keys. // NewSortedSet can also take some initial values as varargs. func NewSortedSet[T comparable](comparer Comparer[T], values ...T) SortedSet[T] { - s := SortedSet[T]{ - m: NewSortedMap[T, struct{}](comparer), - } + m := NewSortedMap[T, struct{}](comparer) for _, value := range values { - s.m = s.m.set(value, struct{}{}, true) + m = m.set(value, struct{}{}, true) } - return s + return SortedSet[T]{m} } -// Set returns a set containing the new value. +// Add returns a set containing the new value. // // This function will return a new set even if the set already contains the value. -func (s SortedSet[T]) Set(values ...T) SortedSet[T] { - for _, value := range values { - s.m = s.m.Set(value, struct{}{}) - } - return s +func (s SortedSet[T]) Add(value T) SortedSet[T] { + return SortedSet[T]{s.m.Set(value, struct{}{})} } // Delete returns a set with the given key removed. -func (s SortedSet[T]) Delete(values ...T) SortedSet[T] { - for _, value := range values { - s.m = s.m.Delete(value) - } - return s +func (s SortedSet[T]) Delete(value T) SortedSet[T] { + return SortedSet[T]{s.m.Delete(value)} } // Has returns true when the set contains the given value diff --git a/sets_test.go b/sets_test.go index 5a83eb9..ca3aa3d 100644 --- a/sets_test.go +++ b/sets_test.go @@ -6,8 +6,8 @@ import ( func TestSetsPut(t *testing.T) { s := NewSet[string](nil) - s2 := s.Set("1").Set("1") - s2.Set("2") + s2 := s.Add("1").Add("1") + s2.Add("2") if s.Len() != 0 { t.Fatalf("Unexpected mutation of set") } @@ -34,7 +34,7 @@ func TestSetsPut(t *testing.T) { func TestSetsDelete(t *testing.T) { s := NewSet[string](nil) - s2 := s.Set("1") + s2 := s.Add("1") s3 := s.Delete("1") if s2.Len() != 1 { t.Fatalf("Unexpected non-mutation of set") @@ -52,7 +52,7 @@ func TestSetsDelete(t *testing.T) { func TestSortedSetsPut(t *testing.T) { s := NewSortedSet[string](nil) - s2 := s.Set("1").Set("1").Set("0") + s2 := s.Add("1").Add("1").Add("0") if s.Len() != 0 { t.Fatalf("Unexpected mutation of set") } @@ -86,7 +86,7 @@ func TestSortedSetsPut(t *testing.T) { func TestSortedSetsDelete(t *testing.T) { s := NewSortedSet[string](nil) - s2 := s.Set("1") + s2 := s.Add("1") s3 := s.Delete("1") if s2.Len() != 1 { t.Fatalf("Unexpected non-mutation of set") -- cgit v1.2.3 From bdfdabc970ef286de9390ff0ab7740ff1145d388 Mon Sep 17 00:00:00 2001 From: Oskar Haarklou Veileborg Date: Thu, 12 Jan 2023 10:59:36 +0100 Subject: list: fix Append & Prepend, remove varargs support Similar reason for the API change as the previous commit. --- immutable.go | 16 ++++------------ immutable_test.go | 13 +++++++++++++ 2 files changed, 17 insertions(+), 12 deletions(-) diff --git a/immutable.go b/immutable.go index e43bc70..666bb49 100644 --- a/immutable.go +++ b/immutable.go @@ -117,12 +117,8 @@ func (l *List[T]) set(index int, value T, mutable bool) *List[T] { } // Append returns a new list with value added to the end of the list. -func (l *List[T]) Append(values ...T) *List[T] { - other := l.clone() - for _, value := range values { - other.append(value, true) - } - return other +func (l *List[T]) Append(value T) *List[T] { + return l.append(value, false) } func (l *List[T]) append(value T, mutable bool) *List[T] { @@ -145,12 +141,8 @@ func (l *List[T]) append(value T, mutable bool) *List[T] { } // Prepend returns a new list with value(s) added to the beginning of the list. -func (l *List[T]) Prepend(values ...T) *List[T] { - other := l.clone() - for i := len(values) - 1; i >= 0; i-- { - other.prepend(values[i], true) - } - return other +func (l *List[T]) Prepend(value T) *List[T] { + return l.prepend(value, false) } func (l *List[T]) prepend(value T, mutable bool) *List[T] { diff --git a/immutable_test.go b/immutable_test.go index a878a78..9a0de37 100644 --- a/immutable_test.go +++ b/immutable_test.go @@ -223,6 +223,19 @@ func TestList(t *testing.T) { } }) + t.Run("AppendImmutable", func(t *testing.T) { + outer_l := NewList[int]() + for N := 0; N < 1_000; N++ { + l1 := outer_l.Append(0) + outer_l.Append(1) + if actual := l1.Get(N); actual != 0 { + t.Fatalf("Append mutates list with %d elements. Got %d instead of 0", N, actual) + } + + outer_l = outer_l.Append(0) + } + }) + RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) { l := NewTList() for i := 0; i < 100000; i++ { -- cgit v1.2.3 From bda5726650b18edea367db0fb16a29b9e711e3e2 Mon Sep 17 00:00:00 2001 From: Oskar Haarklou Veileborg Date: Thu, 12 Jan 2023 11:00:26 +0100 Subject: Fix random seed for TestRandom The closure passed to t.Run captured the loop variable which would always be equal to `*randomN` once the tests started running. This meant that all of the runs used the same random seed. --- immutable_test.go | 1 + 1 file changed, 1 insertion(+) diff --git a/immutable_test.go b/immutable_test.go index 9a0de37..581d4d8 100644 --- a/immutable_test.go +++ b/immutable_test.go @@ -2495,6 +2495,7 @@ func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand) } t.Run(name, func(t *testing.T) { for i := 0; i < *randomN; i++ { + i := i t.Run(fmt.Sprintf("%08d", i), func(t *testing.T) { t.Parallel() fn(t, rand.New(rand.NewSource(int64(i)))) -- cgit v1.2.3