ETH_Informatik/Informatik_I/Exercise_5/Task_4

Task 4: Run-length encoding

• Task
• Solution

Task

Run-length encoding is a simple data compression technique that represents \(N\) consecutive identical values \(W\) (a run) by a tuple (\(N,W\)). This method is applied for image compression, for instance. Example:

Write a program that implements run-length encoding and decoding of a byte sequence as described above. By a byte, we mean an integer value in the range \([ 0; 255 ]\). Use the stepwise refinement method to implement the program. Your solution must consist of at least two functions, encode and decode. Please implement them in run_length.cpp.

The input is structured as follows:

1. One integer that determines whether to encode: \(0\) or decode: \(1\).
2. Byte sequence to be encoded or decoded (of arbitrary length). If a value outside the range \([ 0; 255 ]\) (except $-1$) is entered, output error and stop the en- or decoding.
3. Integer -1 signaling the end of the byte sequence. Any extra input should be ignored.

For the example above, the inputs are:

Encode:

0 42 42 85 85 85 85 172 172 172 13 13 42 -1

Decode:

1 2 42 4 85 3 172 2 13 1 42 -1

The output is expected on a single line in the following format:

1. A start value to indicate the begin of the sequence: either \(0\) for decoded values or \(1\) for encoded values.
2. The values that make up the encoded or decoded byte sequence.
3. The value \(-1\) to indicate the end of the sequence.

I.e., you can 'reuse' the output as the input.

Note 1): As the encoded sequence must be a byte sequence, runs of length 256 or longer need to be split into multiple runs of length 255 at most.

Note 2): The first input element (the integer that determines wether to encode or decode), is already consumed by the main, that calls either the encode or decode function.

Note 3): Your output should not be followed by new line (i.e., do not use std::endl or \n at the end of your printout)

Note 4): The program will print your output (the result of the decoding or encoding), surrounded by asterisks. You don't have to worry about them, the autograder can safely recognize your solution

Note 5): Output only what is strictly required (the encoded or decoded sequence). The autograder will only accept output that exactly matches the expected result. For all other messages, use std::cerr as in:

std::cerr << "This is a test message\n"

Those will be ignored by the autograder.

Special cases: While decoding a byte sequence two special cases can occur. These must be handled as follows:

1. If a byte sequence ends in the middle of a tuple, stop printing the output of en- or decoding and output error.
2. Tuples of run-length 0 are possible. For such tuples, output only the leading indicator (\(0\)/\(1\)) and the trailing \(-1\).

Hint: You can enter multiple numbers at once separated with a space on the console, e.g, you can copy and paste the above examples, and sequentially read them using multiple std::cin >> _var_ calls.

Also note that, even though the program's output and the user input are both shown in the same console, they are processed separately internally, so you do not have to worry that the two will mix: if your program outputs something to the console before reading another value, it will only read the user input and not the previous output value. See the Calculator code in the Lecture 4 handout for an example of reading input and producing output in a loop.

Finally, part of the correctness for this task is the termination of your code, so pay attention to this. The autograder may not catch these kinds of mistakes.

Restrictions: using a vector, an array or a similar data structure in any part of your code is not allowed and would result in 0 points.

Solution

#include "run_length.h"

void encode() {
  int i;
  int c;
  int count;
  std::cin >> i;
  std::cout << 1 << " ";
  while (i != -1) {
    count = 0;
    c = i;
    while (i == c && i >= 0 && i <= 255) {
      ++count;
      std::cin >> i;
      if (count == 255) {
        break;
      }
    }
    if (i < -1 || i > 255) {
      if (count == 0) {
        std::cout << "error";
        return;
      } else {
        std::cout << count << " ";
        std::cout << c << " ";
        std::cout << "error";
        return;
      }
    }
    std::cout << count << " ";
    std::cout << c << " ";
  }
  std::cout << -1;
}

void decode() {
  int i;
  int count;
  std::cin >> count;
  std::cin >> i;
  std::cout << 0 << " ";
  while (count != -1) {
    if (i < -1 || i > 255) {
      std::cout << "error";
      return;
    }
    if (count < -1 || count > 255) {
      std::cout << "error";
      return;
    }
    for (int j = 0; j < count; ++j) {
      std::cout << i << " ";
    }
    std::cin >> count;
    if (count != -1)
      std::cin >> i;
    if (i == -1) {
      std::cout << "error";
      return;
    }
  }
  std::cout << -1;
}

---

Made by JirR02 in Switzerland 🇨🇭