#include <stdio.h>
#include <stdlib.h>
#include <ntddk.h>
#include <app.avl.h>

//
#include <stdio.h>
#include <app.convstr.h>


void
pS(void *Struct)
{
    int i;
    if (Struct == NULL)
    {
        printf("NULL");
        return;
    }
    printf("%02X", ((char*)Struct)[0]);
    for(i = 1; i < 2 * sizeof(appBLOCK) + sizeof(int); i++)
    {
        printf(", %02X", ((char*)Struct)[i]);
    }
}

void
pT(void *Struct)
{
    if (Struct == NULL)
    {
        printf("NULL");
        return;
    }
    printf("%d, ", ((appTRIPLET*)Struct)->A);
    printf("%d, ", ((appTRIPLET*)Struct)->B);
    printf("%d"  , ((appTRIPLET*)Struct)->k);
}

void
pI(void *Struct)
{
    if (Struct == NULL)
    {
        printf("NULL");
        return;
    }
    printf("%d, ", ((appTRIPLET*)Struct)->A);
    printf("%d"  , ((appTRIPLET*)Struct)->A+((appTRIPLET*)Struct)->k);
}

RTL_GENERIC_COMPARE_RESULTS
CompareRoutine(
    __in struct _RTL_AVL_TABLE  *Table,
    __in PVOID  FirstStruct,
    __in PVOID  SecondStruct
)
{
    int i, j, k1, k2;
    appBLOCK A1, A2;

    A1 = ((struct appTRIPLET*)FirstStruct)->A;
    k1 = ((struct appTRIPLET*)FirstStruct)->k;
    A2 = ((struct appTRIPLET*)SecondStruct)->A;
    k2 = ((struct appTRIPLET*)SecondStruct)->k;

    if (k1 == 1 && (A1 >= A2 && A1 < A2 + k2)) return GenericEqual;
    if (k2 == 1 && (A2 >= A1 && A2 < A1 + k1)) return GenericEqual;
    if (A1 > A2) return GenericGreaterThan;
    if (A1 < A2) return GenericLessThan;
    return GenericEqual;
}

PVOID
Allocate_Routine(
    __in struct _RTL_AVL_TABLE  *Table,
    __in CLONG  ByteSize
)
{
    void *temp;
    temp = malloc(ByteSize);
    return temp;
}

VOID
FreeRoutine(
    __in struct _RTL_AVL_TABLE  *Table,
    __in PVOID  Buffer
)
{
    free(Buffer);
}

BOOLEAN
addNode(appBLOCK A, appBLOCK B, appNUMBER k, PRTL_AVL_TABLE Table)
{
    BOOLEAN ok;
    ULONG TableLength = RtlNumberGenericTableElementsAvl(Table);
    appTRIPLET T, Left, Right, *PLeft, *PRight, *PL, *PR, *temp;
    PVOID restart;

    //Find the edge intervals
    Left.A = A;
    Left.k = 1;
    Right.A = A + k;
    Right.k = 1;

    if(RtlLookupElementGenericTableAvl(Table, &Left) != NULL)
    {
        PLeft = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &Left);
        PL = PLeft;
    }
    else
    {
        RtlInsertElementGenericTableAvl(Table, &Left, sizeof(Left), &ok);
        restart = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &Left);
        restart = (PVOID)((char*)(restart) - 0x20);
        PLeft = (appTRIPLET*)RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);
        RtlDeleteElementGenericTableAvl(Table, &Left);
        PL = NULL;
    }

    if(RtlLookupElementGenericTableAvl(Table, &Right) != NULL)
    {
        PR = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &Right);
        restart = (PVOID)((char*)(PR) - 0x20);
        PRight = (appTRIPLET*)RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);
    }
    else
    {
        RtlInsertElementGenericTableAvl(Table, &Right, sizeof(Right), &ok);
        restart = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &Right);
        restart = (PVOID)((char*)(restart) - 0x20);
        PLeft = (appTRIPLET*)RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);
        RtlDeleteElementGenericTableAvl(Table, &Right);
        PR = NULL;
    }
    printf("[%d, %d)\n", A, A+k);
    printf("PL: [");pI(PL);printf(")\n");
    printf("PR: [");pI(PR);printf(")\n\n");

    //Split edge intervals
    if(PL != NULL)
    {
        Left.A = PL->A;
        Left.B = PL->B;
        Left.k = A - PL->A;
        PL = &Left;
    }
    if(PR != NULL)
    {
        Right.A = A + k;
        Right.B = PR->B + ((A + k) - PR->A);
        Right.k = PR->A + PR->k - (A + k);
        PR = &Right;
    }


    //Delete crossing intervals
    restart = (PVOID)((char*)(PLeft) - 0x20);
    for(temp = PLeft; temp != PRight; temp = RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);)
    {
        RtlDeleteElementGenericTableAvl(Table, temp);
    }

    //Add the main interval
    T.A = A;
    T.B = B;
    T.k = k;
    RtlInsertElementGenericTableAvl(Table, &T, sizeof(T), &ok);

    //Add the splitted intervals
    if(PL != NULL) RtlInsertElementGenericTableAvl(Table, PL, sizeof(appTRIPLET), &ok);
    if(PR != NULL) RtlInsertElementGenericTableAvl(Table, PR, sizeof(appTRIPLET), &ok);

    return ok;
}

BOOLEAN
existNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
    appTRIPLET T, *P;
    T.A = A;
    T.k = 1;
    P = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &T);
    if(P == NULL) return FALSE;
    return TRUE;
}

appTRIPLET*
findNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
    appTRIPLET T, *P;
    T.A = A;
    T.k = 1;
    P = RtlLookupElementGenericTableAvl(Table, &T);
    return P;
}

BOOLEAN
deleteNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
    BOOLEAN ok;
    appTRIPLET *P = findNode(A, Table);
    ok = RtlDeleteElementGenericTableAvl(Table, P);
    return ok;
}