1 % (c) 2019-2026 Lehrstuhl fuer Softwaretechnik und Programmiersprachen.
2 % Heinrich Heine Universitaet Duesseldorf
3 % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html)
4 :- module(fibonacci_heap, [init/0,
5 reset/0,
6 push/2,
7 push_bt/2,
8 delete_elm/1,
9 delete_elm_bt/1,
10 elm_exists/1,
11 is_empty/0,
12 get_max_value/1,
13 get_max_priority/1,
14 get_priority_of/2,
15 get_priority_of_silent_fail/2,
16 get_and_remove_max_value/1,
17 get_and_remove_max_value_bt/1,
18 update/2,
19 update_bt/2,
20 inc_priority_of/2,
21 inc_priority_of_bt/2,
22 dec_priority_of/2,
23 dec_priority_of_bt/2,
24 mult_priority_of/2,
25 mult_priority_of_bt/2,
26 mult_priority_of_all/1,
27 set_maintain_update_order/1]).
28
29 :- use_module(probsrc(pathes_lib),[safe_load_foreign_resource/2]).
30 :- use_module(probsrc(error_manager), [add_error_and_fail/2]).
31 :- use_module(probsrc(module_information)).
32
33 :- module_info(group, extension).
34 :- module_info(description, 'Fibonacci heap to store atoms with a priority.').
35
36 % Note: By default, the heap maintains the insertion/update order if several elements have the same priority.
37 % Can be set to false using set_maintain_update_order(false).
38
39 foreign_resource(fibonacci_heap, [reset,
40 push,
41 push_with_fixed_update_count,
42 is_empty,
43 delete_elm,
44 get_max_value_,
45 get_max_priority_,
46 get_priority_of_,
47 get_update_count_of_,
48 get_and_remove_max_value_,
49 elm_exists,
50 update,
51 inc_priority_of,
52 dec_priority_of,
53 mult_priority_of,
54 mult_priority_of_all,
55 set_maintain_update_order_]).
56
57 foreign(reset, c, reset).
58 foreign(push, c, push(+float,+atom)).
59 foreign(push_with_fixed_update_count, c, push_with_fixed_update_count(+float,+atom,+integer)).
60 foreign(delete_elm, c, delete_elm(+atom,[-integer])).
61 foreign(is_empty, c, is_empty([-integer])).
62 foreign(get_max_value_, c, get_max_value_([-atom])).
63 foreign(get_max_priority_, c, get_max_priority_([-float])).
64 foreign(get_priority_of_, c, get_priority_of_(+atom,[-float])).
65 foreign(get_update_count_of_, c, get_update_count_of_(+atom,[-integer])).
66 foreign(get_and_remove_max_value_, c, get_and_remove_max_value_([-atom])).
67 foreign(elm_exists, c, elm_exists(+atom,[-integer])).
68 foreign(update, c, update(+atom,+float,[-integer])).
69 foreign(inc_priority_of, c, inc_priority_of(+atom,+float,[-integer])).
70 foreign(dec_priority_of, c, dec_priority_of(+atom,+float,[-integer])).
71 foreign(mult_priority_of, c, mult_priority_of(+atom,+float,[-integer])).
72 foreign(mult_priority_of_all, c, mult_priority_of_all(+float)).
73 foreign(set_maintain_update_order_, c, set_maintain_update_order_(+integer)).
74
75 is_empty :-
76 is_empty(Empty),
77 Empty == 1.
78
79 delete_elm(Value) :-
80 delete_elm(Value, Success),
81 Success == 1.
82
83 update(Value, Priority) :-
84 update(Value, Priority, Success),
85 Success == 1.
86
87 get_max_value(MaxValue) :-
88 catch(get_max_value_(MaxValue),
89 Exception,
90 add_error_and_fail(get_max_value, Exception)).
91
92 get_max_priority(MaxPrio) :-
93 catch(get_max_priority_(MaxPrio),
94 Exception,
95 add_error_and_fail(get_max_priority, Exception)).
96
97 get_priority_of(Value, Priority) :-
98 catch(get_priority_of_(Value, Priority),
99 Exception,
100 add_error_and_fail(get_priority_of, Exception)).
101
102 get_priority_of_silent_fail(Value, Priority) :-
103 catch(get_priority_of_(Value, Priority),
104 _,
105 fail).
106
107 get_and_remove_max_value(MaxValue) :-
108 catch(get_and_remove_max_value_(MaxValue),
109 Exception,
110 add_error_and_fail(get_and_remove_max_value, Exception)).
111
112 get_update_count_of(Value, UpdateCount) :-
113 catch(get_update_count_of_(Value, UpdateCount),
114 Exception,
115 add_error_and_fail(get_update_count_of, Exception)).
116
117 elm_exists(Value) :-
118 elm_exists(Value, Exists),
119 Exists == 1.
120
121 inc_priority_of(Value, IncBy) :-
122 inc_priority_of(Value, IncBy, Success),
123 Success == 1.
124
125 dec_priority_of(Value, IncBy) :-
126 dec_priority_of(Value, IncBy, Success),
127 Success == 1.
128
129 mult_priority_of(Value, MultBy) :-
130 mult_priority_of(Value, MultBy, Success),
131 Success == 1.
132
133 % Note: push/2 of an existing value updates its priority.
134 push_bt(Priority, Value) :-
135 ( elm_exists(Value)
136 -> get_priority_of(Value, OldPriority),
137 get_update_count_of(Value, OldUpdateCount),
138 push(Priority, Value),
139 ( true
140 ; push_with_fixed_update_count(OldPriority, Value, OldUpdateCount),
141 fail
142 )
143 ; push(Priority, Value),
144 ( true
145 ; delete_elm(Value),
146 fail
147 )
148 ).
149
150 update_bt(Value, Priority) :-
151 get_priority_of(Value, OldPriority),
152 update(Value, Priority),
153 ( true
154 ; update(Value, OldPriority),
155 fail
156 ).
157
158 delete_elm_bt(Value) :-
159 get_priority_of(Value, Priority),
160 get_update_count_of(Value, UpdateCount),
161 delete_elm(Value),
162 ( true
163 ; push_with_fixed_update_count(Priority, Value, UpdateCount),
164 fail
165 ).
166
167 get_and_remove_max_value_bt(MaxValue) :-
168 get_max_value(MaxValue),
169 delete_elm_bt(MaxValue).
170
171 inc_priority_of_bt(Value, IncBy) :-
172 ( inc_priority_of(Value, IncBy)
173 ; dec_priority_of(Value, IncBy),
174 fail
175 ).
176
177 dec_priority_of_bt(Value, DecBy) :-
178 ( dec_priority_of(Value, DecBy)
179 ; inc_priority_of(Value, DecBy),
180 fail
181 ).
182
183 mult_priority_of_bt(Value, IncBy) :-
184 get_priority_of(Value, OldPriority),
185 ( mult_priority_of(Value, IncBy)
186 ; update(Value, OldPriority),
187 fail
188 ).
189
190 set_maintain_update_order(MaintainOrder) :-
191 ( MaintainOrder == true
192 -> set_maintain_update_order_(1)
193 ; set_maintain_update_order_(0)
194 ).
195
196 :- dynamic loaded/0.
197
198 init :-
199 load,
200 reset.
201
202 load :-
203 ( loaded
204 -> true
205 ; asserta(loaded),
206 safe_load_foreign_resource(fibonacci_heap, fibonacci_heap)
207 ).