package com.google.zxing.common;\r
\r
/**\r
- * <p>Represnts a square matrix of bits. In function arguments below, i is the row position\r
- * and j the column position of a bit. The top left bit corresponds to i = 0 and j = 0.</p>\r
+ * <p>Represents a 2D matrix of bits. In function arguments below, and throughout the common\r
+ * module, x is the column position, and y is the row position. The ordering is always x, y.\r
+ * The origin is at the top-left.</p>\r
*\r
- * <p>Internally the bits are represented in a compact 1-D array of 32-bit ints. The\r
- * ordering of bits is column-major; that is the bits in this array correspond to\r
- * j=0 and i=0..dimension-1 first, then j=1 and i=0..dimension-1, etc.</p>\r
+ * <p>Internally the bits are represented in a 1-D array of 32-bit ints. However, each row begins\r
+ * with a new int. This is done intentionally so that we can copy out a row into a BitArray very\r
+ * efficiently.</p>\r
*\r
- * <p>Within each int, less-signficant bits correspond to lower values of i and higher rows.\r
- * That is, the top-left bit is the least significant bit of the first int.</p>\r
+ * <p>The ordering of bits is row-major. Within each int, the least significant bits are used first,\r
+ * meaning they represent lower x values. This is compatible with BitArray's implementation.</p>\r
*\r
- * <p>This class is a convenient wrapper around this representation, but also exposes the internal\r
- * array for efficient access and manipulation.</p>\r
- *\r
- * @author srowen@google.com (Sean Owen)\r
+ * @author Sean Owen\r
+ * @author dswitkin@google.com (Daniel Switkin)\r
*/\r
public final class BitMatrix {\r
\r
- private final int dimension;\r
- private final int[] bits;\r
+ // TODO: Just like BitArray, these need to be public so ProGuard can inline them.\r
+ public final int width;\r
+ public final int height;\r
+ public final int rowSize;\r
+ public final int[] bits;\r
\r
+ // A helper to construct a square matrix.\r
public BitMatrix(int dimension) {\r
- if (dimension < 1) {\r
- throw new IllegalArgumentException("dimension must be at least 1");\r
- }\r
- this.dimension = dimension;\r
- int numBits = dimension * dimension;\r
- int arraySize = numBits >> 5; // one int per 32 bits\r
- if ((numBits & 0x1F) != 0) { // plus one more if there are leftovers\r
- arraySize++;\r
+ this(dimension, dimension);\r
+ }\r
+\r
+ public BitMatrix(int width, int height) {\r
+ if (width < 1 || height < 1) {\r
+ throw new IllegalArgumentException("Both dimensions must be greater than 0");\r
}\r
- bits = new int[arraySize];\r
+ this.width = width;\r
+ this.height = height;\r
+ this.rowSize = (width + 31) >> 5;\r
+ bits = new int[rowSize * height];\r
}\r
\r
/**\r
- * @param i row offset\r
- * @param j column offset\r
+ * <p>Gets the requested bit, where true means black.</p>\r
+ *\r
+ * @param x The horizontal component (i.e. which column)\r
+ * @param y The vertical component (i.e. which row)\r
* @return value of given bit in matrix\r
*/\r
- public boolean get(int i, int j) {\r
- int offset = i + dimension * j;\r
- return ((bits[offset >> 5] >>> (offset & 0x1F)) & 0x01) != 0;\r
+ public boolean get(int x, int y) {\r
+ int offset = y * rowSize + (x >> 5);\r
+ return ((bits[offset] >>> (x & 0x1f)) & 1) != 0;\r
}\r
\r
/**\r
* <p>Sets the given bit to true.</p>\r
*\r
- * @param i row offset\r
- * @param j column offset\r
+ * @param x The horizontal component (i.e. which column)\r
+ * @param y The vertical component (i.e. which row)\r
+ */\r
+ public void set(int x, int y) {\r
+ int offset = y * rowSize + (x >> 5);\r
+ bits[offset] |= 1 << (x & 0x1f);\r
+ }\r
+\r
+ /**\r
+ * <p>Flips the given bit.</p>\r
+ *\r
+ * @param x The horizontal component (i.e. which column)\r
+ * @param y The vertical component (i.e. which row)\r
*/\r
- public void set(int i, int j) {\r
- int offset = i + dimension * j;\r
- bits[offset >> 5] |= 1 << (offset & 0x1F);\r
+ public void flip(int x, int y) {\r
+ int offset = y * rowSize + (x >> 5);\r
+ bits[offset] ^= 1 << (x & 0x1f);\r
+ }\r
+\r
+ /**\r
+ * Clears all bits (sets to false).\r
+ */\r
+ public void clear() {\r
+ int max = bits.length;\r
+ for (int i = 0; i < max; i++) {\r
+ bits[i] = 0;\r
+ }\r
}\r
\r
/**\r
* <p>Sets a square region of the bit matrix to true.</p>\r
*\r
- * @param topI row offset of region's top-left corner (inclusive)\r
- * @param leftJ column offset of region's top-left corner (inclusive)\r
- * @param height height of region\r
- * @param width width of region\r
+ * @param left The horizontal position to begin at (inclusive)\r
+ * @param top The vertical position to begin at (inclusive)\r
+ * @param width The width of the region\r
+ * @param height The height of the region\r
*/\r
- public void setRegion(int topI, int leftJ, int height, int width) {\r
- if (topI < 0 || leftJ < 0) {\r
- throw new IllegalArgumentException("topI and leftJ must be nonnegative");\r
+ public void setRegion(int left, int top, int width, int height) {\r
+ if (top < 0 || left < 0) {\r
+ throw new IllegalArgumentException("Left and top must be nonnegative");\r
}\r
if (height < 1 || width < 1) {\r
- throw new IllegalArgumentException("height and width must be at least 1");\r
- }\r
- int maxJ = leftJ + width;\r
- int maxI = topI + height;\r
- if (maxI > dimension || maxJ > dimension) {\r
- throw new IllegalArgumentException(\r
- "topI + height and leftJ + width must be <= matrix dimension");\r
- }\r
- for (int j = leftJ; j < maxJ; j++) {\r
- int jOffset = dimension * j;\r
- for (int i = topI; i < maxI; i++) {\r
- int offset = i + jOffset;\r
- bits[offset >> 5] |= 1 << (offset & 0x1F);\r
+ throw new IllegalArgumentException("Height and width must be at least 1");\r
+ }\r
+ int right = left + width;\r
+ int bottom = top + height;\r
+ if (bottom > this.height || right > this.width) {\r
+ throw new IllegalArgumentException("The region must fit inside the matrix");\r
+ }\r
+ for (int y = top; y < bottom; y++) {\r
+ int offset = y * rowSize;\r
+ for (int x = left; x < right; x++) {\r
+ bits[offset + (x >> 5)] |= 1 << (x & 0x1f);\r
}\r
}\r
}\r
\r
/**\r
- * @return row/column dimension of this matrix\r
+ * A fast method to retrieve one row of data from the matrix as a BitArray.\r
+ *\r
+ * @param y The row to retrieve\r
+ * @param row An optional caller-allocated BitArray, will be allocated if null or too small\r
+ * @return The resulting BitArray - this reference should always be used even when passing\r
+ * your own row\r
+ */\r
+ public BitArray getRow(int y, BitArray row) {\r
+ if (row == null || row.getSize() < width) {\r
+ row = new BitArray(width);\r
+ }\r
+ int offset = y * rowSize;\r
+ for (int x = 0; x < rowSize; x++) {\r
+ row.setBulk(x << 5, bits[offset + x]);\r
+ }\r
+ return row;\r
+ }\r
+\r
+ /**\r
+ * This is useful in detecting a corner of a 'pure' barcode.\r
+ * \r
+ * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white\r
+ */\r
+ public int[] getTopLeftOnBit() {\r
+ int bitsOffset = 0;\r
+ while (bitsOffset < bits.length && bits[bitsOffset] == 0) {\r
+ bitsOffset++;\r
+ }\r
+ if (bitsOffset == bits.length) {\r
+ return null;\r
+ }\r
+ int y = bitsOffset / rowSize;\r
+ int x = (bitsOffset % rowSize) << 5;\r
+ \r
+ int theBits = bits[bitsOffset];\r
+ int bit = 0;\r
+ while ((theBits << (31-bit)) == 0) {\r
+ bit++;\r
+ }\r
+ x += bit;\r
+ return new int[] {x, y};\r
+ }\r
+\r
+ /**\r
+ * @return The width of the matrix\r
*/\r
- public int getDimension() {\r
- return dimension;\r
+ public int getWidth() {\r
+ return width;\r
}\r
\r
/**\r
- * @return array of ints holding internal representation of this matrix's bits\r
+ * @return The height of the matrix\r
*/\r
- public int[] getBits() {\r
- return bits;\r
+ public int getHeight() {\r
+ return height;\r
+ }\r
+\r
+ public boolean equals(Object o) {\r
+ if (!(o instanceof BitMatrix)) {\r
+ return false;\r
+ }\r
+ BitMatrix other = (BitMatrix) o;\r
+ if (width != other.width || height != other.height ||\r
+ rowSize != other.rowSize || bits.length != other.bits.length) {\r
+ return false;\r
+ }\r
+ for (int i = 0; i < bits.length; i++) {\r
+ if (bits[i] != other.bits[i]) {\r
+ return false;\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+\r
+ public int hashCode() {\r
+ int hash = width;\r
+ hash = 31 * hash + width;\r
+ hash = 31 * hash + height;\r
+ hash = 31 * hash + rowSize;\r
+ for (int i = 0; i < bits.length; i++) {\r
+ hash = 31 * hash + bits[i];\r
+ }\r
+ return hash;\r
}\r
\r
public String toString() {\r
- StringBuffer result = new StringBuffer(dimension * (dimension + 1));\r
- for (int i = 0; i < dimension; i++) {\r
- for (int j = 0; j < dimension; j++) {\r
- result.append(get(i, j) ? 'X' : ' ');\r
+ StringBuffer result = new StringBuffer(height * (width + 1));\r
+ for (int y = 0; y < height; y++) {\r
+ for (int x = 0; x < width; x++) {\r
+ result.append(get(x, y) ? "X " : " ");\r
}\r
result.append('\n');\r
}\r
projects / zxing.git / blobdiff