1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131 | -- Abstract:
--
-- An unbounded minimum Fibonacci heap of definite non-limited elements.
--
-- References:
--
-- [1] Introduction to Algorithms, Third Edition. Thomas H. Cormen,
-- Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Chapter 19.
--
-- Copyright (C) 2017 - 2022 Free Software Foundation, Inc.
--
-- This library is free software; you can redistribute it and/or modify it
-- under terms of the GNU General Public License as published by the Free
-- Software Foundation; either version 3, or (at your option) any later
-- version. This library is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHAN-
-- TABILITY or FITNESS FOR A PARTICULAR PURPOSE.
--
-- As a special exception under Section 7 of GPL version 3, you are granted
-- additional permissions described in the GCC Runtime Library Exception,
-- version 3.1, as published by the Free Software Foundation.
pragma License (Modified_GPL);
with Ada.Finalization;
generic
type Element_Type is private;
type Key_Type is private;
with function Key (Item : in Element_Type) return Key_Type;
with procedure Set_Key (Item : in out Element_Type; Key : in Key_Type);
pragma Unreferenced (Set_Key); -- needed for Decrease_Key
with function "<" (Left, Right : in Key_Type) return Boolean is <>;
package SAL.Gen_Unbounded_Definite_Min_Heaps_Fibonacci is
type Heap_Type is new Ada.Finalization.Controlled with private;
Empty_Heap : constant Heap_Type;
overriding
procedure Initialize (Object : in out Heap_Type);
overriding
procedure Finalize (Object : in out Heap_Type);
overriding
procedure Adjust (Object : in out Heap_Type);
procedure Clear (Heap : in out Heap_Type);
-- Empty Heap.
function Count (Heap : in Heap_Type) return Base_Peek_Type;
-- Return count of elements in Heap.
function Remove (Heap : in out Heap_Type) return Element_Type
with Pre => Heap.Count > 0;
-- Remove minimum element in Heap, return it.
function Min_Key (Heap : in out Heap_Type) return Key_Type
with Pre => Heap.Count > 0;
-- Return a copy of the minimum key value.
function Get (Heap : in out Heap_Type) return Element_Type renames Remove;
procedure Drop (Heap : in out Heap_Type)
with Pre => Heap.Count > 0;
-- Remove minimum element in Heap, discard it.
procedure Add (Heap : in out Heap_Type; Item : in Element_Type);
-- Add Item to Heap.
procedure Insert (Heap : in out Heap_Type; Item : in Element_Type) renames Add;
type Constant_Reference_Type (Element : not null access constant Element_Type) is private with
Implicit_Dereference => Element;
function Peek (Heap : in Heap_Type) return Constant_Reference_Type
with Pre => Heap.Count > 0;
-- Return a constant reference to the min element.
pragma Inline (Peek);
type Variable_Reference_Type (Element : not null access Element_Type) is private with
Implicit_Dereference => Element;
function Peek_Var (Heap : in Heap_Type) return Variable_Reference_Type
with Pre => Heap.Count > 0;
pragma Inline (Peek_Var);
-- Return a variable reference to the min element. User must not change Key.
--
-- Not named "Peek" to avoid ambiguity with the constant version.
-- We don't provide a Cursor/Iterator interface; too complex to
-- implement. So far, we only need a read-only forward iterator,
-- which Process provides.
procedure Process (Heap : in Heap_Type; Process_Element : access procedure (Element : in Element_Type));
-- Call Process_Element with each Element in Heap. Min is first; rest are in
-- arbitrary order.
private
type Node;
type Node_Access is access Node;
type Node is record
Element : aliased Element_Type;
Parent : Node_Access;
Child : Node_Access;
Left : Node_Access;
Right : Node_Access;
Degree : Natural;
Mark : Boolean;
end record;
type Heap_Type is new Ada.Finalization.Controlled with record
Min : Node_Access;
Count : Base_Peek_Type;
end record;
type Constant_Reference_Type (Element : not null access constant Element_Type) is
record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
type Variable_Reference_Type (Element : not null access Element_Type) is
record
Dummy : Integer := raise Program_Error with "uninitialized reference";
end record;
Empty_Heap : constant Heap_Type := (Ada.Finalization.Controlled with Min => null, Count => 0);
end SAL.Gen_Unbounded_Definite_Min_Heaps_Fibonacci;
|