HeapPQ class. More...

#include <VastDefs.h>

Public Member Functions
	HeapPQ ()
void	PQinitialize (int sqrt_nsites, double ymin, double deltay)
void	PQreset ()
void	PQinsert (Halfedge he, Site v, double offset)
void	PQdelete (Halfedge *he)
int	PQbucket (Halfedge *he)
int	PQempty ()
Vector2D	PQ_min ()
Halfedge *	PQextractmin ()
Protected Attributes
int	PQcount
int	PQmin
int	PQhashsize
double	ymin
double	deltay
Halfedge *	PQhash

Detailed Description

HeapPQ class.

Maintains a hash table in order to find halfedges in n*log(n) time.

Definition at line 100 of file VastDefs.h.

Constructor & Destructor Documentation

HeapPQ::HeapPQ ( )

Definition at line 73 of file VastDefs.cc.

{
    PQhash = NULL;
}

Member Function Documentation

Vector2D HeapPQ::PQ_min ( )

Definition at line 138 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    Vector2D answer;

    while(PQhash[PQmin].PQnext == NULL) PQmin++;

    answer.x = PQhash[PQmin].PQnext->vertex->coord.x;
    answer.y = PQhash[PQmin].PQnext->ystar;
    return answer;
}

int HeapPQ::PQbucket ( Halfedge * he )

Definition at line 122 of file VastDefs.cc.

Referenced by PQdelete(), and PQinsert().

{
    int bucket;

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

void HeapPQ::PQdelete ( Halfedge * he )

Definition at line 108 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    Halfedge *last;

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

        last->PQnext = he->PQnext;
        PQcount--;
        he->vertex = NULL;
    }
}

int HeapPQ::PQempty ( )

Definition at line 133 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    return PQcount==0;
}

Halfedge * HeapPQ::PQextractmin ( )

Definition at line 149 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    Halfedge *curr;

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

void HeapPQ::PQinitialize	(	int	sqrt_nsites,
		double	ymin,
		double	deltay
	)

Definition at line 78 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    PQcount = 0;
    PQmin = 0;
    PQhashsize = 4 * sqrt_nsites;
    PQhash = new Halfedge[PQhashsize];
    this->ymin = ymin;
    this->deltay = deltay;
}

void HeapPQ::PQinsert	(	Halfedge *	he,
		Site *	v,
		double	offset
	)

Definition at line 93 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
    Halfedge *last, *next;

    he->vertex = v;
    he->ystar = v->coord.y + offset;
    last = &PQhash[PQbucket(he)];
    while((next = last->PQnext) != 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++;
}