Generics in Practice
Exercise Overview
Build a comprehensive data processing library using Go generics. You'll create type-safe collections, algorithms, and utilities that work with multiple data types while maintaining compile-time safety.
Learning Objectives
- Design and implement generic data structures
- Create reusable algorithms with type parameters
- Use constraints to limit generic types
- Apply generics to solve real-world problems
- Understand when to use generics vs interfaces
- Build generic utility functions for common operations
- Create type-safe builders and configuration patterns
The Problem - Type-Safe Data Processing Library
You need to build a data processing library that can handle different data types while maintaining type safety and avoiding code duplication.
Initial Code
1package main
2
3import (
4 "fmt"
5 "constraints"
6 "math"
7)
8
9// TODO: Implement generic collection types
10type Collection[T any] interface {
11 // Add collection interface methods
12}
13
14// TODO: Implement generic stack
15type Stack[T any] struct {
16 // Add stack implementation
17}
18
19// TODO: Implement generic queue
20type Queue[T any] struct {
21 // Add queue implementation
22}
23
24// TODO: Implement generic binary search tree
25type BST[T constraints.Ordered] struct {
26 // Add BST implementation
27}
28
29// TODO: Implement generic algorithms
30func GenericSort[T constraints.Ordered](slice []T) {
31 // Implement generic sorting
32}
33
34func GenericBinarySearch[T constraints.Ordered](slice []T, target T) int {
35 // Implement generic binary search
36}
37
38func GenericFilter[T any](slice []T, predicate func(T) bool) []T {
39 // Implement generic filtering
40}
41
42// TODO: Implement generic map-reduce
43func GenericMap[T, U any](slice []T, mapper func(T) U) []U {
44 // Implement generic mapping
45}
46
47func GenericReduce[T any](slice []T, reducer func(T, T) T, initial T) T {
48 // Implement generic reduction
49}
50
51// TODO: Implement generic data processor
52type DataProcessor[T any] struct {
53 // Add processor implementation
54}
55
56// TODO: Implement generic cache
57type Cache[K comparable, V any] struct {
58 // Add cache implementation
59}
60
61// TODO: Implement generic pool
62type Pool[T any] struct {
63 // Add pool implementation
64}
65
66// Example data types for testing
67type Product struct {
68 ID int
69 Name string
70 Price float64
71}
72
73type Person struct {
74 ID int
75 Name string
76 Age int
77}
78
79// Custom constraints
80type Number interface {
81 ~int | ~int64 | ~float64 | ~float32
82}
83
84type Addable interface {
85 Number | string
86}
87
88func main() {
89 // TODO: Demonstrate generic functionality
90}
Tasks
Task 1: Implement Generic Stack
Create a type-safe stack with proper generics:
1type Stack[T any] struct {
2 items []T
3 mutex sync.RWMutex
4}
5
6func NewStack[T any]() *Stack[T] {
7 return &Stack[T]{
8 items: make([]T, 0),
9 }
10}
11
12func Push(item T) {
13 s.mutex.Lock()
14 defer s.mutex.Unlock()
15 s.items = append(s.items, item)
16}
17
18func Pop() {
19 s.mutex.Lock()
20 defer s.mutex.Unlock()
21
22 if len(s.items) == 0 {
23 var zero T
24 return zero, false
25 }
26
27 last := len(s.items) - 1
28 item := s.items[last]
29 s.items = s.items[:last]
30 return item, true
31}
32
33func Peek() {
34 s.mutex.RLock()
35 defer s.mutex.RUnlock()
36
37 if len(s.items) == 0 {
38 var zero T
39 return zero, false
40 }
41
42 return s.items[len(s.items)-1], true
43}
44
45func IsEmpty() bool {
46 s.mutex.RLock()
47 defer s.mutex.RUnlock()
48 return len(s.items) == 0
49}
50
51func Size() int {
52 s.mutex.RLock()
53 defer s.mutex.RUnlock()
54 return len(s.items)
55}
56
57func Clear() {
58 s.mutex.Lock()
59 defer s.mutex.Unlock()
60 s.items = s.items[:0]
61}
62
63func ToSlice() []T {
64 s.mutex.RLock()
65 defer s.mutex.RUnlock()
66
67 result := make([]T, len(s.items))
68 copy(result, s.items)
69 return result
70}
Task 2: Implement Generic Queue with Priority Support
Create a queue that supports both FIFO and priority queue operations:
1type QueueItem[T any] struct {
2 Value T
3 Priority int
4 Timestamp time.Time
5}
6
7type PriorityQueue[T any] struct {
8 items []QueueItem[T]
9 mutex sync.RWMutex
10}
11
12func NewPriorityQueue[T any]() *PriorityQueue[T] {
13 return &PriorityQueue[T]{
14 items: make([]QueueItem[T], 0),
15 }
16}
17
18func Enqueue(value T, priority int) {
19 pq.mutex.Lock()
20 defer pq.mutex.Unlock()
21
22 item := QueueItem[T]{
23 Value: value,
24 Priority: priority,
25 Timestamp: time.Now(),
26 }
27
28 // Insert while maintaining priority order
29 inserted := false
30 for i, existing := range pq.items {
31 if priority > existing.Priority {
32 pq.items = append(pq.items[:i], append([]QueueItem[T]{item}, pq.items[i:]...)...)
33 inserted = true
34 break
35 }
36 }
37
38 if !inserted {
39 pq.items = append(pq.items, item)
40 }
41}
42
43func Dequeue() {
44 pq.mutex.Lock()
45 defer pq.mutex.Unlock()
46
47 if len(pq.items) == 0 {
48 var zero T
49 return zero, false
50 }
51
52 item := pq.items[0]
53 pq.items = pq.items[1:]
54 return item.Value, true
55}
56
57func DequeueByPriority(priority int) {
58 pq.mutex.Lock()
59 defer pq.mutex.Unlock()
60
61 for i, item := range pq.items {
62 if item.Priority == priority {
63 pq.items = append(pq.items[:i], pq.items[i+1:]...)
64 return item.Value, true
65 }
66 }
67
68 var zero T
69 return zero, false
70}
Task 3: Implement Generic Binary Search Tree
Create a type-safe BST with ordered constraints:
1type BSTNode[T constraints.Ordered] struct {
2 Value T
3 Left *BSTNode[T]
4 Right *BSTNode[T]
5}
6
7type BST[T constraints.Ordered] struct {
8 root *BSTNode[T]
9 count int
10 mutex sync.RWMutex
11}
12
13func NewBST[T constraints.Ordered]() *BST[T] {
14 return &BST[T]{}
15}
16
17func Insert(value T) {
18 bst.mutex.Lock()
19 defer bst.mutex.Unlock()
20
21 bst.root = bst.insertRecursive(bst.root, value)
22 bst.count++
23}
24
25func insertRecursive(node *BSTNode[T], value T) *BSTNode[T] {
26 if node == nil {
27 return &BSTNode[T]{Value: value}
28 }
29
30 if value < node.Value {
31 node.Left = bst.insertRecursive(node.Left, value)
32 } else if value > node.Value {
33 node.Right = bst.insertRecursive(node.Right, value)
34 }
35
36 return node
37}
38
39func Search(value T) bool {
40 bst.mutex.RLock()
41 defer bst.mutex.RUnlock()
42
43 return bst.searchRecursive(bst.root, value)
44}
45
46func searchRecursive(node *BSTNode[T], value T) bool {
47 if node == nil {
48 return false
49 }
50
51 if value == node.Value {
52 return true
53 } else if value < node.Value {
54 return bst.searchRecursive(node.Left, value)
55 } else {
56 return bst.searchRecursive(node.Right, value)
57 }
58}
59
60func InOrderTraversal() []T {
61 bst.mutex.RLock()
62 defer bst.mutex.RUnlock()
63
64 result := make([]T, 0, bst.count)
65 bst.inOrderRecursive(bst.root, &result)
66 return result
67}
68
69func inOrderRecursive(node *BSTNode[T], result *[]T) {
70 if node == nil {
71 return
72 }
73
74 bst.inOrderRecursive(node.Left, result)
75 *result = append(*result, node.Value)
76 bst.inOrderRecursive(node.Right, result)
77}
78
79func Min() {
80 bst.mutex.RLock()
81 defer bst.mutex.RUnlock()
82
83 if bst.root == nil {
84 var zero T
85 return zero, false
86 }
87
88 current := bst.root
89 for current.Left != nil {
90 current = current.Left
91 }
92
93 return current.Value, true
94}
95
96func Max() {
97 bst.mutex.RLock()
98 defer bst.mutex.RUnlock()
99
100 if bst.root == nil {
101 var zero T
102 return zero, false
103 }
104
105 current := bst.root
106 for current.Right != nil {
107 current = current.Right
108 }
109
110 return current.Value, true
111}
Task 4: Implement Generic Algorithms
Create reusable generic algorithms:
1// Generic sorting with multiple algorithms
2type SortAlgorithm int
3
4const (
5 BubbleSort SortAlgorithm = iota
6 QuickSort
7 MergeSort
8)
9
10func GenericSort[T constraints.Ordered](slice []T, algorithm SortAlgorithm) {
11 switch algorithm {
12 case BubbleSort:
13 bubbleSort(slice)
14 case QuickSort:
15 quickSort(slice)
16 case MergeSort:
17 mergeSort(slice)
18 }
19}
20
21func bubbleSort[T constraints.Ordered](slice []T) {
22 n := len(slice)
23 for i := 0; i < n-1; i++ {
24 for j := 0; j < n-i-1; j++ {
25 if slice[j] > slice[j+1] {
26 slice[j], slice[j+1] = slice[j+1], slice[j]
27 }
28 }
29 }
30}
31
32func quickSort[T constraints.Ordered](slice []T) {
33 if len(slice) < 2 {
34 return
35 }
36
37 left, right := 0, len(slice)-1
38 pivot := len(slice) / 2
39
40 slice[pivot], slice[right] = slice[right], slice[pivot]
41
42 for i := left; i < right; i++ {
43 if slice[i] < slice[right] {
44 slice[left], slice[i] = slice[i], slice[left]
45 left++
46 }
47 }
48
49 slice[left], slice[right] = slice[right], slice[left]
50
51 quickSort(slice[:left])
52 quickSort(slice[left+1:])
53}
54
55// Generic binary search
56func GenericBinarySearch[T constraints.Ordered](slice []T, target T) int {
57 left, right := 0, len(slice)-1
58
59 for left <= right {
60 mid := left +/2
61
62 if slice[mid] == target {
63 return mid
64 } else if slice[mid] < target {
65 left = mid + 1
66 } else {
67 right = mid - 1
68 }
69 }
70
71 return -1
72}
73
74// Generic filter with multiple predicate types
75func GenericFilter[T any](slice []T, predicate func(T) bool) []T {
76 result := make([]T, 0)
77 for _, item := range slice {
78 if predicate(item) {
79 result = append(result, item)
80 }
81 }
82 return result
83}
84
85// Generic map
86func GenericMap[T, U any](slice []T, mapper func(T) U) []U {
87 result := make([]U, len(slice))
88 for i, item := range slice {
89 result[i] = mapper(item)
90 }
91 return result
92}
93
94// Generic reduce
95func GenericReduce[T any](slice []T, reducer func(T, T) T, initial T) T {
96 if len(slice) == 0 {
97 return initial
98 }
99
100 result := initial
101 for _, item := range slice {
102 result = reducer(result, item)
103 }
104 return result
105}
106
107// Generic group by
108func GenericGroupBy[T any, K comparable](slice []T, keyFunc func(T) K) map[K][]T {
109 result := make(map[K][]T)
110 for _, item := range slice {
111 key := keyFunc(item)
112 result[key] = append(result[key], item)
113 }
114 return result
115}
116
117// Generic unique
118func GenericUnique[T comparable](slice []T) []T {
119 seen := make(map[T]bool)
120 result := make([]T, 0)
121
122 for _, item := range slice {
123 if !seen[item] {
124 seen[item] = true
125 result = append(result, item)
126 }
127 }
128
129 return result
130}
131
132// Generic intersection
133func GenericIntersection[T comparable](slice1, slice2 []T) []T {
134 set1 := make(map[T]bool)
135 for _, item := range slice1 {
136 set1[item] = true
137 }
138
139 result := make([]T, 0)
140 for _, item := range slice2 {
141 if set1[item] {
142 result = append(result, item)
143 }
144 }
145
146 return GenericUnique(result)
147}
Task 5: Implement Generic Cache with Multiple Eviction Policies
Create a thread-safe generic cache:
1type EvictionPolicy int
2
3const (
4 LRU EvictionPolicy = iota
5 LFU
6 FIFO
7)
8
9type CacheItem[K comparable, V any] struct {
10 Key K
11 Value V
12 AccessCount int
13 LastAccess time.Time
14 CreatedAt time.Time
15}
16
17type Cache[K comparable, V any] struct {
18 items map[K]*CacheItem[K, V]
19 accessOrder []K // For LRU
20 maxSize int
21 policy EvictionPolicy
22 mutex sync.RWMutex
23}
24
25func NewCache[K comparable, V any](maxSize int, policy EvictionPolicy) *Cache[K, V] {
26 return &Cache[K, V]{
27 items: make(map[K]*CacheItem[K, V]),
28 accessOrder: make([]K, 0),
29 maxSize: maxSize,
30 policy: policy,
31 }
32}
33
34func Set(key K, value V) {
35 c.mutex.Lock()
36 defer c.mutex.Unlock()
37
38 if item, exists := c.items[key]; exists {
39 // Update existing item
40 item.Value = value
41 item.AccessCount++
42 item.LastAccess = time.Now()
43 c.updateAccessOrder(key)
44 return
45 }
46
47 // Add new item
48 item := &CacheItem[K, V]{
49 Key: key,
50 Value: value,
51 AccessCount: 1,
52 LastAccess: time.Now(),
53 CreatedAt: time.Now(),
54 }
55
56 c.items[key] = item
57 c.accessOrder = append(c.accessOrder, key)
58
59 // Check if eviction is needed
60 if len(c.items) > c.maxSize {
61 c.evict()
62 }
63}
64
65func Get(key K) {
66 c.mutex.Lock()
67 defer c.mutex.Unlock()
68
69 item, exists := c.items[key]
70 if !exists {
71 var zero V
72 return zero, false
73 }
74
75 item.AccessCount++
76 item.LastAccess = time.Now()
77 c.updateAccessOrder(key)
78
79 return item.Value, true
80}
81
82func updateAccessOrder(key K) {
83 switch c.policy {
84 case LRU:
85 // Move key to end
86 for i, k := range c.accessOrder {
87 if k == key {
88 c.accessOrder = append(c.accessOrder[:i], c.accessOrder[i+1:]...)
89 c.accessOrder = append(c.accessOrder, key)
90 break
91 }
92 }
93 }
94}
95
96func evict() {
97 var keyToEvict K
98
99 switch c.policy {
100 case LRU:
101 // Remove least recently used
102 if len(c.accessOrder) > 0 {
103 keyToEvict = c.accessOrder[0]
104 c.accessOrder = c.accessOrder[1:]
105 }
106 case LFU:
107 // Remove least frequently used
108 minCount := math.MaxInt32
109 for key, item := range c.items {
110 if item.AccessCount < minCount {
111 minCount = item.AccessCount
112 keyToEvict = key
113 }
114 }
115 case FIFO:
116 // Remove oldest item
117 oldestTime := time.Now()
118 for key, item := range c.items {
119 if item.CreatedAt.Before(oldestTime) {
120 oldestTime = item.CreatedAt
121 keyToEvict = key
122 }
123 }
124 }
125
126 if keyToEvict != {
127 delete(c.items, keyToEvict)
128 }
129}
130
131func Delete(key K) bool {
132 c.mutex.Lock()
133 defer c.mutex.Unlock()
134
135 if _, exists := c.items[key]; !exists {
136 return false
137 }
138
139 delete(c.items, key)
140
141 // Remove from access order
142 for i, k := range c.accessOrder {
143 if k == key {
144 c.accessOrder = append(c.accessOrder[:i], c.accessOrder[i+1:]...)
145 break
146 }
147 }
148
149 return true
150}
151
152func Clear() {
153 c.mutex.Lock()
154 defer c.mutex.Unlock()
155
156 c.items = make(map[K]*CacheItem[K, V])
157 c.accessOrder = make([]K, 0)
158}
159
160func Size() int {
161 c.mutex.RLock()
162 defer c.mutex.RUnlock()
163 return len(c.items)
164}
165
166func Keys() []K {
167 c.mutex.RLock()
168 defer c.mutex.RUnlock()
169
170 keys := make([]K, 0, len(c.items))
171 for key := range c.items {
172 keys = append(keys, key)
173 }
174
175 return keys
176}
Solution Approach
Click to see detailed solution
Complete Implementation with Examples:
1package main
2
3import (
4 "fmt"
5 "math"
6 "sort"
7 "sync"
8 "time"
9)
10
11// Implement all the generic structures and algorithms from the tasks above
12// ...
13
14// Example usage and demonstration
15func main() {
16 fmt.Println("=== Generic Stack Demo ===")
17 stack := NewStack[int]()
18 stack.Push(1)
19 stack.Push(2)
20 stack.Push(3)
21
22 for !stack.IsEmpty() {
23 if item, ok := stack.Pop(); ok {
24 fmt.Printf("Popped: %d\n", item)
25 }
26 }
27
28 fmt.Println("\n=== Generic Queue Demo ===")
29 queue := NewPriorityQueue[string]()
30 queue.Enqueue("Low priority task", 1)
31 queue.Enqueue("High priority task", 10)
32 queue.Enqueue("Medium priority task", 5)
33
34 for !queue.IsEmpty() {
35 if item, ok := queue.Dequeue(); ok {
36 fmt.Printf("Dequeued: %s\n", item)
37 }
38 }
39
40 fmt.Println("\n=== Generic BST Demo ===")
41 bst := NewBST[int]()
42 values := []int{5, 3, 7, 2, 4, 6, 8}
43 for _, v := range values {
44 bst.Insert(v)
45 }
46
47 fmt.Printf("In-order traversal: %v\n", bst.InOrderTraversal())
48 fmt.Printf("Search 4: %t\n", bst.Search(4))
49 fmt.Printf("Search 9: %t\n", bst.Search(9))
50
51 fmt.Println("\n=== Generic Algorithms Demo ===")
52 numbers := []int{64, 34, 25, 12, 22, 11, 90}
53 fmt.Printf("Original: %v\n", numbers)
54
55 GenericSort(numbers, QuickSort)
56 fmt.Printf("Sorted: %v\n", numbers)
57
58 fmt.Printf("Binary search 25: index %d\n", GenericBinarySearch(numbers, 25))
59
60 even := GenericFilter(numbers, func(n int) bool { return n%2 == 0 })
61 fmt.Printf("Even numbers: %v\n", even)
62
63 squared := GenericMap(numbers, func(n int) int { return n * n })
64 fmt.Printf("Squared: %v\n", squared)
65
66 sum := GenericReduce(numbers, func(a, b int) int { return a + b }, 0)
67 fmt.Printf("Sum: %d\n", sum)
68
69 fmt.Println("\n=== Generic Cache Demo ===")
70 cache := NewCache[string, int](3, LRU)
71 cache.Set("a", 1)
72 cache.Set("b", 2)
73 cache.Set("c", 3)
74
75 if value, ok := cache.Get("a"); ok {
76 fmt.Printf("Cache hit 'a': %d\n", value)
77 }
78
79 cache.Set("d", 4) // Should evict "b"
80
81 if _, ok := cache.Get("b"); ok {
82 fmt.Println("Cache hit 'b': unexpected")
83 } else {
84 fmt.Println("Cache miss 'b': expected")
85 }
86
87 fmt.Println("\n=== Complex Generic Types Demo ===")
88 type Product struct {
89 ID int
90 Name string
91 Price float64
92 }
93
94 products := []Product{
95 {ID: 1, Name: "Laptop", Price: 999.99},
96 {ID: 2, Name: "Mouse", Price: 29.99},
97 {ID: 3, Name: "Keyboard", Price: 79.99},
98 }
99
100 // Filter expensive products
101 expensive := GenericFilter(products, func(p Product) bool {
102 return p.Price > 50
103 })
104 fmt.Printf("Expensive products: %v\n", expensive)
105
106 // Group by price range
107 grouped := GenericGroupBy(products, func(p Product) string {
108 if p.Price < 50 {
109 return "cheap"
110 } else if p.Price < 100 {
111 return "moderate"
112 }
113 return "expensive"
114 })
115 for category, items := range grouped {
116 fmt.Printf("Category %s: %v\n", category, items)
117 }
118}
Testing Your Implementation
1. Basic Functionality Tests
1func TestGenericStack(t *testing.T) {
2 stack := NewStack[string]()
3
4 stack.Push("hello")
5 stack.Push("world")
6
7 assert.Equal(t, 2, stack.Size())
8
9 item, ok := stack.Pop()
10 assert.True(t, ok)
11 assert.Equal(t, "world", item)
12
13 item, ok = stack.Peek()
14 assert.True(t, ok)
15 assert.Equal(t, "hello", item)
16
17 assert.False(t, stack.IsEmpty())
18
19 stack.Pop()
20 assert.True(t, stack.IsEmpty())
21}
22
23func TestGenericSort(t *testing.T) {
24 // Test with integers
25 ints := []int{3, 1, 4, 1, 5, 9}
26 GenericSort(ints, QuickSort)
27 assert.True(t, sort.IntsAreSorted(ints))
28
29 // Test with strings
30 strings := []string{"banana", "apple", "cherry"}
31 GenericSort(strings, QuickSort)
32 assert.True(t, sort.StringsAreSorted(strings))
33
34 // Test with custom struct
35 type Person struct {
36 Name string
37 Age int
38 }
39
40 people := []Person{
41 {"Alice", 30},
42 {"Bob", 25},
43 {"Charlie", 35},
44 }
45
46 GenericSort(people, QuickSort)
47 for i := 1; i < len(people); i++ {
48 assert.LessOrEqual(t, people[i-1].Age, people[i].Age)
49 }
50}
2. Performance Tests
1func BenchmarkGenericSort(b *testing.B) {
2 sizes := []int{100, 1000, 10000}
3
4 for _, size := range sizes {
5 b.Run(fmt.Sprintf("size_%d", size), func(b *testing.B) {
6 data := make([]int, size)
7 for i := range data {
8 data[i] = rand.Intn(size)
9 }
10
11 b.ResetTimer()
12 for i := 0; i < b.N; i++ {
13 testData := make([]int, len(data))
14 copy(testData, data)
15 GenericSort(testData, QuickSort)
16 }
17 })
18 }
19}
20
21func BenchmarkCacheOperations(b *testing.B) {
22 cache := NewCache[int, string](1000, LRU)
23
24 b.Run("Set", func(b *testing.B) {
25 for i := 0; i < b.N; i++ {
26 cache.Set(i%100, fmt.Sprintf("value_%d", i))
27 }
28 })
29
30 b.Run("Get", func(b *testing.B) {
31 for i := 0; i < b.N; i++ {
32 cache.Get(i % 100)
33 }
34 })
35}
3. Type Safety Tests
1// Test that generics provide compile-time type safety
2func TestTypeSafety() {
3 // These should compile without issues
4 intStack := NewStack[int]()
5 stringStack := NewStack[string]()
6 productStack := NewStack[Product]()
7
8 intStack.Push(42)
9 stringStack.Push("hello")
10 productStack.Push(Product{ID: 1, Name: "Test", Price: 99.99})
11
12 // These would cause compile-time errors:
13 // intStack.Push("string") // Compile error!
14 // stringStack.Push(42) // Compile error!
15}
16
17// Test constraints
18func TestConstraints() {
19 // This works because int is Ordered
20 intBst := NewBST[int]()
21 intBst.Insert(42)
22
23 // This works because string is Ordered
24 stringBst := NewBST[string]()
25 stringBst.Insert("hello")
26
27 // This would cause compile-time error:
28 // productBst := NewBST[Product]() // Product doesn't satisfy Ordered constraint
29}
Extension Challenges
- Add more data structures - Implement generic HashMap, LinkedList, Graph
- Add generic algorithms - Implement more sorting algorithms, search algorithms
- Add functional programming utilities - Implement generic Option, Either types
- Add generic builders - Create type-safe builder patterns
- Add serialization - Implement generic JSON/binary serialization
Key Takeaways
- Generics eliminate code duplication while maintaining type safety
- Constraints limit generic types to ensure operations are valid
- Type parameters make APIs more expressive and flexible
- Generic algorithms work with any type that satisfies constraints
- Performance is comparable to hand-written specific implementations
- Compile-time safety catches type errors before runtime
- Reusability is significantly improved with well-designed generics
This exercise demonstrates how to effectively use Go generics to build type-safe, reusable libraries and utilities that work across different data types while maintaining excellent performance and compile-time safety.