Example: Binary Search Tree (BST) as Template

Example of Binary Search Tree (BST) as template by using vectors, iterators, and time STL.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

Please notice that as an example, the first tree will have all the nodes to the left, the the second tree will have all the nodes to the right, and the third tree will be balance.

Since the second tree have to check first to the left and then to the right it will take more time than the first tree. Also since the third tree is balance it will find faster the values than the second tree

BSTree.cc:

#ifndef BST_CC
#define BST_CC

#include <iostream>

using namespace std;

// Forward declaration of class BST
// By fowarding the declaration, the class BST
// can access to the private data members of BSTNode
// helping to maintain the concept of encapsulation
template <typename T> class BST;

/**
 * BSTNode
 * @description:
 */
template <typename T>
class BSTNode {

	// This is needed to grant class BST access
	// to the private members of BSTNode
	// and help to maintaining the concept of encapsulation
	friend class BST<T>;

	private:
		BSTNode<T>* pLeft;
		T data;
		BSTNode<T>* pRight;

	public:

	//Default Constructor
	BSTNode(void);

	//Constructor
	BSTNode(const T& newData);

	// **** Get Methods ****

	T getData() const;

	// **** Set Methods ****

	void setData(const T& newData);

	//Destructor
	~BSTNode(void);

};

//////////////////////////////////////////////////////////////////

/**
 * BST
 * @description:
 */
template <typename T>
class BST {

	private:	

	int numberOfNodes;

	BSTNode<T> *pRoot;

	T insertNode(BSTNode<T> **pBSTNode,
			     const T& newData);

	T findNode(BSTNode<T> **pBSTNode,
		  	   const T& searchData);

	void displayPreOrderTraversal(BSTNode<T> *pBSTNode) const;

	void displayInOrderTraversal(BSTNode<T> *pBSTNode) const;

	void displayPostOrderTraversal(BSTNode<T> *pBSTNode) const;

	void removeAll(BSTNode<T> *pBSTNode) const;

	public:

	//Default Constructor
	BST(void);

	//Constructor
	BST(const T& newData);

	// **** Get Methods ****

	// **** Set Methods ****

	// **** Methods ****
	T insert(const T& newData);

	T find(const T& searchData);

	int size(void);

	void displayPreOrder(void) const;

	void displayInOrder(void) const;

	void displayPostOrder(void) const;

	//Destructor
	~BST(void);

};

//*****************************************************************************
//**** BSTNODE METHODS ****
//*****************************************************************************

///////////////////////////////////////////////////////////////////////////////
//**** BSTNODE PRIVATE METHODS ****
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//**** BSTNODE PUBLIC METHODS ****
///////////////////////////////////////////////////////////////////////////////

template <typename T>
BSTNode<T>::BSTNode(void){
	//cout << endl << '[Default BSTNode]' << endl;
}

template <typename T>
BSTNode<T>::BSTNode(const T& newData):
					  pLeft(NULL),
					  data(newData),
					  pRight(NULL){
//	cout << endl << '[BSTNode]' << endl;
}

// **** Get Methods ****

/**
 *
 */
template <typename T>
T BSTNode<T>::getData() const{
	return data;
}

// **** Set Methods ****

template <typename T>
void BSTNode<T>::setData(const T& newData){
	data = newData;
}

template <typename T>
BSTNode<T>::~BSTNode(void){
//	cout << endl << '[~BSTNode(X)]' << endl;
}

//*****************************************************************************
//**** BST METHODS ****
//*****************************************************************************

///////////////////////////////////////////////////////////////////////////////
//**** BST PRIVATE METHODS ****
///////////////////////////////////////////////////////////////////////////////

/**
 *
 */
template <typename T>
T BST<T>::insertNode(BSTNode<T> **pBSTNode,
			 		 const T& newData){

	// If subBST is empty then
	// create new BSTNode for the value
	if (*pBSTNode == NULL){

		*pBSTNode = new BSTNode<T>(newData);

		numberOfNodes++;

		return newData;

	}else{

		// If the data is not duplicated
		if (newData != (*pBSTNode)->data){

			// if newData is less than the current node's data
			// then insert a left BSTNode with newData
			// else insert a right BSTNode with newData
			if (newData < (*pBSTNode)->data ){

				insertNode( &( ( *pBSTNode) -> pLeft), newData);		

			}else{

				insertNode( &( ( *pBSTNode) -> pRight), newData);		

			}
		}else{

			T rtnT;

			return rtnT;
		}

	}
}

/**
 *
 */
template <typename T>
T BST<T>::findNode(BSTNode<T> **pBSTNode,
	  	   		   const T& searchData){

	T rtnT;

	// If subBST is empty
	if (*pBSTNode == NULL){

		// Object not found 

		return rtnT;

	}else{

		// If the data is not found
		// Keep searching
		if (searchData != (*pBSTNode)->data){

			// if newData is less than the current node's data
			// then insert a left BSTNode with newData
			// else insert a right BSTNode with newData
			if (searchData < (*pBSTNode)->data ){

				rtnT = findNode( &( ( *pBSTNode) -> pLeft), searchData);		

Just to let you know			}else{

				rtnT = findNode( &( ( *pBSTNode) -> pRight), searchData);		

			}

		}else{

			rtnT = (*pBSTNode)->data;
		}

	}	

	return rtnT;
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPreOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Process Node
		cout << pBSTNode->data << ' ';

		// Traverse left subBST
		displayPreOrderTraversal(pBSTNode->pLeft);

		// Traverse right subBST
		displayPreOrderTraversal(pBSTNode->pRight);

	}
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayInOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		displayInOrderTraversal( pBSTNode->pLeft);

		// Process Node
		cout << pBSTNode->data << ' ';

		// Traverse right subBST
		displayInOrderTraversal( pBSTNode->pRight);

	}

}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPostOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		displayPostOrderTraversal(pBSTNode->pLeft);

		// Traverse right subBST
		displayPostOrderTraversal(pBSTNode->pRight);

		// Process Node
		cout << pBSTNode->data << ' ';

	}

}

/**
 *
 */
template <typename T>
void BST<T>::removeAll(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		removeAll(pBSTNode->pLeft);

		// Traverse right subBST
		removeAll(pBSTNode->pRight);

		delete pBSTNode;

	}

}

///////////////////////////////////////////////////////////////////////////////
//**** BST PUBLIC METHODS ****
///////////////////////////////////////////////////////////////////////////////

/**
 *
 */
template <typename T>
BST<T>::BST(void){
	//cout << endl << '[Default BST]' << endl;
	pRoot = NULL;
	numberOfNodes = 0;
}

/**
 *
 */
template <typename T>
BST<T>::BST(const T& newData){
	//cout << endl << '[BST]' << endl;
	numberOfNodes = 0;
}

// **** Get Methods ****

// **** Set Methods ****

// **** Methods ****

/**
 *
 */
template <typename T>
T BST<T>::insert(const T& newData){
	return insertNode( &pRoot, newData);
}

/**
 *
 */
template <typename T>
T BST<T>::find(const T& searchData){

	//cout << endl << '[find : ' << searchData << ']' << endl;

	return findNode( &pRoot, searchData);
}

/**
 *
 */
template <typename T>
int BST<T>::size(void){
	return numberOfNodes;
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPreOrder(void) const{
	displayPreOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayInOrder(void) const{
	displayInOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPostOrder(void) const{
	displayPostOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
BST<T>::~BST(void){

	cout << endl << '[~BST(X)]' << endl;

//	removeAll(pRoot);

}

#endif

main.cpp:

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <sys/time.h>
#include <vector>
#include <algorithm>
#include 'BSTree.cc'

const int MAX_NUMBERS = 10000;

int main(int argc, char *argv[]){

	cout << endl << '{main}' << endl;

	vector<int> numbers;
	vector<int> reverseNumbers;
	vector<int> randomNumbers;

	BST<int> tree;
	BST<int> reverseTree;
	BST<int> randomTree;

	//Declare at top of main...

	struct timeval initialSimTime, postSimTime;

	double totalSimTime;

	int findMod = 10000;
	int NTimes = 5000;

	cout << 'Create Numbers...' << endl;

	// Insert the first 10,000 odd numbers, in order, into it.
	for (int i = 1; i < MAX_NUMBERS; i += 2)
			reverseNumbers.push_back(i);

	numbers = reverseNumbers;

	reverse(numbers.begin(), numbers.end());

	randomNumbers = numbers;

	random_shuffle(randomNumbers.begin(), randomNumbers.end());

	while(!numbers.empty()){
		tree.insert(numbers.back());
		numbers.pop_back();
	}

	while(!reverseNumbers.empty()){
		reverseTree.insert(reverseNumbers.back());
		reverseNumbers.pop_back();
	}

	while(!randomNumbers.empty()){
		randomTree.insert(randomNumbers.back());
		randomNumbers.pop_back();
	}

	cout << 'Search...' << endl;

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (tree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation took '<< totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (reverseTree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << '(Reverse) Simulation took '
	     << totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (tree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << '(Random) Simulation took '
	 	 << totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

/*
	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod == 0)
			if (tree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation took '<< totalSimTime << ' seconds' << endl;

	// Start over with a new BST and insert the same odd numbers,
	// but in reverse order.
	// Again, search for the first 20 multiples of 1,000 and
	// report how long each takes	

	// Insert the first 10,000 odd numbers, in order, into it.
	for (int i = MAX_NUMBERS; i >= 0; i--)
		if (i % 2 != 0)
			reverseTree.insert(i);

	findMod = 1000;
	NTimes = 20;

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod)
			if (reverseTree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation (Reverse) took '<< totalSimTime << ' seconds' << endl;

	// Insert the first 10,000 odd integers in random order into,
	// yet another BST, and run the same test.

	// Insert the first 10,000 odd numbers, in order, into it.

	int i;
	srand(time(NULL));

	bool bMatch[MAX_NUMBERS];

	for (int i = 0; i < MAX_NUMBERS; i++)
		bMatch[i] = false;

	int max = MAX_NUMBERS;
	int min = 0;

	int counter = 0;
	while(randomTree.size() < MAX_NUMBERS){

		i = rand() % (max - 1) + min;

		if ((max - 1) == i)
			max--;

		if ((min + 1) == i)
			min++;

		if (i >= max)
			i -= min;	

		for (int j = 0; j < MAX_NUMBERS; j++)
			cout << ((bMatch[i])? 1: 0);

		if ( i % 2 != 0 && !bMatch[i]){
			bMatch[i] = true;
			cout << ' ' << i;
			randomTree.insert(i);
		}
		cout << endl;

	}

	cout << endl << 'SIZE: ' << randomTree.size() << endl;

	findMod = 1000;
	NTimes = 20;

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod)
			if (reverseTree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation (Random) took '<< totalSimTime << ' seconds' << endl;
*/

	return 0;
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Example Generating Prime Numbers using Sieve of Eratosthenes Algorithm

Example of how to generate prime numbers using Sieve of Eratosthenes algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

primes.cpp:

#include<iostream>
#include<vector>
#include<stdio.h>
#include<ctime>
#include<math.h>
#include<string.h>
using namespace std;

//
// generatePrimesSlow()
// The array arr store the prime numbers up to and including x
// To test if a number i is prime, see if any prime number
// before i divides i evenly. If no prime number does, i is prime
// and is added to our array of prime numbers.
// Note: We should never see a number less than 2 in our array!
//
void generatePrimesSlow(int x, int * arr, int * amount)
{
   int count = 0; // numbers currently in the array

   for(int i=2; i<=x; i++) {
      bool isPrime = true;
      for (int j=0; j<count; j++) {
         if (i % arr[j] == 0) {
            isPrime = false;
            break;
	 }
      }
      if (isPrime) {
         arr[count] = i;
         count++;
      }
   }
   *amount = count;
}

//
// generatePrimesFast()
// The array arr stores our prime numbers up to and including x
// To generate these numbers, we use the the Sieve of Eratosthenes
// Visit http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
// for the explanation of the algorithm.
//
void generatePrimesFast(int x, int * arr, int * amount)
{
   int num = 2;
   int count = 0;
   bool *boolArr = new bool[x+1];
   //bool boolArr[x];
   memset(boolArr, true, (x+1)*sizeof(bool));
   for(int i=2; i<=x; i++) {
      if (boolArr[i]) {
         arr[count] = i;
         count++;
         int temp = i+i;
         while (temp <= x) {
            boolArr[temp] = false;
            temp += i;
         }
      }
   }
   *amount = count;
}

int main() {
   cout << 'Up to what number would you like to generate primes? ';
   int max;
   cin >> max;
   cout << endl;

   // This will be our array to hold the prime numbers.
   // Notice that this is probably way too much memory, since not every
   // number up to max will be prime
   // In fact, very very few numbers will be, let's try to free up some
   // memory by using some math
   // I think a bound for the number of primes up to N is N/lg(N)
   // Let's try it

   int amount = 0;
   int num_primes;
   if (max > 150) {
      double x = max;
      double actualNumberOfPrimes = x/(log(x)-4);
      //double actualNumberOfPrimes = x/(log(x));
      num_primes = (int) actualNumberOfPrimes;
   }
   else
      num_primes = max;
   int arr[num_primes+1];
   memset(arr,0,sizeof(arr));
   //generatePrimesFast(max, arr, &amount);
   generatePrimesSlow(max, arr, &amount);

   cout << 'Here are the prime numbers from 2 to ' << max << endl;
   for (int i=0; i < amount; i++) {
      cout << arr[i] << endl;
   }
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
2 Comments

Simple Tree in VC++

Simple Tree in Visual C++

This code was compiled and tested on a Windows.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

mainTree.cpp:

#include 'standard.h'
#include 'tree.h'

using namespace std;

//Print the divider to the specified file
void PrintDivider ( ofstream& fout,
				    char symbol,
					int numOfSymbols,
					int section );

//Print the count to the specified file
void PrintCount ( ofstream& fout,
				  int count );

int main(void)
{
	//declare the files
	ifstream fin;
	ofstream fout;

	//Set the task number to -1
	int section = -1;

	//Open the files
	fin.open('tree.txt');
	fout.open('treeOut.txt');

	//Create an instance of the class
	TreeClass tree;

	//Declare variables
	int numOfNodesInTree;

	//print empty tree message
	tree.PrintTree ( fout );
	PrintDivider ( fout,
		           '*',
				   63,
				   section++);

	//Insert values from the input file
	tree.CreateATree ( fin );

	//Print the tree nodes on one line
	tree.PrintTree ( fout );
	PrintDivider ( fout,
		           '*',
				   63,
				   section++);

	//Calculate the number of nodes in the tree
	numOfNodesInTree = tree.CountNodesInTree();

	//Print the count
	PrintCount ( fout,
		         numOfNodesInTree );
	fout << endl;

	//Close the files
	fin.close();
	fout.close();

	return 0;
}

//Print the divider to the specified file
void PrintDivider ( ofstream& fout,
				    char symbol,
					int numOfSymbols,
					int section )
{
	fout << endl << endl;
	fout << '#' << setw(2)<< section << BLANK;
	fout.fill( symbol );
	fout << setw( numOfSymbols ) << BLANK;
	fout << endl;
	fout.fill( BLANK );
	fout << setw(3)<<BLANK;

}

//Print the count to the specified file
void PrintCount ( ofstream& fout,
				  int count )
{
	fout << ' Number of Nodes currently in the tree are: '
		 << count << endl;

}

standard.h:

#ifndef standard_h

#define standard_h

#include <iostream>

#include <iomanip>

#include <fstream>

using namespace std;

const char BLANK = ' ';

#endif

tree.h:

#ifndef tree_h

#define tree_h

#include 'standard.h'

struct nodeType

{

	int value;

};

struct treeType

{

	nodeType  data;

    treeType* left;

	treeType* right;

};

typedef treeType* treePtr;

class TreeClass

{ 

	private:

		treePtr root;

		//Insert the node in ascending order

		void InsertNode ( treePtr& ptr,

		                  nodeType aNode );

		//Create memory, insert data into a tree node

		treePtr GetANode ( nodeType ANode );

		//Delete a leaf node from a tree, free the memory

		void DeleteLeaf( treePtr location, 

					     treePtr& parent );

		//Delete a node with one left child only

		void DeleteLeft ( treePtr location,

					      treePtr& parent );

		//Delete a node with one right child only

		void DeleteRight ( treePtr location,

						   treePtr& parent );

		//Delete a node that has two children

		void DeleteTwoChildren( treePtr& location );

		//Called recursively to visit each node in the tree InOrder

		void InOrder ( ofstream& fout,

			           treePtr ptr );

		//Called recursively to visit each node in the tree PreOrder

		void PreOrder ( ofstream& fout,

			            treePtr ptr );

		//Called recursively to visit each node in the tree PostOrder

		void PostOrder ( ofstream& fout,

			             treePtr ptr );

		//Count the nodes in the tree

		void CountNodes ( treePtr ptr,

			              int& count );

	public:

		//Constructor

		TreeClass( void );

		//Create a tree from an input file

		void CreateATree ( ifstream& fin );

		//Return a bool based on value of root

		bool EmptyTree() const;

		//Print Tree content to an output file

		void PrintTree ( ofstream& fout );

		//Count the nodes in a tree

		int CountNodesInTree ( void );

		//Delete a node in the tree, return success of delete

		bool Delete ( int num );

		//Insert a node in Order in a tree

		void Insert ( nodeType node );

		//Print tree in PreOrder

		void PrintPreOrder ( ofstream& fout );

		//Print tree in PostOrder

		void PrintPostOrder ( ofstream& fout );

		//Search the tree for a num, return the node, the parent and a flag

		void Search ( treePtr& ptr,

			          treePtr& parent,

					  int num,

					  bool& success );

		//The destructor, free the memory

		~TreeClass ( void );

};

#endif

TreeFunctions.cpp:

#include 'tree.h'
///Add your methods HERE

///Private Methods ------------------------------------------------------------------------///

//Insert the node in ascending order
void TreeClass::InsertNode ( treePtr& ptr,
				             nodeType aNode )
{
	//if this is the first node
	if ( ptr == NULL )
	{

		ptr = GetANode ( aNode );

	}
	//is the value less than current ptr value, insert to the left
	else if ( aNode.value < ptr->data.value )
	{
		InsertNode ( ptr->left, aNode );
	}
	//if the value greater than the current ptr value,insert to the right
	else
	{
		InsertNode ( ptr->right, aNode );
	}
}

//Create memory, insert data into a tree node
treePtr TreeClass::GetANode ( nodeType aNode )
{
	treePtr ptr;

	//Create a new tree node
	ptr = new treeType;

	//Put the data into the tree node
	ptr->data = aNode;

	//Set the pointers of this new leaf node
	ptr->left = NULL;
	ptr->right = NULL;

	return ptr;
}

//Delete a leaf node from a tree, free the memory
void TreeClass:GrineleteLeaf( treePtr location,
						    treePtr& parent )
{
	//Check to see if it is the root
    if ( parent == NULL )
	{
		root = NULL;
	}
	else if (parent->right == location)
	{
		//right child, sever connection
		parent->right = NULL;
	}
    else
	{
		//left child, sever connection
        parent->left = NULL;
	}

	//free the memory
	delete location;
}

//Delete a node with one left child only
void TreeClass:GrineleteLeft ( treePtr location,
						     treePtr& parent )
{
	//Check to see if it is the root
	if ( parent == NULL )
	{
		//Make left child the root
		root = location->left;
	}
	else if ( parent->left == location )
	{
		//left child, re-connect to it's left
		parent->left = location->left;
	}
	else
	{
		//right child, re-connect to it's right
		parent->right = location->left;
	}

	//Set left pointer to NULL
	location->left = NULL;

	//Free the memory
	delete location;
}

//Delete a node with one right child only
void TreeClass:GrineleteRight( treePtr location,
						     treePtr& parent )
{
	//Check to see if it is the root
	if ( parent == NULL )
	{
		//Set root to the right child
		root = location->right;
	}
	else if ( parent->right == location )
	{
		//right child, re-connect right
		parent->right = location->right;
	}
    else
	{
		//left child, re-connect left
		parent->left = location->right;
	}

	//Set right pointer to NULL
	location->right = NULL;

	//Free the memory
	delete location;
}

//Delete a node that has two children
void TreeClass:GrineleteTwoChildren( treePtr& location )
{

	treePtr place;
	treePtr walker;

	//Go left once
	place = location->left;

	//Check right, if NULL stop
	if ( place->right == NULL )
	{// found a place
		//move the data into location
		location->data = place->data;

		//Set the pointer of location left to place's left
		location->left = place->left;

	}// found a place

	else
	{// walk through tree
		do
		{
			// find node without right child
			walker = place;

			//Keep going right
			place = place->right;
		}while ( place->right!=NULL );

		//move the data into location
		location->data = place->data;

		//connect left child of place to right of walker
		walker->right = place->left;

	}// walk through tree

	//set place's pointer to NULL
	place->left = NULL;

	//Free the memory
	delete place;
}

//Called recursively to visit each node in the tree InOrder
void TreeClass::InOrder( ofstream& fout,
					     treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Go left
		InOrder( fout,
		         ptr->left );

		//Print this node
		fout << setw(3) << ptr->data.value;

		//Go right
		InOrder( fout,
		         ptr->right );
   }
}

//Called recursively to visit each node in the tree PreOrder
void TreeClass:RazzreOrder ( ofstream& fout,
						   treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Print this node
		fout << setw(3) << ptr->data.value;

		//Go left
		PreOrder( fout,
		          ptr->left );

		//Go right
		PreOrder( fout,
		          ptr->right );

   }
} 

//Called recursively to visit each node in the tree PostOrder
void TreeClass:RazzostOrder ( ofstream& fout,
						    treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Go left
		PostOrder( fout,
		           ptr->left );

		//Go right
		PostOrder( fout,
		           ptr->right );

		//Print the node
		fout << setw(3) << ptr->data.value;
   }
}

//Count the nodes in the tree
void TreeClass::CountNodes ( treePtr ptr,
						     int& count )
{
	//There is still a node in the tree
	if ( ptr !=NULL )
	{
		//Increment the count
		count++;

		//Go left
		CountNodes ( ptr->left,
			         count );

		//Go right
		CountNodes ( ptr->right,
			         count );
	}
}
///Public Methods ------------------------------------------------------------------------///
//Constructor
TreeClass::TreeClass()
{
	root = NULL;
}

//Create a tree from an input file
void TreeClass::CreateATree ( ifstream& fin )
{
	nodeType node;

	//while there is data in the input file
	while ( !fin.eof() )
	{
		//read a value
		fin >> node.value;

		//Insert the value into the tree
		Insert( node );
	}
}

//Return a bool based on value of root
bool TreeClass::EmptyTree() const
{
	return ( root == NULL );
}

//Print Tree content to an output file
void TreeClass:RazzrintTree ( ofstream& fout)

{
	//Set a node to the root
	treePtr ptr = root;

	//if null, tree is empty
	if (ptr == NULL)
	{
		fout<< 'Tree is empty' << endl;
	}
	else
	{
		//Call Inorder Print of tree
		InOrder ( fout,
	              ptr );
	}	           

}

//Count the nodes in a tree
int TreeClass::CountNodesInTree ( void )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Initialize the count
	int count = 0;

	//Call the recursive method to count the nodes in the tree
	CountNodes ( ptr,
		         count );

	return count;
}

//Delete a node in the tree, return success of delete
bool TreeClass:Grinelete ( int num )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Parent of root is null
	treePtr parent = NULL;

	bool success ;

	//Call recursive search method
	Search ( ptr,
		     parent,
			 num,
			 success );

	//If it was successful, node was found
	if ( success )
	{
		//Is it a leaf node?
		if ( ptr->left == NULL && ptr->right == NULL )
		{
			//Delete the leaf
			DeleteLeaf ( ptr,
				         parent );
		}
		//This is a node with only a left child
		else if ( ptr->left !=NULL && ptr->right == NULL )
		{
			//Delete a node with a left child
			DeleteLeft ( ptr,
				         parent );
		}
		//This is a node with a right child
		else if ( ptr->left == NULL && ptr->right != NULL )
		{
			//Delete a node with a right child
			DeleteRight ( ptr,
				          parent );
		}
		//it must be a node with two children
		else
		{
			//Delete a node with two children
			DeleteTwoChildren ( ptr );
		}
	}

	return success;
}

//Insert a node in Order in a tree
void TreeClass::Insert ( nodeType node )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Call the recursive method to insert a node
	InsertNode ( ptr,
		         node );

	//if this is the first node,set the root to the new node
	if ( EmptyTree())
	{
		root = ptr;
	}
}

//Print tree in PreOrder
void TreeClass:RazzrintPreOrder ( ofstream& fout )
{
	//Call the recursive method for PreOrder
	PreOrder ( fout,
		       root );
}

//Print tree in PostOrder
void TreeClass:RazzrintPostOrder ( ofstream& fout )
{
	//Call the recursive method for PostOrder
	PostOrder ( fout,
		        root );
}

//Search the tree for a num, return the node, the parent and a flag
void TreeClass::Search ( treePtr& ptr,
						 treePtr& parent,
						 int num,
						 bool& success )
{
	//Node was not found yet
	success = false;

	//while there are still nodes to search and node value was not found
	while ( ptr !=NULL && !success )
	{
		//If the node value in the tree is the value you are searching for
		if ( ptr->data.value == num )
		{
			//you found it
			success = true;
		}
		//if the node value in the tree is less than the value you are searching for
		else if ( num < ptr->data.value )
		{
			//Set the parent to the current ptr in the tree
			parent = ptr;

			//Move to the left
			ptr = ptr->left;
		}
		else
		{
			//Set the parent to the current ptr in the tree
			parent = ptr;

			//Move to the right
			ptr = ptr->right;
		}
	}
}

//The destructor, free the memory
TreeClass::~TreeClass ( void )
{
	//while the tree is not empty
	while ( !EmptyTree())
	{
		//Delete the node at the root
		Delete ( root->data.value );
	}
}

tree.txt:

48
12
56
2
9
18
52
49
10
-5
55
5
59
57
58
9
65
41
18
42

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Count all Alphabetics Characters Existent in the String

Process input file by Count all alphabetic characters existent in the string.

I would advice to compile them in Linux as I did.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

StreamOperation.h:

#ifndef STREAM_OPERATION_H
#define STREAM_OPERATION_H

#include <iostream>		// for cout

#include <fstream>		// for ifstream, ofstream

#include <string>       // for String
#include <cctype>       // for classify and transform individual characters

using namespace std;

/**
 * author: Alejandro G. Carlstein
 * Class: StreamOperation
 * Description: This class will read a textfile and produce an output
 *				in another text file. The other text file will contain
 * 				a copy of the input file but all blank lines will be
 *				removed, the lines are going to be numbered, all
 *              semicolons will be replaces with the string 'SEMI-COLON',
 *				print the number of lines removed at the second to last
 *              line, and finally print the number of alphabetic characters
 */
class StreamOperation {

private:   

	bool doRemoveBlankLines;

	bool doReplaceAllStrings;

	bool doCountLines;	

	int numLinesRemoved;

	int numAlphaCharacters;

	string oldStr;

	string newStr;

	void replaceAll(string& str,
					string oldStr,
					string newStr);

	int countAlphaCharacters(string str);

	void copyStream(ifstream& fin,
			  		ofstream& fout);

public:

	// Default constructor
	StreamOperation(void);

	// * Get Methods *

	// Get the number of lines removed
	int getNumberLinesRemoved();

	// Get the number of alphabetic character
	int getNumberAlphaCharacters();

	// * Set Methods * 	

	// * Print Methods *

	// Print the number of blank lines removed
	void printNumberLinesRemoved(ofstream& output);		

	// Print the number of alphabetic characters
	void printNumberAlphaCharacters(ofstream& output);		

	// * Process Methods *

	// Copy the content from an input stream to an output stream
	void copy(ifstream& input,
			  ofstream& output);	

	// Copy the content from an input stream to an output stream.
    // This method can remove all the blank lines in the output
    // stream when copying.
	void copy(ifstream& input,
			  ofstream& output,
			  bool removeBlankLines);

	// Copy the content from an input stream to an output stream.
	// This method can remove all the blank lines in the output
 	// stream when copying.
	// This method can number all the lines in the output stream.
	void copy(ifstream& input,
			  ofstream& output,
			  bool removeBlankLines,
              bool numberLines);

	// Copy the content from an input stream to an output stream.
	// This method can replace all old strings for a new string
	// This method can remove all the blank lines in the output
 	// stream when copying.
	// This method can number all the lines in the output stream.
	void copy(ifstream& input,
			  ofstream& output,
              string oldString,
			  string newString,
			  bool removeBlankLines,
			  bool numberLines);

    // Default destructor
	~StreamOperation(void);
};

#endif

StreamOperation.cpp:

/**
 * author: Alejandro G. Carlstein  
 * Class: StreamOperation
 * Description: This class will read a textfile and produce an output
 *		in another text file. The other text file will contain
 * 		a copy of the input file but all blank lines will be
 *		removed, the lines are going to be numbered, all
 *              semicolons will be replaces with the string 'SEMI-COLON',
 *		print the number of lines removed at the second to last
 *              line, and finally print the number of alphabetic characters
 */

#include 'StreamOperation.h'

/**
 * Public Methods
 */

/**
 * StreamOperation
 * @description: Default Constructor
 */
StreamOperation::StreamOperation(void){

	numLinesRemoved = 0;

	numAlphaCharacters = 0;

	doRemoveBlankLines = false;

	doReplaceAllStrings = false;

	doCountLines = false;

	oldStr = '';

	newStr = '';

}

// * Get Methods *

/**
 * getNumberLinesRemoved
 * @description: Get the number of lines removed
 * @return: integer
*/
int StreamOperation::getNumberLinesRemoved(){
	return numLinesRemoved;
}

/**
 * getNumberAlphaCharacters
 * @description: Get the number of alphabetic character
 * @return: integer
 */
int StreamOperation::getNumberAlphaCharacters(){
	return numAlphaCharacters;
}

// * Set Methods *

// * Print Methods *

// Print the number of blank lines removed
void StreamOperation:RazzrintNumberLinesRemoved(ofstream& output){
	if (output.is_open()){
		output << numLinesRemoved;
	} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
	}
}

// Print the number of alphabetic characters
void StreamOperation:RazzrintNumberAlphaCharacters(ofstream& output){
	if (output.is_open()){
		output << numAlphaCharacters;
	} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
	}
}

// * Process Methods *

/**
 * copy
 * @description: Copy the content from an input stream to an output stream
 * @param: input, output
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output){

	doRemoveBlankLines = false;

	doReplaceAllStrings = false;

	doCountLines = false;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *
 * @param: input, output, removeBlankLines
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output,
						   bool removeBlankLines){

	doReplaceAllStrings = false;

	doCountLines = false;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: input, output, removeBlankLines, numberLines
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output,
						   bool removeBlankLines,
						   bool numberLines){

	doReplaceAllStrings = false;

	doCountLines = numberLines;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *				 This method can replace all old strings for a new string
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: input, output, oldstring, new string, removeBlankLines, numberLines
 */
void StreamOperation::copy(ifstream& input,
			  			   ofstream& output,
			               string oldString,
			 			   string newString,
			  			   bool removeBlankLines,
						   bool numberLines){

	doReplaceAllStrings = true;

	oldStr = oldString;

	newStr = newString;

	doCountLines = numberLines;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * StreamOperation
 * @description: Default Destructor
 */
StreamOperation::~StreamOperation(void){
};

/**
 * Private Methods
 */

/**
 * replaceAll
 * @description: This method will remove all substrings for a new substring
 *               inside the string
 * @param: str, oldStr, newStr
 */
void StreamOperation::replaceAll(string& str,
			   		  			 string oldStr,
				  	  			 string newStr){

	// The method find return the unsigned int string::npos
    // if substring not found. Therefore, string::size_type
	// type is used
	string::size_type position = 0;

	// Until the end of the string is reached, search for every
    // string that maches the old string and replace it with
	// the new string.
	while((position = str.find(oldStr, position)) != string::npos){
		str.replace(position,
					oldStr.length(),
					newStr);
		position++;
	}
}

/**
 * countAlphaCharacters
 * @description: Count all alphabetics characters existent in the string
 * @param: str
 * @return: integer
 */
int StreamOperation::countAlphaCharacters(string str){

	int countAlpha = 0;

	// Go thought the whole string, counting all
	// the alphabetic characters
	for (int position = 0;
		 position < str.length();
		 position++){

		countAlpha += (isalpha(str[position]) ? 1 : 0);

	}

	return countAlpha;
}

/**
 * copyStream
 * @description: This method copy the content from an input stream to
 *               an output stream.
 *				 Base on the flags doRemoveBlankLines, doCountLines, and
 *               doReplaceAllStrings:
 *				 This method can replace all old strings for a new string
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: fin, fout
 */
void StreamOperation::copyStream(ifstream& fin,
							     ofstream& fout){
	int lineCounter;

	string strBuffer;

	numLinesRemoved = 0;

	numAlphaCharacters = 0;	

	lineCounter = 1;

	// Check if input and output stream can be open
	if (fin.is_open()){

		if (fout.is_open()){	

			//Read one line at the time as a string until eof
			while(!fin.eof()){

				getline(fin, strBuffer);

				// If the string is empty and doRemoveBlankLines
				// is true, count the string as as a blank line
				// else process the string
				if (strBuffer.empty() && doRemoveBlankLines){

					numLinesRemoved++;

				}else{

					// Count the alphabetic character of the string
					numAlphaCharacters += countAlphaCharacters(strBuffer);

					// Replace all semicolons with the string SEMICOLON
					if (doReplaceAllStrings)
						replaceAll(strBuffer, oldStr, newStr);

					// Add a number to each line if doCountLines is true
					if (doCountLines)
						fout << lineCounter++ << ' ';					

					fout << strBuffer << endl;

				}

			}

		} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
		}

	}else{
		cerr << '[X] Error: Program cannot read file!' << endl
			 << 'Exit Program!' << endl;
	}

}

processFile.cpp:

/**
 * Author: Alejandro G. Carlstein
 * Description: Use the file StreamOperations.cpp as an input file
 *				and process it using StreamOperation class
 */

#include <iostream>
#include <fstream>
#include 'StreamOperation.h'

static const string INPUT_FILE = 'StreamOperation.cpp';
static const string OUTPUT_FILE = 'Output.txt';
static const string SEMI_COLON = ';';
static const string STR_SEMI_COLON = 'SEMI-COLON';

/**
 * Main function
 * @param: argc, argv
 */

int main(int argc, char *argv[]){

	ifstream inputFile;
	ofstream outputFile;

	// If the program is executed with two parameters (file 1  and file 2)
    // used these parameters as input file and output file
	// If the program is executed without parameters use default files
    // If the program is executed with the -h parameter display help
	// If the program get more than two parameters or
    // wrong key display help
	if (argc == 1 || argc == 3){

		if (argc == 1){

			inputFile.open(INPUT_FILE.data());

			outputFile.open(OUTPUT_FILE.data());	

		}else{

			inputFile.open(argv[1]);

			outputFile.open(argv[2]);
		}

		StreamOperation StrOp;

		// Copy the content from the input file to the output file
	    // In the process, replace the ; with string SEMI-COLON,
		// remove the blank lines and number all the lines
		StrOp.copy(inputFile,
				   outputFile,
				   SEMI_COLON,
				   STR_SEMI_COLON,
				   true,
	               true);

		outputFile << 'Lines Removed: '
				   << StrOp.getNumberLinesRemoved() << endl;

		outputFile << 'Alphabetic Characters: '
				   << StrOp.getNumberAlphaCharacters();

		inputFile.close();

		outputFile.close();

	} else {
		cout << argv[0] << ' input_file output_file ' << endl;
	}	

	return 0;
}

input.txt:

23
This is
An example

of things;
That we can input;

;; aaa ;

output.txt:

1 23
2 This is
3 An example
4 of thingsSEMI-COLON
5 That we can inputSEMI-COLON
6 SEMI-COLONSEMI-COLON aaa SEMI-COLON

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

/**
* author: Alejandro G. Carlstein
* Course: CS 240
* Class: StreamOperation
* Description: This class will read a textfile and produce an output
*        in another text file. The other text file will contain
*         a copy of the input file but all blank lines will be
*        removed, the lines are going to be numbered, all
*              semicolons will be replaces with the string ‘SEMI-COLON’,
*        print the number of lines removed at the second to last
*              line, and finally print the number of alphabetic characters
*/

#include “StreamOperation.h”

/**
* Public Methods
*/

/**
* StreamOperation
* @description: Default Constructor
*/
StreamOperation::StreamOperation(void){

numLinesRemoved = 0;

numAlphaCharacters = 0;

doRemoveBlankLines = false;

doReplaceAllStrings = false;

doCountLines = false;

oldStr = “”;

newStr = “”;

}

// * Get Methods *

/**
* getNumberLinesRemoved
* @description: Get the number of lines removed
* @return: integer
*/
int StreamOperation::getNumberLinesRemoved(){
return numLinesRemoved;
}

/**
* getNumberAlphaCharacters
* @description: Get the number of alphabetic character
* @return: integer
*/
int StreamOperation::getNumberAlphaCharacters(){
return numAlphaCharacters;
}

// * Set Methods *

// * Print Methods *

// Print the number of blank lines removed
void StreamOperation:RazzrintNumberLinesRemoved(ofstream& output){
if (output.is_open()){
output << numLinesRemoved;
} else {
cerr << “[X] Error: Program cannot write file!” << endl
<< “Exit program!” << endl;
}
}

// Print the number of alphabetic characters
void StreamOperation:RazzrintNumberAlphaCharacters(ofstream& output){
if (output.is_open()){
output << numAlphaCharacters;
} else {
cerr << “[X] Error: Program cannot write file!” << endl
<< “Exit program!” << endl;
}
}

// * Process Methods *

/**
* copy
* @description: Copy the content from an input stream to an output stream
* @param: input, output
*/
void StreamOperation::copy(ifstream& input,
ofstream& output){

doRemoveBlankLines = false;

doReplaceAllStrings = false;

doCountLines = false;

copyStream(input, output);

}

/**
* copy
* @description: Copy the content from an input stream to an output stream.
*               This method can remove all the blank lines in the output
*                 stream when copying.
*
* @param: input, output, removeBlankLines
*/
void StreamOperation::copy(ifstream& input,
ofstream& output,
bool removeBlankLines){

doReplaceAllStrings = false;

doCountLines = false;

doRemoveBlankLines = removeBlankLines;

copyStream(input, output);

}

/**
* copy
* @description: Copy the content from an input stream to an output stream.
*               This method can remove all the blank lines in the output
*                 stream when copying.
*               This method can number all the lines in the output stream.
* @param: input, output, removeBlankLines, numberLines
*/
void StreamOperation::copy(ifstream& input,
ofstream& output,
bool removeBlankLines,
bool numberLines){

doReplaceAllStrings = false;

doCountLines = numberLines;

doRemoveBlankLines = removeBlankLines;

copyStream(input, output);

}

/**
* copy
* @description: Copy the content from an input stream to an output stream.
*                 This method can replace all old strings for a new string
*               This method can remove all the blank lines in the output
*                 stream when copying.
*               This method can number all the lines in the output stream.
* @param: input, output, oldstring, new string, removeBlankLines, numberLines
*/
void StreamOperation::copy(ifstream& input,
ofstream& output,
string oldString,
string newString,
bool removeBlankLines,
bool numberLines){

doReplaceAllStrings = true;

oldStr = oldString;

newStr = newString;

doCountLines = numberLines;

doRemoveBlankLines = removeBlankLines;

copyStream(input, output);

}

/**
* StreamOperation
* @description: Default Destructor
*/
StreamOperation::~StreamOperation(void){
};

/**
* Private Methods
*/

/**
* replaceAll
* @description: This method will remove all substrings for a new substring
*               inside the string
* @param: str, oldStr, newStr
*/
void StreamOperation::replaceAll(string& str,
string oldStr,
string newStr){

// The method find return the unsigned int string::npos
// if substring not found. Therefore, string::size_type
// type is used
string::size_type position = 0;

// Until the end of the string is reached, search for every
// string that maches the old string and replace it with
// the new string.
while((position = str.find(oldStr, position)) != string::npos){
str.replace(position,
oldStr.length(),
newStr);
position++;
}
}

/**
* countAlphaCharacters
* @description: Count all alphabetics characters existent in the string
* @param: str
* @return: integer
*/
int StreamOperation::countAlphaCharacters(string str){

int countAlpha = 0;

// Go thought the whole string, counting all
// the alphabetic characters
for (int position = 0;
position < str.length();
position++){

countAlpha += (isalpha(str[position]) ? 1 : 0);

}

return countAlpha;
}

/**
* copyStream
* @description: This method copy the content from an input stream to
*               an output stream.
*                 Base on the flags doRemoveBlankLines, doCountLines, and
*               doReplaceAllStrings:
*                 This method can replace all old strings for a new string
*               This method can remove all the blank lines in the output
*                 stream when copying.
*               This method can number all the lines in the output stream.
* @param: fin, fout
*/
void StreamOperation::copyStream(ifstream& fin,
ofstream& fout){
int lineCounter;

string strBuffer;

numLinesRemoved = 0;

numAlphaCharacters = 0;

lineCounter = 1;

// Check if input and output stream can be open
if (fin.is_open()){

if (fout.is_open()){

//Read one line at the time as a string until eof
while(!fin.eof()){

getline(fin, strBuffer);

// If the string is empty and doRemoveBlankLines
// is true, count the string as as a blank line
// else process the string
if (strBuffer.empty() && doRemoveBlankLines){

numLinesRemoved++;

}else{

// Count the alphabetic character of the string
numAlphaCharacters += countAlphaCharacters(strBuffer);

// Replace all semicolons with the string SEMICOLON
if (doReplaceAllStrings)
replaceAll(strBuffer, oldStr, newStr);

// Add a number to each line if doCountLines is true
if (doCountLines)
fout << lineCounter++ << ” “;

fout << strBuffer << endl;

}

}

} else {
cerr << “[X] Error: Program cannot write file!” << endl
<< “Exit program!” << endl;
}

}else{
cerr << “[X] Error: Program cannot read file!” << endl
<< “Exit Program!” << endl;
}

}

/**
 * author: Alejandro G. Carlstein
 * Course: CS 240
 * Class: StreamOperation
 * Description: This class will read a textfile and produce an output
 *		in another text file. The other text file will contain
 * 		a copy of the input file but all blank lines will be
 *		removed, the lines are going to be numbered, all
 *              semicolons will be replaces with the string 'SEMI-COLON',
 *		print the number of lines removed at the second to last
 *              line, and finally print the number of alphabetic characters
 */

#include 'StreamOperation.h'

/**
 * Public Methods
 */

/**
 * StreamOperation
 * @description: Default Constructor
 */
StreamOperation::StreamOperation(void){

	numLinesRemoved = 0;

	numAlphaCharacters = 0;

	doRemoveBlankLines = false;

	doReplaceAllStrings = false;

	doCountLines = false;

	oldStr = '';

	newStr = '';

}

// * Get Methods *

/**
 * getNumberLinesRemoved
 * @description: Get the number of lines removed
 * @return: integer
*/
int StreamOperation::getNumberLinesRemoved(){
	return numLinesRemoved;
}

/**
 * getNumberAlphaCharacters
 * @description: Get the number of alphabetic character
 * @return: integer
 */
int StreamOperation::getNumberAlphaCharacters(){
	return numAlphaCharacters;
}

// * Set Methods *

// * Print Methods *

// Print the number of blank lines removed
void StreamOperation:RazzrintNumberLinesRemoved(ofstream& output){
	if (output.is_open()){
		output << numLinesRemoved;
	} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
	}
}

// Print the number of alphabetic characters
void StreamOperation:RazzrintNumberAlphaCharacters(ofstream& output){
	if (output.is_open()){
		output << numAlphaCharacters;
	} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
	}
}

// * Process Methods *

/**
 * copy
 * @description: Copy the content from an input stream to an output stream
 * @param: input, output
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output){

	doRemoveBlankLines = false;

	doReplaceAllStrings = false;

	doCountLines = false;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *
 * @param: input, output, removeBlankLines
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output,
						   bool removeBlankLines){

	doReplaceAllStrings = false;

	doCountLines = false;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: input, output, removeBlankLines, numberLines
 */
void StreamOperation::copy(ifstream& input,
						   ofstream& output,
						   bool removeBlankLines,
						   bool numberLines){

	doReplaceAllStrings = false;

	doCountLines = numberLines;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * copy
 * @description: Copy the content from an input stream to an output stream.
 *				 This method can replace all old strings for a new string
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: input, output, oldstring, new string, removeBlankLines, numberLines
 */
void StreamOperation::copy(ifstream& input,
			  			   ofstream& output,
			               string oldString,
			 			   string newString,
			  			   bool removeBlankLines,
						   bool numberLines){

	doReplaceAllStrings = true;

	oldStr = oldString;

	newStr = newString;

	doCountLines = numberLines;

	doRemoveBlankLines = removeBlankLines;

	copyStream(input, output);

}

/**
 * StreamOperation
 * @description: Default Destructor
 */
StreamOperation::~StreamOperation(void){
};

/**
 * Private Methods
 */

/**
 * replaceAll
 * @description: This method will remove all substrings for a new substring
 *               inside the string
 * @param: str, oldStr, newStr
 */
void StreamOperation::replaceAll(string& str,
			   		  			 string oldStr,
				  	  			 string newStr){

	// The method find return the unsigned int string::npos
    // if substring not found. Therefore, string::size_type
	// type is used
	string::size_type position = 0;

	// Until the end of the string is reached, search for every
    // string that maches the old string and replace it with
	// the new string.
	while((position = str.find(oldStr, position)) != string::npos){
		str.replace(position,
					oldStr.length(),
					newStr);
		position++;
	}
}

/**
 * countAlphaCharacters
 * @description: Count all alphabetics characters existent in the string
 * @param: str
 * @return: integer
 */
int StreamOperation::countAlphaCharacters(string str){

	int countAlpha = 0;

	// Go thought the whole string, counting all
	// the alphabetic characters
	for (int position = 0;
		 position < str.length();
		 position++){

		countAlpha += (isalpha(str[position]) ? 1 : 0);

	}

	return countAlpha;
}

/**
 * copyStream
 * @description: This method copy the content from an input stream to
 *               an output stream.
 *				 Base on the flags doRemoveBlankLines, doCountLines, and
 *               doReplaceAllStrings:
 *				 This method can replace all old strings for a new string
 *               This method can remove all the blank lines in the output
 *				 stream when copying.
 *               This method can number all the lines in the output stream.
 * @param: fin, fout
 */
void StreamOperation::copyStream(ifstream& fin,
							     ofstream& fout){
	int lineCounter;

	string strBuffer;

	numLinesRemoved = 0;

	numAlphaCharacters = 0;	

	lineCounter = 1;

	// Check if input and output stream can be open
	if (fin.is_open()){

		if (fout.is_open()){	

			//Read one line at the time as a string until eof
			while(!fin.eof()){

				getline(fin, strBuffer);

				// If the string is empty and doRemoveBlankLines
				// is true, count the string as as a blank line
				// else process the string
				if (strBuffer.empty() && doRemoveBlankLines){

					numLinesRemoved++;

				}else{

					// Count the alphabetic character of the string
					numAlphaCharacters += countAlphaCharacters(strBuffer);

					// Replace all semicolons with the string SEMICOLON
					if (doReplaceAllStrings)
						replaceAll(strBuffer, oldStr, newStr);

					// Add a number to each line if doCountLines is true
					if (doCountLines)
						fout << lineCounter++ << ' ';					

					fout << strBuffer << endl;

				}

			}

		} else {
			cerr << '[X] Error: Program cannot write file!' << endl
				 << 'Exit program!' << endl;
		}

	}else{
		cerr << '[X] Error: Program cannot read file!' << endl
			 << 'Exit Program!' << endl;
	}

}
Share
Leave a comment

File Transfer Client and Server using Vigenere Cipher

[Disclaimer: This code is provided for educational purposes, you are responsible of how you use this code and this code is provided ‘as is’. Meaning that I do not take responsibility of  any harm that this code may or not produce]

The following is an example of a client and server that let you transfer a file from the client to the server by encrypting and then decrypting the packages using Vigenere Cipher.

Test file content example:

Note: This program is designed only to send files that are alphabetic in lower case, without spaces, and  only one line.

abcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyzaabcdefghijklmnopqrstuvwxyza

Makefile:

As a good policy, always add your name, short description, and any other information that could help a user that doesn’t know as you the content of your code and its behaviour.

Note: In the server, there must be a subdirectory named cli_serv in which ssh and scp can access after loading.



#########################################################################
# Author: Alejandro G. Carlstein Ramos Mejia
# Description: Client/Server File Transfer using Vergene Cipher
#
#
# make <= compile all files
# make build <= compile all files
# make all <= clean and compile all files
# make ssh <= Connect to server and go to folder cli_serv
# make upload <= Upload files on SRC_FILES list to server
# make uploadssh <= Upload files on SRC_FILES list to server and connect to server
# make submit <= Tar files on SRC_FILES list
# make zipsubmit <= Tar files on SRC_FILES list and gzip them
# make clean <= Clean all executable and *.o files
# make debug_server <= Debug server using dbg
# make debug_client <= Debug client using dbg
# make ldebug_server <= Debug for leaks on server
# make ldebug_client <= Debug for leaks on client
##########################################################################

##########################################################################
# Variables
##########################################################################

# PROJECT is the name used when preparing for sumit/
# The tar and/or zip file will be using this name
PROJECT = server_client_vergene

# SRC_FILES are list of files in the project.
# This list is used when uploading files to the server.
# Also, this list is used when tar/zipped for submit
SRC_FILES = \
	cli.c \
	serv.c\
	default.h \
	default.c \
	text.txt\
	Makefile \
	README

# OpenSSH SSH client (remote login program)
SSH = ssh

# secure copy (remote file copy program)
# SCP is used for uploading files to the server in secure mode
SCP = scp

# FOLDER_SERVER is the folder that SSH and SCP will try to access after login
FOLDER_SERVER = server_client_vergene

# SSH_SERVER is the hostname of the server
SSH_SERVER = bingsuns2.cc.binghamton.edu

# SSH_OPTION
# -t opens a pseudo-tty with in the current session.
# This flag is required to execute the commands on SSH_CD_FOLDER
SSH_OPTION = -t

# SSH_CD_FOLDER executes cd
# Then change the prompt to show the number of bash in the server
SSH_CD_FOLDER = 'cd $(FOLDER_SERVER); bash; echo $PS1'

# CC indicates which compiler is going to be used
CC = gcc

# Files required for compiling the server
CODE_SERVER_FILE = serv.c default.c

# Files required for compiling the client
CODE_CLIENT_FILE = cli.c default.c

# Name of the executable file for the server
EXEC_SERVER_FILE = serv

# Name for the executable file for the client
EXEC_CLIENT_FILE = cli

# Flags for the compiler
# -g indicate to provide debuggin information
# -Wall activates the warnings.
# -lm indicate the compiler to add basic mathematics libraries
CFLAGS = -g -Wall -lm

# COMPILE is the combination of the compiler with the flags
COMPILE = $(CC) $(CFLAGS)

# MFLAGS are flags that require to be added at the end
MFLAGS =

# USERNAME is used later when required to do an upload followed with ssh
USERNAME =

# Detect if the computer is SunOS to add flags needed for compiling
UNAME := $(shell uname)
ifeq ($(UNAME), SunOS)
 MFLAGS := -lsocket -lnsl
endif

##########################################################################
# 'make' options
##########################################################################

# Clean all files and compile client and server
all: clean compile_server compile_client

# Just build server and client
build: compile_server compile_client 

# Compile server
compile_server: $(CODE_SERVER_FILE)
	$(CC) $(CFLAGS) -o $(EXEC_SERVER_FILE) $(CODE_SERVER_FILE) $(MFLAGS)

# Compile client
compile_client: $(CODE_CLIENT_FILE)
	$(CC) $(CFLAGS) -o $(EXEC_CLIENT_FILE) $(CODE_CLIENT_FILE) $(MFLAGS)

# Debug server
debug_server:
	gdb $(EXEC_SERVER_FILE) 

# Debug client
debug_client:
	gdb $(EXEC_CLIENT_FILE) 

# Leak debug server
ldebug_server:
	valgrind --leak-check=full --show-reachable=yes -v $(EXEC_SERVER_FILE)

# Leak debug client
ldebug_client:
	valgrind --leak-check=full --show-reachable=yes -v $(EXEC_CLIENT_FILE)

# Upload files and connect to server
uploadssh:
	@echo -n 'Upload and connect to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SCP) $(SRC_FILES) $$user_name@$(SSH_SERVER):./$(FOLDER_SERVER);\
	$(SSH) $(SSH_OPTION) $$user_name@$(SSH_SERVER) $(SSH_CD_FOLDER);\

# Upload files to server
upload:
	@echo -n 'Upload to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SCP) $(SRC_FILES) $$user_name@$(SSH_SERVER):./$(FOLDER_SERVER);\

# Connect to server
ssh:
	@echo -n 'Connect to $(SSH_SERVER)- USERNAME: ';\
	read user_name;\
	$(SSH) $(SSH_OPTION) $$user_name@$(SSH_SERVER) $(SSH_CD_FOLDER);\

# Makes a archive containing all the project source files for submission.
submit:	$(SRC_FILES)
	tar -cvf $(PROJECT).tar $(SRC_FILES)

# Makes a archive containing all the project source files for submission
# and zip them
zipsubmit:	$(SRC_FILES)
	tar cvfz $(PROJECT).tar.gz $(SRC_FILES)

# Clean files
.PHONY: clean
clean:
	rm -f *~ *.o $(EXEC_SERVER_FILE) $(EXEC_CLIENT_FILE)

Default file is required for both the server and the client. It holds the libraries and definitions shared by both programs.

Default.h file:

/**
 * Author: Alejandro G. Carlstein
 * Description: File Transfer Client/Server
 */

#ifndef ACARLS_DEFAULT_H
#define ACARLS_DEFAULT_H

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <unistd.h>
#include <dirent.h>

/* Required for linux */
#include <string.h>

/* Required for SunOS */
#include <strings.h>

#include <ctype.h>

#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <netdb.h>

#define DEFAULT_PORT 					8414
#define DATA_PACKET_SIZE 			1024
#define NUM_BYTES							8
#define ENCRYPTION_KEY		    'security'
#define CHAR_KEY_A						97
#define CHAR_PLAIN_A					97
#define CHAR_CIPHER_A					65

#define DBG_LV0 0
#define DBG_LV1 0
#define DBG_LV2 0
#define DBG_LV3 0

#define TRUE									1
#define FALSE									0

#define QUIT_TRUE							0
#define QUIT_FALSE						1

#define CODE_FAIL							'0FAIL'
#define CODE_OK								'1OK'

#define CODE_HELLO						'100HELLO'
#define CODE_WELCOME 					'101WELCOME'
#define CODE_REQ_SERVER_NAME 	'102REQ_SERVER_NAME'

#define CODE_MSG 							'200MSG'

#define CODE_DATA							'300DATA'
#define CODE_EOF							'301EOF'
#define CODE_PUT						  '302PUT'
#define CODE_REQUEST_FILENAME	'303REQ_FILENAME'
#define CODE_REQUEST_ENCRYPT  '304REQ_ENCRYPT'
#define CODE_ENCRYPT					'305ENCRYPT'
#define CODE_REQUEST_FILE     '306REQUEST_FILE'

#define CODE_CMD							'400CMD'
#define CODE_LS								'401LS'

#define CODE_ERROR            '500ERROR'
#define CODE_ERROR_LS					'501ERROR_LS'
#define CODE_ERROR_CREAT_FILE '502ERROR_CREAT_FILE'

#define CODE_EXIT							'600EXIT'

#define MSG_ERR_WRONG_PROTOCOL  'Wrong protocol!'
#define MSG_ERROR_CREAT_FILE 		'Couldn't create file'
#define MSG_PORT_NUMBER_ONLY 		'Need port number only! \n%s <Port Number>'
#define MSG_ERR_COULDNT_SOCKET  'Couldn't obtain socket - %d'
#define MSG_ERR_COULDNT_CONNECT 'Couldn't connect!'
#define MSG_ERR_SENDING_DATA 		'Couldn't send data!'
#define MSG_ERR_RECEIVING_DATA	'Couln't recieve data!'
#define MSG_ERR_CONNECTION_FAIL 'Connection failed.'
#define MSG_ERR_NO_DIR_STREAM 	'Could not obtain the directory stream'

void debug(int debugLevel, char *fmt, ...);
void errorDoExit(char *fmt, ...);

#endif

Default.c:

/**
 * Author: Alejandro G. Carlstein
 * Description: File Transfer Client/Server
 */

#include 'default.h'

void debug(int debugLevel, char *fmt, ...){
	if (debugLevel == 1){
		va_list argp;
		fprintf(stdout, '[DBG] ');
		va_start(argp, fmt);
		vfprintf(stdout, fmt, argp);
		va_end(argp);
		fprintf(stdout, '\n');
	}
}

void errorDoExit(char *fmt, ...){
	va_list argp;
	fprintf(stderr, '[Error] ');
	va_start(argp, fmt);
	vfprintf(stderr, fmt, argp);
	va_end(argp);
	if (errno){
		fprintf(stderr, '=> %s\n', strerror(errno));
	}else{
		fprintf(stderr, '\n');
	}
	exit(1);
}

The following is the code for the server.
serv.c:

/**
 * Assignment: 1
 * Course: CS458
 * Author: Alejandro G. Carlstein
 * Description: FTP Server
 */

#include 'default.h'

/*max. length queue of pending connections may grow. */
#define MAX_BACKLOG							5
#define SETSOCKOPT_VAL  				1

#define MSG_SERVER_NAME 				'Server Name: ACARLSTEIN Server Version 1.0'
#define MSG_WAIT_CLIENT					'Waiting client...\n'
#define MSG_WAIT_CLIENT_ON_PORT	'\nTCPServer Waiting for client on port %d\n'

#define MSG_ERR_NO_SOCKET_OPT		'Couldn't set and/or get socket options'
#define MSG_ERR_UNABLE_BIND    	'Unable to bind'
#define MSG_ERR_UNABLE_LISTEN  	'Unable to Listen'
#define MSG_ERR_CANT_SEND_LIST  'Can't send server list\n'

struct Connection{
	int sock;
	int bytes_recieved;
	int port_number;
	int socket_descriptor;
	char send_data[DATA_PACKET_SIZE];
	char recv_data[DATA_PACKET_SIZE];
  struct sockaddr_in server_addr;
  struct sockaddr_in client_addr;
};

void setUpConnection(struct Connection *new_connection,
										 int port_number);
int menuDriver(struct Connection *new_connection);
void sendData(struct Connection *new_connection,
							const char* data);
int recieveData(struct Connection *new_connection);
void handShake(struct Connection* new_connection);
void sendListDirectoryContents(struct Connection* new_connection);
int receiveFileFromClient(struct Connection* new_connection);
int strdecrypt(const char* str_in,
							 char* str_out);

/**
 * MAIN
 */
int main(int argc, char *argv[]){
	debug(DBG_LV0, 'argc: %d', argc); 	

	short DO_QUIT_PROGRAM;
	int i;
	int port_number;
	socklen_t sin_size = sizeof(struct sockaddr_in);
	struct Connection connection;

	for(i = 0; DBG_LV1 && i < argc; ++i)
		debug(DBG_LV1, 'argv[%d]: %s', i, argv[i]); 		

	if (argc > 2)	errorDoExit(MSG_PORT_NUMBER_ONLY, argv[0]);

	port_number = (argc == 2) ? atoi(argv[1]) : DEFAULT_PORT;

	DO_QUIT_PROGRAM = QUIT_FALSE;
	while(DO_QUIT_PROGRAM){

		fflush(stdout);

		setUpConnection(&connection, port_number);

		printf(MSG_WAIT_CLIENT_ON_PORT, port_number);

		connection.socket_descriptor = accept(connection.sock,
													  						  (struct sockaddr *)&connection.client_addr,
																				  &sin_size);

		if (connection.socket_descriptor  == -1)
			errorDoExit(MSG_ERR_COULDNT_CONNECT);

		handShake(&connection);

 		menuDriver(&connection);

		close(connection.sock); 		

	}

  return 0;
}

/**
 * Menu driver waiting for instructions
 */
int menuDriver(struct Connection *new_connection){

	short DO_QUIT_CONNECTION;
	int bytes_received = 1;

	DO_QUIT_CONNECTION = QUIT_FALSE;
 	while (DO_QUIT_CONNECTION){  

		if(bytes_received == 0){
			DO_QUIT_CONNECTION = QUIT_TRUE;
		}else{

			printf(MSG_WAIT_CLIENT);

			bytes_received = recieveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_LS) == 0){
				sendListDirectoryContents(new_connection);
			}else
			if (strcmp(new_connection->recv_data, CODE_PUT) == 0){
				bytes_received = receiveFileFromClient(new_connection);
			}else{
				close(new_connection->sock);
				fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - PUT\n');
				DO_QUIT_CONNECTION = QUIT_TRUE;
			}
		}
	}
	return 0;
}

/**
 * Set up connection with the client
 */
void setUpConnection(struct Connection *new_connection,
										 int port_number){
	debug(DBG_LV0, 'setUpConnection(port_number: %d)', port_number);

	int opt_val = SETSOCKOPT_VAL;
	new_connection->port_number = port_number;

  if ((new_connection->sock = socket(AF_INET, SOCK_STREAM, 0)) == -1)
		errorDoExit(MSG_ERR_COULDNT_SOCKET, new_connection->sock);

	if (setsockopt(new_connection->sock, SOL_SOCKET, SO_REUSEADDR, &opt_val, sizeof(int)) == -1)
		errorDoExit(MSG_ERR_NO_SOCKET_OPT);

	debug(DBG_LV1, 'Got socket!');

  new_connection->server_addr.sin_family = AF_INET;
 	debug(DBG_LV1,'sin_family');      

  new_connection->server_addr.sin_port = htons(port_number);
	debug(DBG_LV1,'sin_port');

  new_connection->server_addr.sin_addr.s_addr = INADDR_ANY;
	debug(DBG_LV1, 'sin_addr');

  bzero(&(new_connection->server_addr.sin_zero), NUM_BYTES);
	debug(DBG_LV1,'sin_zero');

	// bind a name to a socket
  if (bind(new_connection->sock,
  				(struct sockaddr *)&new_connection->server_addr,
  				sizeof(struct sockaddr)) == -1){
		close(new_connection->sock);
		errorDoExit(MSG_ERR_UNABLE_BIND);
	}

	// Listen for connection on the socket
  if (listen(new_connection->sock, MAX_BACKLOG) == -1){
		close(new_connection->sock);
   	errorDoExit(MSG_ERR_UNABLE_LISTEN);
  }
	debug(DBG_LV1, 'Listening...');	

}

/**
 * Send data to client
 */
void sendData(struct Connection *new_connection,
							const char* data){
	debug(DBG_LV0, 'sendData(data: %s)', data);

 	int data_length;

	bzero(new_connection->send_data, DATA_PACKET_SIZE);
 	strcpy(new_connection->send_data, data);
 	data_length = strlen(new_connection->send_data);

 	debug(DBG_LV1, 'new_connection->send_data: %s',
 	      new_connection->send_data);

	if (send(new_connection->socket_descriptor,
					 new_connection->send_data,
					 data_length, 0) != data_length){
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_SENDING_DATA '\n');
	}
}

/**
 * Receive data from client
 */
int recieveData(struct Connection *new_connection){
	debug(DBG_LV0, 'recieveData()');

	bzero(new_connection->recv_data, DATA_PACKET_SIZE);
	int bytes_recieved = recv(new_connection->socket_descriptor,
														new_connection->recv_data,
														DATA_PACKET_SIZE,
														0);		

	debug(DBG_LV1, 'Check bytes received');

	if(bytes_recieved < 1){

		close(new_connection->sock);

		if(bytes_recieved == 0){
			fprintf(stderr, MSG_ERR_CONNECTION_FAIL '\n');
		}else{
			fprintf(stderr,MSG_ERR_RECEIVING_DATA '\n');
		}

	}else{

		debug(DBG_LV1, 'Received: %s', new_connection->recv_data);

		new_connection->bytes_recieved = bytes_recieved;
  	new_connection->recv_data[bytes_recieved] = '\0';
  }

  return bytes_recieved;
}

/**
 * Hand shake with client to test own protocol
 */
void handShake(struct Connection* new_connection){
	debug(DBG_LV0, 'handShake()');

	printf('Connection from (%s , %d)...\n',
         inet_ntoa(new_connection->client_addr.sin_addr),
         ntohs(new_connection->client_addr.sin_port));

	debug(DBG_LV1,' If client say HELLO, Greed client with WELCOME');
 	recieveData(new_connection);
	if (strcmp(new_connection->recv_data, CODE_HELLO) == 0){
		debug(DBG_LV1, 'Client handshake with server');
		sendData(new_connection, CODE_WELCOME);
	}else{
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - HELLO/WELCOME \n');
	}

	debug(DBG_LV0,'If client ask for server name send server name to client');
 	recieveData(new_connection);
	if (strcmp(new_connection->recv_data, CODE_REQ_SERVER_NAME) == 0){
		debug(DBG_LV1, 'Client asking for server name');
		sendData(new_connection, MSG_SERVER_NAME);
	}else{
		close(new_connection->sock);
		fprintf(stderr, MSG_ERR_WRONG_PROTOCOL ' - SERVER NAME\n');
	}
}

/**
 * Send list of directory contents to client
 */
void sendListDirectoryContents(struct Connection* new_connection){
	debug(DBG_LV0, 'void displayLocalListDirectoryContents()');
	int bytes_received;
	struct dirent *dirent_struct_ptr;
	DIR *directory_stream_ptr;

	if ((directory_stream_ptr = opendir('./')) != NULL){

  	while ((dirent_struct_ptr = readdir(directory_stream_ptr))){
			sendData(new_connection, dirent_struct_ptr->d_name);				

			bytes_received = recieveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_OK) != 0){
				fprintf(stderr, MSG_ERR_CANT_SEND_LIST);
			}
   	}
		sendData(new_connection, CODE_EOF);			  		

	}else{
		sendData(new_connection, CODE_ERROR_LS);
		errorDoExit(MSG_ERR_NO_DIR_STREAM);
	}

}

/**
 * Receive encrypted file from client
 */
int receiveFileFromClient(struct Connection* new_connection){
	debug(DBG_LV0, 'void receiveFileFromClient(is_encrypted: %s)');											

	int bytes_received;

	char filename[DATA_PACKET_SIZE];
	char filename_se[DATA_PACKET_SIZE];
	char filename_sd[DATA_PACKET_SIZE];
	char str_unencrypted[DATA_PACKET_SIZE];
	FILE *fp_se, *fp_sd;

	/* Request filename */
	debug(DBG_LV1, 'Request filename from client');
	sendData(new_connection, CODE_REQUEST_FILENAME);

	/* receive filename */
	bytes_received = recieveData(new_connection);
	strcpy(filename, new_connection->recv_data);
	sprintf(filename_se, '%s_se', filename);
	sprintf(filename_sd, '%s_sd', filename);

	debug(DBG_LV1, 'filename: %s', filename);
	debug(DBG_LV1, 'filename_se: %s', filename_se);
	debug(DBG_LV1, 'filename_sd: %s', filename_sd);	

	fp_se = fopen(filename_se, 'w');
	fp_sd = fopen(filename_sd, 'w');
	debug(DBG_LV1, 'Files open');

	if (fp_se == NULL || fp_sd == NULL){
		debug(DBG_LV1, 'Error, closing files');
		fclose(fp_se);
		fclose(fp_sd);
		errorDoExit(MSG_ERROR_CREAT_FILE);
	}else{

		debug(DBG_LV1, 'Download file...');
		/* Send code request file */
		sendData(new_connection, CODE_REQUEST_FILE);				

		bytes_received = recieveData(new_connection);

  	/* while loop until eof */
  	while (strcmp(new_connection->recv_data, CODE_EOF) != 0){

			debug(DBG_LV1, 'Saving: %s', new_connection->recv_data);
	  	/* save encrypted package */
			fprintf(fp_se, '%s', new_connection->recv_data);

			/* Decencrypt package */
			bzero(str_unencrypted, DATA_PACKET_SIZE);
			strdecrypt(new_connection->recv_data, str_unencrypted);
			debug(DBG_LV1, 'Decrypt: %s\n', new_connection->recv_data);

			/* Save unecrypted package */
			debug(DBG_LV1, 'DECRYPT: %s', str_unencrypted);

			fprintf(fp_sd, '%s', str_unencrypted);

			debug(DBG_LV1, 'Sending OK...');
	  	/*send ok */
			sendData(new_connection, CODE_OK);
			bytes_received = recieveData(new_connection);
  	}

	}	

	fclose(fp_se);
	fclose(fp_sd);
	return 0;
}

/**
 * Decrypt string
 */
int strdecrypt(const char* str_in,
							 char* str_out){
	debug(DBG_LV0, 'strdencrypt(str_in: %s)', str_in);

	int i, j;
	int i_cipher, i_key, i_temp;
	char str_key[DATA_PACKET_SIZE];
	strcpy(str_key, ENCRYPTION_KEY);
	char char_temp;
	for (i = 0, j = 0; i < strlen(str_in); ++i, ++j){

		i_cipher = str_in[i] - CHAR_CIPHER_A;
		i_key = str_key[j] - CHAR_KEY_A;
		i_temp = i_cipher - i_key;

		debug(DBG_LV1, 'Ci([%c]%d): %d, Ki([%c]%d): %d, Ci - Ki: %d',
					str_in[i], i, i_cipher, str_key[j], j, i_key, i_temp);

		if (i_temp > -1){
			//COMMON KNOWN DECRYPT ALGORIGHTM
			i_temp = ((i_temp) % 26);
		}else{
			//DECRYPT ALGORITHM FOR UNCOMMON CASES WHERE I_TEMP IS NEGATIVE
			i_temp = ((i_temp + 26) % 26);
		}

		char_temp = i_temp + CHAR_PLAIN_A;
		if (isalpha(char_temp)){
			str_out[i] = char_temp;
		}else{
			str_out[i] = '\0';
		}

		if ( (j + 1) >= strlen(str_key)) j = -1;
	}

	return 0;
}

The following is the code for the client.

cli.c

/**
 * Assignment: 1
 * Course: CS458
 * Author: Alejandro G. Carlstein
 * Description: Transfer Encrypted File Client
 */

#include 'default.h'

#define DEFAULT_HOST 									'localhost'
#define EXIT_PROGRAM 									0
#define DONT_EXIT_PROGRAM 						1

#define CMD_QUIT											'quit'
#define CMD_HELP											'help'
#define CMD_LS												'ls'
#define CMD_LLS												'lls'
#define CMD_LPWD											'lpwd'
#define CMD_PUT												'put'

#define MSG_DISPLAY_MENU 							'User help:\n'\
																			'help - Display help option\n'\
																		  'lls  - Display local directory list contents\n'\
                    				          'lpwd - Display local current directory\n'\
                    				          'put  - Transfer local file to server\n'\
                    				          '  put <file to transfer>\n'\
                    				          'quit - Quit program\n'

#define MSG_ERROR_UNKNOWN_COMMAND			'[X] Command not recognized: %s\n'
#define MSG_ERROR_GETTING_HOSTNAME 		'Couln't get hostname!'
#define MSG_ERROR_SERVER_DISCONNECTED 'Server disconnected...\n'

enum TOKENS{
	TOKEN_COMMAND,
	TOKEN_FILENAME,
	MAX_TOKENS
};

struct Connection{
	int sock;
	int bytes_received;
	int port_number;
	char send_data[DATA_PACKET_SIZE];
	char recv_data[DATA_PACKET_SIZE];
	struct hostent *host;
  struct sockaddr_in server_addr;
};

void getConnection(struct Connection *new_connection,
									 char *hostname,
									 int port_number);
void menuDriver(struct Connection *new_connection);
int receiveData(struct Connection *new_connection);
int sendData(struct Connection* new_connection, const char* data);
void handShake(struct Connection* new_connection);
void promptUser(char* tokens[]);
void displayHelp(void);
void displayLocalListDirectoryContents(void);
void printNameCurrentDirectory(void);
void receiveListDirectoryContents(struct Connection *new_connection);
void putFileOnServer(struct Connection *new_connection,
										 const char* filename);
int strencrypt(const char* str_in,
               char* str_out);
/**
 * MAIN
 */
int main(int argc, char* argv[]){
	debug(DBG_LV0, 'argc: %d', argc); 	

	int i;
	int port_number = (argc >= 3 ) ? atoi(argv[2]) : DEFAULT_PORT;
	char* host_name = (argc >= 2) ? argv[1] : DEFAULT_HOST;

	struct Connection connection;

	for(i = 0; i < argc; ++i)
		debug(DBG_LV0, 'argv[%d]: %s', i, argv[i]); 		

	if (argc > 3)
		errorDoExit(MSG_PORT_NUMBER_ONLY, argv[0]);

	debug(DBG_LV1, 'host: %s', host_name);

	getConnection(&connection, host_name, port_number);

	handShake(&connection);

	menuDriver(&connection);

	return 0;

}

/**
 * Driver menu
 */
void menuDriver(struct Connection *new_connection){
	debug(DBG_LV0, 'menuDriver()');

	short doExit = DONT_EXIT_PROGRAM;
	int i;
	char* tokens[MAX_TOKENS] = {NULL, NULL};
	char command[DATA_PACKET_SIZE];
	char filename[DATA_PACKET_SIZE];

  while(doExit){

		promptUser(tokens);				

		for (i = 0; DBG_LV1 && i < MAX_TOKENS; ++i)
			debug(DBG_LV1, 'TOKEN[%d]: %s', i, tokens[i]);

		/* Must copy string to work on SunOS */
		if (tokens[TOKEN_COMMAND] != NULL){
			strcpy(command, tokens[TOKEN_COMMAND]);
   		debug(DBG_LV1, '[Command: %s]', command);
		}

		if (tokens[TOKEN_FILENAME] != NULL){
    	strcpy(filename, tokens[TOKEN_FILENAME]);
	    debug(DBG_LV1, '[Filename: %s]', filename);
    }

		/* MENU */

		if (strcmp(command, CMD_QUIT) == 0){
			debug(DBG_LV1, 'COMMAND> %s: ', CMD_QUIT);
			close(new_connection->sock);
			printf('Bye Bye\n');
			doExit = EXIT_PROGRAM;

		}else
		if (strcmp(command, 'help') == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_HELP);
			displayHelp();

		}else
		if (strcmp(command, CMD_LLS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LLS);
			displayLocalListDirectoryContents();

		}else
		if (strcmp(command, CMD_LLS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LLS);
			displayLocalListDirectoryContents();

		}else
		if (strcmp(command, CMD_LS) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LS);
			receiveListDirectoryContents(new_connection);

		}else
		if (strcmp(command, CMD_LPWD) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_LPWD);
			printNameCurrentDirectory();

		}else
		if (strcmp(command, CMD_PUT) == 0){
			debug(DBG_LV1, 'COMMAND> %s ', CMD_PUT);
			putFileOnServer(new_connection, filename);

		}else{
			printf(MSG_ERROR_UNKNOWN_COMMAND, command);
		}

	}

}

/**
 * Obtain connection with server
 */
void getConnection(struct Connection *new_connection,
									 char *hostname,
									 int port_number){
	debug(DBG_LV0, 'getConnection(hostname: %s, port_number: %d)', hostname, port_number);

	if ((new_connection->host = gethostbyname(hostname)) == NULL)
		errorDoExit(MSG_ERROR_GETTING_HOSTNAME);

	new_connection->port_number = port_number;	

	if ((new_connection->sock = socket(AF_INET, SOCK_STREAM, 0)) == -1)
		errorDoExit(MSG_ERR_COULDNT_SOCKET, new_connection->sock);

	debug(DBG_LV1, 'Got socket!');

  new_connection->server_addr.sin_family = AF_INET;
	debug(DBG_LV1,'sin_family');

  new_connection->server_addr.sin_port = htons(port_number);
	debug(DBG_LV1,'sin_port');

  new_connection->server_addr.sin_addr = *((struct in_addr *)new_connection->host->h_addr);
	debug(DBG_LV1, 'sin_addr');

	// bzero() is used only for setting the values to zero
	bzero(&(new_connection->server_addr.sin_zero), NUM_BYTES);
	debug(DBG_LV1,'sin_zero');

  if (connect(new_connection->sock,
  					  (struct sockaddr *)&new_connection->server_addr,
  					  sizeof(struct sockaddr)) == -1)
		errorDoExit(MSG_ERR_COULDNT_CONNECT);

	debug(DBG_LV1, 'Got connection!');
}

/**
 * Receive data
 * @Return: Number of bytes received
 */
int receiveData(struct Connection *new_connection){
	debug(DBG_LV0, 'receiveData()');

	bzero(new_connection->recv_data, DATA_PACKET_SIZE);
	int bytes_received = recv(new_connection->sock,
														new_connection->recv_data,
														DATA_PACKET_SIZE,
														0);		

	if(bytes_received < 1){
		close(new_connection->sock);
		if(bytes_received == 0){
			close(new_connection->sock);
			printf(MSG_ERROR_SERVER_DISCONNECTED);
			errorDoExit(MSG_ERR_CONNECTION_FAIL);		

		}else{
			errorDoExit(MSG_ERR_RECEIVING_DATA);
		}
	}

	debug(DBG_LV1, 'Received (%d): %s',
				strlen(new_connection->recv_data), new_connection->recv_data);	

	new_connection->bytes_received = bytes_received;
  new_connection->recv_data[bytes_received] = '\0'; 

  return bytes_received;
}

/**
 * Send data
 * @Return: Number of bytes sended
 */
int sendData(struct Connection* new_connection,
						const char* data){
	debug(DBG_LV0, 'sendData(%s)', data);
	int data_length;

	bzero(new_connection->send_data, DATA_PACKET_SIZE);
	strcpy(new_connection->send_data, data);
	data_length = strlen(new_connection->send_data);

	if (send(new_connection->sock, new_connection->send_data,
					 data_length, 0) != data_length){
		close(new_connection->sock);
		errorDoExit(MSG_ERR_SENDING_DATA);
	}

	return data_length;
}

/**
 * Hand shake with the server to verify own protocol
 */
void handShake(struct Connection* new_connection){
	debug(DBG_LV0, 'handShake()');

	debug(DBG_LV1, 'Sending HELLO message...');
	sendData(new_connection, CODE_HELLO);

	debug(DBG_LV1, 'Getting WELCOME message...');
	receiveData(new_connection);  		

	if (strcmp(new_connection->recv_data, CODE_WELCOME) > -1){
		debug(DBG_LV1, 'Got WELCOME!');

		debug(DBG_LV1, 'Request server name');
		sendData(new_connection, CODE_REQ_SERVER_NAME);

		receiveData(new_connection);
		printf('Server Name: %s\n', new_connection->recv_data);
	}else{
		errorDoExit(MSG_ERR_WRONG_PROTOCOL);
	}
}

/**
 * Prompt user for input
 */
void promptUser(char* tokens[]){
	char str_input[DATA_PACKET_SIZE];
	char *p;
	int i;

	printf('\nftp> ');
	fgets(str_input, DATA_PACKET_SIZE, stdin);		

	p = strtok(str_input, ' \n');
  for (i = 0; p != NULL; (p = strtok(NULL, ' \n')), i++)
		tokens[i] = p;
}

/**
 * Display help message
 */
void displayHelp(void){
	debug(DBG_LV0, 'displayHelp()');
	printf(MSG_DISPLAY_MENU);
}

/**
 * Display local list directory contents
 */
void displayLocalListDirectoryContents(void){
	debug(DBG_LV0, 'void displayLocalListDirectoryContents()');

	struct dirent *dirent_struct_ptr;
	DIR *directory_stream_ptr;

	if ((directory_stream_ptr = opendir('./')) != NULL){
		printNameCurrentDirectory();

  	while ((dirent_struct_ptr = readdir(directory_stream_ptr))){
	  	printf(' %s\n',dirent_struct_ptr->d_name);
   	}
	}else{
		errorDoExit(MSG_ERR_NO_DIR_STREAM);
	}

}

/**
 * Print the name of the current directory
 */
void printNameCurrentDirectory(void){
	debug(DBG_LV0, 'void printNameCurrentDirectory()');

	long size;
	char *buf;
	char *ptr;
	size = pathconf('.', _PC_PATH_MAX);
	if ((buf = (char *)malloc((size_t)size)) != NULL){
		ptr = getcwd(buf, (size_t)size);
	}else{
		errorDoExit('Could not obtain the current directory');
	}
	printf('Current Directory: %s\n', ptr);
}

/**
 * Receive the list of directory contents from the server
 */
void receiveListDirectoryContents(struct Connection *new_connection){
	debug(DBG_LV0, 'receiveListDirectoryContents()');

	sendData(new_connection, CODE_LS);

	receiveData(new_connection);
	while (strcmp(new_connection->recv_data, CODE_EOF) != 0){

		if (strcmp(new_connection->recv_data, CODE_ERROR_LS) == 0){
			fprintf(stderr, 'Couldn't read list directory contents!\n');
			break;
		}else{
			printf('%s\n', new_connection->recv_data);
			sendData(new_connection, CODE_OK);
		}
		receiveData(new_connection);
	}

}

/**
 * Put an encrypted file on the server
 */
void putFileOnServer(struct Connection *new_connection,
										 const char* filename){
	debug(DBG_LV0, 'void putFileOnServer(filename: %s)', filename);

	char str_filename[DATA_PACKET_SIZE];
	char filename_ce[DATA_PACKET_SIZE];
	char str_in_file[DATA_PACKET_SIZE];
	char str_in_file_encrypt[DATA_PACKET_SIZE];
	FILE *fp, *fp_ce;

	strcpy(str_filename, filename);

	debug(DBG_LV1, 'str_filename: %s', str_filename);

	sprintf(filename_ce, '%s_ce', str_filename);

	debug(DBG_LV1, 'filename_ce: %s', filename_ce);

	debug(DBG_LV1, 'OPEN FILE TO READ');
	fp = fopen(str_filename, 'r');

	debug(DBG_LV1, 'OPEN FILE TO WRITE');
	fp_ce = fopen(filename_ce, 'w');

	if (fp == NULL || fp_ce == NULL){
		fclose(fp_ce);
		fclose(fp);
		errorDoExit('Couldn't open file');
	}else{

		/* Send PUT code to server */
		sendData(new_connection, CODE_PUT);

		debug(DBG_LV0, 'Waiting for CODE_REQUEST_FILENAME');
		/* Receive filename request form server */
		receiveData(new_connection);
		if (strcmp(new_connection->recv_data, CODE_REQUEST_FILENAME) == 0){

			debug(DBG_LV0, 'Send filename');
			/* Send filename to server */
			sendData(new_connection, str_filename);

			/* Receive request to send file */
			receiveData(new_connection);
			if (strcmp(new_connection->recv_data, CODE_REQUEST_FILE) == 0){
				printf('Sending file: %s.\n', filename);
					/* Encrypt file */
				while(fgets(str_in_file, DATA_PACKET_SIZE, fp) != NULL){
					debug(DBG_LV2, 'Reading (Len: %d): %s', strlen(str_in_file), str_in_file);						

					/* encrypt package */
					strencrypt(str_in_file, str_in_file_encrypt);

					/* Save it in <filename>_ce */
					fprintf(fp_ce, '%s', str_in_file_encrypt);					

					/* send packages */
					sendData(new_connection, str_in_file_encrypt);

					/* Waiting for ok */
					receiveData(new_connection);
					if (strcmp(new_connection->recv_data, CODE_OK) == 0){
						printf('OK');
					}else{
						errorDoExit('Wrong protocol - Waiting OK');
					}	

				}
				sendData(new_connection, CODE_EOF);			

			}else{
				errorDoExit('Wrong protocol - Waiting request for file ');
			}

		}else{
			errorDoExit('Wrong protocol - Waiting for request of filename');
		}

	}

	fclose(fp);
	fclose(fp_ce);

}

/**
 * Encrypt the string using key
 * @Return: Number of bytes encrypted
 */
int strencrypt(const char* str_in,
               char* str_out){
	debug(DBG_LV0, 'strencrypt(str_in: %s)', str_in);

	int i, j;
	int i_plain, i_key;

	char str_key[DATA_PACKET_SIZE];

	strcpy(str_key, ENCRYPTION_KEY);

	for (i = 0, j = 0; i < strlen(str_in) - 1; ++i, ++j){

		i_plain = (unsigned int)str_in[i] - CHAR_PLAIN_A;
		i_key = (unsigned int)str_key[j] - CHAR_KEY_A;

		str_out[i] = (char)((i_plain + i_key) % 26 + CHAR_CIPHER_A);

		debug(DBG_LV1, '(str_out: %d) [%c:%d] = (str_in:%d)[%c:%d], (key:%d)[%c:%d]',
					i, str_out[i], (int)str_out[i],
					i, str_in[i], (int) str_in[i],
					j, str_key[j], (int)str_key[j]);

		if ( (j + 1) >= strlen(str_key)) j = -1;
	}

	return strlen(str_in);
}

When I wrote the code, I was following certain guidelines. As you may think the code could be written better. I agree.

In case you have any questions about the code please post them. I will try to answer you as soon as possible.

Share
Leave a comment