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 int size;\r
  28 \r
  29   public BitArray(int size) {\r
  30     this.size = size;\r
  31     this.bits = makeArray(size);\r
  32   }\r
  33 \r
  34   public int getSize() {\r
  35     return size;\r
  36   }\r
  37 \r
  38   /**\r
  39    * @param i bit to get\r
  40    * @return true iff bit i is set\r
  41    */\r
  42   public boolean get(int i) {\r
  43     return (bits[i >> 5] & (1 << (i & 0x1F))) != 0;\r
  44   }\r
  45 \r
  46   /**\r
  47    * Sets bit i.\r
  48    *\r
  49    * @param i bit to set\r
  50    */\r
  51   public void set(int i) {\r
  52     bits[i >> 5] |= 1 << (i & 0x1F);\r
  53   }\r
  54 \r
  55   /**\r
  56    * Sets a block of 32 bits, starting at bit i.\r
  57    *\r
  58    * @param i first bit to set\r
  59    * @param newBits the new value of the next 32 bits. Note again that the least-significant bit\r
  60    * corresponds to bit i, the next-least-significant to i+1, and so on.\r
  61    */\r
  62   public void setBulk(int i, int newBits) {\r
  63     bits[i >> 5] = newBits;\r
  64   }\r
  65 \r
  66   /**\r
  67    * Clears all bits (sets to false).\r
  68    */\r
  69   public void clear() {\r
  70     int max = bits.length;\r
  71     for (int i = 0; i < max; i++) {\r
  72       bits[i] = 0;\r
  73     }\r
  74   }\r
  75 \r
  76   /**\r
  77    * Efficient method to check if a range of bits is set, or not set.\r
  78    *\r
  79    * @param start start of range, inclusive.\r
  80    * @param end end of range, exclusive\r
  81    * @param value if true, checks that bits in range are set, otherwise checks that they are not set\r
  82    * @return true iff all bits are set or not set in range, according to value argument\r
  83    * @throws IllegalArgumentException if end is less than or equal to start\r
  84    */\r
  85   public boolean isRange(int start, int end, boolean value) {\r
  86     if (end < start) {\r
  87       throw new IllegalArgumentException();\r
  88     }\r
  89     if (end == start) {\r
  90       return true; // empty range matches\r
  91     }\r
  92     end--; // will be easier to treat this as the last actually set bit -- inclusive    \r
  93     int firstInt = start >> 5;\r
  94     int lastInt = end >> 5;\r
  95     for (int i = firstInt; i <= lastInt; i++) {\r
  96       int firstBit = i > firstInt ? 0 : start & 0x1F;\r
  97       int lastBit = i < lastInt ? 31 : end & 0x1F;\r
  98       int mask;\r
  99       if (firstBit == 0 && lastBit == 31) {\r
 100         mask = -1;\r
 101       } else {\r
 102         mask = 0;\r
 103         for (int j = firstBit; j <= lastBit; j++) {\r
 104           mask |= 1 << j;\r
 105         }\r
 106       }\r
 107       if (value) {\r
 108         if ((bits[i] & mask) != mask) {\r
 109           return false;\r
 110         }\r
 111       } else {\r
 112         if ((bits[i] & mask) != 0) {\r
 113           return false;\r
 114         }\r
 115       }\r
 116     }\r
 117     return true;\r
 118   }\r
 119 \r
 120   /**\r
 121    * @return underlying array of ints. The first element holds the first 32 bits, and the least\r
 122    *         significant bit is bit 0.\r
 123    */\r
 124   public int[] getBitArray() {\r
 125     return bits;\r
 126   }\r
 127 \r
 128   /**\r
 129    * Reverses all bits in the array.\r
 130    */\r
 131   public void reverse() {\r
 132     int[] newBits = makeArray(size);\r
 133     int max = newBits.length;\r
 134     for (int i = 0; i < max; i++) {\r
 135       newBits[i] = 0;\r
 136     }\r
 137     int size = this.size;\r
 138     for (int i = 0; i < size; i++) {\r
 139       if (get(size - i - 1)) {\r
 140         newBits[i >> 5] |= 1 << (i & 0x1F);\r
 141       }\r
 142     }\r
 143     bits = newBits;\r
 144   }\r
 145 \r
 146   private static int[] makeArray(int size) {\r
 147     int arraySize = size >> 5;\r
 148     if ((size & 0x1F) != 0) {\r
 149       arraySize++;\r
 150     }\r
 151     return new int[arraySize];\r
 152   }\r
 153 \r
 154 }