lib.bend checks

raw source on the hub · import 0xa7cf27ec43eaf330fae4f6dc71a5f4aa/lib.bend as Lib

UnionFind — functional disjoint-set structure for U32 elements.

The parent map is keyed by the canonical String form of each U32. An absent key denotes a singleton root. Union links one root to the other; find is a structurally terminating, map-preserving walk fueled by the map size.

1 import

import Base

Types

type UnionFind source · line 8 · raw

Data

UF
```
@parent:Map<&2, U32> -> UnionFind
```

Definitions

def UnionFind.empty source · line 11 · raw

UnionFind

def UnionFind.new source · line 14 · raw

UnionFind

def UnionFind.key source · line 17 · raw

@x:U32 -> String

def UnionFind.parent_of source · line 20 · raw

@r:Pair(Map<&2, U32>, U32) -> U32

def UnionFind.find.go source · line 24 · raw

@fuel:Nat -> @+parent:Map<&2, U32> -> @+x:U32 -> U32

def UnionFind.find source · line 32 · raw

@+uf:UnionFind -> @x:U32 -> U32

def UnionFind.union source · line 37 · raw

@uf:UnionFind -> @+x:U32 -> @+y:U32 -> UnionFind

def UnionFind.connected source · line 45 · raw

@+uf:UnionFind -> @x:U32 -> @y:U32 -> Bool