dlib C++ Library - conditioning_class_kernel_4.h

// 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_