How to organize Go code in packages

Question

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?

Are you certain these are the saved versions of the source files? That error suggests that the `quickfind.go` file says `package quickfind` (actually, it looks like you pasted the same file twice. What is quickfind.go?) — JimB, Feb 15 '16 at 20:29
@JimB Thanks, I copied the first file two times. Now it should be correct. — sschmeck, Feb 15 '16 at 20:34
You can't have two packages in the same folder. Please read https://golang.org/doc/code.html — fl0cke, Feb 15 '16 at 20:43
also http://stackoverflow.com/questions/9985559/organizing-a-multiple-file-go-project if it helps — JimB, Feb 15 '16 at 20:48
@fl0cke Ok. How can I reorganize my code? Just moving the files into subfolders results in other errors. — sschmeck, Feb 15 '16 at 20:55
@JimB My problem is that I want to separate the `struct` from the functions but have no idea how the Go way is to achieve this. After the quick find I plan to create a _quick union_ and a _weighted quick union_ algorithm all using the same `struct`. — sschmeck, Feb 15 '16 at 20:59
@sschmeck: the full answer your question is to read the documentation at [How to Write Go Code](https://golang.org/doc/code.html), linked here and in both duplicate answers. The direct answer to your error is the same as those others, you can't have multiple package declarations in a single directory. The other issue you have is that you can't define methods on a type from another package . The method set is part of the type, and types are defined within a "package". (you also have a relative import which should never be used) — JimB, Feb 15 '16 at 21:07
@JimB This means that it's impossible to share a `struct` over several _union find_ implementations or methods. But how do you share structures in Go? — sschmeck, Feb 15 '16 at 21:11
@sschmeck I would suggest starting with a simpler program & reading some tutorials. The comment section of a closed question is not the best place for this kind of advice. Here is list of go books https://github.com/dariubs/GoBooks — fl0cke, Feb 15 '16 at 21:19
@sschmeck: I don't understand the question (since you already know you can export types). By share, do you mean modify? Go is a statically typed language, you can't directly extend an imported type. You can implement interfaces locally in your package, for example, see the [sort package](https://golang.org/pkg/sort/), or how the crypto hash functions all return a [`hash.Hash`](https://golang.org/pkg/hash/#Hash) interface. (You might want to visit a forum better suited for a conversation, like the mailing list.) — JimB, Feb 15 '16 at 21:28
@fl0cke I read the free Introduction book and parts of the Phrasebook. But I've no idea how to structure code. The hello example using a stringutil library seems so heavy weight to me. Is this the Go way of separating code? — sschmeck, Feb 15 '16 at 21:31

peterSO · Answer 1 · 2016-02-15T22:20:45.923

3

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.

edited Feb 15 '16 at 22:20

answered Feb 15 '16 at 21:52

peterSO

158,998
31
281
276

1

How do you know that I'm reading Sedgewick ;-) Thanks for the link. BTW: I assumed that the algorithm is less important than the fact that I want a structure to use in different ways. – sschmeck Feb 15 '16 at 22:25

kostya · Accepted Answer · 2016-02-16T03:18:29.497

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 {
    ...
}

I implemented your approach. You can use the `Unionfind struct` as _embedded type_ if necessary. The main benefit for a single package was that you can share functions without exporting them. — sschmeck, Mar 02 '16 at 10:59

score 0 · Answer 3 · answered Feb 15 '16 at 22:21

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.

How to organize Go code in packages

3 Answers3