Population

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.