Programming 102, test 2, Ahsan Zahid

// Ahsan Zahid
// Math/CS 102
// Test 2

// 1.

// a)
// Creating a new pointer array of integers, fill with -1.
int *p = new int[100];
for(int x=0; x<100; x++){
    p[x] = -1;
}

// b)
//Allocate numbers to A, spaces to B, then 9-x is reverse order in the loop.
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int B[10];
for(int x =0; x<10; x++){
    B[x] = A[(9-x)];
}

// c)
// Some data already in p; so delete the contents of p, then reassign the pointer to &x;
int *p = new int(5);
int x = 10;
cout<<p<<" "<<*p<<endl;
cout<<&x<<" "<<x<<endl;

delete p;
p = &x;
cout<<p <<" "<<*p;

// d
// Both p and q point to dynamically alocated int 5. Delete either, then set both to the null pointer.
int *p = new int(5);
int *q = p;
cout <<*p<<" "<<*q<<" "<<p<<" "<<q<<endl;
delete p;
p = nullptr;
q = nullptr;
cout<<p<<" "<<q;

// e)
// declare struct, then point both nodes at m.
struct node{int n; node* p;};
node n,m;
// ...
n.p = &m;
m.p = &m;
cout<<n.p<<" "<<m.p<<endl;

// 2.
// a)
    // i) {2, 3, 4}
    // ii) {2, 3, 4}
    // iii) {4.6, 5.0, 8.2}
    // iv) {"Dog", "cat", "dog"}
// b
template <class T> void fcnB(T& a, T&b, T&c, bool compare(T& a, T&b)){
    if(a.compare(b)) swap(a,b);
    if(b.compare(c)) swap(b,c);
    if(a.compare(b)) swap(a,b);
}

// 3.
// a)
// Need a method to pop. To pop, take the last element, get rid of it, and shrink the vector.
void pop() {
        //Only remove if there is at least one element actually in the array.
        if ((avail-1) != begin()){
            //Temp contains  reference to the last pointer with something there.
            T* temp = data[(avail-1)];
            //Get rid of whatever is at temp.
            alloc.deallocate(temp);
            //Set avail one back, so it now points to the empty space we just created.
            --avail;

        }
    }

// b) To act as just a stack class, the [] operator is not needed, so long as the beginning and ending iterators are known and can be accessed. Any methods that access the interior of the vector (which aren't needed by other methods) can be taken out, as a stack only deals with the ending and sometimes starting elements.

// c) If our goal is just to return the top element... We just get it from data. If we start at data, go up to avail, and then go back one, we'll have arrived at the last/top element in the vector. We want the actual element, so we deference it.
T getTopElement(){
    return *data[(avail-1)];
}

// 4.

// a) If n is odd, the parent is (n-1)/2. If n is even, parent is (n-2)/2

// b) In the given implementation, there's no definition as to what to do if the value to be searched does not exist in the tree. Will it return null? Will it create the node? Nothing is defined. Also it uses a single pointer for the tree, so it seems it can only really hold one node.

// c)
    // i)
    // If pt has the tree above, pt.ptr[3] would refer to 6. pt.prt[4] would need to be null, or some other sentinel defining the lack of a node at that space.

    // ii)
    // First off, this uses an array of pointers, so it can hold more than one node. Also, the search function (as it claims, at least...) will point to where a number SHOULD be, if it does not actually exist in the tree.

    // iii)
size_t search(T){
    n=0;
    while(true){
        if(T>*pTr[n]) n = 2*n+2;
        else if(T<*pTr[n]) n = 2*n+1;
        //If there's nothing at that value.. then go ahead and return T.
        if(!pTr[n]){
            return n;
        }
        //if the thing at that node is T, then by George, we've found it! Return the position!
        if(*pTr[n]==T){
            return n;
        }
        //But if not, then do this same thing again from the new part of the tree.
    }

}

size_t insert(T){
    n=0;
    while(true){
        if(T>*pTr[n]) n = 2*n+2;
        else if(T<*pTr[n]) n = 2*n+1;
        //If there's nothing at that value.. then put T there.
        if(!pTr[n]){
            pTr[n] = &T;
            return n;
        }
        //if the thing at that node is T, then it's already there. Just return the index.
        if(*pTr[n]==T){
            return n;
        }
        //But if we haven't found the right place yet, then do this same thing again from the new part of the tree.
    }

}