[Go] How to deal with sort and heap (1)

1. Understanding Interface

1-a. What is an interface

Before we take a look at sort and heap packages, we have to understand what Interface is and how it works. We use Interface to maintain flexible code. Instead of relying on concrete implementations, interfaces allow you to work with abstract method sets, enabling you to apply different types that fulfill the same contract.

Let’s say you want to write code that calculates the area of shapes: circle, rectangle and etc. Without the help of interfaces, you have to implement Area function for each types.

For example, without Interface you have to implement the functions as folllowing code.

package main

import (
    "fmt"
)

// Rectangle struct represents a rectangle shape.
type Rectangle struct {
    Width, Height float64
}

// Circle struct represents a circle shape.
type Circle struct {
    Radius float64
}

// Function to calculate the area and perimeter of a rectangle.
func PrintRectangleInfo(r Rectangle) {
    area := r.Width * r.Height
    perimeter := 2 * (r.Width + r.Height)
    fmt.Printf("Rectangle Area: %f\n", area)
    fmt.Printf("Rectangle Perimeter: %f\n", perimeter)
}

// Function to calculate the area and perimeter of a circle.
func PrintCircleInfo(c Circle) {
    area := 3.14 * c.Radius * c.Radius
    perimeter := 2 * 3.14 * c.Radius
    fmt.Printf("Circle Area: %f\n", area)
    fmt.Printf("Circle Perimeter: %f\n", perimeter)
}

func main() {
    r := Rectangle{Width: 3, Height: 4}
    c := Circle{Radius: 5}

    PrintRectangleInfo(r)
    PrintCircleInfo(c)
}

Info functions must be implemented for circle and rectangle. The worse things happens here. When you were to add more types like parallelogram or triangle, you have to implement Info functions for them as well.

However, thanks to Interface, we can only implement Info function only once.

Let’s see an example.

package main

import (
    "fmt"
)

// Shape interface defines the methods that any shape must implement.
type Shape interface {
    Area() float64
    Perimeter() float64
}

// Rectangle struct represents a rectangle shape.
type Rectangle struct {
    Width, Height float64
}

// Implement the Shape interface for Rectangle.
func (r Rectangle) Area() float64 {
    return r.Width * r.Height
}

func (r Rectangle) Perimeter() float64 {
    return 2 * (r.Width + r.Height)
}

// Circle struct represents a circle shape.
type Circle struct {
    Radius float64
}

// Implement the Shape interface for Circle.
func (c Circle) Area() float64 {
    return 3.14 * c.Radius * c.Radius
}

func (c Circle) Perimeter() float64 {
    return 2 * 3.14 * c.Radius
}

// Function to print area and perimeter of any shape.
func PrintShapeInfo(s Shape) {
    fmt.Printf("Area: %f\n", s.Area())
    fmt.Printf("Perimeter: %f\n", s.Perimeter())
}

func main() {
    r := Rectangle{Width: 3, Height: 4}
    c := Circle{Radius: 5}

    PrintShapeInfo(r)
    PrintShapeInfo(c)
}

As you can see the code above, the PrintShapeInfo function is implemented only once.

It is because the parameter of PrintShapeInfo is a type of Shape which is an interface. All the types that fullfill the conditions to be a shape can be a shape and the can be passed to PrintShapeInfo.

If you want to add a Triangle or Parallelogram, nothing happens. Only thing you need to do is fullfilling the condition by implementing signature of Interface.

The signature is simply denoted here.

type Shape interface {
    Area() float64
    Perimeter() float64
}

The types that wants to be a Shape interface, the methods Area and Primeter must be implmented.

1-b. Using an interface

To implement code with interfaces, you need to know some more techniques.

The first one is type assertion.

The type assertion is used to retrieve the dynamic value of an interface variables. In our example, the shape interface can be retrieved back into circle or rectangle.

func PrintAreaAndCheckType(s Shape) {
    fmt.Printf("Area: %f\n", s.Area())

    // Type assertion to recover the concrete type
    if c, ok := s.(Circle); ok {
        fmt.Printf("This is a Circle with radius: %f\n", c.Radius)
    } else if sq, ok := s.(Square); ok {
        fmt.Printf("This is a Square with side length: %f\n", sq.Side)
    } else {
        fmt.Println("Unknown shape type")
    }
}

As the interface is passed as a parameter, we do not know which type it was originally. To retrieve its original type, we have to use assertion like below.

value, ok := interfaceValue.(ConcreteType)

In a type assertion, value is the asserted value, and ok is a boolean indicating success. If ConcreteType is not the original type, ok is set to false. If it is, ok is true, and value holds the original value

Look at line 5 of PrintAreaAndCheckType. The Circle type is asserted and if the assertion succeeds, the funtion will print “This is a Circle with radius: (Radius)“.

Secondly, we have to know type switch.

It allows us to check multiple types and execute different code based on the type of the value stored in the interface.

switch v := interfaceValue.(type) {
case string:
    fmt.Println("String:", v)
case int:
    fmt.Println("Integer:", v)
default:
    fmt.Println("Unknown type")
}

The main difference from a single type assertion is that instead of using ok, the default code block is executed when none of the specified type cases match

The last and most important technique is an empty interface.

The empty interface is a special type that can hold values of any type. This makes it extremly versatile; however, dealing with it requires sophisticated type assertions and type switches.

Let’s see an example.

func describe(i interface{}) {
    fmt.Printf("Type: %T, Value: %v\n", i, i)
}

func main() {
    describe(42)
    describe("Hello")
    describe(true)
}

We can print the type and value of i no matter what type it is, by simply using the empty interface and the format specifier %T.

These traits and techniques are used in several utility packages like sort and heap.

Let’s deep dive into those packages.

2. Leveraging interfaces with sort package

We have seen what interface is and how it works in Go. Now we can dive into practical example.

The sort package is a powerful utility that allows us to sort slices of any type. The magic behind this flexibility lies in the use of interface.

2-a. the sort interface

the sort package provides a way to sort any slices that satisfies the sort interface. The following three methods must be implemented to be sortable.

type Interface interface {
    Len() int          
    Less(i, j int) bool 
    Swap(i, j int)      
}

The sort package already provides a type called sort.IntSlice.

package sort

type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

The methods are already implemented, so we can just pass []int type variable to Sort function. We can use Sort function which is used for various types or just simply Ints function.

package main

import (
    "fmt"
    "sort"
)

func main() {
    nums1 := []int{5, 2, 6, 3, 1, 4}
    nums2 := []int{5, 2, 6, 3, 1, 4}
    // Sort the slice in ascending order
    sort.Sort(sort.IntSlice(nums1))
    sort.Ints(nums2)
    
    // both results are the same.
    fmt.Println("Sorted:", nums1)
    fmt.Println("Sorted:", nums2)
}

2-b. Custom types sorting

How about custum types? How can we implement the required methods to use Sort

Let’s see the example below.

package main

import (
    "fmt"
    "sort"
)

type Named interface {
    GetName() string
}

type Person struct {
    Name string
    Age  int
}

func (p Person) GetName() string {
    return p.Name
}

type ByName []Named

func (a ByName) Len() int           { return len(a) }
func (a ByName) Less(i, j int) bool { return a[i].GetName() < a[j].GetName() }
func (a ByName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
    people := []Named{
        Person{Name: "Charlie", Age: 35},
        Person{Name: "Alice", Age: 30},
        Person{Name: "Bob", Age: 25},
    }

    sort.Sort(ByName(people))

    for _, p := range people {
        fmt.Println(p.GetName())
    }
}

We can sort the custom Person type because it satisfies the sort.Interface through the Named interface. The Named interface is implemented by the Person struct, which allows Person instances to be sorted using the Sort function.

     +---------------------+
     |   Person Struct     |
     |---------------------|
     | Name  string        |
     | Age   int           |
     |---------------------|
     | GetName()           |
     +---------------------+
                |
                v
     +---------------------+
     | Named Interface     |
     |---------------------|
     | GetName()           |
     +---------------------+
                |
                v
     +---------------------+
     |  ByName             |
     | (Alias for []Named) |
     |---------------------|
     | Len()               |
     | Less(i, j int) bool |
     | Swap(i, j int)      |
     +---------------------+
                |
                v
     +---------------------+
     |   sort.Sort(ByName) |
     +---------------------+

This diagram accurately represents the flow where Person implements the Named interface, ByName is a slice of Named types, and sort.Sort is used to sort the ByName slice. This flow demonstrates how interfaces and type aliases in Go work together to create a flexible and powerful sorting mechanism.

3. Conclusion

We have delved into the world of interfaces and the sort package. In the next post, we’ll delve into the heap package and the use of pointer receivers in Go, further demonstrating the power and flexibility of interfaces in building robust and reusable code.

Leave a Reply

Your email address will not be published. Required fields are marked *