1 // Copyright (C) 2004 Davis E. King (davis@dlib.net) 2 // License: Boost Software License See LICENSE.txt for the full license. 3 #ifndef DLIB_CONDITIONING_CLASS_KERNEl_3_ 4 #define DLIB_CONDITIONING_CLASS_KERNEl_3_ 5 6 #include "conditioning_class_kernel_abstract.h" 7 #include "../assert.h" 8 #include "../algs.h" 9 10 11 namespace dlib 12 { 13 14 template < 15 unsigned long alphabet_size 16 > 17 class conditioning_class_kernel_3 18 { 19 /*! 20 INITIAL VALUE 21 total == 1 22 counts == pointer to an array of alphabet_size data structs 23 for all i except i == 0: counts[i].count == 0 24 counts[0].count == 1 25 counts[0].symbol == alphabet_size-1 26 for all i except i == alphabet_size-1: counts[i].present == false 27 counts[alphabet_size-1].present == true 28 29 CONVENTION 30 counts == pointer to an array of alphabet_size data structs 31 get_total() == total 32 get_count(symbol) == counts[x].count where 33 counts[x].symbol == symbol 34 35 36 LOW_COUNT(symbol) == sum of counts[0].count though counts[x-1].count 37 where counts[x].symbol == symbol 38 if (counts[0].symbol == symbol) LOW_COUNT(symbol)==0 39 40 41 if (counts[i].count == 0) then 42 counts[i].symbol == undefined value 43 44 if (symbol has a nonzero count) then 45 counts[symbol].present == true 46 47 get_memory_usage() == global_state.memory_usage 48 !*/ 49 50 public: 51 52 class global_state_type 53 { 54 public: global_state_type()55 global_state_type () : memory_usage(0) {} 56 private: 57 unsigned long memory_usage; 58 59 friend class conditioning_class_kernel_3<alphabet_size>; 60 }; 61 62 conditioning_class_kernel_3 ( 63 global_state_type& global_state_ 64 ); 65 66 ~conditioning_class_kernel_3 ( 67 ); 68 69 void clear( 70 ); 71 72 bool increment_count ( 73 unsigned long symbol, 74 unsigned short amount = 1 75 ); 76 77 unsigned long get_count ( 78 unsigned long symbol 79 ) const; 80 81 unsigned long get_total ( 82 ) const; 83 84 unsigned long get_range ( 85 unsigned long symbol, 86 unsigned long& low_count, 87 unsigned long& high_count, 88 unsigned long& total_count 89 ) const; 90 91 void get_symbol ( 92 unsigned long target, 93 unsigned long& symbol, 94 unsigned long& low_count, 95 unsigned long& high_count 96 ) const; 97 98 unsigned long get_memory_usage ( 99 ) const; 100 101 global_state_type& get_global_state ( 102 ); 103 104 static unsigned long get_alphabet_size ( 105 ); 106 107 private: 108 109 // restricted functions 110 conditioning_class_kernel_3(conditioning_class_kernel_3<alphabet_size>&); // copy constructor 111 conditioning_class_kernel_3& operator=(conditioning_class_kernel_3<alphabet_size>&); // assignment operator 112 113 struct data 114 { 115 unsigned short count; 116 unsigned short symbol; 117 bool present; 118 }; 119 120 // data members 121 unsigned short total; 122 data* counts; 123 global_state_type& global_state; 124 125 }; 126 127 // ---------------------------------------------------------------------------------------- 128 // ---------------------------------------------------------------------------------------- 129 // member function definitions 130 // ---------------------------------------------------------------------------------------- 131 // ---------------------------------------------------------------------------------------- 132 133 template < 134 unsigned long alphabet_size 135 > 136 conditioning_class_kernel_3<alphabet_size>:: conditioning_class_kernel_3(global_state_type & global_state_)137 conditioning_class_kernel_3 ( 138 global_state_type& global_state_ 139 ) : 140 total(1), 141 counts(new data[alphabet_size]), 142 global_state(global_state_) 143 { 144 COMPILE_TIME_ASSERT( 1 < alphabet_size && alphabet_size < 65536 ); 145 146 data* start = counts; 147 data* end = counts+alphabet_size; 148 start->count = 1; 149 start->symbol = alphabet_size-1; 150 start->present = false; 151 ++start; 152 while (start != end) 153 { 154 start->count = 0; 155 start->present = false; 156 ++start; 157 } 158 counts[alphabet_size-1].present = true; 159 160 // update memory usage 161 global_state.memory_usage += sizeof(data)*alphabet_size + 162 sizeof(conditioning_class_kernel_3); 163 164 } 165 166 // ---------------------------------------------------------------------------------------- 167 168 template < 169 unsigned long alphabet_size 170 > 171 conditioning_class_kernel_3<alphabet_size>:: ~conditioning_class_kernel_3()172 ~conditioning_class_kernel_3 ( 173 ) 174 { 175 delete [] counts; 176 // update memory usage 177 global_state.memory_usage -= sizeof(data)*alphabet_size + 178 sizeof(conditioning_class_kernel_3); 179 } 180 181 // ---------------------------------------------------------------------------------------- 182 183 template < 184 unsigned long alphabet_size 185 > 186 void conditioning_class_kernel_3<alphabet_size>:: clear()187 clear( 188 ) 189 { 190 total = 1; 191 data* start = counts; 192 data* end = counts+alphabet_size; 193 start->count = 1; 194 start->symbol = alphabet_size-1; 195 start->present = false; 196 ++start; 197 while (start != end) 198 { 199 start->count = 0; 200 start->present = false; 201 ++start; 202 } 203 counts[alphabet_size-1].present = true; 204 205 } 206 207 // ---------------------------------------------------------------------------------------- 208 209 template < 210 unsigned long alphabet_size 211 > 212 typename conditioning_class_kernel_3<alphabet_size>::global_state_type& conditioning_class_kernel_3<alphabet_size>:: get_global_state()213 get_global_state( 214 ) 215 { 216 return global_state; 217 } 218 219 // ---------------------------------------------------------------------------------------- 220 221 template < 222 unsigned long alphabet_size 223 > 224 unsigned long conditioning_class_kernel_3<alphabet_size>:: get_memory_usage()225 get_memory_usage( 226 ) const 227 { 228 return global_state.memory_usage; 229 } 230 231 // ---------------------------------------------------------------------------------------- 232 233 template < 234 unsigned long alphabet_size 235 > 236 bool conditioning_class_kernel_3<alphabet_size>:: increment_count(unsigned long symbol,unsigned short amount)237 increment_count ( 238 unsigned long symbol, 239 unsigned short amount 240 ) 241 { 242 // if we are going over a total of 65535 then scale down all counts by 2 243 if (static_cast<unsigned long>(total)+static_cast<unsigned long>(amount) >= 65536) 244 { 245 total = 0; 246 data* start = counts; 247 data* end = counts+alphabet_size; 248 249 while (start != end) 250 { 251 if (start->count == 1) 252 { 253 if (start->symbol == alphabet_size-1) 254 { 255 // this symbol must never be zero so we will leave its count at 1 256 ++total; 257 } 258 else 259 { 260 start->count = 0; 261 counts[start->symbol].present = false; 262 } 263 } 264 else 265 { 266 start->count >>= 1; 267 total += start->count; 268 } 269 270 ++start; 271 } 272 } 273 274 275 data* start = counts; 276 data* swap_spot = counts; 277 278 if (counts[symbol].present) 279 { 280 while (true) 281 { 282 if (start->symbol == symbol && start->count!=0) 283 { 284 unsigned short temp = start->count + amount; 285 286 start->symbol = swap_spot->symbol; 287 start->count = swap_spot->count; 288 289 swap_spot->symbol = static_cast<unsigned short>(symbol); 290 swap_spot->count = temp; 291 break; 292 } 293 294 if ( (start->count) < (swap_spot->count)) 295 { 296 swap_spot = start; 297 } 298 299 300 ++start; 301 } 302 } 303 else 304 { 305 counts[symbol].present = true; 306 while (true) 307 { 308 if (start->count == 0) 309 { 310 start->symbol = swap_spot->symbol; 311 start->count = swap_spot->count; 312 313 swap_spot->symbol = static_cast<unsigned short>(symbol); 314 swap_spot->count = amount; 315 break; 316 } 317 318 if ((start->count) < (swap_spot->count)) 319 { 320 swap_spot = start; 321 } 322 323 ++start; 324 } 325 } 326 327 total += amount; 328 329 return true; 330 } 331 332 // ---------------------------------------------------------------------------------------- 333 334 template < 335 unsigned long alphabet_size 336 > 337 unsigned long conditioning_class_kernel_3<alphabet_size>:: get_count(unsigned long symbol)338 get_count ( 339 unsigned long symbol 340 ) const 341 { 342 if (counts[symbol].present == false) 343 return 0; 344 345 data* start = counts; 346 while (start->symbol != symbol) 347 { 348 ++start; 349 } 350 return start->count; 351 } 352 353 // ---------------------------------------------------------------------------------------- 354 355 template < 356 unsigned long alphabet_size 357 > 358 unsigned long conditioning_class_kernel_3<alphabet_size>:: get_alphabet_size()359 get_alphabet_size ( 360 ) 361 { 362 return alphabet_size; 363 } 364 365 // ---------------------------------------------------------------------------------------- 366 367 template < 368 unsigned long alphabet_size 369 > 370 unsigned long conditioning_class_kernel_3<alphabet_size>:: get_total()371 get_total ( 372 ) const 373 { 374 return total; 375 } 376 377 // ---------------------------------------------------------------------------------------- 378 379 template < 380 unsigned long alphabet_size 381 > 382 unsigned long conditioning_class_kernel_3<alphabet_size>:: get_range(unsigned long symbol,unsigned long & low_count,unsigned long & high_count,unsigned long & total_count)383 get_range ( 384 unsigned long symbol, 385 unsigned long& low_count, 386 unsigned long& high_count, 387 unsigned long& total_count 388 ) const 389 { 390 if (counts[symbol].present == false) 391 return 0; 392 393 total_count = total; 394 unsigned long low_count_temp = 0; 395 data* start = counts; 396 while (start->symbol != symbol) 397 { 398 low_count_temp += start->count; 399 ++start; 400 } 401 402 low_count = low_count_temp; 403 high_count = low_count_temp + start->count; 404 return start->count; 405 } 406 407 // ---------------------------------------------------------------------------------------- 408 409 template < 410 unsigned long alphabet_size 411 > 412 void conditioning_class_kernel_3<alphabet_size>:: get_symbol(unsigned long target,unsigned long & symbol,unsigned long & low_count,unsigned long & high_count)413 get_symbol ( 414 unsigned long target, 415 unsigned long& symbol, 416 unsigned long& low_count, 417 unsigned long& high_count 418 ) const 419 { 420 unsigned long high_count_temp = counts->count; 421 const data* start = counts; 422 while (target >= high_count_temp) 423 { 424 ++start; 425 high_count_temp += start->count; 426 } 427 428 low_count = high_count_temp - start->count; 429 high_count = high_count_temp; 430 symbol = static_cast<unsigned long>(start->symbol); 431 } 432 433 // ---------------------------------------------------------------------------------------- 434 435 } 436 437 #endif // DLIB_CONDITIONING_CLASS_KERNEl_3_ 438 439