disjointset_test.gno

  1package disjointset
  2
  3import (
  4	"strings"
  5	"testing"
  6
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10func TestSingletons(t *testing.T) {
 11	d := New(5)
 12	uassert.Equal(t, 5, d.Len())
 13	uassert.Equal(t, 5, d.Groups())
 14	for i := 0; i < 5; i++ {
 15		uassert.Equal(t, i, d.Find(i))
 16		uassert.Equal(t, 1, d.Size(i))
 17	}
 18}
 19
 20func TestUnionAndConnected(t *testing.T) {
 21	d := New(6)
 22	uassert.True(t, d.Union(0, 1))
 23	uassert.True(t, d.Union(1, 2))
 24	uassert.True(t, d.Connected(0, 2))
 25	uassert.False(t, d.Connected(0, 3))
 26	uassert.Equal(t, 4, d.Groups()) // {0,1,2} {3} {4} {5}
 27	uassert.Equal(t, 3, d.Size(0))
 28}
 29
 30// Merging an already-merged pair is a no-op and must not lose a group.
 31func TestUnionIdempotent(t *testing.T) {
 32	d := New(4)
 33	uassert.True(t, d.Union(0, 1))
 34	uassert.False(t, d.Union(0, 1))
 35	uassert.False(t, d.Union(1, 0))
 36	uassert.Equal(t, 3, d.Groups())
 37}
 38
 39func TestOutOfRange(t *testing.T) {
 40	d := New(3)
 41	uassert.Equal(t, -1, d.Find(-1))
 42	uassert.Equal(t, -1, d.Find(3))
 43	uassert.False(t, d.Union(0, 99))
 44	uassert.False(t, d.Union(-1, 0))
 45	uassert.Equal(t, 0, d.Size(99))
 46	// out of range is connected to nothing, not even itself
 47	uassert.False(t, d.Connected(99, 99))
 48	uassert.Equal(t, 3, d.Groups())
 49}
 50
 51// The result must not depend on the order unions were applied.
 52func TestPartitionIsOrderIndependent(t *testing.T) {
 53	a := New(7)
 54	a.Union(0, 1)
 55	a.Union(2, 3)
 56	a.Union(1, 3)
 57	b := New(7)
 58	b.Union(3, 1)
 59	b.Union(2, 3)
 60	b.Union(1, 0)
 61	uassert.Equal(t, render(a.Partition()), render(b.Partition()))
 62	uassert.Equal(t, "0,1,2,3|4|5|6", render(a.Partition()))
 63}
 64
 65// Path compression must not change what the structure means.
 66func TestFindCompressesWithoutChangingGroups(t *testing.T) {
 67	d := New(10)
 68	for i := 0; i < 9; i++ {
 69		d.Union(i, i+1) // a long chain, the worst case for an uncompressed find
 70	}
 71	uassert.Equal(t, 1, d.Groups())
 72	root := d.Find(0)
 73	for i := 0; i < 10; i++ {
 74		uassert.Equal(t, root, d.Find(i))
 75	}
 76	uassert.Equal(t, 10, d.Size(0))
 77	uassert.Equal(t, "0,1,2,3,4,5,6,7,8,9", render(d.Partition()))
 78}
 79
 80func TestEmpty(t *testing.T) {
 81	d := New(0)
 82	uassert.Equal(t, 0, d.Len())
 83	uassert.Equal(t, 0, d.Groups())
 84	uassert.Equal(t, 0, len(d.Partition()))
 85}
 86
 87func TestClamped(t *testing.T) {
 88	uassert.Equal(t, 0, New(-3).Len())
 89	uassert.Equal(t, MaxN, New(MaxN+50).Len())
 90}
 91
 92func render(groups [][]int) string {
 93	parts := []string{}
 94	for _, g := range groups {
 95		nums := []string{}
 96		for _, x := range g {
 97			nums = append(nums, itoa(x))
 98		}
 99		parts = append(parts, strings.Join(nums, ","))
100	}
101	return strings.Join(parts, "|")
102}
103
104func itoa(i int) string {
105	if i == 0 {
106		return "0"
107	}
108	var b []byte
109	for i > 0 {
110		b = append([]byte{byte('0' + i%10)}, b...)
111		i /= 10
112	}
113	return string(b)
114}