priorityq-sort.h File Reference

#include "priorityq-heap.h"

Include dependency graph for priorityq-sort.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)

pqDeletePriorityQ

#define pqDeletePriorityQ

(

pq

)

__gl_pqSortDeletePriorityQ(pq)

pqExtractMin

#define pqExtractMin

(

pq

)

__gl_pqSortExtractMin(pq)

PQhandle

#define PQhandle   PQSortHandle

pqInit

#define pqInit

(

pq

)

__gl_pqSortInit(pq)

pqInsert

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

pqIsEmpty

#define pqIsEmpty

(

pq

)

__gl_pqSortIsEmpty(pq)

PQkey

#define PQkey   PQSortKey

pqMinimum

#define pqMinimum

(

pq

)

__gl_pqSortMinimum(pq)

pqNewPriorityQ

#define pqNewPriorityQ

(

leq

)

__gl_pqSortNewPriorityQ(leq)

PriorityQ

#define PriorityQ   PriorityQSort

Typedef Documentation

PQhandle

typedef PQHeapHandle PQhandle

PQkey

typedef PQHeapKey PQkey

PriorityQ

typedef struct PriorityQ PriorityQ

Function Documentation

pqDelete()

void pqDelete	(	PriorityQ *	pq,
		PQhandle	handle
	)

{
  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

)

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

pqExtractMin()

PQkey pqExtractMin

(

PriorityQ *

pq

)

{
  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

)

{
  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
	)

{
  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

)

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

References __gl_pqHeapIsEmpty, PriorityQ::heap, and PriorityQ::size.

pqMinimum()

PQkey pqMinimum

(

PriorityQ *

pq

)

{
  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;
}

References __gl_pqHeapIsEmpty, __gl_pqHeapMinimum, PriorityQ::heap, LEQ, PriorityQ::order, and PriorityQ::size.

pqNewPriorityQ()

PriorityQ * pqNewPriorityQ

(

int(*)(PQkey key1, PQkey key2)

leq

)

{
  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;
}