//
// huffman.h
//
// (c) Copyright 2000 William A. McKee.  All rights reserved.
//
// Created April 29, 2000
//

#include <vector>
#include <algorithm>
#include <string>

#include "table.h"

class Encoding
{
public :
    std::string huffman_string;
    Encoding () { }
    ~Encoding () { }
    Encoding & operator = (Encoding & rhs)
    {
        huffman_string = rhs.huffman_string;
        return *this;
    }
};

class Node
{
private :
    int const weight;
    Node * dummy;
protected :
    int Weight () const { return weight; }
public :
    Node (int const w) : weight (w) { dummy = NULL; }
    virtual ~Node () {}
    int operator + (const Node & rhs) const { return weight + rhs.weight; }
    bool operator > (const Node & rhs) const { return weight > rhs.weight; }
    virtual void Encode (std::string & str, Table<Encoding> & table) const = 0;
    virtual Node * & Left () { return dummy; }
    virtual Node * & Right () { return dummy; }
    virtual bool IsLeaf () const { return false; }
    virtual int Code () const { return 0; }
};

class Leaf : public Node
{
private :
    int const code;
public :
    virtual ~Leaf () {}
    Leaf (int const w, int const c)
        : Node (w), code (c) {}
    virtual void Encode (std::string & str, Table<Encoding> & table) const
    {
        table [code].huffman_string = str;
    }
    virtual bool IsLeaf () const { return true; }
    virtual int Code () const { return code; }
};

class Interior : public Node
{
private :
    Node * left;
    Node * right;
public :
    virtual ~Interior () { delete left; delete right; }
    Interior (Node * l, Node * r)
        : Node ((l == NULL ? 0 : *l) + (r == NULL ? 0 : *r)),
          left (l), right (r) {}
    virtual void Encode (std::string & str, Table<Encoding> & table) const
    {
        str += '0';
        left -> Encode (str, table);
        str.resize (str.size () - 1);

        str += '1';
        right -> Encode (str, table);
        str.resize (str.size () - 1);
    }
    virtual Node * & Left () { return left; }
    virtual Node * & Right () { return right; }
};

class NodeCompare
{
public :
    int operator () (const Node * const & lhs, const Node * const & rhs) const
    {
    // sort largest to smallest by weight

        return (*lhs > *rhs);
    }
};

inline Node * BuildHuffman (std::vector<Node *> & data)
{
    if (! data.empty ())
    for (;;)
    {
        std::sort (data.begin (), data.end (), NodeCompare ());

        Node * const last = data.back ();
        data.pop_back ();
        if (data.empty ())
            return last;

        Node * const next = data.back ();
        data.pop_back ();
        data.push_back (new Interior (last, next));
    }
    return NULL;
}