text: // Copyright (C) 2004  Davis E. King (davis@dlib.net)
  // License: Boost Software License   See LICENSE.txt for the full license.
  #ifndef DLIB_CONDITIONING_CLASS_KERNEl_4_
  #define DLIB_CONDITIONING_CLASS_KERNEl_4_
  
  #include "conditioning_class_kernel_abstract.h"
  #include "../assert.h"
  #include "../algs.h"
  
  namespace dlib
  {
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      class conditioning_class_kernel_4 
      {
          /*!
              REQUIREMENTS ON pool_size
                  pool_size > 0
                  this will be the number of nodes contained in our memory pool
  
              REQUIREMENTS ON mem_manager
                  mem_manager is an implementation of memory_manager/memory_manager_kernel_abstract.h
  
              INITIAL VALUE
                  total == 1
                  escapes == 1
                  next == 0
                  
              CONVENTION                
                  get_total() == total
                  get_count(alphabet_size-1) == escapes
  
                  if (next != 0) then
                      next == pointer to the start of a linked list and the linked list
                              is terminated by a node with a next pointer of 0.
  
                  get_count(symbol) == node::count for the node where node::symbol==symbol 
                                       or 0 if no such node currently exists.
  
                  if (there is a node for the symbol) then
                      LOW_COUNT(symbol) == the sum of all node's counts in the linked list
                      up to but not including the node for the symbol.
  
                  get_memory_usage() == global_state.memory_usage
          !*/
  
  
          struct node
          {
              unsigned short symbol;
              unsigned short count;
              node* next;
          };
  
      public:
  
          class global_state_type
          {
          public:
              global_state_type (
              ) : 
                  memory_usage(pool_size*sizeof(node)+sizeof(global_state_type))
                  {}
          private:
              unsigned long memory_usage;
  
              typename mem_manager::template rebind<node>::other pool;
  
              friend class conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>;
          };
  
          conditioning_class_kernel_4 (
              global_state_type& global_state_
          );
  
          ~conditioning_class_kernel_4 (
          );
  
          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:
  
          void half_counts (
          );
          /*!
              ensures
                  - divides all counts by 2 but ensures that escapes is always at least 1
          !*/
  
          // restricted functions
          conditioning_class_kernel_4(conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>&);        // copy constructor
          conditioning_class_kernel_4& operator=(conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>&);    // assignment operator
  
          // data members
          unsigned short total;
          unsigned short escapes;
          node* next;
          global_state_type& global_state;
  
      };   
  
  // ----------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------
      // member function definitions
  // ----------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      conditioning_class_kernel_4 (
          global_state_type& global_state_
      ) :
          total(1),
          escapes(1),
          next(0),
          global_state(global_state_)
      {
          COMPILE_TIME_ASSERT( 1 < alphabet_size && alphabet_size < 65536 );
  
          // update memory usage
          global_state.memory_usage += sizeof(conditioning_class_kernel_4);
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      ~conditioning_class_kernel_4 (
      )
      {
          clear();
          // update memory usage
          global_state.memory_usage -= sizeof(conditioning_class_kernel_4);
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      void conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      clear(
      )
      {
          total = 1;
          escapes = 1;
          while (next)
          {
              node* temp = next;
              next = next->next;
              global_state.pool.deallocate(temp);
          }
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      unsigned long conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_memory_usage(
      ) const
      {
          return global_state.memory_usage;
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      typename conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::global_state_type& conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_global_state(
      )
      {
          return global_state;
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      bool conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      increment_count (
          unsigned long symbol,
          unsigned short amount
      )
      {        
          if (symbol == alphabet_size-1)
          {
              // make sure we won't cause any overflow
              if (total >= 65536 - amount )                        
                  half_counts();
  
              escapes += amount;
              total += amount;
              return true;
          }
  
          
          // find the symbol and increment it or add a new node to the list
          if (next)
          {
              node* temp = next;
              node* previous = 0;
              while (true)
              {
                  if (temp->symbol == static_cast<unsigned short>(symbol))
                  {
                      // make sure we won't cause any overflow
                      if (total >= 65536 - amount )                        
                          half_counts();
                      
                      // we have found the symbol
                      total += amount;
                      temp->count += amount;
  
                      // if this node now has a count greater than its parent node
                      if (previous && temp->count > previous->count)
                      {
                          // swap the nodes so that the nodes will be in semi-sorted order
                          swap(temp->count,previous->count);
                          swap(temp->symbol,previous->symbol);
                      }
                      return true;
                  }
                  else if (temp->next == 0)
                  {
                      // we did not find the symbol so try to add it to the list
                      if (global_state.pool.get_number_of_allocations() < pool_size)
                      {
                          // make sure we won't cause any overflow
                          if (total >= 65536 - amount )                        
                              half_counts();
  
                          node* t = global_state.pool.allocate();
                          t->next = 0;
                          t->symbol = static_cast<unsigned short>(symbol);
                          t->count = amount;
                          temp->next = t;
                          total += amount;
                          return true;
                      }
                      else
                      {
                          // no memory left
                          return false;
                      }
                  }
                  else if (temp->count == 0)
                  {
                      // remove nodes that have a zero count
                      if (previous)
                      {
                          previous->next = temp->next;
                          node* t = temp;
                          temp = temp->next;
                          global_state.pool.deallocate(t);
                      }
                      else
                      {
                          next = temp->next;
                          node* t = temp;
                          temp = temp->next;
                          global_state.pool.deallocate(t);
                      }
                  }
                  else
                  {
                      previous = temp;
                      temp = temp->next;
                  }
              } // while (true)
          }
          // if there aren't any nodes in the list yet then do this instead
          else
          {
              if (global_state.pool.get_number_of_allocations() < pool_size)
              {
                  // make sure we won't cause any overflow
                  if (total >= 65536 - amount )                        
                      half_counts();
  
                  next = global_state.pool.allocate();
                  next->next = 0;
                  next->symbol = static_cast<unsigned short>(symbol);
                  next->count = amount;
                  total += amount;
                  return true;
              }
              else
              {
                  // no memory left
                  return false;
              }
          }
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      unsigned long conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_count (
          unsigned long symbol
      ) const
      {
          if (symbol == alphabet_size-1)
          { 
              return escapes;
          }
          else
          {
              node* temp = next;
              while (temp)
              {
                  if (temp->symbol == symbol)
                      return temp->count;
                  temp = temp->next;
              }
              return 0;
          }        
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      unsigned long conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_alphabet_size (        
      ) 
      {
          return alphabet_size;
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      unsigned long conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_total (
      ) const
      {
          return total;
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      unsigned long conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_range (
          unsigned long symbol,
          unsigned long& low_count,
          unsigned long& high_count,
          unsigned long& total_count
      ) const
      {   
          if (symbol != alphabet_size-1)
          {
              node* temp = next;
              unsigned long low = 0;
              while (temp)
              {
                  if (temp->symbol == static_cast<unsigned short>(symbol))
                  {
                      high_count = temp->count + low;
                      low_count = low;                
                      total_count = total;
                      return temp->count;
                  }
                  low += temp->count;
                  temp = temp->next;
              }
              return 0;
          }
          else
          {
              total_count = total;
              high_count = total;
              low_count = total-escapes;
              return escapes;
          }
      }
  
  // ----------------------------------------------------------------------------------------
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      void conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      get_symbol (
          unsigned long target,
          unsigned long& symbol,            
          unsigned long& low_count,
          unsigned long& high_count
      ) const
      {
          node* temp = next;
          unsigned long high = 0;
          while (true)
          {
              if (temp != 0)
              {
                  high += temp->count;
                  if (target < high)
                  {
                      symbol = temp->symbol;
                      high_count = high;
                      low_count = high - temp->count;
                      return;
                  }
                  temp = temp->next;
              }
              else
              {
                  // this must be the escape symbol
                  symbol = alphabet_size-1;
                  low_count = total-escapes;
                  high_count = total;
                  return;
              }            
          }
      }
  
  // ----------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------
      // private member function definitions
  // ----------------------------------------------------------------------------------------
  // ----------------------------------------------------------------------------------------
  
  
      template <
          unsigned long alphabet_size,
          unsigned long pool_size,
          typename mem_manager
          >
      void conditioning_class_kernel_4<alphabet_size,pool_size,mem_manager>::
      half_counts (
      ) 
      {
          total = 0;
          if (escapes > 1)
              escapes >>= 1;
  
          //divide all counts by 2
          node* temp = next;
          while (temp)
          {
              temp->count >>= 1;
              total += temp->count;
              temp = temp->next;
          }
          total += escapes;
      }
  
  // ----------------------------------------------------------------------------------------
   
  }
  
  #endif // DLIB_CONDITIONING_CLASS_KERNEl_4_
  
  