// huffman.cpp
// Build a Huffman tree from a list of alphabet elements
// and their weights.
// Steve Tanimoto, 7 October 1999.

// This program builds a Huffman tree from a set of letters
// with associated weights.
// The implementations of insert and deleteMin here are very
// inefficient, since the point of this program is to
// demonstrate the "greedy" Huffman tree construction,
// rather than, say, heap implementations of priority queues.
// Therefore this program runs in O(N^2) time
// but not in O(N log N) as it would if it used a heap.

// The data in this demonstration is hard-coded into
// a pair of static (global) arrays: letters[] and weights[].
// This simplifies the presentation but is not a suitable
// style in which to write an actual software tool.
// In that case, we would avoid global variables and
// have the data read from a file.

#include <stdio.h>
#include "huffman.h"

#define N 7

void HNode::setLeftChild(HNode *theLC) {
    lc = theLC;
}

void HNode::setRightChild(HNode *theRC) {
    rc = theRC;
}

HNode *HNode::getLC()     { return lc; }
HNode *HNode::getRC()     { return rc; }
char   HNode::getLetter() { return letter; }
float  HNode::getWeight() { return weight; }

static char  letters[N] = {'a', 'b', 'c', 'd', 'e',  'f',  'g'};
static float weights[N] = {0.2, 0.1, 0.1, 0.1, 0.4, 0.05, 0.05};
static HNode *trees[N];

HNode *deleteMin() {
  float smallestWeight = 100.0;
  int indexOfSmallest = -1;
  HNode *smallest = NULL;
  for (int i=0; i<N; i++) {
    if (trees[i] != NULL) {
      float w = trees[i]->getWeight();
      if (w < smallestWeight) {
        smallestWeight = w;
        indexOfSmallest = i;
      }
    }
  }
  printf("\nIn deleteMin indexOfSmallest is %d.\n",
         indexOfSmallest);
  if (indexOfSmallest == -1) return NULL;
  smallest = trees[indexOfSmallest];
  trees[indexOfSmallest] = NULL;
  return smallest;
}

void insert(HNode *hn) {
  // Find the first NULL array entry:
  int indexOfFreePosition = -1;
  for (int i=0; i<N; i++) {
    if (trees[i] == NULL) {
      indexOfFreePosition = i;
      break;
    }
  }
  printf("\nIn insert, indexOfFreePosition is %d.\n", 
         indexOfFreePosition);
  // Insert the node pointer there:
  trees[indexOfFreePosition] = hn;
}

void display(HNode *hn, int depth) {
  // Do an inorder tree traversal, printing the weight
  // and letter (if any) of each node, indented according
  // to its tree depth.
  // The result is a tree diagram, printed sideways.

  if (hn->getLC() != NULL) display(hn->getLC(), depth + 1);
  for (int i=0; i<depth; i++) printf("     ");
  printf("%3.2f", hn->getWeight());
  if (hn->getLC() == NULL) printf(" -- %c", hn->getLetter());
  printf("\n");
  if (hn->getRC() != NULL) display(hn->getRC(), depth + 1);
}

int main() {
  int i;
  float w;
  char c;
  HNode *hn1, *hn2, *hn3;

  printf("\nBeginning Huffman tree construction.\n");

  printf("\nInitializing the forest of trees.\n");

  // Create a 1-node tree for each alphabet element:
  for (i=0; i<N; i++) {
    trees[i] = new HNode(letters[i], weights[i]);
  }

  printf("\nCombining trees.\n");

  for (i=0; i<N-1; i++) {
    // Find the two lowest-weight trees:
    // (Here is what makes this a "greedy" algorithm.)
    hn1 = deleteMin();
    hn2 = deleteMin();
    // Combine them, by making them children of a new node:
    hn3 = new HNode('-', hn1->getWeight() + hn2->getWeight());
    hn3->setLeftChild(hn1);
    hn3->setRightChild(hn2);
    // Enter the new tree into the forest:
    insert(hn3);
  }

  printf("\nAnd here is the Huffman tree.\n\n");
  display(hn3, 0);
}