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. |