Haffman

#include <iostream>

// Найти степень двойки, не превосходящей n
int MaxPower(int n) {
  int power = 1;
  while (power <= n) {
    power <<= 1;
  }
  return power >> 1;
}

int MaxPower2(int n) {
  int power = 1;
  while (n > 1) {
    n >>= 1;
    power <<= 1;
  }
  return power;
}

int MaxPower3(int n) {
  int power = 1;
  while (n > 0) {
    power <<= 1;
    n >>= 1;
  }
  return power >> 1;
}




typedef char byte;

struct IInputStream {
  // Возвращает false, если поток закончился
  virtual bool Read(byte& value) = 0;
};

struct IOutputStream {
  virtual void Write(byte value) = 0;
};

class OutputStream : public IOutputStream {
 public:
  void Write(byte value) override { std::cout << value; }
};


class BitWriter {
 public:
  explicit BitWriter(IOutputStream& out_stream) : out_stream_(out_stream) {}

  void WriteBit(bool bit);
  void WriteByte(byte b);

 private:
  IOutputStream& out_stream_;
  byte buffer = 0;
  int buffer_length = 0;  // От 0 до 7.
};

void BitWriter::WriteBit(bool bit) {
  // Закинем бит в буфер.
  buffer = (bit ? 1 : 0) << (7 - buffer_length);
  ++buffer_length;
  // Если буфер заполнился (его длина стала равна 8), то сбрасываем в out_stream.
  if (buffer_length == 8) {
    out_stream_.Write(buffer);
    buffer = 0;
    buffer_length = 0;
  }
}
void BitWriter::WriteByte(byte b) {
  // Если буфер пуст, то сразу сбрасываем b в out_stream.
  if (buffer_length == 0) {
    out_stream_.Write(b);
    return;
  }
  // Иначе: Дополняем buffer первой частью b.
  // 00000|101 -> 101|00000 -> 101|bbbbb
  int first_part_length = 8 - buffer_length;
  buffer <<= 8 - buffer_length;
  buffer += b >> buffer_length;
  // Скидываем в out_stream.
  out_stream_.Write(buffer);
  // Вторую часть b кладем в buffer. bbb|00000
  buffer = b << (8 - buffer_length);
}

void Encode(IInputStream& original, IOutputStream& compressed);
void Decode(IInputStream& compressed, IOutputStream& original);


int main() {
//  int n = 0;
//  std::cin >> n;
//  std::cout << MaxPower(n) << std::endl;
//  std::cout << MaxPower2(n) << std::endl;
//  std::cout << MaxPower3(n) << std::endl;
  OutputStream output;
  BitWriter bit_writer(output);
  // Пишем дерево 10a110b10c0d0r.
  bit_writer.WriteBit(true);
  bit_writer.WriteBit(false);
  bit_writer.WriteByte('a');
  bit_writer.WriteBit(true);
  bit_writer.WriteBit(true);
  bit_writer.WriteBit(false);
  bit_writer.WriteByte('b');
  bit_writer.WriteBit(true);
  bit_writer.WriteBit(false);
  bit_writer.WriteByte('c');
  bit_writer.WriteBit(false);
  bit_writer.WriteByte('d');
  bit_writer.WriteBit(false);
  bit_writer.WriteByte('r');
  // Нужно финализировать – последний буфер скинуть в byte.
  // Можно отдельно записать число неиспользуемых бит в потоке.
  return 0;
}