1  #include <BinaryTree.h>
   2  namespace {
   3      const char splat('*');
   4      typedef std::string::const_iterator const_iterator;
   5  }
   6  
   7  BinaryTree::BinaryTree(const std::string binaryTreeDescription) : sentinel_(0) {
   8      InternalNode* currentNode = &sentinel_;        
   9      const const_iterator end = binaryTreeDescription.end();
  10      for(const_iterator it = binaryTreeDescription.begin(); it!=end; ++it) {
  11          const char currentChar = *it;
  12  
  13          if(currentChar==splat) {
  14              InternalNode* internalNode = new InternalNode(currentNode);
  15              currentNode->setVacant(internalNode);
  16              currentNode = internalNode;
  17              }
  18  
  19          else {
  20              LeafNode* leafNode = new LeafNode(currentNode, currentChar);
  21              currentNode->setVacant(leafNode);
  22              while(currentNode->isFull()) currentNode = currentNode->getParent();
  23              }
  24          }
  25  }
  26  
  27  
  28  // For debugging only:
  29  std::string BinaryTree::getDescription() const {
  30      std::string description;
  31      const Node* node = getRoot();
  32      while(node) {
  33          const InternalNode* internalNode = dynamic_cast<const InternalNode*>(node);
  34          if(internalNode) {
  35              description += splat;
  36              node = internalNode->getLeftBranch();
  37              }
  38          else {
  39              const LeafNode* leafNode = dynamic_cast<const LeafNode*>(node);
  40              description += leafNode->getSymbol();
  41              const InternalNode* parent = node->getParent();
  42              while(node==parent->getRightBranch()) {
  43                  node = parent;
  44                  parent = node->getParent();
  45                  }
  46              node = parent->getRightBranch();
  47              }
  48          }
  49      return description;
  50  }
  51  
  52  
  53  std::string BinaryTree::decode(const std::string binaryString) const {
  54      std::string result;
  55      const_iterator it = binaryString.begin();
  56      const const_iterator end = binaryString.end();
  57      while(it!=end) {
  58          const Node* node = getRoot();
  59          const InternalNode* internalNode = dynamic_cast<const InternalNode*>(node);
  60          while(internalNode!=0) {
  61              node = internalNode->getBranch('0'!=*it);
  62              ++it;
  63              internalNode = dynamic_cast<const InternalNode*>(node);
  64              }
  65          result += dynamic_cast<const LeafNode*>(node)->getSymbol();
  66          }
  67  
  68      return result;
  69  }