Login

A.First Edition
This is third assignment of comp352.
B.The problem
กก
C.The idea of program
D.The major functions
C.Further improvement
//the file name is dictionary.h
// The Dictionary abstract class.  KEComp compares a key
// and an element. EEComp compares two elements.  
template <class Key, class Elem, class KEComp, class EEComp>
class  Dictionary {
public:
  // Reinitialize dictionary
  virtual void clear() = 0;
  // Insert an element.  Return true if insert is
  // successful, false otherwise.
  virtual bool insert(const Elem&) = 0;
  // Remove some element matching Key.  Return true if such
  // exists, false otherwise.  If multiple entries match
  // Key, an arbitrary one is removed.
  virtual bool remove(const Key&, Elem*&) = 0;
  // Remove and return an arbitrary element from dictionary.
  // Return true if some element is found, false otherwise.
  virtual bool removeAny(Elem*&) = 0;
  // Return a copy of some Elem matching Key.  Return true
  // if such exists, false otherwise.  If multiple elements
  // match Key, return an arbitrary one.
  virtual bool find(const Key&, Elem*&) const = 0;
  // Return the number of elements in the dictionary.
  virtual int size() = 0;
};
กก
// Binary tree node abstract class
template <class Elem> class BinNode {
public:
  // Return the node's element
  virtual Elem& val() = 0;
  // Set the node's element
  virtual void setVal(const Elem&) = 0;
  // Return the node's left child
  virtual BinNode* left() const = 0;
  // Set the node's left child
  virtual void setLeft(BinNode*) = 0;
  // Return the node's right child
  virtual BinNode* right() const = 0;
  // Set the node's right child
  virtual void setRight(BinNode*) = 0;
  // Return true iff the node is a leaf
  virtual bool isLeaf() = 0;
};
//the file name is BinNode.h
// Binary tree node class
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
  Elem it;                     // The node's value
  BinNodePtr* lc;              // Pointer to left child
  BinNodePtr* rc;              // Pointer to right child
public:
  // Two constructors -- with and without initial values
  BinNodePtr() { lc = rc = NULL; }
  BinNodePtr(const Elem& e, BinNodePtr* l =NULL,
                     BinNodePtr* r =NULL)
    { it = e; lc = l; rc = r; }
  ~BinNodePtr() {}             // Destructor
  Elem& val() { return it; }
  void setVal(const Elem& e) { it = e; }
  inline BinNode<Elem>* left() const { return lc; }
  void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; }
  inline BinNode<Elem>* right() const { return rc; }
  void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }
  bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};
//the file name is BST.h
// This file includes all of the pieces of the BST implementation

#include "dictionary.h"

#include "binnode.h"

// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary<Key, Elem, KEComp, EEComp> {
protected:
  BinNode<Elem>* root;   // Root of the BST
  int nodecount;         // Number of nodes in the BST
  // Private "helper" functions
  void clearhelp(BinNode<Elem>*);
  BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
  BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
  BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
                            BinNode<Elem>*&);
  bool findhelp(BinNode<Elem>*, const Key&, Elem*&) const;
  void printhelp(BinNode<Elem>*, int) const;
public:
  BST() { root = NULL; nodecount = 0; }  // Constructor
  ~BST() { clearhelp(root); }            // Destructor
  void clear()
    { clearhelp(root); root = NULL; nodecount = 0; }
  bool insert(const Elem& e) {
    root = inserthelp(root, e);
    nodecount++;
    return true;
  }
  bool remove(const Key& K, Elem*& e) {
    BinNode<Elem>* t = NULL;
    root = removehelp(root, K, t);
    if (t == NULL) return false;  // Nothing found
    e = &(t->val());
    nodecount--;
    delete t;
    return true;
  }
  bool removeAny(Elem*& e) { // Delete min value
    if (root == NULL) return false; // Empty tree
    BinNode<Elem>* t;
    root = deletemin(root, t);
    e = &(t->val());
    delete t;
    nodecount--;
    return true;
  }
  bool find(const Key& K, Elem*& e) const
    { return findhelp(root, K, e); }
  int size() { return nodecount; }
  void print() const {
    if (root == NULL) cout << "The BST is empty.\n";
    else printhelp(root, 0);
  }
};

template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
clearhelp(BinNode<Elem>* subroot) {
  if (subroot == NULL) return;
  clearhelp(subroot->left());
  clearhelp(subroot->right());
  delete subroot;
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
  if (subroot == NULL)            // Empty tree: create node
    return (new BinNodePtr<Elem>(val, NULL, NULL));
  if (EEComp::lt(val, subroot->val())) // Insert on left
    subroot->setLeft(inserthelp(subroot->left(), val));
  else subroot->setRight(inserthelp(subroot->right(), val));
  return subroot;  // Return subtree with node inserted
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
  if (subroot->left() == NULL) { // Found min
    min = subroot;
    return subroot->right();
  }
  else {                         // Continue left
    subroot->setLeft(deletemin(subroot->left(), min));
    return subroot;
  }
}

template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
           BinNode<Elem>*& t) {
  if (subroot == NULL) return NULL; // Val is not in tree
  else if (KEComp::lt(K, subroot->val())) // Check left
    subroot->setLeft(removehelp(subroot->left(), K, t));
  else if (KEComp::gt(K, subroot->val())) // Check right
    subroot->setRight(removehelp(subroot->right(), K, t));
  else {                           // Found it: remove it
    BinNode<Elem>* temp;
    t = subroot;
    if (subroot->left() == NULL)       // Only a right child
      subroot = subroot->right();      //  so point to right
    else if (subroot->right() == NULL) // Only a left child
      subroot = subroot->left();       //  so point to left
    else {                    // Both children are non-empty
      subroot->setRight(deletemin(subroot->right(), temp));
      Elem te = subroot->val();
      subroot->setVal(temp->val());
      temp->setVal(te);
      t = temp;
    }
  }
  return subroot;
}

template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
      BinNode<Elem>* subroot, const Key& K, Elem*& e) const {
  if (subroot == NULL) return false;         // Empty tree
  else if (KEComp::lt(K, subroot->val()))    // Check left
    return findhelp(subroot->left(), K, e);
  else if (KEComp::gt(K, subroot->val()))    // Check right
    return findhelp(subroot->right(), K, e);
  else { e = &(subroot->val());  return true; } // Found it
}

template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
  if (subroot == NULL) return;          // Empty tree
  printhelp(subroot->left(), level+1);  // Do left subtree
  for (int i=0; i<level; i++)           // Indent to level
    cout << "  ";
  cout << subroot->val() << "\n";       // Print node value
  printhelp(subroot->right(), level+1); // Do right subtree
}

//the file name is Elem.h
//This is the element of login system
class Record
{
private:
	int id;
	char pwd[7];
public:
	Record(const Record& rec);
	int getID() const {return id;}
	const char* getPWD() const { return pwd;}
	void setID(int newID){ id = newID;}
	void setPWD(const char* newPWD){strncpy(pwd, newPWD, 6);}
	Record(int newID, char* password);	
	Record();
	Record& operator=(const Record& rec);
};

Record::Record()
{
	id =-1;
}

Record& Record::operator =(const Record& rec)
{
	id = rec.getID();
	strcpy(pwd, rec.getPWD());
	return *this;
}


Record::Record(int newID, char* password)
{
	id=newID;
	strncpy(pwd, password, 7);
}

Record::Record(const Record& rec)
{
	id = rec.getID();
	strcpy(pwd, rec.getPWD());
}

class KEComp
{
public:
	static bool lt(int key, const Record& Elem) {return key<Elem.getID();}
	static bool eq(int key, const Record& Elem) {return key==Elem.getID();}
	static bool gt(int key, const Record& Elem) {return key>Elem.getID();}
};

class EEComp
{
public:
	static bool lt(const Record& Elem1, const Record& Elem2)
		{ return Elem1.getID()<Elem2.getID();}
	static bool eq(const Record& Elem1, const Record& Elem2)
		{ return Elem1.getID()==Elem2.getID();}
	static bool gt(const Record& Elem1, const Record& Elem2)
		{ return Elem1.getID()>Elem2.getID();}
};


//the file name is menu.h
/*********************************************************
*Name of file: menu.h
*function: It is a generic class for input menus. 
*Idea of program: Whatever an input menu is simply ask user to
*	input a number to indicate his choice which has some associated
*	infomation displayed. So I just set up a menu by inputing a 
*	set of strings and return the number which user input.
*	I also want it to have a set of automatical response by
*	inputing a set of function pointers which can be called when a
*	number is entered.
************************************************************/
#include <iostream>

using namespace std;

const int MaxMenuItems = 10;
const int MaxTitleLength = 20;
class Menu
{
private:
	char titles[MaxMenuItems][MaxTitleLength];
	void (*respondList[MaxMenuItems])();
	int itemCount;	
	int quitIndex;
	int getInput();
	void printMenu();
public:
	void setMenu(char** menuTitles, int titleNum);
	int input(bool useDefault=true);	
	void setRespond(int index, void (*respond)());
	void setQuitIndex(int index);//this is not very useful
};

void Menu::setQuitIndex(int index)
{
	if (index<itemCount)
	{
		quitIndex = index;
	}
	else
	{
		cout<<"Out of menu count!\n";
	}
}


void Menu::setMenu(char** menuTitles, int titleNum)
{
	itemCount = titleNum;
	for (int i=0; i< titleNum; i++)
	{
		strcpy(titles[i], menuTitles[i]);
		respondList[i]=NULL;
	}
	quitIndex = itemCount-1;//by default it should quit at last item
}

void Menu::setRespond(int index, void (*respond)())
{
	if (index<itemCount)
	{
		respondList[index] = respond;
	}
	else
	{
		cout<<"Out of menu count!\n";
	}
}

int Menu::input(bool useDefault)
{
	int index;
	index = getInput();
	if (useDefault)
	{
		if (respondList[index]!=NULL)
		{
			respondList[index];
		}
	}
	return index;
}

void Menu::printMenu()
{
	cout<<"\n       Menu (choose by enter item index\n";
	for (int i=0; i<itemCount; i++)
	{
		cout<<"\t("<<i+1<<") "<<titles[i]<<endl;
	}
	cout<<"choice>";
}


int Menu::getInput()
{
	//char buffer[20];
	int result=0;
	printMenu();
	do 
	{
		cin>>result;		
		if (result<1||result>itemCount)
		{
			cout<<"Please enter a number for your choices!\n";
		}
	}
	while (result<1||result>itemCount);
	return result-1;
}
//the file name is login.cpp
//////////////////////////////////////////////////////////////////////
//author: qingzhe huang
//date: oct. 26, 2003
//purpose: To use BST to simulate login system
//idea of program:
//		1. My class MyBST is only inherited from a certain template class---BST
//		with all type parameter already set up. So, it is not a template class
//		anymore. 
//		2. By printing it in alphabetic order, I should use inorder. By saving
//		in file in a way such that when it is read in, it can gives exact same
//		tree. It should use preorder.
//		3. I implement my own Key-Element-compare class and Element-Element-compare
//		class. 
//		4. ID should be 7-digit, if it is smaller than 1000000, which has length of 7,
//		0's should be added in the front to make it as long as 7 characters.
//		5.	Password is 6-character strings and the longer part will be chopped to 6.
//		6. There are a default input and output file name, if there is no parameter 
//		following command line. If there is one parameter after file name, it is 
//		considered to be input file name. If there are two parameter, then they are
//		input file name and output file name.
////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include "BST.h"
#include "Elem.h"
#include "Menu.h"
#include <fstream>

using namespace std;

char* menuStr[5] = {"Add new user", "Delete user", "Verify user", "Print user", "Quit"};

char* defaultFileName = "c:\\nickid.dat";

class MyBST: public BST<int, Record, KEComp, EEComp>
{
private:
	ifstream in;
	ofstream out;
	Menu menu;
	void int2str(int i, char* buffer, int len);
	void preOrder(BinNode<Record>*& node);
	void visitNode(BinNode<Record>*& node);
	void inOrder(BinNode<Record>* node);
	void printNode(BinNode<Record>* node);
	void doAdd();
	bool getID(int& ID);
	bool getPassword(char* str);
	bool deleteUser(int ID);
	void doVerify();
	void doDelete();
	void doPrint();
public:
	void readFile(const char* fileName);
	void writeFile(const char* fileName);
	bool addNew(int ID, char* passWord);
	bool verifyUser(int ID, char* passWord);
	void printUsers();
	void getChoice();
};


int main(int argc, char** argv)
{	
	MyBST my;
	char* inputName = defaultFileName, *outputName=defaultFileName;
	if (argc==2)
	{
		inputName = argv[1];
	}
	else
	{
		if (argc==3)
		{
			inputName=argv[1];
			outputName=argv[2];
		}
	}
	my.readFile(inputName);
	my.getChoice();
	my.writeFile(outputName);

	return 0;
}

//the buffer should be at least one longer than "len" for '\0'
void MyBST::int2str(int i, char* buffer, int len)
{
	int length;
	itoa(i, buffer, 10);
	length = strlen(buffer);
	if (length< len)
	{
		for (int j=0; j<=len; j++)//<= to include '\0'
		{
			if (j<=length)
			{
				buffer[len-j]=buffer[length-j];
			}
			else
			{
				buffer[len-j]='0';//to fill with '0'
			}
		}
	}
}


void MyBST::doVerify()
{
	int id;
	char buffer[20];
	if (getID(id))
	{
		if (getPassword(buffer))
		{
			if (verifyUser(id, buffer))
			{
				cout<<"Valid user\n";
				return;
			}
			else
			{
				cout<<"Invalid user\n";
				return;
			}
		}
	}
	cout<<"incorrect input of ID or password\n";
}

void MyBST::doPrint()
{
	inOrder(root);
}


void MyBST::doDelete()
{
	int ID;
	if (getID(ID))
	{
		if (deleteUser(ID))
		{
			cout<<"user "<<ID<<" is deleted successfully!\n";
			return;
		}
	}
	cout<<"fail to delete "<<ID<<endl;
}

bool MyBST::getID(int& ID)
{	
	char buffer[20];
	int i=0;
	char* ptr=buffer;
	char* start=buffer;
	cout<<"\nPlease enter your ID:";
	cin>>buffer;
	while (i<7)
	{
		if (*ptr==' '&&i==0)
		{
			start++;
			ptr++;
		}
		else
		{
			if (*ptr>='0'&&*ptr<='9')
			{	
				ptr++;
				i++;
			}
			else
			{
				return false;
			}
		}
	}
	*ptr = '\0';
	ID = atoi(start);
	return true;
}

bool MyBST::getPassword(char* buffer)
{
	int i=0;
	char* ptr=buffer;
	int start=0;
	cout<<"\nPlease enter your password:";
	cin>>buffer;
	while (i<6)
	{
		if (*ptr==' '&&i==0)
		{
			start++;
		}
		else
		{
			if (isalnum(*ptr))
			{
				i++;
			}
			else
			{
				return false;
			}
		}
		ptr++;
	}
	*ptr = '\0';
	if (start!=0)
	{
		i=0;
		while (i<7)//include '\0'
		{
			buffer[i]=buffer[start+i];
		}
	}

	return true;
}
	


void MyBST::doAdd()
{
	int ID;
	char buffer[30];
	cout<<"Please enter your ID and password:";
	if (getID(ID))
	{
		if (getPassword(buffer))
		{
			if (addNew(ID, buffer))
			{	
				cout<<"\nYour ID is added successfully!\n";
				return;
			}
		}
	}
	cout<<"Fail to add your ID\n";
}


void MyBST::getChoice()
{
	int index;
	char** temp=menuStr;
	menu.setMenu(temp, 5);
	while ((index=menu.input(false))!=4)
	{
		switch(index)
		{
		case 0:
			doAdd();
			break;
		case 1:
			doDelete();
			break;
		case 2:
			doVerify();
			break;
		case 3:
			doPrint();
			break;
		}
	}
}


void MyBST::printNode(BinNode<Record>* node)
{
	int id;
	char buffer[8];
	id = node->val().getID();
	int2str(id, buffer, 7);
	cout<<buffer<<"   "<<node->val().getPWD()<<endl;	
}

void MyBST::inOrder(BinNode<Record>* node)
{
	BinNode<Record>*l, *r;
	if  (node!=NULL)
	{
		l = node->left();
		r = node->right();
		inOrder(l);
		printNode(node);
		inOrder(r);
	}
}

bool MyBST::verifyUser(int ID, char* password)
{
	Record* rec;
	if (find(ID, rec))
	{
		if (!strcmp(password, rec->getPWD()))
		{
			return true;
		}
	}
	return false;
}

bool MyBST::deleteUser(int ID)
{
	Record* rec;
	if (remove(ID, rec))
	{
		//delete rec;
		return true;
	}
	
	return false;
}

void MyBST::preOrder(BinNode<Record>*& node)
{
	BinNode<Record>* l, *r;
	while (node!=NULL)
	{
		l = node->left();
		r = node->right();
		visitNode(node);
		preOrder(l);
		preOrder(r);
	}
}


void MyBST::visitNode(BinNode<Record>*& node)
{
	int i;
	char buffer[8];
	i = node->val().getID();
	int2str(i, buffer, 7);
	out<<"   "<<buffer<<"  "<<node->val().getPWD();
	delete node;
	node =NULL;
}




void MyBST::readFile(const char* fileName)
{
	int id;
	char buffer[30];
	Record* ptr;
	in.open(fileName, ios::in);
	clear();
	while (!in.eof())
	{
		in>>id>>buffer;
		ptr = new Record(id, buffer);	
		insert(*ptr);
	}
	in.close();
}

void MyBST::writeFile(const char* fileName)
{
	out.open(fileName, ios::out);
	preOrder(root);
}

bool MyBST::addNew(int ID, char* passWord)
{
	Record *rec;

	if (find(ID, rec))
	{
		cout<<"User ID "<<ID<<" already exists!\n";
		return false;
	}
	else
	{
		rec = new Record(ID, passWord);
		insert(*rec);
		return true;
	}
}



//the input file is here.


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)