YAP 7.1.0
•All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
yap_rl.c
1/*******************************************************************************************
2
3Copyright (C) 2004,2005,2006,2007,2008 (Nuno A. Fonseca) <nuno.fonseca@gmail.com>
4
5This program is free software; you can redistribute it and/or
6modify it under the terms of the GNU General Public License
7as published by the Free Software Foundation; either
8version 2 of the License, or (at your option) any later
9version.
10
11This program is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with this program; if not, write to the Free Software
18Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
20
21Last rev: $Id: yap_rl.c,v 1.1 2008-03-26 23:05:22 nunofonseca Exp $
22**************************************************************************/
23
24#include <time.h>
25#include <stdio.h>
26
27#include "range_list.h"
28#include <YapInterface.h>
29
30#define IDTYPE YAP_Int
31#define PTR2ID(ptr) ((IDTYPE)(ptr))
32#define ID2PTR(id) ((RL_Tree*)(id))
33
34
35/* ############################################################ */
36unsigned long int memory_usage=0;
37unsigned long int tree_mem=0;
38
39#define STORE_TREE_SIZE(tree) tree_mem=tree->mem_alloc
40#define UPDATE_MEM_USAGE(tree) memory_usage+=(tree->mem_alloc>0?tree->mem_alloc-tree_mem:0)
41#define FREE_MEM_USAGE(tree) (memory_usage-=tree->mem_alloc)
42#define ADD_MEM_USAGE(tree) (memory_usage+=tree->mem_alloc)
43
46static
47YAP_Bool
48rl_new(void) {
49 YAP_Term t1=YAP_Deref(YAP_ARG1);
50 YAP_Term t2=YAP_Deref(YAP_ARG2);
51 RL_Tree* new_tree;
52 IDTYPE newid;
53
54 // Check args
55 if (!YAP_IsIntTerm(t1) || !YAP_IsVarTerm(t2)) {
56 fprintf(stderr,"Error in rl_new arguments\n");
57 return(FALSE);
58 }
59 //
60 new_tree=new_rl(YAP_IntOfTerm(t1));
61 if(new_tree==NULL) {
62 fprintf(stderr,"Error creating new rl.");
63 return (FALSE);
64 }
65 //printf("New rl %d %p--%u\n",PTR2ID(new_tree),new_tree,(int)new_tree,YAP_IntOfTerm(t1));
66 // return reference
67 newid=YAP_MkIntTerm(PTR2ID(new_tree));
68 if(!YAP_Unify(YAP_Deref(YAP_ARG2),newid))
69 return (FALSE);
70
71 return(TRUE);
72}
73/* @pred rl_new( ? OldTree, ? NewTree).
74 *
75 * copy from old tree to mew tree
76 */
77static
78YAP_Bool
79rl_copy(void) {
80 YAP_Term t1=YAP_Deref(YAP_ARG1); // src
81 YAP_Term t2=YAP_Deref(YAP_ARG2); // dest
82 RL_Tree* new_tree;
83 IDTYPE id1,newid;
84 RL_Tree* tree;
85
86 // Check args
87 if (!YAP_IsIntTerm(t1))
88 return(FALSE);
89 if (!YAP_IsVarTerm(t2))
90 return(FALSE);
91 //
92 id1=YAP_IntOfTerm(t1);
93 tree=ID2PTR(id1);
94 new_tree=copy_rl(tree);
95
96 if(new_tree==NULL) {
97 fprintf(stderr,"Error creating new rl.");
98 return (FALSE);
99 }
100 //
101#ifdef STATS
102 ADD_MEM_USAGE(new_tree);
103#endif
104
105 // return list reference
106 newid=YAP_MkIntTerm(PTR2ID(new_tree));
107 if(!YAP_Unify(YAP_Deref(YAP_ARG2),newid))
108 return (FALSE);
109 return(TRUE);
110}
115static
116YAP_Bool
117rl_size(void) {
118
119 YAP_Term t1=YAP_Deref(YAP_ARG1),t_size;
120 IDTYPE id;
121 RL_Tree* tree;
122 unsigned int size;
123
124 if (YAP_IsVarTerm(t1))
125 return(FALSE);
126
127 id = YAP_IntOfTerm(t1);
128 tree=ID2PTR(id);
129
130 size=tree->size*sizeof(RL_Node)+sizeof(RL_Tree);
131 t_size=YAP_MkIntTerm(size);
132 if(!YAP_Unify(YAP_ARG2,t_size) )
133 return (FALSE);
134
135 return(TRUE);
136}
141static
142YAP_Bool
143rl_mem_usage(void) {
144
145 YAP_Term t1=YAP_Deref(YAP_ARG1);
146
147 if(!YAP_Unify(t1,YAP_MkIntTerm(memory_usage)) )
148 return (FALSE);
149
150 return(TRUE);
151}
152
155static
156YAP_Bool
157rl_free(void) {
158
159 YAP_Term t1=YAP_Deref(YAP_ARG1);
160 IDTYPE id;
161 RL_Tree* tree;
162
163 // Check args
164 if (YAP_IsVarTerm(t1))
165 return(FALSE);
166
167 id=YAP_IntOfTerm(t1);
168 tree=ID2PTR(id);
169#ifdef STATS
170 FREE_MEM_USAGE(tree);
171#endif
172
173 free_rl(tree);
174
175 return (TRUE);
176}
177
178/*
179 * @pred rl_set_in( + Tree, +Value )
180 *
181 */
182static
183YAP_Bool
184rl_set_in(void) {
185
186 YAP_Term t1=YAP_Deref(YAP_ARG1);
187 YAP_Term t2=YAP_Deref(YAP_ARG2);
188 IDTYPE id;
189 NUM val;
190 RL_Tree *tree;
191
192 // Check args
193 if (YAP_IsVarTerm(t1) || YAP_IsVarTerm(t2) )
194 return(FALSE);
195
196 id = YAP_IntOfTerm(t1);
197 val = YAP_IntOfTerm(t2);
198
199 tree=ID2PTR(id);
200
201#ifdef STATS
202 STORE_TREE_SIZE(tree);
203 set_in_rl(tree,val,IN);
204 UPDATE_MEM_USAGE(tree);
205#else
206 set_in_rl(tree,val,IN);
207#endif
208 return (TRUE);
209}
210
211#ifdef UNUSED
212 /*
213 *
214 *
215 */
216static
217YAP_Bool
218rl_in(void) {
219
220 YAP_Term t1=YAP_Deref(YAP_ARG1);
221 YAP_Term t2=YAP_Deref(YAP_ARG2);
222 IDTYPE id;
223 NUM val;
224 RL_Tree *tree;
225
226 // Check args
227 if (YAP_IsVarTerm(t1) || YAP_IsVarTerm(t2) )
228 return(FALSE);
229
230 id = YAP_IntOfTerm(t1);
231 val = YAP_IntOfTerm(t2);
232
233 tree=ID2PTR(id);
234
235 if ( in_rl(tree,val) )
236 return (TRUE);
237 return (FALSE);
238}
239#endif
240
241/*@pred rl_free( ? Tree).
242 *
243 *
244 */
245static
246YAP_Bool
247rl_set_out(void) {
248
249 YAP_Term t1=YAP_Deref(YAP_ARG1);
250 YAP_Term t2=YAP_Deref(YAP_ARG2);
251 IDTYPE id;
252 NUM val;
253 RL_Tree *tree;
254
255 // Check args
256 if (YAP_IsVarTerm(t1) || YAP_IsVarTerm(t2) )
257 return(FALSE);
258
259 id = YAP_IntOfTerm(t1);
260 val = YAP_IntOfTerm(t2);
261
262 tree=ID2PTR(id);
263#ifdef STATS
264 STORE_TREE_SIZE(tree);
265 set_in_rl(tree,val,OUT);
266 UPDATE_MEM_USAGE(tree);
267#else
268 set_in_rl(tree,val,OUT);
269#endif
270 return (TRUE);
271}
272/*
273 *
274 *
275 */
276static
277YAP_Bool
278rl_freeze(void) {
279
280 YAP_Term t1=YAP_Deref(YAP_ARG1);
281 IDTYPE id;
282 RL_Tree *tree;
283
284 // Check args
285 if (YAP_IsVarTerm(t1) )
286 return(FALSE);
287
288 id = YAP_IntOfTerm(t1);
289 tree=ID2PTR(id);
290
291
292#ifdef STATS
293 STORE_TREE_SIZE(tree);
294 freeze_rl(tree);
295 UPDATE_MEM_USAGE(tree);
296#else
297 freeze_rl(tree);
298#endif
299
300 return (TRUE);
301}
307static
308YAP_Bool
309rl_set_all_in(void) {
310
311 YAP_Term t1=YAP_Deref(YAP_ARG1);
312 IDTYPE id;
313 RL_Tree *tree;
314
315 // Check args
316 if (YAP_IsVarTerm(t1) )
317 return(FALSE);
318
319 id = YAP_IntOfTerm(t1);
320 tree=ID2PTR(id);
321
322
323#ifdef STATS
324 STORE_TREE_SIZE(tree);
325 rl_all(tree,IN);
326 freeze_rl(tree);
327 UPDATE_MEM_USAGE(tree);
328#else
329 rl_all(tree,IN);
330 freeze_rl(tree);
331#endif
332
333 return (TRUE);
334}
339static
340YAP_Bool
341rl_print(void) {
342
343 YAP_Term t1=YAP_Deref(YAP_ARG1);
344 IDTYPE id;
345 RL_Tree *tree;
346
347 // Check args
348 if (YAP_IsVarTerm(t1) ) {
349 fprintf(stderr,"Error printing tree..");
350 return(FALSE);
351 }
352 id = YAP_IntOfTerm(t1);
353 tree=ID2PTR(id);
354
355 display_tree(tree);
356
357 return (TRUE);
358}
359
360
361/* ==============================================================================
362 *
363 *
364 */
365typedef struct {
366 YAP_Term last_solution; /* the last solution */
367} yap_back_data_type;
368
369yap_back_data_type *back_data;
370
371/*
372 *
373 *
374 */
375static
376YAP_Bool
377rl_b_in2(void) {
378
379 YAP_Term t1=YAP_Deref(YAP_ARG1);
380 IDTYPE id;
381 NUM val;
382 RL_Tree *tree;
383
384 YAP_PRESERVED_DATA(back_data,yap_back_data_type);
385 id = YAP_IntOfTerm(t1);
386 tree=ID2PTR(id);
387 val=YAP_IntOfTerm(back_data->last_solution);
388 val=rl_next_in_bigger(tree,val);
389 if ( val > 0 && YAP_Unify(YAP_Deref(YAP_ARG2),YAP_MkIntTerm(val))) {
390 back_data->last_solution=YAP_MkIntTerm(val);
391 return TRUE;
392 }
393 YAP_cut_fail();
394 return (FALSE);
395}
396static
397YAP_Bool
398rl_b_in1(void) {
399
400 YAP_Term t1=YAP_Deref(YAP_ARG1);
401 YAP_Term t2=YAP_Deref(YAP_ARG2);
402 IDTYPE id;
403 NUM val;
404 RL_Tree *tree;
405
406 // Check args
407 if (!YAP_IsIntTerm(t1)) {
408 YAP_cut_fail();
409 return(FALSE);
410 }
411 if ( YAP_IsVarTerm(t2) ) {
412 // return all in through backtracking
413 YAP_PRESERVE_DATA(back_data,yap_back_data_type);
414 back_data->last_solution = YAP_MkIntTerm(0);
415 return rl_b_in2();
416 } else {
417 id = YAP_IntOfTerm(t1);
418 tree=ID2PTR(id);
419 val = YAP_IntOfTerm(t2);
420 if ( in_rl(tree,val) ) {
421 YAP_cut_succeed();
422 return (TRUE);
423 }
424 YAP_cut_fail();
425 return (FALSE);
426 }
427}
428/* ******************************************************* */
429void init_rl(void);
430
431void init_rl(void){
432
433
434 YAP_UserCPredicate("rl_new", rl_new,2); // Maximum -> RangeID
435 YAP_UserCPredicate("rl_free", rl_free,1); // RangeId ->
436 YAP_UserCPredicate("rl_size", rl_size,2); // RangeId -> Size (in bytes)
437 YAP_UserCPredicate("rl_mem", rl_mem_usage,1); // -> TotalMemory (in bytes)
438
439 YAP_UserCPredicate("rl_copy", rl_copy,2); // RangeId -> NewRangeId
440 YAP_UserCPredicate("rl_set_out", rl_set_out,2);// RangeId x Number ->
441 YAP_UserBackCPredicate("rl_in", rl_b_in1,rl_b_in2,2,sizeof(yap_back_data_type)); // +RangeId x ?Number
442 //YAP_UserCPredicate("rl_in", rl_in,2); // RangeId x Number ->
443 YAP_UserCPredicate("rl_set_in", rl_set_in,2); // RangeIdxNumber ->
444 YAP_UserCPredicate("rl_set_all_in", rl_set_all_in,1); // RangeId ->
445
446 YAP_UserCPredicate("rl_print", rl_print,1); // RangeId ->
447
448 YAP_UserCPredicate("rl_freeze", rl_freeze,1); // RangeId
449
450 // fprintf(stderr,"Range list module succesfully loaded.");
451 //fflush(stderr);
452}
YAP_Deref
#define YAP_Deref(t)
X_API macro.
Definition: YapInterface.h:86
range_list.h
range list core data-structures
rl_struct
Definition: range_list.h:127
yap_back_data_type
Definition: yap_rl.c:365
RL_Node
Definition: range_list.h:117