1		% (c) 2009-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
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/1.
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(R) -> R=success
70		; assertz(loaded(failure_to_load)),
71		%assert_dir,
72		%assertz(user:library_directory(prob_home('.'))),
73		safe_load_foreign_resource(myheap,myheap),
74		retractall(loaded(_)),
75		assertz(loaded(success))
76		).
77
78
79		%:- dynamic user:library_directory/1.
80		%assert_dir :- (user:library_directory('.') -> true ; assertz(user:library_directory('.'))).
81
82		myheap_isempty :- myheap_empty(X),X=1.
83
84		test :- assertz(user:library_directory('.')),
85		myheap_init,
86		myheap_add_node(22,2),
87		myheap_add_node(33,3),
88		myheap_add_node(221,2),
89		myheap_add_node_at_front(11),
90		myheap_add_node_at_front(5),
91		myheap_add_node_random(12345),
92		myheap_add_node_random(6789),
93		myheap_portray,
94		myheap_top_weight(W),
95		myheap_pop(X),
96		print(popped_pl(X:W)),nl, flush_output(user),
97		myheap_portray,
98		myheap_size(Sz),
99		print(size(Sz)),nl, flush_output(user),
100		myheap_max_weight(W2),
101		myheap_pop_max(Y),
102		print(popped_max(Y:W2)),nl, flush_output(user),
103		myheap_portray,
104		myheap_size(Sz2),
105		print(size(Sz2)),nl, flush_output(user),
106		myheap_pop(Y2),
107		print(popped_pl(Y2)),nl, flush_output(user),
108		myheap_portray,
109		myheap_empty(Y3),
110		print(empty_pl(Y3)),nl, flush_output(user),
111		myheap_top_weight(W3),
112		print(W3),nl.
113
114
115		bench :- bench(100000).
116		bench(X) :- myheap_init,
117		statistics(runtime,_),
118		add_nodes(X),
119		pop,
120		assert_nodes(X),
121		pop_nodes.
122
123		pop :- myheap_pop(P), P \= -1,!, pop.
124		pop :- print_time(pop).
125
126		add_nodes(X) :- X>0, !,myheap_add_node_at_front(X), X1 is X-1, add_nodes(X1).
127		add_nodes(_) :- print_time(add_nodes).
128
129		:- dynamic o1/1, o2/1.
130		assert_nodes(X) :- X>0, !,asserta(o1(X)),assertz(o2(X)), X1 is X-1, assert_nodes(X1).
131		assert_nodes(_) :- print_time(assert_nodes).
132
133		pop_nodes :- retract(o1(X)), !, retract(o2(X)), pop_nodes.
134		pop_nodes :- print_time(pop_nodes).
135		print_time(T) :- statistics(runtime,[_,T2]), print(T), print(' : '), print(T2), print(' ms'),nl.