Union-find with union by rank and full path compression: generated algorithm definition
DefinitionAlgo_union_find_GeneratedThe compiled semantics of union_find.algo in the examples/kruskal import root. This bundle contains source-function frames, transition rules and the stable public call/run/output interfaces. Imported modules are linked through the shared execution semantics, including mutable aliases and named tick increments.
These are the algorithm definitions proved about by the corresponding analysis nodes. Named-line observations are in a separate Points bundle, so editing labels does not change the main algorithm statement. The reproduction target is Algo2Lean v0.1.4; raw generated files and platform-adapted packaging are tracked separately, and release/source links must be finalized before submission.
<!-- algo2lean-provenance-v0.1.4 -->Algo2Lean provenance and reproduction. These definitions target Algo2Lean v0.1.4, using the compiler source at public commit 0f79d5e4242e6477531c9ee4410409f5b1c92f76, and Lean 4.33.1. The versioned compiler location is Algo2Lean v0.1.4. Compile all supplied .algo files and imports to reproduce the raw generated definitions. Release publication and exact website parity require their separately recorded checks; this metadata alone does not assert them. Prove2Me imports and declaration packaging are mechanically adapted, with original hashes, compiler-reported source ranges, and adaptations recorded in transplant provenance. Exact reproduction does not prove the compiler correct.
import Definitions.Def_Algo2LeanLib_Modules
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
-- Generated by Algo2Lean 0.1.4 https://github.com/lunjiah/algo2lean
namespace Algo.«union_find»
open _root_.Algo2LeanGenerated
-- Independently compiled module; imported algorithms keep their own transitions.
namespace Algo2LeanGenerated
abbrev Ref_UnionFind := ObjectRef
-- Shallow class membership; fields and referenced objects are observed separately.
def is_UnionFind (h : Heap) (ref : Ref_UnionFind) : Prop :=
ref < h.nextObject ∧ h.objectClass ref = some "union_find.UnionFind"
instance (h : Heap) (ref : Ref_UnionFind) : Decidable (is_UnionFind h ref) :=
inferInstanceAs (Decidable (ref < h.nextObject ∧ h.objectClass ref = some "union_find.UnionFind"))
def field_UnionFind_parent (h : Heap) (ref : Ref_UnionFind) : Option SeqRef :=
if is_UnionFind h ref then (h.readField ref "parent").bind ObjectValue.asSeq else none
def set_UnionFind_parent (h : Heap) (ref : Ref_UnionFind) (value : SeqRef) : Heap :=
h.writeField ref "parent" (ObjectValue.seqValue value)
@[simp] theorem field_UnionFind_parent_set (h : Heap) (ref : Ref_UnionFind) (value : SeqRef)
(valid : is_UnionFind h ref) :
field_UnionFind_parent (set_UnionFind_parent h ref value) ref = some value := by
have valid' : is_UnionFind (set_UnionFind_parent h ref value) ref := by
simpa [set_UnionFind_parent, is_UnionFind] using valid
rw [field_UnionFind_parent, if_pos valid']
unfold set_UnionFind_parent
rw [Heap.readField_writeField_same h ref "parent" _ "union_find.UnionFind" valid.2]
rfl
def field_UnionFind_rank (h : Heap) (ref : Ref_UnionFind) : Option SeqRef :=
if is_UnionFind h ref then (h.readField ref "rank").bind ObjectValue.asSeq else none
def set_UnionFind_rank (h : Heap) (ref : Ref_UnionFind) (value : SeqRef) : Heap :=
h.writeField ref "rank" (ObjectValue.seqValue value)
@[simp] theorem field_UnionFind_rank_set (h : Heap) (ref : Ref_UnionFind) (value : SeqRef)
(valid : is_UnionFind h ref) :
field_UnionFind_rank (set_UnionFind_rank h ref value) ref = some value := by
have valid' : is_UnionFind (set_UnionFind_rank h ref value) ref := by
simpa [set_UnionFind_rank, is_UnionFind] using valid
rw [field_UnionFind_rank, if_pos valid']
unfold set_UnionFind_rank
rw [Heap.readField_writeField_same h ref "rank" _ "union_find.UnionFind" valid.2]
rfl
def field_UnionFind_size (h : Heap) (ref : Ref_UnionFind) : Option Int :=
if is_UnionFind h ref then (h.readField ref "size").bind ObjectValue.asInt else none
def set_UnionFind_size (h : Heap) (ref : Ref_UnionFind) (value : Int) : Heap :=
h.writeField ref "size" (ObjectValue.intValue value)
@[simp] theorem field_UnionFind_size_set (h : Heap) (ref : Ref_UnionFind) (value : Int)
(valid : is_UnionFind h ref) :
field_UnionFind_size (set_UnionFind_size h ref value) ref = some value := by
have valid' : is_UnionFind (set_UnionFind_size h ref value) ref := by
simpa [set_UnionFind_size, is_UnionFind] using valid
rw [field_UnionFind_size, if_pos valid']
unfold set_UnionFind_size
rw [Heap.readField_writeField_same h ref "size" _ "union_find.UnionFind" valid.2]
rfl
/-- Build input data directly; this helper does not execute `__init__`. -/
def create_UnionFind (h : Heap) (value_parent : SeqRef) (value_rank : SeqRef) (value_size : Int) : Heap × Ref_UnionFind :=
let ref := h.nextObject
let h := h.allocateObject "union_find.UnionFind"
let h := set_UnionFind_parent h ref value_parent
let h := set_UnionFind_rank h ref value_rank
let h := set_UnionFind_size h ref value_size
(h, ref)
structure State_UnionFind___init__ where
v0 : Ref_UnionFind := 0 -- self
v1 : Int := 0 -- size
v2 : Int := 0 -- vertex
t3 : Unit := () -- temporary
t4 : Bool := false -- temporary
t5 : SeqRef := 0 -- temporary
t6 : Ref_UnionFind := 0 -- temporary
t7 : Int := 0 -- temporary
t8 : SeqRef := 0 -- temporary
t9 : Ref_UnionFind := 0 -- temporary
t10 : Int := 0 -- temporary
structure State_UnionFind_find where
v0 : Ref_UnionFind := 0 -- self
v1 : Int := 0 -- vertex
v2 : SeqRef := 0 -- parent
v3 : Int := 0 -- root
t4 : Int := 0 -- temporary
t5 : Int := 0 -- temporary
t6 : Ref_UnionFind := 0 -- temporary
t7 : Int := 0 -- temporary
t8 : Bool := false -- temporary
t9 : Int := 0 -- temporary
structure State_UnionFind_union where
v0 : Ref_UnionFind := 0 -- self
v1 : Int := 0 -- a
v2 : Int := 0 -- b
v3 : Int := 0 -- left
v4 : Int := 0 -- right
t5 : Bool := false -- temporary
t6 : Bool := false -- temporary
t7 : Bool := false -- temporary
t8 : Bool := false -- temporary
t9 : Bool := false -- temporary
t10 : Int := 0 -- temporary
t11 : Ref_UnionFind := 0 -- temporary
t12 : Int := 0 -- temporary
t13 : Int := 0 -- temporary
t14 : Ref_UnionFind := 0 -- temporary
t15 : Int := 0 -- temporary
structure State_UnionFind where
v0 : Int := 0 -- size
v1 : Ref_UnionFind := 0 -- _instance
t2 : Ref_UnionFind := 0 -- temporary
t3 : Unit := () -- temporary
t4 : Ref_UnionFind := 0 -- temporary
t5 : Int := 0 -- temporary
t6 : Ref_UnionFind := 0 -- temporary
inductive Frame where
| invalid
| fn_UnionFind___init__ (pc : Nat) (state : State_UnionFind___init__)
| fn_UnionFind_find (pc : Nat) (state : State_UnionFind_find)
| fn_UnionFind_union (pc : Nat) (state : State_UnionFind_union)
| fn_UnionFind (pc : Nat) (state : State_UnionFind)
inductive Result where
| fn_UnionFind___init__ (value : Unit)
| fn_UnionFind_find (value : Int)
| fn_UnionFind_union (value : Bool)
| fn_UnionFind (value : Ref_UnionFind)
abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)
inductive Step : Configuration → Configuration → Prop where
| UnionFind___init___pc1 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind___init__ (s.t3)) stack)
| UnionFind___init___pc2 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 2 s) stack) (.active h (Frame.fn_UnionFind___init__ 1 { s with t3 := () }) stack)
| UnionFind___init___pc3_true (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (condition : s.t4 = true) :
Step (.active h (Frame.fn_UnionFind___init__ 3 s) stack) (.active h (Frame.fn_UnionFind___init__ 7 s) stack)
| UnionFind___init___pc3_false (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (condition : s.t4 = false) :
Step (.active h (Frame.fn_UnionFind___init__ 3 s) stack) (.active h (Frame.fn_UnionFind___init__ 2 s) stack)
| UnionFind___init___pc4 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 4 s) stack) (.active h (Frame.fn_UnionFind___init__ 3 { s with t4 := (decide ((s.v2 < s.v1))) }) stack)
| UnionFind___init___pc5 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 5 s) stack) (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
| UnionFind___init___pc6 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 6 s) stack) (.active h (Frame.fn_UnionFind___init__ 5 { s with v2 := (s.v2 + (1 : Int)) }) stack)
| UnionFind___init___pc7 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind___init__ 7 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v2 s.v2) (Frame.fn_UnionFind___init__ 6 s) stack)
| UnionFind___init___pc8 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 8 s) stack) (.active (h.tick "uf_init" 1) (Frame.fn_UnionFind___init__ 4 s) stack)
| UnionFind___init___pc9 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 9 s) stack) (.active h (Frame.fn_UnionFind___init__ 8 { s with v2 := (0 : Int) }) stack)
| UnionFind___init___pc10 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.v0))) :
Step (.active h (Frame.fn_UnionFind___init__ 10 s) stack) (.active (set_UnionFind_size h (s.v0) (s.v1)) (Frame.fn_UnionFind___init__ 9 s) stack)
| UnionFind___init___pc11 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.t6))) :
Step (.active h (Frame.fn_UnionFind___init__ 11 s) stack) (.active (set_UnionFind_rank h (s.t6) (s.t5)) (Frame.fn_UnionFind___init__ 10 s) stack)
| UnionFind___init___pc12 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 12 s) stack) (.active h (Frame.fn_UnionFind___init__ 11 { s with t6 := s.v0 }) stack)
| UnionFind___init___pc13 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 13 s) stack) (.active (h.allocate (fun _ => s.t7)) (Frame.fn_UnionFind___init__ 12 { s with t5 := h.nextRef }) stack)
| UnionFind___init___pc14 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 14 s) stack) (.active h (Frame.fn_UnionFind___init__ 13 { s with t7 := (0 : Int) }) stack)
| UnionFind___init___pc15 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) (defined : (is_UnionFind h (s.t9))) :
Step (.active h (Frame.fn_UnionFind___init__ 15 s) stack) (.active (set_UnionFind_parent h (s.t9) (s.t8)) (Frame.fn_UnionFind___init__ 14 s) stack)
| UnionFind___init___pc16 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 16 s) stack) (.active h (Frame.fn_UnionFind___init__ 15 { s with t9 := s.v0 }) stack)
| UnionFind___init___pc17 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 17 s) stack) (.active (h.allocate (fun _ => s.t10)) (Frame.fn_UnionFind___init__ 16 { s with t8 := h.nextRef }) stack)
| UnionFind___init___pc18 (h : Heap) (s : State_UnionFind___init__) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind___init__ 18 s) stack) (.active h (Frame.fn_UnionFind___init__ 17 { s with t10 := (0 : Int) }) stack)
| UnionFind_find_pc1 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t4)) stack)
| UnionFind_find_pc2 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 2 s) stack) (.active h (Frame.fn_UnionFind_find 1 { s with t4 := s.v3 }) stack)
| UnionFind_find_pc3 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 3 s) stack) (.active (h.tick "uf_compress" 1) (Frame.fn_UnionFind_find 2 s) stack)
| UnionFind_find_pc4 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : s.v2 < h.nextRef) :
Step (.active h (Frame.fn_UnionFind_find 4 s) stack) (.active (h.write s.v2 s.v1 s.v3) (Frame.fn_UnionFind_find 3 s) stack)
| UnionFind_find_pc5 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 5 s) stack) (.active h (Frame.fn_UnionFind_find 4 { s with v3 := s.t5 }) stack)
| UnionFind_find_pc6 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 6 s) stack) (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t6), v1 := s.t7 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_find 5 { s with t5 := result }) | _ => .invalid) :: stack))
| UnionFind_find_pc7 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (s.v2 < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind_find 7 s) stack) (.active h (Frame.fn_UnionFind_find 6 { s with t7 := (h.read s.v2 s.v1) }) stack)
| UnionFind_find_pc8 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (is_UnionFind h (s.t6))) :
Step (.active h (Frame.fn_UnionFind_find 8 s) stack) (.active h (Frame.fn_UnionFind_find 7 { s with t6 := s.t6 }) stack)
| UnionFind_find_pc9 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 9 s) stack) (.active h (Frame.fn_UnionFind_find 8 { s with t6 := s.v0 }) stack)
| UnionFind_find_pc10 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 10 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_find (s.t9)) stack)
| UnionFind_find_pc11 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 11 s) stack) (.active h (Frame.fn_UnionFind_find 10 { s with t9 := s.v1 }) stack)
| UnionFind_find_pc12_true (h : Heap) (s : State_UnionFind_find) (stack : Stack) (condition : s.t8 = true) :
Step (.active h (Frame.fn_UnionFind_find 12 s) stack) (.active h (Frame.fn_UnionFind_find 11 s) stack)
| UnionFind_find_pc12_false (h : Heap) (s : State_UnionFind_find) (stack : Stack) (condition : s.t8 = false) :
Step (.active h (Frame.fn_UnionFind_find 12 s) stack) (.active h (Frame.fn_UnionFind_find 9 s) stack)
| UnionFind_find_pc13 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : ((s.v2 < h.nextRef))) :
Step (.active h (Frame.fn_UnionFind_find 13 s) stack) (.active h (Frame.fn_UnionFind_find 12 { s with t8 := (decide (((h.read s.v2 s.v1) = s.v1))) }) stack)
| UnionFind_find_pc14 (h : Heap) (s : State_UnionFind_find) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_find 14 s) stack) (.active (h.tick "uf_find" 1) (Frame.fn_UnionFind_find 13 s) stack)
| UnionFind_find_pc15 (h : Heap) (s : State_UnionFind_find) (stack : Stack) (defined : (((field_UnionFind_parent h (s.v0)).isSome = true))) :
Step (.active h (Frame.fn_UnionFind_find 15 s) stack) (.active h (Frame.fn_UnionFind_find 14 { s with v2 := ((field_UnionFind_parent h (s.v0)).getD 0) }) stack)
| UnionFind_union_pc1 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t5)) stack)
| UnionFind_union_pc2 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 2 s) stack) (.active h (Frame.fn_UnionFind_union 1 { s with t5 := true }) stack)
| UnionFind_union_pc3 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind_union 3 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v3 s.v4) (Frame.fn_UnionFind_union 2 s) stack)
| UnionFind_union_pc4 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind_union 4 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 2 s) stack)
| UnionFind_union_pc5 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) ∧ ((((field_UnionFind_rank h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind_union 5 s) stack) (.active (h.write ((field_UnionFind_rank h (s.v0)).getD 0) s.v3 ((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3) + (1 : Int))) (Frame.fn_UnionFind_union 2 s) stack)
| UnionFind_union_pc6 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_parent h (s.v0)).isSome = true)))) ∧ (((field_UnionFind_parent h (s.v0)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_UnionFind_union 6 s) stack) (.active (h.write ((field_UnionFind_parent h (s.v0)).getD 0) s.v4 s.v3) (Frame.fn_UnionFind_union 5 s) stack)
| UnionFind_union_pc7_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t7 = true) :
Step (.active h (Frame.fn_UnionFind_union 7 s) stack) (.active h (Frame.fn_UnionFind_union 4 s) stack)
| UnionFind_union_pc7_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t7 = false) :
Step (.active h (Frame.fn_UnionFind_union 7 s) stack) (.active h (Frame.fn_UnionFind_union 6 s) stack)
| UnionFind_union_pc8 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) :
Step (.active h (Frame.fn_UnionFind_union 8 s) stack) (.active h (Frame.fn_UnionFind_union 7 { s with t7 := (decide (((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v4) < (h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3)))) }) stack)
| UnionFind_union_pc9_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t6 = true) :
Step (.active h (Frame.fn_UnionFind_union 9 s) stack) (.active h (Frame.fn_UnionFind_union 3 s) stack)
| UnionFind_union_pc9_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t6 = false) :
Step (.active h (Frame.fn_UnionFind_union 9 s) stack) (.active h (Frame.fn_UnionFind_union 8 s) stack)
| UnionFind_union_pc10 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (((((field_UnionFind_rank h (s.v0)).isSome = true))) ∧ (((field_UnionFind_rank h (s.v0)).getD 0) < h.nextRef))) :
Step (.active h (Frame.fn_UnionFind_union 10 s) stack) (.active h (Frame.fn_UnionFind_union 9 { s with t6 := (decide (((h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v3) < (h.read ((field_UnionFind_rank h (s.v0)).getD 0) s.v4)))) }) stack)
| UnionFind_union_pc11 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 11 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind_union (s.t9)) stack)
| UnionFind_union_pc12 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 12 s) stack) (.active h (Frame.fn_UnionFind_union 11 { s with t9 := false }) stack)
| UnionFind_union_pc13_true (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t8 = true) :
Step (.active h (Frame.fn_UnionFind_union 13 s) stack) (.active h (Frame.fn_UnionFind_union 12 s) stack)
| UnionFind_union_pc13_false (h : Heap) (s : State_UnionFind_union) (stack : Stack) (condition : s.t8 = false) :
Step (.active h (Frame.fn_UnionFind_union 13 s) stack) (.active h (Frame.fn_UnionFind_union 10 s) stack)
| UnionFind_union_pc14 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 14 s) stack) (.active h (Frame.fn_UnionFind_union 13 { s with t8 := (decide ((s.v3 = s.v4))) }) stack)
| UnionFind_union_pc15 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 15 s) stack) (.active (h.tick "uf_union" 1) (Frame.fn_UnionFind_union 14 s) stack)
| UnionFind_union_pc16 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 16 s) stack) (.active h (Frame.fn_UnionFind_union 15 { s with v4 := s.t10 }) stack)
| UnionFind_union_pc17 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 17 s) stack) (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t11), v1 := s.t12 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_union 16 { s with t10 := result }) | _ => .invalid) :: stack))
| UnionFind_union_pc18 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 18 s) stack) (.active h (Frame.fn_UnionFind_union 17 { s with t12 := s.v2 }) stack)
| UnionFind_union_pc19 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (is_UnionFind h (s.t11))) :
Step (.active h (Frame.fn_UnionFind_union 19 s) stack) (.active h (Frame.fn_UnionFind_union 18 { s with t11 := s.t11 }) stack)
| UnionFind_union_pc20 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 20 s) stack) (.active h (Frame.fn_UnionFind_union 19 { s with t11 := s.v0 }) stack)
| UnionFind_union_pc21 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 21 s) stack) (.active h (Frame.fn_UnionFind_union 20 { s with v3 := s.t13 }) stack)
| UnionFind_union_pc22 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 22 s) stack) (.active h (Frame.fn_UnionFind_find 15 ({ v0 := (s.t14), v1 := s.t15 } : State_UnionFind_find)) ((fun value => match value with | .fn_UnionFind_find result => (Frame.fn_UnionFind_union 21 { s with t13 := result }) | _ => .invalid) :: stack))
| UnionFind_union_pc23 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 23 s) stack) (.active h (Frame.fn_UnionFind_union 22 { s with t15 := s.v1 }) stack)
| UnionFind_union_pc24 (h : Heap) (s : State_UnionFind_union) (stack : Stack) (defined : (is_UnionFind h (s.t14))) :
Step (.active h (Frame.fn_UnionFind_union 24 s) stack) (.active h (Frame.fn_UnionFind_union 23 { s with t14 := s.t14 }) stack)
| UnionFind_union_pc25 (h : Heap) (s : State_UnionFind_union) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind_union 25 s) stack) (.active h (Frame.fn_UnionFind_union 24 { s with t14 := s.v0 }) stack)
| UnionFind_pc1 (h : Heap) (s : State_UnionFind) (stack : Stack) (defined : is_UnionFind h s.t2) :
Step (.active h (Frame.fn_UnionFind 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_UnionFind (s.t2)) stack)
| UnionFind_pc2 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 2 s) stack) (.active h (Frame.fn_UnionFind 1 { s with t2 := s.v1 }) stack)
| UnionFind_pc3 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 3 s) stack) (.active h (Frame.fn_UnionFind___init__ 18 ({ v0 := s.t4, v1 := s.t5 } : State_UnionFind___init__)) ((fun value => match value with | .fn_UnionFind___init__ result => (Frame.fn_UnionFind 2 { s with t3 := result }) | _ => .invalid) :: stack))
| UnionFind_pc4 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 4 s) stack) (.active h (Frame.fn_UnionFind 3 { s with t5 := s.v0 }) stack)
| UnionFind_pc5 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 5 s) stack) (.active h (Frame.fn_UnionFind 4 { s with t4 := s.v1 }) stack)
| UnionFind_pc6 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 6 s) stack) (.active h (Frame.fn_UnionFind 5 { s with v1 := s.t6 }) stack)
| UnionFind_pc7 (h : Heap) (s : State_UnionFind) (stack : Stack) :
Step (.active h (Frame.fn_UnionFind 7 s) stack) (.active (h.allocateObject "union_find.UnionFind") (Frame.fn_UnionFind 6 { s with t6 := h.nextObject }) stack)
theorem terminal (h : Heap) (result : Result) :
Algo2LeanCore.Terminal Step (.done h result) := by
intro next transition
cases transition
end Algo2LeanGenerated
open Algo2LeanGenerated
def entry_UnionFind___init__ (input : Ref_UnionFind × Int) : Frame :=
(Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__))
def UnionFind.__init__.ValidInput (h : Heap) (input : Ref_UnionFind × Int) : Prop := is_UnionFind h input.1
def UnionFind.__init__.initial (h : Heap) (input : Ref_UnionFind × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__))
def UnionFind.__init__.Run (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Unit) : Prop :=
_root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.__init__.initial h input) (.done h' (Result.fn_UnionFind___init__ output))
def UnionFind.__init__.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int) (trace : Transcript) : Prop :=
_root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.__init__.initial h input) trace final
def UnionFind.__init__.Call (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Unit) : Prop :=
_root_.Algo.«union_find».UnionFind.__init__.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind___init__ 18 ({ v0 := input.1, v1 := input.2 } : State_UnionFind___init__)) h' (Result.fn_UnionFind___init__ output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.__init__.CallFrom (state : Configuration) (finalHeap : Heap) (output : Unit) : Prop :=
match state with
| .active heap (Frame.fn_UnionFind___init__ pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind___init__ pc locals) finalHeap (Result.fn_UnionFind___init__ output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.__init__.load (input : Heap × (Ref_UnionFind × Int)) : Heap × (Ref_UnionFind × Int) := input
def UnionFind.__init__.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
_root_.Algo.«union_find».UnionFind.__init__.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.__init__.Returns (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Unit) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.__init__.Run loaded.1 loaded.2 finalHeap my_output
-- Output and clock increments from one completed execution.
def UnionFind.__init__.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Unit) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.__init__.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.__init__.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.__init__.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«union_find».UnionFind.__init__.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.__init__.Returns input output := by
obtain ⟨heap, execution, _⟩ := run
exact ⟨heap, execution⟩
theorem UnionFind.__init__.Returns.withCost {input output}
(run : _root_.Algo.«union_find».UnionFind.__init__.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.__init__.ReturnsWithCost input output costs := by
obtain ⟨heap, execution⟩ := run
exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.__init__.load input).1 heap, heap, execution, rfl⟩
theorem UnionFind.__init__.Call.run {before input after output}
(call : _root_.Algo.«union_find».UnionFind.__init__.Call before input after output) :
_root_.Algo.«union_find».UnionFind.__init__.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_UnionFind_find (input : Ref_UnionFind × Int) : Frame :=
(Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find))
def UnionFind.find.ValidInput (h : Heap) (input : Ref_UnionFind × Int) : Prop := is_UnionFind h input.1
def UnionFind.find.initial (h : Heap) (input : Ref_UnionFind × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find))
def UnionFind.find.Run (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Int) : Prop :=
_root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.find.initial h input) (.done h' (Result.fn_UnionFind_find output))
def UnionFind.find.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int) (trace : Transcript) : Prop :=
_root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.find.initial h input) trace final
def UnionFind.find.Call (h : Heap) (input : Ref_UnionFind × Int) (h' : Heap) (output : Int) : Prop :=
_root_.Algo.«union_find».UnionFind.find.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind_find 15 ({ v0 := input.1, v1 := input.2 } : State_UnionFind_find)) h' (Result.fn_UnionFind_find output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.find.CallFrom (state : Configuration) (finalHeap : Heap) (output : Int) : Prop :=
match state with
| .active heap (Frame.fn_UnionFind_find pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind_find pc locals) finalHeap (Result.fn_UnionFind_find output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.find.load (input : Heap × (Ref_UnionFind × Int)) : Heap × (Ref_UnionFind × Int) := input
def UnionFind.find.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
_root_.Algo.«union_find».UnionFind.find.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.find.Returns (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Int) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.find.Run loaded.1 loaded.2 finalHeap my_output
-- Output and clock increments from one completed execution.
def UnionFind.find.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int)) (my_output : Int) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.find.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.find.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.find.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«union_find».UnionFind.find.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.find.Returns input output := by
obtain ⟨heap, execution, _⟩ := run
exact ⟨heap, execution⟩
theorem UnionFind.find.Returns.withCost {input output}
(run : _root_.Algo.«union_find».UnionFind.find.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.find.ReturnsWithCost input output costs := by
obtain ⟨heap, execution⟩ := run
exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.find.load input).1 heap, heap, execution, rfl⟩
theorem UnionFind.find.Call.run {before input after output}
(call : _root_.Algo.«union_find».UnionFind.find.Call before input after output) :
_root_.Algo.«union_find».UnionFind.find.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_UnionFind_union (input : Ref_UnionFind × Int × Int) : Frame :=
(Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union))
def UnionFind.union.ValidInput (h : Heap) (input : Ref_UnionFind × Int × Int) : Prop := is_UnionFind h input.1
def UnionFind.union.initial (h : Heap) (input : Ref_UnionFind × Int × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union))
def UnionFind.union.Run (h : Heap) (input : Ref_UnionFind × Int × Int) (h' : Heap) (output : Bool) : Prop :=
_root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.union.initial h input) (.done h' (Result.fn_UnionFind_union output))
def UnionFind.union.ValidHeapTranscript (h : Heap) (input : Ref_UnionFind × Int × Int) (trace : Transcript) : Prop :=
_root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.union.initial h input) trace final
def UnionFind.union.Call (h : Heap) (input : Ref_UnionFind × Int × Int) (h' : Heap) (output : Bool) : Prop :=
_root_.Algo.«union_find».UnionFind.union.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind_union 25 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_UnionFind_union)) h' (Result.fn_UnionFind_union output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.union.CallFrom (state : Configuration) (finalHeap : Heap) (output : Bool) : Prop :=
match state with
| .active heap (Frame.fn_UnionFind_union pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind_union pc locals) finalHeap (Result.fn_UnionFind_union output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def UnionFind.union.load (input : Heap × (Ref_UnionFind × Int × Int)) : Heap × (Ref_UnionFind × Int × Int) := input
def UnionFind.union.ValidTranscript (my_input : Heap × (Ref_UnionFind × Int × Int)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
_root_.Algo.«union_find».UnionFind.union.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.union.Returns (my_input : Heap × (Ref_UnionFind × Int × Int)) (my_output : Bool) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.union.Run loaded.1 loaded.2 finalHeap my_output
-- Output and clock increments from one completed execution.
def UnionFind.union.ReturnsWithCost (my_input : Heap × (Ref_UnionFind × Int × Int)) (my_output : Bool) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.union.load my_input
∃ finalHeap, _root_.Algo.«union_find».UnionFind.union.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem UnionFind.union.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«union_find».UnionFind.union.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.union.Returns input output := by
obtain ⟨heap, execution, _⟩ := run
exact ⟨heap, execution⟩
theorem UnionFind.union.Returns.withCost {input output}
(run : _root_.Algo.«union_find».UnionFind.union.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.union.ReturnsWithCost input output costs := by
obtain ⟨heap, execution⟩ := run
exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.union.load input).1 heap, heap, execution, rfl⟩
theorem UnionFind.union.Call.run {before input after output}
(call : _root_.Algo.«union_find».UnionFind.union.Call before input after output) :
_root_.Algo.«union_find».UnionFind.union.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_UnionFind (input : Int) : Frame :=
(Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind))
def UnionFind.ValidInput (_h : Heap) (_input : Int) : Prop := True
def UnionFind.initial (h : Heap) (input : Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind))
def UnionFind.Run (h : Heap) (input : Int) (h' : Heap) (output : Ref_UnionFind) : Prop :=
_root_.Algo.«union_find».UnionFind.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«union_find».UnionFind.initial h input) (.done h' (Result.fn_UnionFind output))
def UnionFind.ValidHeapTranscript (h : Heap) (input : Int) (trace : Transcript) : Prop :=
_root_.Algo.«union_find».UnionFind.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«union_find».UnionFind.initial h input) trace final
def UnionFind.Call (h : Heap) (input : Int) (h' : Heap) (output : Ref_UnionFind) : Prop :=
_root_.Algo.«union_find».UnionFind.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_UnionFind 7 ({ v0 := input } : State_UnionFind)) h' (Result.fn_UnionFind output)
-- Complete this function from the supplied local state, under any caller stack.
def UnionFind.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_UnionFind) : Prop :=
match state with
| .active heap (Frame.fn_UnionFind pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_UnionFind pc locals) finalHeap (Result.fn_UnionFind output)
| _ => False
-- The value view gives each sequence input its own object.
def UnionFind.load (input : Int) : Heap × (Int) :=
let h0 : Heap := {}
(h0, input)
def UnionFind.ValidTranscript (my_input : Int) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.load my_input
_root_.Algo.«union_find».UnionFind.ValidHeapTranscript loaded.1 loaded.2 trace
def UnionFind.Returns (my_input : Int) (my_output : Heap × (Ref_UnionFind)) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.load my_input
_root_.Algo.«union_find».UnionFind.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def UnionFind.ReturnsWithCost (my_input : Int) (my_output : Heap × (Ref_UnionFind)) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«union_find».UnionFind.load my_input
_root_.Algo.«union_find».UnionFind.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem UnionFind.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«union_find».UnionFind.ReturnsWithCost input output costs) : _root_.Algo.«union_find».UnionFind.Returns input output := by
obtain ⟨execution, _⟩ := run
exact execution
theorem UnionFind.Returns.withCost {input output}
(run : _root_.Algo.«union_find».UnionFind.Returns input output) : ∃ costs, _root_.Algo.«union_find».UnionFind.ReturnsWithCost input output costs := by
exact ⟨Heap.cost (_root_.Algo.«union_find».UnionFind.load input).1 output.1, run, rfl⟩
theorem UnionFind.Call.run {before input after output}
(call : _root_.Algo.«union_find».UnionFind.Call before input after output) :
_root_.Algo.«union_find».UnionFind.Run before input after output :=
⟨call.1, call.2.root⟩
end Algo.«union_find»