aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBen Johnson <benbjohnson@yahoo.com>2023-01-02 10:49:14 -0700
committerGitHub <noreply@github.com>2023-01-02 10:49:14 -0700
commit4dd1fd8b0a5501553e35fc21ecde1a6b1863c2ca (patch)
tree11208329fc4edf7c9b7167a1e7148b9e4ca69864
parentMerge pull request #34 from laher/sets (diff)
parentset/sorted-set: Items() to return slice of items (diff)
downloadpds-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.md25
-rw-r--r--immutable.go49
-rw-r--r--immutable_test.go32
-rw-r--r--sets.go123
-rw-r--r--sets_test.go4
5 files changed, 212 insertions, 21 deletions
diff --git a/README.md b/README.md
index d1b3b87..ed771c6 100644
--- a/README.md
+++ b/README.md
@@ -2,7 +2,7 @@ Immutable ![release](https://img.shields.io/github/release/benbjohnson/immutable
=========
This repository contains *generic* immutable collection types for Go. It includes
-`List`, `Map`, and `SortedMap` implementations. Immutable collections can
+`List`, `Map`, `SortedMap`, `Set` and `SortedSet` implementations. Immutable collections can
provide efficient, lock free sharing of data by requiring that edits to the
collections return new collections.
@@ -284,6 +284,29 @@ type Comparer[K comparable] interface {
Please see the internal `defaultComparer` for an example, bearing in mind that it works for several types.
+## Set
+
+The `Set` represents a collection of unique values. It uses a `map[T]struct{}`, so it carries over some characteristics from the built-in Go `map` type.
+Values neeed to be `comparable`.
+
+Like Maps, Sets require a `Hasher` to hash keys and check for equality. There are built-in
+hasher implementations for most primitive types such as `int`, `uint`, and
+`string` keys. You may pass in a `nil` hasher to `NewMap()` if you are using
+one of these key types.
+
+
+## Sorted Set
+
+The `SortedSet` represents a sorted collection of unique values.
+Unlike the `Set`, however, keys can be iterated over in-order. It is implemented
+as a B+tree.
+
+Sorted sets require a `Comparer` to sort values and check for equality. There are
+built-in comparer implementations for `int`, `uint`, and `string` keys. You may
+pass a `nil` comparer to `NewSortedSet()` if you are using one of these key
+types.
+
+The API is identical to the `Set` implementation.
## Contributing
diff --git a/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) {
diff --git a/sets.go b/sets.go
index 0fe550c..fc30ffb 100644
--- a/sets.go
+++ b/sets.go
@@ -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")