You are implementing a simple compression scheme for sequences of 32‑bit signed integers. The codec should support **two encoding strategies**: 1. **Run‑Length Encoding (RLE)** for long runs of equal values. 2. **Bit‑Packed Encoding (BP)** for blocks of values that can be represented with a small, uniform bit‑width. The codec is **streaming**: values arrive one by one, and the encoder should buffer them into blocks and choose an encoding strategy per block. ### Compressed representation Design a compressed representation made of **blocks**. For concreteness, define: - **RLE block** - Represents a run of a single repeated integer value. - Fields: - `type = 'R'` - `value` (int32) - `count` (int, number of repetitions) - Only use RLE blocks when `count >= RLE_MIN_RUN` (e.g., `RLE_MIN_RUN = 3`). Shorter runs should not be encoded as RLE. - **Bit‑packed block** - Represents a sequence of `count` possibly different integers, all of which fit into `bitWidth` bits in two's‑complement representation. - Fields: - `type = 'B'` - `bitWidth` (1–32) - `count` (number of values) - A packed payload containing exactly `count` values, each stored using `bitWidth` bits. - You may choose a **maximum block size** `MAX_BP_BLOCK` (e.g., 128 values) for simplicity. You can decide the in‑memory representation of a bit‑packed payload (e.g., array of 32‑bit integers where bits are tightly packed), as long as the decoder can reconstruct the original sequence exactly. ### Encoder Implement an `Encoder` class with the following behavior: - It receives input values **one at a time** via a method like: ```text void add(int value) ``` - Internally, the encoder may maintain a buffer of recent values to decide whether to form an RLE block or a bit‑packed block. - At appropriate times (e.g., when a block is full, when the encoding strategy should change, or when `flush()` is called), it should **emit blocks**. - Provide a method: ```text List<Block> flush() ``` that finalizes the stream, closes any open block, and returns the list of compressed blocks. **Encoding strategy constraints:** - For a maximal run of the same value with length `L`: - If `L >= RLE_MIN_RUN`, you should encode it as a single RLE block. - Otherwise, those values should be part of a bit‑packed block. - For bit‑packed blocks: - You may group consecutive non‑RLE values into blocks up to size `MAX_BP_BLOCK`. - Choose `bitWidth` for a block as the minimum number of bits needed to represent **all** its values. - You do **not** need to prove global optimality of the compression, but your encoder must consistently follow the above rules. The encoder must correctly handle: - Negative values and the full range of 32‑bit signed integers (`Integer.MIN_VALUE` to `Integer.MAX_VALUE`). - Transitions between RLE and bit‑packed segments in the stream. ### Decoder Implement a corresponding `Decoder` that reconstructs the original integer sequence from a list of blocks. - Its constructor receives the list of blocks produced by the encoder: ```text class Decoder implements Iterator<Integer> { Decoder(List<Block> blocks) { ... } boolean hasNext(); int next(); } ``` - `hasNext()` / `next()` should expose the **original sequence of integers** in order, exactly as they were passed to `Encoder.add(...)`. - The decoder must correctly iterate across both RLE and bit‑packed blocks. ### Tasks 1. Specify the exact in‑memory structure you will use for `Block` and the bit‑packed payload. 2. Implement `Encoder.add(value)` and `Encoder.flush()` to produce a valid block sequence. 3. Implement `Decoder` as an iterator over the decompressed values. 4. Write unit tests for cases including: - Simple sequences without repeats (forces bit‑packing). - Long runs of a single value (forces RLE). - Alternating patterns (switching between RLE and BP). - Values near `Integer.MAX_VALUE`, `Integer.MIN_VALUE`, and negative numbers. - Empty input sequence. Assume you are working in an object‑oriented language (e.g., Java, C++, or similar) and focus on clean class design and correctness of the codec pair.