priorityq.h File Reference

#include "priorityq-heap.h"

Include dependency graph for priorityq.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	PriorityQ

Macros
#define	PQkey   PQSortKey
#define	PQhandle   PQSortHandle
#define	PriorityQ   PriorityQSort
#define	pqNewPriorityQ(leq)   __gl_pqSortNewPriorityQ(leq)
#define	pqDeletePriorityQ(pq)   __gl_pqSortDeletePriorityQ(pq)
#define	pqInit(pq)   __gl_pqSortInit(pq)
#define	pqInsert(pq, key)   __gl_pqSortInsert(pq,key)
#define	pqMinimum(pq)   __gl_pqSortMinimum(pq)
#define	pqExtractMin(pq)   __gl_pqSortExtractMin(pq)
#define	pqDelete(pq, handle)   __gl_pqSortDelete(pq,handle)
#define	pqIsEmpty(pq)   __gl_pqSortIsEmpty(pq)

Typedefs
typedef PQHeapKey	PQkey
typedef PQHeapHandle	PQhandle
typedef struct PriorityQ	PriorityQ

Functions
PriorityQ *	pqNewPriorityQ (int(*leq)(PQkey key1, PQkey key2))
void	pqDeletePriorityQ (PriorityQ *pq)
int	pqInit (PriorityQ *pq)
PQhandle	pqInsert (PriorityQ *pq, PQkey key)
PQkey	pqExtractMin (PriorityQ *pq)
void	pqDelete (PriorityQ *pq, PQhandle handle)
PQkey	pqMinimum (PriorityQ *pq)
int	pqIsEmpty (PriorityQ *pq)

Macro Definition Documentation

pqDelete

#define pqDelete	(		pq,
			handle
	)		__gl_pqSortDelete(pq,handle)

Definition at line 78 of file priorityq.h.

pqDeletePriorityQ

#define pqDeletePriorityQ

(

pq

)

__gl_pqSortDeletePriorityQ(pq)

Definition at line 59 of file priorityq.h.

pqExtractMin

#define pqExtractMin

(

pq

)

__gl_pqSortExtractMin(pq)

Definition at line 77 of file priorityq.h.

PQhandle

#define PQhandle   PQSortHandle

Definition at line 55 of file priorityq.h.

pqInit

#define pqInit

(

pq

)

__gl_pqSortInit(pq)

Definition at line 74 of file priorityq.h.

pqInsert

#define pqInsert	(		pq,
			key
	)		__gl_pqSortInsert(pq,key)

Definition at line 75 of file priorityq.h.

pqIsEmpty

#define pqIsEmpty

(

pq

)

__gl_pqSortIsEmpty(pq)

Definition at line 79 of file priorityq.h.

PQkey

#define PQkey   PQSortKey

Definition at line 54 of file priorityq.h.

pqMinimum

#define pqMinimum

(

pq

)

__gl_pqSortMinimum(pq)

Definition at line 76 of file priorityq.h.

pqNewPriorityQ

#define pqNewPriorityQ

(

leq

)

__gl_pqSortNewPriorityQ(leq)

Definition at line 58 of file priorityq.h.

PriorityQ

#define PriorityQ   PriorityQSort

Definition at line 56 of file priorityq.h.

Typedef Documentation

PQhandle

typedef PQHeapHandle PQhandle

Definition at line 94 of file priorityq.h.

PQkey

typedef PQHeapKey PQkey

Definition at line 93 of file priorityq.h.

PriorityQ

typedef struct PriorityQ PriorityQ

Definition at line 95 of file priorityq.h.

Function Documentation

pqDelete()

void pqDelete	(	PriorityQ *	pq,
		PQhandle	handle
	)

Definition at line 234 of file priorityq-heap.c.

{
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  long curr;
 
  assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL );
 
  curr = h[hCurr].node;
  n[curr].handle = n[pq->size].handle;
  h[n[curr].handle].node = curr;
 
  if( curr <= -- pq->size ) {
    if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) {
      FloatDown( pq, curr );
    } else {
      FloatUp( pq, curr );
    }
  }
  h[hCurr].key = NULL;
  h[hCurr].node = pq->freeList;
  pq->freeList = hCurr;
}

pqDeletePriorityQ()

void pqDeletePriorityQ

(

PriorityQ *

pq

)

Definition at line 88 of file priorityq-heap.c.

{
  memFree( pq->handles );
  memFree( pq->nodes );
  memFree( pq );
}

pqExtractMin()

PQkey pqExtractMin

(

PriorityQ *

pq

)

Definition at line 211 of file priorityq-heap.c.

{
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hMin = n[1].handle;
  PQkey min = h[hMin].key;
 
  if( pq->size > 0 ) {
    n[1].handle = n[pq->size].handle;
    h[n[1].handle].node = 1;
 
    h[hMin].key = NULL;
    h[hMin].node = pq->freeList;
    pq->freeList = hMin;
 
    if( -- pq->size > 0 ) {
      FloatDown( pq, 1 );
    }
  }
  return min;
}

pqInit()

int pqInit

(

PriorityQ *

pq

)

Definition at line 149 of file priorityq-heap.c.

{
  long i;
 
  /* This method of building a heap is O(n), rather than O(n lg n). */
 
  for( i = pq->size; i >= 1; --i ) {
    FloatDown( pq, i );
  }
  pq->initialized = TRUE;
}

pqInsert()

PQhandle pqInsert	(	PriorityQ *	pq,
		PQkey	key
	)

Definition at line 163 of file priorityq-heap.c.

{
  long curr;
  PQhandle free_handle;
 
  curr = ++ pq->size;
  if( (curr*2) > pq->max ) {
    PQnode *saveNodes= pq->nodes;
    PQhandleElem *saveHandles= pq->handles;
 
    /* If the heap overflows, double its size. */
    pq->max <<= 1;
    pq->nodes = (PQnode *)memRealloc( pq->nodes, 
                     (size_t) 
                     ((pq->max + 1) * sizeof( pq->nodes[0] )));
    if (pq->nodes == NULL) {
       pq->nodes = saveNodes;   /* restore ptr to free upon return */
       return LONG_MAX;
    }
    pq->handles = (PQhandleElem *)memRealloc( pq->handles,
                                 (size_t)
                                  ((pq->max + 1) * 
                           sizeof( pq->handles[0] )));
    if (pq->handles == NULL) {
       pq->handles = saveHandles; /* restore ptr to free upon return */
       return LONG_MAX;
    }
  }
 
  if( pq->freeList == 0 ) {
    free_handle = curr;
  } else {
    free_handle = pq->freeList;
    pq->freeList = pq->handles[free_handle].node;
  }
 
  pq->nodes[curr].handle = free_handle;
  pq->handles[free_handle].node = curr;
  pq->handles[free_handle].key = keyNew;
 
  if( pq->initialized ) {
    FloatUp( pq, curr );
  }
  assert(free_handle != LONG_MAX);
  return free_handle;
}

pqIsEmpty()

int pqIsEmpty

(

PriorityQ *

pq

)

Definition at line 242 of file priorityq.c.

{
  return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
}

pqMinimum()

PQkey pqMinimum

(

PriorityQ *

pq

)

Definition at line 224 of file priorityq.c.

{
  PQkey sortMin, heapMin;
 
  if( pq->size == 0 ) {
    return __gl_pqHeapMinimum( pq->heap );
  }
  sortMin = *(pq->order[pq->size-1]);
  if( ! __gl_pqHeapIsEmpty( pq->heap )) {
    heapMin = __gl_pqHeapMinimum( pq->heap );
    if( LEQ( heapMin, sortMin )) {
      return heapMin;
    }
  }
  return sortMin;
}

pqNewPriorityQ()

PriorityQ * pqNewPriorityQ

(

int(*)(PQkey key1, PQkey key2)

leq

)

Definition at line 58 of file priorityq-heap.c.

{
  PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
  if (pq == NULL) return NULL;
 
  pq->size = 0;
  pq->max = INIT_SIZE;
  pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) );
  if (pq->nodes == NULL) {
     memFree(pq);
     return NULL;
  }
 
  pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) );
  if (pq->handles == NULL) {
     memFree(pq->nodes);
     memFree(pq);
     return NULL;
  }
 
  pq->initialized = FALSE;
  pq->freeList = 0;
  pq->leq = leq;
 
  pq->nodes[1].handle = 1;  /* so that Minimum() returns NULL */
  pq->handles[1].key = NULL;
  return pq;
}