1 /****************************************************************************************/
2 /* */
3 /* vinci_memory.c */
4 /* */
5 /****************************************************************************************/
6 /* */
7 /* Authors: Benno Bueeler (bueeler@ifor.math.ethz.ch) */
8 /* and */
9 /* Andreas Enge (enge@ifor.math.ethz.ch) */
10 /* Institute for Operations Research */
11 /* Swiss Federal Institute of Technology Zurich */
12 /* Switzerland */
13 /* */
14 /* Last Changes: February 4, 2001 */
15 /* */
16 /****************************************************************************************/
17 /* */
18 /* some functions needed globally for the maintenance of the dynamic data structures */
19 /* */
20 /****************************************************************************************/
21
22 #include "vinci.h"
23
24 /****************************************************************************************/
25 /* memory allocation */
26 /****************************************************************************************/
27
my_malloc(long int size)28 void *my_malloc (long int size)
29 /* works exactly like malloc, but keeps trace of the used memory in the statistical */
30 /* variables and eventually frees the memory reserve */
31
32 { void *pointer;
33
34 pointer = malloc (size);
35
36 if (pointer == NULL)
37 {
38 fprintf (stderr, "\n***** ERROR: Out of memory\n");
39 exit (0);
40 }
41 else
42 {
43 #ifdef STATISTICS
44 Stat_ActualMem += size;
45 if (Stat_ActualMem > Stat_MaxMem)
46 Stat_MaxMem = Stat_ActualMem;
47 #endif
48 }
49
50 return pointer;
51 }
52
53 /****************************************************************************************/
54
my_realloc(void * pointer,long int new_size,long int size_diff)55 void *my_realloc (void *pointer, long int new_size, long int size_diff)
56 /* works exactly like realloc, but keeps trace of the used memory in the statistical */
57 /* variables and eventually frees the memory reserve */
58 /* size_diff is the difference between the new and the old size (usually positive */
59 /* for enlargements) */
60
61 {
62 pointer = realloc (pointer, new_size);
63
64 if (pointer == NULL)
65 {
66 fprintf (stderr, "\n***** ERROR: Out of memory");
67 exit (0);
68 }
69 else
70 {
71 #ifdef STATISTICS
72 Stat_ActualMem += size_diff;
73 if (Stat_ActualMem > Stat_MaxMem)
74 Stat_MaxMem = Stat_ActualMem;
75 #endif
76 }
77
78 return pointer;
79 }
80
81 /****************************************************************************************/
82
my_free(void * pointer,long int size)83 void my_free (void *pointer, long int size)
84 /* frees the memory space used by pointer and keeps track of the freed space in the */
85 /* statistical variables */
86
87 {
88 free (pointer);
89 #ifdef STATISTICS
90 Stat_ActualMem -= size;
91 #endif
92 }
93
94 /****************************************************************************************/
95
create_vertex()96 T_Vertex *create_vertex ()
97 /* create a new vertex */
98
99 {
100 static int actualnumber = 0;
101 T_Vertex *v;
102
103 v = (T_Vertex *) my_malloc (sizeof (T_Vertex));
104 v -> coords = (real *) my_malloc (G_d * sizeof (real));
105 v -> no = ++actualnumber;
106
107 return v;
108 }
109
110 /****************************************************************************************/
111
free_vertex(T_Vertex * v)112 void free_vertex (T_Vertex *v)
113 /* frees the memory space needed by the dynamic components of v and v itself */
114
115 {
116 my_free (v -> coords, G_d * sizeof (real));
117 my_free (v, sizeof (T_Vertex));
118 }
119
120 /****************************************************************************************/
121
create_hyperplanes()122 void create_hyperplanes ()
123 /* reserves memory space for the global variable G_Hyperplanes; G_m and G_d must be */
124 /* set correctly */
125
126 { int i;
127
128 G_Hyperplanes = (real **) my_malloc (G_m * sizeof (real *));
129
130 for (i = 0; i < G_m; i++)
131 G_Hyperplanes [i] = (real *) my_malloc ((G_d + 1) * sizeof (real));
132 /* The last entry is needed for the right hand side. */
133
134 }
135
136 /****************************************************************************************/
137
free_hyperplanes()138 void free_hyperplanes ()
139 /* frees the memory space needed by the global variable G_Hyperplanes; G_m must be */
140 /* set correctly */
141
142 { int i;
143
144 for (i = 0; i < G_m; i++)
145 my_free (G_Hyperplanes [i], (G_d + 1) * sizeof (real));
146 my_free (G_Hyperplanes, G_m * sizeof (real *));
147 }
148
149 /****************************************************************************************/
150
create_incidence()151 void create_incidence ()
152 /* reserves memory space for the global variable G_Incidence; G_m and G_n must be */
153 /* set correctly */
154
155 { int i;
156
157 G_Incidence = (boolean **) my_malloc (G_n * sizeof (boolean *));
158 for (i = 0; i < G_n; i++)
159 G_Incidence [i] = (boolean *) my_malloc (G_m * sizeof (boolean));
160 }
161
162 /****************************************************************************************/
163
free_incidence()164 void free_incidence ()
165 /* frees the memory space needed by the global variable G_Incidence; G_m and G_n */
166 /* must be set correctly */
167
168 { int i;
169
170 for (i = 0; i < G_n; i++)
171 my_free (G_Incidence [i], G_m * sizeof (boolean));
172 my_free (G_Incidence, G_n * sizeof (boolean *));
173 }
174
175 /****************************************************************************************/
176
create_faces()177 T_VertexSet *create_faces ()
178 /* reserves memory space for the variable where the faces are stored and fills the */
179 /* array with empty sets; G_d must be set correctly */
180
181 { int i;
182 T_VertexSet *face;
183
184 face = (T_VertexSet *) my_malloc ((G_d + 1) * sizeof (T_VertexSet));
185 for (i = 0; i <= G_d; i++)
186 face [i] = create_empty_set ();
187
188 return face;
189 }
190
191 /****************************************************************************************/
192
free_faces(T_VertexSet * face)193 void free_faces (T_VertexSet *face)
194 /* frees the memory space needed by the variable face and the sets of the array; */
195 /* G_d must be set correctly */
196
197 { int i;
198
199 for (i = 0; i <= G_d; i++)
200 free_set (face [i]);
201 my_free (face, (G_d + 1) * sizeof (T_VertexSet));
202 }
203
204 /****************************************************************************************/
205
create_basis()206 rational ***create_basis ()
207 /* reserves memory space for an array of matrices; in each dimension d from 1 to G_d */
208 /* a matrix of dimension (d+1) X G_d is created; G_d must be set correctly. */
209
210 { int d;
211 rational ***basis;
212
213 basis = (rational ***) my_malloc ((G_d + 1) * sizeof (rational **));
214 for (d = 1; d <= G_d; d++)
215 basis [d] = create_matrix (d+1, G_d);
216
217 return basis;
218 }
219
220 /****************************************************************************************/
221
free_basis(rational *** basis)222 void free_basis (rational *** basis)
223 /* frees the memory space used by the array of matrices and all of the matrices */
224
225 { int d;
226
227 for (d = 1; d <= G_d; d++)
228 free_matrix (basis [d], d+1, G_d);
229
230 my_free (basis, (G_d + 1) * sizeof (rational **));
231 }
232
233 /****************************************************************************************/
234
create_fact()235 rational *create_fact ()
236 /* reserves memory space for the variable where factorials are stored; G_d must be */
237 /* set correctly */
238
239 { rational *fact;
240
241 fact = (rational *) my_malloc ((G_d + 1) * sizeof (rational));
242
243 return fact;
244 }
245
246 /****************************************************************************************/
247
free_fact(rational * fact)248 void free_fact (rational *fact)
249 /* frees the memory space needed by the variable fact */
250
251 {
252 my_free (fact, (G_d + 1) * sizeof (rational));
253 }
254
255 /****************************************************************************************/
256
create_vector()257 rational *create_vector ()
258 /* reserves memory space for a vector with G_d entries; G_d must be set correctly */
259
260 { rational *v;
261
262 v = (rational *) my_malloc (G_d * sizeof (rational));
263
264 return v;
265 }
266
267 /****************************************************************************************/
268
free_vector(rational * v)269 void free_vector (rational *v)
270 /* frees the memory space needed by the vector v */
271
272 {
273 my_free (v, G_d * sizeof (rational));
274 }
275
276 /****************************************************************************************/
277
create_int_vector(int n)278 int *create_int_vector (int n)
279 /* reserves memory space for a vector with n entries */
280
281 { int *v;
282
283 v = (int *) my_malloc (n * sizeof (int));
284
285 return v;
286 }
287
288 /****************************************************************************************/
289
free_int_vector(int * v,int n)290 void free_int_vector (int *v, int n)
291 /* frees the memory space needed by the vector v of length n */
292
293 {
294 my_free (v, n * sizeof (int));
295 }
296
297 /****************************************************************************************/
298
create_matrix(int m,int n)299 rational **create_matrix (int m, int n)
300 /* reserves memory space for an mXn matrix */
301
302 { int i;
303 rational **A;
304
305 A = (rational **) my_malloc (m * sizeof (rational *));
306 for (i = 0; i < m; i++)
307 A [i] = (rational *) my_malloc (n * sizeof (rational));
308
309 return A;
310 }
311
312 /****************************************************************************************/
313
redim_matrix(rational *** A,int m_alt,int m_neu,int n)314 void redim_matrix (rational ***A, int m_alt, int m_neu, int n)
315 /* resizes the matrix A to m_neu rows */
316
317 { int i;
318
319 (*A) = (rational **) my_realloc (*A, m_neu * sizeof (rational *),
320 (m_neu - m_alt) * sizeof (rational *));
321 if (*A == NULL)
322 { fprintf (stderr, "\n***** ERROR: Out of memory in 'redim_matrix.'");
323 exit (0);
324 }
325
326 for (i = m_alt; i < m_neu; i++)
327 {
328 (*A) [i] = (rational *) my_malloc (n * sizeof (rational));
329 }
330
331 }
332
333 /****************************************************************************************/
334
free_matrix(rational ** A,int m,int n)335 void free_matrix (rational **A, int m, int n)
336 /* frees the memory space needed by the matrix A */
337
338 { int i;
339
340 for (i = 0; i < m; i++)
341 my_free (A [i], n * sizeof (rational));
342 my_free (A, m * sizeof (rational *));
343 }
344
345 /****************************************************************************************/
346
create_key(T_Key * key,int key_choice)347 void create_key (T_Key *key, int key_choice)
348 /* creates the dynamic parts of the key; G_d must be set correctly */
349
350 {
351 if (key_choice == KEY_PLANES_VAR)
352 {
353 key -> hypervar.hyperplanes =
354 (T_LassInt *) my_malloc ((G_Storage + 2) * sizeof (T_LassInt));
355 key -> hypervar.variables =
356 (T_LassInt *) my_malloc ((G_Storage + 2) * sizeof (T_LassInt));
357 }
358 }
359
360 /****************************************************************************************/
361
free_key(T_Key key,int key_choice)362 void free_key (T_Key key, int key_choice)
363 /* frees the dynamic parts of the key */
364
365 {
366 if (key_choice == KEY_PLANES_VAR)
367 {
368 my_free (key.hypervar.hyperplanes, (G_Storage + 2) * sizeof (T_LassInt));
369 my_free (key.hypervar.variables, (G_Storage + 2) * sizeof (T_LassInt));
370 }
371 }
372
373 /****************************************************************************************/
374 /* statistical routines */
375 /****************************************************************************************/
376
377 #ifdef STATISTICS
378
init_statistics()379 void init_statistics ()
380 /* initializes the statistical variables */
381
382 { int i;
383
384 Stat_Count = 0;
385 Stat_Smallest = 1e199;
386 Stat_Biggest = -1e199;
387 for (i = 0; i < STAT_BIGGEST_EXP - STAT_SMALLEST_EXP + 3; i++)
388 { Stat_CountPos [i] = 0;
389 Stat_CountNeg [i] = 0;
390 }
391
392 Stat_CountStored = (unsigned int *) my_malloc ((G_d - 1) * sizeof (unsigned int));
393 Stat_CountRetrieved = (unsigned int *) my_malloc ((G_d - 1) * sizeof (unsigned int));
394
395 for (i = 0; i < G_d - 1; i++)
396 Stat_CountStored [i] = Stat_CountRetrieved [i] = 0;
397
398 Stat_CountShifts = 0;
399 }
400
401 /****************************************************************************************/
402
update_statistics(rational volume)403 void update_statistics (rational volume)
404 /* The input parameter is a newly computed partial volume, i. e. a simplex volume or */
405 /* Lawrence's formula evaluated at one vertex. The function should be called after */
406 /* each simplex computation or evaluation of Lawrence's formula. */
407
408 { int sign = 1; /* the sign of the volume */
409 char s_volume [30]; /* the absolute value of the volume as a string */
410 int pos_e; /* position of the letter 'e' in s_volume */
411 char s_exponent [6]; /* the exponent of volume as a string */
412 int exponent_length, exponent;
413
414 if (volume < 0) sign = -1;
415
416 Stat_Count ++;
417 if (volume > Stat_Biggest)
418 Stat_Biggest = volume;
419 if (volume < Stat_Smallest)
420 Stat_Smallest = volume;
421
422 /* determine the size class of the simplex */
423 sprintf (s_volume, "%28.20e", fabs (volume));
424 pos_e = strcspn (s_volume, "e");
425 exponent_length = strlen (s_volume) - pos_e;
426 memcpy (s_exponent, & (s_volume [pos_e + 1]), exponent_length);
427 exponent = atoi (s_exponent);
428
429 if (sign == 1)
430 { if (exponent < STAT_SMALLEST_EXP)
431 Stat_CountPos [0] ++;
432 else if (exponent > STAT_BIGGEST_EXP)
433 Stat_CountPos [STAT_BIGGEST_EXP - STAT_SMALLEST_EXP + 2] ++;
434 else
435 Stat_CountPos [exponent - STAT_SMALLEST_EXP + 1] ++;
436 }
437 else
438 { if (exponent < STAT_SMALLEST_EXP)
439 Stat_CountNeg [0] ++;
440 else if (exponent > STAT_BIGGEST_EXP)
441 Stat_CountNeg [STAT_BIGGEST_EXP - STAT_SMALLEST_EXP + 2] ++;
442 else
443 Stat_CountNeg [exponent - STAT_SMALLEST_EXP + 1] ++;
444 }
445
446 #ifdef RATIONAL
447 if (Stat_Count % 1000 == 0) printf ("\n%10i partial volumes computed.", Stat_Count);
448 #else
449 if (Stat_Count % 100000 == 0) printf ("\n%10i partial volumes computed.", Stat_Count);
450 #endif
451 }
452
453 /****************************************************************************************/
454
free_statistics()455 void free_statistics ()
456
457 {
458 free (Stat_CountStored);
459 free (Stat_CountRetrieved);
460 }
461
462 #endif
463
464 /****************************************************************************************/
465 /* routines for storing intermediate volumes in balanced trees (avl-trees) */
466 /****************************************************************************************/
467
compare_key(T_Key key1,T_Key key2,int key_choice)468 static int compare_key (T_Key key1, T_Key key2, int key_choice)
469 /* compares key1 with key2; if key1 is smaller, -1 is returned, if key1 is bigger +1 */
470 /* and if both are equal 0. key_choice determines which component of the key is */
471 /* relevant for comparing. */
472
473 { int i;
474 T_LassInt *p1, *p2;
475
476 switch (key_choice)
477 {
478 case KEY_VERTICES:
479 if (key1.vertices.d < key2.vertices.d) return -1;
480 else if (key1.vertices.d > key2.vertices.d) return 1;
481 else /* both volumes are for the same dimension */
482 if (key1.vertices.set.lastel < key2.vertices.set.lastel) return -1;
483 else if (key1.vertices.set.lastel > key2.vertices.set.lastel) return 1;
484 else
485 { /* both sets have the same cardinality */
486 for (i=0; i <= key1.vertices.set.lastel; i++)
487 if (key1.vertices.set.loe [i] -> no < key2.vertices.set.loe [i] -> no)
488 return -1;
489 else if (key1.vertices.set.loe [i] -> no > key2.vertices.set.loe [i] -> no)
490 return 1;
491 }
492 return 0;
493 break;
494 case KEY_PLANES_VAR:
495 /*
496 for (i=0; ; i++)
497 if (key1.hypervar.hyperplanes [i] < key2.hypervar.hyperplanes [i])
498 return -1;
499 else if (key1.hypervar.hyperplanes [i] > key2.hypervar.hyperplanes [i])
500 return 1;
501 else if (key1.hypervar.hyperplanes [i] > G_m) return 0;
502 */
503 for (p1 = key1.hypervar.hyperplanes, p2 = key2.hypervar.hyperplanes;;
504 p1++, p2++)
505 if ((*p1) < (*p2)) return -1;
506 else if ((*p1) > (*p2)) return 1;
507 else if ((*p1) > G_m) return 0;
508 break;
509 }
510
511 /* to avoid warning */
512 printf ("\n*** Control reaches place where it should not be.");
513 exit (1);
514 }
515
516 /****************************************************************************************/
517
tree_out(T_Tree ** ppr,boolean * pi_balance,T_Key key,rational ** volume,T_Key ** keyfound,int key_choice)518 void tree_out (T_Tree **ppr , boolean *pi_balance, T_Key key, rational **volume,
519 T_Key **keyfound, int key_choice)
520 /* looks up the node corresponding to the variable "key" in the specified tree. If */
521 /* it is found the volume is returned via the variable of the same name. */
522 /* At the same time the found key is returned in "foundkey"; this is important for */
523 /* Lasserre, where only a part of the key is compared, but the whole key is needed */
524 /* later. */
525 /* Otherwise, a new node is created and a pointer to its volume part is returned via */
526 /* the variable "volume" so that the computed volume can be inserted by the calling */
527 /* routine. */
528 /* As in the previous routine "key_choice" determines the active part of the keys. */
529
530 { T_Tree *p1, *p2;
531 int cmp;
532
533 /* Are we grounded? If so, add the node here and set the rebalance flag, then exit. */
534 if (!*ppr)
535 {
536 (*ppr) = (T_Tree *) my_malloc (sizeof (T_Tree));
537 (*ppr) -> tree_l = NULL;
538 (*ppr) -> tree_r = NULL;
539 (*ppr) -> tree_b = 0;
540 /* copy the key into the new node */
541 create_key (&((*ppr) -> key), key_choice);
542 switch (key_choice)
543 {
544 case KEY_VERTICES:
545 (*ppr) -> key.vertices.set = duplicate_set (key.vertices.set);
546 (*ppr) -> key.vertices.d = key.vertices.d;
547 break;
548 case KEY_PLANES_VAR:
549 memcpy ((*ppr) -> key.hypervar.hyperplanes, key.hypervar.hyperplanes,
550 (G_Storage + 2) * sizeof (T_LassInt));
551 memcpy ((*ppr) -> key.hypervar.variables, key.hypervar.variables,
552 (G_Storage + 2) * sizeof (T_LassInt));
553 break;
554 }
555 (*ppr) -> vol = -1; /* to recognise that element is newly created */
556 *volume = &((*ppr) -> vol);
557 *pi_balance = TRUE;
558 return;
559 }
560
561 cmp = compare_key ((*ppr) -> key, key, key_choice);
562
563 /* if LESS, prepare to move to the left. */
564 if (cmp < 0)
565 {
566 tree_out (&((*ppr) -> tree_l), pi_balance, key, volume, keyfound, key_choice);
567 if (*pi_balance)
568 { /* left branch has grown longer */
569 switch ((*ppr) -> tree_b)
570 {
571 case 1: /* right branch WAS longer; balance is ok now */
572 /* LESS: case 1.. balance restored implicitly */
573 (*ppr) -> tree_b = 0;
574 *pi_balance = FALSE;
575 break;
576 case 0: /* balance WAS okay; now left branch longer */
577 /* LESS: case 0.. balance bad but still ok */
578 (*ppr) -> tree_b = -1;
579 break;
580 case -1: /* left branch was already too long. rebalance */
581 p1 = (*ppr) -> tree_l;
582 if (p1 -> tree_b == -1)
583 { /* LESS: single LL */
584 (*ppr) -> tree_l = p1->tree_r;
585 p1 -> tree_r = (*ppr);
586 (*ppr) -> tree_b = 0;
587 (*ppr) = p1;
588 }
589 else
590 { /* LESS: real LR */
591 p2 = p1 -> tree_r;
592 p1 -> tree_r = p2 -> tree_l;
593 p2 -> tree_l = p1;
594 (*ppr) -> tree_l = p2 -> tree_r;
595 p2 -> tree_r = (*ppr);
596 if (p2 -> tree_b == -1)
597 (*ppr) -> tree_b = 1;
598 else (*ppr) -> tree_b = 0;
599 if (p2->tree_b == 1)
600 p1 -> tree_b = -1;
601 else p1 -> tree_b = 0;
602 (*ppr) = p2;
603 }
604 (*ppr) -> tree_b = 0;
605 *pi_balance = FALSE;
606 } /* switch */
607 } /* if */
608 } /* cmp < 0 */
609
610 /* if MORE, prepare to move to the right. */
611 else if (cmp > 0)
612 {
613 tree_out (&((*ppr) -> tree_r), pi_balance, key, volume, keyfound, key_choice);
614 if (*pi_balance)
615 { /* right branch has grown longer */
616 switch ((*ppr) -> tree_b)
617 {
618 case -1: /* MORE: balance was off, fixed implicitly */
619 (*ppr) -> tree_b = 0;
620 *pi_balance = FALSE;
621 break;
622 case 0: /* MORE: balance was okay, now off but ok */
623 (*ppr)->tree_b = 1;
624 break;
625 case 1: /* MORE: balance was off, need to rebalance */
626 p1 = (*ppr) -> tree_r;
627 if (p1 -> tree_b == 1)
628 { /* MORE: single RR */
629 (*ppr) -> tree_r = p1 -> tree_l;
630 p1 -> tree_l = (*ppr);
631 (*ppr) -> tree_b = 0;
632 (*ppr) = p1;
633 }
634 else
635 { /* MORE: real RL */
636 p2 = p1 -> tree_l;
637 p1 -> tree_l = p2 -> tree_r;
638 p2 -> tree_r = p1;
639 (*ppr) -> tree_r = p2 -> tree_l;
640 p2 -> tree_l = (*ppr);
641 if (p2 -> tree_b == 1)
642 (*ppr) -> tree_b = -1;
643 else (*ppr) -> tree_b = 0;
644 if (p2 -> tree_b == -1)
645 p1 -> tree_b = 1;
646 else p1 -> tree_b = 0;
647 (*ppr) = p2;
648 }
649 (*ppr) -> tree_b = 0;
650 *pi_balance = FALSE;
651 } /* switch */
652 } /* if */
653 } /* cmp > 0 */
654
655 /* not less, not more: this is the same key! give volume back! */
656 else
657 {
658 *pi_balance = FALSE;
659 *volume = &((*ppr) -> vol);
660 *keyfound = &((*ppr) -> key);
661 }
662 }
663
664 /****************************************************************************************/
665
add_hypervar(T_LassInt hyperplane,T_LassInt variable,T_Key * key)666 void add_hypervar (T_LassInt hyperplane, T_LassInt variable, T_Key *key)
667 /* adds the specified hyperplane and variable index to the variable "key" maintain- */
668 /* ing the ascending orders; if one index is G_m+1 resp. G_d+1 it is omitted. */
669 /* For the working of the procedure it is necessary that the last array entry is */
670 /* G_m + 1 resp. G_d + 1 and that there is still some space left in the arrays. */
671 /* Attention: Only use this function if you work with the planes and variables as */
672 /* key! */
673
674 { int i, j;
675
676 if (hyperplane != G_m+1)
677 {
678 for (i = 0; (*key).hypervar.hyperplanes [i] < hyperplane; i++);
679 if ((*key).hypervar.hyperplanes [i] != hyperplane)
680 { /* insert index */
681 for (j = G_d; j > i; j--)
682 (*key).hypervar.hyperplanes [j] = (*key).hypervar.hyperplanes [j-1];
683 (*key).hypervar.hyperplanes [i] = hyperplane;
684 }
685 }
686
687 if (variable != G_d+1)
688 {
689 for (i = 0; (*key).hypervar.variables [i] < variable; i++);
690 if ((*key).hypervar.variables [i] != variable)
691 { /* insert index */
692 for (j = G_d; j > i; j--)
693 (*key).hypervar.variables [j] = (*key).hypervar.variables [j-1];
694 (*key).hypervar.variables [i] = variable;
695 }
696 }
697 }
698
699
700 /****************************************************************************************/
701
delete_hypervar(T_LassInt hyperplane,T_LassInt variable,T_Key * key)702 void delete_hypervar (T_LassInt hyperplane, T_LassInt variable, T_Key *key)
703 /* deletes the indices from the variable key; if one index is -1 it is omitted. */
704 /* Attention: Only use this function if you work with the planes and variables as */
705 /* key! */
706
707 { int i, j;
708
709 if (hyperplane != G_m+1)
710 {
711 for (i = 0; i <= G_d && (*key).hypervar.hyperplanes [i] != hyperplane; i++);
712 if (i != G_d + 1)
713 { /* index found, delete it */
714 for (j = i; (*key).hypervar.hyperplanes [j] != G_m + 1; j++)
715 (*key).hypervar.hyperplanes [j] = (*key).hypervar.hyperplanes [j+1];
716 }
717 }
718
719 if (variable != G_d+1)
720 {
721 for (i = 0; i <= G_d && (*key).hypervar.variables [i] != variable; i++);
722 if (i != G_d + 1)
723 { /* index found, delete it */
724 for (j = i; (*key).hypervar.variables [j] != G_d + 1; j++)
725 (*key).hypervar.variables [j] = (*key).hypervar.variables [j+1];
726 }
727 }
728 }
729
730 /****************************************************************************************/
731