Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members

mxcpcHuffmanTree.cpp

00001 //           ///          //
00002 //          /////        ////
00003 //         /// XXX     XXX ///
00004 //        ///    XXX XXX    ///     $RCSfile: mxcpcHuffmanTree.cpp,v $  
00005 //       ///       XXX       ///     $Revision: 1.3 $
00006 //      ///      XXX XXX      ///     $Date: 2005/08/09 13:57:26 $
00007 //     ////    XXX     XXX    ////     $Author: cvs-steve $
00008 //    ////                     ////
00009 //   ////  M  O  B  O  T  I  X  ////////////////////////////////////////////////
00010 //  //// Security Vision Systems ///////////////////////////////////////////////
00011 
00012 // Copyright (c) 2005, MOBOTIX AG.
00013 // This software is made available under the BSD licence. Please refer 
00014 // to the file LICENCE.TXT contained in this distribution for details.
00015 
00016 
00017 #include <mxcpcHuffmanTree.h>
00018 #include <mxcpc_exceptions.h>
00019 
00020 
00021 
00022 mxcpcHuffmanTree::mxcpcHuffmanTree() {
00023 
00024   RootNode   = 0;
00025   GroundNode = 0;
00026 
00027   try { 
00028     RootNode = new Node;   
00029     GroundNode = new Node;
00030   } catch(std::bad_alloc) {
00031       delete RootNode;
00032       delete GroundNode;
00033       throw;
00034     }
00035   
00036   RootNode->Child0 = 0;
00037   RootNode->Child1 = 0;
00038   RootNode->IsLeaf = false;
00039   
00040   GroundNode->Child0 = GroundNode;
00041   GroundNode->Child1 = GroundNode;
00042   GroundNode->IsLeaf = false;
00043 }
00044 
00045 
00046 mxcpcHuffmanTree::~mxcpcHuffmanTree() {
00047 
00048   clear();
00049   
00050   delete RootNode;
00051   delete GroundNode;
00052 }
00053 
00054 
00055 
00056 const mxcpcHuffmanTree::Node *mxcpcHuffmanTree::getRoot(void) {
00057 
00058   return(RootNode);
00059 }
00060 
00061 
00062 void mxcpcHuffmanTree::clear(void) {
00063 
00064   if(RootNode->Child0) {
00065     deleteSubTree(RootNode->Child0);
00066     RootNode->Child0 = 0;
00067   }
00068   if(RootNode->Child1) {
00069     deleteSubTree(RootNode->Child1);
00070     RootNode->Child1 = 0;
00071   }
00072 }
00073 
00074 
00075 bool mxcpcHuffmanTree::configureFromTable(const unsigned char *table, 
00076                                           int max_path_len) {
00077   
00078   const unsigned char *val_ptr;
00079   int symbol_num;
00080   int i, j;
00081   
00082   //fprintf(stderr, "\n\nmxcpcHuffmanTree::configureFromTable: max_path_len: %d\n\n", max_path_len);
00083   
00084   clear();
00085   
00086   val_ptr = table + 16;
00087   for(i = 1; i < max_path_len; i++) {
00088     symbol_num = table[i];
00089     for(j = 0; j < symbol_num; j++) {
00090       if(addLeaf(i + 1, *val_ptr)) {   // failure!
00091         clear();
00092         fprintf(stderr, "\n\nmxcpcHuffmanTree::configureFromTable: WHY CLEAR!\n\n");
00093         return(true);
00094       }
00095       else
00096         val_ptr++;
00097     }
00098   }
00099   
00100   groundUnusedPaths(RootNode);
00101   return(false);
00102 }
00103 
00104 
00105 int mxcpcHuffmanTree::countLeaves(void) {
00106 
00107   return(countLeaves(RootNode));
00108 }
00109 
00110 
00111 bool mxcpcHuffmanTree::addLeaf(int path_len, unsigned char value) {
00112 
00113   Node *leaf;
00114   bool result;
00115   
00116   try {
00117     leaf = new Node;
00118   } catch(std::bad_alloc) {
00119       return(true);
00120     }
00121   
00122   leaf->Child0 = 0;
00123   leaf->Child1 = 0;
00124   leaf->IsLeaf = true;
00125   leaf->Value  = value;
00126   
00127   result = addLeaf(RootNode, path_len, leaf);
00128   
00129   if(result) delete leaf;
00130  
00131   return(result); 
00132 }
00133 
00134 
00135 bool mxcpcHuffmanTree::addLeaf(Node *subtree_root, int path_len, Node *leaf) {
00136 
00137   bool result;
00138   Node *new_node;
00139   
00140   if(subtree_root->IsLeaf) return(true);
00141   
00142   if(path_len == 1) {   // try to add leaf...
00143   
00144     if(!subtree_root->Child0) {
00145       subtree_root->Child0 = leaf;
00146       return(false);
00147     }
00148     else if(!subtree_root->Child1) { 
00149       subtree_root->Child1 = leaf;
00150       return(false);
00151     }
00152     else
00153       return(true);
00154   }
00155   
00156   else {
00157        
00158     // --- try 0-direction... --- 
00159     // ensure we have inner 0-child node...
00160     if(!subtree_root->Child0) {
00161       try {
00162         new_node = new Node;  
00163       } catch(std::bad_alloc) {
00164           return(true);
00165         }
00166       new_node->Child0 = 0;
00167       new_node->Child1 = 0;
00168       new_node->IsLeaf = false;
00169       subtree_root->Child0 = new_node;
00170     }
00171     // try 0-child subtree...
00172     result = addLeaf(subtree_root->Child0, path_len - 1, leaf);
00173     if(!result) return(false);
00174          
00175     // --- try 1-direction... --- 
00176     // ensure we have inner 1-child node...
00177     if(!subtree_root->Child1) {
00178       try {
00179         new_node = new Node;  
00180       } catch(std::bad_alloc) {
00181           return(true);
00182         }
00183       new_node->Child0 = 0;
00184       new_node->Child1 = 0;
00185       new_node->IsLeaf = false;
00186       subtree_root->Child1 = new_node;
00187     }
00188     // try 1-child subtree...
00189     result = addLeaf(subtree_root->Child1, path_len - 1, leaf);
00190     if(!result) return(false);
00191      
00192     return(true);
00193   }
00194 }
00195 
00196 
00202 void mxcpcHuffmanTree::deleteSubTree(Node *subtree_root) {
00203 
00204   if(subtree_root == GroundNode) return;
00205 
00206   if(subtree_root->Child0) deleteSubTree(subtree_root->Child0);
00207   if(subtree_root->Child1) deleteSubTree(subtree_root->Child1);
00208   
00209   delete subtree_root;
00210 }
00211 
00212 
00213 void mxcpcHuffmanTree::groundUnusedPaths(Node *subtree) {
00214 
00215   if(subtree->Child0) 
00216     groundUnusedPaths(subtree->Child0);
00217   else
00218     subtree->Child0 = GroundNode;
00219     
00220   if(subtree->Child1)
00221     groundUnusedPaths(subtree->Child1);
00222   else
00223     subtree->Child1 = GroundNode;
00224 }
00225 
00226 
00227 int mxcpcHuffmanTree::countLeaves(Node *subtree) {
00228 
00229   int num;
00230   
00231   if(subtree == GroundNode) return(0);
00232   
00233   if(subtree->IsLeaf) 
00234     return(1);
00235   else {
00236     num = 0;
00237     if(subtree->Child0) num += countLeaves(subtree->Child0);
00238     if(subtree->Child1) num += countLeaves(subtree->Child1);
00239     return(num);
00240   } 
00241 }

Generated on Mon Aug 15 03:39:30 2005 for mxcpc by  doxygen 1.4.2-20050421