CPhoneBook09
[ Home ] [ Up ]

//PhoneBook09.cpp

// insertAtHead              added 09 11/27/2000
// searchByName              added
// void swap(p,q)            added 
// void swap(e1,e2)          added 
// bool isSortedByName()     added 06 11/08/2000
//    void sortByName(void); added 05
//Overload << for output     added 04
//Constructor CPhoneBook(ch) added 03


////////////////////////////////////////////////////////////
// project #6 Date Assigned 11/8/2000, Date Due 11/17/2000
// describe ten shuffling methods   (20)
// implement one of the ten methods (20)
// write the testShuffle            (10)
// Five test runs                   (10)


////////////////////////////////////////////////////////////
//include files
////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>


////////////////////////////////////////////////////////////
//constants
////////////////////////////////////////////////////////////
int const MAX_LEN = 10;
int const MAX_COUNT = 10;
int const TEST_COUNT = 5;


////////////////////////////////////////////////////////////
//global variables
////////////////////////////////////////////////////////////
int masterKey = 1;


////////////////////////////////////////////////////////////
//test values
////////////////////////////////////////////////////////////
const char *testNames[] = 
  {"Bob", "Tom", "Ann", "Ron", "Ben", "Ken", "Rob",
   "Sam", "Don", "Dan", "Tim"};

const int MAX_NAMES = sizeof(testNames)/sizeof(testNames[0]);

const char *testPhones[] = 
  {"111-1111", "222-2222", "333-3333", "444-4444"};

const int MAX_PHONES = sizeof(testPhones)/sizeof(testPhones[0]);

const char *testGroups[] = 
  {"Group1", "Group2", "Group3", "Group4"};

const int MAX_GROUPS = sizeof(testGroups)/sizeof(testGroups[0]);


////////////////////////////////////////////////////////////
//CPhoneEntry
////////////////////////////////////////////////////////////
struct CPhoneEntry
  {
  char name[MAX_LEN+1];
  char phone[14+1];
  char group[10+1];
  int key;
  CPhoneEntry *next;
  };


////////////////////////////////////////////////////////////
//CPhoneBook
////////////////////////////////////////////////////////////
class CPhoneBook
  {
  private:
    CPhoneEntry *first;
    CPhoneEntry *last;
    int count;
    CPhoneEntry * addressOfEntryAt(int pos);
  public:
    CPhoneBook(void);
    bool insertAtEnd(char name[], char phone[], char group[], int key);
    void display(void);
    void deleteAll(void);
    ~CPhoneBook(void);
    CPhoneBook(char ch);
    void sortByName(void);
    bool isSortedByName(void);
    void displayReverse(void);
    void displayReverse2(void);
    friend ostream & operator << (ostream &os, const CPhoneBook &list);
    CPhoneEntry * searchByName(char name[]);
    bool insertAtHead(char name[], char phone[], char group[], int key);

    bool deleteByAddress(CPhoneEntry *p);
    bool deleteByName(char name[]);
    int deleteAllByName(char name[]);
    bool deleteByPosition(int pos);
    bool searchReplaceByName(char nameOld[], char nameNew[]);
    int searchReplaceAllByName(char nameOld[], char nameNew[]);
    int deleteDuplicates(void);

  };


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testInsertAtHead(void)
  {
    {
    CPhoneBook myBook;
    myBook.display();
    myBook.insertAtHead("John", "231-7000", "friend", 1);
    myBook.display();
    myBook.insertAtHead("Tom",  "231-7001", "enemy", 1);
    myBook.display();
    }

  }


bool CPhoneBook::insertAtHead(char name[], char phone[], char group[], int key)
  {
  CPhoneEntry *p;

  p = new CPhoneEntry;
  if (NULL == p)
      return false;

  strcpy(p->name, name);
  strcpy(p->phone, phone);
  strcpy(p->group, group);
  p->key = key;

  if (NULL == first)
      {
      first = p;
      last  = p;
      p->next = NULL;
      }
    else
      {
      p->next = first;
      first = p;
      }

  count++;
  return true;
  }



// p=first
// if the found return p
// else advance p and go to prev statement
/*
   p = first
   while p <> NULL
     if at p the name we are looking for then
         return p
       else
         advance p
     end while

   return NULL
*/


void testSearchByName(void)
  {
  CPhoneBook b1('r');
  char tName[MAX_LEN+1];
  cout << b1;
  for (int i=1; i<=TEST_COUNT; i++)
    {
    strcpy(tName, testNames[rand()%MAX_NAMES]);
    cout << tName << " is at " << b1.searchByName(tName) << endl;
    }
  }


CPhoneEntry * CPhoneBook::searchByName(char name[])
  {
  CPhoneEntry *p;

  p = first;
  while (p != NULL)
    {
    if ((strcmp(p->name, name)==0))
        return p;
      else
        p = p->next;
    }

  return NULL;
  }


//CPhoneEntry * CPhoneBook::addressOfEntryAt(int pos)
//Returns the address of node at position [0 to count-1]
//Possibilities   return
//-------------   ------
//Empty list      NULL
//Nonempty
//  pos=0           address of first node
//  pos [0,count-1] address of the node by advancing pos times
//  pos >= count    NULL

CPhoneEntry * CPhoneBook::addressOfEntryAt(int pos)
  {
  if (count <= 0)
      return NULL;
  if (pos < 0)
      return NULL;
  if (pos >= count)
      return NULL;

  CPhoneEntry *p;
  p = first;

  for (int steps=1; steps<=pos; steps++)
    p = p->next;

  return p;
  }


//void CPhoneBook::displayReverse(void)
void CPhoneBook::displayReverse2(void)
  {
  for (int pos=count-1; pos>=0; pos--)
    {
    CPhoneEntry *p;  //better if put outside the loop
    p = addressOfEntryAt(pos);

    cout << p->name << ", ";
    cout << p->phone << ", ";
    cout << p->group << ", ";
    cout << p->key << endl;
    }

  cout << endl;
  }



////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testDisplayReverse2(void)
  {
  for (int i=1; i<=TEST_COUNT; i++)
    {
    cout << "Test #" << i << ": ";
    CPhoneBook b1('r');
    cout << "Original\n";
    b1.display();
    cout << "Reverse\n";
    b1.displayReverse2();
    }
  }


//void CPhoneBook::displayReverse(void)
/* start from the first, display the last node
   start from the first, display next to the last

  for pos=count to 1 step -1 do the following
    point to first
    advance pointer pos-1 times
    display the pointed node

*/
void CPhoneBook::displayReverse(void)
  {
  CPhoneEntry *p;

  for (int pos=count; pos>0; pos--)
    {
    p = first;

    for (int steps=1; steps<=pos-1; steps++)
      p = p->next;

    cout << p->name << ", ";
    cout << p->phone << ", ";
    cout << p->group << ", ";
    cout << p->key << endl;
    }

  cout << endl;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testDisplayReverse(void)
  {
  for (int i=1; i<=TEST_COUNT; i++)
    {
    cout << "Test #" << i << ": ";
    CPhoneBook b1('r');
    cout << "Original\n";
    b1.display();
    cout << "Reverse\n";
    b1.displayReverse();
    }
  }


////////////////////////////////////////////////////////////
//swap the records
////////////////////////////////////////////////////////////
void swap(CPhoneEntry &e1, CPhoneEntry &e2)
  {
  char tName[MAX_LEN+1];
  char tPhone[14+1];
  char tGroup[10+1];
  int  tKey;
  //plug the e1 and e2 at the right places
  strcpy(tName, e1.name);
  strcpy(e1.name, e2.name);
  strcpy(e2.name, tName);

  strcpy(tPhone, e1.phone);
  strcpy(e1.phone, e2.phone);
  strcpy(e2.phone, tPhone);

  strcpy(tGroup, e1.group);
  strcpy(e1.group, e2.group);
  strcpy(e2.group, tGroup);

  tKey = e1.key;
  e1.key = e2.key;
  e2.key = tKey;
  }


////////////////////////////////////////////////////////////
//swap the records through the pointers
////////////////////////////////////////////////////////////
void swap(CPhoneEntry *p, CPhoneEntry *q)
  {
  char tName[MAX_LEN+1];
  char tPhone[14+1];
  char tGroup[10+1];
  int  tKey;

  strcpy(tName, p->name);
  strcpy(p->name, q->name);
  strcpy(q->name, tName);

  strcpy(tPhone, p->phone);
  strcpy(p->phone, q->phone);
  strcpy(q->phone, tPhone);

  strcpy(tGroup, p->group);
  strcpy(p->group, q->group);
  strcpy(q->group, tGroup);

  tKey = p->key;
  p->key = q->key;
  q->key = tKey;
  }


////////////////////////////////////////////////////////////
//bool CPhoneBook::isSortedByName(void)
////////////////////////////////////////////////////////////
//Go from left to right
//if a pair is found to be out of order
//then return false else return true
bool CPhoneBook::isSortedByName(void)
  {
  CPhoneEntry *p, *q;

  if (first == last)
      return true;

  p = first;
  q = p->next;
  while (q != NULL)
    {
    if ((strcmp(p->name, q->name)>0))
        return false;
    p = q; // or p = p->next
    q = q->next;
    }

  return true;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testIsSortedByName(void)
  {
  //for (int i=0; i<TEST_COUNT; i++)
  //  {
    CPhoneBook b1('r');
    cout << "Original: " << b1;
    if (b1.isSortedByName())
        cout << "The list is SORTED\n";
      else
        cout << "The list is NOT SORTED\n";

    b1.sortByName();
    cout << "Sorted:   "<< b1;
    if (b1.isSortedByName())
        cout << "The list is SORTED\n";
      else
        cout << "The list is NOT SORTED\n";
  //  }
  }


////////////////////////////////////////////////////////////
//void CPhoneBook::sortByName(void)
////////////////////////////////////////////////////////////
//Algorithm
/*
  do the following
    check pairs from left to right and put them in order
    until no change in order of the list

  if first = last then exit function
  do the following
    set sorted = true
    p = first
    q = p->next
    while q <> null
      if name at p > name at q then
          swap records at p and q except the pointers
          sorted = false
          end if
      p = q or p = p->next
      q = q->next
      end while

    while not sorted
*/
void CPhoneBook::sortByName(void)
  {
  if (first == last) return;

  bool sorted;
  CPhoneEntry *p, *q;

  do 
    {
    sorted = true;
    p = first;
    q = p->next;
    while (q != NULL)
      {
      if ((strcmp(p->name, q->name)>0))
          {
          //swap records at p and q except the pointers
          //swap(p, q); //using pointers
          swap(*p, *q); //using records
          sorted = false;
          }
      p = q; // or p = p->next
      q = q->next;
      }

    }
    while (!sorted);
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testSortByName(void)
  {
  //for (int i=0; i<TEST_COUNT; i++)
  //  {
    CPhoneBook b1('r');
    cout << "Original: " << b1;
    b1.sortByName();
    cout << "Sorted:   "<< b1;
  //  }
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
ostream & operator << (ostream &dan, const CPhoneBook &list)
  {
  CPhoneEntry *p;

  dan << "Phonebook[" << list.count << "]\n";

  p = list.first;

  while (p != NULL)
    {
    dan << p->name << ", ";
    dan << p->phone << ", ";
    dan << p->group << ", ";
    dan << p->key << endl;
    p = p->next;
    };

  return dan;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testOperatorOutput(void)
  {
  //for (int i=0; i<TEST_COUNT; i++)
  //  {
    CPhoneBook b1('r'), b2('r');
    cout << b1 << b2;
  //  }
  }


////////////////////////////////////////////////////////////
//Constructor for CPhoneBook
////////////////////////////////////////////////////////////
//'r' random elements
//'u' distinct random elements
//'s' sorted list
//'i' enter from the keyboard
CPhoneBook::CPhoneBook(char ch)
  {
  cout << "constructor called\n";
  count = 0;
  first = NULL;
  last = NULL;

  if ('r' == ch)
      {
      char rName[MAX_LEN+1];
      char rPhone[14+1];
      char rGroup[10+1];
      int  rKey;

      for(int n = rand()%(MAX_COUNT+1); n>0; n--)
        {
        strcpy(rName, testNames[rand()%MAX_NAMES]);
        strcpy(rPhone, testPhones[rand()%MAX_PHONES]);
        strcpy(rGroup, testGroups[rand()%MAX_GROUPS]);
        rKey = masterKey++;
        insertAtEnd(rName, rPhone, rGroup, rKey);
        }
      }
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testCPhoneBookConstructor(void)
  {
  for (int i=0; i<TEST_COUNT; i++)
    {
    CPhoneBook b1('r');
    b1.display();
    }
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook::~CPhoneBook(void)
  {
  cout << "destructor called\n";
  deleteAll();
  }


////////////////////////////////////////////////////////////
//void CPhoneBook::deleteAll(void)
////////////////////////////////////////////////////////////
//deletes all the nodes from the linked list
void CPhoneBook::deleteAll(void)
  {
  while (first != NULL)
    {
    last = first->next;
    delete first;
    first = last;
    }
  count = 0;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void CPhoneBook::display(void)
  {
  CPhoneEntry *p;
  cout << "Phonebook[" << count << "]\n";
  p = first;
  while (p != NULL)
    {
    cout << p->name << ", ";
    cout << p->phone << ", ";
    cout << p->group << ", ";
    cout << p->key << endl;
    p = p->next;
    };
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
bool CPhoneBook::insertAtEnd(char name[], char phone[], char group[], int key)
  {
  CPhoneEntry *p;

  p = new CPhoneEntry;
  if (NULL == p)
      return false;

  strcpy(p->name, name);
  strcpy(p->phone, phone);
  strcpy(p->group, group);
  p->key = key;
  p->next = NULL;

  if (NULL == first)
      {
      first = p;
      last  = p;
      }
    else
      {
      last->next = p;
      last = p;
      }

  count++;
  return true;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testInsertAtEnd(void)
  {
    {
    CPhoneBook myBook;
    myBook.display();
    myBook.insertAtEnd("John", "231-7000", "friend", 1);
    myBook.display();
    myBook.insertAtEnd("Tom",  "231-7001", "enemy", 1);
    myBook.display();
    }

    {
    CPhoneBook yourBook;
    yourBook.display();
    }
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook::CPhoneBook(void)
  {
  cout << "constructor called\n";
  count = 0;
  first = NULL;
  last = NULL;
  }


////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void main(void)
  {
  //testInsertAtEnd();
  //testCPhoneBookConstructor();
  //testOperatorOutput();
  //testSortByName();
  //testIsSortedByName();
  //testDisplayReverse();
  //testDisplayReverse2();
  testSearchByName();
  //testInsertAtHead();
  }