00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
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
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)) {
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) {
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
00159
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
00172 result = addLeaf(subtree_root->Child0, path_len - 1, leaf);
00173 if(!result) return(false);
00174
00175
00176
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
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 }