Algo.dijkstra.dijkstra_fibonacci.Generated definitions
DefinitionAlgo_dijkstra_dijkstra_fibonacci_GeneratedDefinitions and required structural lemmas from Algo.dijkstra.dijkstra_fibonacci.Generated. Source declarations are retained by compiler-reported ranges; imports are redirected to the corresponding definition bundles. This bundle contains no theorem stubs.
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
import Definitions.Def_Algo2LeanLib_Interface
import Definitions.Def_Algo_graph_Generated
import Definitions.Def_Algo_fibonacci_heap_Generated
import Definitions.Def_Algo_dijkstra_dijkstra_Generated
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.«dijkstra».«dijkstra_fibonacci»
open _root_.Algo2LeanGenerated
-- Independently compiled module; imported algorithms keep their own transitions.
def FibonacciHeap_as_PriorityQueue : Algo.«dijkstra».«priority_queue».«PriorityQueue».Code where
toInterfaceCode := Algo2LeanCore.InterfaceAdapter.code Algo.«fibonacci_heap».Algo2LeanGenerated.Step
valid := fun heap ref => decide (Algo.«fibonacci_heap».Algo2LeanGenerated.is_FibonacciHeap heap ref)
entry_PriorityQueue_push_or_decrease := fun input =>
Algo2LeanCore.InterfaceAdapter.entry (Algo.«fibonacci_heap».entry_FibonacciHeap_push_or_decrease input) (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_push_or_decrease value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_push_or_decrease value) | _ => none)
entry_PriorityQueue_pop_min := fun input =>
Algo2LeanCore.InterfaceAdapter.entry (Algo.«fibonacci_heap».entry_FibonacciHeap_pop_min input) (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_pop_min value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_pop_min value) | _ => none)
entry_PriorityQueue_is_empty := fun input =>
Algo2LeanCore.InterfaceAdapter.entry (Algo.«fibonacci_heap».entry_FibonacciHeap_is_empty input) (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_is_empty value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_is_empty value) | _ => none)
theorem FibonacciHeap_as_PriorityQueue_summary_push_or_decrease {before after : Heap} {input : ObjectRef × Int × Int} {output : Unit}
(contract : Algo.«fibonacci_heap».FibonacciHeap.push_or_decrease.Call before input after output) :
Algo.«dijkstra».«priority_queue».«PriorityQueue».push_or_decrease.Call FibonacciHeap_as_PriorityQueue before input after output := by
have receiver_valid : Algo.«fibonacci_heap».Algo2LeanGenerated.is_FibonacciHeap before input.1 := contract.1
refine ⟨?_, ?_⟩
· simpa [FibonacciHeap_as_PriorityQueue] using receiver_valid
· exact Algo2LeanCore.InterfaceAdapter.summary Algo.«fibonacci_heap».Algo2LeanGenerated.terminal contract.2 (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_push_or_decrease value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_push_or_decrease value) | _ => none) rfl
theorem FibonacciHeap_as_PriorityQueue_summary_pop_min {before after : Heap} {input : ObjectRef} {output : Int}
(contract : Algo.«fibonacci_heap».FibonacciHeap.pop_min.Call before input after output) :
Algo.«dijkstra».«priority_queue».«PriorityQueue».pop_min.Call FibonacciHeap_as_PriorityQueue before input after output := by
have receiver_valid : Algo.«fibonacci_heap».Algo2LeanGenerated.is_FibonacciHeap before input := contract.1
refine ⟨?_, ?_⟩
· simpa [FibonacciHeap_as_PriorityQueue] using receiver_valid
· exact Algo2LeanCore.InterfaceAdapter.summary Algo.«fibonacci_heap».Algo2LeanGenerated.terminal contract.2 (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_pop_min value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_pop_min value) | _ => none) rfl
theorem FibonacciHeap_as_PriorityQueue_summary_is_empty {before after : Heap} {input : ObjectRef} {output : Bool}
(contract : Algo.«fibonacci_heap».FibonacciHeap.is_empty.Call before input after output) :
Algo.«dijkstra».«priority_queue».«PriorityQueue».is_empty.Call FibonacciHeap_as_PriorityQueue before input after output := by
have receiver_valid : Algo.«fibonacci_heap».Algo2LeanGenerated.is_FibonacciHeap before input := contract.1
refine ⟨?_, ?_⟩
· simpa [FibonacciHeap_as_PriorityQueue] using receiver_valid
· exact Algo2LeanCore.InterfaceAdapter.summary Algo.«fibonacci_heap».Algo2LeanGenerated.terminal contract.2 (fun result : Algo.«fibonacci_heap».Algo2LeanGenerated.Result => match result with | .fn_FibonacciHeap_is_empty value => some (Algo.«dijkstra».«priority_queue».«PriorityQueue».Result.fn_PriorityQueue_is_empty value) | _ => none) rfl
def use_dijkstra_dijkstra_0 : Algo.«dijkstra».«dijkstra».Dependencies where
«PriorityQueue» := FibonacciHeap_as_PriorityQueue
namespace Algo2LeanGenerated
abbrev Ref__a2l_import_0_Edge := Algo.«graph».Algo2LeanGenerated.Ref_Edge
abbrev Ref__a2l_import_0_Graph := Algo.«graph».Algo2LeanGenerated.Ref_Graph
abbrev Ref__a2l_import_1_FibonacciHeap := Algo.«fibonacci_heap».Algo2LeanGenerated.Ref_FibonacciHeap
abbrev Ref__a2l_import_2_PriorityQueue := ObjectRef
abbrev is__a2l_import_0_Edge := Algo.«graph».Algo2LeanGenerated.is_Edge
abbrev create__a2l_import_0_Edge := Algo.«graph».Algo2LeanGenerated.create_Edge
abbrev field__a2l_import_0_Edge_target := Algo.«graph».Algo2LeanGenerated.field_Edge_target
abbrev set__a2l_import_0_Edge_target := Algo.«graph».Algo2LeanGenerated.set_Edge_target
abbrev field__a2l_import_0_Edge_weight := Algo.«graph».Algo2LeanGenerated.field_Edge_weight
abbrev set__a2l_import_0_Edge_weight := Algo.«graph».Algo2LeanGenerated.set_Edge_weight
abbrev field__a2l_import_0_Edge_next := Algo.«graph».Algo2LeanGenerated.field_Edge_next
abbrev set__a2l_import_0_Edge_next := Algo.«graph».Algo2LeanGenerated.set_Edge_next
abbrev is__a2l_import_0_Graph := Algo.«graph».Algo2LeanGenerated.is_Graph
abbrev create__a2l_import_0_Graph := Algo.«graph».Algo2LeanGenerated.create_Graph
abbrev field__a2l_import_0_Graph_size := Algo.«graph».Algo2LeanGenerated.field_Graph_size
abbrev set__a2l_import_0_Graph_size := Algo.«graph».Algo2LeanGenerated.set_Graph_size
abbrev field__a2l_import_0_Graph_heads := Algo.«graph».Algo2LeanGenerated.field_Graph_heads
abbrev set__a2l_import_0_Graph_heads := Algo.«graph».Algo2LeanGenerated.set_Graph_heads
abbrev is__a2l_import_1_FibonacciHeap := Algo.«fibonacci_heap».Algo2LeanGenerated.is_FibonacciHeap
abbrev create__a2l_import_1_FibonacciHeap := Algo.«fibonacci_heap».Algo2LeanGenerated.create_FibonacciHeap
abbrev field__a2l_import_1_FibonacciHeap_keys := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_keys
abbrev set__a2l_import_1_FibonacciHeap_keys := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_keys
abbrev field__a2l_import_1_FibonacciHeap_parents := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_parents
abbrev set__a2l_import_1_FibonacciHeap_parents := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_parents
abbrev field__a2l_import_1_FibonacciHeap_children := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_children
abbrev set__a2l_import_1_FibonacciHeap_children := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_children
abbrev field__a2l_import_1_FibonacciHeap_left := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_left
abbrev set__a2l_import_1_FibonacciHeap_left := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_left
abbrev field__a2l_import_1_FibonacciHeap_right := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_right
abbrev set__a2l_import_1_FibonacciHeap_right := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_right
abbrev field__a2l_import_1_FibonacciHeap_degrees := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_degrees
abbrev set__a2l_import_1_FibonacciHeap_degrees := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_degrees
abbrev field__a2l_import_1_FibonacciHeap_marks := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_marks
abbrev set__a2l_import_1_FibonacciHeap_marks := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_marks
abbrev field__a2l_import_1_FibonacciHeap_present := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_present
abbrev set__a2l_import_1_FibonacciHeap_present := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_present
abbrev field__a2l_import_1_FibonacciHeap_table := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_table
abbrev set__a2l_import_1_FibonacciHeap_table := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_table
abbrev field__a2l_import_1_FibonacciHeap_minimum := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_minimum
abbrev set__a2l_import_1_FibonacciHeap_minimum := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_minimum
abbrev field__a2l_import_1_FibonacciHeap_size := Algo.«fibonacci_heap».Algo2LeanGenerated.field_FibonacciHeap_size
abbrev set__a2l_import_1_FibonacciHeap_size := Algo.«fibonacci_heap».Algo2LeanGenerated.set_FibonacciHeap_size
def seq__a2l_import_0_Edge_optional : SequenceType (Option Ref__a2l_import_0_Edge) where
name := "graph.Edge?"
encode := fun value => (match value with | some ref => ObjectValue.objectValue ref | none => ObjectValue.noneValue)
decode := ObjectValue.asNullableObject
decode_encode := by intro value; cases value <;> rfl
structure State_dijkstra_fibonacci where
v0 : Ref__a2l_import_0_Graph := 0 -- graph
v1 : Int := 0 -- source
v2 : SeqRef := 0 -- distance
v3 : SeqRef := 0 -- settled
v4 : Ref__a2l_import_1_FibonacciHeap := 0 -- queue
t5 : SeqRef := 0 -- temporary
t6 : Ref__a2l_import_0_Graph := 0 -- temporary
t7 : Int := 0 -- temporary
t8 : Ref__a2l_import_2_PriorityQueue := 0 -- temporary
t9 : SeqRef := 0 -- temporary
t10 : SeqRef := 0 -- temporary
t11 : Ref__a2l_import_1_FibonacciHeap := 0 -- temporary
t12 : SeqRef := 0 -- temporary
t13 : Int := 0 -- temporary
t14 : Bool := false -- temporary
t15 : SeqRef := 0 -- temporary
t16 : SeqRef := 0 -- temporary
t17 : Int := 0 -- temporary
inductive Frame where
| invalid
| fn_dijkstra_fibonacci (pc : Nat) (state : State_dijkstra_fibonacci)
| import_1 (frame : Algo.«fibonacci_heap».Algo2LeanGenerated.Frame) (inner : Algo.«fibonacci_heap».Algo2LeanGenerated.Stack) (resume : Algo.«fibonacci_heap».Algo2LeanGenerated.Result → Frame)
| import_3_use_dijkstra_dijkstra_0 (frame : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Frame use_dijkstra_dijkstra_0)) (inner : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Stack use_dijkstra_dijkstra_0)) (resume : Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Result → Frame)
inductive Result where
| fn_dijkstra_fibonacci (value : SeqRef)
abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)
inductive Step : Configuration → Configuration → Prop where
| dijkstra_fibonacci_pc1 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) (defined : s.t5 < h.nextRef) :
Step (.active h (Frame.fn_dijkstra_fibonacci 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_dijkstra_fibonacci (s.t5)) stack)
| dijkstra_fibonacci_pc2 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 2 s) stack) (.active h (Frame.import_3_use_dijkstra_dijkstra_0 (Algo.«dijkstra».«dijkstra».entry_dijkstra use_dijkstra_dijkstra_0 (s.t6, s.t7, s.t8, s.t9, s.t10)) [] (fun value => match value with | .fn_dijkstra result => (Frame.fn_dijkstra_fibonacci 1 { s with t5 := result }) | _ => .invalid)) stack)
| dijkstra_fibonacci_pc3 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 3 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 2 { s with t10 := s.v3 }) stack)
| dijkstra_fibonacci_pc4 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 4 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 3 { s with t9 := s.v2 }) stack)
| dijkstra_fibonacci_pc5 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 5 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 4 { s with t8 := s.v4 }) stack)
| dijkstra_fibonacci_pc6 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 6 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 5 { s with t7 := s.v1 }) stack)
| dijkstra_fibonacci_pc7 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 7 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 6 { s with t6 := s.v0 }) stack)
| dijkstra_fibonacci_pc8 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 8 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 7 { s with v4 := s.t11 }) stack)
| dijkstra_fibonacci_pc9 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 9 s) stack) (.active h (Frame.import_1 (Algo.«fibonacci_heap».entry_FibonacciHeap ()) [] (fun value => match value with | .fn_FibonacciHeap result => (Frame.fn_dijkstra_fibonacci 8 { s with t11 := result }) | _ => .invalid)) stack)
| dijkstra_fibonacci_pc10 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 10 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 9 { s with v3 := s.t12 }) stack)
| dijkstra_fibonacci_pc11 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 11 s) stack) (.active (h.allocate (fun _ => s.t13)) (Frame.fn_dijkstra_fibonacci 10 { s with t12 := h.nextRef }) stack)
| dijkstra_fibonacci_pc12 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 12 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 11 { s with t13 := (0 : Int) }) stack)
| dijkstra_fibonacci_pc13 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) (defined : s.t15 < h.nextRef) :
Step (.active h (Frame.fn_dijkstra_fibonacci 13 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_dijkstra_fibonacci (s.t15)) stack)
| dijkstra_fibonacci_pc14 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 14 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 13 { s with t15 := s.v2 }) stack)
| dijkstra_fibonacci_pc15_true (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) (condition : s.t14 = true) :
Step (.active h (Frame.fn_dijkstra_fibonacci 15 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 14 s) stack)
| dijkstra_fibonacci_pc15_false (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) (condition : s.t14 = false) :
Step (.active h (Frame.fn_dijkstra_fibonacci 15 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 12 s) stack)
| dijkstra_fibonacci_pc16 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) (defined : (((decide ((s.v1 < (0 : Int)))) = false → ((((field__a2l_import_0_Graph_size h (s.v0)).isSome = true)))))) :
Step (.active h (Frame.fn_dijkstra_fibonacci 16 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 15 { s with t14 := ((decide ((s.v1 < (0 : Int)))) || (decide ((s.v1 ≥ ((field__a2l_import_0_Graph_size h (s.v0)).getD 0))))) }) stack)
| dijkstra_fibonacci_pc17 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 17 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 16 { s with v2 := s.t16 }) stack)
| dijkstra_fibonacci_pc18 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 18 s) stack) (.active (h.allocate (fun _ => s.t17)) (Frame.fn_dijkstra_fibonacci 17 { s with t16 := h.nextRef }) stack)
| dijkstra_fibonacci_pc19 (h : Heap) (s : State_dijkstra_fibonacci) (stack : Stack) :
Step (.active h (Frame.fn_dijkstra_fibonacci 19 s) stack) (.active h (Frame.fn_dijkstra_fibonacci 18 { s with t17 := (-(1 : Int)) }) stack)
| import_1 (h : Heap) (frame : Algo.«fibonacci_heap».Algo2LeanGenerated.Frame) (inner : Algo.«fibonacci_heap».Algo2LeanGenerated.Stack)
(resume : Algo.«fibonacci_heap».Algo2LeanGenerated.Result → Frame) (caller : Stack) (after : Algo.«fibonacci_heap».Algo2LeanGenerated.Configuration)
(transition : Algo.«fibonacci_heap».Algo2LeanGenerated.Step (.active h frame inner) after) :
Step (.active h (Frame.import_1 frame inner resume) caller)
(Algo2LeanCore.ModuleCall.config Frame.import_1 resume caller after)
| import_3_use_dijkstra_dijkstra_0 (h : Heap) (frame : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Frame use_dijkstra_dijkstra_0)) (inner : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Stack use_dijkstra_dijkstra_0))
(resume : Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Result → Frame) (caller : Stack) (after : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Configuration use_dijkstra_dijkstra_0))
(transition : (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Step use_dijkstra_dijkstra_0) (.active h frame inner) after) :
Step (.active h (Frame.import_3_use_dijkstra_dijkstra_0 frame inner resume) caller)
(Algo2LeanCore.ModuleCall.config Frame.import_3_use_dijkstra_dijkstra_0 resume caller after)
theorem terminal (h : Heap) (result : Result) :
Algo2LeanCore.Terminal Step (.done h result) := by
intro next transition
cases transition
theorem import_1_simulates :
Algo2LeanCore.ModuleCall.Simulates Frame.import_1 Algo.«fibonacci_heap».Algo2LeanGenerated.Step Step := by
apply Algo2LeanCore.ModuleCall.Delegates.simulates
· exact Step.import_1
· exact Algo.«fibonacci_heap».Algo2LeanGenerated.terminal
theorem import_3_use_dijkstra_dijkstra_0_simulates :
Algo2LeanCore.ModuleCall.Simulates Frame.import_3_use_dijkstra_dijkstra_0 (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.Step use_dijkstra_dijkstra_0) Step := by
apply Algo2LeanCore.ModuleCall.Delegates.simulates
· exact Step.import_3_use_dijkstra_dijkstra_0
· exact (Algo.«dijkstra».«dijkstra».Algo2LeanGenerated.terminal use_dijkstra_dijkstra_0)
end Algo2LeanGenerated
open Algo2LeanGenerated
def entry_dijkstra_fibonacci (input : Ref__a2l_import_0_Graph × Int) : Frame :=
(Frame.fn_dijkstra_fibonacci 19 ({ v0 := input.1, v1 := input.2 } : State_dijkstra_fibonacci))
def dijkstra_fibonacci.ValidInput (h : Heap) (input : Ref__a2l_import_0_Graph × Int) : Prop := is__a2l_import_0_Graph h input.1
def dijkstra_fibonacci.initial (h : Heap) (input : Ref__a2l_import_0_Graph × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_dijkstra_fibonacci 19 ({ v0 := input.1, v1 := input.2 } : State_dijkstra_fibonacci))
def dijkstra_fibonacci.Run (h : Heap) (input : Ref__a2l_import_0_Graph × Int) (h' : Heap) (output : SeqRef) : Prop :=
_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.initial h input) (.done h' (Result.fn_dijkstra_fibonacci output))
def dijkstra_fibonacci.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_Graph × Int) (trace : Transcript) : Prop :=
_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.initial h input) trace final
def dijkstra_fibonacci.Call (h : Heap) (input : Ref__a2l_import_0_Graph × Int) (h' : Heap) (output : SeqRef) : Prop :=
_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_dijkstra_fibonacci 19 ({ v0 := input.1, v1 := input.2 } : State_dijkstra_fibonacci)) h' (Result.fn_dijkstra_fibonacci output)
-- Complete this function from the supplied local state, under any caller stack.
def dijkstra_fibonacci.CallFrom (state : Configuration) (finalHeap : Heap) (output : SeqRef) : Prop :=
match state with
| .active heap (Frame.fn_dijkstra_fibonacci pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_dijkstra_fibonacci pc locals) finalHeap (Result.fn_dijkstra_fibonacci output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def dijkstra_fibonacci.load (input : Heap × (Ref__a2l_import_0_Graph × Int)) : Heap × (Ref__a2l_import_0_Graph × Int) := input
def dijkstra_fibonacci.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_Graph × Int)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.load my_input
_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ValidHeapTranscript loaded.1 loaded.2 trace
def dijkstra_fibonacci.Returns (my_input : Heap × (Ref__a2l_import_0_Graph × Int)) (my_output : Seq) : Prop :=
let loaded := _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.load my_input
∃ finalHeap result, _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Run loaded.1 loaded.2 finalHeap result ∧ finalHeap.store result = my_output
-- Output and clock increments from one completed execution.
def dijkstra_fibonacci.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_Graph × Int)) (my_output : Seq) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.load my_input
∃ finalHeap result, _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Run loaded.1 loaded.2 finalHeap result ∧ finalHeap.store result = my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem dijkstra_fibonacci.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ReturnsWithCost input output costs) : _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Returns input output := by
obtain ⟨heap, result, execution, value, _⟩ := run
exact ⟨heap, result, execution, value⟩
theorem dijkstra_fibonacci.Returns.withCost {input output}
(run : _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Returns input output) : ∃ costs, _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.ReturnsWithCost input output costs := by
obtain ⟨heap, result, execution, value⟩ := run
exact ⟨Heap.cost (_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.load input).1 heap, heap, result, execution, value, rfl⟩
theorem dijkstra_fibonacci.Call.run {before input after output}
(call : _root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Call before input after output) :
_root_.Algo.«dijkstra».«dijkstra_fibonacci».dijkstra_fibonacci.Run before input after output :=
⟨call.1, call.2.root⟩
end Algo.«dijkstra».«dijkstra_fibonacci»