CODEWITHSUNDEEP
gocode-structure
sschmeck
sschmeck

Reputation: 7715

How to organize Go code in packages

I'm trying to implement the union find algorithm using Go. I want to implement different strategies like quick find, quick union and weighted quick union using one structure UnionFind see below. I put the code into a package unionfind

package unionfind

type Unionfind struct {
    elements []int
}

func makeUnionfind(n int) Unionfind {
    elements := make([]int, n)
    for idx := range elements {
        elements[idx] = idx
    }
    return Unionfind{elements}
}

Next I create the functions for the different strategies starting with quick find. The example below isn't working. But I have no idea where to put the strategy specific code, how to name the package and how to import the common structure type.

// create a separate package for each strategy?
package quickfind

// import the structure locally?
import ufp "./unionfind"

// prefer methods over functions for convenience?
func (uf *ufp.Unionfind) union(a int, b int) {
    aroot := uf.elements[a]
    broot := uf.elements[b]
    for k, v := range uf.elements {
        if v == aroot {
            uf.elements[k] = broot
        }
    }
}

func (uf *ufp.Unionfind) connected(a int, b int) bool {
    return uf.elements[a] == uf.elements[b]
}

How should I organize my code the get the quick find algorithm working but have the UnionFindstructure separated?

Upvotes: 0

Views: 747

Answers (3)

kostya
kostya

Reputation: 9569

You won't be able to use the same struct for all union find implementations. For example weighted quick union requires array of tree sizes in addition to the elements.

What you are trying to achieve here is to have the same operations implemented differently. This is what interfaces are for in Go.

Additionally using aliases for package imports to save a few key strokes is not a good practice. Instead it is better to come up with good names such as package name together with its interace/struct/function names makes sense.

I would organize all algorithms in one package with the following structure:

package algorithms

type UnionFind interface {
    Union(a int, b int)
    Connected(a int, b int) bool
}

func QuickFind(n int) UnionFind {
    return &quickFind{......}
}

func QuickUnion(n int) UnionFind {
    return &quickUnion{......}
}

type quickUnion struct {
    ....
}

func (qu *quickUnion) Union(a int, b int) {
    ...
}

func (qu *quickUnion) Connected(a int, b int) bool {
    ...
}

type quickFind struct {
    ....
}

func (qf *quickFind) Union(a int, b int) {
    ...
}

func (qf *quickFind) Connected(a int, b int) bool {
    ...
}

Upvotes: 1

sschmeck
sschmeck

Reputation: 7715

I adapted my code to get a working solution.

  • provide a library/package unionfind for the common type Unionfind
  • put the quick find algorithm into its own package 'quickfind' with its own folder
  • import the unionfind the default way using the GOPATH
  • replace the methods by functions

The first file is algorithms/unionfind/unionfindtype.go.

package unionfind

type Unionfind struct {
    Elements []int
}

func MakeUnionfind(n int) Unionfind {
    elements := make([]int, n)
    for idx := range elements {
        elements[idx] = idx
    }
    return Unionfind{elements}
}

The second file is algorithms/unionfind/quickfind/quickfind.go.

package quickfind

import ufp "algorithms/unionfind"

func union(uf *ufp.Unionfind, a int, b int) {
    aroot := uf.Elements[a]
    broot := uf.Elements[b]
    for k, v := range uf.Elements {
        if v == aroot {
            uf.Elements[k] = broot
        }
    }
}

func connected(uf *ufp.Unionfind, a int, b int) bool {
    return uf.Elements[a] == uf.Elements[b]
}

Thanks to JimB and fl0cke for the suggestions.

Upvotes: 0

peterSO
peterSO

Reputation: 166825

The first thing to do is to explain your problem clearly. For example,

I want to implement several alternative union-find algorithms in Go. For example, quick-fund, quick-union, weighted QU, path compression, and weighted + path. See Union-Find Algorithms, Princeton University and Chapter one of Algorithms in Java by Sedgwick.

An analog might be the Go crypto package which implements many alternative cryptographic hash functions.

Upvotes: 3

Related Questions