unionfind

README

unionfind

a union find sets data structure based on map and list in golang.

Usage

uf := unionfind.New()

uf.Union(1, 2, 3)
fmt.Println(uf.Find(1))    // Prints [1, 2, 3]
fmt.Println(uf.Find(2))    // Prints [1, 2, 3]
fmt.Println(uf.Find(2, 3)) // Prints [1, 2, 3]
fmt.Println(uf.InSameSet(1, 2)) // Prints true
fmt.Println(uf.InSameSet(1, 3)) // Prints true
fmt.Println(uf.InSameSet(2, 3)) // Prints true

uf.Union(4, 5, 6)
fmt.Println(uf.Find(4))    // Prints [4, 5, 6]
fmt.Println(uf.Find(5))    // Prints [4, 5, 6]
fmt.Println(uf.Find(4, 6)) // Prints [4, 5, 6]
fmt.Println(uf.InSameSet(4, 5)) // Prints true
fmt.Println(uf.InSameSet(4, 6)) // Prints true
fmt.Println(uf.InSameSet(5, 6)) // Prints true

fmt.Println(uf.Find(1, 6))      // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.InSameSet(1, 4)) // Prints false
fmt.Println(uf.InSameSet(1, 5)) // Prints false
fmt.Println(uf.InSameSet(2, 6)) // Prints false

uf.Union(2, 6)
fmt.Println(uf.Find(1)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(2)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(3)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(4)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(5)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(1, 6)) // Prints [1, 2, 3, 4, 5, 6]

fmt.Println(uf.InSameSet(1, 4)) // Prints true
fmt.Println(uf.InSameSet(1, 5)) // Prints true
fmt.Println(uf.InSameSet(2, 6)) // Prints true

fmt.Println(uf.RemoveSet(1)) // Prints [1, 2, 3, 4, 5, 6]
fmt.Println(uf.Find(3))      // Prints [ ]

Documentation

Index

• type UnionFindSets
  • func New() UnionFindSets
  • func (ufs UnionFindSets) Distinct(objects ...interface{}) []interface{}
  • func (ufs UnionFindSets) Find(objects ...interface{}) (result []interface{})
  • func (ufs UnionFindSets) InSameSet(a, b interface{}) bool
  • func (ufs UnionFindSets) InSameSetSlice(object interface{}, slice []interface{}) bool
  • func (ufs UnionFindSets) RemoveSet(object interface{}) (result []interface{})
  • func (ufs UnionFindSets) Union(objects ...interface{})

Types

type UnionFindSets

type UnionFindSets map[interface{}]*listPkg.List

UnionFindSets data structure.

func New

func New() UnionFindSets

New return a new UnionFindSets instance.

func (UnionFindSets) Distinct

func (ufs UnionFindSets) Distinct(objects ...interface{}) []interface{}

Distinct removes the duplicate objects in any same set.

func (UnionFindSets) Find

func (ufs UnionFindSets) Find(objects ...interface{}) (result []interface{})

Find all set members of objects, with no duplicates.

func (UnionFindSets) InSameSet

func (ufs UnionFindSets) InSameSet(a, b interface{}) bool

InSameSet check if a and b are in the same set

func (UnionFindSets) InSameSetSlice

func (ufs UnionFindSets) InSameSetSlice(object interface{}, slice []interface{}) bool

InSameSetSlice check if object is in the same set with any member of slice.

func (UnionFindSets) RemoveSet

func (ufs UnionFindSets) RemoveSet(object interface{}) (result []interface{})

RemoveSet remove the set object belongs to. returns the removed set members.

func (UnionFindSets) Union

func (ufs UnionFindSets) Union(objects ...interface{})

Union objects into the same set, including the existing set members of objects