LZW Compressor
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Pages
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...
 
std::vector< Node >::size_type size () const
 Returns the number of dictionary entries.
 

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 66 of file lzw_v6.cpp.

Constructor & Destructor Documentation

EncoderDictionary::EncoderDictionary ( )
inline

Default constructor.

It builds the initials cheat sheet.

Definition at line 93 of file lzw_v6.cpp.

References initials, reset(), and vn.

94  {
95  const long int minc = std::numeric_limits<char>::min();
96  const long int maxc = std::numeric_limits<char>::max();
97  CodeType k {0};
98 
99  for (long int c = minc; c <= maxc; ++c)
100  initials[static_cast<unsigned char> (c)] = k++;
101 
102  vn.reserve(globals::dms);
103  reset();
104  }

Member Function Documentation

void EncoderDictionary::reset ( )
inline

Resets dictionary to its initial contents.

Note
Adds dummy nodes to account for the metacodes.

Definition at line 110 of file lzw_v6.cpp.

References vn.

Referenced by compress(), and EncoderDictionary().

111  {
112  vn.clear();
113 
114  const long int minc = std::numeric_limits<char>::min();
115  const long int maxc = std::numeric_limits<char>::max();
116 
117  for (long int c = minc; c <= maxc; ++c)
118  vn.push_back(Node(c));
119 
120  // add dummy nodes for the metacodes
121  vn.push_back(Node('\x00')); // MetaCode::Eof
122  }
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 131 of file lzw_v6.cpp.

References search_initials(), and vn.

Referenced by compress().

132  {
133  if (i == globals::dms)
134  return search_initials(c);
135 
136  const CodeType vn_size = vn.size();
137  CodeType ci {vn[i].first}; // Current Index
138 
139  if (ci != globals::dms)
140  {
141  while (true)
142  if (c < vn[ci].c)
143  {
144  if (vn[ci].left == globals::dms)
145  {
146  vn[ci].left = vn_size;
147  break;
148  }
149  else
150  ci = vn[ci].left;
151  }
152  else
153  if (c > vn[ci].c)
154  {
155  if (vn[ci].right == globals::dms)
156  {
157  vn[ci].right = vn_size;
158  break;
159  }
160  else
161  ci = vn[ci].right;
162  }
163  else // c == vn[ci].c
164  return ci;
165  }
166  else
167  vn[i].first = vn_size;
168 
169  vn.push_back(Node(c));
170  return globals::dms;
171  }
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 178 of file lzw_v6.cpp.

References initials.

Referenced by compress(), and search_and_insert().

179  {
180  return initials[static_cast<unsigned char> (c)];
181  }

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