#include <cstdlib>
#include <iostream>

#include "Colectie.h"

using std::cout;

Colectie::Colectie() {
    elements = NULL;
    nextElements = NULL;
    total = 0;
    capacity = 0;
    firstFree = 0;

    expand(SIZE_FACTOR);
}

void Colectie::expand(int newCapacity) {
    // keep a pointer to the old vectors
    TElem* oldElements = elements;
    int* oldNextElements = nextElements;
    int oldCapacity = capacity;

    // alocate new vectors
    TElem* newElements = static_cast<TElem*>(malloc(sizeof(TElem) * (newCapacity)));
    int* newNextElements = static_cast<int*>(malloc(sizeof(int) * (newCapacity)));

    // initialize the whole new vectors
    for (int i = 0; i < newCapacity; i++) {
        newElements[i] = MISSING_VALUE;
        newNextElements[i] = MISSING_POSITION;
    }

    // assign the new vectors to use the innerAdd function we already have
    elements = newElements;
    nextElements = newNextElements;
    capacity = newCapacity;

    // re-add each element in the old vector
    for (int i = 0; i < oldCapacity; i++) {
        TElem element = oldElements[i];
        innerAdd(element);
    }

    // if capacity is 0, this is the initial expand
    // so don't do anything to the contents of the old vectors
    if (oldCapacity != 0) {
        free(oldElements);
        free(oldNextElements);
    }
}

int Colectie::findFirstFree() {
    int position = 0;
    while (true) {
        if (position == capacity) {
            // we filled the list, there are no left positions
            // set the next free position to the old capacity
            // the list will be exanded on the next add
            position = capacity;
            break;
        }

        // we found the firs tposition without value
        if (elements[position] == MISSING_VALUE) {
            break;
        }

        position++;
    }

    return position;
}

int Colectie::hash(TElem element) const {
    return abs(element % capacity);
}

void Colectie::print() const {
    cout << "START PRINT\n";
    for (int i = 0; i < capacity; i++) {
        if (elements[i] != MISSING_VALUE)
            cout << i << "\t";
    }
    cout << "\n";

    for (int i = 0; i < capacity; i++) {
        if (elements[i] != MISSING_VALUE)
            cout << elements[i] << "\t";
    }
    cout << "\n";

    for (int i = 0; i < capacity; i++) {
        if (elements[i] != MISSING_VALUE)
            cout << nextElements[i] << "\t";
    }
    cout << "\n";
    cout << "END PRINT\n";
}

void Colectie::innerAdd(TElem element) {
    // we want to put our element at the position of our hash
    int targetPosition = hash(element);

    if (elements[targetPosition] != MISSING_VALUE) {
        // the position of our hash is not empty
        // find the last position of elements sitting at our hash
        // since we need to make it point to our target position
        // which is the first free position
        int previousPosition = targetPosition;

        while (true) {
            // we found the last element in the chain
            if (nextElements[previousPosition] == MISSING_POSITION) {
                break;
            }

            // advance a position
            previousPosition = nextElements[previousPosition];
        }

        // make sure the last element in the chain points at
        // the target position
        targetPosition = firstFree;
        nextElements[previousPosition] = firstFree;
    }

    elements[targetPosition] = element;

    // our target position might have been the first free position
    // find it again
    if (targetPosition == firstFree) {
        firstFree = findFirstFree();
    }
}

void Colectie::add(TElem element) {
    if (total == capacity) {
        expand(capacity * SIZE_FACTOR);
    }

    innerAdd(element);
    total += 1;
}

bool Colectie::elementExists(TElem element) const {
    int targetPosition = hash(element);

    while (true) {
        if (elements[targetPosition] == element) {
            // we found our element in the chain
            return true;
        }

        if (nextElements[targetPosition] == MISSING_POSITION) {
            // we reached the end of the chain
            return false;
        }

        targetPosition = nextElements[targetPosition];
    }
}

int Colectie::getElementPosition(TElem element) const {
    int targetPosition = hash(element);

    while (true) {
        if (elements[targetPosition] == element) {
            break;
        }

        targetPosition = nextElements[targetPosition];
    }

    return targetPosition;
}

int Colectie::getPositionBefore(int position) const {
    int previousPosition = MISSING_POSITION;

    for (int i = 0; i < capacity; i++) {
        if (nextElements[i] == position) {
            previousPosition = i;
            break;
        }
    }

    return previousPosition;
}

int Colectie::getPositionAfter(int position) const {
    int nextPosition = nextElements[position];
    return nextPosition;
}

void Colectie::pullNextElementsBack(int position) {
    int nextPosition = nextElements[position];

    while (true) {
        elements[position] = elements[nextPosition];

        if (nextElements[nextPosition] == MISSING_POSITION) {
            // the next element is the end of the chain
            // and we already pulled it's value
            // we can skip to clearing the value
            // and making the previous element not point to anything
            break;
        }

        // advance a position
        position = nextPosition;
        nextPosition = nextElements[nextPosition];
    }

    elements[nextPosition] = MISSING_VALUE;
    nextElements[position] = MISSING_POSITION;
}

bool Colectie::remove(TElem element) {
    if (!elementExists(element)) {
        // element is not in the chain
        return false;
    }

    int targetPosition = getElementPosition(element);
    int previousPosition = getPositionBefore(targetPosition);
    int nextPosition = getPositionAfter(targetPosition);

    if (nextPosition == MISSING_POSITION && previousPosition == MISSING_POSITION) {
        // element is the only one in the chain
        elements[targetPosition] = MISSING_VALUE;
    } else if (nextPosition == MISSING_POSITION) {
        // element is the last one in the chain
        elements[targetPosition] = MISSING_VALUE;
        nextElements[previousPosition] = MISSING_POSITION;
    } else {
        // element can be the first in the chain
        // and cannot be the last one in the chain
        // so we can pull the next value back
        pullNextElementsBack(targetPosition);
    }

    total -= 1;
    return true;
}

int Colectie::occurances(TElem element) const {
    int targetPosition = hash(element);
    int n = 0;

    while (true) {
        if (elements[targetPosition] == element) {
            n++;
        }

        if (nextElements[targetPosition] == MISSING_POSITION) {
            break;
        }

        targetPosition = nextElements[targetPosition];
    }

    return n;
}

int Colectie::size() const {
    return total;
}

void Colectie::adauga(TElem element) {
    add(element);
}

bool Colectie::sterge(TElem element) {
    return remove(element);
}

int Colectie::nrAparitii(TElem element) const {
    return occurances(element);
}

bool Colectie::cauta(TElem element) const {
    return elementExists(element);
}

int Colectie::dim() const {
    return size();
}

bool Colectie::vida() const {
    return size() == 0;
}

Colectie::~Colectie() {
    free(elements);
    free(nextElements);
}

IteratorColectie Colectie::iterator() {
    return IteratorColectie(this);
}