//
// huff.cpp
//
// (c) Copyright 2000 William A. McKee.  All rights reserved.
//
// Created April 27, 2000
//
// STL implementation of Huffman encoding.
//
// Compiled with VC++ 6.0: cl /GX huff.cpp
//
// Modification suggested by TiTi(tm), 28/04/2000
//   - make Print virtual
//
// Suggestion by NeilB (April 28, 2000)
//   - private data, protected accessors
//   - "IMHO typedefs like this obfuscate the code rather than make it 
//     clearer." [I tend to agree, so I removed the typedef. - WAM]

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

using namespace std;

class Node
{
private :
    int const weight;
protected :
    Node (int const w) : weight (w) {}
    int Weight () const { return weight; }
public :
    virtual ~Node () {}
    Node operator + (const Node & rhs) const
        { return Node (weight + rhs.weight); }
    bool operator > (const Node & rhs) const
        { return weight > rhs.weight; }
    virtual void Print (string & str) const = 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 Print (string & str) const;
};

class Interior : public Node
{
private :
    const Node * const left;
    const Node * const right;
public :
    virtual ~Interior () { delete left; delete right; }
    Interior (const Node * const l, const Node * const r)
        : Node (*l + *r), left (l), right (r) {}
    virtual void Print (string & str) const;
};

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

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

void Leaf::Print (string & str) const
{
    cout << str << "," << code << "," << Weight () << endl;
}

void Interior::Print (string & str) const
{
    str += '0';
    left -> Print (str);
    str.resize (str.size () - 1);

    str += '1';
    right -> Print (str);
    str.resize (str.size () - 1);
}

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

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

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

int main (int argc, char * * argv)
{
    if (argc < 2)
    {
        char * default_data [] = { NULL,
            "15", "4", "17", "8", "30", "12", "41", "10", "6", "19", "27" };

        argc = sizeof (default_data) / sizeof (*default_data);
        argv = default_data;
    }

    vector<const Node *> data;

    for (int i = 1; i < argc; i++)
    {
        data.push_back (new Leaf (atoi (argv [i]), i));
        data.back () -> Print (string ());
    }

    cout << "Huffman encoding:" << endl;

    const Node * const root = BuildHuffman (data);

    if (root != NULL)
    {
        root -> Print (string ());
        delete root;
    }

    return EXIT_SUCCESS;
}