ANNpr_queue Class Reference

#include <pr_queue.h>

Collaboration diagram for ANNpr_queue:

List of all members.

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)

---

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 QuadProgPP::max().

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

                { delete [] pq; }

---

Member Function Documentation

ANNbool ANNpr_queue::empty

(

)

[inline]

Definition at line 75 of file pr_queue.h.

References ANNfalse, and ANNtrue.

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

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

Definition at line 102 of file pr_queue.h.

References ANN_FLOP.

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, and annError().

Referenced by ANNkd_split::ann_pri_search(), ANNbd_shrink::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;
                }

ANNbool ANNpr_queue::non_empty

(

)

[inline]

Definition at line 78 of file pr_queue.h.

References ANNfalse, and ANNtrue.

Referenced by ANNkd_tree::annkPriSearch().

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

void ANNpr_queue::reset

(

)

[inline]

Definition at line 81 of file pr_queue.h.

                { n = 0; }

---

The documentation for this class was generated from the following file:

• pr_queue.h