C++ Student Database realization using binary files

database

This will be a simple but yet efficient realization of a Database creation using C++ and binary file as Database.

Problem: Create a Student Database using binary file implementation. The Database should contain student details – faculty number, name and average score. The Faculty number should be in range 43000 – 43999. Create Database methods like – insert student details, delete student details, edit student details (you are allowed to edit only the average score), print all the current students. Make a simple console interface with exit option.

Before writing down the solution let’s recall what is a binary file – a file organized by blocks or containers. We will create structure/class Student and each object will be represented in the file as container. This way every object has specific place in the file and we can modify it freely – in the sequential ordered files such approach was not possible. When using binary files we should initialize the empty file in advance (with some trivial or empty objects). The methods of reading/writing/modifying binary files will be shown in the codes below.

Let’s first define all the helper functions plus the main function too:

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

#define MIN_FN 43000
#define MAX_FN 43999

const string fileName = "DB.data";
const int maxNameSize = 100;

struct Student {
	int fn;
	char name[maxNameSize];
	double avgScore;
};

void choose(char&);
void init();
void insertStudent();
void deleteStudent();
void editStudent();
void searchStudent();
void clearBuffer();
void printStudents();

void main()
{
	init();
	char choice = ' ';
	while (choice != 'x') {
		cout << "\n\t You have entered the Students Database";
		cout << "\n\t --------------------------------------";
		cout << "\n\t (I)nsert student details";
		cout << "\n\t (D)elete student details";
		cout << "\n\t (E)dit   student details";
		cout << "\n\t (P)rint all students    ";
		cout << "\n\t (S)earch student details";
		cout << "\n\t e(X)it\n\n";
		cout << "\n\t >";
		choose(choice);
	}
}

We have made the program more flexible by defining the min and max value. If we need to further extend the database it can be easily done by changing the values. We have created a structure called Student and we are ready to go (please pay attention the name is not dynamically allocated. Why?).

The simple interface is ready too. Let’s see what init() function will do:

void init() {
	fstream file;
	file.open(fileName,ios::in | ios::out | ios::app);
	file.seekg(0,ios::end);
	long isEmpty = file.tellg();

	if (isEmpty <= 0) {

		Student blankStudent = {0, " ", 0.0 };

		for (int i = MIN_FN; i <= MAX_FN; ++i) 
			file.write((const char*)(&blankStudent),sizeof(Student));
	}

	file.close();
}

First we open the file for both reading and writing. Then we set the ios – in,out and app. Appendix flag will move the get pointer to the end of the file (I have experiences some issues on different compilations though that’s why I move it again with specific command – file.seekg(0,ios::end); ). Let’s recall that seekg(offset,pos) moves the get pointer from “pos” with “offset” positions (left or right depends on the “offset” sign). Then we check if the file is empty – if it’s not empty – close it, if it’s empty – create it.

We create a blank Student and then fulfill the database with it. Pay attention to the casting we are doing – (const char*)(&blankStudent). We are saying – take the address of a blankStudent and cast it to a pointer to char.

Let’s see the choice function now:

void choose(char& choice) {
	cin >> choice;
	switch (choice) {
	case 'I' : case 'i' :
		insertStudent();
		break;
	case 'D' : case 'd' :
		deleteStudent();
		break;
	case 'E' : case 'e' :
		editStudent();
		break;
	case 'P' : case 'p' :
		printStudents();
		break;
	case 'S' : case 's' :
		searchStudent();
		break;
	case 'X' : case 'x' :
		return;
	default:
		cout << "\n\tUnknown command!" << endl;
		clearBuffer();
		break;
	}
}

Nothing puzzling here – let’s analyze the clearBuffer():

void clearBuffer() {
	cin.clear();
	cin.ignore(1000,'\n');
}

This is very important to get rid of the cin buffer when a wrong/unknown key is pressed. Try to remove it and see what will be the result. There is one magic constant here – 1000, it should be moved as a global variable. What will happen if the cin buffer is 1001 symbols? Test it.

Now let’s see the insert function:

void insertStudent() {
	fstream file;
	file.open(fileName,ios::in | ios::out);

	Student S;
	bool isValid = true;

	cout << "\n\t Input the student faculty number>";
	do {
		cin >> S.fn;
		if (!cin || S.fn < MIN_FN || S.fn > MAX_FN) {
			clearBuffer();
			cout << "\n\t The number should be between: " << MIN_FN << " and " << MAX_FN << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	cout << "\n\t Input the student name>";
	do {
		char nameBuffer[maxNameSize+maxNameSize];
		bool isNameOk = true;
		cin.ignore();

		cin.getline(nameBuffer,maxNameSize+maxNameSize);
		if (strlen(nameBuffer) > maxNameSize) isNameOk = false;
		else strcpy_s(S.name,strlen(nameBuffer)+1,nameBuffer);

		if (!isNameOk || !cin) {
			clearBuffer();
			cout << "\n\t There is something wrong with the name you have provided!" << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	cout << "\n\t Input the average score of the student>";
	do {
		cin >> S.avgScore;
		if (!cin) {
			clearBuffer();
			cout << "\n\t There is something wrong with the score you have provided!" << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	file.seekp(sizeof(Student)*(S.fn - MIN_FN));
	file.write((const char*)(&S),sizeof(Student));
	
	cout << "\n\t The student was successfully inserted!" << endl;
	file.close();
}

We have implemented extended error checking – we will do that in the other helper functions. Maybe it is good idea to be separated by external function? Why?

void deleteStudent() {
	fstream file;
	file.open(fileName,ios::in | ios::out);

	bool isValid = true;
	int fnBuffer;
	Student blankStudent = {0, " ", 0.0 };

	cout << "\n\t Input the student faculty number to be deleted>";
	do {
		cin >> fnBuffer;
		if (!cin || fnBuffer < MIN_FN || fnBuffer > MAX_FN) {
			clearBuffer();
			cout << "\n\t The number should be between: " << MIN_FN << " and " << MAX_FN << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	file.seekp(sizeof(Student)*(fnBuffer - MIN_FN));
	file.write((const char*)(&blankStudent),sizeof(Student));

	cout << "\n\t The student was successfully deleted!" << endl;
	file.close();
}

The delete function is not so different as approach. You will notice that once entered in this function you are not able to return to the main menu. It can be fixed with few lines or maybe 1 line of code. I leave that to you.

void editStudent() {
	fstream file;
	file.open(fileName,ios::in | ios::out);

	bool isValid = true;
	int fnBuffer;
	double newAvgScore;

	cout << "\n\t Input the student faculty number to be edited>";
	do {
		cin >> fnBuffer;
		if (!cin || fnBuffer < MIN_FN || fnBuffer > MAX_FN) {
			clearBuffer();
			cout << "\n\t The number should be between: " << MIN_FN << " and " << MAX_FN << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	cout << "\n\t You are allowed to edit only the average score!\n";

	cout << "\n\t Input the new student average score>";
	do {
		cin >> newAvgScore;
		if (!cin) {
			clearBuffer();
			cout << "\n\t There is something wrong with the score you have provided!" << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	file.seekp(sizeof(Student)*(fnBuffer - MIN_FN +1) - sizeof(double));
	file.write((const char*)(&newAvgScore),sizeof(double));

	cout << "\n\t The student was successfully edited!" << endl;
	file.close();
}

This is a good example of how the binary files works. The edit function should change the average score of the N-th Student. Let’s see what seekp does – we are moving the put pointer not to the start of the N-th student, but to the start of (N+1)th student: sizeof(Student)*(fnBuffer – MIN_FN +1). If we start writing there, we will overwrite the (N+1)th student details! That’s why we move back with sizeof(double) – now if we start writing, we will overwrite exactly the Nth student’ average score.

void printStudents() {
	ifstream file;
	file.open(fileName,ios::in);
	Student S;

	while (file.read((char*)(&S),sizeof(Student))) {
		if (S.fn >= MIN_FN && S.fn <= MAX_FN) {
			cout << "\n\t FN: " << S.fn << endl;
			cout << "\n\t Name: " << S.name << endl;
			cout << "\n\t Average Score: " << S.avgScore << endl;
			cout << "\n\t --------------------------------------" << endl;
		}
	}

	file.close();
}

Simple print function to print out all the Students in the database.

void searchStudent() {
	ifstream file;
	file.open(fileName,ios::in);
	double avgScoreSearch;
	Student S;
	bool isValid;

	cout << "\n\t Input the average score to be searched>";
	do {
		cin >> avgScoreSearch;
		if (!cin) {
			clearBuffer();
			cout << "\n\t There is something wrong with the score you have provided!" << endl << endl;
			cout << "\n\t >";
			isValid = false;
		}
		else isValid = true;
	} while(!isValid);

	while (file.read((char*)(&S),sizeof(Student))) {
		if (S.fn >= MIN_FN && S.fn <= MAX_FN && S.avgScore == avgScoreSearch) {
			cout << "\n\t FN: " << S.fn << endl;
			cout << "\n\t Name: " << S.name << endl;
			cout << "\n\t Average Score: " << S.avgScore << endl;
			cout << "\n\t --------------------------------------" << endl;
		}
	}

	file.close();
}

This function is an extra. Search function to detect students with the average score passed by the interface.

Play around with the Database – in fact it can be greatly reduced because lot of function blocks are repeated. It is a good exercise of optimization. With few optimizations I reduced the code with more than 35 lines. I am sure with the right motivation you could beat that.

In the next post we are going to solve an exercise helper program.

C++ reading double numbers from file with sequential order

Problem: In a file organized by sequential method you have lot of numbers divided by each other with blank spaces, tabulation symbols or newlines. Write a C++ program that calculates their average.

#include <iostream>
#include <fstream>
using namespace std;

void main() 
{
	ifstream file;
	file.open("test.txt",ios::in);
	
	if (!file) {
		cout << "I am not able to open the file!" << endl;
		return;
	}

	double currentNumber = 0.0;
	double sum = 0.0;
	int count = 0;

	while (file >> currentNumber) {
		sum += currentNumber;
		++count;
	}

	cout << "The average of all numbers is: " << sum/count << endl;
}

If you recall in our previous posts we have defined what is a “blankspaces”. That’s why file >> currentNumber is sufficient command to gather all the numbers in the file.

C++ File Stream – counting the words in a file

Problem: Word is a letter string or number. Find the total count of words in a file organized by the sequential method.

In the following code I have solved the problem without using recursion.

#include <iostream>
#include <fstream>
using namespace std;

bool isLetter(char const &);
bool isDigit(char const &);

void main() 
{
	ifstream file;
	file.open("test.txt",ios::in);
	
	if (!file) {
		cout << "I am not able to open the file!" << endl;
		return;
	}

	int wordsCount = 0;
	char charBuffer;
	bool wordGet_regular = false;
	bool wordGet_number = false;

	while (file) {

		file.get(charBuffer);

		if (wordGet_regular) {
			if (!isLetter(charBuffer))
				wordGet_regular = false;
			else continue;
		}
			if (wordGet_number) {
				if (!isDigit(charBuffer))
					wordGet_number = false;
				else continue;
			}
				if (isLetter(charBuffer)) {
					++wordsCount;
					wordGet_regular = true;
				}
				else
					if (isDigit(charBuffer)) {
						++wordsCount;
						wordGet_number = true;
					}
	}

	cout << "There are total " << wordsCount << " words in this file!" << endl;

}

bool isLetter(char const & c) {
	return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}

bool isDigit(char const & c) {
	return (c >= '0' && c <= '9');
}

let’s input a test file with such content:

jhdsfh
sdfkjsdkfj
3737
dsfkjk2 fdf 444 rrrr 33f4f2f2f2

There are total 17 words in this file!

Now let’s test the code on something bigger!

The Chapter 1 in “The Little Prince” has exactly 521 words.

Let’s test it with the King James version of the bible: http://www.ccel.org/ccel/bible/kjv.txt

There are total 985441 words in this file!

C++ File Streams – few simple manipulations

OLYMPUS DIGITAL CAMERA

Let’s solve one simple problem with file streams.

Problem: Find all the sentences in one file organized by sequential method (a sentence is a string starting with capital letter and ending with ‘.’, ‘!’ or ‘?’).

In order to deal with files we need to include the library fstream. File organized by a sequential method means that every symbol is treated as such – the file is a sequence of ASCII symbols.

There are three major methods to access a file:

1) istream – access the file in read only state – you are not allowed to modify the file! (i = input)
2) ostream – access the file to write in it – you are not able to read it (o = output)
3) fstream – access the file to both read and write – you are allowed to do everything (f = full?)

	ifstream file;
	file.open("test.txt",ios::in);

Here, we have created an object “file” which will handle the file processing. On the second row we have called the method open with two attributes – the file name and the ios flag (in our case we need only to read only – so the flag is “in”)

Here we go with the final realization of the problem:

#include <iostream>
#include <fstream>
using namespace std;

bool isCapitalLetter(char const &);
bool isSign(char const &);

void main() 
{
	ifstream file;
	file.open("test.txt",ios::in);
	
	if (!file) {
		cout << "I am not able to open the file!" << endl;
		return;
	}

	int sentencesCount = 0;
	char charBuffer;
	bool sentenceGet = false;

	while (file) {

		file.get(charBuffer);

		if (sentenceGet) {
			if (isSign(charBuffer)) {
				++sentencesCount;
				sentenceGet = false;
			}
		}

		else 
			if (isCapitalLetter(charBuffer)) 
				sentenceGet = true;
		}

	cout << "There are total " << sentencesCount << " sentences in this file!" << endl;

}

bool isCapitalLetter(char const & c) {
	return (c >= 'A' && c <= 'Z');
}

bool isSign(char const & c) {
	return (c == '.' || c == '!' || c == '?');
}

When dealing with files and as soon as you open it there are two pointers created – put and get. You can specify their starting position – in our case we are using the default starting position – at the beginning. With the command file.get(charBuffer); we get the first character from the file, save it to the char variable charBuffer and the get and put pointers move automatically one position ahead. When the get pointer points to the EOF symbol (“end of file” symbol created at the end of the file) the while(file) trigger is activated the the loop stops.

In the posts ahead we are going to play around with files, so stay tuned. This is just a surface scratch.

Oh, forgot to test the code, let’s test it!

First, you need to create a test.txt in the directory your program is.

I have typed this in the file:

this is just a test file.

OK! Let’s right some symbols…
askfjjfsdhgsdhjhwuhufh3ufh3u?
John? Are you here? Hey, Doe!

Let’s see the result:

There are total 5 sentences in this file!

All looking good! Now let’s see how many sentences we have in this post (from the beginning of it till exactly the end of this scope plus one(to include the dot too)).

There are total 29 sentences in this file!

Not so bad, not so bad …

C++ stream manipulator – int width(int)

We will leave the Objects and Classes for a while. In the next posts I want to discuss streams through some short code fragments. Let’s analyze this code:

schubler

#include <iostream>
using namespace std;

void main() 
{
	cout << "Please input a sentence to be manipulated: ";
	char str[50];
	while (cin >> str) {
		cout.width(5);
		cout << str << endl;
	}
}

As you know the keyboard itself is a stream and as such we can manipulate the stream in the go. Let’s say we input the sentence: Hi there John Doe, this is just a test! Let’s see what the output will be:

Hi
there
John
Doe,
this
is
just
a
test!

As you can see the width() manipulator is redefining the width of the output frame – in our example the width is 5. You should pay attention that this width redefinition will be triggered just once (if triggered at all) and then the stream goes back to its default state. That’s why we put the cout.width() in the loop.

If you pay attention the aligning of the field is RIGHT. Furthermore I don’t think this sentence is revealing all the behavior of the width operator. Why? The words in the sentence were five or less letters! Let’s put another sentence and see the output:

Congratulations, this is your second test!

Congratulations,
this
is
your
second
test!

As you can see the string is not cut. That’s good to know and correct to be implemented. Now, what about calling width() on the input stream? What will cin.width(5) for example do? Let’s test!

We will use the first sentence again : Hi there John Doe, this is just a test!

Let’s modify the code fragment a bit:

#include <iostream>
using namespace std;

void main() 
{
	cout << "Please input a sentence to be manipulated: ";
	char str[50];
	while (cin >> str) {
		cin.width(5);
		cout.width(5);
		cout << str << endl;
	}
}

And the result is:

Hi
ther
e
John
Doe,
this
is
just
a
test
!

Now, let’s analyze what is going on. We defined cin.width(5); which means read/get the first 5 symbols from the stream and stop when it reaches a whitespace (not blankspace, but whitespace – blankspace is a whitespace, but whitespace is not a blankspace) or when we exceeded the size of the attribute of the width operator. OK, we have:

Hi(w)there(w)John(w)Doe,(w)this(w)is(w)just(w)a(w)test! , where by (w) we defined a whitespace!

So, the first cin.width(5) will save Hi on our char array (string) str.
The second cin.width(5) will start from t (there) and will read first symbol – t, second – h, third – e, forth – r … and suddenly stops. Why is that? That’s because when dealing with the width() operator it saves the last character for the end of the string (new line = ‘\n’).

OK, so far – so good. Now let’s see the third cin.width(5). Before analyze the output let’s see what we have read from the stream so far:

Hi(w)there(w)John(w)Doe,(w)this(w)is(w)just(w)a(w)test!

Now, that makes more sense why in the third row we have only one “e”, right? Right after the char “e” the cin reaches a whitespace (in this example – space) and the cin exits.

With width() operator we can read/write a stream by packets – which makes the whole experience a little bit more comfortable.

C++ Class Inheritance : some observations and database realization

Problem: We have a base class Worker which defines a name of the worker plus the payment he/she generates for one hour. Furthermore we have two inherited classes – HourlyWorker and SalariedWorker. For each inherited class we have two private-members variables: how many hours the worker worked in the current week plus the type of job position of the worker. The hourly worker total payment is defined by the total hours he/she worked. If the total hours are below or equal to 40 hours there are no changes. If the total hours are above 40 hours and lower or equal to 60 hours, the current worker will receive 1.5 times more than the initial payment for one hour (defined in the Worker class). If the total hours are above 60 hours, the current worker will receive 2 times more than the initial payment. The SalariedWorker will receive the payment he/she generates for one hour multiplied by 40 (no matter how much time he/she worked). You should implement this database using Class Inheritance (you should use the rule of Four). Create two arrays which holds the two types of workers (hourly and salaried). Calculate and print out the salary of each worker.

inheritance

Let’s first create the header file. We will include the definitions of all the Classes inside. Let’s first take a look of it:

#ifndef DBWORKER_H_
#define DBWORKER_H_

class Worker {
public:
	Worker();
	~Worker();
	Worker(Worker const&);
	Worker(char* const, double const);
	Worker& operator=(Worker const&);
	double getOneHourPayment() const;
private:
	void copyWorker(Worker const&);
	char* name;
	double oneHourPayment;
};

class HourlyWorker : public Worker {
public:
	HourlyWorker();
	~HourlyWorker();
	HourlyWorker(HourlyWorker const&);
	HourlyWorker(char* const, double const,char* const, int const);
	HourlyWorker& operator=(HourlyWorker const&);
	double moneyToBePaid() const;
private:
	int totalWeekHours;
	char* typeOfWork;
	void copyHourlyWorker(HourlyWorker const&);
};

class SalariedWorker : public Worker {
public:
	SalariedWorker();
	~SalariedWorker();
	SalariedWorker(SalariedWorker const&);
	SalariedWorker(char* const, double const,char* const, int const);
	SalariedWorker& operator=(SalariedWorker const&);
	double moneyToBePaid() const;
private:
	int totalWeekHours;
	char* typeOfWork;
	void copyHourlyWorker(SalariedWorker const&);
};

#endif

As you can see there are no such differences when using not-derived classes. Maybe you have noticed this definition: class HourlyWorker : public Worker
With this notation we tell the compiler that the class HourlyWorker will inherit the class Worker with public behavior – this means the private members and methods of class Worker will be private members and methods to class HourlyWorker. The public members and methods of Class Worker will be public members and methods to class HourlyWorker. In fact – there is one other scope we are allowed to use: it is called protected but we are not going to discuss it in the current post.

Now let’s create a file in the project Worker.cpp

#include <iostream>
#include <string>
#include "DBWorker.h"
using namespace std;

Worker::Worker() {
	name = NULL;
	oneHourPayment = 0.0;
}

Worker::~Worker() {
	delete [] name;
	name = NULL;
}

Worker::Worker(Worker const& W) {
	copyWorker(W);
}

Worker::Worker(char* const tempName,double const oneHour) {
	if (tempName == NULL) name = NULL;
	else {
		name = new char[strlen(tempName)+1];
		strcpy_s(name,strlen(tempName)+1,tempName);
	}
	oneHourPayment = oneHour;
}

void Worker::copyWorker(Worker const& W) {
	if (!name) delete [] name;
	name = new char[strlen(W.name)+1];
	strcpy_s(name,strlen(W.name)+1,W.name);
	oneHourPayment = W.oneHourPayment;
}

Worker& Worker::operator=(Worker const& W) {
	if (this != &W) {
		delete [] name;
		copyWorker(W);
	}
	else
		return *this;
}

double Worker::getOneHourPayment() const {
	return oneHourPayment;
}

As you can see there is nothing to be puzzled from here. Now let’s analyze the definitions of HourlyWorker.cpp

#include <iostream>
#include <string>
#include "DBWorker.h"
using namespace std;

HourlyWorker::HourlyWorker() : Worker() {
	totalWeekHours = 0;
	typeOfWork = NULL;
}

HourlyWorker::~HourlyWorker() {
	delete [] typeOfWork;
	typeOfWork = NULL;
}

HourlyWorker::HourlyWorker(HourlyWorker const & W) : Worker(W) {
	copyHourlyWorker(W);
}

void HourlyWorker::copyHourlyWorker(HourlyWorker const& W) {
	if (!typeOfWork) delete [] typeOfWork;
	typeOfWork = new char[strlen(W.typeOfWork)+1];
	strcpy_s(typeOfWork,strlen(W.typeOfWork)+1,W.typeOfWork);
	totalWeekHours = W.totalWeekHours;
}

HourlyWorker::HourlyWorker(char* const workerName, double const salary, char* const typeWork, int const hours) : Worker(workerName,salary) {
	if (typeWork == NULL) typeOfWork = NULL;
	else {
		typeOfWork = new char[strlen(typeWork)+1];
		strcpy_s(typeOfWork,strlen(typeWork)+1,typeWork);
	}
	totalWeekHours = hours;
}

HourlyWorker& HourlyWorker::operator=(HourlyWorker const& W) {
	Worker::operator=(W);
	if (this != &W) {
		delete [] typeOfWork;
		copyHourlyWorker(W);
	}
	else
		return *this;
}

double HourlyWorker::moneyToBePaid() const {
	return (totalWeekHours <= 40) ? totalWeekHours*getOneHourPayment() :
		   (totalWeekHours <= 60  ? totalWeekHours*getOneHourPayment()*1.5 :
									totalWeekHours*getOneHourPayment()*2);
}

We are going to discuss this realization with details. Let’s first analyze the default constructor:

HourlyWorker::HourlyWorker() : Worker()

As your intuition tells you: with this notations we are calling the default constructor of the class Worker within the default constructor of the class HourlyWorker.

There are no extra notations we have to implement in the destructor!

HourlyWorker::HourlyWorker(HourlyWorker const & W) : Worker(W)

Again we are calling the copy constructor of the base Class withing the copy constructor of the derived class. This is a MUST have notation when dealing with dynamic variables (otherwise the default copy constructor will be used and this will cause a real mess in the Heap)

HourlyWorker::HourlyWorker(char* const workerName, double const salary, char* const typeWork, int const hours) : Worker(workerName,salary)

We are defining a constructor with four parameters here with a good reason (with no class inheritance a constructor with two parameters will be enough, because we have only two private members). We are implementing such construction, because we need to supply to the constructor of the base class Worker the two private members. We are doing that with the notation : Worker(workerName,salary).

Worker::operator=(W);

You will see this within the scope of the assign operator. This cute notation calls the default assign operator of the base class Worker! Easy as that!

We will implement the other cpp file using the same approach (just minor differences in the logic, not the syntax)

SalariedWorker.cpp

#include <iostream>
#include <string>
#include "DBWorker.h"
using namespace std;

SalariedWorker::SalariedWorker() : Worker() {
	totalWeekHours = 0;
	typeOfWork = NULL;
}

SalariedWorker::~SalariedWorker() {
	delete [] typeOfWork;
	typeOfWork = NULL;
}

SalariedWorker::SalariedWorker(SalariedWorker const & W) : Worker(W) {
	copyHourlyWorker(W);
}

void SalariedWorker::copyHourlyWorker(SalariedWorker const& W) {
	if (!typeOfWork) delete [] typeOfWork;
	typeOfWork = new char[strlen(W.typeOfWork)+1];
	strcpy_s(typeOfWork,strlen(W.typeOfWork)+1,W.typeOfWork);
	totalWeekHours = W.totalWeekHours;
}

SalariedWorker::SalariedWorker(char* const workerName, double const salary, char* const typeWork, int const hours) : Worker(workerName,salary) {
	if (typeWork == NULL) typeOfWork = NULL;
	else {
		typeOfWork = new char[strlen(typeWork)+1];
		strcpy_s(typeOfWork,strlen(typeWork)+1,typeWork);
	}
	totalWeekHours = hours;
}

SalariedWorker& SalariedWorker::operator=(SalariedWorker const& W) {
	Worker::operator=(W);
	if (this != &W) {
		delete [] typeOfWork;
		copyHourlyWorker(W);
	}
	else
		return *this;
}

double SalariedWorker::moneyToBePaid() const {
	return 40*getOneHourPayment();
}

OK, we are ready to go! Let’s play with the interface now:

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "DBWorker.h"

using namespace std;

int main()
{
	srand(time(0));
	HourlyWorker HWS[3];
	SalariedWorker SWS[3];
	HWS[0] = HourlyWorker("John Doe",rand()%10,"Administrator",rand()%200);
	HWS[1] = HourlyWorker("Pit Doe",rand()%10,"Lawyer",rand()%200);
	HWS[2] = HourlyWorker("Martin Jr",rand()%10,"Food Control",rand()%200);
	SWS[0] = SalariedWorker("Scooby Doo",rand()%10,"Librarian",rand()%200);
	SWS[1] = SalariedWorker("Mickey Mouse",rand()%10,"Math Teacher",rand()%200);
	SWS[2] = SalariedWorker("Donald Duck",rand()%10,"Primary Teacher",rand()%200);

	for (int i = 0; i < 3; ++i) {
		cout << HWS[i].moneyToBePaid() << endl;
		cout << SWS[i].moneyToBePaid() << endl;
	}

	return 0;
}

Please pay attention that this is just the basics of the Class Inheritance!

C++ Binary Ordered Tree – Template

We already know what is a Binary Tree. But what is Ordered? We will define Binary Ordered Tree as a Binary Tree in which each node value is greater than all the node values in the Left Sub Tree and it is lesser than all the node values in the Right Sub Tree.

As you can see in the diagram above – all the nodes values (the number withing the circles) fulfill the definition, so this is a Binary Ordered Tree. In fact – there are no so much difference than regular Binary Tree when it comes to basic definitions. Let’s start with the headers:

#ifndef BINORDTREE_H_
#define BINORDTREE_H_

template <class T>
struct node {
	T root;
	node* leftTree;
	node* rightTree;
};

template <class T>
class BinOrdTree{
public:
	BinOrdTree();
	~BinOrdTree();
	BinOrdTree(const BinOrdTree&);
	BinOrdTree& operator=(const BinOrdTree&);
	void createTree();
	void print() const;
	bool empty() const;
	T getRoot() const;
	BinOrdTree getLeftTree() const;
	BinOrdTree getRightTree() const;
	void Create3 (T const &,BinOrdTree const &,BinOrdTree const &);
	void addNode(T const &);
	void removeMinElem(T &, BinOrdTree<T> &) const;
	void deleteElem(T const & x);
private:
	node<T>* tree;
	void delBinTree(node<T>* &);
	void copy (node<T>* &, node<T> const * const &) const;
	void copyTree (const BinOrdTree&);
	void pr(node<T> const * const &) const;
	void addElem(node<T> * &, T const &) const;
};

#endif

The constructors/destructors is the same as the previous posts – nothing new”

template <class T>
BinOrdTree<T>::BinOrdTree() {
	tree = NULL;
}

template <class T>
BinOrdTree<T>::~BinOrdTree() {
	delBinTree(tree);
}

template <class T>
void BinOrdTree<T>::delBinTree(node<T>* &startTree) {
  if (!startTree) return;
	else {
		delBinTree(startTree->leftTree);
		delBinTree(startTree->rightTree);
		delete startTree;
		startTree = NULL;
	}
}

template <class T>
void BinOrdTree<T>::copy(node<T>* & pos, node<T> const * const & hostNode) const {
	pos = NULL;
	if (hostNode) {
		pos = new node<T>;
		pos->root = hostNode->root;
		copy(pos->leftTree,hostNode->leftTree);
		copy(pos->rightTree,hostNode->rightTree);
	}
}

template <class T>
void BinOrdTree<T>::copyTree(const BinOrdTree<T>& hostTree) {
	copy(tree,hostTree.tree);
}

template <class T>
BinOrdTree<T>::BinOrdTree(const BinOrdTree& hostTree) {
	copyTree(hostTree);
}

template <class T>
BinOrdTree<T>& BinOrdTree<T>::operator=(const BinOrdTree& hostTree) {
	if (this != &hostTree) {
		delBinTree(tree);
		copyTree(hostTree);
	}
	else 
		return *this;
}

template <class T>
void BinOrdTree<T>::Create3(T const & value, 
						 BinOrdTree<T> const  & LT,
						 BinOrdTree<T> const  & RT) {
	if (tree) delBinTree(tree);
	tree = new node<T>;
	tree->root = value;
	copy(tree->leftTree,LT.tree);
	copy(tree->rightTree,RT.tree);
}

Now about creating a Binary Ordered Tree .. We need to push the elements one by one and find it the correct place. Imagine we push an element from the main root of the Binary Ordered Tree. We need to check if the value is great or less than the value of the main root. If the value for example is greater – we need to push the element to the Right Sub Tree of the main tree and then continue this procedure until we find the best place. Let’s implement this function to our class:

template <class T>
void BinOrdTree<T>::createTree() {
	BinOrdTree<T> BOT;
	T value;
	char buffer;
	cout << "Input an element? y/n: ";
	cin >> buffer;
	if (buffer != 'y') return;
	cout << "Please input the value: ";
	cin >> value;
	addNode(value);
	createTree();
}

template <class T>
void BinOrdTree<T>::print() const {
	pr(tree);
	cout << endl;
}

template <class T>
void BinOrdTree<T>::pr(node<T> const * const & current) const {
	if (current) {
		cout << current -> root << " | ";
		pr(current->leftTree);
		pr(current->rightTree);
	}
}

template <class T>
bool BinOrdTree<T>::empty() const {
	return tree == NULL;
}

template <class T>
T BinOrdTree<T>::getRoot() const {
	return tree->root;
}

template <class T>
BinOrdTree<T> BinOrdTree<T>::getLeftTree() const {
	BinOrdTree<T> CT;
	copy(CT.tree,tree->leftTree);
	return CT;
}

template <class T>
BinOrdTree<T> BinOrdTree<T>::getRightTree() const {
	BinOrdTree<T> CT;
	copy(CT.tree,tree->rightTree);
	return CT;
}

template <class T>
void BinOrdTree<T>::addNode(T const & x){
	addElem(tree,x);
}

template <class T>
void BinOrdTree<T>::addElem(node<T> * & BOT, T const & x) const {
	if (!BOT) {
		BOT = new node<T>;
		BOT->leftTree = NULL;
		BOT->rightTree = NULL;
		BOT->root = x;
	}
	else {
		if (x < BOT->root) addElem(BOT->leftTree,x);
		else addElem(BOT->rightTree,x);
	}
}

Again using recursion will be the best approach. We wrap our words in code and we are now able to push or add elements on a Binary Ordered Tree. What about pop or delete elements? Now the things got little bit more complicated… The thing is – when you delete an element of a Binary Ordered Tree you can totally change its structure. That’s why in case the element we want to delete is the root itself – we will look for the minimum element in the Right Sub Tree and will use it as the new root of the tree (with Left Sub Tree – the original Left Sub Tree and Right Sub Tree the original Right Sub Tree without the minimum element used as the current root).The next function is doing this:

template <class T>
void BinOrdTree<T>::removeMinElem(T & x, BinOrdTree<T> & BOT) const {
	T a = getRoot();
	if (getLeftTree().empty()) {
		x = a;
		BOT = getRightTree();
	}
	else {
		BinOrdTree saveRightTree = getRightTree();
		BinOrdTree constructLeftTree = 
			getLeftTree();
		constructLeftTree.removeMinElem(x,constructLeftTree);
		BOT.Create3(a,constructLeftTree,saveRightTree);
	}
}

It will just find a minimum element of a given tree, save it to x and then the function will save to BOT the constructed Binary Ordered Tree with the minimum element missing. Using this very helpful function we can now construct the basic function for deleting nodes.

template <class T>
void BinOrdTree<T>::deleteElem(T const & x) {
	if (empty()) {
		cout << "No such element " << x << "!" << endl;
		return;
	}
	if (x == getRoot()) {
		T minTemp;
		BinOrdTree<T> treeTemp;
		getRightTree().removeMinElem(minTemp,treeTemp);
		Create3(minTemp,getLeftTree(),treeTemp);
	}
	else {
		if (x < getRoot()) {
			BinOrdTree<T> treeTemp;
			treeTemp = getLeftTree();
			treeTemp.deleteElem(x);
			Create3(getRoot(),treeTemp,getRightTree());
		}
		else {
			BinOrdTree<T> treeTemp;
			treeTemp = getRightTree();
			treeTemp.deleteElem(x);
			Create3(getRoot(),getLeftTree(),treeTemp);
		}
	}
}

Now we have a fully loaded Template of Binary Ordered Tree!

C++ Binary Tree – Template and Problem Solving

Now we are going to reveal one of the most interesting structures so far – the Binary Tree. The Binary Tree main element is a structure with a value plus two pointers – one pointing to a left element and one pointing to a right element. The value of the first element is called root. The left element pointer is pointing to the so called – Left Tree (this includes not only the element the root is pointing but all the sub-elements as well). The right element pointer is pointing to the so called – Right Tree. You can inspect the diagram below to get the idea clarified.

As you can see in the following example 2 is the main element of our Binary Tree. We define it as the root. 2 is pointing to two sub-roots – one to the left starting with 7 defined as Left Tree and one to the right starting with 5 defined as Right Tree. And again 7 has one Left Tree starting with 2 and one Right Tree starting with 6.

This abstraction is really handy when working with more demanding problems. But let’s start the implementation. Like we did in the previous posts – let’s start with the headers:

#ifndef BINTREE_H_
#define BINTREE_H_

template <class T>
struct node {
	T root;
	node* leftTree;
	node* rightTree;
};

template <class T>
class BinTree{
public:
	BinTree();
	~BinTree();
	BinTree(const BinTree&);
	BinTree& operator=(const BinTree&);
	void createMain();
	void print() const;
	bool empty() const;
	T getRoot() const;
	BinTree getLeftTree() const;
	BinTree getRightTree() const;
	void Create3 (T const &,BinTree const &,BinTree const &);
private:
	node<T>* tree;
	void delBinTree(node<T>* &);
	void copy (node<T>* &, node<T> const * const &) const;
	void copyTree (const BinTree&);
	void pr(node<T> const * const &) const;
	void createTree(node<T> * &);
};

#endif

Again we are not going to discuss in details the big four or the rule of four – default constructor, destructor, copy constructor and assign operator or overload operator. Their realization is not different from the examples we did in the previous posts.

template <class T>
BinTree<T>::BinTree() {
	tree = NULL;
}

template <class T>
BinTree<T>::~BinTree() {
	delBinTree(tree);
}

template <class T>
void BinTree<T>::delBinTree(node<T>* &startTree) {
  if (!startTree) return;
	else {
		delBinTree(startTree->leftTree);
		delBinTree(startTree->rightTree);
		delete startTree;
		startTree = NULL;
	}
}

template <class T>
void BinTree<T>::copy(node<T>* & pos, node<T> const * const & hostNode) const {
	pos = NULL;
	if (hostNode) {
		pos = new node<T>;
		pos->root = hostNode->root;
		copy(pos->leftTree,hostNode->leftTree);
		copy(pos->rightTree,hostNode->rightTree);
	}
}

template <class T>
void BinTree<T>::copyTree(const BinTree<T>& hostTree) {
	copy(tree,hostTree.tree);
}

template <class T>
BinTree<T>::BinTree(const BinTree& hostTree) {
	copyTree(hostTree);
}

template <class T>
BinTree<T>& BinTree<T>::operator=(const BinTree& hostTree) {
	if (this != &hostTree) {
		delBinTree(tree);
		copyTree(hostTree);
	}
	else 
		return *this;
}

Several things should be noticed here. As you can see we are using lot of recursion. In fact crawling a Binary Tree is hardly done without proper recursion methods. Let’s examine further the copy constructor helper function:
void BinTree::copy(node* & pos, node const * const & hostNode) const

Why do we use this notation -> copy(node* & pos ?
Because recursion is involved we want to keep it right. The function is calling itself later in its scope by calling copy(pos->leftTree,hostNode->leftTree); In order to make the things right we need to add the deference symbol &, otherwise our syntax will be wrong. pos->leftTree is node* &.

Now about the second attribute – node const * const & hostNode. We want to keep the source node intact. If you are puzzled why do we implement so many const in the attribute – you better take a look on the previous post. The const after the function is stating that the current function must not change this.

Now let’s continue with the other implementations:

template <class T>
void BinTree<T>::Create3(T const & value, 
						 BinTree<T> const  & LT,
						 BinTree<T> const  & RT) {
	if (tree) delBinTree(tree);
	tree = new node<T>;
	tree->root = value;
	copy(tree->leftTree,LT.tree);
	copy(tree->rightTree,RT.tree);
}

template <class T>
void BinTree<T>::createTree(node<T>* &pos) {
	T x;
	char choice;
	cout << "root= ";
	cin >> x;
	pos = new node<T>;
	pos->root = x;
	pos->leftTree = NULL;
	pos->rightTree = NULL;
	cout << "Does " << x << " have a left tree? y/n: ";
	cin >> choice;
	if (choice == 'y') createTree(pos->leftTree);
	cout << "Does " << x << " have a right tree? y/n: ";
	cin >> choice;
	if (choice == 'y') createTree(pos->rightTree);
}

Create3() function is an interface function – helping the user to construct Binary Trees by supplying the root, the Left Tree and the Right Tree. Easy as that. On the other hand – createTree() function is an interaction function. The user is going to construct the whole tree step by step (in the Create3() function the user should supply already constructed trees – the Left Tree and the Right Tree).As you can observe recursion is everywhere.

template <class T>
void BinTree<T>::createMain() {
	createTree(tree);
}

template <class T>
void BinTree<T>::print() const {
	pr(tree);
	cout << endl;
}

template <class T>
void BinTree<T>::pr(node<T> const * const & current) const {
	if (current) {
		cout << current -> root << " | ";
		pr(current->leftTree);
		pr(current->rightTree);
	}
}

template <class T>
bool BinTree<T>::empty() const {
	return tree == NULL;
}

template <class T>
T BinTree<T>::getRoot() const {
	return tree->root;
}

template <class T>
BinTree<T> BinTree<T>::getLeftTree() const {
	BinTree<T> CT;
	copy(CT.tree,tree->leftTree);
	return CT;
}

template <class T>
BinTree<T> BinTree<T>::getRightTree() const {
	BinTree<T> CT;
	copy(CT.tree,tree->rightTree);
	return CT;
}

This function are clear and plain. Just adding to the interface a must-have functions. I believe we are ready to test.

int main() 
{
        typedef BinTree<int> IntBinTree;
	IntBinTree T1;
	T1.createMain();
	cout << T1.getRoot() << endl;
	T1.getLeftTree().print();
	T1.getRightTree().print();
	IntBinTree T2;
	T2.Create3(T1.getRoot(), T1.getRightTree(), T1.getLeftTree());
	T2.print();
	return 0;
}

All is looking right so far. Play around with the interface and we are going to solve few problems. By the way – if you are lazy to construct tree over and over again – on the first prompt you can just paste in the console:

10 y 11 y 13 n n y 14 n n y 12 y 15 n n y 16 n n

As you know the cin operator is reading those values one by one, when divided by “whitespace” (space, return, tabulation symbols, etc.)

OK, now let’s play around.

Problem 1: Write down a function which increase all the elements of a Binary Tree by some value.

Can you guess what method we are going to use in order to solve that problem? Yes! Recursion!

IntBinTree totalAddElem (IntBinTree& BT, int x) {
	IntBinTree BT_buffer;
	if (BT.empty()) return BT_buffer;
	BT_buffer.Create3(BT.getRoot() + x, 
					  totalAddElem(BT.getLeftTree(),x), 
					  totalAddElem(BT.getRightTree(),x));
	return BT_buffer;
}

Problem 2: Write down a function which replace all the elements’ values by their factorial.

IntBinTree totalFact(IntBinTree& BT) {
	IntBinTree BT_buffer;
	if (BT.empty()) return BT_buffer;
	BT_buffer.Create3(fact(BT.getRoot()),
		totalFact(BT.getLeftTree()),
		totalFact(BT.getRightTree()));
	return BT_buffer;
}

int fact(int x) {
	if (x == 1 || x == 0) return 1;
	else return x*fact(x-1);
}

Here we go, easy as that – recursion and recursion.

Problem 3: Write down a function to check if two Binary Trees are equal

template <class T>
bool isEqual(BinTree<T> const &LT, BinTree<T> const &RT) {
	if (LT.empty() && RT.empty()) return true;
	if ((LT.empty()^RT.empty()) || LT.getRoot() != RT.getRoot()) return false;
	return isEqual(LT.getLeftTree(),RT.getLeftTree()) &&
		isEqual(LT.getRightTree(),RT.getRightTree());
}

In the above code the symbol ^ is exclusive OR. Google it if you never heard it – sometimes it can save you several lines of code. Now let’s test all the solutions:

#include <iostream>
#include "BinTree.cpp"
using namespace std;
typedef BinTree<int> IntBinTree;

IntBinTree totalAddElem (IntBinTree&, int);
IntBinTree totalFact(IntBinTree&);
int fact(int);


int main() 
{
	IntBinTree T1;
	T1.createMain();
	cout << T1.getRoot() << endl;
	T1.getLeftTree().print();
	T1.getRightTree().print();
	IntBinTree T2;
	T2.Create3(T1.getRoot(), T1.getRightTree(), T1.getLeftTree());
	T2.print();
	T2 = totalAddElem(T2,10);
	T2.print();
	T2 = totalAddElem(T2,-20);
	T2.print();
	T2 = totalFact(T2);
	T2.print();
	cout << isEqual(T2,T1) << endl;
	cout << isEqual(T2,T2) << endl;
	return 0;
}

IntBinTree totalAddElem (IntBinTree& BT, int x) {
	IntBinTree BT_buffer;
	if (BT.empty()) return BT_buffer;
	BT_buffer.Create3(BT.getRoot() + x, 
					  totalAddElem(BT.getLeftTree(),x), 
					  totalAddElem(BT.getRightTree(),x));
	return BT_buffer;
}

IntBinTree totalFact(IntBinTree& BT) {
	IntBinTree BT_buffer;
	if (BT.empty()) return BT_buffer;
	BT_buffer.Create3(fact(BT.getRoot()),
		totalFact(BT.getLeftTree()),
		totalFact(BT.getRightTree()));
	return BT_buffer;
}

int fact(int x) {
	if (x == 1 || x == 0) return 1;
	else return x*fact(x-1);
}

All looking OK. Maybe you have noticed that we didn’t provide delete and add member-functions? We will do that in the next post – Binary Tree is not very efficient to be worked with, that’s why we are going to talk about Binary Ordered Trees. But first play around with the regular Binary Trees…

C++ const – left or right?

NoChange

As you have seen in the previous posts we have used const in the beginning of each parameter (when needed). I am sure you will see different notations too – stating that an integer for example is constant, but the const notation is on the right side of the parameter. Is there any difference between ex.1 and ex.2?

const int 5; //ex.1
int const 5; //ex.2

No, there is no difference between these rows. Now let’s took another example – is there any difference between ex.3 and ex.4?

const int * 5; //ex.3
int * const 5; //ex.4

Oops, now what is constant? The pointer or the pointer value?

From now on we should implement better notation in order to avoid such issues. It appears that const is affecting the closest-left type (or if no left-type the first right-type). Let’s see what is going on with ex.1 -> we do not have adjacent left-type so we are looking for the first right-type. That’s why const int 5; = int cost 5;

Now what about ex.3? We have const int* 5; There is no left-type so we are looking for the first right-type – as it appears it is int, so const int* 5; = int const * 5;

In the ex.4 the const is referring to the first left-type which is *. So, ex.3 is telling the compiler “define NON-constant pointer with CONSTANT integer value”, when ex.4 is telling the compiler “define CONSTANT pointer with NON-constant integer value”. Let’s do some testing:

int Arr[2] = {1, 2};
	int const * p1 = Arr;
	int * const p2 = Arr;
	*p1 = 4;
	*p2 = 4;

Let’s try to compile and OoOops –> error C3892: ‘p1’ : you cannot assign to a variable that is const (that happens because we tried to change the “int” which is protected by const!)

Let’s try another example now:

int Arr[2] = {1, 2};
	int const * p1 = Arr;
	int * const p2 = Arr;
	p2 = p1; //the compiler should crash here

OoOoops ->error C2440: ‘=’ : cannot convert from ‘const int *’ to ‘int *const ‘ (that happens because we tried to change the constant pointer and force it to point to another value).

Now some of you may ask – can we combine ex.3 and ex.4? What if we want constant pointer and constant pointed value at the same time? Here we go:

int Arr[2] = {1, 2};
	int const * const p1 = Arr;
	*p1 = 1;    //nope!
	p1 = NULL;  //double nope!

Error 1 error C3892: ‘p1’ : you cannot assign to a variable that is const
Error 2 error C3892: ‘p1’ : you cannot assign to a variable that is const

Hope I saved you some time if you messed up with the const notation…

C++ DLList or Double Linked List Template and Problem Solving

Doubly-linked-list.svg

The last list we are going to discuss is Double Linked List. In fact it’s the same as ordinary Linked List (Linked List with one connection), but we have two pointers on each elem – one pointing to the previous elem in the List and one pointing to the next elem in the List. The default implementation consist of only one function to include an elem – a function to include an elem to the end of the Double Linked List.

The other interesting difference from the single Linked List – we have two iterators here. One iterator starting from the begin of the list and moving forward and one iterator starting from the end of the list and moving backward. Let’s see the header now:

#ifndef DLLIST_H_
#define DLLIST_H_

template <class T>
struct elem {
	T inf;
	elem* prev;
	elem* next;
};

template <class T>
class DLList {
public:
	DLList();
	~DLList();
	DLList(const DLList&);
	DLList& operator=(const DLList&);
	void ToEnd(const T&);
	void IterStart(elem<T>* = NULL);
	void IterEnd(elem<T>* = NULL);
	elem<T>* IterPrev();
	elem<T>* IterNext();
	void print() const;
	void print_reverse() const;
	bool DeleteElem(elem<T>*,T&);
private:
	elem<T>* start;
	elem<T>* end;
	elem<T>* currentS;
	elem<T>* currentE;
	void delDLList();
	void copyDLList(const DLList<T>&);
};

#endif 

Here we go with the definitions (I will include the whole file this time)

#include <iostream>
#include "DLList.h"
using namespace std;

template <class T>
DLList<T>::DLList() {
	start = NULL; 
	end = NULL;
	currentS = NULL;
	currentE = NULL;
}

template <class T>
DLList<T>::~DLList() {
	delDLList();
}

template <class T>
DLList<T>::DLList(const DLList& DLL) {
	copyDLList(DLL);
}

template <class T>
void DLList<T>::delDLList() {
	elem<T>* iter = start;
	elem<T>* destroyer ;
	while (iter) {
		destroyer = iter;
		iter = iter->next;
		delete destroyer;
	}
	end = NULL;
	start = NULL;
}

template <class T>
void DLList<T>::copyDLList(const DLList& DLL) {
	elem<T>* right_iter = DLL.start;
	if (!right_iter) {
		start = NULL;
		end = NULL;
	}
	else {
		while (right_iter) {
			ToEnd(right_iter->inf);
			right_iter = right_iter->next;
		}
	}
}

template <class T>
DLList<T>& DLList<T>::operator=(const DLList& DLL) {
	if (this != &DLL) {
		delDLList();
		copyDLList(DLL);
	}
	else
		return *this;
}

template <class T>
void DLList<T>::ToEnd(const T& var) {
	elem<T>* bblock = new elem<T>;
	bblock->inf = var;
	if (end == NULL) {
		bblock->next = NULL;
		bblock->prev = NULL;
		start = end = bblock;
	}
	else {
		end->next = bblock;
		bblock->prev = end;
		bblock->next = NULL;
		end = bblock;
	}
}

template <class T>
void DLList<T>::IterStart(elem<T>* pos = NULL) {
	if (pos) currentS = pos;
	else currentS = start;
}

template <class T>
void DLList<T>::IterEnd(elem<T>* pos = NULL) {
	if (pos) currentE = pos;
	else currentE = end;
}

template <class T>
elem<T>* DLList<T>::IterPrev() {
	elem<T>* p = currentE;
	if (currentE) currentE = currentE->prev;
	return p;
}

template <class T>
elem<T>* DLList<T>::IterNext() {
	elem<T>* p = currentS;
	if (currentS) currentS = currentS->next;
	return p;
}

template <class T>
void DLList<T>::print() const {
	elem<T>* iter = start;
	if (!iter) {
		cout << "The DLList is empty!" << endl;
		return;
	}
	else {
		while (iter) {
			cout << iter->inf << " | ";
			iter = iter->next;
		}
	}
  cout << endl;
}

template <class T>
void DLList<T>::print_reverse() const {
	elem<T>* iter = end;
	if (!iter) {
		cout << "The DLList is empty!" << endl;
		return;
	}
	else {
		while (iter) {
			cout << iter->inf << " | ";
			iter = iter->prev;
		}
	}
}

template <class T>
bool DLList<T>::DeleteElem(elem<T>* pos,T& var) {
	if (start == NULL) return false;
	var = pos->inf;
	if (pos == start && pos == end) {
		start = NULL;
		end = NULL;
	}
	else {
		if (pos == start) {
			start = pos->next;
			start->prev = NULL;
		}

		if (pos == end) {
			end = end->prev;
			end->next = NULL;
		}
		
		delete pos;
	}
	return true;
}

As I noted before – there is plenty of space to optimize this methods (I am sure some bugs can be found too!). But it will do the work, let’s test the main methods now:

int main() 
{
	IntDLList DLL;
	DLL.print();
	DLL.print_reverse();
	DLL.ToEnd(1);
	DLL.IterStart();
	int x = 0;
	DLL.DeleteElem(DLL.IterNext(),x);
	IntDLList DLL2;
	DLL2 = DLL;
	DLL2.print();
	return 0;
}

Yeahp, all is looking OK. The constructors are working, the copy constructor is OK, and the most important – the destructor cleans the HEAP. Now, let’s solve one task.

Problem: You have a Double Linked List with 10 elements. Let’s define the elements as a1,a2, ..,a10. Write a program which will calculate S = a1*a10 + … + a5*a6

The following code will do that:

#include <iostream>
#include "DLList.cpp"
using namespace std;
typedef DLList<int> IntDLList;

int SymmetricSum(DLList<int>&, int);

int main() 
{
	IntDLList DLL;
	for (int i = 0; i < 10; ++i) 
		DLL.ToEnd(i);
	DLL.print();
	cout << SymmetricSum(DLL,10) << endl;
	return 0;
}

int SymmetricSum(DLList<int>& DLL, int length) {
	int S = 0;
	DLL.IterStart();
	DLL.IterEnd();
	elem<int>* left = NULL;
	elem<int>* right = NULL;
	for (int i = 0; i < length/2; ++i) {
		left = DLL.IterNext();
		right = DLL.IterPrev();
		S += left->inf * right->inf;
	}
	return S;
}

In fact we did little bit more when defining the outer helper function – now we can do that for random n.