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.