extend.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4 #include <complex.h>
   5
   6 #include "matrix.h"
   7 #include "extend.h"
   8
   9 // linked list
  10 struct Node {
  11   int data;
  12   struct Node* next;
  13 };
  14
  15 void printLinkedList(struct Node *node);
  16 void append(struct Node** head_ref, int new_data);
  17 void freeList(struct Node** head_ref);
  18
  19 /****************************************************************************
  20  * Attempts to extend the dimension of the affine space by one dimension.
  21  * The affine space is specified by
  22  * the first 'k' columns of the 'n'x'n' matrix 'G', translated by 'h',
  23  * that will be extended to include the vector 'xi'. 'GBar' is 'G^(-1)^T'.
  24  ****************************************************************************/
  25
  26 void extend(int n, int *k, int *h, int **G, int **GBar, int *xi) {
  27
  28   int a;
  29
  30   struct Node* setS = NULL;
  31   struct Node* setT = NULL;
  32   struct Node* setWalker = NULL;
  33
  34   int i;
  35
  36   for(a=0; a<*k; a++) {
  37     if(dotProductMod(xi, GBar[a], n, 2) == 1) {
  38         append(&setS, a);
  39     }
  40   }
  41   unsigned int firstT = 1; // set initially to true
  42   for(a=*k; a<n; a++) {
  43     if(dotProductMod(xi, GBar[a], n, 2) == 1) {
  44       if(firstT) {
  45         append(&setT, a);
  46         i = a;
  47         firstT = 0;
  48       }
  49       else {
  50         append(&setS, a);
  51         append(&setT, a);
  52       }
  53     }
  54   }
  55
  56   if(setT == NULL) {
  57     freeList(&setS);
  58     freeList(&setT);
  59     return; // xi is in the linear space so do nothing
  60   }
  61
  62   setWalker = setS;
  63   while(setWalker != NULL) {
  64     // update GBar rows, gbar
  65     for(a=0; a<n; a++)
  66       GBar[setWalker->data][a] = (GBar[setWalker->data][a] + GBar[i][a])%2;
  67     // update G rows, g
  68     for(a=0; a<n; a++)
  69       G[i][a] = (G[i][a] + G[setWalker->data][a])%2;
  70
  71     setWalker = setWalker->next;
  72   }
  73
  74   // Swap 'i' and 'k+1'
  75   int* tmpVec;
  76   tmpVec = G[i];
  77   G[i] = G[*k];
  78   G[*k] = tmpVec;
  79   tmpVec = GBar[i];
  80   GBar[i] = GBar[*k];
  81   GBar[*k] = tmpVec;
  82
  83   freeList(&setS);
  84   freeList(&setT);
  85
  86   // increment 'k'
  87   *k = *k + 1;
  88
  89   return;
  90
  91 }
  92
  93
  94 void append(struct Node** head_ref, int new_data)
  95 {
  96     struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
  97     struct Node *last = *head_ref;
  98
  99     new_node->data = new_data;
 100     new_node->next = NULL;
 101
 102     // if the linked list is empty, then make the new node as head
 103     if (*head_ref == NULL) {
 104       *head_ref = new_node;
 105       return;
 106     }
 107
 108     // else traverse till the last node
 109     while (last->next != NULL) {
 110         last = last->next;
 111     }
 112     last->next = new_node;
 113
 114     return;
 115 }
 116
 117 /*void freeList(struct Node** head_ref)
 118 {
 119
 120   struct Node *second_last_walker = *head_ref;
 121   struct Node *walker = *head_ref;
 122
 123     // else traverse till the last node
 124     if(walker != NULL) {
 125       while(walker->next != NULL) {
 126         while(walker->next != NULL) {
 127           //printf("!%d\n", walker->data);
 128           second_last_walker = walker;
 129           walker = walker->next;
 130           //printf("%d\n", walker->data);
 131           //printf("!%d\n", second_last_walker->data);
 132         }
 133         free(walker);
 134         second_last_walker->next = NULL;
 135         walker = *head_ref;
 136         //printf("!!%d\n", second_last_walker->data);
 137       }
 138     }
 139     free(walker);
 140
 141     return;
 142     }*/
 143
 144 void freeList(struct Node** head_ref)
 145 {
 146
 147   struct Node *walker = *head_ref;
 148   struct Node *walker2;
 149
 150     // else traverse till the last node
 151     if(walker != NULL) {
 152       walker2 = walker->next;
 153       while(walker2 != NULL) {
 154         free(walker);
 155         walker = walker2;
 156         walker2 = walker->next;
 157       }
 158     }
 159     free(walker);
 160
 161     return;
 162 }
 163
 164
 165 void printLinkedList(struct Node *node)
 166 {
 167   if(node == NULL)
 168     printf("NULL\n");
 169   else {
 170     while (node != NULL)
 171       {
 172         printf(" %d ", node->data);
 173         node = node->next;
 174       }
 175   }
 176   printf("\n");
 177 }