/*
 * Created by on 28.04.2015.
 * ADS SoSe 2015
 * Thema: LinearHashing mit Shell Sort
*/


#ifndef LINEARHASHING_H
#define LINEARHASHING_H

#include <iostream>
#include "Container.h"
#include <math.h>
#include <cmath>

enum status { leer,besetzt };

class LinHashException : public ContainerException {
public:
    virtual const char * what() const noexcept override { return "LinearHashing: empty"; }
};
class LinHashNotImplemented: public ContainerException{
public:
    virtual const char * what() const noexcept override{
        return "LinearHashing: Function not implemented\n";
    }
};

template <typename E, size_t N=7>
class LinearHashing : public Container<E> {
    size_t nmax;
    size_t n;
    size_t d;
    size_t nts;

    void sort() const;
    struct OverflowContainer{
        E* overflowbucket = new E[N/2]();
        status overflowstatus[N/2] = {leer};
        OverflowContainer* nextOverflow = nullptr;
        ~OverflowContainer(){
            if(nextOverflow)
                delete nextOverflow;
        }
    };
    struct Bucket{
        E* bucketElem = new E[N]();
        status bucketstatus[N] = {leer};
        OverflowContainer* newoverflow = nullptr;
    };
    Bucket* table;
public:
    LinearHashing() : nmax{N}, n{1}, d{0}, nts{0} {
        table = new Bucket[n];
    }
    LinearHashing(std::initializer_list<E> el) : LinearHashing() { for (auto e: el) add(e); }

    virtual ~LinearHashing() {
        for(size_t i = 0; i < n; ++i){
            if(table[i].newoverflow != nullptr)
                destructOverflow(i);
        }
        delete[] table;
    }

    using Container<E>::add;
    virtual void add(const E e[], size_t len) override;

    using Container<E>::remove;
    virtual void remove(const E e[], size_t len) override;

    virtual bool member(const E& e) const override;
    virtual size_t size() const override {
        return n;
    }

    virtual E min() const override;
    virtual E max() const override;

    virtual std::ostream& print(std::ostream& o) const override;

    virtual size_t apply(std::function<void(const E&)> f, Order order = dontcare) const override;
    virtual void destructOverflow(int);
    virtual void split();
    virtual inline size_t compIndex(E);
    virtual inline size_t compReIndex(E);
    virtual inline  void addToOverflow(E, OverflowContainer*);
    virtual void reHash(size_t);
    virtual void reHashOverflow(OverflowContainer*);
};

template <typename E, size_t N>
void LinearHashing<E,N>::add(const E e[], size_t len) {
    for(size_t i=0; i < len; ++i){
        size_t address = compIndex(e[i]);
        for(size_t j=0; j < N; ++j){
            if(table[address].bucketstatus[j] == leer){
                table[address].bucketElem[j] = e[i];
                table[address].bucketstatus[j] = besetzt;
                break;
            }else if(j == (N-1) && table[address].newoverflow == nullptr){
                table[address].newoverflow = new OverflowContainer();
                addToOverflow(e[i],table[address].newoverflow);
                split();
                reHash(nts);
                if(nts+1 == (pow(2, d))){
                    nts=0;
                    ++d;
                }else{
                    ++nts;
                }
            }else if(j == (N-1) && table[address].newoverflow != nullptr){
                addToOverflow(e[i],table[address].newoverflow);
            }
        }
    }
}

template <typename E, size_t N>
void LinearHashing<E,N>::split(){
    Bucket* tmp = new Bucket[size()+1];
    std::copy(table,table+size(),tmp);
    delete[] table;
    table = tmp;
    ++n;
}

template <typename E, size_t N>
void LinearHashing<E,N>::remove(const E e[], size_t len) {
    throw LinHashNotImplemented();
}

template <typename E, size_t N>
bool LinearHashing<E,N>::member(const E& e) const {
    return false;
}

template <typename E, size_t N>
E LinearHashing<E,N>::min() const {
    if (this->empty()) throw LinHashException();
    E rc = 0;
    return rc;
}

template <typename E, size_t N>
E LinearHashing<E,N>::max() const {
    if (this->empty()) throw LinHashException();
    E rc = 0;
    return rc;
}

template <typename E, size_t N>
std::ostream& LinearHashing<E,N>::print(std::ostream& o) const {
    o << "LinearHashing [ TableSize=" << n << " BucketSize=" << N << " d=" << d << " nextToSplit=" << nts << " ]\nElemente \nvalues=\n";
    for (size_t i = 0; i < n; ++i) {
        o << "Bucket[" << i << "]" << '\n';
        for (size_t j = 0; j < N; ++j) {
            o << " [" << table[i].bucketElem[j] << "] ";
        }
        o << '\n';
        if (table[i].newoverflow != nullptr) {
            o << "Overflow Bucket:\n";
            OverflowContainer *tmp = table[i].newoverflow;
            while (tmp) {
                for (int k = 0; k < (N / 2); ++k) {
                    o << " [" << tmp->overflowbucket[k] << "] ";
                }
                tmp = tmp->nextOverflow;
                o << '\n';
            }
        }
    }
    return o;
}

template <typename E, size_t N>
size_t LinearHashing<E,N>::apply(std::function<void(const E&)> f, Order order) const {
    size_t rc = 0;
    return rc;
}

template <typename E, size_t N>
void LinearHashing<E,N>::sort() const { // Achtung, O(n*n)
    /*
    for (size_t i = 0; i < n; ++i) {
        size_t min = i;
        for (size_t j = i+1; j < n; ++j)
            if (Bucket::bucketElem[min] > Bucket::bucketElem[j]) min = j;
        std::swap(Bucket::bucketElem[min], Bucket::bucketElem[i]);

    }*/
    throw LinHashNotImplemented();
}

template  <typename E, size_t N>
void LinearHashing<E, N>::destructOverflow(int index) {
    OverflowContainer* tmp = table[index].newoverflow;
    delete tmp;
    table[index].newoverflow = nullptr;
}

template <typename E, size_t N>
inline size_t LinearHashing<E, N>::compIndex(E e){
    size_t adrOP = powl(2,d);
    return hashValue(e) % adrOP;
}

template <typename E, size_t N>
size_t LinearHashing<E, N>::compReIndex(E e) {
    size_t adrOP = powl(2,d+1);
    return hashValue(e) % adrOP;
}

template <typename E, size_t N>
void LinearHashing<E, N>::addToOverflow(E e, LinearHashing::OverflowContainer *container) {
    size_t i=0;
    while( i < N/2){
        if(container->overflowstatus[i] == leer){
            container->overflowbucket[i] = e;
            container->overflowstatus[i] = besetzt;
            break;
        }else if(i == (N/2)-1 && container->nextOverflow == nullptr){
            container->nextOverflow = new OverflowContainer();
            container = container->nextOverflow;
            split();
            reHash(nts);
            if(nts+1 == (pow(2, d))){
                nts=0;
                ++d;
            }else{
                ++nts;
            }
            i=0;
        }else if(i == (N/2)-1 && container->nextOverflow != nullptr){
            container = container->nextOverflow;
            i=0;
        }else{
            ++i;
        }
    }
}
template <typename E, size_t N>
void LinearHashing<E, N>::reHash(size_t index){
    bool reHashed = false;
    for(size_t i = 0; i < N; ++i){
        if(compIndex(table[index].bucketElem[i]) != compReIndex(table[index].bucketElem[i]) && table[index].bucketstatus[i] == besetzt){
            for (size_t j = 0; j < N && !reHashed ; ++j) {
                if(table[n-1].bucketstatus[j] == leer){
                    table[n-1].bucketElem[j] = table[index].bucketElem[i];
                    table[n-1].bucketstatus[j] = besetzt;
                    table[index].bucketstatus[i] = leer;
                    table[index].bucketElem[i] = 0;
                    reHashed = true;
                }
            }
            reHashed = false;
        }
    }
    if(table[index].newoverflow != nullptr){
        reHashOverflow(table[index].newoverflow);
    }
}
template <typename E, size_t N>
void LinearHashing<E, N>::reHashOverflow(OverflowContainer* container) {
    size_t i=0;
    bool reHashed = false;
    while(i < (N/2)){
        if(compIndex(container->overflowbucket[i]) != compReIndex(container->overflowbucket[i]) && container->overflowstatus[i] == besetzt){
            for(size_t j=0; j < N && !reHashed; ++j){
                if(table[n-1].bucketstatus[j] == leer){
                    table[n-1].bucketElem[j] = container->overflowbucket[i];
                    table[n-1].bucketstatus[j] = besetzt;
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }else if(j == N-1 && table[n-1].newoverflow == nullptr){
                    table[n-1].newoverflow = new OverflowContainer();
                    addToOverflow(container->overflowbucket[i],table[n-1].newoverflow);
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }else if(j == N-1 && table[n-1].newoverflow != nullptr){
                    addToOverflow(container->overflowbucket[i], table[n-1].newoverflow);
                    container->overflowbucket[i] = 0;
                    container->overflowstatus[i] = leer;
                    reHashed = true;
                }
            }
            reHashed = false;
            ++i;
        }else{
            ++i;
        }
        if(container->nextOverflow){
            container = container->nextOverflow;
            i = 0;
        }
    }
}
#endif //LINEARHASHING_H