MFC COLLECTION CLASSES:
A collection class is used to create objects that are capable of storing other objects. MFC provides three basic types of collection classes. Each is available in template and non-template version. Using them requires very little code writing on the programmer's part. You must #include <afxtempl.h> in order to use any of the template collection classes.
USING CArray:
The member function 'SetAtGrow' stores an item in the CArray at the specified position or index. If the CArray is not large enough to hold, it expands to accommodate the new item. The member function 'SetAt' does the same but does not increase the CArray size automatically. The member function 'GetSize' gives the number of items stored in the CArray.
EXAMPLE 5.2:
#include <afx.h> // for using MFC class CString in a console type app.
#include <iostream.h>
#include <afxtempl.h> // for use of any MFC collection classes
int main()
{
CArray<CString, CString&> rgSports;
// The first parameter represents the type of object stored inside the list, the next
// parameter is the type of object passed as an argument for CArray functions
// Define the objects.
CString szBaseball("Baseball - NY Yankees");
CString szSoccer("Soccer - NY Giants");
CString szCricket("Cricket - South Africa");
CString szHockey("Hockey - Korea");
CString szBasketball("Baseball - Celtics");
// Add five teams to the rgSports array. The first parameter becomes the index and
// the second CString name , the reference to it will be passed.
rgSports.SetAtGrow(0, szBaseball);
rgSports.SetAtGrow(1, szSoccer);
rgSports.SetAtGrow(0, szCricket);
rgSports.SetAtGrow(0, szHockey);
rgSports.SetAtGrow(0, szBasketball);
// Display the contents of the Sports array.
cout << " The following are the major teams in respective sports:" << endl;
int nSports = rgSports.GetSize();
for( int nSportsIndex = 0; nSportsIndex < nSports; nSportsIndex++ )
{
cout << "\t" << rgSports[nSportsIndex] << endl;
}
// Remove the the items stored in the rgSports array.
rgSports.RemoveAll();
return EXIT_SUCCESS;
}
USING CList:
A CList has two ends i.e., a head and a tail. To add an item to the head of a Clist, the member function AddHead is used whereas to add an item to the tail of a CList the member function AddTail is used.
EXAMPLE 5.3:
#include <afx.h> // for using MFC class CString
#include <iostream.h>
#include <afxtempl.h> // for use of any MFC collection class
int main()
{
// The first parameter represents the type of object stored inside the list, the next
// parameter is the type of object passed as an argument for CList functions
// rgSports is an instance of CArray.
CList<CString, CString&> ProfessorList;
// Define the objects.
CString szTariq("Sobh, Tariq");
CString szKhaled("Elleithy, Khaled");
CString szAusif("Mahmood, Ausif");
CString szYi("Yi, Hua");
CString szAbdel("Abuzneid, AbdelShakour");
// Add five names to the ProfessorList.
ProfessorList.AddTail( szTariq );
ProfessorList.AddTail( szKhalid );
ProfessorList.AddTail( szAusif );
ProfessorList.AddTail( szYi);
ProfessorList.AddTail( szAbdel );
// Display the contents of the ProfessorList.
cout << " The members of the teaching staff at Stamford Campus:" << endl;
POSITION pos = ProfessorList.GetHeadPosition();
While( pos != NULL )
{
CString szProfessor = ProfessorList.GetNext( pos );
cout << "\t" << szProfessor << endl;
}
// Remove the the items stored in the rgSports array.
ProfessorList.RemoveAll();
Return EXIT_SUCCESS;
}
USING CMap:
The SetAt member function is used to store an item and a key in the collection. The Lookup member function is used to retrieve an item in the collection based on the key. A CMap can be searched using a GetStartPosition function which returns a POSITION variable that is advanced to the next item using GetNextAssoc member function.
EXAMPLE 5.4:
#include <afx.h> // for using MFC classes in a console app
#include <iostream.h>
#include <afxtempl.h> // for use of any MFC collection class
int main()
{
CMap<int, int, CString, CString&> ProfessorList;
// The first two parameters are used for the key type. The first is the type of key
// used inside the collection and the second parameter is the type of key used as an
// argument in the member functions.
// The third parameter represent the type of object stored inside the hash table, the
// last parameter is the type of object passed as an argument for CMap functions
// Define the objects.
CString szTariq("Sobh, Tariq");
CString szKhaled("Elleithy, Khaled");
CString szAusif("Mahmood, Ausif");
CString szYi("Yi, Hua");
CString szAbdel("Abuzneid, AbdelShakour");
// Add five names to the ProfessorList.
// First hash code is generated to add an item to the hash table.
// hash code = key % hash_table_size.
// For example if the table size is 100, then Mod 100 will divide
// the number by 100, and the remainder is the position
// e.g., 12564%100 is 64 so it will store szTariq at position 64
ProfessorList.SetAt( 12564, szTariq );
ProfessorList.SetAt( 12453, szKhalid );
ProfessorList.SetAt( 16342, szAusif );
ProfessorList.SetAt( 16355, szYi);
ProfessorList.SetAt( 16370, szAbdel );
// Display the contents of the ProfessorList.
cout << " The members of the teaching staff at Stamford Campus:" << endl;
// \n is for new line and\t is for tab
cout << "\nName\tID Number" << endl;
// will move the pos pointer to the beginning.
POSITION pos = ProfessorList.GetStartPosition();
While( pos != NULL )
{
CString szProfessor; // Professor Name
int nidNumber; // Professor's ID Number
ProfessorList.GetNextAssoc( pos, nidNumber, szProfessor );
cout << "\t" << szProfessor << "\t" << nidNumber << endl;
}
// To retrieve a professor's name using the key
CString szProfessor;
// We want to find the name of the professor whose ID is 12453.
BOOL bFound = ProfessorList.Lookup( 12453, szProfessor );
if( TRUE ==bFound )
// writing bFound == TRUE also works but its more error prone.
{
cout << "\nNumber ID belongs to " << szProfessor << endl;
}
// Remove the the items stored in the rgSports array.
ProfessorList.RemoveAll();
Return EXIT_SUCCESS;
}
IMPLEMENTATION OF LZW COMPRESSION:
LZW is a famous text compression algorithm (also used in compressing images to gif form) developed by Lempel Ziv and Welsch.
EXAMPLE 5.5:
Text Compression
C version of compress program:
Develop a win32 console type application. Add a cpp file called comp.cpp and a header file called compconsts.h as shown below.
//--------compconsts.h---------------------------------------------
// constants defined for the LZW compression program
#ifndef COMPCONSTS_H
#define COMPCONSTS_H
const
D
= 4099, // hash
function divisor
codes
= 4096, // 2^12
ByteSize
= 8,
excess
= 4, // 12 -
ByteSize
alpha
= 256, // 2^ByteSize
mask1
= 255, // alpha - 1
mask2
= 15; // 2^excess-1
struct hash_bucket {
int
code;
unsigned
long key;
struct
hash_bucket * next;
};
struct element {
/* hash table data structure needed in LZW compression */
int
code;
unsigned
long key;
};
void InitHashTable();
void SetAt(unsigned long k, struct element e);
int Lookup(unsigned long key, struct element e);
struct
hash_bucket * hash_table[D];
struct
hash_bucket hashb[codes]; /* total
number of buckets */
struct
hash_bucket * avail, * last;/* storage pool pointers */
void InitHashTable() {
int
i;
for
(i = 0; i < (codes-1); i++)
hashb[i].next
= &(hashb[i+1]);
avail
= &(hashb[0]); last = &(hashb[codes-1]);
for (i =
0; i < D; i++)
hash_table[i]
= NULL;
}
void SetAt(unsigned long k, struct element e) {
int
pos; struct hash_bucket * tempavail, * temp_hash;
pos
= k % D;
tempavail
= avail;
tempavail->key
= e.key;
tempavail->code
= e.code ;
avail
= avail->next;
if
(avail == last) {
printf("Hash
table overflow, out of buckets in storage pool \n");
exit(1);
}
if
(hash_table[pos] == NULL) { /* nothing
in this linked list */
hash_table[pos]
= tempavail;
tempavail->next
= NULL;
}
else /* linked list has some buckets already */
{
temp_hash
= hash_table[pos];
hash_table[pos]
= tempavail;
tempavail->next
= temp_hash;
}
}
int Lookup(unsigned long key, struct element * e) {
int
found, pos;
found
= 0;
struct
hash_bucket * temp_hash ;
pos
= key % D;
temp_hash
= hash_table[pos] ;
while
(found == 0) {
if
(temp_hash == NULL)
break;
if
(temp_hash->key == key)
{
found
= 1;
e->code
= temp_hash->code;
e->key
= temp_hash->key;
break;
}
temp_hash
= temp_hash->next;
}
return
found;
}
#endif
/*-----------------------Comp.cpp----------------------------------*/
#include <afxtempl.h>
#include <fstream.h>
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "compconsts.h"
/*
constants for the compression program */
void
Compressit();
void
Output(unsigned long pcode);
/*--------------globals---------------------------------*/
int
LeftOver, /* code bits yet to be
output */
status=0; /*
status= 0 means no bits in LeftOver */
FILE * in;
FILE * out;
/*------------------------------------------------------*/
/*-------------------------------------------------------------*/
void OpenFiles()
{
char
OutputFile[50], InputFile[50];
char
* found ; int fnamelenwoutext;
int
i;
printf("Enter
name of file to compress, should have .txt extension\n");
scanf("%s",
InputFile);
/*
name should not have an extension */
found
= strstr(InputFile, ".txt") ;
if
(found == NULL) {
cerr
<< "File name does not have an extension .txt" << endl;
exit
(1);
}
//
open files in binary mode
in
= fopen(InputFile,"rb"); /*
binary mode reading */
if
(in== NULL) {
printf("Cannot
open %s\n" , InputFile);
exit
(1);
}
/*
remove the extension from the Input File and add .zzz extension */
fnamelenwoutext
= found-InputFile ;
for (i =
0; i <= fnamelenwoutext; i++)
OutputFile[i]
= InputFile[i];
OutputFile[fnamelenwoutext]
= '\0';
strcat(OutputFile,
".zzz");
out
= fopen(OutputFile, "wb");
}
/*-------------------------------------------------------------------*/
void Compressit()
{
/*
Lempel-Ziv-Welch compressor */
int
used; unsigned long k, pcode, temp1;
struct
element e;
InitHashTable(); /* initialize hashtable size */
for
(int i = 0; i < alpha; i++) { /* initialize */
e.key
= i;
e.code
= i;
temp1=e.key
;
SetAt(temp1,e);
}
used
= alpha; /* number of codes used */
/*
input and compress */
unsigned
char c;
c
= fgetc(in); /* first character of
input file */
pcode
= c; /* prefix code */
if
(!feof(in)) { /* file length is >
1 */
do
{ /* process rest of file */
c
= fgetc(in);
if
(feof(in)) break; /*
finished */
k
= (pcode << ByteSize) + c;
/*
see if code for k is in the dictionary
*/
if
(Lookup(k, &e)==1) pcode = e.code; /* yes
*/
else
{ /* k not in table */
Output(pcode);
if
(used < codes) { /* create new code */
e.code
= used++;
e.key
= ((pcode << ByteSize) | c);
temp1
= e.key;
SetAt(temp1,e);
}
else
{
printf("error,
overflow in dictionary\n");
exit(1);
}
pcode
= c; }
}
while (true);
/*
output last code(s) */
Output(pcode);
if
(status) {
c
= LeftOver << excess;
fputc(c,out);
}
}
fclose(out);
fclose(in);
}
/*--------------------------------------------------------------------*/
void Output(unsigned long pcode)
{
/* output 8 bits, save rest in
LeftOver */
unsigned
char c, d;
if
(status) { /* 4 bits
remain */
d
= pcode & mask1; /* right ByteSize bits */
c
= (LeftOver << excess) | (pcode >> ByteSize);
fputc(c,out);
fputc(d,out);
status
= 0;
}
else {
LeftOver
= pcode & mask2; /* right
excess bits */
c
= pcode >> excess;
fputc(c,out);
status
= 1;
}
}
/*---------------------------------------------------------------------*/
/*---------------------------------------------------------------------*/
int main() {
OpenFiles();
Compressit();
cout
<< "program done" <<endl;
}
/*----------------------------------------------------------------------*/
C++ version of compress program using MFC
CMap:
Develop a win32 console type application. Add a cpp file called comp.cpp and a header file called compconsts.h as shown below.
//--------compconsts.h---------------------------------------------
// constants defined for the LZW compression program
#ifndef COMPCONSTS_H
#define COMPCONSTS_H
const
D
= 4099, // hash
function divisor
codes
= 4096, // 2^12
ByteSize
= 8,
excess
= 4, // 12 -
ByteSize
alpha
= 256, // 2^ByteSize
mask1
= 255, // alpha - 1
mask2
= 15; // 2^excess-1
#endif
/*-----------------------Comp.cpp----------------------------------*/
#include <afxtempl.h>
#include <fstream.h>
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "compconsts.h"
/*
constants for the compression program */
struct
element { /* hash table data structure
needed in LZW compression */
int
code;
unsigned
long key;
};
void
Compressit();
void
Output(unsigned long pcode);
int
LeftOver, /* code bits yet to be
output */
status=0; /* status= 0 means no bits in
LeftOver */
ifstream in;
ofstream out;
void OpenFiles()
{
//
create input and output streams
char
OutputFile[50], InputFile[50];
char
* found ; int fnamelenwoutext;
int
i;
printf("Enter
name of file to compress, should have .txt extension\n");
cin
>> InputFile;
/*
name should not have an extension */
found
= strstr(InputFile, ".txt") ;
if
(found == NULL) {
cerr
<< "File name does not have an extension .txt" << endl;
exit
(1);
}
//
open files in binary mode
in.open(InputFile,
ios::binary);
if
(in.fail()) {
cerr
<< "Cannot open " << InputFile << endl;
exit
(1);
}
/*
remove the extension from the Input File and add .zzz extension */
fnamelenwoutext
= found-InputFile ;
for (i =
0; i <= fnamelenwoutext; i++)
OutputFile[i]
= InputFile[i];
OutputFile[fnamelenwoutext]
= '\0';
strcat(OutputFile,
".zzz");
out.open(OutputFile,
ios::binary);
}
//-------------------------------------------------------------------
void Compressit()
{
//
Lempel-Ziv-Welch compressor
CMap
<unsigned long, unsigned long&,element, element &> h;
h.InitHashTable(543,TRUE); // initialize hastable size
struct
element e;
for
(int i = 0; i < alpha; i++) { // initialize
e.key
= i;
e.code
= i;
unsigned
long temp1;
temp1=e.key
;
h.SetAt(temp1,e);
}
int
used = alpha; // number of codes used
//
input and compress
unsigned
char c;
in.get(c); // first character of input file
unsigned
long pcode = c; // prefix code
if
(!in.eof()) { // file length is > 1
do
{ // process rest of file
in.get(c);
if
(in.eof()) break; // finished
unsigned
long k = (pcode << ByteSize) + c;
//
see if code for k is in the dictionary
if
(h.Lookup(k, e)) pcode = e.code; // yes
else
{ // k not in table
Output(pcode);
if
(used < codes) { // create new code
e.code
= used++;
e.key
= ((pcode << ByteSize) | c);
unsigned
long temp1;
temp1
= e.key;
h.SetAt(temp1,e);
}
pcode
= c; }
}
while (true);
//
output last code(s)
Output(pcode);
if
(status) {
c
= LeftOver << excess;
out.put(c);
}
}
out.close();
in.close();
}
/*--------------------------------------------------------------------*/
void Output(unsigned long pcode)
{
/* output 8 bits, save rest in
LeftOver */
unsigned
char c, d;
if
(status) { /* 4 bits
remain */
d
= pcode & mask1; /* right ByteSize bits */
c
= (LeftOver << excess) | (pcode >> ByteSize);
out.put(c);
out.put(d);
status
= 0;
}
else {
LeftOver
= pcode & mask2; /* right
excess bits */
c
= pcode >> excess;
out.put(c);
status
= 1;
}
}
/*---------------------------------------------------------------------*/
/*---------------------------------------------------------------------*/
int main() {
OpenFiles();
Compressit();
cout
<< "program done" <<endl;
}
LZW Decompression Program:
Develop a win32 console application and add two cpp files and three header files. The header files are called compconsts.h, Cdecompress.h and decompress_element.h.
//--------compconsts.h---------------------------------------------
// constants defined for the LZW compression/decomp
program
#ifndef COMPCONSTS_H
#define COMPCONSTS_H
const
D
= 4099, // hash
function divisor
codes
= 4096, // 2^12
ByteSize
= 8,
excess
= 4, // 12 -
ByteSize
alpha
= 256, // 2^ByteSize
mask
= 15,
mask1
= 255, // alpha - 1
mask2
= 15; // 2^excess-1
#endif
//----------------------Cdecompress.h--------------------------------------
//---------Class encapsulating the decompression
process-------------------
#include <fstream.h>
#include "decompress_element.h"
#include "compconsts.h"
#ifndef CDECOMPRESS_H
#define CDECOMPRESS_H
class CDecompress {
unsigned
char s[codes]; // used to reconstruct
text
int
size, //
size of reconstructed text
LeftOver, //
left over bits from last code
status; //
0 iff no left over bits
decompress_element
ht[codes]; //
dictionary
ifstream
in;
ofstream
out;
public:
CDecompress()
{ status = 0;}
void
SetFilesDecompress();
void
Decompressit();
private:
bool
GetCode(int& code);
void
OutputDecompress(int code);
};
#endif
//-----------------decompress_element.h---------------------------------
// definition for the class decompress_element
needed in LZW decompression
#ifndef DECOMPRESS_ELEMENT_H
#define DECOMPRESS_ELEMENT_H
class decompress_element {
friend
class Cdecompress();
public:
void
set_prefix(int m) { prefix = m;}
int
get_prefix(){return prefix;}
void
set_suffix(unsigned char n) { suffix = n;}
unsigned
char get_suffix() { return suffix; }
private:
int
prefix;
unsigned
char suffix;
};
#endif
The cpp files to be added are called Cdecompress.cpp and decompress.cpp.
//----------------------Cdecompress.cpp--------------------------------------
//---------Implementation file for Cdecompress
class-------------------------
#include <fstream.h>
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "decompress_element.h"
#include "Cdecompress.h"
#include "compconsts.h"
//-------------------------------------------------------------------
void CDecompress::SetFilesDecompress()
{
//
determine file name
char
OutputFile[50], InputFile[50];
//
see if file name is provided
cout
<< "Enter name of file to decompress" << endl;
cout
<< "Omit the extension .zzz" << endl;
cin
>> OutputFile;
//
name should not have an extension
if
(strchr(OutputFile, '.')) {
cerr
<< "File name has an extension" << endl;
exit
(1);
}
strcpy(InputFile,
OutputFile);
strcat(InputFile,
".zzz");
//
open files in binary mode
in.open(InputFile,
ios::binary);
if
(in.fail()) {
cerr
<< "Cannot open " << InputFile << endl;
exit
(1);
}
out.open(OutputFile,
ios::binary);
}
//-------------------------------------------------------------------
void CDecompress::OutputDecompress(int code) {
//
Output string corresponding to code
size
= -1;
while
(code >= alpha) { // suffix in
dictionary
s[++size]
= ht[code].get_suffix();
code
= ht[code].get_prefix();
}
s[++size]
= code; // code < alpha
//
decompressed string is s[size] .... s[0]
for
(int i = size; i >= 0; i--)
out.put(s[i]);
}
//-------------------------------------------------------------------
bool CDecompress::GetCode(int& code)
{
//
put next code in compressed file into code
//
return false if no more codes
unsigned
char c, d;
in.get(c); // input 8 bits
if
(in.eof()) return false; // no more
codes
//
see if any left over bits from before
//
if yes, concatenate with left over 4 bits
if
(status) code = (LeftOver << ByteSize) | c;
else
{ // no left over bits, need four more bits to complete code
in.get(d); // another 8 bits
code
= (c << excess) | (d >> excess);
LeftOver
= d & mask; // save 4 bits
}
status
= 1 - status;
return
true;
}
//-------------------------------------------------------------------
void CDecompress::Decompressit()
{
//
decompress a compressed file
int
used = alpha; // codes used so far
//
input and decompress
int
pcode, //
previous code
ccode; // current code
if
(GetCode(pcode)) { // file is not empty
s[0]
= pcode; // character for pcode
out.put(s[0]); // output string for pcode
size
= 0; // s[size] is first
character of last string output
};
while
(GetCode(ccode)) { // get another code
if
(ccode < used) { // ccode
is defined
OutputDecompress(ccode);
if
(used < codes) { // create new code
ht[used].set_prefix(pcode);
ht[used++].set_suffix(s[size]);
}
}
else { // special case, undefined code
ht[used].set_prefix(pcode);
ht[used++].set_suffix(s[size]);
OutputDecompress(ccode);
}
pcode
= ccode;
}
out.close();
in.close();
}
//----------------------decompress.cpp
(main)-------------------------------
//---------LZW decompression program (console
app)--------------------------
#include <iostream.h>
#include "Cdecompress.h"
void main()
{
CDecompress
d1;
d1.SetFilesDecompress();
d1.Decompressit();
cout
<< "done decompression" << endl;
}