src/baseparsuif/suifmath/int_matrix.h

   1 /* file "int_matrix.h" */
   2
   3 /*  Copyright (c) 1994 Stanford University
   4
   5     All rights reserved.
   6
   7     This software is provided under the terms described in
   8     the "suif_copyright.h" include file. */
   9
  10 #include <suif_copyright.h>
  11
  12 #pragma interface
  13 //
  14 // two dimensional integer matrix class to allow easy referencing
  15 //
  16
  17 #ifndef INT_MATRIX_H
  18 #define INT_MATRIX_H
  19
  20 #ifndef ABS
  21 #define ABS(A) (((A)<0) ? -1*(A):(A))
  22 #endif
  23
  24 #ifdef MAX
  25 #undef MAX
  26 #endif
  27 inline int    MAX(int A, int B) { return (A > B)?A:B; }
  28 inline double MAX(double A, double B) { return (A > B)?A:B; }
  29
  30 #ifdef MIN
  31 #undef MIN
  32 #endif
  33 inline int    MIN(int A, int B) { return (A < B)?A:B; }
  34 inline double MIN(double A, double B) { return (A < B)?A:B; }
  35
  36 #include <stdlib.h>
  37
  38 int gcd(int, int);
  39 int lcm(int, int);
  40
  41
  42 /**********************************************************************************
  43  *** integer row                                                                ***
  44  ***                                                                            ***
  45  **********************************************************************************/
  46 class integer_row {
  47     friend class integer_matrix;
  48     friend class lin_ineq;
  49     int sz;
  50
  51 protected:
  52     int * R;
  53     int rsz;
  54
  55 public:
  56     integer_row();
  57     integer_row(const integer_row & rw);
  58     integer_row(const integer_row * rw);
  59     integer_row(int s);
  60 //    integer_row(const int * ilist, int s) { R=0; sz=0; init(ilist, s); }
  61     ~integer_row() { clear(); }
  62     void clear();
  63 private:
  64     void mknew(int s);
  65 public:
  66     void init(const integer_row & rw);
  67     void init(const integer_row * rw) { init(*rw); }
  68     void init(int s);
  69     void init(const int * ilist, int s);
  70     void init() { R=0; sz=0; rsz=0; }
  71
  72     int n() const { return sz; }
  73
  74     int & operator[](int i) { assert((i>=0)&&(i<sz)); return R[i]; }
  75     int c(int i) const { assert((i>=0)&&(i<sz)); return R[i]; }
  76
  77     boolean operator==(const integer_row & a) const;
  78     boolean operator!=(const integer_row & a) const { return !((*this) == a); }
  79     integer_row & operator=(const integer_row & row);
  80     void operator^=(integer_row & row); // Swap Rows
  81     integer_row operator+(const integer_row & row) const;
  82     integer_row operator-(const integer_row & row) const;
  83     integer_row operator*(const integer_row & row) const;
  84     integer_row operator/(const integer_row & row) const;
  85 //    integer_row operator+(int r) const;
  86 //    integer_row operator-(int r) const;
  87 //    integer_row operator*(int r) const;
  88 //    integer_row operator/(int r) const;
  89
  90     integer_row operator%(const integer_row & row) const;
  91         // operator%: shuffle operator ret[x] = this[row[x]]
  92
  93     integer_row & operator+=(const integer_row & row);
  94     integer_row & operator-=(const integer_row & row);
  95     integer_row & operator*=(const integer_row & row);
  96     integer_row & operator/=(const integer_row & row);
  97     integer_row & operator=(int val);
  98     integer_row & operator+=(int val);
  99     integer_row & operator-=(int val);
 100     integer_row & operator*=(int val);
 101     integer_row & operator/=(int val);
 102
 103     void do_addmul(const integer_row &, int mul=1);
 104
 105     void print(FILE * fp=stdout) const { for(int i=0; i< n(); i++) fprintf(fp, "%d ", R[i]); fprintf(fp, "\n"); }
 106     integer_row del_col(int i, int j) const;
 107     integer_row del_col(int i) const { return del_col(i, i); }
 108     integer_row insert_col(int i) const;
 109
 110     integer_row swap_col(int i, int j) const;
 111
 112     void do_del_col(int i, int j);
 113     void do_del_col(int i) { do_del_col(i, i); };
 114     void do_del_columns(const integer_row &mask); // delete entries with 1s;
 115     void do_insert_col(int i);
 116     void do_swap_col(int i, int j);
 117 public:
 118
 119     int * data_array() { return R; }
 120
 121     int hashkey() const;
 122 };
 123
 124
 125 class coeff;
 126 /**********************************************************************************
 127  *** integer matrix                                                             ***
 128  ***                                                                            ***
 129  **********************************************************************************/
 130 class integer_matrix {
 131
 132 public:
 133         int nn; // number of columns;
 134         int mm;  // number of rows;
 135         integer_row * A;  // the matrix;
 136
 137 protected:
 138         int realmm;
 139         virtual integer_row *alloc_rows(int num_rows);
 140         void mknew(int rows, int cols);
 141 public:
 142         integer_matrix(int rows,int cols);
 143         integer_matrix(const integer_matrix & m);
 144         integer_matrix(const integer_matrix * m);
 145         integer_matrix(const integer_matrix & m, int rows);
 146         integer_matrix(const integer_matrix * m, int rows);
 147         integer_matrix(const coeff *);
 148         integer_matrix();
 149
 150         virtual ~integer_matrix();
 151         void clear();
 152         void init(int rows,int cols);
 153         void init(const integer_matrix & M);
 154         void init(const integer_matrix * m) { init(*m); }
 155         void init(const integer_matrix & M, int rows);
 156         void init(const integer_matrix * m, int rows) { init(*m, rows); }
 157         void init(FILE *);
 158         void init(FILE *, int, int);
 159         void init(const coeff *);
 160         void init(const int *data, int rows, int cols);
 161         int init(const immed_list & ilist, int c=0);
 162
 163
 164         immed_list * cvt_immed_list() const;
 165
 166
 167         boolean operator==(const integer_matrix &  a) const;
 168         boolean operator!=(const integer_matrix &  a) const
 169             { return (!((*this) == a)); }
 170
 171         integer_row & operator [](int row) { assert((row>=0)&&(row<mm)); return A[row]; }
 172         const integer_row &r(int row) const
 173             { assert((row>=0)&&(row<mm)); return A[row]; }
 174         integer_matrix & operator=(const integer_matrix & in);
 175
 176         integer_matrix  operator%(const integer_row & shuffle) const;
 177         int n() const { return nn; }
 178         int m() const { return mm; }
 179
 180         integer_matrix del_row(int i, int j) const;
 181         integer_matrix del_row(int i) const { return del_row(i, i); }
 182
 183         integer_matrix del_col(int i, int j) const;
 184         integer_matrix del_col(int i) const { return del_col(i, i); }
 185         integer_matrix del_columns(const integer_row & r) const;
 186         integer_matrix insert_col(int i) const;
 187
 188         integer_matrix swap_col(int i, int j) const;
 189
 190         void do_del_row(int i, int j);
 191         void do_del_row(int i) { do_del_row(i, i); };
 192         void do_del_rows(const integer_row & r);
 193
 194         void do_del_col(int i, int j);
 195         void do_del_col(int i) { do_del_col(i, i); }
 196         void do_del_columns(const integer_row & r);
 197         void do_insert_col(int i);
 198         void do_add_rows(int rws); // adds rows to end;
 199
 200         void do_swap_col(int i, int j);
 201         void do_swap_row(int i, int j);
 202
 203         void do_rowadd(int rto, int radd, int mul=1);
 204         void do_coladd(int cto, int cadd, int mul=1);
 205
 206         void print(FILE *fp=stdout, int flag=0) const;
 207
 208         void check() const;
 209
 210
 211         // matrix operations
 212         integer_matrix  operator*(const integer_matrix &) const;
 213         integer_matrix  operator+(const integer_matrix &) const;
 214         integer_matrix  operator-(const integer_matrix &) const;
 215         integer_matrix  operator*(int i) const;
 216         integer_matrix  operator/(int i) const;
 217         integer_matrix  operator+(int i) const;
 218         integer_matrix  operator-(int i) const;
 219
 220         integer_matrix & operator+=(const integer_matrix & in);
 221         integer_matrix & operator-=(const integer_matrix & in);
 222         integer_matrix & operator+=(int);
 223         integer_matrix & operator-=(int);
 224         integer_matrix & operator*=(int);
 225         integer_matrix & operator/=(int);
 226         void ident(int v);
 227         void ident() { assert(mm == nn); ident(mm); }
 228         integer_matrix transpose() const;
 229         int determinant() const;
 230         integer_matrix inverse(int * det = 0) const;
 231
 232         void swap(int i, int j) { (*this)[i] ^= (*this)[j]; }
 233
 234         // returns (m-r1+r2)x(n-c1+c2) matrix, obtained from block;
 235         // with corners at (r1,c1) to (m+r2,m+c2);
 236         // puts fill value at new locations not corresponding to original;
 237         integer_matrix  resize_offset(int r1, int r2, int c1, int c2,
 238                                       int fill=0) const;
 239         // selects block (r1,c1) to (r2,c2) from this;
 240         integer_matrix  resize(int r1, int r2, int c1, int c2, int fill=0)
 241             const { return resize_offset(r1, r2-mm, c1, c2-nn, fill); }
 242
 243         // puts a2 rows below a1;
 244         integer_matrix r_merge(const integer_matrix & a1,
 245                                const integer_matrix & a2) const;
 246         integer_matrix c_merge(const integer_matrix & a1,
 247                                const integer_matrix & a2) const;
 248         integer_matrix  operator|(const integer_matrix & A) const
 249             { return c_merge(*this, A); }
 250         integer_matrix  operator&(const integer_matrix & A) const
 251             { return r_merge(*this, A); }
 252
 253         integer_matrix composeL(int r_comp, int c_comp,
 254                                 const integer_matrix *const * list,
 255                                 int exit_on_error=TRUE) const;
 256         integer_matrix compose(int r_comp, int c_comp,
 257                                const integer_matrix * m1=0,
 258                                const integer_matrix * m2=0,
 259                                const integer_matrix * m3=0,
 260                                const integer_matrix * m4=0,
 261                                const integer_matrix * m5=0,
 262                                const integer_matrix * m6=0,
 263                                const integer_matrix * m7=0,
 264                                const integer_matrix * m8=0,
 265                                const integer_matrix * m9=0,
 266                                const integer_matrix * m10=0,
 267                                const integer_matrix * m11=0,
 268                                const integer_matrix * m12=0,
 269                                const integer_matrix * m13=0,
 270                                const integer_matrix * m14=0,
 271                                const integer_matrix * m15=0,
 272                                const integer_matrix * m16=0,
 273                                const integer_matrix * m17=0,
 274                                const integer_matrix * m18=0,
 275                                const integer_matrix * m19=0,
 276                                const integer_matrix * m20=0,
 277                                const integer_matrix * m21=0,
 278                                const integer_matrix * m22=0,
 279                                const integer_matrix * m23=0,
 280                                const integer_matrix * m24=0,
 281                                const integer_matrix * m25=0,
 282                                const integer_matrix * m26=0,
 283                                const integer_matrix * m27=0,
 284                                const integer_matrix * m28=0,
 285                                const integer_matrix * m29=0,
 286                                const integer_matrix * m30=0,
 287                                const integer_matrix * m31=0,
 288                                const integer_matrix * m32=0) const;
 289     private:
 290         void composeL_print(int er, int r_comp, int c_comp,
 291                             const integer_matrix *const * list) const;
 292 };
 293
 294 typedef integer_matrix * p_integer_matrix;
 295
 296 inline integer_matrix Ident(int i) { integer_matrix tmp; tmp.ident(i); return tmp; }
 297
 298 // Permutation matrices
 299 integer_matrix rowswitch(const integer_matrix & A, int r1, int r2);
 300 integer_matrix colswitch(const integer_matrix & A, int c1, int c2);
 301 integer_matrix rowadd(const integer_matrix & A, int rto, int radd, int mul=1);
 302 integer_matrix coladd(const integer_matrix & A, int cto, int cadd, int mul=1);
 303
 304 integer_matrix * NIM(const integer_matrix & A);
 305 integer_matrix * NIM(const integer_matrix * A);
 306 integer_matrix * NIM(int i, int j);
 307 integer_matrix * NIM(int i);
 308
 309 class nim_op {
 310     nim_op * next;
 311     integer_matrix * m;
 312 public:
 313     nim_op()                    { next = NULL;
 314                                   m = NULL; }
 315     nim_op(nim_op * t)          { assert(t);
 316                                   next = t->next;
 317                                   t->next = this;
 318                                   m = NULL; }
 319     ~nim_op();
 320     integer_matrix * NIM(const integer_matrix & A);
 321     integer_matrix * NIM(const integer_matrix * A);
 322     integer_matrix * NIM(int i, int j);
 323     integer_matrix * NIM(int i);
 324 };
 325
 326
 327
 328
 329 void compose_print(int);
 330 integer_matrix Compose(int r_comp, int c_comp,
 331                        const integer_matrix * m1=0,
 332                        const integer_matrix * m2=0,
 333                        const integer_matrix * m3=0,
 334                        const integer_matrix * m4=0,
 335                        const integer_matrix * m5=0,
 336                        const integer_matrix * m6=0,
 337                        const integer_matrix * m7=0,
 338                        const integer_matrix * m8=0,
 339                        const integer_matrix * m9=0,
 340                        const integer_matrix * m10=0,
 341                        const integer_matrix * m11=0,
 342                        const integer_matrix * m12=0,
 343                        const integer_matrix * m13=0,
 344                        const integer_matrix * m14=0,
 345                        const integer_matrix * m15=0,
 346                        const integer_matrix * m16=0,
 347                        const integer_matrix * m17=0,
 348                        const integer_matrix * m18=0,
 349                        const integer_matrix * m19=0,
 350                        const integer_matrix * m20=0,
 351                        const integer_matrix * m21=0,
 352                        const integer_matrix * m22=0,
 353                        const integer_matrix * m23=0,
 354                        const integer_matrix * m24=0,
 355                        const integer_matrix * m25=0,
 356                        const integer_matrix * m26=0,
 357                        const integer_matrix * m27=0,
 358                        const integer_matrix * m28=0,
 359                        const integer_matrix * m29=0,
 360                        const integer_matrix * m30=0,
 361                        const integer_matrix * m31=0,
 362                        const integer_matrix * m32=0);
 363
 364 integer_matrix Compose(int r_comp, int c_comp,
 365                        int a1,    int a2=0,  int a3=0,  int a4=0,
 366                        int a5=0,  int a6=0,  int a7=0,  int a8=0,
 367                        int a9=0,  int a10=0, int a11=0, int a12=0,
 368                        int a13=0, int a14=0, int a15=0, int a16=0,
 369                        int a17=0, int a18=0, int a19=0, int a20=0,
 370                        int a21=0, int a22=0, int a23=0, int a24=0,
 371                        int a25=0, int a26=0, int a27=0, int a28=0,
 372                        int a29=0, int a30=0, int a31=0, int a32=0,
 373                        int a33=0, int a34=0, int a35=0, int a36=0,
 374                        int a37=0, int a38=0, int a39=0, int a40=0,
 375                        int a41=0, int a42=0, int a43=0, int a44=0,
 376                        int a45=0, int a46=0, int a47=0, int a48=0,
 377                        int a49=0, int a50=0, int a51=0, int a52=0,
 378                        int a53=0, int a54=0, int a55=0, int a56=0,
 379                        int a57=0, int a58=0, int a59=0, int a60=0);
 380
 381
 382 #endif /* INT_MATRIX_H */