#include <pr_queue.h>

Collaboration diagram for ANNpr_queue:

Classes
struct	pq_node

Public Member Functions
	ANNpr_queue (int max)

	~ANNpr_queue ()

ANNbool	empty ()

ANNbool	non_empty ()

void	reset ()

void	insert (PQkey kv, PQinfo inf)

void	extr_min (PQkey &kv, PQinfo &inf)

Private Attributes
int	n

int	max_size

pq_node *	pq

Detailed Description

Definition at line 54 of file pr_queue.h.

Constructor & Destructor Documentation

ANNpr_queue::ANNpr_queue ( int max )

inline

Definition at line 65 of file pr_queue.h.

References max_size, n, and pq.

                 {
                         n = 0;                                          // initially empty
                         max_size = max;                         // maximum number of items
                         pq = new pq_node[max+1];        // queue is array [1..max] of nodes
                 }

ANNpr_queue::~ANNpr_queue ( )

inline

Definition at line 72 of file pr_queue.h.

References pq.

73 { delete [] pq; }

ANNpr_queue::pq

pq_node * pq

Definition: pr_queue.h:62

Member Function Documentation

ANNbool ANNpr_queue::empty ( )

inline

Definition at line 75 of file pr_queue.h.

References ANNfalse, ANNtrue, and n.

76 { if (n==0) return ANNtrue; else return ANNfalse; }

ANNtrue

Definition: ANN.h:132

ANNfalse

Definition: ANN.h:132

ANNpr_queue::n

int n

Definition: pr_queue.h:60

void ANNpr_queue::extr_min	(	PQkey &	kv,
		PQinfo &	inf
	)

inline

Definition at line 102 of file pr_queue.h.

References ANN_FLOP, ANNpr_queue::pq_node::info, ANNpr_queue::pq_node::key, n, and pq.

Referenced by ANNkd_tree::annkPriSearch().

                 {
                         kv = pq[1].key;                         // key of min item
                         inf = pq[1].info;                       // information of min item
                         register PQkey kn = pq[n--].key;// last item in queue
                         register int p = 1;                     // p points to item out of position
                         register int r = p<<1;          // left child of p
                         while (r <= n) {                        // while r is still within the heap
                                 ANN_FLOP(2)                             // increment floating ops
                                                                                 // set r to smaller child of p
                                 if (r < n  && pq[r].key > pq[r+1].key) r++;
                                 if (kn <= pq[r].key)    // in proper order
                                         break;
                                 pq[p] = pq[r];                  // else swap with child
                                 p = r;                                  // advance pointers
                                 r = p<<1;
                         }
                         pq[p] = pq[n+1];                        // insert last item in proper place
                 }

void ANNpr_queue::insert	(	PQkey	kv,
		PQinfo	inf
	)

inline

Definition at line 84 of file pr_queue.h.

References ANN_FLOP, ANNabort, annError(), ANNpr_queue::pq_node::info, ANNpr_queue::pq_node::key, max_size, n, and pq.

Referenced by ANNbd_shrink::ann_pri_search(), ANNkd_split::ann_pri_search(), and ANNkd_tree::annkPriSearch().

                 {
                         if (++n > max_size) annError("Priority queue overflow.", ANNabort);
                         register int r = n;
                         while (r > 1) {                         // sift up new item
                                 register int p = r/2;
                                 ANN_FLOP(1)                             // increment floating ops
                                 if (pq[p].key <= kv)    // in proper order
                                         break;
                                 pq[r] = pq[p];                  // else swap with parent
                                 r = p;
                         }
                         pq[r].key = kv;                         // insert new item at final location
                         pq[r].info = inf;
                 }