/*____________________________________________________________________________
by Martin Robinson
collection of function and macro
______________________________________________________________________________
todo:

preprocessor________________________________________________________________*/

#pragma once
#ifndef _HEAP
#define _HEAP

/*most basic macro____________________________________________________________
swap...xor swap
*/
#define swap(A,B) if (A!=B){A^=B;B^=A;A^=B;}
/*HEAP________________________________________________________________________
this awesome data structure will be needed on pathfinding and maybe more
it is basicly à stack that always return the smallest data
____________________________________________________________________________*/
#define parent(INDEX) ((INDEX-1)>>1)
#define lchild(INDEX) ((INDEX<<1)+1)
#define rchild(INDEX) ((INDEX+1)<<1)
#define haveParent(INDEX) (INDEX>0)
#define haveOneChild(INDEX,SIZE) (lchild(INDEX)<SIZE)
#define haveTwoChild(INDEX,SIZE) (rchild(INDEX)<SIZE)
#define notChildOrder(HEAP,INDEX) (HEAP[lchild(INDEX)] > HEAP[rchild(INDEX)])
#define notParentOrder(HEAP,INDEX) (HEAP[parent(INDEX)]>HEAP[INDEX])
#define notChildParentOrder(HEAP, INDEX, CHILD) (HEAP[INDEX] > HEAP[CHILD])


//---------only example------------------
//pushing data, append at the end of the array
//then recursively compare with parent 
//and swap if not meet order
//---------only example------------------
#ifdef testHEAP
    void rhpush(int array[],int index)
    {
        if (haveParent(index) && notParentOrder(array, index))
        {
            swap(array[parent(index)], array[index]);
            rhpush(array, parent(index));
        }
    }

    int hpush(int array[], int qty, int data)
    {
        array[qty] = data;
        rhpush(array,qty);
        return ++qty;
    }

//---------only example------------------
//poping data, swap with last, 
//then recursively compare with child
//in the order the smallest then
//the biggest
//then swap if order not met
//---------only example------------------
    void rhpop(int array[], int index, int qty)
    {

        if(haveTwoChild(index,qty))
        {
            int child[2] = {lchild(index), rchild(index)};
            if (notChildOrder(array,index))
                swap(child[0], child[1]);
            int i;
            for (i=0;i<2;i++)
                if (notChildParentOrder(array, index, child[i]))
                {
                    swap(array[index], array[child[i]]);
                    rhpop(array, child[i], qty);
                    return;
                }
        }
        else if (haveOneChild(index,qty) && notChildParentOrder(array, index, lchild(index)))
            swap(array[index], array[lchild(index)]);
    }

    int hpop(int array[], int qty)
    {
        array[0] = 0;
        qty--;
        swap(array[0], array[qty]);
        rhpop(array,0,qty);
        return qty;
    }
#endif
//---------only example------------------

#endif