Question

lineage program to Memheck-clean. The program is a simplified family tree manager. It maintains a list of Persons in a PersonList. Each Person object maintains a set of pointers to his/her parents as well as to his/her children. The code contains several memory leaks. To compile:

please highlight the changes

$g++ -g -O0 -fno-inline *.cpp -o lineage

code

linage.cpp

// Adapted from http://people.cs.ksu.edu/~sherrill/labs/lab05/lineage.cpp
#include "person.h"
#include "personList.h"

int main() {
    PersonList theList;

    theList.addPerson("Bob", "Mark", "Betty");
    theList.addPerson("Jim", "Bob", "Sally");
    theList.addPerson("Frank", "Jim", "Mary");
    theList.addPerson("Leonard", "Jim", "Mary");
    theList.addPerson("Kim", "Leonard", "Sarah");

    theList.printLineage("Jim");
    theList.printLineage("Kim");
    theList.printLineage("Betty");

    return 0;
}

/* Output (your revised solution should give the same output)
Ancestors of Jim
mother: Sally
father: Bob
grand mother: Betty
grand father: Mark

Decendents of Jim
child: Frank
child: Leonard
grand child: Kim

Ancestors of Kim
mother: Sarah
father: Leonard
grand mother: Mary
grand father: Jim
great grand mother: Sally
great grand father: Bob
great great grand mother: Betty
great great grand father: Mark

Decendents of Kim

Ancestors of Betty

Decendents of Betty
child: Bob
grand child: Jim
great grand child: Frank
great grand child: Leonard
great great grand child: Kim
*/

person.cpp

#include "person.h"
#include
#include

using std::cout;
using std::endl;

Person::Person(char *name, Person* father, Person* mother){
    this->name = new char[strlen(name)];
    strcpy(this->name, name);
    this->father = father;
    this->mother = mother;
    capacity = 1;
    numChildren = 0;
    children = new Person*[capacity];
}

Person::~Person(){
    delete children;
}

void Person::addChild(Person *newChild){
    if(numChildren == capacity) expand(&children, &capacity);
    children[numChildren++] = newChild;
}

void Person::printAncestors(){
    cout << endl << "Ancestors of " << name << endl;
    printLineage('u', 0);
}

void Person::printDecendents(){
    cout << endl << "Decendents of " << name << endl;
    printLineage('d', 0);
}

void Person::printLineage(char dir, int level){
    char *temp = compute_relation(level);

    if(dir == 'd'){
        for(int i = 0; i < numChildren; i++){
            cout << temp << "child: " << children[i]->getName() << endl;
            children[i]->printLineage(dir, level + 1);
        }
    } else {
        if(mother){
            cout << temp << "mother: " << mother->getName() << endl;
            mother->printLineage(dir, level + 1);
        }
        if(father){
            cout << temp << "father: " << father->getName() << endl;
            father->printLineage(dir, level + 1);
        }
    }
}

/* helper function to compute the lineage
* if level = 0 then returns the empty string
* if level >= 1 then returns ("great ")^(level - 1) + "grand "
*/
char* Person::compute_relation(int level){
    if(level == 0) return strcpy(new char[1], "");

    char *temp = strcpy(new char[strlen("grand ") + 1], "grand ");;
  
    for(int i = 2; i <= level; i++){
        char *temp2 = new char[strlen("great ") + strlen(temp) + 1];
        strcat(strcpy(temp2, "great "), temp);
        temp = temp2;
    }
    return temp;
}

/* non-member function which doubles the size of t
* NOTE: t's type will be a pointer to an array of pointers
*/
void expand(Person ***t, int *MAX){
Person **temp = new Person*[2 * *MAX];
memcpy(temp, *t, *MAX * sizeof(**t));
*MAX *= 2;
*t = temp;
}

person.h

#ifndef __PERSON_H__
#define __PERSON_H__

class Person{
    private:
        char *name;
        Person *father; // pointer to the father
        Person *mother; // pointer to the mother
        Person **children; // array of pointers to the kids
        int numChildren; // number of kids in children array
        int capacity; // capacity of children array

    public:
        Person(char *name, Person* father, Person* mother);
        ~Person();

        const char* getName(){return name;}

        void addChild(Person *newChild);

        void printAncestors();
        void printDecendents();

    private:
        void printLineage(char dir, int level);
        /* helper function to compute the lineage
         * if level = 0 then returns the empty string
         * if level >= 1 then returns ("great ")^(level - 1) + "grand "
         */
        char* compute_relation(int level);
};
/* non-member function which doubles the size of t
* NOTE: t's type will be a pointer to an array of pointers
*/
void expand(Person ***t, int *MAX);

#endif // __PERSON_H__

personList.cpp

#include "personList.h"
#include
#include

using std::cout;
using std::endl;

PersonList::PersonList(){
    capacity = 2;
    numPeople = 0;
    theList = new Person*[capacity];
}

PersonList::~PersonList(){
    delete [] theList;
}

void PersonList::addPerson(char* child_name, char* father_name, char* mother_name){
    Person *father = 0;
    Person *mother = 0;
  
    // try to find the three names in the theList
    for(int i = 0; i < numPeople; i++){
        if(!strcmp(theList[i]->getName(), child_name)){
            cout << "ERROR: " << child_name << " already has parents!!!";
            return;
        } else if(!strcmp(theList[i]->getName(), father_name)) {
            father = theList[i];
        } else if(!strcmp(theList[i]->getName(), mother_name)) {
            mother = theList[i];
        }
    }

    if(father == 0){
      // father_name is not in the theList so create a new person
      father = new Person(father_name, 0, 0);
      insertIntoList(father);
    }
    if(mother == 0){
      // mother_name is not in the theList so create a new person
      mother = new Person(mother_name, 0, 0);
      insertIntoList(mother);
    }
    Person *newChild = new Person(child_name, father, mother);
    insertIntoList(newChild);
    father->addChild(newChild);
    mother->addChild(newChild);
}

void PersonList::insertIntoList(Person *newPerson){
    if(numPeople == capacity) expand(&theList, &capacity);

    theList[numPeople++] = newPerson;
}

void PersonList::printLineage(char* person){
    for(int i = 0; i < numPeople; i++) {
        if(!strcmp(theList[i]->getName(), person)){
            theList[i]->printAncestors();
            theList[i]->printDecendents();
            return;
        }
    }
    cout << endl << person << " is not in the list!" << endl;
}

personList.h

#ifndef __PERSONLIST_H__
#define __PERSONLIST_H__
#include "person.h"

class PersonList{
    private:
      Person **theList; // array of pointers to person objects
      int numPeople; // current number of people in theList
      int capacity; // capacity of theList array

    public:
        PersonList();
        ~PersonList();
        void addPerson(char* child_name, char* father_name, char* mother_name);
        void insertIntoList(Person *newPerson);
        void printLineage(char* person);
};
#endif // __PERSONLIST_H__

Answer 1

// LINAGE.CPP

// Adapted from http://people.cs.ksu.edu/~sherrill/labs/lab05/lineage.cpp
#include "person.h"
#include "personList.h"

int main() {
    PersonList theList;

    theList.addPerson("Bob", "Mark", "Betty");
    theList.addPerson("Jim", "Bob", "Sally");
    theList.addPerson("Frank", "Jim", "Mary");
    theList.addPerson("Leonard", "Jim", "Mary");
    theList.addPerson("Kim", "Leonard", "Sarah");

    theList.printLineage("Jim");
    theList.printLineage("Kim");
    theList.printLineage("Betty");

    return 0;
}

/* Output (your revised solution should give the same output)
Ancestors of Jim
mother: Sally
father: Bob
grand mother: Betty
grand father: Mark

Decendents of Jim
child: Frank
child: Leonard
grand child: Kim

Ancestors of Kim
mother: Sarah
father: Leonard
grand mother: Mary
grand father: Jim
great grand mother: Sally
great grand father: Bob
great great grand mother: Betty
great great grand father: Mark

Decendents of Kim

Ancestors of Betty

Decendents of Betty
child: Bob
grand child: Jim
great grand child: Frank
great grand child: Leonard
great great grand child: Kim
*/


// PERSON.CPP

#include "person.h"
#include<iostream>
#include<string.h>

using std::cout;
using std::endl;

Person::Person(const char *name, Person* father, Person* mother){
    this->name = new char[strlen(name)];
    strcpy(this->name, name);
    this->father = father;
    this->mother = mother;
    capacity = 1;
    numChildren = 0;
    children = new Person*[capacity];
}

Person::~Person(){
    delete children;
    delete name;
}

void Person::addChild(Person *newChild){
    if(numChildren == capacity) expand(&children, &capacity);
    children[numChildren++] = newChild;
}

void Person::printAncestors(){
    cout << endl << "Ancestors of " << name << endl;
    printLineage('u', 0);
}

void Person::printDecendents(){
    cout << endl << "Decendents of " << name << endl;
    printLineage('d', 0);
}

void Person::printLineage(char dir, int level){
    char *temp = compute_relation(level);

    if(dir == 'd'){
        for(int i = 0; i < numChildren; i++){
            cout << temp << "child: " << children[i]->getName() << endl;
            children[i]->printLineage(dir, level + 1);
        }
    } else {
        if(mother){
            cout << temp << "mother: " << mother->getName() << endl;
            mother->printLineage(dir, level + 1);
        }
        if(father){
            cout << temp << "father: " << father->getName() << endl;
            father->printLineage(dir, level + 1);
        }
    }
}

/* helper function to compute the lineage
* if level = 0 then returns the empty string
* if level >= 1 then returns ("great ")^(level - 1) + "grand "
*/
char* Person::compute_relation(int level){
    if(level == 0) return strcpy(new char[1], "");

    char *temp = strcpy(new char[strlen("grand ") + 1], "grand ");;
  
    for(int i = 2; i <= level; i++){
        char *temp2 = new char[strlen("great ") + strlen(temp) + 1];
        strcat(strcpy(temp2, "great "), temp);
        temp = temp2;
        delete[] temp2;   // change
    }
    return temp;
}

/* non-member function which doubles the size of t
* NOTE: t's type will be a pointer to an array of pointers
*/

void expand(Person ***t, int *MAX){
    Person **temp = new Person*[2 * *MAX];
    memcpy(temp, *t, *MAX * sizeof(**t));
    delete[] *t;   // change
    *MAX *= 2;
    *t = temp;
}

// PERSONLIST.CPP


#include "personList.h"
#include<iostream>
#include<string.h>

using std::cout;
using std::endl;

PersonList::PersonList(){
    capacity = 2;
    numPeople = 0;
    theList = new Person*[capacity];
}

PersonList::~PersonList(){
    delete [] theList;
}

void PersonList::addPerson(const char* child_name, const char* father_name, const char* mother_name){
    Person *father = 0;
    Person *mother = 0;
  
    // try to find the three names in the theList
    for(int i = 0; i < numPeople; i++){
        if(!strcmp(theList[i]->getName(), child_name)){
            cout << "ERROR: " << child_name << " already has parents!!!";
            return;
        } else if(!strcmp(theList[i]->getName(), father_name)) {
            father = theList[i];
        } else if(!strcmp(theList[i]->getName(), mother_name)) {
            mother = theList[i];
        }
    }

    if(father == 0){
      // father_name is not in the theList so create a new person
      father = new Person(father_name, 0, 0);
      insertIntoList(father);
    }
    if(mother == 0){
      // mother_name is not in the theList so create a new person
      mother = new Person(mother_name, 0, 0);
      insertIntoList(mother);
    }
    Person *newChild = new Person(child_name, father, mother);
    insertIntoList(newChild);
    father->addChild(newChild);
    mother->addChild(newChild);
}

void PersonList::insertIntoList(Person *newPerson){
    if(numPeople == capacity) expand(&theList, &capacity);

    theList[numPeople++] = newPerson;
}

void PersonList::printLineage(const char* person){
    for(int i = 0; i < numPeople; i++) {
        if(!strcmp(theList[i]->getName(), person)){
            theList[i]->printAncestors();
            theList[i]->printDecendents();
            return;
        }
    }
    cout << endl << person << " is not in the list!" << endl;
}


// PERSON.H



#ifndef __PERSON_H__
#define __PERSON_H__

class Person{
    private:
        char *name;
        Person *father; // pointer to the father
        Person *mother; // pointer to the mother
        Person **children; // array of pointers to the kids
        int numChildren; // number of kids in children array
        int capacity; // capacity of children array

    public:
        Person(const char *name, Person* father, Person* mother);
        ~Person();

        const char* getName(){return name;}

        void addChild(Person *newChild);

        void printAncestors();
        void printDecendents();

    private:
        void printLineage( char dir, int level);
        /* helper function to compute the lineage
         * if level = 0 then returns the empty string
         * if level >= 1 then returns ("great ")^(level - 1) + "grand "
         */
        char* compute_relation(int level);
};
/* non-member function which doubles the size of t
* NOTE: t's type will be a pointer to an array of pointers
*/
void expand(Person ***t, int *MAX);

#endif // __PERSON_H__



// PERSONLIST.H

#ifndef __PERSONLIST_H__
#define __PERSONLIST_H__
#include "person.h"

class PersonList{
    private:
      Person **theList; // array of pointers to person objects
      int numPeople; // current number of people in theList
      int capacity; // capacity of theList array

    public:
        PersonList();
        ~PersonList();
        void addPerson(const char* child_name, const char* father_name, const char* mother_name);
        void insertIntoList(Person *newPerson);
        void printLineage(const char* person);

};
#endif // __PERSONLIST_H__

just copy all the code into respective files.

***** ensure that code is copied correctly *******

command to run

g++ linage.cpp person.cpp personList.cpp

./a.out