Warp wrote:

>   Without seeing the whole program it's impossible to tell.

Well, the program isn't that large, so just for a giggle I'll include it 
here. The compiler claims there's nothing wrong with it, but clearly 
there is. I can't wait to see how many different kinds of mistake I've 
made... :-}



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

typedef char Symbol;
typedef std::vector<bool> Codeword;

std::string codeword(const Codeword &c)
{
   std::string out;

   for (unsigned int i=0; i<c.size(); i++)
     if (c[i]) out.append("1"); else out.append("0");

   return out;
}

class SymbolInfo
{
public:
   Symbol symbol;
   double prob;
   Codeword code;

   SymbolInfo(Symbol s, double pr) : code()
   {
     symbol = s;
     prob = pr;
   }

   void prefix(const bool p)
   {
     code.push_back(p);
   }
};

class Tree
{
public:
   Tree(SymbolInfo& s) : symbols()
   {
     symbols.push_back(s);
     prob = s.prob;
   }

   void join(const Tree& tree)
   {
     for (unsigned int i=0; i<symbols.size(); i++)
       symbols[i].prefix(false);

     for (unsigned int i=0; i<tree.symbols.size(); i++)
     {
       SymbolInfo s = tree.symbols[i];
       s.prefix(true);
       symbols.push_back(s);
       prob += s.prob;
     }
   }

   const Codeword& lookup(const Symbol key)
   {
     for (unsigned int i=0; i<symbols.size(); i++)
       if (symbols[i].symbol == key) return symbols[i].code;
   }

   const double Prob() {return prob;}

private:
   std::vector<SymbolInfo> symbols;
   double prob;
};

const Tree& build_tree(std::vector<SymbolInfo> info)
{
   std::vector<Tree> trees;

   for (unsigned int i=0; i<info.size(); i++)
   {
     Tree t(info[i]);
     trees.push_back(t);
   }

   while (trees.size() > 1)
   {
     int index = 0;
     for (unsigned int i = 1; i<trees.size(); i++)
       if (trees[i].Prob() < trees[index].Prob()) index = i;

     Tree t0 = trees[index];
     trees.erase(trees.begin() + index);

     index = 0;
     for (unsigned int i = 1; i<trees.size(); i++)
       if (trees[i].Prob() < trees[index].Prob()) index = i;

     Tree t1 = trees[index];
     trees.erase(trees.begin() + index);

     t0.join(t1);
     trees.push_back(t0);
   }

   return trees[0];
}

int main()
{
   SymbolInfo A('A', 0.5);
   SymbolInfo B('B', 0.25);
   SymbolInfo C('C', 0.125);
   SymbolInfo D('D', 0.125);
   std::vector<SymbolInfo> symbols;
   symbols.push_back(A);
   symbols.push_back(B);
   symbols.push_back(C);
   symbols.push_back(D);
   Tree t = build_tree(symbols);

   std::cout << "A: " << codeword(t.lookup('A')) << std::endl;
   std::cout << "B: " << codeword(t.lookup('B')) << std::endl;
   std::cout << "C: " << codeword(t.lookup('C')) << std::endl;
   std::cout << "D: " << codeword(t.lookup('D')) << std::endl;
}

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message