1 // Copyright (C) 2003 Davis E. King (davis@dlib.net) 2 // License: Boost Software License See LICENSE.txt for the full license. 3 #ifndef DLIB_CONDITIONING_CLASS_KERNEl_1_ 4 #define DLIB_CONDITIONING_CLASS_KERNEl_1_ 5 6 #include "conditioning_class_kernel_abstract.h" 7 #include "../assert.h" 8 #include "../algs.h" 9 10 namespace dlib 11 { 12 13 template < 14 unsigned long alphabet_size 15 > 16 class conditioning_class_kernel_1 17 { 18 /*! 19 INITIAL VALUE 20 total == 1 21 counts == pointer to an array of alphabet_size unsigned shorts 22 for all i except i == alphabet_size-1: counts[i] == 0 23 counts[alphabet_size-1] == 1 24 25 CONVENTION 26 counts == pointer to an array of alphabet_size unsigned shorts 27 get_total() == total 28 get_count(symbol) == counts[symbol] 29 30 LOW_COUNT(symbol) == sum of counts[0] though counts[symbol-1] 31 or 0 if symbol == 0 32 33 get_memory_usage() == global_state.memory_usage 34 !*/ 35 36 public: 37 38 class global_state_type 39 { 40 public: global_state_type()41 global_state_type () : memory_usage(0) {} 42 private: 43 unsigned long memory_usage; 44 45 friend class conditioning_class_kernel_1<alphabet_size>; 46 }; 47 48 conditioning_class_kernel_1 ( 49 global_state_type& global_state_ 50 ); 51 52 ~conditioning_class_kernel_1 ( 53 ); 54 55 void clear( 56 ); 57 58 bool increment_count ( 59 unsigned long symbol, 60 unsigned short amount = 1 61 ); 62 63 unsigned long get_count ( 64 unsigned long symbol 65 ) const; 66 67 unsigned long get_total ( 68 ) const; 69 70 unsigned long get_range ( 71 unsigned long symbol, 72 unsigned long& low_count, 73 unsigned long& high_count, 74 unsigned long& total_count 75 ) const; 76 77 void get_symbol ( 78 unsigned long target, 79 unsigned long& symbol, 80 unsigned long& low_count, 81 unsigned long& high_count 82 ) const; 83 84 unsigned long get_memory_usage ( 85 ) const; 86 87 global_state_type& get_global_state ( 88 ); 89 90 static unsigned long get_alphabet_size ( 91 ); 92 93 94 private: 95 96 // restricted functions 97 conditioning_class_kernel_1(conditioning_class_kernel_1<alphabet_size>&); // copy constructor 98 conditioning_class_kernel_1& operator=(conditioning_class_kernel_1<alphabet_size>&); // assignment operator 99 100 // data members 101 unsigned short total; 102 unsigned short* counts; 103 global_state_type& global_state; 104 105 }; 106 107 // ---------------------------------------------------------------------------------------- 108 // ---------------------------------------------------------------------------------------- 109 // member function definitions 110 // ---------------------------------------------------------------------------------------- 111 // ---------------------------------------------------------------------------------------- 112 113 template < 114 unsigned long alphabet_size 115 > 116 conditioning_class_kernel_1<alphabet_size>:: conditioning_class_kernel_1(global_state_type & global_state_)117 conditioning_class_kernel_1 ( 118 global_state_type& global_state_ 119 ) : 120 total(1), 121 counts(new unsigned short[alphabet_size]), 122 global_state(global_state_) 123 { 124 COMPILE_TIME_ASSERT( 1 < alphabet_size && alphabet_size < 65536 ); 125 126 unsigned short* start = counts; 127 unsigned short* end = counts+alphabet_size-1; 128 while (start != end) 129 { 130 *start = 0; 131 ++start; 132 } 133 *start = 1; 134 135 // update memory usage 136 global_state.memory_usage += sizeof(unsigned short)*alphabet_size + 137 sizeof(conditioning_class_kernel_1); 138 } 139 140 // ---------------------------------------------------------------------------------------- 141 142 template < 143 unsigned long alphabet_size 144 > 145 conditioning_class_kernel_1<alphabet_size>:: ~conditioning_class_kernel_1()146 ~conditioning_class_kernel_1 ( 147 ) 148 { 149 delete [] counts; 150 // update memory usage 151 global_state.memory_usage -= sizeof(unsigned short)*alphabet_size + 152 sizeof(conditioning_class_kernel_1); 153 } 154 155 // ---------------------------------------------------------------------------------------- 156 157 template < 158 unsigned long alphabet_size 159 > 160 void conditioning_class_kernel_1<alphabet_size>:: clear()161 clear( 162 ) 163 { 164 total = 1; 165 unsigned short* start = counts; 166 unsigned short* end = counts+alphabet_size-1; 167 while (start != end) 168 { 169 *start = 0; 170 ++start; 171 } 172 *start = 1; 173 } 174 175 // ---------------------------------------------------------------------------------------- 176 177 template < 178 unsigned long alphabet_size 179 > 180 unsigned long conditioning_class_kernel_1<alphabet_size>:: get_memory_usage()181 get_memory_usage( 182 ) const 183 { 184 return global_state.memory_usage; 185 } 186 187 // ---------------------------------------------------------------------------------------- 188 189 template < 190 unsigned long alphabet_size 191 > 192 typename conditioning_class_kernel_1<alphabet_size>::global_state_type& conditioning_class_kernel_1<alphabet_size>:: get_global_state()193 get_global_state( 194 ) 195 { 196 return global_state; 197 } 198 199 // ---------------------------------------------------------------------------------------- 200 201 template < 202 unsigned long alphabet_size 203 > 204 bool conditioning_class_kernel_1<alphabet_size>:: increment_count(unsigned long symbol,unsigned short amount)205 increment_count ( 206 unsigned long symbol, 207 unsigned short amount 208 ) 209 { 210 // if we are going over a total of 65535 then scale down all counts by 2 211 if (static_cast<unsigned long>(total)+static_cast<unsigned long>(amount) >= 65536) 212 { 213 total = 0; 214 unsigned short* start = counts; 215 unsigned short* end = counts+alphabet_size; 216 while (start != end) 217 { 218 *start >>= 1; 219 total += *start; 220 ++start; 221 } 222 // make sure it is at least one 223 if (counts[alphabet_size-1]==0) 224 { 225 ++total; 226 counts[alphabet_size-1] = 1; 227 } 228 } 229 counts[symbol] += amount; 230 total += amount; 231 return true; 232 } 233 234 // ---------------------------------------------------------------------------------------- 235 236 template < 237 unsigned long alphabet_size 238 > 239 unsigned long conditioning_class_kernel_1<alphabet_size>:: get_count(unsigned long symbol)240 get_count ( 241 unsigned long symbol 242 ) const 243 { 244 return counts[symbol]; 245 } 246 247 // ---------------------------------------------------------------------------------------- 248 249 template < 250 unsigned long alphabet_size 251 > 252 unsigned long conditioning_class_kernel_1<alphabet_size>:: get_alphabet_size()253 get_alphabet_size ( 254 ) 255 { 256 return alphabet_size; 257 } 258 259 // ---------------------------------------------------------------------------------------- 260 261 template < 262 unsigned long alphabet_size 263 > 264 unsigned long conditioning_class_kernel_1<alphabet_size>:: get_total()265 get_total ( 266 ) const 267 { 268 return total; 269 } 270 271 // ---------------------------------------------------------------------------------------- 272 273 template < 274 unsigned long alphabet_size 275 > 276 unsigned long conditioning_class_kernel_1<alphabet_size>:: get_range(unsigned long symbol,unsigned long & low_count,unsigned long & high_count,unsigned long & total_count)277 get_range ( 278 unsigned long symbol, 279 unsigned long& low_count, 280 unsigned long& high_count, 281 unsigned long& total_count 282 ) const 283 { 284 if (counts[symbol] == 0) 285 return 0; 286 287 total_count = total; 288 289 const unsigned short* start = counts; 290 const unsigned short* end = counts+symbol; 291 unsigned short high_count_temp = *start; 292 while (start != end) 293 { 294 ++start; 295 high_count_temp += *start; 296 } 297 low_count = high_count_temp - *start; 298 high_count = high_count_temp; 299 return *start; 300 } 301 302 // ---------------------------------------------------------------------------------------- 303 304 template < 305 unsigned long alphabet_size 306 > 307 void conditioning_class_kernel_1<alphabet_size>:: get_symbol(unsigned long target,unsigned long & symbol,unsigned long & low_count,unsigned long & high_count)308 get_symbol ( 309 unsigned long target, 310 unsigned long& symbol, 311 unsigned long& low_count, 312 unsigned long& high_count 313 ) const 314 { 315 unsigned long high_count_temp = *counts; 316 const unsigned short* start = counts; 317 while (target >= high_count_temp) 318 { 319 ++start; 320 high_count_temp += *start; 321 } 322 323 low_count = high_count_temp - *start; 324 high_count = high_count_temp; 325 symbol = static_cast<unsigned long>(start-counts); 326 } 327 328 // ---------------------------------------------------------------------------------------- 329 330 } 331 332 #endif // DLIB_CONDITIONING_CLASS_KERNEl_1_ 333 334