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