home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / IRITS.ZIP / PRIORQUE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  9.4 KB  |  254 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. * PriorQue.c - implement priority queue, using regular binary trees         *
  7. * (that guarantees only average time of NlogN...) and with the following     *
  8. * operations:                                     *
  9. * 1. PQInit(&PQ) - initialize the queue, must be called before usage.         *
  10. * 2. PQEmpty(PQ) - returns TRUE iff PQ is empty.                 *
  11. * 3. PQCompFunc(&CompFunc) - sets (a pointer to) the function that is         *
  12. *    used to compere two items in the queue. the function should get two     *
  13. *    item pointers, and should return >1, 0, <1 as comparison result for     *
  14. *    greater than, equal, or less than respectively.                 *
  15. * 4. PQFirst(&PQ, Delete) - returns the first element of the priority         *
  16. *    queue, and delete it from queue if delete is TRUE.                 *
  17. * 5. PQInsert(&PQ, NewItem) - insert NewItem into the queue             *
  18. *    (NewItem is a pointer to it), using the comparison function CompFunc.   *
  19. * 6. PQDelete(&PQ, OldItem) - Delete old item from the queue             *
  20. *    again using the comparison function CompFunc.                 *
  21. * 7. PQNext(PQ, CmpItem, NULL) - returns the smallest item which is bigger   *
  22. *    than given item CmpItem. PQ is not modified. Return NULL if none.         *
  23. * 8. PQPrint(PQ, &PrintFunc) - print the queue in order using the given      *
  24. *    printing function PrintFunc.                         *
  25. * 9. PQFree(&PQ, FreeItems) - Free the queue. The items are also freed if    *
  26. *    FreeItems is TRUE.                                 *
  27. *                                         *
  28. *             Written by Gershon Elber,   Dec 88                   *
  29. *****************************************************************************/
  30.  
  31. #include <stdio.h>
  32. #include "program.h"
  33. #include "priorql.h"
  34. #include "priorqg.h"
  35. #include "allocatg.h"
  36.  
  37. static int (*CompFunc)();     /* Pointer to comparison function (see above). */
  38.  
  39. /******************************************************************************
  40. * PQEmpty - initialize the queue...                          *
  41. ******************************************************************************/
  42. void PQInit(PriorQue **PQ)
  43. {
  44.     *PQ = NULL;
  45. }
  46.  
  47. /******************************************************************************
  48. * PQEmpty - returns TRUE iff PQ priority queue is empty.              *
  49. ******************************************************************************/
  50. int PQEmpty(PriorQue *PQ)
  51. {
  52.     return PQ == NULL;
  53. }
  54. /******************************************************************************
  55. * PQCompFunc - sets (a pointer to) the function that is used to compere two   *
  56. * items in the queue. The function should get two item pointers, and should   *
  57. * return >1, 0, <1 as comparison result for greater than, equal, or less than *
  58. * respectively.                                      *
  59. ******************************************************************************/
  60. void PQCompFunc(int (*PQCompFunc)())
  61. {
  62.     CompFunc = PQCompFunc;
  63. }
  64.  
  65. /******************************************************************************
  66. * PQFirst - returns the first element of the priority queue, and delete it    *
  67. * from queue if Delete is TRUE. return NULL if empty queue              *
  68. ******************************************************************************/
  69. VoidPtr PQFirst(PriorQue **PQ, int Delete)
  70. {
  71.     VoidPtr Data;
  72.     PriorQue *Ptemp = (*PQ);
  73.  
  74.     if (*PQ == NULL) return NULL;
  75.  
  76.     while (Ptemp -> Right != NULL)
  77.     Ptemp = Ptemp -> Right;                  /* Find smallest item. */
  78.     Data = Ptemp -> Data;
  79.  
  80.     if (Delete) PQDelete(PQ, Data);
  81.  
  82.     return Data;
  83. }
  84.  
  85. /******************************************************************************
  86. * PQInsert - insert new item into the queue (NewItem is a pointer to it),     *
  87. * using given compare function CompFunc. CompFunc should return >1, 0, <1     *
  88. * as two item comparison result for greater than, equal, or less than         *
  89. * respectively.                                      *
  90. *   Insert is always as a leaf of the tree.                      *
  91. *   Return pointer to old data if was replaced or NULL if the item is new.    *
  92. ******************************************************************************/
  93. VoidPtr PQInsert(PriorQue **PQ, VoidPtr NewItem)
  94. {
  95.     int Compare;
  96.     VoidPtr Data;
  97.  
  98.     if ((*PQ) == NULL) {
  99.     PQ_NEW_NODE(*PQ);
  100.     (*PQ) -> Data = NewItem;
  101.     return NULL;
  102.     }
  103.     else {
  104.     Compare = (*CompFunc)(NewItem, (*PQ) -> Data);
  105.     Compare = SIGN(Compare);
  106.     switch (Compare) {
  107.         case -1:
  108.         return PQInsert(&((*PQ) -> Right), NewItem);
  109.         case 0:
  110.         Data = (*PQ) -> Data;
  111.         (*PQ) -> Data = NewItem;
  112.         return Data;
  113.         case 1:
  114.         return PQInsert(&((*PQ) -> Left), NewItem);
  115.     }
  116.     }
  117.     return NULL;                    /* Makes warning silent. */
  118. }
  119.  
  120. /******************************************************************************
  121. * PQDelete - Delete old item from the queue, again using the comparison       *
  122. * function CompFunc.                                  *
  123. * Returns pointer to Deleted item if was fould and deleted, NULL otherwise.   *
  124. ******************************************************************************/
  125. VoidPtr PQDelete(PriorQue **PQ, VoidPtr OldItem)
  126. {
  127.     int Compare;
  128.     PriorQue *Ptemp;
  129.     VoidPtr Data;
  130.     VoidPtr OldData;
  131.  
  132.     if ((*PQ) == NULL) {
  133.     return NULL;
  134.     }
  135.     else {
  136.     Compare = (*CompFunc)(OldItem, (*PQ) -> Data);
  137.     Compare = SIGN(Compare);
  138.     switch (Compare) {
  139.         case -1:
  140.         return PQDelete(&((*PQ) -> Right), OldItem);
  141.         case 0:
  142.         OldData = (*PQ) -> Data;       /* The returned deleted item. */
  143.  
  144.         if ((*PQ) -> Right == NULL && (*PQ) -> Left == NULL) {
  145.             /* Thats easy - we delete a leaf: */
  146.             Data = (*PQ) -> Data;
  147.             PQ_FREE_NODE(*PQ); /* Note *PQ is also set to NULL here. */
  148.         }
  149.         else
  150.         if ((*PQ) -> Right != NULL) {
  151.             /* replace this node by the biggest in the Right branch: */
  152.             /* move once to the Right and then Left all the time...  */
  153.             Ptemp = (*PQ) -> Right;
  154.             if (Ptemp -> Left != NULL) {
  155.             while (Ptemp -> Left -> Left != NULL)
  156.                 Ptemp = Ptemp -> Left;
  157.             Data = Ptemp -> Left -> Data;   /*Save data pointer. */
  158.             PQDelete(&(Ptemp -> Left), Data);  /* Delete recurs. */
  159.             (*PQ) -> Data = Data; /* And put that data instead...*/
  160.             }
  161.             else {
  162.             Data = Ptemp -> Data;      /* Save the data pointer. */
  163.             PQDelete(&((*PQ) -> Right), Data); /* Delete recurs. */
  164.             (*PQ) -> Data = Data; /* And put that data instead...*/
  165.             }
  166.         }
  167.         else {                        /* Left != NULL. */
  168.             /* replace this node by the biggest in the Left branch:  */
  169.             /* move once to the Left and then Right all the time...  */
  170.             Ptemp = (*PQ) -> Left;
  171.             if (Ptemp -> Right != NULL)    {
  172.             while (Ptemp -> Right -> Right != NULL)
  173.                 Ptemp = Ptemp -> Right;
  174.             Data = Ptemp -> Right -> Data; /* Save data pointer. */
  175.             PQDelete(&(Ptemp -> Right), Data);  /*Delete recurs. */
  176.             (*PQ) -> Data = Data; /* And put that data instead...*/
  177.             }
  178.             else {
  179.             Data = Ptemp -> Data;      /* Save the data pointer. */
  180.             PQDelete(&((*PQ) -> Left), Data);  /* Delete recurs. */
  181.             (*PQ) -> Data = Data; /* And put that data instead...*/
  182.             }
  183.         }
  184.         return OldData;
  185.         case 1:
  186.         return PQDelete(&((*PQ) -> Left), OldItem);
  187.     }
  188.     }
  189.     return NULL;                    /* Makes warning silent. */
  190. }
  191.  
  192. /******************************************************************************
  193. * PQNext - returns the smallest item which is bigger than given item CmpItem. *
  194. * PQ is not modified. Return NULL if none was found.                  *
  195. * BiggerThan will allways hold the smallest Item bigger than current one.     *
  196. ******************************************************************************/
  197. VoidPtr PQNext(PriorQue *PQ, VoidPtr CmpItem, VoidPtr BiggerThan)
  198. {
  199.     int Compare;
  200.     PriorQue *Ptemp;
  201.  
  202.     if (PQ == NULL) return BiggerThan;
  203.     else {
  204.     Compare = (*CompFunc)(CmpItem, PQ -> Data);
  205.     Compare = SIGN(Compare);
  206.     switch (Compare) {
  207.         case -1:
  208.         return PQNext(PQ -> Right, CmpItem, PQ -> Data);
  209.         case 0:
  210.         /* Found it - if its right tree is not empty, returns its    */
  211.         /* smallest, else returns BiggerThan...                 */
  212.         if (PQ -> Left != NULL) {
  213.             Ptemp = PQ -> Left;
  214.             while (Ptemp -> Right != NULL) Ptemp = Ptemp -> Right;
  215.             return Ptemp -> Data;
  216.         }
  217.         else return BiggerThan;
  218.         case 1:
  219.         return PQNext(PQ -> Left, CmpItem, BiggerThan);
  220.     }
  221.     }
  222.     return NULL;                    /* Makes warning silent. */
  223. }
  224.  
  225. /******************************************************************************
  226. * PQPrint - print the queue in order using the given printing functionq       *
  227. * PrintFunc.                                      *
  228. ******************************************************************************/
  229. void PQPrint(PriorQue *PQ, void (*PrintFunc)())
  230. {
  231.     if (PQ == NULL) return;
  232.  
  233.     PQPrint(PQ -> Right, PrintFunc);
  234.  
  235.     (*PrintFunc)(PQ -> Data);
  236.  
  237.     PQPrint(PQ -> Left, PrintFunc);
  238. }
  239.  
  240. /******************************************************************************
  241. * PQFree - Free the queue. The items are also freed if FreeItems is TRUE.     *
  242. ******************************************************************************/
  243. void PQFree(PriorQue *PQ, int FreeItem)
  244. {
  245.     if (PQ == NULL) return;
  246.  
  247.     PQFree(PQ -> Right, FreeItem);
  248.     PQFree(PQ -> Left, FreeItem);
  249.  
  250.     if (FreeItem) MyFree((char *) PQ -> Data, OTHER_TYPE);
  251.     MyFree((char *) PQ, OTHER_TYPE);
  252. }
  253.  
  254.