#include <cstdlib>
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

struct NodeChunk{
    string * val;
    NodeChunk * next;
};

struct Stack{
    int chunkSize;
    int topElt;
    NodeChunk * firstChunk;
};


NodeChunk* createNewNodeChunk (int N) {
	NodeChunk* New = new NodeChunk;
	New -> val = new string[N];
	New -> next = NULL;

	return New;
}

void initStack (int chunkSize, Stack& s) {
	s.chunkSize = chunkSize;
	s.topElt = 0;									//Change to 0s!!!
	s.firstChunk = createNewNodeChunk(chunkSize);
}

bool isEmpty (Stack s) {
	// if(s.topElt == -1 && s.firstChunk -> next == NULL){
		// return true;
	// }
	// return false;
	return s.firstChunk == NULL;
}

void push (string val, Stack& s) {
//if the firstChunk is full, create new Chunk and stick between stack and currrent firstChunk
	if (isEmpty(s)){
		s.firstChunk = createNewNodeChunk(s.chunkSize);

	}
	if (s.topElt == (s.chunkSize - 1)){
		NodeChunk* temp = createNewNodeChunk(s.chunkSize);
		temp -> next = s.firstChunk;
		s.firstChunk = temp;
		s.topElt = -1;
	}

	//cout << s.topElt << endl;
	s.topElt++;
	s.firstChunk -> val[s.topElt] = val;
	//cout << s.firstChunk -> val[s.topElt] << endl;
}

void pop (Stack& s) {
	assert(!isEmpty(s));

	if (s.topElt == 0){
		NodeChunk* temp = s.firstChunk;
		s.firstChunk = s.firstChunk -> next;
		delete[] temp -> val;
		delete temp;
		if (isEmpty(s)){
			s.topElt = -1;
		}
		else{
			s.topElt = s.chunkSize -1;
		}
	}
	else{
	s.firstChunk -> val[s.topElt] = ""; //Maybe dont need, just ignore it?
	s.topElt--;
	}
}

string top (const Stack& s) {
	assert(!isEmpty(s));

	return s.firstChunk -> val[s.topElt];
}

int size (const Stack& s) {
	int count = 0;
	NodeChunk* temp = s.firstChunk;
	while (temp -> next != NULL){
		count++;
		temp = temp -> next;
	}

	return s.topElt + 1 + count * s.chunkSize;
}

void swap (Stack& s) {
	assert(size(s) >= 2);

	//topElt is the first element in a new chunk
	if(s.topElt == 0){
		string temp2 = s.firstChunk -> val[s.topElt];
		s.firstChunk -> val[s.topElt] = s.firstChunk -> next -> val[s.chunkSize -1];
		s.firstChunk -> next -> val[s.chunkSize -1] = temp2;
	}
	else{
		//Normal Swap
		string temp2 = s.firstChunk -> val[s.topElt];
		s.firstChunk -> val[s.topElt] = s.firstChunk -> val[s.topElt - 1];
		s.firstChunk -> val[s.topElt - 1] = temp2;
	}
}

int size (const Stack& s) {
	int count = 0;
	NodeChunk* temp = s.firstChunk;
	while (temp -> next != NULL){
		count++;
		temp = temp -> next;
	}

	return s.topElt + 1 + count * s.chunkSize;
}

void print(Stack s) {
    assert(!isEmpty(s));
    NodeChunk *temp = s.firstChunk;
    for(int i = 0; i <= s.topElt; i++)
        cout << temp->val[i] << endl;
    if (temp->next == NULL)
        return;
    temp = temp->next;
    while (true) {
        for(int i = 0; i < s.chunkSize; i++)
            cout << temp->val[i] << endl;
        if (temp->next == NULL)
            break;
        temp = temp->next;
    }
    return;
}

int main (int argc, char* argv[]) {

    // Stack s;
    // initStack (3, s);
    // push("first", s);
    // push("second", s);
    // print(s);
    // swap(s);
    // print(s);



	Stack s1;
	initStack (1, s1);
	push ("a", s1);
	push ("b", s1);
	push ("c", s1);
	cout << size(s1) << endl;
	pop(s1);
	cout << top(s1) << endl;
	swap(s1);
	cout << top(s1) << endl;
	pop(s1);
	cout << top(s1) << endl;

	cout << size(s1) << endl;

}