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

mxcpcHuffmanTree.cpp

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

Generated on Mon Jan 30 15:52:43 2006 for mxcpc by  doxygen 1.4.4