// Copyright (C) 2003 Davis E. King (davis@dlib.net) // License: Boost Software License See LICENSE.txt for the full license. #ifndef DLIB_CONDITIONING_CLASS_KERNEl_2_ #define DLIB_CONDITIONING_CLASS_KERNEl_2_ #include "conditioning_class_kernel_abstract.h" #include "../assert.h" #include "../algs.h" namespace dlib { template < unsigned long alphabet_size > class conditioning_class_kernel_2 { /*! INITIAL VALUE total == 1 symbols == pointer to array of alphabet_size data structs for all i except i == alphabet_size-1: symbols[i].count == 0 symbols[i].left_count == 0 symbols[alphabet_size-1].count == 1 symbols[alpahbet_size-1].left_count == 0 CONVENTION symbols == pointer to array of alphabet_size data structs get_total() == total get_count(symbol) == symbols[symbol].count symbols is organized as a tree with symbols[0] as the root. the left subchild of symbols[i] is symbols[i*2+1] and the right subchild is symbols[i*2+2]. the partent of symbols[i] == symbols[(i-1)/2] symbols[i].left_count == the sum of the counts of all the symbols to the left of symbols[i] get_memory_usage() == global_state.memory_usage !*/ public: class global_state_type { public: global_state_type () : memory_usage(0) {} private: unsigned long memory_usage; friend class conditioning_class_kernel_2<alphabet_size>; }; conditioning_class_kernel_2 ( global_state_type& global_state_ ); ~conditioning_class_kernel_2 ( ); void clear( ); bool increment_count ( unsigned long symbol, unsigned short amount = 1 ); unsigned long get_count ( unsigned long symbol ) const; inline unsigned long get_total ( ) const; unsigned long get_range ( unsigned long symbol, unsigned long& low_count, unsigned long& high_count, unsigned long& total_count ) const; void get_symbol ( unsigned long target, unsigned long& symbol, unsigned long& low_count, unsigned long& high_count ) const; unsigned long get_memory_usage ( ) const; global_state_type& get_global_state ( ); static unsigned long get_alphabet_size ( ); private: // restricted functions conditioning_class_kernel_2(conditioning_class_kernel_2<alphabet_size>&); // copy constructor conditioning_class_kernel_2& operator=(conditioning_class_kernel_2<alphabet_size>&); // assignment operator // data members unsigned short total; struct data { unsigned short count; unsigned short left_count; }; data* symbols; global_state_type& global_state; }; // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // member function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > conditioning_class_kernel_2<alphabet_size>:: conditioning_class_kernel_2 ( global_state_type& global_state_ ) : total(1), symbols(new data[alphabet_size]), global_state(global_state_) { COMPILE_TIME_ASSERT( 1 < alphabet_size && alphabet_size < 65536 ); data* start = symbols; data* end = symbols + alphabet_size-1; while (start != end) { start->count = 0; start->left_count = 0; ++start; } start->count = 1; start->left_count = 0; // update the left_counts for the symbol alphabet_size-1 unsigned short temp; unsigned long symbol = alphabet_size-1; while (symbol != 0) { // temp will be 1 if symbol is odd, 0 if it is even temp = static_cast<unsigned short>(symbol&0x1); // set symbol to its parent symbol = (symbol-1)>>1; // note that all left subchidren are odd and also that // if symbol was a left subchild then we want to increment // its parents left_count if (temp) ++symbols[symbol].left_count; } global_state.memory_usage += sizeof(data)*alphabet_size + sizeof(conditioning_class_kernel_2); } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > conditioning_class_kernel_2<alphabet_size>:: ~conditioning_class_kernel_2 ( ) { delete [] symbols; global_state.memory_usage -= sizeof(data)*alphabet_size + sizeof(conditioning_class_kernel_2); } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > void conditioning_class_kernel_2<alphabet_size>:: clear( ) { data* start = symbols; data* end = symbols + alphabet_size-1; total = 1; while (start != end) { start->count = 0; start->left_count = 0; ++start; } start->count = 1; start->left_count = 0; // update the left_counts unsigned short temp; unsigned long symbol = alphabet_size-1; while (symbol != 0) { // temp will be 1 if symbol is odd, 0 if it is even temp = static_cast<unsigned short>(symbol&0x1); // set symbol to its parent symbol = (symbol-1)>>1; // note that all left subchidren are odd and also that // if symbol was a left subchild then we want to increment // its parents left_count symbols[symbol].left_count += temp; } } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > unsigned long conditioning_class_kernel_2<alphabet_size>:: get_memory_usage( ) const { return global_state.memory_usage; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > typename conditioning_class_kernel_2<alphabet_size>::global_state_type& conditioning_class_kernel_2<alphabet_size>:: get_global_state( ) { return global_state; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > bool conditioning_class_kernel_2<alphabet_size>:: increment_count ( unsigned long symbol, unsigned short amount ) { // if we need to renormalize then do so if (static_cast<unsigned long>(total)+static_cast<unsigned long>(amount) >= 65536) { unsigned long s; unsigned short temp; for (unsigned short i = 0; i < alphabet_size-1; ++i) { s = i; // divide the count for this symbol by 2 symbols[i].count >>= 1; symbols[i].left_count = 0; // bubble this change up though the tree while (s != 0) { // temp will be 1 if symbol is odd, 0 if it is even temp = static_cast<unsigned short>(s&0x1); // set s to its parent s = (s-1)>>1; // note that all left subchidren are odd and also that // if s was a left subchild then we want to increment // its parents left_count if (temp) symbols[s].left_count += symbols[i].count; } } // update symbols alphabet_size-1 { s = alphabet_size-1; // divide alphabet_size-1 symbol by 2 if it's > 1 if (symbols[alphabet_size-1].count > 1) symbols[alphabet_size-1].count >>= 1; // bubble this change up though the tree while (s != 0) { // temp will be 1 if symbol is odd, 0 if it is even temp = static_cast<unsigned short>(s&0x1); // set s to its parent s = (s-1)>>1; // note that all left subchidren are odd and also that // if s was a left subchild then we want to increment // its parents left_count if (temp) symbols[s].left_count += symbols[alphabet_size-1].count; } } // calculate the new total total = 0; unsigned long m = 0; while (m < alphabet_size) { total += symbols[m].count + symbols[m].left_count; m = (m<<1) + 2; } } // increment the count for the specified symbol symbols[symbol].count += amount;; total += amount; unsigned short temp; while (symbol != 0) { // temp will be 1 if symbol is odd, 0 if it is even temp = static_cast<unsigned short>(symbol&0x1); // set symbol to its parent symbol = (symbol-1)>>1; // note that all left subchidren are odd and also that // if symbol was a left subchild then we want to increment // its parents left_count if (temp) symbols[symbol].left_count += amount; } return true; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > unsigned long conditioning_class_kernel_2<alphabet_size>:: get_count ( unsigned long symbol ) const { return symbols[symbol].count; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > unsigned long conditioning_class_kernel_2<alphabet_size>:: get_alphabet_size ( ) { return alphabet_size; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > unsigned long conditioning_class_kernel_2<alphabet_size>:: get_total ( ) const { return total; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > unsigned long conditioning_class_kernel_2<alphabet_size>:: get_range ( unsigned long symbol, unsigned long& low_count, unsigned long& high_count, unsigned long& total_count ) const { if (symbols[symbol].count == 0) return 0; unsigned long current = symbol; total_count = total; unsigned long high_count_temp = 0; bool came_from_right = true; while (true) { if (came_from_right) { high_count_temp += symbols[current].count + symbols[current].left_count; } // note that if current is even then it is a right child came_from_right = !(current&0x1); if (current == 0) break; // set current to its parent current = (current-1)>>1 ; } low_count = high_count_temp - symbols[symbol].count; high_count = high_count_temp; return symbols[symbol].count; } // ---------------------------------------------------------------------------------------- template < unsigned long alphabet_size > void conditioning_class_kernel_2<alphabet_size>:: get_symbol ( unsigned long target, unsigned long& symbol, unsigned long& low_count, unsigned long& high_count ) const { unsigned long current = 0; unsigned long low_count_temp = 0; while (true) { if (static_cast<unsigned short>(target) < symbols[current].left_count) { // we should go left current = (current<<1) + 1; } else { target -= symbols[current].left_count; low_count_temp += symbols[current].left_count; if (static_cast<unsigned short>(target) < symbols[current].count) { // we have found our target symbol = current; high_count = low_count_temp + symbols[current].count; low_count = low_count_temp; break; } else { // go right target -= symbols[current].count; low_count_temp += symbols[current].count; current = (current<<1) + 2; } } } } // ---------------------------------------------------------------------------------------- } #endif // DLIB_CONDITIONING_CLASS_KERNEl_1_