Generic Collections

Exercise: Generic Collections

Difficulty - Intermediate

Learning Objectives

  • Understand Go generics syntax and type parameters
  • Learn to use constraints for type restrictions
  • Practice building generic data structures
  • Master generic functions with multiple type parameters
  • Implement common collection operations generically

Problem Statement

Create a collections package that implements type-safe generic data structures and utility functions.

Type Definitions

 1package collections
 2
 3// Stack is a generic LIFO stack
 4type Stack[T any] struct {
 5	items []T
 6}
 7
 8func NewStack[T any]() *Stack[T]
 9func Push(item T)
10func Pop()
11func Peek()
12func IsEmpty() bool
13func Size() int
14
15// Queue is a generic FIFO queue
16type Queue[T any] struct {
17	items []T
18}
19
20func NewQueue[T any]() *Queue[T]
21func Enqueue(item T)
22func Dequeue()
23func Front()
24func IsEmpty() bool
25func Size() int
26
27// Set is a generic set implementation
28type Set[T comparable] struct {
29	items map[T]struct{}
30}
31
32func NewSet[T comparable]() *Set[T]
33func Add(item T)
34func Remove(item T)
35func Contains(item T) bool
36func Size() int
37func ToSlice() []T
38func Union(other *Set[T]) *Set[T]
39func Intersection(other *Set[T]) *Set[T]
40
41// Ordered constraint for comparable and orderable types
42type Ordered interface {
43	~int | ~int8 | ~int16 | ~int32 | ~int64 |
44		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
45		~float32 | ~float64 | ~string
46}
47
48// Generic utility functions
49func Map[T any, U any](slice []T, fn func(T) U) []U
50func Filter[T any](slice []T, predicate func(T) bool) []T
51func Reduce[T any, U any](slice []T, initial U, fn func(U, T) U) U
52func Find[T any](slice []T, predicate func(T) bool)
53func Max[T Ordered](values ...T) T
54func Min[T Ordered](values ...T) T
55func Contains[T comparable](slice []T, item T) bool
56func Reverse[T any](slice []T) []T

Example Usage

 1package main
 2
 3import (
 4	"fmt"
 5	"strings"
 6	"collections"
 7)
 8
 9func main() {
10	// Stack example
11	stack := collections.NewStack[int]()
12	stack.Push(1)
13	stack.Push(2)
14	stack.Push(3)
15
16	val, _ := stack.Pop()
17	fmt.Println("Popped:", val) // 3
18
19	// Queue example
20	queue := collections.NewQueue[string]()
21	queue.Enqueue("first")
22	queue.Enqueue("second")
23	queue.Enqueue("third")
24
25	val2, _ := queue.Dequeue()
26	fmt.Println("Dequeued:", val2) // first
27
28	// Set example
29	set := collections.NewSet[string]()
30	set.Add("apple")
31	set.Add("banana")
32	set.Add("apple") // Duplicate ignored
33	fmt.Println("Set size:", set.Size()) // 2
34
35	set2 := collections.NewSet[string]()
36	set2.Add("banana")
37	set2.Add("cherry")
38
39	union := set.Union(set2)
40	fmt.Println("Union:", union.ToSlice()) // [apple banana cherry]
41
42	// Generic functions
43	numbers := []int{1, 2, 3, 4, 5}
44	doubled := collections.Map(numbers, func(n int) int { return n * 2 })
45	fmt.Println("Doubled:", doubled) // [2 4 6 8 10]
46
47	evens := collections.Filter(numbers, func(n int) bool { return n%2 == 0 })
48	fmt.Println("Evens:", evens) // [2 4]
49
50	sum := collections.Reduce(numbers, 0, func(acc, n int) int { return acc + n })
51	fmt.Println("Sum:", sum) // 15
52
53	words := []string{"hello", "world", "go"}
54	upper := collections.Map(words, strings.ToUpper)
55	fmt.Println("Upper:", upper) // [HELLO WORLD GO]
56
57	fmt.Println("Max:", collections.Max(5, 2, 8, 1, 9)) // 9
58	fmt.Println("Min:", collections.Min(5, 2, 8, 1, 9)) // 1
59}

Solution

Click to see the complete solution 
  1package collections
  2
  3// Stack implementation
  4type Stack[T any] struct {
  5	items []T
  6}
  7
  8func NewStack[T any]() *Stack[T] {
  9	return &Stack[T]{items: make([]T, 0)}
 10}
 11
 12func Push(item T) {
 13	s.items = append(s.items, item)
 14}
 15
 16func Pop() {
 17	if len(s.items) == 0 {
 18		var zero T
 19		return zero, false
 20	}
 21	item := s.items[len(s.items)-1]
 22	s.items = s.items[:len(s.items)-1]
 23	return item, true
 24}
 25
 26func Peek() {
 27	if len(s.items) == 0 {
 28		var zero T
 29		return zero, false
 30	}
 31	return s.items[len(s.items)-1], true
 32}
 33
 34func IsEmpty() bool {
 35	return len(s.items) == 0
 36}
 37
 38func Size() int {
 39	return len(s.items)
 40}
 41
 42// Queue implementation
 43type Queue[T any] struct {
 44	items []T
 45}
 46
 47func NewQueue[T any]() *Queue[T] {
 48	return &Queue[T]{items: make([]T, 0)}
 49}
 50
 51func Enqueue(item T) {
 52	q.items = append(q.items, item)
 53}
 54
 55func Dequeue() {
 56	if len(q.items) == 0 {
 57		var zero T
 58		return zero, false
 59	}
 60	item := q.items[0]
 61	q.items = q.items[1:]
 62	return item, true
 63}
 64
 65func Front() {
 66	if len(q.items) == 0 {
 67		var zero T
 68		return zero, false
 69	}
 70	return q.items[0], true
 71}
 72
 73func IsEmpty() bool {
 74	return len(q.items) == 0
 75}
 76
 77func Size() int {
 78	return len(q.items)
 79}
 80
 81// Set implementation
 82type Set[T comparable] struct {
 83	items map[T]struct{}
 84}
 85
 86func NewSet[T comparable]() *Set[T] {
 87	return &Set[T]{items: make(map[T]struct{})}
 88}
 89
 90func Add(item T) {
 91	s.items[item] = struct{}{}
 92}
 93
 94func Remove(item T) {
 95	delete(s.items, item)
 96}
 97
 98func Contains(item T) bool {
 99	_, exists := s.items[item]
100	return exists
101}
102
103func Size() int {
104	return len(s.items)
105}
106
107func ToSlice() []T {
108	result := make([]T, 0, len(s.items))
109	for item := range s.items {
110		result = append(result, item)
111	}
112	return result
113}
114
115func Union(other *Set[T]) *Set[T] {
116	result := NewSet[T]()
117	for item := range s.items {
118		result.Add(item)
119	}
120	for item := range other.items {
121		result.Add(item)
122	}
123	return result
124}
125
126func Intersection(other *Set[T]) *Set[T] {
127	result := NewSet[T]()
128	for item := range s.items {
129		if other.Contains(item) {
130			result.Add(item)
131		}
132	}
133	return result
134}
135
136// Ordered constraint
137type Ordered interface {
138	~int | ~int8 | ~int16 | ~int32 | ~int64 |
139		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
140		~float32 | ~float64 | ~string
141}
142
143// Generic utility functions
144func Map[T any, U any](slice []T, fn func(T) U) []U {
145	result := make([]U, len(slice))
146	for i, v := range slice {
147		result[i] = fn(v)
148	}
149	return result
150}
151
152func Filter[T any](slice []T, predicate func(T) bool) []T {
153	result := make([]T, 0)
154	for _, v := range slice {
155		if predicate(v) {
156			result = append(result, v)
157		}
158	}
159	return result
160}
161
162func Reduce[T any, U any](slice []T, initial U, fn func(U, T) U) U {
163	result := initial
164	for _, v := range slice {
165		result = fn(result, v)
166	}
167	return result
168}
169
170func Find[T any](slice []T, predicate func(T) bool) {
171	for _, v := range slice {
172		if predicate(v) {
173			return v, true
174		}
175	}
176	var zero T
177	return zero, false
178}
179
180func Max[T Ordered](values ...T) T {
181	if len(values) == 0 {
182		var zero T
183		return zero
184	}
185	max := values[0]
186	for _, v := range values[1:] {
187		if v > max {
188			max = v
189		}
190	}
191	return max
192}
193
194func Min[T Ordered](values ...T) T {
195	if len(values) == 0 {
196		var zero T
197		return zero
198	}
199	min := values[0]
200	for _, v := range values[1:] {
201		if v < min {
202			min = v
203		}
204	}
205	return min
206}
207
208func Contains[T comparable](slice []T, item T) bool {
209	for _, v := range slice {
210		if v == item {
211			return true
212		}
213	}
214	return false
215}
216
217func Reverse[T any](slice []T) []T {
218	result := make([]T, len(slice))
219	for i, v := range slice {
220		result[len(slice)-1-i] = v
221	}
222	return result
223}

Key Takeaways

  1. Type Parameters: Use [T any] syntax for generic types
  2. Constraints: comparable and Ordered restrict type parameters
  3. Zero Values: Use var zero T to return zero value of generic type
  4. Type Safety: Generics provide compile-time type checking
  5. Reusability: Write once, use with any compatible type