Idiomatic/Proper Go code refactoring for a UnionFind library

Question

I am practicing a classic algorithm problem in go "number of islands". I want to solve it using unionfind. Although I can tweak and make it work, I would like to know the best way to structure my code.

Here is the main program.

package main

import (
  "fmt"

  u "practice/leetcode/library/unionfind"
)

type point u.Point

func numIslands(grid [][]byte) int {
  res := 0
  if grid == nil || grid[0] == nil {
    return res
  }
  m := len(grid)
  n := len(grid[0])
  num := 0
  uf := u.NewUnionFind()
  directions := []point{
    point{1, 0}, 
    point{-1, 0},
    point{0, 1},
    point{0, -1},
  }
  emptyPoint := point{}
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == 1 {
        p := point{i, j}
        uf.Add(p)
        num++
        for _, v := range directions {
          newx := i + v.X 
          newy := j + v.Y
          if 0 <= newx && newx < m && 0 <= newy && newy < n && grid[newx][newy] == 1 {
            newp := point{newx, newy}
            if uf.Find(newp) == emptyPoint {
              continue
            }
            uf.Union(p, newp)
            num--
          }
        }
      }
    }
  }
  return num
}

func main() {
  // expect 1
  grid := [][]byte {
    {1,1,1,1,0},
    {1,1,0,1,0},
    {1,1,0,0,0},
    {0,0,0,0,0},
  }
  fmt.Println(numIslands(grid))
  
  // expect 2
  grid = [][]byte {
    {1,0},
    {0,1},
  }
  fmt.Println(numIslands(grid))
}

Here is the unionfind library I wrote

package unionfind

type Point struct {
  X int
  Y int
}

type UnionFind struct {
  parent map[Point]Point
}

func NewUnionFind() *UnionFind {
  parent := make(map[Point]Point)
  return &UnionFind{parent}
}

func (uf *UnionFind) Add(c Point) {
  if _, ok := uf.parent[c]; ok {
    return
  }
  uf.parent[c] = c
}

func (uf *UnionFind) Find(c Point) Point {
  if p, ok := uf.parent[c]; ok {
    if p != c {
      uf.parent[c] = uf.Find(p)
    }
    return uf.parent[c]
  }
  return Point{}
}

func (uf *UnionFind) Union(c1 Point, c2 Point) {
  p1 := uf.Find(c1)
  p2 := uf.Find(c2)
  if p1 != p2 {
    uf.parent[p1] = p2
  }
}

The problem is when I ran the main program, i got the following errors:

# command-line-arguments
./200_number_of_islands_uf.go:31:15: cannot use p (type point) as type unionfind.Point in argument to uf.Add
./200_number_of_islands_uf.go:38:23: cannot use newp (type point) as type unionfind.Point in argument to uf.Find
./200_number_of_islands_uf.go:38:30: invalid operation: uf.Find(newp) == emptyPoint (mismatched types unionfind.Point and point)
./200_number_of_islands_uf.go:41:21: cannot use p (type point) as type unionfind.Point in argument to uf.Union
./200_number_of_islands_uf.go:41:21: cannot use newp (type point) as type unionfind.Point in argument to uf.Union

The hard requirement I want is: 1.I want to keep the unionfind as a library 2.I need to access the Point struct in the main program

The design requirement I am trying to follow is: I tried to avoid using an interface for the UnionFind parent map since I can foresee only the Point struct get pass in to the library.

My requirements could be wrong. I am open to suggestions to refactor the code and make it more elegant looking.

Answer 1

When you do this:

type point u.Point

then point is not just an aliased name for u.Point which can be used interchangeably - it's an entirely new type, and one which your uniontype package knows nothing about and therefore will not accept.

So just don't do that, and instead directly use the type the uniontype package provides for you. For example, change:

directions := []point{
    point{1, 0}, 
    point{-1, 0},
    point{0, 1},
    point{0, -1},
}
emptyPoint := point{}

to:

directions := []u.Point{
    u.Point{1, 0}, 
    u.Point{-1, 0},
    u.Point{0, 1},
    u.Point{0, -1},
}
emptyPoint := u.Point{}

and so on.