FilesExpand file tree

 master

/

FrequencyTable.hpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

163 lines (85 loc) · 4.48 KB

 master

/

FrequencyTable.hpp

Copy path

Top

File metadata and controls

• Code
• Blame

163 lines (85 loc) · 4.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

/*

* Reference arithmetic coding

*

* Copyright (c) Project Nayuki

* MIT License. See readme file.

* https://www.nayuki.io/page/reference-arithmetic-coding

*/

#pragma once

#include <cstdint>

#include <vector>

/*

* A table of symbol frequencies. The table holds data for symbols numbered from 0

* to getSymbolLimit()-1. Each symbol has a frequency, which is a non-negative integer.

* Frequency table objects are primarily used for getting cumulative symbol

* frequencies. These objects can be mutable depending on the implementation.

* The total of all symbol frequencies must not exceed UINT32_MAX.

*/

class FrequencyTable {

public: virtual ~FrequencyTable() = 0;

// Returns the number of symbols in this frequency table, which is a positive number.

public: virtual std::uint32_t getSymbolLimit() const = 0;

// Returns the frequency of the given symbol.

public: virtual std::uint32_t get(std::uint32_t symbol) const = 0;

// Sets the frequency of the given symbol to the given value.

public: virtual void set(std::uint32_t symbol, std::uint32_t freq) = 0;

// Increments the frequency of the given symbol.

public: virtual void increment(std::uint32_t symbol) = 0;

// Returns the total of all symbol frequencies. The returned

// value is always equal to getHigh(getSymbolLimit() - 1).

public: virtual std::uint32_t getTotal() const = 0;

// Returns the sum of the frequencies of all the symbols strictly below the given symbol value.

public: virtual std::uint32_t getLow(std::uint32_t symbol) const = 0;

// Returns the sum of the frequencies of the given symbol and all the symbols below.

public: virtual std::uint32_t getHigh(std::uint32_t symbol) const = 0;

};

class FlatFrequencyTable final : public FrequencyTable {

/*---- Fields ----*/

// Total number of symbols, which is at least 1.

private: std::uint32_t numSymbols;

/*---- Constructor ----*/

// Constructs a flat frequency table with the given number of symbols.

public: explicit FlatFrequencyTable(std::uint32_t numSyms);

/*---- Methods ----*/

public: std::uint32_t getSymbolLimit() const override;

public: std::uint32_t get(std::uint32_t symbol) const override;

public: std::uint32_t getTotal() const override;

public: std::uint32_t getLow(std::uint32_t symbol) const override;

public: std::uint32_t getHigh(std::uint32_t symbol) const override;

public: void set(std::uint32_t symbol, std::uint32_t freq) override;

public: void increment(std::uint32_t symbol) override;

private: void checkSymbol(std::uint32_t symbol) const;

};

/*

* A mutable table of symbol frequencies. The number of symbols cannot be changed

* after construction. The current algorithm for calculating cumulative frequencies

* takes linear time, but there exist faster algorithms such as Fenwick trees.

*/

class SimpleFrequencyTable final : public FrequencyTable {

/*---- Fields ----*/

// The frequency for each symbol. Its length is at least 1.

private: std::vector<std::uint32_t> frequencies;

// cumulative[i] is the sum of 'frequencies' from 0 (inclusive) to i (exclusive).

// Initialized lazily. When its length is not zero, the data is valid.

private: mutable std::vector<std::uint32_t> cumulative;

// Always equal to the sum of 'frequencies'.

private: std::uint32_t total;

/*---- Constructors ----*/

// Constructs a frequency table from the given array of symbol frequencies.

// There must be at least 1 symbol, and the total must not exceed UINT32_MAX.

public: explicit SimpleFrequencyTable(const std::vector<std::uint32_t> &freqs);

// Constructs a frequency table by copying the given frequency table.

public: explicit SimpleFrequencyTable(const FrequencyTable &freqs);

/*---- Methods ----*/

public: std::uint32_t getSymbolLimit() const override;

public: std::uint32_t get(std::uint32_t symbol) const override;

public: void set(std::uint32_t symbol, std::uint32_t freq) override;

public: void increment(std::uint32_t symbol) override;

public: std::uint32_t getTotal() const override;

public: std::uint32_t getLow(std::uint32_t symbol) const override;

public: std::uint32_t getHigh(std::uint32_t symbol) const override;

// Recomputes the array of cumulative symbol frequencies.

private: void initCumulative(bool checkTotal=true) const;

// Adds the given integers, or throws an exception if the result cannot be represented as a uint32_t (i.e. overflow).

private: static std::uint32_t checkedAdd(std::uint32_t x, std::uint32_t y);

};