priorityq File Reference

#include <climits>
#include "memalloc"
#include "geom"

Include dependency graph for priorityq:

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

Go to the source code of this file.

Classes
struct	PQnode
struct	PQhandleElem
struct	PriorityQ
struct	PriorityQ

Macros
#define	tools_glutess_priorityq
#define	PQkey   PQHeapKey
#define	PQhandle   PQHeapHandle
#define	PriorityQ   PriorityQHeap
#define	pqNewPriorityQ(leq)   __gl_pqHeapNewPriorityQ(leq)
#define	pqDeletePriorityQ(pq)   __gl_pqHeapDeletePriorityQ(pq)
#define	pqInit(pq)   __gl_pqHeapInit(pq)
#define	pqInsert(pq, key)   __gl_pqHeapInsert(pq,key)
#define	pqMinimum(pq)   __gl_pqHeapMinimum(pq)
#define	pqExtractMin(pq)   __gl_pqHeapExtractMin(pq)
#define	pqDelete(pq, handle)   __gl_pqHeapDelete(pq,handle)
#define	pqIsEmpty(pq)   __gl_pqHeapIsEmpty(pq)
#define	__gl_pqHeapMinimum(pq)   ((pq)->handles[(pq)->nodes[1].handle].key)
#define	__gl_pqHeapIsEmpty(pq)   ((pq)->size == 0)
#define	LEQ(x, y)   VertLeq((GLUvertex *)x, (GLUvertex *)y)
#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)
#define	LT(x, y)   (! LEQ(y,x))
#define	GT(x, y)   (! LEQ(x,y))
#define	pq_Swap(a, b)   do{PQkey *tmp = *a; *a = *b; *b = tmp;} while(false)

Typedefs
typedef void *	PQkey
typedef long	PQhandle
typedef struct PriorityQ	PriorityQ

Functions
long	INIT_SIZE ()
PriorityQ *	pqNewPriorityQ (int(*leq)(PQkey key1, PQkey key2))
void	pqDeletePriorityQ (PriorityQ *pq)
inline void	static_FloatDown (PriorityQ *pq, long curr)
inline void	static_FloatUp (PriorityQ *pq, long curr)
void	pqInit (PriorityQ *pq)
PQhandle	pqInsert (PriorityQ *pq, PQkey keyNew)
PQkey	pqExtractMin (PriorityQ *pq)
void	pqDelete (PriorityQ *pq, PQhandle hCurr)
PQkey	pqMinimum (PriorityQ *pq)
int	pqIsEmpty (PriorityQ *pq)

Macro Definition Documentation

__gl_pqHeapIsEmpty

#define __gl_pqHeapIsEmpty

(

pq

)

((pq)->size == 0)

Definition at line 72 of file priorityq.

__gl_pqHeapMinimum

#define __gl_pqHeapMinimum

(

pq

)

((pq)->handles[(pq)->nodes[1].handle].key)

Definition at line 71 of file priorityq.

GT

#define GT	(		x,
			y
	)		(! LEQ(x,y))

Definition at line 396 of file priorityq.

LEQ

#define LEQ	(		x,
			y
	)		VertLeq((GLUvertex *)x, (GLUvertex *)y)

Definition at line 84 of file priorityq.

LT

#define LT	(		x,
			y
	)		(! LEQ(y,x))

Definition at line 395 of file priorityq.

pq_Swap

#define pq_Swap	(		a,
			b
	)		do{PQkey *tmp = *a; *a = *b; *b = tmp;} while(false)

Definition at line 398 of file priorityq.

pqDelete [1/2]

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

Definition at line 330 of file priorityq.

pqDelete [2/2]

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

Definition at line 330 of file priorityq.

pqDeletePriorityQ [1/2]

#define pqDeletePriorityQ

(

pq

)

__gl_pqHeapDeletePriorityQ(pq)

Definition at line 311 of file priorityq.

pqDeletePriorityQ [2/2]

#define pqDeletePriorityQ

(

pq

)

__gl_pqSortDeletePriorityQ(pq)

Definition at line 311 of file priorityq.

pqExtractMin [1/2]

#define pqExtractMin

(

pq

)

__gl_pqHeapExtractMin(pq)

Definition at line 329 of file priorityq.

pqExtractMin [2/2]

#define pqExtractMin

(

pq

)

__gl_pqSortExtractMin(pq)

Definition at line 329 of file priorityq.

PQhandle [1/2]

typedef PQHeapHandle PQhandle   PQHeapHandle

Definition at line 307 of file priorityq.

PQhandle [2/2]

#define PQhandle   PQSortHandle

Definition at line 307 of file priorityq.

pqInit [1/2]

#define pqInit

(

pq

)

__gl_pqHeapInit(pq)

Definition at line 326 of file priorityq.

pqInit [2/2]

#define pqInit

(

pq

)

__gl_pqSortInit(pq)

Definition at line 326 of file priorityq.

pqInsert [1/2]

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

Definition at line 327 of file priorityq.

pqInsert [2/2]

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

Definition at line 327 of file priorityq.

pqIsEmpty [1/2]

#define pqIsEmpty

(

pq

)

__gl_pqHeapIsEmpty(pq)

Definition at line 331 of file priorityq.

pqIsEmpty [2/2]

#define pqIsEmpty

(

pq

)

__gl_pqSortIsEmpty(pq)

Definition at line 331 of file priorityq.

PQkey [1/2]

typedef PQHeapKey PQkey   PQHeapKey

Definition at line 306 of file priorityq.

PQkey [2/2]

#define PQkey   PQSortKey

Definition at line 306 of file priorityq.

pqMinimum [1/2]

#define pqMinimum

(

pq

)

__gl_pqHeapMinimum(pq)

Definition at line 328 of file priorityq.

pqMinimum [2/2]

#define pqMinimum

(

pq

)

__gl_pqSortMinimum(pq)

Definition at line 328 of file priorityq.

pqNewPriorityQ [1/2]

#define pqNewPriorityQ

(

leq

)

__gl_pqHeapNewPriorityQ(leq)

Definition at line 310 of file priorityq.

pqNewPriorityQ [2/2]

#define pqNewPriorityQ

(

leq

)

__gl_pqSortNewPriorityQ(leq)

Definition at line 310 of file priorityq.

PriorityQ [1/2]

typedef struct PriorityQ PriorityQ   PriorityQHeap

Definition at line 308 of file priorityq.

PriorityQ [2/2]

#define PriorityQ   PriorityQSort

Definition at line 308 of file priorityq.

tools_glutess_priorityq

#define tools_glutess_priorityq

Definition at line 4 of file priorityq.

Typedef Documentation

PQhandle

typedef PQHeapHandle PQhandle

Definition at line 56 of file priorityq.

PQkey

typedef PQHeapKey PQkey

Definition at line 55 of file priorityq.

PriorityQ

typedef struct PriorityQ PriorityQ

Definition at line 56 of file priorityq.

Function Documentation

INIT_SIZE()

long INIT_SIZE ( )

inline

Definition at line 77 of file priorityq.

                        {
  static const long s_value = 32;
  return s_value;
}

pqDelete()

void pqDelete ( PriorityQ *  pq, PQhandle  hCurr  )

inline

Definition at line 263 of file priorityq.

{
  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 )) {
      static_FloatDown( pq, curr );
    } else {
      static_FloatUp( pq, curr );
    }
  }
  h[hCurr].key = NULL;
  h[hCurr].node = pq->freeList;
  pq->freeList = hCurr;
}

pqDeletePriorityQ()

void pqDeletePriorityQ ( PriorityQ *  pq )

inline

Definition at line 117 of file priorityq.

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

pqExtractMin()

PQkey pqExtractMin ( PriorityQ *  pq )

inline

Definition at line 240 of file priorityq.

{
  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 ) {
      static_FloatDown( pq, 1 );
    }
  }
  return min;
}

pqInit()

int pqInit ( PriorityQ *  pq )

inline

Definition at line 178 of file priorityq.

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

pqInsert()

PQhandle pqInsert ( PriorityQ *  pq, PQkey  keyNew  )

inline

Definition at line 192 of file priorityq.

{
  long curr;
  PQhandle free;
 
  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 = curr;
  } else {
    free = pq->freeList;
    pq->freeList = pq->handles[free].node;
  }
 
  pq->nodes[curr].handle = free;
  pq->handles[free].node = curr;
  pq->handles[free].key = keyNew;
 
  if( pq->initialized ) {
    static_FloatUp( pq, curr );
  }
  assert(free != LONG_MAX);
  return free;
}

pqIsEmpty()

int pqIsEmpty ( PriorityQ *  pq )

inline

Definition at line 551 of file priorityq.

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

pqMinimum()

PQkey pqMinimum ( PriorityQ *  pq )

inline

Definition at line 533 of file priorityq.

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

inline

Definition at line 87 of file priorityq.

{
  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 = TOOLS_GLU_FALSE;
  pq->freeList = 0;
  pq->leq = leq;
 
  pq->nodes[1].handle = 1;  /* so that Minimum() returns NULL */
  pq->handles[1].key = NULL;
  return pq;
}

static_FloatDown()

inline void static_FloatDown	(	PriorityQ *	pq,
		long	curr
	)

Definition at line 125 of file priorityq.

{
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hCurr, hChild;
  long child;
 
  hCurr = n[curr].handle;
  for( ;; ) {
    child = curr << 1;
    if( child < pq->size && LEQ( h[n[child+1].handle].key,
                 h[n[child].handle].key )) {
      ++child;
    }
 
    assert(child <= pq->max);
 
    hChild = n[child].handle;
    if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) {
      n[curr].handle = hCurr;
      h[hCurr].node = curr;
      break;
    }
    n[curr].handle = hChild;
    h[hChild].node = curr;
    curr = child;
  }
}

static_FloatUp()

inline void static_FloatUp	(	PriorityQ *	pq,
		long	curr
	)

Definition at line 155 of file priorityq.

{
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hCurr, hParent;
  long parent;
 
  hCurr = n[curr].handle;
  for( ;; ) {
    parent = curr >> 1;
    hParent = n[parent].handle;
    if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) {
      n[curr].handle = hCurr;
      h[hCurr].node = curr;
      break;
    }
    n[curr].handle = hParent;
    h[hParent].node = curr;
    curr = parent;
  }
}