1		% (c) 2009-2022 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
5		:- module(myheap, [myheap_init/0,
6		myheap_reset/0, myheap_add_node/2, myheap_add_node_at_front/1, myheap_add_node_at_end/1,
7		myheap_add_node_random/1,
8		myheap_size/1,
9		myheap_empty/1, myheap_isempty/0,
10		myheap_top_id/1, myheap_top_weight/1,
11		myheap_pop/1,
12
13		myheap_max_weight/1,
14		myheap_pop_max/1,
15		myheap_portray/0,
16
17		test/0, bench/0]).
18
19
20		/* the interface to a heap global variable stored and maintained in C */
21		% it is not used if environ(prob_myheap,false)
22
23		foreign(myheap_initialize,myheap_initialize). % initializes the data structure
24		foreign(myheap_reset,myheap_reset). % resets the heap to the empty heap; frees memory
25		foreign(myheap_add_node,myheap_add_node(+integer,+integer)). % ID, Weight
26		foreign(myheap_add_node_at_front,myheap_add_node_at_front(+integer)). % ID
27		foreign(myheap_add_node_at_end,myheap_add_node_at_end(+integer)). % ID
28		foreign(myheap_add_node_random,myheap_add_node_random(+integer)). % ID
29		foreign(myheap_size,myheap_size([-integer])).
30		foreign(myheap_empty,myheap_empty([-integer])). %return 1 if empty, 0 if non-empty
31		foreign(myheap_top_id,myheap_top_id([-integer])).
32		foreign(myheap_top_weight,myheap_top_weight([-integer])).
33		foreign(myheap_max_weight,myheap_max_weight([-integer])).
34		foreign(myheap_pop,myheap_pop([-integer])). % pops the ID with minimum Weight, -1 if empty
35		foreign(myheap_pop_max,myheap_pop_max([-integer])). % pops the ID with maximum Weight, -1 if empty
36		foreign(myheap_portray,myheap_portray). % pops the ID with maximum Weight, -1 if empty
37
38		% to do: also implement a pop from end to replace the not_all_z/1 relation
39		% for mixed depth-first, breadth-first traversal
40
41		foreign_resource(myheap,
42		[
43		myheap_reset
44		,myheap_initialize
45		,myheap_add_node
46		,myheap_add_node_at_front
47		,myheap_add_node_at_end
48		,myheap_add_node_random
49		,myheap_size
50		,myheap_empty
51		,myheap_top_id
52		,myheap_top_weight
53		,myheap_max_weight
54		,myheap_pop
55		,myheap_pop_max
56		,myheap_portray
57		]).
58
59
60		:- dynamic loaded/0.
61
62		myheap_init :- loadfr, %print(initializing_myheap),nl,
63		myheap_initialize.
64
65		:- use_module('../../src/pathes', []). % set up library search paths
66		:- use_module(probsrc(pathes_lib),[safe_load_foreign_resource/2]).
67
68		loadfr :-
69		(loaded -> true
70		; assertz(loaded),
71		%assert_dir,
72		%assertz(user:library_directory(prob_home('.'))),
73		safe_load_foreign_resource(myheap,myheap)
74		).
75
76
77		%:- dynamic user:library_directory/1.
78		%assert_dir :- (user:library_directory('.') -> true ; assertz(user:library_directory('.'))).
79
80		myheap_isempty :- myheap_empty(X),X=1.
81
82		test :- assertz(user:library_directory('.')),
83		myheap_init,
84		myheap_add_node(22,2),
85		myheap_add_node(33,3),
86		myheap_add_node(221,2),
87		myheap_add_node_at_front(11),
88		myheap_add_node_at_front(5),
89		myheap_add_node_random(12345),
90		myheap_add_node_random(6789),
91		myheap_portray,
92		myheap_top_weight(W),
93		myheap_pop(X),
94		print(popped_pl(X:W)),nl, flush_output(user),
95		myheap_portray,
96		myheap_size(Sz),
97		print(size(Sz)),nl, flush_output(user),
98		myheap_max_weight(W2),
99		myheap_pop_max(Y),
100		print(popped_max(Y:W2)),nl, flush_output(user),
101		myheap_portray,
102		myheap_size(Sz2),
103		print(size(Sz2)),nl, flush_output(user),
104		myheap_pop(Y2),
105		print(popped_pl(Y2)),nl, flush_output(user),
106		myheap_portray,
107		myheap_empty(Y3),
108		print(empty_pl(Y3)),nl, flush_output(user),
109		myheap_top_weight(W3),
110		print(W3),nl.
111
112
113		bench :- bench(100000).
114		bench(X) :- myheap_init,
115		statistics(runtime,_),
116		add_nodes(X),
117		pop,
118		assert_nodes(X),
119		pop_nodes.
120
121		pop :- myheap_pop(P), P \= -1,!, pop.
122		pop :- print_time(pop).
123
124		add_nodes(X) :- X>0, !,myheap_add_node_at_front(X), X1 is X-1, add_nodes(X1).
125		add_nodes(_) :- print_time(add_nodes).
126
127		:- dynamic o1/1, o2/1.
128		assert_nodes(X) :- X>0, !,asserta(o1(X)),assertz(o2(X)), X1 is X-1, assert_nodes(X1).
129		assert_nodes(_) :- print_time(assert_nodes).
130
131		pop_nodes :- retract(o1(X)), !, retract(o2(X)), pop_nodes.
132		pop_nodes :- print_time(pop_nodes).
133		print_time(T) :- statistics(runtime,[_,T2]), print(T), print(' : '), print(T2), print(' ms'),nl.