/*
 * The author of this software is Steven Fortune.  Copyright (c) 1994 by AT&T
 * Bell Laboratories.
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.- */

#
#include "vdefs.h"

#ifndef lint
static char RCSid[] = "$Id: vheap.c,v 1.2 2003/07/24 15:44:06 pturner Exp $";
#endif

/* vheap.c */
void PQinsert(struct Halfedge *he, struct Site *v, double offset);
void PQdelete(struct Halfedge *he);
int PQbucket(struct Halfedge *he);
int PQempty(void);
struct Point PQ_min(void);
struct Halfedge *PQextractmin(void);
void PQinitialize(void);

void PQinsert(struct Halfedge * he, struct Site * v, double offset)
{
    struct Halfedge *last, *next;

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

void PQdelete(struct Halfedge * he)
{
    struct Halfedge *last;

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

int PQbucket(struct Halfedge * he)
{
    int bucket;

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



int PQempty(void)
{
    return (PQcount == 0);
}


struct Point PQ_min(void)
{
    struct Point answer;

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

struct Halfedge *PQextractmin(void)
{
    struct Halfedge *curr;

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


void PQinitialize(void)
{
    int i;
    struct Point *s;

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