// Copyright (C) 2003 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#undef DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_
#ifdef DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_
#include "../algs.h"
namespace dlib
{
template <
unsigned long alphabet_size
>
class conditioning_class
{
/*!
REQUIREMENTS ON alphabet_size
1 < alphabet_size < 65536
INITIAL VALUE
get_total() == 1
get_count(X) == 0 : for all valid values of X except alphabet_size-1
get_count(alphabet_size-1) == 1
WHAT THIS OBJECT REPRESENTS
This object represents a conditioning class used for arithmetic style
compression. It maintains the cumulative counts which are needed
by the entropy_coder and entropy_decoder objects.
At any moment a conditioning_class object represents a set of
alphabet_size symbols. Each symbol is associated with an integer
called its count.
All symbols start out with a count of zero except for alphabet_size-1.
This last symbol will always have a count of at least one. It is
intended to be used as an escape into a lower context when coding
and so it must never have a zero probability or the decoder won't
be able to identify the escape symbol.
NOTATION:
Let MAP(i) be a function which maps integers to symbols. MAP(i) is
one to one and onto. Its domain is 1 to alphabet_size inclusive.
Let RMAP(s) be the inverse of MAP(i).
( i.e. RMAP(MAP(i)) == i and MAP(RMAP(s)) == s )
Let COUNT(i) give the count for the symbol MAP(i).
( i.e. COUNT(i) == get_count(MAP(i)) )
Let LOW_COUNT(s) == the sum of COUNT(x) for x == 1 to x == RMAP(s)-1
(note that the sum of COUNT(x) for x == 1 to x == 0 is 0)
Let HIGH_COUNT(s) == LOW_COUNT(s) + get_count(s)
Basically what this is saying is just that you shoudln't assume you know
what order the symbols are placed in when calculating the cumulative
sums. The specific mapping provided by the MAP() function is unspecified.
THREAD SAFETY
This object can be used safely in a multithreaded program as long as the
global state is not shared between conditioning classes which run on
different threads.
GLOBAL_STATE_TYPE
The global_state_type obejct allows instances of the conditioning_class
object to share any kind of global state the implementer desires.
However, the global_state_type object exists primarily to facilitate the
sharing of a memory pool between many instances of a conditioning_class
object. But note that it is not required that there be any kind of
memory pool at all, it is just a possibility.
!*/
public:
class global_state_type
{
global_state_type (
);
/*!
ensures
- #*this is properly initialized
throws
- std::bad_alloc
!*/
// my contents are implementation specific.
};
conditioning_class (
global_state_type& global_state
);
/*!
ensures
- #*this is properly initialized
- &#get_global_state() == &global_state
throws
- std::bad_alloc
!*/
~conditioning_class (
);
/*!
ensures
- all memory associated with *this has been released
!*/
void clear(
);
/*!
ensures
- #*this has its initial value
throws
- std::bad_alloc
!*/
bool increment_count (
unsigned long symbol,
unsigned short amount = 1
);
/*!
requires
- 0 <= symbol < alphabet_size
- 0 < amount < 32768
ensures
- if (sufficient memory is available to complete this operation) then
- returns true
- if (get_total()+amount < 65536) then
- #get_count(symbol) == get_count(symbol) + amount
- else
- #get_count(symbol) == get_count(symbol)/2 + amount
- if (get_count(alphabet_size-1) == 1) then
- #get_count(alphabet_size-1) == 1
- else
- #get_count(alphabet_size-1) == get_count(alphabet_size-1)/2
- for all X where (X != symbol)&&(X != alpahbet_size-1):
#get_count(X) == get_count(X)/2
- else
- returns false
!*/
unsigned long get_count (
unsigned long symbol
) const;
/*!
requires
- 0 <= symbol < alphabet_size
ensures
- returns the count for the specified symbol
!*/
unsigned long get_total (
) const;
/*!
ensures
- returns the sum of get_count(X) for all valid values of X
(i.e. returns the sum of the counts for all the symbols)
!*/
unsigned long get_range (
unsigned long symbol,
unsigned long& low_count,
unsigned long& high_count,
unsigned long& total_count
) const;
/*!
requires
- 0 <= symbol < alphabet_size
ensures
- returns get_count(symbol)
- if (get_count(symbol) != 0) then
- #total_count == get_total()
- #low_count == LOW_COUNT(symbol)
- #high_count == HIGH_COUNT(symbol)
- #low_count < #high_count <= #total_count
!*/
void get_symbol (
unsigned long target,
unsigned long& symbol,
unsigned long& low_count,
unsigned long& high_count
) const;
/*!
requires
- 0 <= target < get_total()
ensures
- LOW_COUNT(#symbol) <= target < HIGH_COUNT(#symbol)
- #low_count == LOW_COUNT(#symbol)
- #high_count == HIGH_COUNT(#symbol)
- #low_count < #high_count <= get_total()
!*/
global_state_type& get_global_state (
);
/*!
ensures
- returns a reference to the global state used by *this
!*/
unsigned long get_memory_usage (
) const;
/*!
ensures
- returns the number of bytes of memory allocated by all conditioning_class
objects that share the global state given by get_global_state()
!*/
static unsigned long get_alphabet_size (
);
/*!
ensures
- returns alphabet_size
!*/
private:
// restricted functions
conditioning_class(conditioning_class<alphabet_size>&); // copy constructor
conditioning_class<alphabet_size>& operator=(conditioning_class<alphabet_size>&); // assignment operator
};
}
#endif // DLIB_CONDITIONING_CLASS_KERNEl_ABSTRACT_