Login
A.First Edition
This is third assignment of comp352.
กก
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.