Chapter 18. File compression

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 18: File Compression and Decompression

// Huffman code

#include "pq.h"

#define nil (-1)

class HuffmanTree {
  struct node { int L, RorCh; };
  node *Htree;
  int n, root;
public:
  HuffmanTree(const unsigned long *freq);
  ~HuffmanTree() { delete []Htree; }
  int NewNode(int L, int x) {
    Htree[n].L = L; Htree[n++].RorCh = x;
    return n - 1;
  }
  int getroot() { return root; }
  friend void traverse(class HuffmanTree &, struct CodeTable *,
		       int, unsigned int code=0, int len=0);
};

struct item {
  unsigned long freq;
  int ptr;
  item(){}
  item(unsigned long f, int p): freq(f), ptr(p){}
  int operator>(item &x){return freq < x.freq;}
};

HuffmanTree::HuffmanTree(const unsigned long *freq) {
  Htree = new node[511];
  n = 0;
  PQ<item> pq(256);  // Size of priority queue
  for (int j=0; j<256; j++)
    if (freq[j]) pq.insert(item(freq[j], NewNode(nil, j)));
  item t1, t2;
  if (pq.empty()) cout << "Empty input file." << endl; 
  else {
    for (;;) {
      t1 = pq.remove();
      if (pq.empty()) break;
      t2 = pq.remove();
      pq.insert(item(t1.freq + t2.freq,
		     NewNode(t1.ptr, t2.ptr)));
    }
    root = t1.ptr;
  }
}

struct CodeTable { unsigned code, len; }; // For code table

void traverse(HuffmanTree &Tr, CodeTable *t, int p,
	      unsigned code, int len) {
  if (Tr.Htree[p].L == nil) {
    unsigned char ch = Tr.Htree[p].RorCh;
    t[ch].code = code; 
    t[ch].len = len;
    cout <<"ch: " << ch << "  code: " << code << "  len:" << len << endl;
  }
  else {
    code <<= 1; len++;
    traverse(Tr, t, Tr.Htree[p].L, code, len);
    traverse(Tr, t, Tr.Htree[p].RorCh, code | 1, len);
  }
}

int main() {
  cout << "Huffman code.\n";
  unsigned long freq[256];
  unsigned char ch;
  int j, k, b;
  char s[] = "AAABBBCCDEFGGGGGHHZZ"; 			// *s -> s[]

  for (j=0; j<256; j++) freq[j] = 0;
  j=0;
  while (ch=s[j++]) freq[ch]++;
  
  HuffmanTree Tr(freq);
  
  CodeTable t[256]; // t is the code table
  for (int i=0; i<256; i++) t[i].code = t[i].len = 0;
 
  traverse(Tr, t, Tr.getroot());
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 18: File Compression and Decompression

// Priority queue class
// File name: pq.h

#include <iostream>
using namespace std;

template <class Type>
class PQ {
  Type *array;
  int MaxSize, Nel, ChunkSize;
  void adjustH();
public:
  PQ(int size, int incr=10) {  
    MaxSize = size;
    array = new Type[MaxSize];
    Nel = 0; ChunkSize = incr;
  }
  ~PQ() { delete[]array; }
  void insert(Type item);
  Type remove();
  int empty() { return Nel == 0; }
};

template <class Type>
void PQ<Type>::insert(Type item) {
  int i, j;
  if (Nel == MaxSize) {
    Type *aOld = array;
    array = new Type[MaxSize += ChunkSize];
    for (i=0; i<Nel; i++) array[i] = aOld[i];
    delete[] aOld;
  }
  i = Nel++;
  while (i > 0 && item > array[(i-1)/2]) {
    array[i] = array[(i-1)/2]; i = (i-1)/2;
  }
  array[i] = item;
}

template <class Type>
Type PQ<Type>::remove() {
  Type item = array[0];
  array[0] = array[--Nel];
  adjustH();
  return item;
}

template <class Type> 
void PQ<Type>::adjustH() {
  int i = 0, j;
  Type item = array[0];
  while ((j = 2 * i + 1) < Nel) {
    if (j < Nel - 1 && array[j+1] > array[j]) j++;
    if (array[j]>item) {
      array[i] = array[j]; i = j; 
    }
    else break;
  }
  array[i] = item;
}