aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAm Laher <amir.laher@tixtrack.com>2022-12-24 22:23:14 +1300
committerAm Laher <amir.laher@tixtrack.com>2022-12-24 22:23:14 +1300
commit6d484e5ae1d142dda3acc24f1d29bd81cb1aa2e1 (patch)
tree7cc52e761bbec9c5091e4a15fe14c447bc61a4b8
parentMerge pull request #30 from laher/master (diff)
downloadpds-6d484e5ae1d142dda3acc24f1d29bd81cb1aa2e1.tar.gz
pds-6d484e5ae1d142dda3acc24f1d29bd81cb1aa2e1.tar.xz
Set + SortedSet with test
-rw-r--r--sets.go170
-rw-r--r--sets_test.go102
2 files changed, 272 insertions, 0 deletions
diff --git a/sets.go b/sets.go
new file mode 100644
index 0000000..0fe550c
--- /dev/null
+++ b/sets.go
@@ -0,0 +1,170 @@
+package immutable
+
+type Set[T comparable] struct {
+ m *Map[T, struct{}]
+}
+
+func NewSet[T comparable](hasher Hasher[T]) Set[T] {
+ return Set[T]{
+ m: NewMap[T, struct{}](hasher),
+ }
+}
+
+func (s Set[T]) Set(val T) Set[T] {
+ return Set[T]{
+ m: s.m.Set(val, struct{}{}),
+ }
+}
+
+func (s Set[T]) Delete(val T) Set[T] {
+ return Set[T]{
+ m: s.m.Delete(val),
+ }
+}
+
+func (s Set[T]) Has(val T) bool {
+ _, ok := s.m.Get(val)
+ return ok
+}
+
+func (s Set[K]) Len() int {
+ return s.m.Len()
+}
+
+func (s Set[T]) Iterator() *SetIterator[T] {
+ itr := &SetIterator[T]{mi: s.m.Iterator()}
+ itr.mi.First()
+ return itr
+}
+
+type SetIterator[T comparable] struct {
+ mi *MapIterator[T, struct{}]
+}
+
+func (itr *SetIterator[T]) Done() bool {
+ return itr.mi.Done()
+}
+
+func (itr *SetIterator[T]) First() {
+ itr.mi.First()
+}
+
+func (itr *SetIterator[T]) Next() (val T, ok bool) {
+ val, _, ok = itr.mi.Next()
+ return
+}
+
+type SetBuilder[T comparable] struct {
+ s Set[T]
+}
+
+func NewSetBuilder[T comparable](hasher Hasher[T]) *SetBuilder[T] {
+ return &SetBuilder[T]{s: NewSet(hasher)}
+}
+
+func (s SetBuilder[T]) Set(val T) {
+ s.s.m = s.s.m.set(val, struct{}{}, true)
+}
+
+func (s SetBuilder[T]) Delete(val T) {
+ s.s.m = s.s.m.delete(val, true)
+}
+
+func (s SetBuilder[T]) Has(val T) bool {
+ return s.s.Has(val)
+}
+
+func (s SetBuilder[T]) Len() int {
+ return s.s.Len()
+}
+
+type SortedSet[T comparable] struct {
+ m *SortedMap[T, struct{}]
+}
+
+func NewSortedSet[T comparable](comparer Comparer[T]) SortedSet[T] {
+ return SortedSet[T]{
+ m: NewSortedMap[T, struct{}](comparer),
+ }
+}
+
+func (s SortedSet[T]) Put(val T) SortedSet[T] {
+ return SortedSet[T]{
+ m: s.m.Set(val, struct{}{}),
+ }
+}
+
+func (s SortedSet[T]) Delete(val T) SortedSet[T] {
+ return SortedSet[T]{
+ m: s.m.Delete(val),
+ }
+}
+
+func (s SortedSet[T]) Has(val T) bool {
+ _, ok := s.m.Get(val)
+ return ok
+}
+
+func (s SortedSet[K]) Len() int {
+ return s.m.Len()
+}
+
+func (s SortedSet[T]) Iterator() *SortedSetIterator[T] {
+ itr := &SortedSetIterator[T]{mi: s.m.Iterator()}
+ itr.mi.First()
+ return itr
+}
+
+type SortedSetIterator[T comparable] struct {
+ mi *SortedMapIterator[T, struct{}]
+}
+
+func (itr *SortedSetIterator[T]) Done() bool {
+ return itr.mi.Done()
+}
+
+func (itr *SortedSetIterator[T]) First() {
+ itr.mi.First()
+}
+
+func (itr *SortedSetIterator[T]) Last() {
+ itr.mi.Last()
+}
+
+func (itr *SortedSetIterator[T]) Next() (val T, ok bool) {
+ val, _, ok = itr.mi.Next()
+ return
+}
+
+func (itr *SortedSetIterator[T]) Prev() (val T, ok bool) {
+ val, _, ok = itr.mi.Prev()
+ return
+}
+
+func (itr *SortedSetIterator[T]) Seek(val T) {
+ itr.mi.Seek(val)
+}
+
+type SortedSetBuilder[T comparable] struct {
+ s SortedSet[T]
+}
+
+func NewSortedSetBuilder[T comparable](comparer Comparer[T]) *SortedSetBuilder[T] {
+ return &SortedSetBuilder[T]{s: NewSortedSet(comparer)}
+}
+
+func (s SortedSetBuilder[T]) Set(val T) {
+ s.s.m = s.s.m.set(val, struct{}{}, true)
+}
+
+func (s SortedSetBuilder[T]) Delete(val T) {
+ s.s.m = s.s.m.delete(val, true)
+}
+
+func (s SortedSetBuilder[T]) Has(val T) bool {
+ return s.s.Has(val)
+}
+
+func (s SortedSetBuilder[T]) Len() int {
+ return s.s.Len()
+}
diff --git a/sets_test.go b/sets_test.go
new file mode 100644
index 0000000..d2e7f32
--- /dev/null
+++ b/sets_test.go
@@ -0,0 +1,102 @@
+package immutable
+
+import (
+ "testing"
+)
+
+func TestSetsPut(t *testing.T) {
+ s := NewSet[string](nil)
+ s2 := s.Set("1").Set("1")
+ if s.Len() != 0 {
+ t.Fatalf("Unexpected mutation of set")
+ }
+ if s.Has("1") {
+ t.Fatalf("Unexpected set element")
+ }
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ itr := s2.Iterator()
+ counter := 0
+ for !itr.Done() {
+ i, v := itr.Next()
+ t.Log(i, v)
+ counter++
+ }
+ if counter != 1 {
+ t.Fatalf("iterator wrong length")
+ }
+}
+
+func TestSetsDelete(t *testing.T) {
+ s := NewSet[string](nil)
+ s2 := s.Set("1")
+ s3 := s.Delete("1")
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ if s3.Len() != 0 {
+ t.Fatalf("Unexpected set length after delete")
+ }
+ if s3.Has("1") {
+ t.Fatalf("Unexpected set element after delete")
+ }
+}
+
+func TestSortedSetsPut(t *testing.T) {
+ s := NewSortedSet[string](nil)
+ s2 := s.Put("1").Put("1").Put("0")
+ if s.Len() != 0 {
+ t.Fatalf("Unexpected mutation of set")
+ }
+ if s.Has("1") {
+ t.Fatalf("Unexpected set element")
+ }
+ if s2.Len() != 2 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+
+ itr := s2.Iterator()
+ counter := 0
+ for !itr.Done() {
+ i, v := itr.Next()
+ t.Log(i, v)
+ if counter == 0 && i != "0" {
+ t.Fatalf("sort did not work for first el")
+ }
+ if counter == 1 && i != "1" {
+ t.Fatalf("sort did not work for second el")
+ }
+ counter++
+ }
+ if counter != 2 {
+ t.Fatalf("iterator wrong length")
+ }
+}
+
+func TestSortedSetsDelete(t *testing.T) {
+ s := NewSortedSet[string](nil)
+ s2 := s.Put("1")
+ s3 := s.Delete("1")
+ if s2.Len() != 1 {
+ t.Fatalf("Unexpected non-mutation of set")
+ }
+ if !s2.Has("1") {
+ t.Fatalf("Set element missing")
+ }
+ if s3.Len() != 0 {
+ t.Fatalf("Unexpected set length after delete")
+ }
+ if s3.Has("1") {
+ t.Fatalf("Unexpected set element after delete")
+ }
+}