makeup.cpp

#include <iostream>
#include <stdlib.h>
#include <cassert>
using namespace std;

struct Cat {
    int lives;
    int id;
    Cat(int in_id){
        lives = 9;
        id = in_id;
    }
};

int main() {
    srand(1983);
    Cat* theCats[2500];
    for (int i = 0; i < 2500; i++){
        theCats[i] = new Cat(rand());
    }
    
    //GOAL 1) convert this array of cats into a linked list in the same order (take away one life) (8 lives now)
    
    //adapt all of the following tests to match your code format
    for (int i=0; i < 2500; i++){
        nextNode = nextNode->next; //structure this test to match your linked list format
        assert(theCats[i]->id == nextNode->cat->id); //same here
        assert(nextNode->cat->lives == 8); //likewise
    }
    
    //GOAL 2) reverse that linked list (take away one life) (7 lives now)
    yourLinkedList.reverse(); // or however you are calling it
    for (int i=0; i < 2500; i++){
        nextNode = nextNode->next; //structure this test to match your linked list format
        assert(theCats[2499-i]->id == nextNode->cat->id); //same here
        assert(nextNode->cat->lives == 7); //likewise adjust
    }
    
    //GOAL 3) convert that linked list back to an array of cats (take away one life) (6 lives now)
    Cat** catArray = yourLinkedList.makeCatArray(); // or however you are calling it
    for (int i=0; i < 2500; i++){
        assert(theCats[2499-i]->id == catArray[i]->id); //adjust to your code
        assert(catArray[i]->lives == 6); //likewise
    }
    
    //GOAL 4) convert that array of cats into a heap in-place (largest id first) in linear time (take away one life) (5 lives now)
    heapify(catArray) //or whatever
    for (int i=0; 2*i+2 < 2500; i++){
        assert(catArray[i]->id >= catArray[2*i+1]->id); //adjust to your code
        assert(catArray[i]->id >= catArray[2*i+2]->id); //adjust to your code
        assert(catArray[i]->lives == 5); //likewise
    }    
    
    //GOAL 5) in index order of that heap insert the cats into a binary search tree (take away one life) (4 lives now)
    // (If there are repeated ids then just ignore the second one so there might be less than 2500 cats now.)
    BST* yourRoot = new BST(); //or whatever
    for(int i=0; i < 2500; i++){
        yourRoot = yourRoot.insert(catArray[i]); //or whatever
    }
    assert(yourRoot->left->maximum()->cat->id < yourRoot->cat->id); //again make it match your choices
    assert(yourRoot->right->minimum()->cat->id > yourRoot->cat->id); //match your choices
    
    //GOAL 6) compute the height of that binary search tree
    cout << yourBST.computeHeight() << endl; //match your choices
     
    for (int i=0; i < 2500; i++){
        delete theCats[i];
    }
    
    //clean whatever you need to here
    
}