1 :- module(fibonacci_heap, [init/0,
2 reset/0,
3 push/2,
4 push_bt/2,
5 delete_elm/1,
6 delete_elm_bt/1,
7 is_empty/0,
8 get_max_value/1,
9 get_max_priority/1,
10 get_priority_of/2,
11 get_priority_of_silent_fail/2,
12 get_and_remove_max_value/1,
13 get_and_remove_max_value_bt/1,
14 update/2,
15 update_bt/2,
16 inc_priority_of/2,
17 inc_priority_of_bt/2,
18 dec_priority_of/2,
19 dec_priority_of_bt/2,
20 mult_priority_of/2,
21 mult_priority_of_bt/2,
22 mult_priority_of_all/1,
23 set_maintain_update_order/1,
24 test/0]).
25
26 :- use_module(probsrc(pathes_lib),[safe_load_foreign_resource/2]).
27 :- use_module(probsrc(error_manager), [add_error_and_fail/2]).
28 :- use_module(probsrc(module_information)).
29
30 :- module_info(group, extension).
31 :- module_info(description, 'Fibonacci heap to store atoms with a priority.').
32
33 % Note: By default, the heap maintains the insertion/update order if several elements have the same priority.
34 % Can be set to false using set_maintain_update_order(false).
35
36 foreign_resource(fibonacci_heap, [reset,
37 push,
38 push_with_fixed_update_count,
39 is_empty,
40 delete_elm,
41 get_max_value_,
42 get_max_priority_,
43 get_priority_of_,
44 get_update_count_of_,
45 get_and_remove_max_value_,
46 elm_exists,
47 update,
48 inc_priority_of,
49 dec_priority_of,
50 mult_priority_of,
51 mult_priority_of_all,
52 set_maintain_update_order_]).
53
54 foreign(reset, c, reset).
55 foreign(push, c, push(+float,+atom)).
56 foreign(push_with_fixed_update_count, c, push_with_fixed_update_count(+float,+atom,+integer)).
57 foreign(delete_elm, c, delete_elm(+atom,[-integer])).
58 foreign(is_empty, c, is_empty([-integer])).
59 foreign(get_max_value_, c, get_max_value_([-atom])).
60 foreign(get_max_priority_, c, get_max_priority_([-float])).
61 foreign(get_priority_of_, c, get_priority_of_(+atom,[-float])).
62 foreign(get_update_count_of_, c, get_update_count_of_(+atom,[-integer])).
63 foreign(get_and_remove_max_value_, c, get_and_remove_max_value_([-atom])).
64 foreign(elm_exists, c, elm_exists(+atom,[-integer])).
65 foreign(update, c, update(+atom,+float,[-integer])).
66 foreign(inc_priority_of, c, inc_priority_of(+atom,+float,[-integer])).
67 foreign(dec_priority_of, c, dec_priority_of(+atom,+float,[-integer])).
68 foreign(mult_priority_of, c, mult_priority_of(+atom,+float,[-integer])).
69 foreign(mult_priority_of_all, c, mult_priority_of_all(+float)).
70 foreign(set_maintain_update_order_, c, set_maintain_update_order_(+integer)).
71
72 is_empty :-
73 is_empty(Empty),
74 Empty == 1.
75
76 delete_elm(Value) :-
77 delete_elm(Value, Success),
78 Success == 1.
79
80 update(Value, Priority) :-
81 update(Value, Priority, Success),
82 Success == 1.
83
84 get_max_value(MaxValue) :-
85 catch(get_max_value_(MaxValue),
86 Exception,
87 add_error_and_fail(get_max_value, Exception)).
88
89 get_max_priority(MaxPrio) :-
90 catch(get_max_priority_(MaxPrio),
91 Exception,
92 add_error_and_fail(get_max_priority, Exception)).
93
94 get_priority_of(Value, Priority) :-
95 catch(get_priority_of_(Value, Priority),
96 Exception,
97 add_error_and_fail(get_priority_of, Exception)).
98
99 get_priority_of_silent_fail(Value, Priority) :-
100 catch(get_priority_of_(Value, Priority),
101 _,
102 fail).
103
104 get_and_remove_max_value(MaxValue) :-
105 catch(get_and_remove_max_value_(MaxValue),
106 Exception,
107 add_error_and_fail(get_and_remove_max_value, Exception)).
108
109 get_update_count_of(Value, UpdateCount) :-
110 catch(get_update_count_of_(Value, UpdateCount),
111 Exception,
112 add_error_and_fail(get_update_count_of, Exception)).
113
114 elm_exists(Value) :-
115 elm_exists(Value, Exists),
116 Exists == 1.
117
118 inc_priority_of(Value, IncBy) :-
119 inc_priority_of(Value, IncBy, Success),
120 Success == 1.
121
122 dec_priority_of(Value, IncBy) :-
123 dec_priority_of(Value, IncBy, Success),
124 Success == 1.
125
126 mult_priority_of(Value, MultBy) :-
127 mult_priority_of(Value, MultBy, Success),
128 Success == 1.
129
130 push_bt(Priority, Value) :-
131 push(Priority, Value),
132 ( true
133 ; delete_elm(Value),
134 fail
135 ).
136
137 update_bt(Value, Priority) :-
138 get_priority_of(Value, OldPriority),
139 update(Value, Priority),
140 ( true
141 ; update(Value, OldPriority),
142 fail
143 ).
144
145 delete_elm_bt(Value) :-
146 get_priority_of(Value, Priority),
147 get_update_count_of(Value, UpdateCount),
148 delete_elm(Value),
149 ( true
150 ; push_with_fixed_update_count(Priority, Value, UpdateCount),
151 fail
152 ).
153
154 get_and_remove_max_value_bt(MaxValue) :-
155 get_max_value(MaxValue),
156 delete_elm_bt(MaxValue).
157
158 inc_priority_of_bt(Value, IncBy) :-
159 ( inc_priority_of(Value, IncBy)
160 ; dec_priority_of(Value, IncBy),
161 fail
162 ).
163
164 dec_priority_of_bt(Value, DecBy) :-
165 ( dec_priority_of(Value, DecBy)
166 ; inc_priority_of(Value, DecBy),
167 fail
168 ).
169
170 mult_priority_of_bt(Value, IncBy) :-
171 get_priority_of(Value, OldPriority),
172 ( mult_priority_of(Value, IncBy)
173 ; update(Value, OldPriority),
174 fail
175 ).
176
177 set_maintain_update_order(MaintainOrder) :-
178 ( MaintainOrder == true
179 -> set_maintain_update_order_(1)
180 ; set_maintain_update_order_(0)
181 ).
182
183 :- dynamic loaded/0.
184
185 init :-
186 load,
187 reset.
188
189 load :-
190 ( loaded
191 -> true
192 ; asserta(loaded),
193 safe_load_foreign_resource(fibonacci_heap, fibonacci_heap)
194 ).
195
196 test :-
197 simple_test,
198 bt_test.
199
200 simple_test :-
201 init,
202 is_empty,
203 push(-1.2, a),
204 elm_exists(a),
205 get_max_value(MaxVal1),
206 get_max_priority(MaxPrio),
207 MaxPrio == -1.2,
208 MaxVal1 == a,
209 push(2, b),
210 elm_exists(b),
211 get_max_value(MaxVal2),
212 MaxVal2 == b,
213 get_and_remove_max_value(MaxVal3),
214 MaxVal3 == b,
215 get_max_value(MaxVal4),
216 MaxVal4 == a,
217 push(3.3, b),
218 get_max_priority(MaxPrio1),
219 MaxPrio1 == 3.3,
220 update(a, 10),
221 get_priority_of(a, PrioA),
222 PrioA == 10.0,
223 get_max_value(MaxVal5),
224 MaxVal5 == a,
225 get_max_priority(MaxPrio2),
226 MaxPrio2 == 10.0,
227 inc_priority_of(b, 10),
228 get_max_value(MaxVal6),
229 MaxVal6 == b,
230 get_max_priority(MaxPrio3),
231 MaxPrio3 == 13.3,
232 delete_elm(b),
233 get_max_value(MaxVal7),
234 MaxVal7 == a,
235 get_max_priority(MaxPrio4),
236 MaxPrio4 == 10.0,
237 mult_priority_of(a, 0.5),
238 get_max_priority(MaxPrio5),
239 MaxPrio5 == 5.0,
240 elm_exists(a),
241 push(5.0, c),
242 get_max_priority(MaxPrio6),
243 MaxPrio6 == 5.0,
244 get_max_value(MaxVal8),
245 MaxVal8 == c,
246 set_maintain_update_order(false),
247 push(5.0, d),
248 get_max_priority(MaxPrio7),
249 MaxPrio7 == 5.0,
250 get_max_value(MaxVal9),
251 MaxVal9 == c,
252 set_maintain_update_order(true),
253 push(5.0, e),
254 get_max_priority(MaxPrio8),
255 MaxPrio8 == 5.0,
256 get_max_value(MaxVal10),
257 MaxVal10 == e,
258 push(4.0, f),
259 update(f, 5.0),
260 get_max_priority(MaxPrio9),
261 MaxPrio9 == 5.0,
262 get_max_value(MaxVal11),
263 MaxVal11 == f,
264 dec_priority_of(f, 2.0),
265 get_priority_of(f, PrioF),
266 PrioF == 3.0.
267
268 bt_test :-
269 init,
270 push(1, a),
271 push(0, b),
272 ( push_bt(3, c),
273 get_max_value(MaxVal1),
274 elm_exists(c),
275 MaxVal1 == c,
276 fail
277 ; get_max_value(MaxVal2),
278 \+ elm_exists(c),
279 MaxVal2 == a
280 ),
281 ( delete_elm_bt(a),
282 get_max_value(MaxVal3),
283 MaxVal3 == b,
284 fail
285 ; get_max_value(MaxVal4),
286 MaxVal4 == a
287 ),
288 ( update_bt(b, 10),
289 get_max_priority(MaxPrio1),
290 MaxPrio1 == 10.0,
291 get_max_value(MaxVal5),
292 MaxVal5 == b,
293 fail
294 ; get_max_priority(MaxPrio2),
295 MaxPrio2 == 1.0,
296 get_max_value(MaxVal6),
297 MaxVal6 == a
298 ),
299 push(10, c),
300 push(10, d),
301 get_max_value(MaxVal7),
302 MaxVal7 == d,
303 ( delete_elm_bt(c),
304 delete_elm_bt(d),
305 fail
306 ; get_max_value(MaxVal8),
307 MaxVal8 == d
308 ),
309 ( delete_elm_bt(a),
310 delete_elm_bt(b),
311 delete_elm_bt(c),
312 delete_elm_bt(d),
313 fail
314 ; get_and_remove_max_value(MaxVal9),
315 MaxVal9 == d,
316 get_and_remove_max_value(MaxVal10),
317 MaxVal10 == c,
318 get_and_remove_max_value(MaxVal11),
319 MaxVal11 == a,
320 get_and_remove_max_value(MaxVal12),
321 MaxVal12 == b
322 ).