LZW Compressor
 All Classes Files Functions Variables Typedefs
EncoderDictionary Class Reference

Encoder's custom dictionary type. More...

Classes

struct  Node
 Binary search tree node. More...
 

Public Member Functions

 EncoderDictionary ()
 Default constructor. More...
 
void reset ()
 Resets dictionary to its initial contents. More...
 
CodeType search_and_insert (CodeType i, char c)
 Searches for a pair (i, c) and inserts the pair if it wasn't found. More...
 
CodeType search_initials (char c) const
 Fakes a search for byte c in the one-byte area of the dictionary. More...
 

Private Attributes

std::vector< Nodevn
 Vector of nodes on top of which the binary search tree is implemented.
 
std::array< CodeType, 1u<< CHAR_BIT > initials
 Cheat sheet for mapping one-byte strings to their codes.
 

Detailed Description

Encoder's custom dictionary type.

Definition at line 53 of file lzw_v5.cpp.

Constructor & Destructor Documentation

EncoderDictionary::EncoderDictionary ( )
inline

Default constructor.

It builds the initials cheat sheet.

Definition at line 80 of file lzw_v5.cpp.

References initials, reset(), and vn.

81  {
82  const long int minc = std::numeric_limits<char>::min();
83  const long int maxc = std::numeric_limits<char>::max();
84  CodeType k {0};
85 
86  for (long int c = minc; c <= maxc; ++c)
87  initials[static_cast<unsigned char> (c)] = k++;
88 
89  vn.reserve(globals::dms);
90  reset();
91  }

Member Function Documentation

void EncoderDictionary::reset ( )
inline

Resets dictionary to its initial contents.

See Also
EncoderDictionary::EncoderDictionary()

Definition at line 97 of file lzw_v5.cpp.

References vn.

Referenced by EncoderDictionary(), and search_and_insert().

98  {
99  vn.clear();
100 
101  const long int minc = std::numeric_limits<char>::min();
102  const long int maxc = std::numeric_limits<char>::max();
103 
104  for (long int c = minc; c <= maxc; ++c)
105  vn.push_back(Node(c));
106  }
CodeType EncoderDictionary::search_and_insert ( CodeType  i,
char  c 
)
inline

Searches for a pair (i, c) and inserts the pair if it wasn't found.

Parameters
icode to search for
cattached byte to search for
Returns
The index of the pair, if it was found.
Return values
globals::dmsif the pair wasn't found

Definition at line 115 of file lzw_v5.cpp.

References reset(), search_initials(), and vn.

Referenced by compress().

116  {
117  // dictionary's maximum size was reached
118  if (vn.size() == globals::dms)
119  reset();
120 
121  if (i == globals::dms)
122  return search_initials(c);
123 
124  const CodeType vn_size = vn.size();
125  CodeType ci {vn[i].first}; // Current Index
126 
127  if (ci != globals::dms)
128  {
129  while (true)
130  if (c < vn[ci].c)
131  {
132  if (vn[ci].left == globals::dms)
133  {
134  vn[ci].left = vn_size;
135  break;
136  }
137  else
138  ci = vn[ci].left;
139  }
140  else
141  if (c > vn[ci].c)
142  {
143  if (vn[ci].right == globals::dms)
144  {
145  vn[ci].right = vn_size;
146  break;
147  }
148  else
149  ci = vn[ci].right;
150  }
151  else // c == vn[ci].c
152  return ci;
153  }
154  else
155  vn[i].first = vn_size;
156 
157  vn.push_back(Node(c));
158  return globals::dms;
159  }
CodeType EncoderDictionary::search_initials ( char  c) const
inline

Fakes a search for byte c in the one-byte area of the dictionary.

Parameters
cbyte to search for
Returns
The code associated to the searched byte.

Definition at line 166 of file lzw_v5.cpp.

References initials.

Referenced by compress(), and search_and_insert().

167  {
168  return initials[static_cast<unsigned char> (c)];
169  }

The documentation for this class was generated from the following file: