/**
 * @package flib
 */
#ifndef F_LIST_IMPL_H_
#define F_LIST_IMPL_H_

#include "flist_def.h"
#include "fexception.h"

//#define ENABLE_FLIST_LOGGING
#ifdef ENABLE_FLIST_LOGGING
    #include <stdio.h>
#endif

//===========================================================================
//                          Exceptions
//===========================================================================
//---------------------------------------------------------------------------
class FVectorException : public FException {
public:
    	FVectorException(const char *_fmt, ...) {
	    	va_list arg;
		    va_start(arg, _fmt);
    		init("FVectorException", _fmt, arg);
	    	va_end(arg);
    	}
};
//---------------------------------------------------------------------------
class FListException : public FException {
public:
    	FListException(const char *_fmt, ...) {
	    	va_list arg;
		    va_start(arg, _fmt);
    		init("FListException", _fmt, arg);
	    	va_end(arg);
    	}
};
//===========================================================================

//===========================================================================
//                          FVector
//===========================================================================
//---------------------------------------------------------------------------
template<class T>
void FVector<T>::IncrRefCnt()
{
    if(fRefCnt == INT_MAX)
        throw FVectorException("IncrRefCnt() - RefCnt==INT_MAX.");
    fRefCnt++;
}
//---------------------------------------------------------------------------
template<class T>
void FVector<T>::DecrRefCnt()
{
    if(fRefCnt <= 0)
        throw FVectorException("DecrRefCnt() - RefCnt==0, implementation error.");
    fRefCnt--;
}

//---------------------------------------------------------------------------
template<class T>
T* FVector<T>::Pointer(flist_ix_t ix) const
/// vraci ukazatel na ix-ty prvek FVectoru
{
    if(ix < 0) ix = Cnt() + ix;
    if(ix >= Cnt())
        throw FVectorException("item(%u) - index out of range!", ix);
    return vector + ix;
}

//---------------------------------------------------------------------------
template<class T>
void FVector<T>::setCapacity(flist_ix_t newcnt)
{
    if(Capacity() == newcnt) return;
    if(RefCnt() != 1)
        throw FVectorException("FVector<T>::setCapacity(%u) - RefCnt() != 1.", newcnt);
    vector = (T*)realloc(vector, newcnt * sizeof(T));
    fCapacity = newcnt;
    if(vector == NULL && newcnt != 0)
        throw FVectorException("FVector<T>::setCapacity(%u) - realloc() failed.", newcnt);
    if(Cnt() > Capacity()) fCnt = newcnt;
}
//--------------------------------------------------------------
template<class T>
void FVector<T>::setCnt(flist_ix_t newcnt)
{
    if(Cnt() == newcnt) return;
    if(RefCnt() != 1)
        throw FVectorException("FVector<T>::setCnt(%u) - RefCnt() != 1", newcnt);
    if(Capacity() < newcnt) {
        flist_ix_t needlen = newcnt * sizeof(T);
        flist_ix_t alloccnt;
        for(alloccnt = INDEX_BLOCK_LEN; alloccnt < needlen; alloccnt <<= 1);
        alloccnt /= sizeof(T);
        setCapacity(alloccnt);
    }
    fCnt = newcnt;
}
// ----------------------------------------------------------------------
template<class T>
void FVector<T>::Shrink()
{
    setCapacity(Cnt()); // nejprimitivnejsi verze
/*
    if(Cnt() == 0) {
        delete[] vector;
        vector = (T*)NULL;
        fCapacity = 0;
    }
    else {
        // pokud je pole male, alokuje se vetsinou po mocninach dvou
        // zavisi to na implementaci malloc v knihovne
        // proto nebudu prealokovavat pole mensi nez SHRINK_TRASHOLD
        // pokud to nebude alspon o polovicku
        unsigned needlen = Cnt() * sizeof(T);
        unsigned alloclen = Capacity() * sizeof(T);
        if(needlen <= SHRINK_TRASHOLD && 2*needlen > alloclen) {
            // v tomto pripade se nic neprealokovava,
            // protoze bychom tim zadnou pamet neusetrili
        }
        else {
            if(needlen <= SHRINK_TRASHOLD) {
                // zarovnej pozadovanou pamet na mocninu 2
                for(fCapacity=1; fCapacity < needlen; fCapacity <<= 1);
                fCapacity /= sizeof(T);
            }
            else {
                fCapacity = Cnt();
            }
            T *oldarray = vector;
            vector = new T[Capacity()];
            for(unsigned u=0; u<Cnt(); u++) vector[u] = oldarray[u];
            delete[] oldarray;
        }
    }                     */
}
//--------------------------------------------------------------
template<class T>
void FVector<T>::Insert(T item, flist_ix_t before_ix)
{
	if(before_ix < 0) before_ix = Cnt() - before_ix;	// append
	if(before_ix > Cnt()) before_ix = Cnt();	// append
    if(Capacity() > Cnt()) {
    	fCnt++;
    }
    else {
        setCnt(Cnt() + 1);
    }
    for(flist_ix_t ui=Cnt()-1; ui>before_ix; ui--) vector[ui] = vector[ui - 1];
    vector[before_ix] = item;
}
//---------------------------------------------------------------------------
template<class T>
void FVector<T>::setVector(T* v, flist_ix_t cnt)
{
    setCnt(cnt);
    for(flist_ix_t u=0; u<Cnt(); u++) vector[u] = v[u];
}
//---------------------------------------------------------------------------
template<class T>
void FVector<T>::Remove(flist_ix_t ix, int cnt)
{
    for(flist_ix_t ix2 = ix+cnt; ix2 < Cnt(); ix2++) {
        vector[ix++] = vector[ix2];
    }
    fCnt = ix;
}
//---------------------------------------------------------------------------
template<class T>
const FVector<T>& FVector<T>::operator=(const FVector<T>& fa)
{
    //setCnt(fa.Capacity());   //zajisti dostatecnou velikost pole
    setCnt(fa.Cnt());
    for(flist_ix_t u=0; u<Cnt(); u++) vector[u] = fa.vector[u];
    return *this;
}
//---------------------------------------------------------------------------
template<class T>
flist_ix_t FVector<T>::Seek(const T& key)
{
    flist_ix_t L = 0, H = Cnt()-1, M;

    if(Cnt()==0) return FEOFLIST;
    while(L <= H) {
        M = (H + L)/2;
        if(vector[M] < key) {
            L = M + 1;
        }
        else if(vector[M] == key) {  //NAJDI PRVNI VYSKYT KLICE
            while(M > 0 && vector[M-1] == key) M--;
            return M;
        }
        else {
            if(M == 0) break;
            //tato podminka je nutna, protoze H,L,M jsou unsigned
            // a kdyz je M==0 pak M-1 je 0xFFFFFFFF
            H = M - 1;
        }
    }
    return FEOFLIST;
}
//---------------------------------------------------------------------------
template<class T>
flist_ix_t FVector<T>::Find(const T& key, flist_ix_t start_ix)
{
    if(start_ix < 0) start_ix = Cnt() - start_ix;
    for(flist_ix_t u=start_ix; u<Cnt(); u++) {
        if(vector[u] == key) return u;
    }
    return FEOFLIST;
}
//---------------------------------------------------------------------------
//===========================================================================

//===========================================================================
//                          FList
//===========================================================================
template<class T>
void FList<T>::setCnt(flist_ix_t newcnt)
{
    flist_ix_t oldcnt = Cnt();
    FVector<T*>::setCnt(newcnt);
    if(newcnt > oldcnt) {
        for(flist_ix_t u=oldcnt; u<Cnt(); u++) vector[u] = NULL;
//        for(unsigned u=oldcnt; u<Cnt(); u++) vector[u] = new T;
    }
    else if(newcnt < oldcnt) {
        for(flist_ix_t i=newcnt; i<oldcnt; i++) {
            T *o = vector[i];
            if(o) {
                if(DeleteOnRemove()) delete o;
                vector[i] = NULL;
            }
        }
    }
}
// ----------------------------------------------------------------------
template<class T>
void FList<T>::Remove(flist_ix_t ix, int cnt)
{
    #ifdef ENABLE_FLIST_LOGGING
    fprintf(stderr, "<4>FList: FList<T>::Remove(ix=%i, cnt=%i)\n", ix, cnt);
    fflush(stderr);
    #endif
    if(ix < 0) ix = Cnt() - ix;
    if(DeleteOnRemove()) for(flist_ix_t ix2 = ix; ix2<ix+cnt && ix2<Cnt(); ix2++) {
        T* item = vector[ix2];
        #ifdef ENABLE_FLIST_LOGGING
        fprintf(stderr, "<4>FList: FList<T>::Remove - Delete on remove %p\n", item);
        fflush(stderr);
        #endif
        if(item) delete item;
        #ifdef ENABLE_FLIST_LOGGING
        else 
            fprintf(stderr, "<4>FList: FList<T>::Remove(%i, %i): item[%i] is NULL and cann't be deleted.\n", ix, cnt, ix2);
        #endif
        //throw FListException("FList<T>::Remove(%i, %i): item[%i] is NULL and cann't be deleted.", ix, cnt, ix2);
    }
    FVector<T*>::Remove(ix, cnt);
    #ifdef ENABLE_FLIST_LOGGING
    fprintf(stderr, "<4>FList: FList<T>::Remove - EXIT\n");
    fflush(stderr);
    #endif
}
//---------------------------------------------------------------------------
template<class T>
flist_ix_t FList<T>::Seek(const T& key)
{
    flist_ix_t L = 0, H = Cnt()-1, M;

    if(Cnt()==0) return FEOFLIST;
    while(L <= H) {
        M = (H + L)/2;
        if((*this)[M] < key) {
            L = M + 1;
        }
        else if((*this)[M] == key) {  //NAJDI PRVNI VYSKYT KLICE
            while(M > 0 && (*this)[M-1] == key) M--;
            return M;
        }
        else {
            if(M == 0) break;
            //tato podminka je nutna, protoze H,L,M jsou unsigned
            // a kdyz je M==0 pak M-1 je 0xFFFFFFFF
            H = M - 1;
        }
    }
    return FEOFLIST;
}
//---------------------------------------------------------------------------
template<class T>
flist_ix_t FList<T>::Find(const T& key, flist_ix_t start_ix)
{
    if(start_ix < 0) start_ix = Cnt() - start_ix;
    for(flist_ix_t u=start_ix; u<Cnt(); u++) {
        if((*this)[u] == key) return u;
    }
    return FEOFLIST;
}
//===========================================================================

//===========================================================================
//                          common functions
//===========================================================================
template<class T>
void MergeSort(T& vect)
{
    #ifdef ENABLE_FLIST_LOGGING
    fprintf(stderr, "<4>FList: FList<T>::MergeSort() ENTER\n");
    #endif
    flist_ix_t cnt = vect.Cnt();
    if(cnt == 0) return;

    flist_ix_t block_cnt;
    flist_ix_t block_len;
    flist_ix_t x1,x2,x12,x22, merge_cnt;

    T& nomerged = vect;
    T merged = nomerged;

    for(block_len=1; block_len<cnt; block_len*=2) {
        block_cnt = cnt / block_len;
        if(cnt % block_len) block_cnt++;
        // projdi vsechny dvojice sousednich bloku
        for(flist_ix_t ux=0, uj=0; uj<block_cnt; uj += 2) {
            // x1 = index prvniho objektu prvniho bloku
            x1 = uj*block_len;
            // x2 je index 1. objektu druheho bloku
            x2 = (uj + 1)*block_len;
            // x12 je index posledniho objektu prvniho bloku
            x12 = x2; if(x12 > cnt) x12 = cnt;
            // x12 je index posledniho objektu druheho bloku
            x22 = x2 + block_len; if(x22 > cnt) x22 = cnt;
            // merge_cnt je pocet porovnani
            merge_cnt  = (x12 > x1)? x12-x1: 0;
            merge_cnt += (x22 > x2)? x22-x2: 0;
            for(flist_ix_t ui=0; ui<merge_cnt; ui++) {
                // kdyz je prvni blok vycerpan, ber prvky z druheho bloku
                if(x1 >= x12)
                    merged.Vector()[ux++] = nomerged.Vector()[x2++];
                // kdyz je druhy blok vycerpan, ber prvky z prvniho bloku
                else if(x2 >= x22)
                    merged.Vector()[ux++] = nomerged.Vector()[x1++];
                // jinak vyber mensi nevybrany prvek z obou bloku
                else {
                    if(nomerged[x1] < nomerged[x2])
                        merged.Vector()[ux++] = nomerged.Vector()[x1++];
                    else
                        merged.Vector()[ux++] = nomerged.Vector()[x2++];
                }
            }
        }
        merged.Switch(nomerged);
    }
    #ifdef ENABLE_FLIST_LOGGING
    fprintf(stderr, "<4>FList: FList<T>::MergeSort() EXIT\n");
    #endif
}
//---------------------------------------------------------------------------
//===========================================================================
#endif