coco
501 lines
14 KiB
C++
501 lines
14 KiB
C++
// 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_
|
|
|