Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
ArithmeticModel.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <stdexcept>
9#include <alib/map>
10#include <alib/set>
11
12template < class SymbolType >
14 ext::map < SymbolType, unsigned > m_high_cumulative_frequency;
15 unsigned m_global_high; // EOF is with probability 1/n (ie its low is m_global_high - 1 and hight is m_global_high) with cumulative frequency right below the m_global_high
16
17public:
19 unsigned frequency = 0;
20 for ( const SymbolType & symbol : alphabet )
21 m_high_cumulative_frequency.insert ( std::make_pair ( symbol, ++ frequency ) );
22 m_global_high = frequency + 1;
23 }
24
25 void update ( const SymbolType & symbol ) {
26 for ( auto i = m_high_cumulative_frequency.find ( symbol ); i != m_high_cumulative_frequency.end ( ) ; ++ i )
27 i->second += 1;
28 m_global_high += 1;
29 }
30
31 void getProbability ( const SymbolType & c, unsigned & low_prob, unsigned & high_prob ) const {
32 auto i = m_high_cumulative_frequency.find ( c );
33 high_prob = i->second;
34 low_prob = 0;
35
36 if ( i != m_high_cumulative_frequency.begin ( ) )
37 low_prob = std::prev ( i )->second;
38 }
39
40 void getProbabilityEof ( unsigned & low_prob, unsigned & high_prob ) const {
41 low_prob = m_global_high - 1;
42 high_prob = m_global_high;
43 }
44
45 SymbolType getChar ( unsigned scaled_value, unsigned & low_prob, unsigned & high_prob ) const {
46 for ( auto i = m_high_cumulative_frequency.begin ( ); i != m_high_cumulative_frequency.end ( ); ++ i )
47 if ( scaled_value < i->second ) {
48 high_prob = i->second;
49 low_prob = 0;
50
51 if ( i != m_high_cumulative_frequency.begin ( ) )
52 low_prob = std::prev ( i )->second;
53
54 return i->first;
55 }
56 throw std::logic_error("error");
57 }
58
59 bool isEof ( unsigned scaled_value ) const {
60 return scaled_value == m_global_high - 1;
61 }
62
63 unsigned getCount ( ) const {
64 return m_global_high;
65 }
66
67};
68
Definition: ArithmeticModel.h:13
void update(const SymbolType &symbol)
Definition: ArithmeticModel.h:25
void getProbability(const SymbolType &c, unsigned &low_prob, unsigned &high_prob) const
Definition: ArithmeticModel.h:31
bool isEof(unsigned scaled_value) const
Definition: ArithmeticModel.h:59
void getProbabilityEof(unsigned &low_prob, unsigned &high_prob) const
Definition: ArithmeticModel.h:40
ArithmeticModel(const ext::set< SymbolType > &alphabet)
Definition: ArithmeticModel.h:18
unsigned getCount() const
Definition: ArithmeticModel.h:63
SymbolType getChar(unsigned scaled_value, unsigned &low_prob, unsigned &high_prob) const
Definition: ArithmeticModel.h:45
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: map.hpp:185
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
auto end() &
Inherited behavior of end for non-const instance.
Definition: map.hpp:215
Definition: set.hpp:44
Definition: BarSymbol.cpp:12
p second
Definition: ToRegExpAlgebraic.h:126
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79