0
# Data Structures
1

2
Core data structures for bit manipulation, matrix operations, and geometric transformations used throughout the ZXing library for barcode processing.
3

4
## Capabilities
5

6
### BitMatrix
7

8
2D boolean matrix representing barcode data, used for both encoding output and 2D barcode decoding.
9

10
```java { .api }
11
/**
12
 * 2D array of bits (boolean values)
13
 * Primary data structure for 2D barcodes and encoding output
14
 */
15
public final class BitMatrix implements Cloneable {
16
    /**
17
     * Create a bit matrix with specified dimensions
18
     * @param width Width in bits/modules
19
     * @param height Height in bits/modules
20
     */
21
    public BitMatrix(int width, int height);
22
    
23
    /**
24
     * Get matrix width
25
     * @return Width in bits/modules
26
     */
27
    public int getWidth();
28
    
29
    /**
30
     * Get matrix height
31
     * @return Height in bits/modules
32
     */
33
    public int getHeight();
34
    
35
    /**
36
     * Get bit value at specific coordinates
37
     * @param x X coordinate (0-based)
38
     * @param y Y coordinate (0-based)
39
     * @return true if bit is set (black), false if unset (white)
40
     */
41
    public boolean get(int x, int y);
42
    
43
    /**
44
     * Set bit at specific coordinates
45
     * @param x X coordinate
46
     * @param y Y coordinate
47
     */
48
    public void set(int x, int y);
49
    
50
    /**
51
     * Unset bit at specific coordinates
52
     * @param x X coordinate
53
     * @param y Y coordinate
54
     */
55
    public void unset(int x, int y);
56
    
57
    /**
58
     * Toggle bit at specific coordinates
59
     * @param x X coordinate
60
     * @param y Y coordinate
61
     */
62
    public void flip(int x, int y);
63
    
64
    /**
65
     * XOR operation with another matrix
66
     * @param mask Matrix to XOR with
67
     */
68
    public void xor(BitMatrix mask);
69
    
70
    /**
71
     * Clear all bits (set to false)
72
     */
73
    public void clear();
74
    
75
    /**
76
     * Set entire rectangular region
77
     * @param left Left coordinate
78
     * @param top Top coordinate
79
     * @param width Region width
80
     * @param height Region height
81
     */
82
    public void setRegion(int left, int top, int width, int height);
83
    
84
    /**
85
     * Get row as BitArray
86
     * @param y Row index
87
     * @param row Optional pre-allocated BitArray for reuse
88
     * @return BitArray representing the row
89
     */
90
    public BitArray getRow(int y, BitArray row);
91
    
92
    /**
93
     * Set entire row from BitArray
94
     * @param y Row index
95
     * @param row BitArray containing row data
96
     */
97
    public void setRow(int y, BitArray row);
98
    
99
    /**
100
     * Rotate matrix 180 degrees
101
     */
102
    public void rotate180();
103
    
104
    /**
105
     * Get enclosing rectangle of set bits
106
     * @return int array [left, top, width, height] or null if no bits set
107
     */
108
    public int[] getEnclosingRectangle();
109
    
110
    /**
111
     * Get top-left set bit coordinates
112
     * @return int array [x, y] or null if no bits set
113
     */
114
    public int[] getTopLeftOnBit();
115
    
116
    /**
117
     * Get bottom-right set bit coordinates
118
     * @return int array [x, y] or null if no bits set
119
     */
120
    public int[] getBottomRightOnBit();
121
    
122
    /**
123
     * Create a deep copy
124
     * @return Cloned BitMatrix
125
     */
126
    public BitMatrix clone();
127
}
128
```
129

130
**Usage Examples:**
131

132
```java
133
// Create and manipulate bit matrix
134
BitMatrix matrix = new BitMatrix(100, 100);
135

136
// Set individual bits
137
matrix.set(10, 10);
138
matrix.set(20, 20);
139

140
// Set rectangular region
141
matrix.setRegion(30, 30, 20, 20);
142

143
// Check bits
144
boolean isSet = matrix.get(10, 10); // true
145
boolean isEmpty = matrix.get(5, 5); // false
146

147
// Get matrix properties
148
int width = matrix.getWidth();   // 100
149
int height = matrix.getHeight(); // 100
150

151
// Work with rows
152
BitArray row = matrix.getRow(10, null);
153
// ... modify row ...
154
matrix.setRow(15, row);
155

156
// Find content bounds
157
int[] bounds = matrix.getEnclosingRectangle();
158
if (bounds != null) {
159
    System.out.println("Content area: " + bounds[0] + "," + bounds[1] + 
160
                      " size " + bounds[2] + "x" + bounds[3]);
161
}
162
```
163

164
### BitArray
165

166
1D boolean array with dynamic sizing, used for 1D barcode processing and as building blocks for 2D operations.
167

168
```java { .api }
169
/**
170
 * 1D array of bits with dynamic sizing
171
 * Primary data structure for 1D barcodes and row operations
172
 */
173
public final class BitArray implements Cloneable {
174
    /**
175
     * Create empty bit array
176
     */
177
    public BitArray();
178
    
179
    /**
180
     * Create bit array with initial size
181
     * @param size Initial size in bits
182
     */
183
    public BitArray(int size);
184
    
185
    /**
186
     * Get current size
187
     * @return Number of bits in array
188
     */
189
    public int getSize();
190
    
191
    /**
192
     * Get size in bytes (internal storage)
193
     * @return Number of bytes used for storage
194
     */
195
    public int getSizeInBytes();
196
    
197
    /**
198
     * Ensure array has at least specified size
199
     * @param size Minimum required size
200
     */
201
    public void ensureCapacity(int size);
202
    
203
    /**
204
     * Get bit value at index
205
     * @param i Bit index (0-based)
206
     * @return true if bit is set, false otherwise
207
     */
208
    public boolean get(int i);
209
    
210
    /**
211
     * Set bit at index
212
     * @param i Bit index
213
     */
214
    public void set(int i);
215
    
216
    /**
217
     * Toggle bit at index
218
     * @param i Bit index
219
     */
220
    public void flip(int i);
221
    
222
    /**
223
     * Find next set bit starting from index
224
     * @param from Starting index (inclusive)
225
     * @return Index of next set bit, or size if none found
226
     */
227
    public int getNextSet(int from);
228
    
229
    /**
230
     * Find next unset bit starting from index
231
     * @param from Starting index (inclusive)
232
     * @return Index of next unset bit, or size if none found
233
     */
234
    public int getNextUnset(int from);
235
    
236
    /**
237
     * Set range of bits
238
     * @param start Starting index (inclusive)
239
     * @param end Ending index (exclusive)
240
     */
241
    public void setBulk(int start, int end);
242
    
243
    /**
244
     * Clear all bits
245
     */
246
    public void clear();
247
    
248
    /**
249
     * Check if range is all set bits
250
     * @param start Starting index (inclusive)
251
     * @param end Ending index (exclusive)
252
     * @param value Value to check for (true = all set, false = all unset)
253
     * @return true if all bits in range match value
254
     */
255
    public boolean isRange(int start, int end, boolean value);
256
    
257
    /**
258
     * Append single bit
259
     * @param bit Bit value to append
260
     */
261
    public void appendBit(boolean bit);
262
    
263
    /**
264
     * Append multiple bits from integer
265
     * @param value Integer containing bits
266
     * @param numBits Number of bits to append (from LSB)
267
     */
268
    public void appendBits(int value, int numBits);
269
    
270
    /**
271
     * Append bits from another BitArray
272
     * @param other Source BitArray
273
     */
274
    public void appendBitArray(BitArray other);
275
    
276
    /**
277
     * XOR with another BitArray
278
     * @param other BitArray to XOR with
279
     */
280
    public void xor(BitArray other);
281
    
282
    /**
283
     * Convert to byte array
284
     * @return Byte array representation
285
     */
286
    public byte[] toBytes();
287
    
288
    /**
289
     * Reverse bit order
290
     */
291
    public void reverse();
292
    
293
    /**
294
     * Create deep copy
295
     * @return Cloned BitArray
296
     */
297
    public BitArray clone();
298
}
299
```
300

301
**Usage Examples:**
302

303
```java
304
// Create and build bit array
305
BitArray bits = new BitArray();
306

307
// Append individual bits
308
bits.appendBit(true);
309
bits.appendBit(false);
310
bits.appendBit(true);
311

312
// Append multiple bits at once
313
bits.appendBits(0b1101, 4); // Append 1101
314

315
// Work with existing array
316
BitArray row = new BitArray(100);
317
row.set(10);
318
row.set(20);
319
row.set(30);
320

321
// Search for patterns
322
int firstSet = row.getNextSet(0);    // 10
323
int nextSet = row.getNextSet(11);    // 20
324
int firstUnset = row.getNextUnset(10); // 11
325

326
// Range operations
327
row.setBulk(40, 50); // Set bits 40-49
328
boolean allSet = row.isRange(40, 50, true); // true
329

330
// Bit manipulation
331
row.flip(25); // Toggle bit 25
332
row.xor(otherArray); // XOR with another array
333
row.reverse(); // Reverse all bits
334
```
335

336
### BitSource
337

338
Helper class for sequential bit reading from byte arrays, commonly used in barcode decoding.
339

340
```java { .api }
341
/**
342
 * Helper for reading bits sequentially from byte array
343
 * Maintains reading position and handles bit boundaries
344
 */
345
public final class BitSource {
346
    /**
347
     * Create bit source from byte array
348
     * @param bytes Source byte array
349
     */
350
    public BitSource(byte[] bytes);
351
    
352
    /**
353
     * Get current bit position
354
     * @return Current reading position in bits
355
     */
356
    public int getBitOffset();
357
    
358
    /**
359
     * Get current byte position
360
     * @return Current reading position in bytes
361
     */
362
    public int getByteOffset();
363
    
364
    /**
365
     * Read specified number of bits
366
     * @param numBits Number of bits to read (1-32)
367
     * @return Integer containing the bits (right-aligned)
368
     * @throws IllegalArgumentException if not enough bits available
369
     */
370
    public int readBits(int numBits);
371
    
372
    /**
373
     * Get number of bits remaining
374
     * @return Available bits for reading
375
     */
376
    public int available();
377
}
378
```
379

380
**Usage Example:**
381

382
```java
383
byte[] data = {(byte)0b11010110, (byte)0b10101001};
384
BitSource source = new BitSource(data);
385

386
// Read various bit quantities
387
int twoBits = source.readBits(2);   // 11 (binary)
388
int threeBits = source.readBits(3); // 010 (binary)
389
int oneBit = source.readBits(1);    // 1 (binary)
390

391
System.out.println("Remaining bits: " + source.available());
392
System.out.println("Current position: " + source.getBitOffset());
393
```
394

395
### Geometric Utilities
396

397
Essential geometric classes for barcode detection and transformation.
398

399
```java { .api }
400
/**
401
 * Represents a point with floating-point coordinates
402
 */
403
public class ResultPoint {
404
    /**
405
     * Create result point
406
     * @param x X coordinate
407
     * @param y Y coordinate
408
     */
409
    public ResultPoint(float x, float y);
410
    
411
    /**
412
     * Get X coordinate
413
     * @return X position
414
     */
415
    public final float getX();
416
    
417
    /**
418
     * Get Y coordinate
419
     * @return Y position
420
     */
421
    public final float getY();
422
    
423
    /**
424
     * Calculate distance to another point
425
     * @param other Target point
426
     * @return Euclidean distance
427
     */
428
    public final float distance(ResultPoint other);
429
    
430
    /**
431
     * Cross product of vectors to two other points
432
     * @param pointA First point
433
     * @param pointB Second point
434
     * @return Cross product value
435
     */
436
    public final float crossProductZ(ResultPoint pointA, ResultPoint pointB);
437
    
438
    /**
439
     * Order three points by y-coordinate, then x-coordinate
440
     * @param patterns Array of exactly 3 points to order
441
     */
442
    public static void orderBestPatterns(ResultPoint[] patterns);
443
}
444

445
/**
446
 * Simple dimension class for width/height pairs
447
 */
448
public final class Dimension {
449
    /**
450
     * Create dimension
451
     * @param width Width value
452
     * @param height Height value
453
     */
454
    public Dimension(int width, int height);
455
    
456
    /**
457
     * Get width
458
     * @return Width value
459
     */
460
    public int getWidth();
461
    
462
    /**
463
     * Get height
464
     * @return Height value
465
     */
466
    public int getHeight();
467
}
468
```
469

470
### Perspective Transformation
471

472
Mathematical utilities for correcting perspective distortion in 2D barcodes.
473

474
```java { .api }
475
/**
476
 * Handles perspective transformation calculations
477
 * Used to correct skewed or angled barcode images
478
 */
479
public final class PerspectiveTransform {
480
    /**
481
     * Create transformation from four corner points
482
     * Maps unit square to arbitrary quadrilateral
483
     * @param x0 X coordinate of corner 0
484
     * @param y0 Y coordinate of corner 0
485
     * @param x1 X coordinate of corner 1
486
     * @param y1 Y coordinate of corner 1
487
     * @param x2 X coordinate of corner 2
488
     * @param y2 Y coordinate of corner 2
489
     * @param x3 X coordinate of corner 3
490
     * @param y3 Y coordinate of corner 3
491
     * @return PerspectiveTransform instance
492
     */
493
    public static PerspectiveTransform quadrilateralToQuadrilateral(
494
        float x0, float y0, float x1, float y1,
495
        float x2, float y2, float x3, float y3);
496
    
497
    /**
498
     * Create transformation to map unit square to quadrilateral
499
     * @param x0 X coordinate of corner 0
500
     * @param y0 Y coordinate of corner 0
501
     * @param x1 X coordinate of corner 1
502
     * @param y1 Y coordinate of corner 1
503
     * @param x2 X coordinate of corner 2
504
     * @param y2 Y coordinate of corner 2
505
     * @param x3 X coordinate of corner 3
506
     * @param y3 Y coordinate of corner 3
507
     * @return PerspectiveTransform instance
508
     */
509
    public static PerspectiveTransform squareToQuadrilateral(
510
        float x0, float y0, float x1, float y1,
511
        float x2, float y2, float x3, float y3);
512
    
513
    /**
514
     * Transform array of points
515
     * @param points Array of alternating x,y coordinates
516
     */
517
    public void transformPoints(float[] points);
518
    
519
    /**
520
     * Transform single point
521
     * @param points Array of length 2 containing x,y coordinates
522
     */
523
    public void transformPoints(float[] points, int offset, int length);
524
}
525
```
526

527
**Perspective Transformation Example:**
528

529
```java
530
// Correct perspective distortion for QR code detection
531
ResultPoint[] corners = detectCorners(); // Implementation-specific
532

533
// Create transformation from detected corners to square
534
PerspectiveTransform transform = PerspectiveTransform.quadrilateralToQuadrilateral(
535
    0, 0,                    // Unit square corner 0
536
    moduleSize, 0,           // Unit square corner 1  
537
    moduleSize, moduleSize,  // Unit square corner 2
538
    0, moduleSize,           // Unit square corner 3
539
    corners[0].getX(), corners[0].getY(), // Detected corner 0
540
    corners[1].getX(), corners[1].getY(), // Detected corner 1
541
    corners[2].getX(), corners[2].getY(), // Detected corner 2
542
    corners[3].getX(), corners[3].getY()  // Detected corner 3
543
);
544

545
// Apply transformation to sample points
546
float[] samplePoints = new float[] {x, y};
547
transform.transformPoints(samplePoints);
548
```
549

550
### Grid Sampling
551

552
Abstract framework for sampling bit matrices from transformed coordinates.
553

554
```java { .api }
555
/**
556
 * Abstract base for sampling grids from bit matrices
557
 * Used to extract regular grids from detected barcode regions
558
 */
559
public abstract class GridSampler {
560
    /**
561
     * Get the singleton instance
562
     * @return GridSampler instance
563
     */
564
    public static GridSampler getInstance();
565
    
566
    /**
567
     * Set the singleton instance
568
     * @param newGridSampler GridSampler implementation to use
569
     */
570
    public static void setGridSampler(GridSampler newGridSampler);
571
    
572
    /**
573
     * Sample a grid from bit matrix using perspective transformation
574
     * @param image Source bit matrix
575
     * @param dimensionX Width of output grid
576
     * @param dimensionY Height of output grid
577
     * @param transform Perspective transformation to apply
578
     * @return Sampled bit matrix
579
     * @throws NotFoundException if sampling fails
580
     */
581
    public abstract BitMatrix sampleGrid(BitMatrix image, int dimensionX, int dimensionY,
582
                                        PerspectiveTransform transform) throws NotFoundException;
583
    
584
    /**
585
     * Sample grid with explicit corner coordinates
586
     * @param image Source bit matrix
587
     * @param dimensionX Width of output grid
588
     * @param dimensionY Height of output grid
589
     * @param p1ToX X coordinate mapping for corner 1
590
     * @param p1ToY Y coordinate mapping for corner 1
591
     * @param p2ToX X coordinate mapping for corner 2
592
     * @param p2ToY Y coordinate mapping for corner 2
593
     * @param p3ToX X coordinate mapping for corner 3
594
     * @param p3ToY Y coordinate mapping for corner 3
595
     * @param p4ToX X coordinate mapping for corner 4
596
     * @param p4ToY Y coordinate mapping for corner 4
597
     * @return Sampled bit matrix
598
     * @throws NotFoundException if sampling fails
599
     */
600
    public abstract BitMatrix sampleGrid(BitMatrix image, int dimensionX, int dimensionY,
601
                                        float p1ToX, float p1ToY, float p2ToX, float p2ToY,
602
                                        float p3ToX, float p3ToY, float p4ToX, float p4ToY)
603
                                        throws NotFoundException;
604
}
605

606
/**
607
 * Default grid sampling implementation
608
 */
609
public final class DefaultGridSampler extends GridSampler {
610
    // Implementation of abstract methods
611
}
612
```
613

614
## Data Structure Integration
615

616
### Conversion Between Structures
617

618
```java
619
// BitMatrix to BitArray (row extraction)
620
BitMatrix matrix = new BitMatrix(100, 50);
621
BitArray row = matrix.getRow(25, null);
622

623
// BitArray to BitMatrix (building matrix row by row)
624
BitMatrix matrix = new BitMatrix(width, height);
625
for (int y = 0; y < height; y++) {
626
    BitArray row = generateRow(y); // Implementation-specific
627
    matrix.setRow(y, row);
628
}
629

630
// Byte array to BitSource for sequential reading
631
byte[] encodedData = getEncodedData(); // Implementation-specific
632
BitSource source = new BitSource(encodedData);
633
```
634

635
### Memory-Efficient Operations
636

637
```java
638
// Reuse BitArray objects to avoid allocation
639
BitArray reusableRow = new BitArray();
640
for (int y = 0; y < height; y++) {
641
    BitArray row = matrix.getRow(y, reusableRow); // Reuses existing array
642
    processRow(row);
643
}
644

645
// Work with bit ranges instead of copying entire arrays
646
BitArray data = new BitArray(1000);
647
if (data.isRange(100, 200, true)) {
648
    // All bits in range 100-199 are set
649
    processSetRegion(100, 200);
650
}
651
```
652

653
### Performance Considerations
654

655
- **BitMatrix**: Efficient for random access, rectangular operations
656
- **BitArray**: Optimized for sequential access, append operations
657
- **BitSource**: Best for stream-like bit reading with position tracking
658
- **Reuse objects**: Pre-allocate arrays and reuse to minimize garbage collection
659
- **Bulk operations**: Use `setBulk()`, `setRegion()` for better performance than individual bit operations