text: /*!
  \file  gk_mkpqueue2.h
  \brief Templates for priority queues that do not utilize locators and as such
         they can use different types of values.
  
  \date   Started 4/09/07
  \author George
  */
  
  
  #ifndef _GK_MKPQUEUE2_H
  #define _GK_MKPQUEUE2_H
  
  
  #define GK_MKPQUEUE2(FPRFX, PQT, KT, VT, KMALLOC, VMALLOC, KMAX, KEY_LT)\
  /*************************************************************************/\
  /*! This function creates and initializes a priority queue */\
  /**************************************************************************/\
  PQT *FPRFX ## Create2(ssize_t maxnodes)\
  {\
    PQT *queue; \
  \
    if ((queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate2: queue")) != NULL) {\
      memset(queue, 0, sizeof(PQT));\
      queue->nnodes   = 0;\
      queue->maxnodes = maxnodes;\
      queue->keys     = KMALLOC(maxnodes, "gk_pqCreate2: keys");\
      queue->vals     = VMALLOC(maxnodes, "gk_pqCreate2: vals");\
  \
      if (queue->keys == NULL || queue->vals == NULL)\
        gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
    }\
  \
    return queue;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function resets the priority queue */\
  /**************************************************************************/\
  void FPRFX ## Reset2(PQT *queue)\
  {\
    queue->nnodes = 0;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function frees the internal datastructures of the priority queue */\
  /**************************************************************************/\
  void FPRFX ## Destroy2(PQT **r_queue)\
  {\
    PQT *queue = *r_queue; \
    if (queue == NULL) return;\
    gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
    *r_queue = NULL;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function returns the length of the queue */\
  /**************************************************************************/\
  size_t FPRFX ## Length2(PQT *queue)\
  {\
    return queue->nnodes;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function adds an item in the priority queue. */\
  /**************************************************************************/\
  int FPRFX ## Insert2(PQT *queue, VT val, KT key)\
  {\
    ssize_t i, j;\
    KT *keys=queue->keys;\
    VT *vals=queue->vals;\
  \
    ASSERT2(FPRFX ## CheckHeap2(queue));\
  \
    if (queue->nnodes == queue->maxnodes) \
      return 0;\
  \
    ASSERT2(FPRFX ## CheckHeap2(queue));\
  \
    i = queue->nnodes++;\
    while (i > 0) {\
      j = (i-1)>>1;\
      if (KEY_LT(key, keys[j])) {\
        keys[i] = keys[j];\
        vals[i] = vals[j];\
        i = j;\
      }\
      else\
        break;\
    }\
    ASSERT(i >= 0);\
    keys[i] = key;\
    vals[i] = val;\
  \
    ASSERT2(FPRFX ## CheckHeap2(queue));\
  \
    return 1;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function returns the item at the top of the queue and removes\
      it from the priority queue */\
  /**************************************************************************/\
  int FPRFX ## GetTop2(PQT *queue, VT *r_val)\
  {\
    ssize_t i, j;\
    KT key, *keys=queue->keys;\
    VT val, *vals=queue->vals;\
  \
    ASSERT2(FPRFX ## CheckHeap2(queue));\
  \
    if (queue->nnodes == 0)\
      return 0;\
  \
    queue->nnodes--;\
  \
    *r_val = vals[0];\
  \
    if ((i = queue->nnodes) > 0) {\
      key = keys[i];\
      val = vals[i];\
      i = 0;\
      while ((j=2*i+1) < queue->nnodes) {\
        if (KEY_LT(keys[j], key)) {\
          if (j+1 < queue->nnodes && KEY_LT(keys[j+1], keys[j]))\
            j = j+1;\
          keys[i] = keys[j];\
          vals[i] = vals[j];\
          i = j;\
        }\
        else if (j+1 < queue->nnodes && KEY_LT(keys[j+1], key)) {\
          j = j+1;\
          keys[i] = keys[j];\
          vals[i] = vals[j];\
          i = j;\
        }\
        else\
          break;\
      }\
  \
      keys[i] = key;\
      vals[i] = val;\
    }\
  \
    ASSERT2(FPRFX ## CheckHeap2(queue));\
  \
    return 1;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function returns the item at the top of the queue. The item is not\
      deleted from the queue. */\
  /**************************************************************************/\
  int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val)\
  {\
    if (queue->nnodes == 0) \
      return 0;\
  \
    *r_val = queue->vals[0];\
  \
    return 1;\
  }\
  \
  \
  /*************************************************************************/\
  /*! This function returns the key of the top item. The item is not\
      deleted from the queue. */\
  /**************************************************************************/\
  KT FPRFX ## SeeTopKey2(PQT *queue)\
  {\
    return (queue->nnodes == 0 ? KMAX : queue->keys[0]);\
  }\
  \
  \
  /*************************************************************************/\
  /*! This functions checks the consistency of the heap */\
  /**************************************************************************/\
  int FPRFX ## CheckHeap2(PQT *queue)\
  {\
    ssize_t i;\
    KT *keys=queue->keys;\
  \
    if (queue->nnodes == 0)\
      return 1;\
  \
    for (i=1; i<queue->nnodes; i++) {\
      ASSERT(!KEY_LT(keys[i], keys[(i-1)/2]));\
    }\
    for (i=1; i<queue->nnodes; i++)\
      ASSERT(!KEY_LT(keys[i], keys[0]));\
  \
    return 1;\
  }\
  
  
  #define GK_MKPQUEUE2_PROTO(FPRFX, PQT, KT, VT)\
    PQT *  FPRFX ## Create2(ssize_t maxnodes);\
    void   FPRFX ## Reset2(PQT *queue);\
    void   FPRFX ## Destroy2(PQT **r_queue);\
    size_t FPRFX ## Length2(PQT *queue);\
    int    FPRFX ## Insert2(PQT *queue, VT node, KT key);\
    int    FPRFX ## GetTop2(PQT *queue, VT *r_val);\
    int    FPRFX ## SeeTopVal2(PQT *queue, VT *r_val);\
    KT     FPRFX ## SeeTopKey2(PQT *queue);\
    int    FPRFX ## CheckHeap2(PQT *queue);\
  
  
  #endif
  