core/src/com/google/zxing/common/BitArray.java

   1 /*\r
   2  * Copyright 2007 Google Inc.\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package com.google.zxing.common;\r
  18 \r
  19 /**\r
  20  * <p>A simple, fast array of bits, represented compactly by an array of ints internally.</p>\r
  21  *\r
  22  * @author srowen@google.com (Sean Owen)\r
  23  */\r
  24 public final class BitArray {\r
  25 \r
  26   private int[] bits;\r
  27   private final int size;\r
  28 \r
  29   public BitArray(int size) {\r
  30     if (size < 1) {\r
  31       throw new IllegalArgumentException("size must be at least 1");\r
  32     }\r
  33     this.size = size;\r
  34     this.bits = makeArray(size);\r
  35   }\r
  36 \r
  37   public int getSize() {\r
  38     return size;\r
  39   }\r
  40 \r
  41   /**\r
  42    * @param i bit to get\r
  43    * @return true iff bit i is set\r
  44    */\r
  45   public boolean get(int i) {\r
  46     return (bits[i >> 5] & (1 << (i & 0x1F))) != 0;\r
  47   }\r
  48 \r
  49   /**\r
  50    * Sets bit i.\r
  51    *\r
  52    * @param i bit to set\r
  53    */\r
  54   public void set(int i) {\r
  55     bits[i >> 5] |= 1 << (i & 0x1F);\r
  56   }\r
  57 \r
  58   /**\r
  59    * Sets a block of 32 bits, starting at bit i.\r
  60    *\r
  61    * @param i first bit to set\r
  62    * @param newBits the new value of the next 32 bits. Note again that the least-significant bit\r
  63    * corresponds to bit i, the next-least-significant to i+1, and so on.\r
  64    */\r
  65   public void setBulk(int i, int newBits) {\r
  66     bits[i >> 5] = newBits;\r
  67   }\r
  68 \r
  69   /**\r
  70    * Clears all bits (sets to false).\r
  71    */\r
  72   public void clear() {\r
  73     int max = bits.length;\r
  74     for (int i = 0; i < max; i++) {\r
  75       bits[i] = 0;\r
  76     }\r
  77   }\r
  78 \r
  79   /**\r
  80    * Efficient method to check if a range of bits is set, or not set.\r
  81    *\r
  82    * @param start start of range, inclusive.\r
  83    * @param end end of range, exclusive\r
  84    * @param value if true, checks that bits in range are set, otherwise checks that they are not set\r
  85    * @return true iff all bits are set or not set in range, according to value argument\r
  86    * @throws IllegalArgumentException if end is less than or equal to start\r
  87    */\r
  88   public boolean isRange(int start, int end, boolean value) {\r
  89     if (end < start) {\r
  90       throw new IllegalArgumentException();\r
  91     }\r
  92     if (end == start) {\r
  93       return true; // empty range matches\r
  94     }\r
  95     end--; // will be easier to treat this as the last actually set bit -- inclusive    \r
  96     int firstInt = start >> 5;\r
  97     int lastInt = end >> 5;\r
  98     for (int i = firstInt; i <= lastInt; i++) {\r
  99       int firstBit = i > firstInt ? 0 : start & 0x1F;\r
 100       int lastBit = i < lastInt ? 31 : end & 0x1F;\r
 101       int mask;\r
 102       if (firstBit == 0 && lastBit == 31) {\r
 103         mask = -1;\r
 104       } else {\r
 105         mask = 0;\r
 106         for (int j = firstBit; j <= lastBit; j++) {\r
 107           mask |= 1 << j;\r
 108         }\r
 109       }\r
 110       if (value) {\r
 111         if ((bits[i] & mask) != mask) {\r
 112           return false;\r
 113         }\r
 114       } else {\r
 115         if ((bits[i] & mask) != 0) {\r
 116           return false;\r
 117         }\r
 118       }\r
 119     }\r
 120     return true;\r
 121   }\r
 122 \r
 123   /**\r
 124    * @return underlying array of ints. The first element holds the first 32 bits, and the least\r
 125    *         significant bit is bit 0.\r
 126    */\r
 127   public int[] getBitArray() {\r
 128     return bits;\r
 129   }\r
 130 \r
 131   /**\r
 132    * Reverses all bits in the array.\r
 133    */\r
 134   public void reverse() {\r
 135     int[] newBits = makeArray(size);\r
 136     int max = newBits.length;\r
 137     for (int i = 0; i < max; i++) {\r
 138       newBits[i] = 0;\r
 139     }\r
 140     int size = this.size;\r
 141     for (int i = 0; i < size; i++) {\r
 142       if (get(size - i - 1)) {\r
 143         newBits[i >> 5] |= 1 << (i & 0x1F);\r
 144       }\r
 145     }\r
 146     bits = newBits;\r
 147   }\r
 148 \r
 149   private static int[] makeArray(int size) {\r
 150     int arraySize = size >> 5;\r
 151     if ((size & 0x1F) != 0) {\r
 152       arraySize++;\r
 153     }\r
 154     return new int[arraySize];\r
 155   }\r
 156 \r
 157 }