zsolve/valuetrees.c

   1 /*
   2 4ti2 -- A software package for algebraic, geometric and combinatorial
   3 problems on linear spaces.
   4
   5 Copyright (C) 2006 4ti2 team.
   6 Main author(s): Matthias Walter.
   7
   8 This program is free software; you can redistribute it and/or
   9 modify it under the terms of the GNU General Public License
  10 as published by the Free Software Foundation; either version 2
  11 of the License, or (at your option) any later version.
  12
  13 This program is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with this program; if not, write to the Free Software
  20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21 */
  22
  23 #include "defs.h"
  24 #include "vectorarray.h"
  25 #include "indexarray.h"
  26 #include "valuetrees.h"
  27
  28 #include <assert.h>
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31
  32 //                                                                            //
  33
  34 ValueTree createValueTree(int level)
  35 {
  36         ValueTree tree = (ValueTree)malloc(sizeof(valuetree_t));
  37
  38         if (tree==NULL)
  39         {
  40                 fprintf(stderr, "Fatal Error: Could not allocate memory for ValueTree!\n");
  41                 exit(1);
  42         }
  43
  44         tree->level = level;
  45         tree->pos = NULL;
  46         tree->neg = NULL;
  47         tree->zero = NULL;
  48         tree->vectors = level<0 ? createIndexArray() : NULL;
  49
  50         return tree;
  51 }
  52
  53 //                                                                            //
  54
  55 void deleteValueTree(ValueTree tree)
  56 {
  57         ValueTreeNode node;
  58
  59         if (tree!=NULL)
  60         {
  61                 while ((node = tree->pos)!=NULL)
  62                 {
  63                         tree->pos = node->next;
  64                         deleteValueTree(node->sub);
  65                         free(node);
  66                 }
  67                 while ((node = tree->neg)!=NULL)
  68                 {
  69                         tree->neg = node->next;
  70                         deleteValueTree(node->sub);
  71                         free(node);
  72                 }
  73                 deleteValueTree(tree->zero);
  74                 deleteIndexArray(tree->vectors);
  75                 free(tree);
  76         }
  77 }
  78
  79 //                                                                            //
  80
  81 void splitValueTree(ZSolveContext ctx, ValueTree tree, int start)
  82 {
  83         int i, compo, value;
  84         bool pos, neg, zero;
  85         ValueTreeNode node, temp;
  86
  87         if (!tree || tree->level>=0)
  88                 return;
  89
  90         assert(tree->pos==NULL);
  91         assert(tree->neg==NULL);
  92         assert(tree->zero==NULL);
  93         assert(tree->vectors);
  94
  95
  96         for (; start<ctx->Current; start++)
  97         {
  98                 compo = start<0 ? ctx->Current : start;
  99                 pos = false;
 100                 neg = false;
 101                 zero = false;
 102                 for (i=0; i<tree->vectors->Size; i++)
 103                 {
 104                         if (ctx->Lattice->Data[tree->vectors->Data[i]][compo]>0)
 105                                 pos = true;
 106                         else if (ctx->Lattice->Data[tree->vectors->Data[i]][compo]<0)
 107                                 neg = true;
 108                         else
 109                                 zero = true;
 110                 }
 111                 if (pos+neg>1)
 112                         break;
 113         }
 114
 115         if (start<ctx->Current && tree->vectors->Size > 1)
 116         {
 117                 compo = start<0 ? ctx->Current : start;
 118                 for (i=0; i<tree->vectors->Size; i++)
 119                 {
 120                         value = ctx->Lattice->Data[tree->vectors->Data[i]][compo];
 121                         if (value>0)
 122                         {
 123                                 node = tree->pos;
 124                                 if (node==NULL || value<node->value)
 125                                 {
 126                                         tree->pos = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 127                                         tree->pos->value = value;
 128                                         tree->pos->next = node;
 129                                         tree->pos->sub = createValueTree(-1);
 130                                         appendToIndexArray(tree->pos->sub->vectors, tree->vectors->Data[i]);
 131                                 }
 132                                 else
 133                                 {
 134                                         while (node->next && value>=node->next->value)
 135                                                 node = node->next;
 136                                         if (value!=node->value)
 137                                         {
 138                                                 temp = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 139                                                 temp->value = value;
 140                                                 temp->sub = createValueTree(-1);
 141                                                 temp->next = node->next;
 142             node->next = temp;
 143                                                 node = temp;
 144                                         }
 145                                         appendToIndexArray(node->sub->vectors, tree->vectors->Data[i]);
 146                                 }
 147                         }
 148                         else if (value<0)
 149                         {
 150                                 node = tree->neg;
 151                                 if (node==NULL || value>node->value)
 152                                 {
 153                                         tree->neg = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 154                                         tree->neg->value = value;
 155                                         tree->neg->next = node;
 156                                         tree->neg->sub = createValueTree(-1);
 157                                         appendToIndexArray(tree->neg->sub->vectors, tree->vectors->Data[i]);
 158                                 }
 159                                 else
 160                                 {
 161                                         while (node->next && value<=node->next->value)
 162                                                 node = node->next;
 163                                         if (value!=node->value)
 164                                         {
 165                                                 temp = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 166                                                 temp->value = value;
 167                                                 temp->sub = createValueTree(-1);
 168                                                 temp->next = node->next;
 169                                                 node->next = temp;
 170                                                 node = temp;
 171                                         }
 172                                         appendToIndexArray(node->sub->vectors, tree->vectors->Data[i]);
 173                                 }
 174                         }
 175                         else
 176                         {
 177                                 if (tree->zero==NULL)
 178                                         tree->zero = createValueTree(-1);
 179                                 appendToIndexArray(tree->zero->vectors, tree->vectors->Data[i]);
 180                         }
 181                 }
 182
 183                 deleteIndexArray(tree->vectors);
 184                 tree->vectors = NULL;
 185                 tree->level = compo;
 186     start++;
 187                 node = tree->pos;
 188                 while (node)
 189                 {
 190                         splitValueTree(ctx, node->sub, start);
 191                         node = node->next;
 192                 }
 193                 node = tree->neg;
 194                 while (node)
 195                 {
 196                         splitValueTree(ctx, node->sub, start);
 197                         node = node->next;
 198                 }
 199
 200                 splitValueTree(ctx, tree->zero, start);
 201                 return;
 202         }
 203 }
 204
 205 //                                                                            //
 206
 207 void createValueTrees(ZSolveContext ctx)
 208 {
 209         int i,j;
 210
 211         ctx->MaxNorm = 0;
 212         for (i=0; i<ctx->Lattice->Size; i++)
 213                 ctx->MaxNorm = maxi(ctx->MaxNorm, normVector(ctx->Lattice->Data[i], ctx->Current));
 214
 215         ctx->Norm = (void **)calloc(ctx->MaxNorm+1, sizeof(ValueTree));
 216
 217         for (i=0; i<ctx->Lattice->Size; i++)
 218         {
 219                 j = normVector(ctx->Lattice->Data[i], ctx->Current);
 220                 // TODO is it correct, to throw out if all 0 on before and current ?! - it seems incorrect, as bayer-test fails.
 221                 if (j==0 && ctx->Lattice->Data[i][ctx->Current] == 0)
 222                         continue;
 223                 // put in corresponding norm-tree
 224                 if (ctx->Norm[j]==NULL)
 225                         ctx->Norm[j] = createValueTree(-1);
 226                 appendToIndexArray( ((ValueTree *)ctx->Norm)[j]->vectors, i);
 227         }
 228
 229         for (i=0; i<=ctx->MaxNorm; i++)
 230                 splitValueTree(ctx, ctx->Norm[i], -1);
 231 }
 232
 233 //                                                                            //
 234
 235 void deleteValueTrees(ZSolveContext ctx)
 236 {
 237         int i;
 238
 239         for (i=0; i<=ctx->MaxNorm; i++)
 240                 deleteValueTree(ctx->Norm[i]);
 241
 242         free(ctx->Norm);
 243         ctx->Norm = NULL;
 244 }
 245
 246 //                                                                            //
 247
 248 bool enumValueReducer(ZSolveContext ctx, ValueTree tree)
 249 {
 250         int value, i, j;
 251         Vector Reducer;
 252         ValueTreeNode node;
 253
 254         if (tree)
 255         {
 256                 if (tree->level>=0)
 257                 {
 258                         value = ctx->Sum[tree->level];
 259                         if (value>0)
 260                         {
 261                                 node = tree->pos;
 262                                 while (node && node->value<=value)
 263                                 {
 264                                         if (enumValueReducer(ctx, node->sub))
 265                                                 return true;
 266                                         node = node->next;
 267                                 }
 268                         }
 269                         if (value<0)
 270                         {
 271                                 node = tree->neg;
 272                                 while (node && node->value>=value)
 273                                 {
 274                                         if (enumValueReducer(ctx, node->sub))
 275                                                 return true;
 276                                         node = node->next;
 277                                 }
 278                         }
 279                         if (enumValueReducer(ctx, tree->zero))
 280                                 return true;
 281                 }
 282                 else
 283                 {
 284                         for (i=0; i<tree->vectors->Size; i++)
 285                         {
 286                                 Reducer = ctx->Lattice->Data[tree->vectors->Data[i]];
 287 /*                              printf("=> Testing reduction of [");
 288                                 printVector(ctx->Sum, ctx->Variables);
 289                                 printf("] by [");
 290                                 printVector(Reducer, ctx->Variables);
 291                                 printf("]\n"); */
 292                                 for (j=0; j<=ctx->Current; j++)
 293                                         if (Reducer[j]*ctx->Sum[j]<0 || abs(ctx->Sum[j])<abs(Reducer[j]))
 294                                                 break;
 295                                 if (j>ctx->Current)
 296                                         return true;
 297                         }
 298                 }
 299         }
 300         return false;
 301 }
 302
 303 //                                                                            //
 304
 305 void insertVectorToValueTree(ZSolveContext ctx, ValueTree tree, int index)
 306 {
 307         int value;
 308         ValueTreeNode node, temp;
 309
 310         assert(tree);
 311         assert(index>=0 && index<ctx->Lattice->Size);
 312
 313         if (tree->level>=0)
 314         {
 315                 value = ctx->Lattice->Data[index][tree->level];
 316                 if (value>0)
 317                 {
 318                         node = tree->pos;
 319                         if (node==NULL || value<node->value)
 320                         {
 321                                 tree->pos = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 322                                 tree->pos->value = value;
 323                                 tree->pos->next = node;
 324                                 tree->pos->sub = createValueTree(-1);
 325                                 appendToIndexArray(tree->pos->sub->vectors, index);
 326                         }
 327                         else
 328                         {
 329                                 while (node->next && value>=node->next->value)
 330                                         node = node->next;
 331                                 if (value==node->value)
 332                                         insertVectorToValueTree(ctx, node->sub, index);
 333                                 else
 334                                 {
 335                                         temp = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 336                                         temp->value = value;
 337                                         temp->sub = createValueTree(-1);
 338                                         appendToIndexArray(temp->sub->vectors, index);
 339                                         temp->next = node->next;
 340                                         node->next = temp;
 341                                 }
 342                         }
 343                 }
 344                 else if (value<0)
 345                 {
 346                         node = tree->neg;
 347                         if (node==NULL || value>node->value)
 348                         {
 349                                 tree->neg = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 350                                 tree->neg->value = value;
 351                                 tree->neg->next = node;
 352                                 tree->neg->sub = createValueTree(-1);
 353                                 appendToIndexArray(tree->neg->sub->vectors, index);
 354                         }
 355                         else
 356                         {
 357                                 while (node->next && value<=node->next->value)
 358                                         node = node->next;
 359                                 if (value==node->value)
 360                                         insertVectorToValueTree(ctx, node->sub, index);
 361                                 else
 362                                 {
 363                                         temp = (ValueTreeNode)malloc(sizeof(valuetreenode_t));
 364                                         temp->value = value;
 365                                         temp->sub = createValueTree(-1);
 366                                         appendToIndexArray(temp->sub->vectors, index);
 367                                         temp->next = node->next;
 368                                         node->next = temp;
 369                                 }
 370                         }
 371                 }
 372                 else
 373                 {
 374                         if (tree->zero==NULL)
 375                         {
 376                                 tree->zero = createValueTree(-1);
 377                                 appendToIndexArray(tree->zero->vectors, index);
 378                         }
 379                         else
 380                                 insertVectorToValueTree(ctx, tree->zero, index);
 381                 }
 382         }
 383         else
 384         {
 385                 appendToIndexArray(tree->vectors, index);
 386                 splitValueTree(ctx, tree, -1);
 387         }
 388 }
 389
 390 //                                                                            //
 391
 392 void insertVectorToValueTrees(ZSolveContext ctx, Vector vector, int norm)
 393 {
 394         if (norm>ctx->MaxNorm)
 395         {
 396                 ctx->Norm = (void **)realloc(ctx->Norm, (norm+1)*sizeof(ValueTree));
 397                 while (norm>ctx->MaxNorm)
 398                         ctx->Norm[++ctx->MaxNorm] = NULL;
 399         }
 400
 401         appendToVectorArray(ctx->Lattice, vector);
 402         if (ctx->Norm[norm]==NULL)
 403         {
 404                 ctx->Norm[norm] = createValueTree(-1);
 405                 appendToIndexArray(((ValueTree *)ctx->Norm)[norm]->vectors, ctx->Lattice->Size-1);
 406         }
 407         else
 408                 insertVectorToValueTree(ctx, ctx->Norm[norm], ctx->Lattice->Size-1);
 409 }
 410
 411 //                                                                            //
 412
 413 void buildValueSum(ZSolveContext ctx)
 414 {
 415         int i,norm;
 416         bool flag;
 417
 418         assert(ctx->First);
 419         assert(ctx->Second);
 420         assert(ctx->Sum);
 421
 422         // same ?
 423         if (ctx->First==ctx->Second)
 424                 return;
 425
 426         // pattern okay ?
 427         if (ctx->First[ctx->Current]*ctx->Second[ctx->Current]>0)
 428                 return;
 429         flag = false;
 430         for (i=0; i<ctx->Current; i++)
 431                 if (ctx->First[i]*ctx->Second[i]<0)
 432                         flag = true;
 433         if (flag)
 434                 return;
 435
 436         // build new
 437         norm = 0;
 438         for (i=0; i<ctx->Variables; i++)
 439         {
 440                 ctx->Sum[i] = ctx->First[i] + ctx->Second[i];
 441                 if (i<ctx->Current)
 442                         norm += abs(ctx->Sum[i]);
 443         }
 444         // all zero?
 445         if (norm==0)
 446                 return;
 447
 448         // DEBUG
 449 /*      printf("build: [");
 450         printVector(ctx->Sum, ctx->Variables);
 451         printf("]\n"); */
 452
 453         // reducable ?
 454         flag = false;
 455         for (i=0; i<=norm/2; i++)
 456         {
 457                 if (i<=ctx->MaxNorm)
 458                 {
 459                         if (enumValueReducer(ctx, ctx->Norm[i]))
 460                         {
 461                                 flag = true;
 462                                 break;
 463                         }
 464                 }
 465         }
 466         if (flag) {
 467 //              printf("(reduced)\n");
 468                 return;
 469         }
 470
 471         // limits okay ?
 472         for (i=0; i<ctx->Current; i++)
 473         {
 474                 if (ctx->Lattice->Properties[i].Lower>ctx->Sum[i]) {
 475 //                      printf("(lower bounds failed)\n");
 476                         return;
 477                 }
 478                 if (ctx->Lattice->Properties[i].Upper<ctx->Sum[i]) {
 479 //                      printf("(upper bounds failed)\n");
 480                         return;
 481                 }
 482         }
 483
 484         if (norm<=ctx->MaxNorm)
 485                 if (enumValueReducer(ctx, ctx->Norm[norm]))
 486                         return;
 487
 488         insertVectorToValueTrees(ctx, copyVector(ctx->Sum, ctx->Variables), norm);
 489
 490         if (ctx->Symmetric)
 491         {
 492                 for (i=0; i<ctx->Variables; i++)
 493                         ctx->Sum[i] = -ctx->Sum[i];
 494                 insertVectorToValueTrees(ctx, copyVector(ctx->Sum, ctx->Variables), norm);
 495         }
 496 }
 497
 498 //                                                                            //
 499
 500 void enumValueSecond(ZSolveContext ctx, ValueTree tree)
 501 {
 502         int i;
 503         ValueTreeNode node;
 504
 505         if (tree)
 506         {
 507                 if (tree->level==ctx->Current)
 508                 {
 509                         if (ctx->First[ctx->Current]>=0)
 510                         {
 511                                 node = tree->neg;
 512                                 while (node)
 513                                 {
 514                                         enumValueSecond(ctx, node->sub);
 515                                         node = node->next;
 516                                 }
 517                         }
 518                         if (ctx->First[ctx->Current]<=0)
 519                         {
 520                                 node = tree->pos;
 521                                 while (node)
 522                                 {
 523                                         enumValueSecond(ctx, node->sub);
 524                                         node = node->next;
 525                                 }
 526                         }
 527                 }
 528                 else if (tree->level>=0)
 529                 {
 530                         if (ctx->First[tree->level]<=0)
 531                         {
 532                                 node = tree->neg;
 533                                 while (node)
 534                                 {
 535                                         enumValueSecond(ctx, node->sub);
 536                                         node = node->next;
 537                                 }
 538                         }
 539                         enumValueSecond(ctx, tree->zero);
 540                         if (ctx->First[tree->level]>=0)
 541                         {
 542                                 node = tree->pos;
 543                                 while (node)
 544                                 {
 545                                         enumValueSecond(ctx, node->sub);
 546                                         node = node->next;
 547                                 }
 548                         }
 549                 }
 550                 else
 551                 {
 552                         assert(tree->vectors);
 553
 554                         for (i=0; tree->vectors!=NULL && i<tree->vectors->Size; i++)
 555                         {
 556                                 ctx->Second = ctx->Lattice->Data[tree->vectors->Data[i]];
 557                                 if (ctx->Second[ctx->Current]!=0)
 558                                         buildValueSum(ctx);
 559                         }
 560                         if (tree->vectors==NULL)
 561                                 enumValueSecond(ctx, tree);
 562                 }
 563         }
 564 }
 565
 566 //                                                                            //
 567
 568 void enumValueFirst(ZSolveContext ctx, ValueTree tree, int norm)
 569 {
 570         int i;
 571
 572         ValueTreeNode node;
 573
 574
 575         if (tree)
 576         {
 577                 if (tree->level>=0)
 578                 {
 579                         node = tree->pos;
 580                         while (node)
 581                         {
 582                                 enumValueFirst(ctx, node->sub, norm);
 583                                 node = node->next;
 584                         }
 585                         enumValueFirst(ctx, tree->zero, norm);
 586                         node = tree->neg;
 587                         while (node)
 588                         {
 589                                 enumValueFirst(ctx, node->sub, norm);
 590                                 node = node->next;
 591                         }
 592                 }
 593                 else
 594                 {
 595                         assert(tree->vectors);
 596
 597                         for (i=0; tree->vectors!=NULL && i<tree->vectors->Size; i++)
 598                         {
 599                                 ctx->First = ctx->Lattice->Data[tree->vectors->Data[i]];
 600                                 if ((!ctx->Symmetric && ctx->First[ctx->Current]<0) || ctx->First[ctx->Current]>0)
 601                                         enumValueSecond(ctx, ctx->Norm[norm]);
 602                         }
 603
 604                         if (tree->vectors==NULL)
 605                                 enumValueFirst(ctx, tree, norm);
 606                 }
 607         }
 608 }
 609
 610 //                                                                            //
 611
 612 void completeValueTrees(ZSolveContext ctx, int norm1, int norm2)
 613 {
 614         assert(ctx->Norm);
 615         assert(!(norm1>ctx->MaxNorm || norm2>ctx->MaxNorm || ctx->Norm[norm1]==NULL || ctx->Norm[norm2]==NULL));
 616
 617         enumValueFirst(ctx, ctx->Norm[norm1], norm2);
 618 }
 619
 620 //                                                                            //