#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;
	s.firstChunk = NULL;
}

bool isEmpty (Stack s) {
	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);
		s.firstChunk -> val[s.topElt] = val;
	}
	else{
		if (s.topElt == (s.chunkSize - 1)){
			s.topElt = 0;
			NodeChunk* temp = createNewNodeChunk(s.chunkSize);
			temp -> val[s.topElt] = val;
			temp -> next = s.firstChunk;
			s.firstChunk = temp;

		}
		else{
			s.topElt++;
			s.firstChunk -> val[s.topElt] = val;
		}
	}
}

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;
		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) {
	if (isEmpty(s))
        return 0;
    int counter = s.topElt + 1;
    if (s.firstChunk->next == NULL)
        return counter;
    NodeChunk *temp = s.firstChunk->next;
    while(true) {
        counter += s.chunkSize;
        if (temp->next == NULL)
            break;
        temp = temp->next;
    }
    return counter;
}

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

	//topElt is the first element in a new chunk
	if(s.topElt == 0 && s.firstChunk -> next != NULL){
		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;
	}
}

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;

}