Back to index

wims  3.65+svn20090927
Functions | Variables
heap.c File Reference
#include "vdefs.h"

Go to the source code of this file.

Functions

void PQinsert (Halfedge *he, Site *v, float offset)
void PQdelete (Halfedge *he)
int PQbucket (Halfedge *he)
int PQempty (void)
Point PQ_min (void)
HalfedgePQextractmin (void)
void PQinitialize (void)

Variables

int PQmin
int PQcount
int PQhashsize
HalfedgePQhash

Function Documentation

Point PQ_min ( void  )

Definition at line 82 of file heap.c.

    {
    Point answer ;

    while (PQhash[PQmin].PQnext == (Halfedge *)NULL)
        {
        ++PQmin ;
        }
    answer.x = PQhash[PQmin].PQnext->vertex->coord.x ;
    answer.y = PQhash[PQmin].PQnext->ystar ;
    return (answer) ;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

int PQbucket ( Halfedge he)

Definition at line 51 of file heap.c.

    {
    int bucket ;


    if     (he->ystar < ymin)  bucket = 0;
    else if (he->ystar >= ymax) bucket = PQhashsize-1;
    else                    bucket = (he->ystar - ymin)/deltay * PQhashsize;
    if (bucket < 0)
        {
        bucket = 0 ;
        }
    if (bucket >= PQhashsize)
        {
        bucket = PQhashsize-1 ;
        }
    if (bucket < PQmin)
        {
        PQmin = bucket ;
        }
    return (bucket);
    }

Here is the caller graph for this function:

void PQdelete ( Halfedge he)

Definition at line 32 of file heap.c.

    {
    Halfedge * last;

    if(he ->  vertex != (Site *) NULL)
        {
        last = &PQhash[PQbucket(he)] ;
        while (last -> PQnext != he)
            {
            last = last->PQnext ;
            }
        last->PQnext = he->PQnext;
        PQcount-- ;
        deref(he->vertex) ;
        he->vertex = (Site *)NULL ;
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

int PQempty ( void  )

Definition at line 75 of file heap.c.

    {
    return (PQcount == 0) ;
    }

Here is the caller graph for this function:

Halfedge* PQextractmin ( void  )

Definition at line 96 of file heap.c.

    {
    Halfedge * curr ;

    curr = PQhash[PQmin].PQnext ;
    PQhash[PQmin].PQnext = curr->PQnext ;
    PQcount-- ;
    return (curr) ;
    }

Here is the caller graph for this function:

void PQinitialize ( void  )

Definition at line 107 of file heap.c.

    {
    int i ;

    PQcount = PQmin = 0 ;
    PQhashsize = 4 * sqrt_nsites ;
    PQhash = (Halfedge *)myalloc(PQhashsize * sizeof *PQhash) ;
    for (i = 0 ; i < PQhashsize; i++)
        {
        PQhash[i].PQnext = (Halfedge *)NULL ;
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void PQinsert ( Halfedge he,
Site v,
float  offset 
)

Definition at line 11 of file heap.c.

    {
    Halfedge * last, * next ;

    he->vertex = v ;
    ref(v) ;
    he->ystar = v->coord.y + offset ;
    last = &PQhash[ PQbucket(he)] ;
    while ((next = last->PQnext) != (Halfedge *)NULL &&
      (he->ystar  > next->ystar  ||
      (he->ystar == next->ystar &&
      v->coord.x > next->vertex->coord.x)))
        {
        last = next ;
        }
    he->PQnext = last->PQnext ;
    last->PQnext = he ;
    PQcount++ ;
    }

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

int PQcount

Definition at line 7 of file heap.c.

Definition at line 8 of file heap.c.

Definition at line 7 of file heap.c.

int PQmin

Definition at line 7 of file heap.c.