SimpleLogin
A.Second Edition
This is second edition of assignment 3 of comp352 and it is a simple solution.
กก
C.Further improvement
//the file name is assignment3.cpp
#include <iostream>
#include <fstream>
#include "BST.h"
#include "Elem.h"
using namespace std;
//char* inputFileName= "c:\\userids.dat";
char* inputFileName= "c:\\laura.dat";
char* outputFileName = "c:\\laura.dat";
class Login
{
private:
BST<char*, Account, MyKEComp, MyEEComp> tree;
int number;
ifstream in;
ofstream out;
Account myAccount;
void printNode(BinNode<Account>* ptr);
void preOrder(BinNode<Account>* ptr);
void inOrder(BinNode<Account>* ptr);
void writeNode(BinNode<Account>* ptr);
void displayLogin();
public:
void choices();
bool addUser();
bool deleteUser();
bool verifyUser();
void print();
void quit();
void readFile(const char* fileName);
};
bool Login::verifyUser()
{
Account a;
char id[20];
char password[20];
cout <<"Enter your user ID: " << endl;
cin >> id;
cout<<"\nand password:";
cin>> password;
if (tree.find(id, a))
{
if (strcmp(a.getPassword(), password)==0)
{
cout<<"valid user\n";
return true;
}
}
cout<<"invalid user!\n";
return false;
}
void Login::printNode(BinNode<Account>* ptr)
{
cout<<ptr->val().getID()<<" "<<ptr->val().getPassword()<<endl;
}
void Login::print()
{
BinNode<Account> *ptr;
ptr = tree.getRoot();
inOrder(ptr);//BinNode need to access the left and right
}
bool Login::addUser()
{
Account a; //because "find" uses call by reference
char id[8];
char password[7];
cout <<"Enter your user ID: " << endl;
cin >> id;
cout<<"\nand password:";
cin>> password;
if (!(tree.find(id, a))) //if not found, insert and return true
{
Account* newAccount = new Account;
newAccount->setUserID(id);
newAccount->setPassword(password);
tree.insert( *newAccount);
cout<<"id added successfully!\n";
return true;
}
else
{
cout<<"id failed to add!\n";
return false;
}
}
bool Login::deleteUser()
{
Account a; //"find" return by reference
char id[20];
cout <<"Enter your user ID: " << endl;
cin >> id;
if (tree.find(id, a )) //if this is true, remove should also return true
{
return (tree.remove(id, a));
}
else
{
return false;
}
}
void Login::writeNode(BinNode<Account>* ptr)
{
char id[10], pwd[10];
strcpy(id, ptr->val().getID());
strcpy(pwd, ptr->val().getPassword());
out<<id<<" "<<pwd<<" ";
}
void Login::inOrder(BinNode<Account>* ptr)
{
BinNode<Account>* l, *r;
if (ptr!=NULL)
{
l = ptr->getLeft();
r= ptr->getRight();
inOrder(l);//BinNode need to access the left and right
printNode(ptr);//you need to write the node into file
// delete ptr;
// ptr = NULL;
inOrder(r);
}
}
void Login::preOrder(BinNode<Account>* ptr)
{
BinNode<Account>* l, *r;
if (ptr!=NULL)
{
l = ptr->getLeft();
r= ptr->getRight();
writeNode(ptr);//you need to write the node into file
//which is the in
// delete ptr;
// ptr = NULL;
preOrder(l);//BinNode need to access the left and right
preOrder(r);
}
}
void Login::quit()
{
out.open(outputFileName);
preOrder(tree.getRoot());
}
void Login::displayLogin()
{
cout << "(1) add new user" << endl;
cout << "(2) delete user" << endl;
cout << "(3) verify user" << endl;
cout << "(4) print users" << endl;
cout << "(5) quit" << endl;
cout << "Select the desired choice:" << endl;
}
void Login::choices()
{
displayLogin();
while (true)
{
cin >> number;
switch (number)
{
case 1:
addUser();
break;
case 2:
deleteUser();
break;
case 3:
verifyUser();
break;
case 4:
print();
break;
case 5:
quit();
return;
// cout<< "Choose a number on the given list" << endl;
}
displayLogin();
}
}
void Login::readFile(const char* fileName)
{
Account* ptr;
in.open(fileName);
char id[10];
char password[10];
while (!in.eof())
{
in>>id>>password;
ptr = new Account(id, password);
//here you use id and password to create a account
tree.insert(*ptr); //establish the tree
}
in.close();
}
int main()
{
Login I;
I.readFile(inputFileName);//a const
I.choices();
return 0;
}
//filename is elem.h
class Account
{
private:
char userID[7+1]; //+1 for the NULL character
char password[6+1];
public:
Account() {;} //default constructor
Account(char* ID, char* Psword) {strcpy(userID, ID); strcpy(password, Psword);}
const char* getID() const{return userID;}
const char* getPassword() const{return password;}
void setUserID(char* ID) {strncpy(userID, ID, 8);}
void setPassword(char* newPsword) {strncpy(password, newPsword, 7);}
};
class MyKEComp
{
public:
static bool lt(char* key, const Account& elem) {return strcmp(key, elem.getID())<0;}
static bool eq(char* key, const Account& elem) {return strcmp(key, elem.getID())==0;}
static bool gt(char* key, const Account& elem) {return strcmp(key, elem.getID())>0;}
};
class MyEEComp
{
public:
static bool lt(const Account& elem1, const Account& elem2)
{return strcmp(elem1.getID(), elem2.getID())<0;}
static bool eq(const Account& elem1, const Account& elem2)
{return strcmp(elem1.getID(), elem2.getID())==0;}
static bool gt(const Account& elem1, const Account& elem2)
{return strcmp(elem1.getID(), elem2.getID())>0;}
};
//filename 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> {
private:
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:
//add one function here
BinNode<Elem>* getRoot(){ return root;}
//add one function here
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
}
//filename Binnode.h
// 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;
virtual BinNode<Elem>* getLeft()=0;
virtual BinNode<Elem>* getRight()=0;
};
// 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(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); }
//add two functions
BinNode<Elem>* getLeft(){ return lc;}
BinNode<Elem>* getRight(){ return rc;}
};
กก
//filename 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;
};