#include "MHVector.h"

int MHVector::aaSortVectorCol = 0;



/**
*  Compare two objects in a vector
*/
int MHVector::Compare (const MH* o, int type) {
    MHVector*   ve  = (MHVector*) o;
    MH*         mh1 = Get (MHVector::aaSortVectorCol);
    MH*         mh2 = ve->Get (MHVector::aaSortVectorCol);

    if (mh1 && mh2)
        return mh1->Compare (mh2, type);
    return -1;
}



/**
*  Create a new vector
*/
void MHVector::create (int capacity) {
    aSize        = 0;
    aCapacity    = capacity;
    aVector      = new MH*[aCapacity];
    aSortType    = 0;
}



/**
*  Empty vector but don't delete objects.
*/
void MHVector::Empty () {
    if (aCapacity) delete []aVector;
    aSize     = 0;
    aCapacity = 0;
    aVector   = 0;
}



/**
*  Erase vector and delete all objects.
*/
void MHVector::Erase () {
    for (int f = 0; f < aSize; f++)
        delete aVector[f];
    delete []aVector;
    aSize     = 0;
    aCapacity = 0;
    aVector   = 0;
}



/**
*  Erase object in vector
*  @param int  - Index in vector
*/
void MHVector::Erase (int index) {
    MH* node = Pop (index);
    delete node;
}



/**
*  Erase object in vector
*  @param MH - Object to erase
*/
void MHVector::Erase (MH* o) {
    MH* node = Pop (o);
    delete node;
}



/**
*  Find a object
*  @param MH*   - Object to use for searching
*  @param int   - FIND_EXACT, FIND_BEFORE, FIND_AFTER
*  @param int   - Compare type, default 0
*  @param int*  - Start index to go from, default 0
*  @return MH*  - Object if found else 0
*/
MH* MHVector::Find (const MH* o, int exact, int type, int* mid2) {
    if (aSize == 0) return 0;
    if (mid2 && (*mid2 < 0 || *mid2 >= aSize)) return 0;

    int  low  = 0;
    int  high = aSize;
    int  comp = 0;
    int  mid3 = 0;
    int* mid  = &mid3;

    if (mid2) mid = mid2;
    if (type != aSortType) Sort (type);

    while (low != high) {
        *mid  = low + (high - low) / 2;
        comp = aVector[*mid]->Compare(o, aSortType) ;

        if (comp == 0)
            return aVector[*mid];
        else if (comp > 0)
            high = *mid;
        else
            low = *mid + 1;
    }

    if (exact == FIND_AFTER && comp < 0) (*mid)++;
    if (exact == FIND_BEFORE && comp > 0) (*mid)--;

    if (exact == FIND_AFTER && *mid < aSize)
        return aVector[*mid];
    else if (exact == FIND_BEFORE && *mid >= 0)
        return aVector[*mid];

    return 0;
}



/**
*  Insert object first in list
*  @param MH* - Object to insert
*  @param int - Position in vector, default 0
*/
void MHVector::Insert (MH* node, int pos) {
    int f;

    if (pos < 0) return;
    if (aSize == aCapacity) {
        //  Increase capacity now
        aCapacity = (aCapacity == 0) ? 10 : aCapacity * 2;
        MH** tmp = new MH*[aCapacity];
        for (f = aSize - 1; f >= pos; f--)
            tmp[f + 1] = aVector[f];
        for (f = 0; f < pos; f++)
            tmp[f] = aVector[f];
        tmp[pos] = node;
        delete []aVector;
        aVector = tmp;
        aSize++;
    }
    else if (pos >= aSize)
        Push (node);
    else {
        for (f = aSize - 1; f >= pos; f--)
            aVector[f + 1] = aVector[f];
        aVector[pos] = node;
        aSize++;
    }
}



/**
*  Insert object at the first slot where key is larger
*  @param MH* - Object to insert
*  @param int - Compare type
*/
void MHVector::InsertSorted (MH* node, int type) {
    int f;

    if (type != aSortType) Sort (type);
    if (aSize == aCapacity) {
        //  Increase capacity now
        aCapacity = (aCapacity == 0) ? 10 : aCapacity * 2;
        MH** tmp = new MH*[aCapacity];

        for (f = aSize - 1; f >= 0; f--) {
            if (aVector[f]->Compare (node, type) < 1) break;
            tmp[f + 1] = aVector[f];
        }
        tmp[f + 1] = node;
        for (; f >= 0; f--)
            tmp[f] = aVector[f];

        delete []aVector;
        aVector = tmp;
        aSize++;
    }
    else {
        for (f = aSize - 1; f >= 0; f--) {
            if (aVector[f]->Compare (node, type) < 1) break;
            aVector[f + 1] = aVector[f];
        }
        aVector[f + 1] = node;
        aSize++;
    }
}



/**
*
*/
void MHVector::insertionSort (MH** ve, int lo0, int hi0) {
    int i;
    int j;
    MH* v;

    for (i = lo0 + 1; i <= hi0; i++) {
        v = ve[i];
        j = i;
        while ((j > lo0) && (ve[j - 1]->Compare(v, aSortType) > 0)) {
            ve[j] = ve[j - 1];
            j--;
        }
        ve[j] = v;
    }
}



/**
*
*/
void MHVector::heapSort (MH** ve, int size) {
    int i;
    MH* tmp;

    for (i = (size / 2) - 1; i >= 0; i--)
        MHVector::siftDown (aSortType, ve, i, size - 1);

    for (i = size - 1; i >= 1; i--) {
        tmp = ve[0];
        ve[0] = ve[i];
        ve[i] = tmp;
        MHVector::siftDown (aSortType, ve, 0, i - 1);
  }
}



/**
*  Find a object. Search from index.
*  If SEARCH_ALL is on then it will try to search through all objects before giving up.
*  @param MH*   - Object to use for searching
*  @param int   - FIND_EXACT, FIND_BEFORE, FIND_AFTER, SEARCH_ALL
*  @param int   - Compare type
*  @param int   - Start index
*  @return MH*  - Found object or 0 if not found
*/
MH* MHVector::Search (const MH* o, int exact, int type, int* mid2) {
    if (aSize == 0) return 0;
    if (mid2 && (*mid2 < 0 || *mid2 >= aSize)) return 0;

    int  cmp  = 0;
    int  mid3 = 0;
    int* mid  = &mid3;

    if (mid2) mid = mid2;
    if (type != aSortType) Sort (type);

    for (; *mid < aSize; (*mid)++) {
        cmp = aVector[*mid]->Compare (o, type);

        if (cmp == 0) {
            return aVector[*mid];
        }
        else if (cmp > 0 && exact != SEARCH_ALL)
            break;
    }
    if (*mid == aSize) (*mid)--;

    if (exact == FIND_AFTER && cmp < 0 && *mid < aSize) (*mid)++;
    if (exact == FIND_BEFORE && cmp > 0) (*mid)--;
    if (exact == FIND_AFTER && *mid < aSize)
        return aVector[*mid];
    else if (exact == FIND_BEFORE && *mid >= 0)
        return aVector[*mid];

    return 0;
}




/**
*
*/
void MHVector::siftDown (int type, MH** ve, int root, int bottom) {
    int  done = 0;
    int  maxChild;
    MH*  tmp;

    done = 0;
    while ((root * 2) <= bottom && !done) {
        if (root * 2 == bottom)
            maxChild = root * 2;
        else if (ve[root * 2]->Compare (ve[root * 2 + 1], type) > 0)
            maxChild = root * 2;
        else
            maxChild = root * 2 + 1;

        if (ve[root]->Compare (ve[maxChild], type) < 0) {
            tmp = ve[root];
            ve[root] = ve[maxChild];
            ve[maxChild] = tmp;
            root = maxChild;
        }
        else
            done = 1;
    }
}



/**
*  Remove object in vector
*  @param int  - Index in vector
*  @return MH* - Object in vector or 0
*/
MH* MHVector::Pop (int index) {
    if (index < 0 || index >= aSize) return 0;

    MH* node = aVector[index];

    for (int f = index + 1; f < aSize; f++)
        aVector[f - 1] = aVector[f];
    aSize--;
    return node;
}



/**
*  Remove object from vector, only the adress of the object is compared.
*  @param MH*   - Object to find
*  @return MH*  - Found object or 0
*/
MH* MHVector::Pop (MH* o) {
    for (int f = 0; f < aSize; f++) {
        if (aVector[f] == o)
            return Pop (f);
    }
    return 0;
}



/**
*  Push a node to the end of vector.
*  If no more room increase size by the double
*/
void MHVector::Push (MH* node) {
    if (aSize == aCapacity) {
        //  Increase capacity now
        aCapacity = (aCapacity == 0) ? 10 : aCapacity * 2;
        MH** tmp = new MH*[aCapacity];
        for (int f = 0; f < aSize; f++)
            tmp[f] = aVector[f];
        delete []aVector;
        aVector = tmp;
    }
    aVector[aSize] = node;
    aSize++;
}



/**
*
*/
void MHVector::quickSort (int type, MH** ve, int l, int r) {
    int M = 4;
    int i;
    int j;
    MH* v;

    if ((r - l) > M) {
        i = (r + l) / 2;
        if (ve[l]->Compare(ve[i], type) > 0) MHVector::swap (ve, l, i);
        if (ve[l]->Compare(ve[r], type) > 0) MHVector::swap (ve, l, r);
        if (ve[i]->Compare(ve[r], type) > 0) MHVector::swap (ve, i, r);

        j = r - 1;
        MHVector::swap (ve, i, j);
        i = l;
        v = ve[j];

        while (1) {
            while (i < r && ve[++i]->Compare(v, type) < 0) {;}
            while (i > 0 && ve[--j]->Compare(v, type) > 0) {;}
            if (j < i) break;
            swap (ve, i, j);
        }
        MHVector::swap (ve, i, r - 1);
        MHVector::quickSort (type, ve, l, j);
        MHVector::quickSort (type, ve, i + 1, r);
    }
}



/**
*  Resize capacity
*  @param int - The number of cells to add to array
*/
void MHVector::Resize (int size) {
    ASS (size > 0)
    if (aCapacity >= size) return;
    aCapacity = size;
    MH** tmp = new MH*[aCapacity];
    for (int f = 0; f < aSize; f++)
        tmp[f] = aVector[f];
    delete []aVector;
    aVector = tmp;
}



/**
*  Reverse order
*/
void MHVector::Reverse () {
    int i = aSize / 2;
    int j = aSize;
    for (int f = 0; f < i; f++)
        MHVector::swap (aVector, f, --j);
}



/**
*
*/
void MHVector::swap (MH** ve, int a, int b) {
    MH* tmp  = ve[a];
    ve[a] = ve[b];
    ve[b] = tmp;
}