diff options
author | Ben Johnson <benbjohnson@yahoo.com> | 2023-01-02 10:49:14 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-01-02 10:49:14 -0700 |
commit | 4dd1fd8b0a5501553e35fc21ecde1a6b1863c2ca (patch) | |
tree | 11208329fc4edf7c9b7167a1e7148b9e4ca69864 | |
parent | Merge pull request #34 from laher/sets (diff) | |
parent | set/sorted-set: Items() to return slice of items (diff) | |
download | pds-4dd1fd8b0a5501553e35fc21ecde1a6b1863c2ca.tar.gz pds-4dd1fd8b0a5501553e35fc21ecde1a6b1863c2ca.tar.xz |
Merge pull request #35 from laher/sets-maps-append-multi
Sets & maps append-multi. Also docs and a fix for SortedSets
-rw-r--r-- | README.md | 25 | ||||
-rw-r--r-- | immutable.go | 49 | ||||
-rw-r--r-- | immutable_test.go | 32 | ||||
-rw-r--r-- | sets.go | 123 | ||||
-rw-r--r-- | sets_test.go | 4 |
5 files changed, 212 insertions, 21 deletions
@@ -2,7 +2,7 @@ Immutable ` if you are using +one of these key types. + + +## Sorted Set + +The `SortedSet` represents a sorted collection of unique values. +Unlike the `Set`, however, keys can be iterated over in-order. It is implemented +as a B+tree. + +Sorted sets require a `Comparer` to sort values and check for equality. There are +built-in comparer implementations for `int`, `uint`, and `string` keys. You may +pass a `nil` comparer to `NewSortedSet()` if you are using one of these key +types. + +The API is identical to the `Set` implementation. ## Contributing diff --git a/immutable.go b/immutable.go index eefc573..b3d7dcb 100644 --- a/immutable.go +++ b/immutable.go @@ -707,6 +707,20 @@ func NewMap[K comparable, V any](hasher Hasher[K]) *Map[K, V] { } } +// NewMapOf returns a new instance of Map, containing a map of provided entries. +// +// If hasher is nil, a default hasher implementation will automatically be chosen based on the first key added. +// Default hasher implementations only exist for int, string, and byte slice types. +func NewMapOf[K comparable, V any](hasher Hasher[K], entries map[K]V) *Map[K, V] { + m := &Map[K, V]{ + hasher: hasher, + } + for k, v := range entries { + m.set(k, v, true) + } + return m +} + // Len returns the number of elements in the map. func (m *Map[K, V]) Len() int { return m.size @@ -738,6 +752,18 @@ 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] { + n := m.clone() + for k, v := range entries { + n.set(k, v, true) + } + return n +} + 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 @@ -1582,6 +1608,20 @@ func NewSortedMap[K comparable, V any](comparer Comparer[K]) *SortedMap[K, V] { } } +// NewSortedMapOf returns a new instance of SortedMap, containing a map of provided entries. +// +// If comparer is nil then a default comparer is set after the first key is inserted. Default comparers +// exist for int, string, and byte slice keys. +func NewSortedMapOf[K comparable, V any](comparer Comparer[K], entries map[K]V) *SortedMap[K, V] { + m := &SortedMap[K, V]{ + comparer: comparer, + } + for k, v := range entries { + m.set(k, v, true) + } + return m +} + // Len returns the number of elements in the sorted map. func (m *SortedMap[K, V]) Len() int { return m.size @@ -1602,6 +1642,15 @@ 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] { + n := m.clone() + for k, v := range entries { + n.set(k, v, true) + } + return n +} + 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/immutable_test.go b/immutable_test.go index 6a0ee22..a878a78 100644 --- a/immutable_test.go +++ b/immutable_test.go @@ -200,8 +200,10 @@ func TestList(t *testing.T) { t.Fatal("Failed to find leaf node due to nil child") } return findLeaf(n.children[0]) - case *listLeafNode[*int]: return n - default: panic("Unexpected case") + case *listLeafNode[*int]: + return n + default: + panic("Unexpected case") } } @@ -959,6 +961,22 @@ func TestMap_Set(t *testing.T) { } }) + t.Run("Multi", func(t *testing.T) { + m := NewMapOf(nil, map[int]string{1: "foo"}) + itr := m.Iterator() + if itr.Done() { + t.Fatal("MapIterator.Done()=false, expected true") + } + if k, v, ok := itr.Next(); !ok { + t.Fatalf("MapIterator.Next()!=ok, expected ok") + } else if k != 1 || v != "foo" { + t.Fatalf("MapIterator.Next()=<%v,%v>, expected <1, \"foo\">", k, v) + } + if k, v, ok := itr.Next(); ok { + t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v) + } + }) + t.Run("VerySmall", func(t *testing.T) { const n = 6 m := NewMap[int, int](nil) @@ -1070,6 +1088,16 @@ func TestMap_Overwrite(t *testing.T) { t.Fatalf("Get(%d)=<%v,%v>", i, v, ok) } } + + t.Run("Simple", func(t *testing.T) { + m := NewMap[int, string](nil) + itr := m.Iterator() + if !itr.Done() { + t.Fatal("MapIterator.Done()=true, expected false") + } else if k, v, ok := itr.Next(); ok { + t.Fatalf("MapIterator.Next()=<%v,%v>, expected nil", k, v) + } + }) } func TestMap_Delete(t *testing.T) { @@ -1,54 +1,98 @@ package immutable +// Set represents a collection of unique values. The set uses a Hasher +// to generate hashes and check for equality of key values. +// +// Internally, the Set stores values as keys of a Map[T,struct{}] type Set[T comparable] struct { m *Map[T, struct{}] } -func NewSet[T comparable](hasher Hasher[T]) Set[T] { - return Set[T]{ +// NewSet returns a new instance of Set. +// +// If hasher is nil, a default hasher implementation will automatically be chosen based on the first key added. +// Default hasher implementations only exist for int, string, and byte slice types. +// NewSet can also take some initial values as varargs. +func NewSet[T comparable](hasher Hasher[T], values ...T) Set[T] { + s := Set[T]{ m: NewMap[T, struct{}](hasher), } + for _, value := range values { + s.m.set(value, struct{}{}, true) + } + return s } -func (s Set[T]) Set(val T) Set[T] { - return Set[T]{ - m: s.m.Set(val, struct{}{}), +// Set 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] { + n := Set[T]{ + m: s.m.clone(), + } + for _, value := range values { + n.m.set(value, struct{}{}, true) } + return n } -func (s Set[T]) Delete(val T) Set[T] { - return Set[T]{ - m: s.m.Delete(val), +// 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) } + return n } +// Has returns true when the set contains the given value func (s Set[T]) Has(val T) bool { _, ok := s.m.Get(val) return ok } +// Len returns the number of elements in the underlying map. func (s Set[K]) Len() int { return s.m.Len() } +// Items returns a slice of the items inside the set +func (s Set[T]) Items() []T { + r := make([]T, 0, s.Len()) + itr := s.Iterator() + for !itr.Done() { + v, _ := itr.Next() + r = append(r, v) + } + return r +} + +// Iterator returns a new iterator for this set positioned at the first value. func (s Set[T]) Iterator() *SetIterator[T] { itr := &SetIterator[T]{mi: s.m.Iterator()} itr.mi.First() return itr } +// SetIterator represents an iterator over a set. +// Iteration can occur in natural or reverse order based on use of Next() or Prev(). type SetIterator[T comparable] struct { mi *MapIterator[T, struct{}] } +// Done returns true if no more values remain in the iterator. func (itr *SetIterator[T]) Done() bool { return itr.mi.Done() } +// First moves the iterator to the first value. func (itr *SetIterator[T]) First() { itr.mi.First() } +// Next moves the iterator to the next value. func (itr *SetIterator[T]) Next() (val T, ok bool) { val, _, ok = itr.mi.Next() return @@ -82,65 +126,112 @@ type SortedSet[T comparable] struct { m *SortedMap[T, struct{}] } -func NewSortedSet[T comparable](comparer Comparer[T]) SortedSet[T] { - return SortedSet[T]{ +// NewSortedSet returns a new instance of SortedSet. +// +// If comparer is nil then +// a default comparer is set after the first key is inserted. Default comparers +// exist for int, string, and byte slice keys. +// NewSortedSet can also take some initial values as varargs. +func NewSortedSet[T comparable](comparer Comparer[T], values ...T) SortedSet[T] { + s := SortedSet[T]{ m: NewSortedMap[T, struct{}](comparer), } + for _, value := range values { + s.m.set(value, struct{}{}, true) + } + return s } -func (s SortedSet[T]) Put(val T) SortedSet[T] { - return SortedSet[T]{ - m: s.m.Set(val, struct{}{}), +// Set 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] { + n := SortedSet[T]{ + m: s.m.clone(), + } + for _, value := range values { + n.m.set(value, struct{}{}, true) } + return n } -func (s SortedSet[T]) Delete(val T) SortedSet[T] { - return SortedSet[T]{ - m: s.m.Delete(val), +// 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) } + return n } +// Has returns true when the set contains the given value func (s SortedSet[T]) Has(val T) bool { _, ok := s.m.Get(val) return ok } +// Len returns the number of elements in the underlying map. func (s SortedSet[K]) Len() int { return s.m.Len() } +// Items returns a slice of the items inside the set +func (s SortedSet[T]) Items() []T { + r := make([]T, 0, s.Len()) + itr := s.Iterator() + for !itr.Done() { + v, _ := itr.Next() + r = append(r, v) + } + return r +} + +// Iterator returns a new iterator for this set positioned at the first value. func (s SortedSet[T]) Iterator() *SortedSetIterator[T] { itr := &SortedSetIterator[T]{mi: s.m.Iterator()} itr.mi.First() return itr } +// SortedSetIterator represents an iterator over a sorted set. +// Iteration can occur in natural or reverse order based on use of Next() or Prev(). type SortedSetIterator[T comparable] struct { mi *SortedMapIterator[T, struct{}] } +// Done returns true if no more values remain in the iterator. func (itr *SortedSetIterator[T]) Done() bool { return itr.mi.Done() } +// First moves the iterator to the first value. func (itr *SortedSetIterator[T]) First() { itr.mi.First() } +// Last moves the iterator to the last value. func (itr *SortedSetIterator[T]) Last() { itr.mi.Last() } +// Next moves the iterator to the next value. func (itr *SortedSetIterator[T]) Next() (val T, ok bool) { val, _, ok = itr.mi.Next() return } +// Next moves the iterator to the previous value. func (itr *SortedSetIterator[T]) Prev() (val T, ok bool) { val, _, ok = itr.mi.Prev() return } +// Next moves the iterator to the given value. +// +// If the value does not exist then the next value is used. If no more keys exist +// then the iterator is marked as done. func (itr *SortedSetIterator[T]) Seek(val T) { itr.mi.Seek(val) } diff --git a/sets_test.go b/sets_test.go index d2e7f32..b3900fc 100644 --- a/sets_test.go +++ b/sets_test.go @@ -51,7 +51,7 @@ func TestSetsDelete(t *testing.T) { func TestSortedSetsPut(t *testing.T) { s := NewSortedSet[string](nil) - s2 := s.Put("1").Put("1").Put("0") + s2 := s.Set("1").Set("1").Set("0") if s.Len() != 0 { t.Fatalf("Unexpected mutation of set") } @@ -85,7 +85,7 @@ func TestSortedSetsPut(t *testing.T) { func TestSortedSetsDelete(t *testing.T) { s := NewSortedSet[string](nil) - s2 := s.Put("1") + s2 := s.Set("1") s3 := s.Delete("1") if s2.Len() != 1 { t.Fatalf("Unexpected non-mutation of set") |