From 7bc00c3af1b4adcb2e783184eddd2e50de8e49f2 Mon Sep 17 00:00:00 2001 From: Suleiman Dibirov <3595194+idsulik@users.noreply.github.com> Date: Fri, 12 Jul 2024 17:57:32 +0300 Subject: [PATCH 1/4] Create LICENSE --- LICENSE | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 LICENSE diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..c8c4db8 --- /dev/null +++ b/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2024 Suleiman Dibirov + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. From c9650d9b9501ef2e269ed00bafe7d711a0d9a06f Mon Sep 17 00:00:00 2001 From: Suleiman Dibirov Date: Fri, 12 Jul 2024 18:07:35 +0300 Subject: [PATCH 2/4] docs: Update README.md --- README.md | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/README.md b/README.md index 3794608..dcf4c79 100644 --- a/README.md +++ b/README.md @@ -1,4 +1,9 @@ # go-collections +[![Go Report Card](https://goreportcard.com/badge/github.com/idsulik/go-collections)](https://goreportcard.com/report/github.com/idsulik/go-collections) +![Build Status](https://img.shields.io/github/actions/workflow/status/idsulik/go-collections/go.yaml?branch=main) +[![Version](https://img.shields.io/github/v/release/idsulik/go-collections)](https://github.com/idsulik/go-collections/releases) +[![License](https://img.shields.io/github/license/idsulik/go-collections)](https://github.com/idsulik/go-collections/blob/main/LICENSE) +[![GoDoc](https://pkg.go.dev/badge/github.com/idsulik/go-collections)](https://pkg.go.dev/github.com/idsulik/go-collections) `go-collections` is a Go library that provides implementations of common data structures including a double-ended queue (Deque), a linked list, a queue, and a stack. This package offers a simple and efficient way to use these structures in Go, with support for generic types. @@ -118,4 +123,4 @@ A LIFO (last-in, first-out) stack that supports standard stack operations. ## License -This project is licensed under the MIT License \ No newline at end of file +This project is licensed under the [MIT License](LICENSE) - see the [LICENSE](LICENSE) file for details. From 8b7be0bb96434a1c620b21da5eef3015b27e4550 Mon Sep 17 00:00:00 2001 From: Suleiman Dibirov Date: Mon, 15 Jul 2024 08:18:03 +0300 Subject: [PATCH 3/4] feat: Add Set structure --- set/set.go | 121 ++++++++++++++++++++++++++++++ set/set_test.go | 194 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 315 insertions(+) create mode 100644 set/set.go create mode 100644 set/set_test.go diff --git a/set/set.go b/set/set.go new file mode 100644 index 0000000..7ed7d75 --- /dev/null +++ b/set/set.go @@ -0,0 +1,121 @@ +package set + +// Set represents a set of unique items. +type Set[T comparable] struct { + items map[T]struct{} +} + +// New creates and returns a new, empty set. +func New[T comparable]() *Set[T] { + return &Set[T]{ + items: make(map[T]struct{}), + } +} + +// Add adds an item to the set. +func (s *Set[T]) Add(item T) { + s.items[item] = struct{}{} +} + +// Remove removes an item from the set. +func (s *Set[T]) Remove(item T) { + delete(s.items, item) +} + +// Has returns true if the set contains the specified item. +func (s *Set[T]) Has(item T) bool { + _, ok := s.items[item] + return ok +} + +// Clear removes all items from the set. +func (s *Set[T]) Clear() { + s.items = make(map[T]struct{}) +} + +// Len returns the number of items in the set. +func (s *Set[T]) Len() int { + return len(s.items) +} + +// IsEmpty returns true if the set is empty. +func (s *Set[T]) IsEmpty() bool { + return len(s.items) == 0 +} + +// Elements returns a slice containing all items in the set. +func (s *Set[T]) Elements() []T { + elements := make([]T, 0, len(s.items)) + for item := range s.items { + elements = append(elements, item) + } + return elements +} + +// AddAll adds multiple items to the set. +func (s *Set[T]) AddAll(items ...T) { + for _, item := range items { + s.Add(item) + } +} + +// RemoveAll removes multiple items from the set. +func (s *Set[T]) RemoveAll(items ...T) { + for _, item := range items { + s.Remove(item) + } +} + +// Diff returns a new set containing items that are in the receiver set but not in the other set. +func (s *Set[T]) Diff(other *Set[T]) *Set[T] { + out := New[T]() + for item := range s.items { + if !other.Has(item) { + out.Add(item) + } + } + return out +} + +// Intersect returns a new set containing items that are in both the receiver set and the other set. +func (s *Set[T]) Intersect(other *Set[T]) *Set[T] { + out := New[T]() + for item := range s.items { + if other.Has(item) { + out.Add(item) + } + } + return out +} + +// Union returns a new set containing items that are in either the receiver set or the other set. +func (s *Set[T]) Union(other *Set[T]) *Set[T] { + out := New[T]() + for item := range s.items { + out.Add(item) + } + for item := range other.items { + out.Add(item) + } + return out +} + +// IsSubset returns true if the receiver set is a subset of the other set. +func (s *Set[T]) IsSubset(other *Set[T]) bool { + for item := range s.items { + if !other.Has(item) { + return false + } + } + return true +} + +// IsSuperset returns true if the receiver set is a superset of the other set. +func (s *Set[T]) IsSuperset(other *Set[T]) bool { + return other.IsSubset(s) +} + +// Equal returns true if the receiver set is equal to the other set. +func (s *Set[T]) Equal(other *Set[T]) bool { + return s.IsSubset(other) && s.IsSuperset(other) +} diff --git a/set/set_test.go b/set/set_test.go new file mode 100644 index 0000000..d819e1a --- /dev/null +++ b/set/set_test.go @@ -0,0 +1,194 @@ +package set + +import ( + "reflect" + "sort" + "testing" +) + +// TestNew checks the creation of a new Set. +func TestNew(t *testing.T) { + s := New[int]() + if s == nil { + t.Error("Expected new set to be non-nil") + } +} + +// TestAdd checks adding elements to the Set. +func TestAdd(t *testing.T) { + s := New[int]() + s.Add(1) + if !s.Has(1) { + t.Errorf("Expected 1 to be in the set") + } +} + +// TestRemove checks removing elements from the Set. +func TestRemove(t *testing.T) { + s := New[int]() + s.Add(1) + s.Remove(1) + if s.Has(1) { + t.Errorf("Expected 1 to be removed from the set") + } +} + +// TestHas checks if the Set has an element. +func TestHas(t *testing.T) { + s := New[int]() + s.Add(1) + if !s.Has(1) { + t.Errorf("Expected 1 to be in the set") + } +} + +// TestClear checks clearing the Set. +func TestClear(t *testing.T) { + s := New[int]() + s.Add(1) + s.Add(2) + s.Clear() + if s.Len() != 0 { + t.Errorf("Expected set to be empty, got size %d", s.Len()) + } +} + +// TestLen checks the size of the Set. +func TestLen(t *testing.T) { + s := New[int]() + s.Add(1) + s.Add(2) + if s.Len() != 2 { + t.Errorf("Expected size 2, got %d", s.Len()) + } +} + +// TestIsEmpty checks if IsEmpty properly identifies an empty Set. +func TestIsEmpty(t *testing.T) { + s := New[int]() + if !s.IsEmpty() { + t.Errorf("Expected set to be empty initially") + } + s.Add(1) + if s.IsEmpty() { + t.Errorf("Expected set not to be empty after adding an element") + } + s.Clear() + if !s.IsEmpty() { + t.Errorf("Expected set to be empty after clearing") + } +} + +// TestElements checks if Elements returns a correct slice of the set's elements. +func TestElements(t *testing.T) { + s := New[int]() + s.Add(1) + s.Add(2) + expected := []int{1, 2} + actual := s.Elements() + sort.Slice(actual, func(i, j int) bool { return actual[i] < actual[j] }) + + if !reflect.DeepEqual(actual, expected) { + t.Errorf("Expected elements %v, got %v", expected, actual) + } +} + +// TestAddAll checks adding multiple elements to the Set. +func TestAddAll(t *testing.T) { + s := New[int]() + s.AddAll(1, 2, 3) + if !s.Has(1) || !s.Has(2) || !s.Has(3) { + t.Errorf("Expected elements 1, 2, 3 to be in the set") + } +} + +// TestRemoveAll checks removing multiple elements from the Set. +func TestRemoveAll(t *testing.T) { + s := New[int]() + s.AddAll(1, 2, 3) + s.RemoveAll(1, 2) + if s.Has(1) || s.Has(2) || !s.Has(3) { + t.Errorf("Expected elements 1 and 2 to be removed from the set") + } +} + +// TestDiff checks the difference between two sets. +func TestDiff(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2, 3) + s2.AddAll(2, 3, 4) + diff := s1.Diff(s2) + expected := []int{1} + actual := diff.Elements() + sort.Slice(actual, func(i, j int) bool { return actual[i] < actual[j] }) + + if !reflect.DeepEqual(actual, expected) { + t.Errorf("Expected difference %v, got %v", expected, actual) + } +} + +// TestIntersect checks the intersection between two sets. +func TestIntersect(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2, 3) + s2.AddAll(2, 3, 4) + intersect := s1.Intersect(s2) + expected := []int{2, 3} + actual := intersect.Elements() + sort.Slice(actual, func(i, j int) bool { return actual[i] < actual[j] }) + + if !reflect.DeepEqual(actual, expected) { + t.Errorf("Expected intersection %v, got %v", expected, actual) + } +} + +// TestUnion checks the union between two sets. +func TestUnion(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2, 3) + s2.AddAll(2, 3, 4) + union := s1.Union(s2) + expected := []int{1, 2, 3, 4} + actual := union.Elements() + sort.Slice(actual, func(i, j int) bool { return actual[i] < actual[j] }) + + if !reflect.DeepEqual(actual, expected) { + t.Errorf("Expected union %v, got %v", expected, actual) + } +} + +// TestIsSubset checks if a set is a subset of another set. +func TestIsSubset(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2) + s2.AddAll(1, 2, 3) + if !s1.IsSubset(s2) { + t.Errorf("Expected s1 to be a subset of s2") + } +} + +// TestIsSuperset checks if a set is a superset of another set. +func TestIsSuperset(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2, 3) + s2.AddAll(1, 2) + if !s1.IsSuperset(s2) { + t.Errorf("Expected s1 to be a superset of s2") + } +} + +// TestEqual checks if two sets are equal. +func TestEqual(t *testing.T) { + s1 := New[int]() + s2 := New[int]() + s1.AddAll(1, 2) + s2.AddAll(1, 2) + if !s1.Equal(s2) { + t.Errorf("Expected s1 to be equal to s2") + } +} From 0ff618731a494e8277ba169ed9f8a51e5549f0b7 Mon Sep 17 00:00:00 2001 From: Suleiman Dibirov Date: Mon, 15 Jul 2024 08:18:31 +0300 Subject: [PATCH 4/4] fix: Change test count 1 -> 3 --- .github/workflows/go.yaml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/.github/workflows/go.yaml b/.github/workflows/go.yaml index 762aff3..7b5deed 100644 --- a/.github/workflows/go.yaml +++ b/.github/workflows/go.yaml @@ -22,7 +22,7 @@ jobs: go-version: '1.20' - name: Run tests - run: go test ./... + run: go test -count=3 -v ./... - name: Build run: go build -v ./... \ No newline at end of file