disjoint

Documentation

Overview

Package disjoint implements a "disjoint-set data structure", otherwise known as the "union–find data structure" which is commonly used for type unification, among other things.

You create new elements with the NewElem function, which returns an Elem that has both Union and Find methods available. Each Elem can store some typed data associated with it, and as a result, this uses golang generics.

The Union method merges two elements into the same set. The Find method picks a representative element for that set. Unless you change the contents of a set, and in the steady-state of a set, any elements Find method will always return the same representative element for that set, and so this can be used to build the IsConnected function quite easily.

The Merge and UnsafeMerge functions can be used to run the Union method for two elements, with a way to update the data for the representative element in the set. This is useful if you want to keep track of a representative piece of data for the set, such as the data type of that set if you were using this for type unification.

This package does not attempt to be thread-safe, and as a result, make sure to wrap this with the synchronization primitives of your choosing.

This package was built by examining wikipedia and other sources, and contains some short excerpts from the wikipedia page.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Index

• func IsConnected[T any](elem1, elem2 *Elem[T]) bool
• func Merge[T any](elem1, elem2 *Elem[T], merge func(T, T) (T, error)) error
• func UnsafeMerge[T any](elem1, elem2 *Elem[T], merge func(T, T) (T, error)) error
• type Elem
  • func NewElem[T any]() *Elem[T]
  • func (obj *Elem[T]) Find() *Elem[T]
  • func (obj *Elem[T]) Union(elem *Elem[T])

Functions

func IsConnected

func IsConnected[T any](elem1, elem2 *Elem[T]) bool

IsConnected returns true if the two elements are part of the same set. Since any set must return the same representative element for it, by comparing this value for each element, we can determine if they're connected.

func Merge

func Merge[T any](elem1, elem2 *Elem[T], merge func(T, T) (T, error)) error

Merge is exactly like UnsafeMerge, except it calls Find on each element first so that we merge the Data associated with the representative elements only. This is almost always what you want.

func UnsafeMerge

func UnsafeMerge[T any](elem1, elem2 *Elem[T], merge func(T, T) (T, error)) error

UnsafeMerge runs the Union operation on two elements. Before this happens, it runs a merge function which takes the data from each of those elements and gives it the opportunity to determine what the new resultant data should be. Note that either of the elements passed in might not be the representative element for their sets, so if you want to be sure to use the "already merged" data, then run Find on each element before passing it to this function. To do this automatically, use the regular Merge function instead.

Types

type Elem

type Elem[T any] struct {
	// Data is some data that the user might want to store with this element.
	Data T
	// contains filtered or unexported fields
}

Elem is the "node" or "element" type for objects contained in the set. It has a single Data field which can be used to store some user data.

func NewElem

func NewElem[T any]() *Elem[T]

NewElem creates a new set with one element and returns the sole element (the representative element) of that set.

func (*Elem[T]) Find

func (obj *Elem[T]) Find() *Elem[T]

Find returns the representative element of the set. The same element will always be returned when this is called on any element in that same set. You can use the IsConnected function to determine if two elements are in the same set.

func (*Elem[T]) Union

func (obj *Elem[T]) Union(elem *Elem[T])

Union combines two elements into the same set. If the elements are already part of the same set, then nothing changes.