/*****************************************************************************
* PriorQue.c - implement priority queue, using regular binary trees	     *
* (that guarantees only average time of NlogN...) and with the following     *
* operations:								     *
* 1. PQInit(&PQ) - initialize the queue, must be called before usage.	     *
* 2. PQEmpty(PQ) - returns TRUE iff PQ is empty.			     *
* 3. PQCompFunc(&CompFunc) - sets (a pointer to) the function that is	     *
*    used to compere two items in the queue. the function should get two     *
*    item pointers, and should return >1, 0, <1 as comparison result for     *
*    greater than, equal, or less than respectively.			     *
* 4. PQFirst(&PQ, Delete) - returns the first element of the priority	     *
*    queue, and delete it from queue if delete is TRUE.			     *
* 5. PQInsert(&PQ, NewItem) - insert NewItem into the queue		     *
*    (NewItem is a pointer to it), using the comparison function CompFunc.   *
* 6. PQDelete(&PQ, OldItem) - Delete old item from the queue		     *
*    again using the comparison function CompFunc.			     *
* 7. PQFind(PQ, OldItem)  - Find old item in queue, again using the	     *
*    comparison function CompFunc.					     *
* 8. PQNext(PQ, CmpItem, NULL) - returns the smallest item which is bigger   *
*    than given item CmpItem. PQ is not modified. Return NULL if none.	     *
* 9. PQPrint(PQ, &PrintFunc) - print the queue in order using the given      *
*    printing function PrintFunc.					     *
*10. PQFree(&PQ, FreeItems) - Free the queue. The items are also freed if    *
*    FreeItems is TRUE.							     *
*									     *
* 			Written by Gershon Elber,   Dec 88                   *
*****************************************************************************/

#include <stdio.h>
#include <string.h>
#include "irit_sm.h"
#include "priorque.h"
#include "imalloc.h"

#define PQ_NEW_NODE(PQ)  { \
	PQ = (PriorQue *) IritMalloc(sizeof(PriorQue)); \
	(PQ) -> Right = (PQ) -> Left = NULL; \
	(PQ) -> Data = NULL; }
#define PQ_FREE_NODE(PQ) { IritFree((VoidPtr) (PQ)); PQ = NULL; }

static PQCompFuncType CompFunc = (PQCompFuncType) strcmp;

/*****************************************************************************
* DESCRIPTION:                                                               M
* Initializes the priority queue.					     M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:       To initialize.                                                 M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQInit, priority queue                                                   M
*****************************************************************************/
void PQInit(PriorQue **PQ)
{
    *PQ = NULL;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* returns TRUE iff PQ priority queue is empty.				     M
*                                                                            M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:       Priority queue to test for containment.                        M
*                                                                            *
* RETURN VALUE:                                                              M
*   int:      TRUE if not empty, FALSE otherwise.                            M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQEmpty, priority queue                                                  M
*****************************************************************************/
int PQEmpty(PriorQue *PQ)
{
    return PQ == NULL;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Sets (a pointer to) the function that is used in comparing two items in    M
* the queue.                                                                 M
*    This comparison function will get two item pointers, and should return  M
* >0, 0, <0 as comparison result for greater than, equal, or less than       M
* relation, respectively.					             M
*                                                                            *
* PARAMETERS:                                                                M
*   NewCompFunc:   A comparison function to used on item in the queue.	     M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQCompFunc, priority queue                                               M
*****************************************************************************/
void PQCompFunc(PQCompFuncType NewCompFunc)
{
    CompFunc = NewCompFunc;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Returns the first element in the given priority queue, and delete it from  M
* the queue if Delete is TRUE. returns NULL if empty queue.		     M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:        To examine/remove first element from.                         M
*   Delete:    If TRUE first element is being removed from the queue.        M
*                                                                            *
* RETURN VALUE:                                                              M
*   VoidPtr:   A pointer to the first element in the queue.                  M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQFirst, priority queue                                                  M
*****************************************************************************/
VoidPtr PQFirst(PriorQue **PQ, int Delete)
{
    VoidPtr Data;
    PriorQue *Ptemp = (*PQ);

    if (*PQ == NULL)
	return NULL;

    while (Ptemp -> Right != NULL)
	Ptemp = Ptemp -> Right;			      /* Find smallest item. */
    Data = Ptemp -> Data;

    if (Delete)
	PQDelete(PQ, Data);

    return Data;
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Insert a new element into the queue (NewItem is a pointer to new element)  M
* using given compare function CompFunc (See PQCompFunc).		     M
*   Insert elelemnt will always be a leaf of the constructed tree.	     M
*   Returns a pointer to old element if was replaced or NULL if the element  M
* is new.                                                                    M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:        To insert a new element to.                                   M
*   NewItem:   The new element to insert.                                    M
*                                                                            *
* RETURN VALUE:                                                              M
*   VoidPtr:   An old element NewItem replaced, or NULL otherwise.           M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQInsert, priority queue                                                 M
*****************************************************************************/
VoidPtr PQInsert(PriorQue **PQ, VoidPtr NewItem)
{
    int Compare;
    VoidPtr Data;

    if ((*PQ) == NULL) {
	PQ_NEW_NODE(*PQ);
	(*PQ) -> Data = NewItem;
	return NULL;
    }
    else {
	Compare = (*CompFunc)(NewItem, (*PQ) -> Data);
	Compare = SIGN(Compare);
	switch (Compare) {
	    case -1:
		return PQInsert(&((*PQ) -> Right), NewItem);
	    case 0:
		Data = (*PQ) -> Data;
		(*PQ) -> Data = NewItem;
		return Data;
	    case 1:
		return PQInsert(&((*PQ) -> Left), NewItem);
	}
    }
    return NULL;				    /* Makes warning silent. */
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Deletes an old item from the queue, using comparison function CompFunc.    M
*   Returns a pointer to Deleted item if was fould and deleted from the      M
* queure, NULL otherwise.						     M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:        To delete OldItem from.                                       M
*   OldItem:   Old element in priority queue PQ to remove from.              M
*                                                                            *
* RETURN VALUE:                                                              M
*   VoidPtr:   Removed OldItem if found, NULL otherwise.                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQDelete, priority queue                                                 M
*****************************************************************************/
VoidPtr PQDelete(PriorQue **PQ, VoidPtr OldItem)
{
    int Compare;
    PriorQue *Ptemp;
    VoidPtr Data;
    VoidPtr OldData;

    if ((*PQ) == NULL) {
	return NULL;
    }
    else {
	Compare = (*CompFunc)(OldItem, (*PQ) -> Data);
	Compare = SIGN(Compare);
	switch (Compare) {
	    case -1:
		return PQDelete(&((*PQ) -> Right), OldItem);
	    case 0:
		OldData = (*PQ) -> Data;       /* The returned deleted item. */

		if ((*PQ) -> Right == NULL && (*PQ) -> Left == NULL) {
		    /* Thats easy - we delete a leaf: */
		    Data = (*PQ) -> Data;
		    PQ_FREE_NODE(*PQ); /* Note *PQ is also set to NULL here. */
		}
		else if ((*PQ) -> Right != NULL) {
		    /* replace this node by the biggest in the Right branch: */
		    /* move once to the Right and then Left all the time...  */
		    Ptemp = (*PQ) -> Right;
		    if (Ptemp -> Left != NULL) {
			while (Ptemp -> Left -> Left != NULL)
			    Ptemp = Ptemp -> Left;
			Data = Ptemp -> Left -> Data;/*Save the data pointer.*/
			PQDelete(&(Ptemp -> Left), Data);  /* Delete recurs. */
			(*PQ) -> Data = Data; /* And put that data instead...*/
		    }
		    else {
			Data = Ptemp -> Data;      /* Save the data pointer. */
			PQDelete(&((*PQ) -> Right), Data); /* Delete recurs. */
			(*PQ) -> Data = Data; /* And put that data instead...*/
		    }
		}
		else {					    /* Left != NULL. */
		    /* replace this node by the biggest in the Left branch:  */
		    /* move once to the Left and then Right all the time...  */
		    Ptemp = (*PQ) -> Left;
		    if (Ptemp -> Right != NULL)	{
			while (Ptemp -> Right -> Right != NULL)
			    Ptemp = Ptemp -> Right;
			Data = Ptemp -> Right -> Data; /* Save data pointer. */
			PQDelete(&(Ptemp -> Right), Data);  /*Delete recurs. */
			(*PQ) -> Data = Data; /* And put that data instead...*/
		    }
		    else {
			Data = Ptemp -> Data;      /* Save the data pointer. */
			PQDelete(&((*PQ) -> Left), Data);  /* Delete recurs. */
			(*PQ) -> Data = Data; /* And put that data instead...*/
		    }
		}
		return OldData;
	    case 1:
		return PQDelete(&((*PQ) -> Left), OldItem);
	}
    }
    return NULL;				    /* Makes warning silent. */
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Finds old item on the queue, PQ, using the comparison	function CompFunc.   M
*   Returns a pointer to item if was fould, NULL otherwise.		     M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:        To search for OldItem at.                                     M
*   OldItem:   Element to search in PQ.                                      M
*                                                                            *
* RETURN VALUE:                                                              M
*   VoidPtr:   Found element or othewise NULL.                               M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQFind, priority queue                                                   M
*****************************************************************************/
VoidPtr PQFind(PriorQue *PQ, VoidPtr OldItem)
{
    int Compare;

    if (PQ == NULL) {
	return NULL;
    }
    else {
	Compare = (*CompFunc)(OldItem, PQ -> Data);
	Compare = SIGN(Compare);
	switch (Compare) {
	    case -1:
		return PQFind(PQ -> Right, OldItem);
	    case 0:
		return PQ -> Data;
	    case 1:
		return PQFind(PQ -> Left, OldItem);
	}
    }
    return NULL;				    /* Makes warning silent. */
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Returns the smallest element in PQ that is larger than given element       M
* CmpItem.                                                                   M
*   PQ is not modified. Return NULL if none was found.			     M
*   LargerThan will allways hold the smallest Item Larger than current one.  M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:           To examine.                                                M
*   CmpItem:      To find the smallest item in PQ that is larger than it.    M
*   LargerThan:   The item that is found larger so far.                      M
*                                                                            *
* RETURN VALUE:                                                              M
*   VoidPtr:     The samllest item in PQ that is larger than CmpItem or      M
*                NULL if no found.					     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQNext, priority queue                                                   M
*****************************************************************************/
VoidPtr PQNext(PriorQue *PQ, VoidPtr CmpItem, VoidPtr LargerThan)
{
    int Compare;
    PriorQue *Ptemp;

    if (PQ == NULL)
	return LargerThan;
    else {
	Compare = (*CompFunc)(CmpItem, PQ -> Data);
	Compare = SIGN(Compare);
	switch (Compare) {
	    case -1:
		return PQNext(PQ -> Right, CmpItem, PQ -> Data);
	    case 0:
		/* Found it - if its right tree is not empty, returns its    */
		/* smallest, else returns LargerThan...			     */
		if (PQ -> Left != NULL) {
		    Ptemp = PQ -> Left;
		    while (Ptemp -> Right != NULL) Ptemp = Ptemp -> Right;
		    return Ptemp -> Data;
		}
		else
		    return LargerThan;
	    case 1:
		return PQNext(PQ -> Left, CmpItem, LargerThan);
	}
    }
    return NULL;				    /* Makes warning silent. */
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Scans the priority queue in order and invokes the "printing" routine,      M
* PrintFunc on every item in the queue as its only argument.		     M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:         Pritority queue to traverse.                                 M
*   PrintFunc:  "Printing function".                                         M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQPrint, priority queue                                                  M
*****************************************************************************/
void PQPrint(PriorQue *PQ, void (*PrintFunc)(VoidPtr))
{
    if (PQ == NULL)
	return;

    PQPrint(PQ -> Right, PrintFunc);

    (*PrintFunc)(PQ -> Data);

    PQPrint(PQ -> Left, PrintFunc);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Frees the given queue. The elelents are also freed if FreeItems is TRUE.   M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:         Priority queue to release.                                   M
*   FreeItem:   If TRUE, elements are being freed as well.                   M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQFree, priority queue                                                   M
*****************************************************************************/
void PQFree(PriorQue *PQ, int FreeItem)
{
    if (PQ == NULL)
	return;

    PQFree(PQ -> Right, FreeItem);
    PQFree(PQ -> Left, FreeItem);

    if (FreeItem)
	IritFree((char *) PQ -> Data);
    IritFree((char *) PQ);
}

/*****************************************************************************
* DESCRIPTION:                                                               M
* Frees the given queue. The elelents are also freed by invoking FreeFunc    M
* onall of them as FreeFunc's only argument.                                 M
*                                                                            *
* PARAMETERS:                                                                M
*   PQ:         Priority queue to release.                                   M
*   FreeFunc:   "Printing function".                                         M
*                                                                            *
* RETURN VALUE:                                                              M
*   void                                                                     M
*                                                                            *
* KEYWORDS:                                                                  M
*   PQFreeFunc, priority queue                                               M
*****************************************************************************/
void PQFreeFunc(PriorQue *PQ, void (*FreeFunc)(VoidPtr))
{
    if (PQ == NULL)
	return;

    PQFreeFunc(PQ -> Right, FreeFunc);
    PQFreeFunc(PQ -> Left, FreeFunc);

    (FreeFunc)(PQ -> Data);
    IritFree((char *) PQ);
}
