#include <string>
#include <iostream>
#include <assert.h>

class sortable
{ public:
    virtual string get_key() = 0; // The "= 0" makes it Pure Virtual
      // anything that inherits sortable is forced to define its own
      // get_key method.
};

// This function (a nasty cheap bubble sort) will sort an array
// of pointers to absolutely anything, so long as those things
// all inherit sortable and provide their own get_key()

void sort(sortable * * A, int N)
{ assert(A != NULL);
  for (int i = N-1; i > 0; i -= 1)
  { for (int j = 0; j < i; j += 1)
    { if (A[j]->get_key() > A[j+1]->get_key())
      { sortable * t = A[j];
        A[j] = A[j+1];
        A[j+1] = t; } } } }

class person: public sortable   // so now our people are sortable
{ public:
    string fname, lname, address, phone;
    virtual string get_key();
    person(string f, string l, string a, string p);
    virtual void print(); };

person::person(string f, string l, string a, string p):
        fname(f), lname(l), address(a), phone(p)
{ }

void person::print()
{ cout << fname << " " << lname << 
          ", of " << address << 
          ", phone " << phone; }

string person::get_key()
{ return lname; }

class employee: public person
{ public:
    string salary, position;
    employee(string f, string l, string a, string p, string s, string n);
    virtual void print(); };

employee::employee(string f, string l, string a, string p, string s, string n):
        person(f, l, a, p), salary(s), position(n)
{ }

void employee::print()
{ person::print();
  cout << "\n    $" << salary << ", " << position; }

class criminal: public person
{ public:
    string crime;
    criminal(string f, string l, string a, string p, string c);
    virtual void print(); };

criminal::criminal(string f, string l, string a, string p, string c):
        person(f, l, a, p), crime(c)
{ }

void criminal::print()
{ cout << crime << ": ";
  person::print(); }

class banker: public criminal
{ public:
    string amount;
    banker(string f, string l, string a, string p, string ae);
    virtual void print(); };

banker::banker(string f, string l, string a, string p, string ae):
        criminal(f, l, a, p, "fraud"), amount(ae)
{ }

void banker::print()
{ person::print();
  cout << ", a banker"; }

class contact_list
{ public:
    person * * data;
    int num;
    contact_list();
    contact_list(const contact_list & B);
    contact_list & operator=(const contact_list & B);
    ~contact_list(); 
    void add(person * p);
    void print_all(); };

contact_list::contact_list()
{ num = 0;
  data = new person * [20]; }

contact_list::~contact_list()
{ // it is the data structure that is disappearing, so all of its parts
  // should be tidied up. But the fact that the container is going away
  // does not mean that all the things it contains are also going. It
  // is not usual to delete data[0], data[1], etc here.
  delete [] data; }

void contact_list::add(person * p)
{ if (num >= 20) return;
  data[num] = p;
  num += 1; }

void contact_list::print_all()
{ for (int i = 0; i < num; i += 1)
  { cout << i << ": ";
    data[i]->print();
    cout << "\n"; } }

contact_list & contact_list::operator=(const contact_list & B)
{ num = B.num;
  delete [] data;
  data = new person * [20];
  for (int i=0; i<num; i+=1)
    data[i] = B.data[i];
  return * this; }

contact_list::contact_list(const contact_list & B)
{ num = B.num;
  data = new person * [20];
  for (int i=0; i<num; i+=1)
    data[i] = B.data[i]; }

void main()
{ contact_list A, B;
  A.add(new person("Lavinia", "Leopard", "55 Frog St.", "4046662233"));
  A.add(new person("Jim", "James", "987 Horse Rd.", "7364536475"));
  A.add(new person("Joe", "Jones", "123 Cat St.", "3051112222"));
  A.add(new person("Jemimah", "Jones", "123 Cat St.", "3051112222"));
  A.add(new person("Jimmy", "Jones", "123 Cat St.", "3051234321"));
  A.add(new person("Jilly", "Jones", "123 Cat St.", "3053242315"));
  A.add(new person("Anathema", "Hamsoup", "234 Dog Av.", "3057651243"));
  A.add(new employee("Colin", "Nostril", "234 Dog Av.", "9765432124", "34500", "manager"));
  A.add(new employee("Evangelina", "Smith", "17 Ant St.", "7253981256", "64250", "designer"));
  A.add(new employee("Lumpy", "Morris", "550 Bee St.", "7352749812", "52000", "secretary"));
  A.add(new employee("Ravioli", "Johnson", "99 Bat St.", "6364858272", "57500", "typist"));
  A.add(new criminal("Knuckles", "Badman", "77 Dark Lane", "9875674532", "burglary"));
  A.add(new criminal("Basher", "McRough", "245 Dog St.", "8272636451", "assault"));
  A.add(new criminal("Murgatroyd", "Madd", "591 Eel Way", "3547852371", "murder"));
  A.add(new banker("Arthur", "Arthropod-Smythe", "3 Rich Road", "1426378491", "57000000"));
  A.add(new banker("Melinda", "Machiavelli", "1 1st St.", "9872436472", "72500000"));
  B = A;
  contact_list C = A;
  A.data[9] = new person("A", "Person", "under the underpass", "411");
  A.print_all();
  B.print_all();
  sort((sortable * *)(C.data), C.num);
    // Oh dear. It's just something you have to do. Even though sort takes
    // a sortable** parameter, and C.data is a person**, and every person
    // is explicitly defined to be a kind of sortable, C++ won't accept it.
    // You have to do a type-cast, and it won't even allow a nice safe
    // dynamic_cast<>
  C.print_all(); }