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		elm_exists/1,
8		is_empty/0,
9		get_max_value/1,
10		get_max_priority/1,
11		get_priority_of/2,
12		get_priority_of_silent_fail/2,
13		get_and_remove_max_value/1,
14		get_and_remove_max_value_bt/1,
15		update/2,
16		update_bt/2,
17		inc_priority_of/2,
18		inc_priority_of_bt/2,
19		dec_priority_of/2,
20		dec_priority_of_bt/2,
21		mult_priority_of/2,
22		mult_priority_of_bt/2,
23		mult_priority_of_all/1,
24		set_maintain_update_order/1]).
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		).