1		% (c) 2009-2017 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		mycounter_set/1, mycounter_dec/1,
18		test/0, bench/0]).
19
20
21		/* the interface to a heap global variable stored and maintained in C */
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		foreign(mycounter_set,mycounter_set(+integer)). % set a counter to some value
39		foreign(mycounter_dec,mycounter_dec([-integer])). % decrement and return value
40
41		% to do: also implement a pop from end to replace the not_all_z/1 relation
42		% for mixed depth-first, breadth-first traversal
43
44		foreign_resource(myheap,
45		[
46		myheap_reset
47		,myheap_initialize
48		,myheap_add_node
49		,myheap_add_node_at_front
50		,myheap_add_node_at_end
51		,myheap_add_node_random
52		,myheap_size
53		,myheap_empty
54		,myheap_top_id
55		,myheap_top_weight
56		,myheap_max_weight
57		,myheap_pop
58		,myheap_pop_max
59		,myheap_portray
60
61		,mycounter_set
62		,mycounter_dec
63		]).
64
65
66		:- dynamic loaded/0.
67
68		myheap_init :- loadfr, %print(initializing_myheap),nl,
69		myheap_initialize.
70
71		loadfr :-
72		(loaded -> true
73		; (assert(loaded),
74		%assert_dir,
75		%assert(user:library_directory(prob_home('.'))),
76		%print(loading_foreign_resource(myheap)),nl,
77		load_foreign_resource(library(myheap)))
78		).
79
80		assert_dir :- (user:library_directory('.') -> true ; assert(user:library_directory('.'))).
81
82		myheap_isempty :- myheap_empty(X),X=1.
83
84		test :- assert(user:library_directory('.')),
85		myheap_init,
86		mycounter_set(10),
87		mycounter_dec(X1), X1==9,
88		mycounter_dec(X2), X2==8,
89		myheap_add_node(22,2),
90		myheap_add_node(33,3),
91		myheap_add_node(221,2),
92		myheap_add_node_at_front(11),
93		myheap_add_node_at_front(5),
94		myheap_add_node_random(12345),
95		myheap_add_node_random(6789),
96		myheap_portray,
97		myheap_top_weight(W),
98		myheap_pop(X),
99		print(popped_pl(X:W)),nl, flush_output(user),
100		myheap_portray,
101		myheap_size(Sz),
102		print(size(Sz)),nl, flush_output(user),
103		myheap_max_weight(W2),
104		myheap_pop_max(Y),
105		print(popped_max(Y:W2)),nl, flush_output(user),
106		myheap_portray,
107		myheap_size(Sz2),
108		print(size(Sz2)),nl, flush_output(user),
109		myheap_pop(Y2),
110		print(popped_pl(Y2)),nl, flush_output(user),
111		myheap_portray,
112		myheap_empty(Y3),
113		print(empty_pl(Y3)),nl, flush_output(user),
114		myheap_top_weight(W3),
115		print(W3),nl.
116
117
118		bench :- bench(100000).
119		bench(X) :- myheap_init,
120		statistics(runtime,_),
121		add_nodes(X),
122		pop,
123		assert_nodes(X),
124		pop_nodes.
125
126		pop :- myheap_pop(P), P \= -1,!, pop.
127		pop :- print_time(pop).
128
129		add_nodes(X) :- X>0, !,myheap_add_node_at_front(X), X1 is X-1, add_nodes(X1).
130		add_nodes(_) :- print_time(add_nodes).
131
132		:- dynamic o1/1, o2/1.
133		assert_nodes(X) :- X>0, !,asserta(o1(X)),assertz(o2(X)), X1 is X-1, assert_nodes(X1).
134		assert_nodes(_) :- print_time(assert_nodes).
135
136		pop_nodes :- retract(o1(X)), !, retract(o2(X)), pop_nodes.
137		pop_nodes :- print_time(pop_nodes).
138		print_time(T) :- statistics(runtime,[_,T2]), print(T), print(' : '), print(T2), print(' ms'),nl.