BitVector.java

/*
 * Class:        BitVector
 * Description:  implements vectors 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 BitVector implements Serializable, Cloneable {
 
   static final long serialVersionUID = -3448233092524725148L;
 
   private int[] v; // the bits data
   private int length; // number of data bits (in bits, not in bytes)
 
   private final static int all_1 = -1; // integer with all bits set to 1
   private final static int one_1 = 1; // integer with only his last bit set to 1
   /*
    * Note sur le format interne du vecteur de bits : On fait toujours en sorte que
    * les bits redondants (ceux qui apparaissent quand length % 32 != 0) soient mis
    * a 0. Ceci permet de faire des operations entre des vecteurs de longeurs
    * differentes en posant que les bits manquants sur le plus petit des deux
    * vecteurs ont la valeur 0.
    */

   public BitVector(int length) {
      this.length = length;
      v = new int[(length + 31) / 32];
      for (int i = 0; i < v.length; i++)
         v[i] = 0;
   }

   public BitVector(int[] vect, int length) {
      if (((length + 31) / 32) != vect.length)
         throw new IllegalArgumentException("The int[] length must be equal to the (length + 31) / 32");
 
      this.length = length;
      v = new int[vect.length];
      for (int i = 0; i < vect.length; i++)
         v[i] = vect[i];
 
      // the extra bits must be set at zero
      v[v.length - 1] &= (all_1 >>> (31 - (length - 1) % 32));
   }

   public BitVector(int[] vect) {
      this(vect, vect.length * 32);
   }

   public BitVector(BitVector that) {
      this.length = that.length;
      this.v = new int[that.v.length];
      for (int i = 0; i < that.v.length; i++)
         this.v[i] = that.v[i];
   }

   public Object clone() {
      try {
         BitVector c = (BitVector) super.clone();
         c.v = (int[]) v.clone();
         return c;
      } catch (CloneNotSupportedException e) {
         IllegalStateException ne = new IllegalStateException();
         ne.initCause(e);
         throw ne;
      }
   }

   public boolean equals(BitVector that) {
      if (this.length != that.length)
         return false;
      for (int i = 0; i < this.v.length; i++)
         if (this.v[i] != that.v[i])
            return false;
      return true;
   }

   public int size() {
      return length;
   }

   public void enlarge(int size, boolean filling) {
      if (size < 0)
         throw new NegativeArraySizeException("The BitVector must have a non-negative size");
      if (filling && (length % 32) != 0)
         v[v.length - 1] ^= all_1 << (length % 32);
      if ((size + 31) / 32 != v.length) {
         int[] new_v = new int[(size + 31) / 32];
         int i;
         for (i = 0; i < new_v.length && i < v.length; i++)
            new_v[i] = v[i];
         for (; i < new_v.length; i++)
            new_v[i] = filling ? all_1 : 0;
         v = new_v;
      }
      length = size;
 
      // the extra bits must be set at zero
      v[v.length - 1] &= (all_1 >>> (31 - (length - 1) % 32));
   }

   public void enlarge(int size) {
      enlarge(size, false);
   }

   public boolean getBool(int pos) {
      if (pos < 0 || pos >= length)
         throw new ArrayIndexOutOfBoundsException(pos);
      return (v[pos >>> 5] & (one_1 << (pos & 31))) != 0;
   }

   public void setBool(int pos, boolean value) {
      if (pos > length || pos < 0)
         throw new ArrayIndexOutOfBoundsException(pos);
      if (value)
         v[pos / 32] |= (one_1 << (pos % 32));
      else
         v[pos / 32] &= (one_1 << (pos % 32)) ^ all_1;
   }

   public int getInt(int pos) {
      if (pos >= v.length || pos < 0)
         throw new ArrayIndexOutOfBoundsException(pos);
      return v[pos];
   }

   public String toString() {
      StringBuffer sb = new StringBuffer();
 
      for (int i = length - 1; i > 0; i--)
         sb.append(getBool(i) ? "1" : "0").append(i % 8 == 0 ? " " : "");
      sb.append(getBool(0) ? "1" : "0");
 
      return sb.toString();
   }

   public BitVector not() {
      BitVector bv = new BitVector(length);
      for (int i = 0; i < v.length; i++)
         bv.v[i] = v[i] ^ all_1;
 
      // the extra bits must be set at zero
      bv.v[v.length - 1] &= (all_1 >>> (31 - (length - 1) % 32));
 
      return bv;
   }

   public BitVector selfNot() {
      for (int i = 0; i < v.length; i++)
         v[i] = v[i] ^ all_1;
 
      // the extra bits must be set at zero
      v[v.length - 1] &= (all_1 >>> (31 - (length - 1) % 32));
 
      return this;
   }

   public BitVector xor(BitVector that) {
      // we always consider that this is longer than that
      if (that.length > this.length)
         return that.xor(this);
 
      BitVector bv = new BitVector(this.length);
 
      int max = this.v.length;
      int min = that.v.length;
 
      for (int i = 0; i < min; i++)
         bv.v[i] = this.v[i] ^ that.v[i];
      for (int i = min; i < max; i++)
         bv.v[i] = this.v[i];
 
      return bv;
   }

   public BitVector selfXor(BitVector that) {
      // we assume that this is large enough to contain that
      if (this.length < that.length)
         this.enlarge(that.length);
 
      int min = that.v.length;
 
      for (int i = 0; i < min; i++)
         this.v[i] ^= that.v[i];
 
      return this;
   }

   public BitVector and(BitVector that) {
      // we always consider this as longer than that
      if (that.length > this.length)
         return that.and(this);
 
      BitVector bv = new BitVector(this.length);
 
      int max = this.v.length;
      int min = that.v.length;
 
      for (int i = 0; i < min; i++)
         bv.v[i] = this.v[i] & that.v[i];
      if (that.length % 32 != 0)
         bv.v[min - 1] |= this.v[min - 1] & (all_1 << (that.length % 32));
      for (int i = min; i < max; i++)
         bv.v[i] = 0;
 
      return bv;
   }

   public BitVector selfAnd(BitVector that) {
      // we assume that this is large enough to contain that
      if (this.length < that.length)
         this.enlarge(that.length, true);
 
      int min = that.v.length;
 
      for (int i = 0; i < min - 1; i++)
         this.v[i] &= that.v[i];
      this.v[min - 1] &= (that.v[min - 1] | (all_1 << (that.length % 32)));
 
      return this;
   }

   public BitVector or(BitVector that) {
      // we always consider this is longer than that
      if (that.length > this.length)
         return that.or(this);
 
      BitVector bv = new BitVector(this.length);
 
      int max = this.v.length;
      int min = that.v.length;
 
      for (int i = 0; i < min; i++)
         bv.v[i] = this.v[i] | that.v[i];
      for (int i = min; i < max; i++)
         bv.v[i] = 0;
 
      return bv;
   }

   public BitVector selfOr(BitVector that) {
      // we assume that this is large enough to contain that
      if (this.length < that.length)
         this.enlarge(that.length);
 
      int min = that.v.length;
 
      for (int i = 0; i < min; i++)
         this.v[i] |= that.v[i];
 
      return this;
   }

   public BitVector shift(int j) {
      BitVector bv = new BitVector(length);
 
      if (j == 0)
         return bv;
      else if (j > 0) {
         int a = j / 32;
         int b = j % 32;
         int c = 32 - b;
 
         int i;
         for (i = 0; i + a < v.length; i++)
            bv.v[i] = v[i + a] >>> b;
         // la retenue
         for (i = 0; i + a + 1 < v.length; i++)
            bv.v[i] ^= v[i + a + 1] << c;
      } else // if(j < 0)
      {
         j = -j;
         int a = j / 32;
         int b = j % 32;
         int c = 32 - b;
 
         int i;
         for (i = a; i < v.length; i++)
            bv.v[i] ^= v[i - a] << b;
         // la retenue
         for (i = a + 1; i < v.length; i++)
            bv.v[i] ^= v[i - a - 1] >>> c;
      }
 
      return bv;
   }

   public BitVector selfShift(int j) {
      if (j == 0)
         return this;
      else if (j > length || j < -length) {
         for (int i = 0; i < v.length; i++)
            v[i] = 0;
      } else if (j > 0) {
         int a = j / 32;
         int b = j % 32;
         int c = 32 - b;
 
         int i;
         for (i = 0; i + a + 1 < v.length; i++) {
            v[i] = v[i + a] >>> b;
            // la retenue
            v[i] ^= v[i + a + 1] << c;
         }
         v[i] = v[i + a] >>> b;
         for (i += 1; i < v.length; i++)
            v[i] = 0;
      } else // if(j < 0)
      {
         j = -j;
         int a = j / 32;
         int b = j % 32;
         int c = 32 - b;
 
         int i;
         for (i = v.length - 1; i > a; i--) {
            v[i] = v[i - a] << b;
            // la retenue
            v[i] ^= v[i - a - 1] >>> c;
         }
         v[i] = v[i - a] << b;
         for (i -= 1; i >= 0; i--)
            v[i] = 0;
      }
 
      return this;
   }

   public boolean scalarProduct(BitVector that) {
      // we must take that is not longer than this
      if (that.v.length > this.v.length)
         return that.scalarProduct(this);
 
      boolean result = false;
      int prod;
 
      for (int i = 0; i < that.v.length; i++) {
         prod = this.v[i] & that.v[i];
         while (prod != 0) {
            // a chaque iteration, on enleve le 1 le plus a droite
            prod &= prod - 1;
            result = !result;
         }
      }
 
      return result;
   }
 
}