dune::HuffTree Struct Reference

#include <FelixCompress.hh>

Classes
struct	Node

Public Member Functions
bool	valuecomp (const Node &one, const Node &other) const
Node *	operator() (const uint16_t value)
void	print (Node *loc)
void	print ()
void	printFile (std::string &filename)
void	generate_codes (Node *loc, size_t buff=0, uint8_t len=0)
void	generate_codes ()
std::unordered_map< uint16_t, Node * >	make_tree (std::vector< Node > nodevec)
	~HuffTree ()

Public Attributes
Node *	root
Node *	nodelist
std::unordered_map< uint16_t, Node * >	nodes

Detailed Description

Definition at line 29 of file FelixCompress.hh.

Constructor & Destructor Documentation

dune::HuffTree::~HuffTree ( )

inline

Definition at line 190 of file FelixCompress.hh.

{ delete[] nodelist; }

Member Function Documentation

void dune::HuffTree::generate_codes ( Node *  loc, size_t  buff = 0, uint8_t  len = 0  )

inline

Definition at line 114 of file FelixCompress.hh.

                                                                   {
    // Assign a string when a leaf is reached. Otherwise go one layer deeper.
    if (loc->left == NULL) {
      loc->huffcode = buff;
      loc->hufflength = len;
      nodes[loc->value] = loc;
    } else {
      // Move one node down.
      generate_codes(loc->left, buff, len + 1);
      generate_codes(loc->right, buff | (1 << len), len + 1);
    }

    // Move one node up.
    return;
  }

void dune::HuffTree::generate_codes ( )

inline

Definition at line 129 of file FelixCompress.hh.

{ return generate_codes(root); }

std::unordered_map<uint16_t, Node*> dune::HuffTree::make_tree ( std::vector< Node >  nodevec )

inline

Definition at line 132 of file FelixCompress.hh.

                                                                       {
    // Order vector to get the same results every time.
    std::sort(nodevec.begin(), nodevec.end());
    // Create a new buffer to hold the leaves and N-1 new nodes.
    const unsigned totlen = 2 * nodevec.size() - 1;
    Node* begin = &nodevec[0];
    nodelist = new Node[totlen];
    std::copy(begin, begin + nodevec.size(), nodelist);

    // Continue until the buffer is filled.
    for (unsigned i = 0; i < totlen - nodevec.size(); ++i) {
      // Find the lowest-frequency non-parented nodes.
      Node* lowest = nodelist;
      while (lowest->hasParent) {
        ++lowest;
      }
      Node* sec_lowest = lowest + 1;
      while (sec_lowest->hasParent) {
        ++sec_lowest;
      }
      for (Node* n = nodelist; n != nodelist + nodevec.size() + i; ++n) {
        // Disregard parented nodes.
        if (n->hasParent) {
          continue;
        }
        if (n->frequency < lowest->frequency) {
          sec_lowest = lowest;
          lowest = n;
        } else if (n->frequency < sec_lowest->frequency && n != lowest) {
          sec_lowest = n;
        }
      }

      // Make lowest value the left node in case of equal frequency.
      if (lowest->frequency == sec_lowest->frequency &&
          lowest->value > sec_lowest->value) {
        Node* tmp = lowest;
        lowest = sec_lowest;
        sec_lowest = tmp;
      }

      // Link the lowest frequency nodes to a new one in the buffer.
      Node* newNode = &nodelist[nodevec.size() + i];
      newNode->left = lowest;
      newNode->right = sec_lowest;
      newNode->frequency = lowest->frequency + sec_lowest->frequency;
      lowest->hasParent = true;
      sec_lowest->hasParent = true;
    }

    // Assign root to the last unparented node and generate codes.
    root = &nodelist[totlen - 1];
    generate_codes();

    // Output the generated map.
    return nodes;
  }

Node* dune::HuffTree::operator() ( const uint16_t  value )

inline

Definition at line 68 of file FelixCompress.hh.

{ return nodes[value]; }

void dune::HuffTree::print ( Node *  loc )

inline

Definition at line 71 of file FelixCompress.hh.

                        {
    if (loc->left == NULL) {
      std::cout << "Node with value " << loc->value << ", frequency "
                << loc->frequency << " and huffcode "
                << std::bitset<32>(loc->huffcode) << " length "
                << (unsigned)loc->hufflength << '\n';
    } else {
      print(loc->left);
      print(loc->right);
    }
    return;
  }

void dune::HuffTree::print ( )

inline

Definition at line 83 of file FelixCompress.hh.

{ return print(root); }

void dune::HuffTree::printFile ( std::string &  filename )

inline

Definition at line 86 of file FelixCompress.hh.

                                      {
    std::ofstream ofile(filename);

    ofile << "Value\tFrequency\tCode\tLength\n";
    std::vector<Node*> local_nlist;

    for(auto p : nodes) {
      Node* n = p.second;
      if(n->frequency == 0) continue;
      local_nlist.push_back(n);
    }

    std::sort(local_nlist.begin(), local_nlist.end());

    for(unsigned i = 0; i < local_nlist.size(); ++i) {
      Node* n = local_nlist[i];
      if(n->value > (1<<16)/2) {
        ofile << (int)n->value-(1<<16) << '\t' << n->frequency << '\t' << n->huffcode << '\t' << (unsigned)n->hufflength << '\n';
      } else {
        if(n->value > 1000) continue; // Disregard start values.
        ofile << n->value << '\t' << n->frequency << '\t' << n->huffcode << '\t' << (unsigned)n->hufflength << '\n';
      }
    }

    ofile.close();
  }

bool dune::HuffTree::valuecomp ( const Node &  one, const Node &  other  ) const

inline

Definition at line 59 of file FelixCompress.hh.

                                                           {
    return one.value < other.value;
  }

Member Data Documentation

Node* dune::HuffTree::nodelist

Definition at line 64 of file FelixCompress.hh.

std::unordered_map<uint16_t, Node*> dune::HuffTree::nodes

Definition at line 65 of file FelixCompress.hh.

Node* dune::HuffTree::root

Definition at line 63 of file FelixCompress.hh.

---

The documentation for this struct was generated from the following file:

• dune-raw-data/dune-raw-data/Overlays/FelixCompress.hh