coco
534 lines
16 KiB
C++
534 lines
16 KiB
C++
// 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_
|
|
|