BitMatrix.java

/*
 * Class:        BitMatrix
 * Description:  implements matrices of bits and their operations
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since
 *
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
package umontreal.ssj.util;
 
import java.io.Serializable;

public class BitMatrix implements Serializable, Cloneable {
 
   static final long serialVersionUID = 2472769969919959608L;
 
   private BitVector[] rows; // rows vectors
 
   private int r, c; // number of rows / columns

   public BitMatrix(int r, int c) {
      rows = new BitVector[r];
      for (int i = 0; i < r; i++)
         rows[i] = new BitVector(c);
      this.r = r;
      this.c = c;
   }

   public BitMatrix(BitVector[] rows) {
      this.rows = new BitVector[rows.length];
      for (int i = 0; i < rows.length; i++)
         this.rows[i] = new BitVector(rows[i]);
      this.r = rows.length;
      this.c = r > 0 ? rows[0].size() : 0;
   }

   public BitMatrix(int[][] data, int r, int c) {
      this.rows = new BitVector[r];
      for (int i = 0; i < r; i++)
         this.rows[i] = new BitVector(data[i], c);
      this.r = r;
      this.c = c;
   }

   public BitMatrix(BitMatrix that) {
      this.r = that.r;
      this.c = that.c;
      this.rows = new BitVector[this.r];
      for (int i = 0; i < this.r; i++)
         this.rows[i] = new BitVector(that.rows[i]);
   }

   public Object clone() {
      try {
         BitMatrix c = (BitMatrix) super.clone();
         c.rows = (BitVector[]) rows.clone();
         for (int i = 0; i < rows.length; i++)
            c.rows[i] = (BitVector) rows[i].clone();
         return c;
      } catch (CloneNotSupportedException e) {
         IllegalStateException ne = new IllegalStateException();
         ne.initCause(e);
         throw ne;
      }
   }

   public boolean equals(BitMatrix that) {
      if (this.r != that.r || this.c != that.c)
         return false;
      for (int i = 0; i < r; i++)
         if (!this.rows[i].equals(that.rows[i]))
            return false;
      return true;
   }

   public String toString() {
      StringBuffer sb = new StringBuffer();
 
      // on affiche les bits sur les lignes dans l'order inverse de l'ordre
      // affiche pour le BitVector pour que le bit a (0,0) soit en haut
      // a gauche
 
      sb.append("{ ");
      for (int i = 0; i < rows.length - 1; i++) {
         for (int j = 0; j < rows[i].size(); j++)
            sb.append(rows[i].getBool(j) ? "1" : "0");
         sb.append(PrintfFormat.NEWLINE + "  ");
      }
      if (r > 0) {
         for (int j = 0; j < c; j++)
            sb.append(rows[r - 1].getBool(j) ? "1" : "0");
         sb.append(" }");
      } else
         sb.append(" }");
 
      return sb.toString();
   }

   public String printData() {
      StringBuffer sb = new StringBuffer();
 
      sb.append("{ ");
      for (int i = 0; i < r; i++) {
         sb.append("{");
         for (int j = 0; j < (c + 31) / 32; j++) {
            sb.append(rows[i].getInt(j));
            if (j != (c - 1) / 32)
               sb.append(", ");
         }
         sb.append("}");
         if (i != r - 1)
            sb.append("," + PrintfFormat.NEWLINE + "  ");
      }
      sb.append(" }");
 
      return sb.toString();
   }

   public int numRows() {
      return r;
   }

   public int numColumns() {
      return c;
   }

   public boolean getBool(int row, int column) {
      if (row >= r || column >= c)
         throw new IndexOutOfBoundsException();
 
      return rows[row].getBool(column);
   }

   public void setBool(int row, int column, boolean value) {
      if (row >= r || column >= c)
         throw new IndexOutOfBoundsException();
 
      rows[row].setBool(column, value);
   }

   public BitMatrix transpose() {
      BitMatrix result = new BitMatrix(c, r);
 
      for (int i = 0; i < r; i++)
         for (int j = 0; j < c; j++)
            result.rows[j].setBool(i, rows[i].getBool(j));
 
      return result;
   }

   public BitMatrix not() {
      BitMatrix result = new BitMatrix(this);
      for (int i = 0; i < r; i++)
         result.rows[i].selfNot();
      return result;
   }

   public BitMatrix and(BitMatrix that) {
      if (this.c != that.c || this.r != that.r)
         throw new IncompatibleDimensionException("Both matrices must have the same dimension. " + "this is a " + this.r
               + "x" + this.c + " matrix " + "while that is a " + that.r + "x" + that.c + " matrix.");
      BitMatrix result = new BitMatrix(this);
      for (int i = 0; i < r; i++)
         result.rows[i].selfAnd(that.rows[i]);
      return result;
   }

   public BitMatrix or(BitMatrix that) {
      if (this.c != that.c || this.r != that.r)
         throw new IncompatibleDimensionException("Both matrices must have the same dimension. " + "this is a " + this.r
               + "x" + this.c + " matrix " + "while that is a " + that.r + "x" + that.c + " matrix.");
      BitMatrix result = new BitMatrix(this);
      for (int i = 0; i < r; i++)
         result.rows[i].selfOr(that.rows[i]);
      return result;
   }

   public BitMatrix xor(BitMatrix that) {
      if (this.c != that.c || this.r != that.r)
         throw new IncompatibleDimensionException("Both matrices must have the same dimension. " + "this is a " + this.r
               + "x" + this.c + " matrix " + "while that is a " + that.r + "x" + that.c + " matrix.");
      BitMatrix result = new BitMatrix(this);
      for (int i = 0; i < r; i++)
         result.rows[i].selfXor(that.rows[i]);
      return result;
   }

   public BitVector multiply(BitVector vect) {
      BitVector res = new BitVector(r);
 
      for (int i = 0; i < r; i++)
         res.setBool(i, rows[i].scalarProduct(vect));
 
      return res;
   }

   public int multiply(int vect) {
      BitVector temp = new BitVector(new int[] { vect });
 
      return multiply(temp).getInt(0);
   }

   public BitMatrix multiply(BitMatrix that) {
      if (this.c != that.r)
         throw new IncompatibleDimensionException("The number of columns of this (" + this.c
               + ") must be equal to the number of rows of that (" + that.r + ").");
 
      /*
       * BitVector[] res = new BitVector[this.r];
       * 
       * for(int i = 0; i < this.r; i++) { res[i] = new BitVector(that.c);
       * 
       * for(int j = 0; j < that.c; j++) { temp = false; for(int k = 0; k < this.c;
       * k++) if(this.rows[i].getBool(k) && that.rows[k].getBool(j)) temp = !temp;
       * res[i].setBool(j,temp); } }
       * 
       * return BitMatrix(res);
       */
 
      // methode plus efficace
 
      BitMatrix res = new BitMatrix(this.r, that.c);
 
      for (int i = 0; i < res.r; i++)
         for (int j = 0; j < res.c; j++)
            if (this.rows[i].getBool(j))
               res.rows[i].selfXor(that.rows[j]);
 
      return res;
   }

   public BitMatrix power(long p) {
      if (c != r)
         throw new IncompatibleDimensionException("Only square matrices can be raised to a power.");
 
      if (p < 0)
         throw new IllegalArgumentException("Only non-negative powers are accepted.");
 
      if (p == 0) {
         // the identity matrix
         BitMatrix bm = new BitMatrix(r, r);
         for (int i = 0; i < r; i++)
            bm.setBool(i, i, true);
         return bm;
      }
 
      if (p == 1)
         return this;
 
      if (p % 2 == 0) {
         BitMatrix temp = this.power(p / 2);
         return temp.multiply(temp);
      } else
         return this.multiply(this.power(p - 1));
   }

   public BitMatrix power2e(int e) {
      if (c != r)
         throw new IncompatibleDimensionException("Only square matrices can be raised to a power.");
      BitMatrix result = this;
 
      for (int i = 0; i < e; i++)
         result = result.multiply(result);
 
      return result;
   }


   public class IncompatibleDimensionException extends RuntimeException {
      private IncompatibleDimensionException() {
         super();
      }
 
      private IncompatibleDimensionException(String message) {
         super(message);
      }
   }
 
}