//----------------------------------------------------------------------
// File:			pr_queue.h
// Programmer:		Sunil Arya and David Mount
// Description:		Include file for priority queue and related
// 					structures.
// Last modified:	01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
// 
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
// 
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//	Revision 0.1  03/04/98
//		Initial release
//----------------------------------------------------------------------

#ifndef PR_QUEUE_H
#define PR_QUEUE_H

#include <ANN/ANNx.h>					// all ANN includes
#include <ANN/ANNperf.h>				// performance evaluation

//----------------------------------------------------------------------
//	Basic types.
//----------------------------------------------------------------------
typedef void			*PQinfo;		// info field is generic pointer
typedef ANNdist			PQkey;			// key field is distance

//----------------------------------------------------------------------
//	Priority queue
//		A priority queue is a list of items, along with associated
//		priorities.  The basic operations are insert and extract_minimum.
//
//		The priority queue is maintained using a standard binary heap.
//		(Implementation note: Indexing is performed from [1..max] rather
//		than the C standard of [0..max-1].  This simplifies parent/child
//		computations.)  User information consists of a void pointer,
//		and the user is responsible for casting this quantity into whatever
//		useful form is desired.
//
//		Because the priority queue is so central to the efficiency of
//		query processing, all the code is inline.
//----------------------------------------------------------------------

class ANNpr_queue {

	struct pq_node {					// node in priority queue
		PQkey			key;			// key value
		PQinfo			info;			// info field
	};
	int			n;						// number of items in queue
	int			max_size;				// maximum queue size
	pq_node		*pq;					// the priority queue (array of nodes)

public:
	ANNpr_queue(int max)				// constructor (given max size)
		{
			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()						// destructor
		{ delete [] pq; }

	ANNbool empty()						// is queue empty?
		{ if (n==0) return ANNtrue; else return ANNfalse; }

	ANNbool non_empty()					// is queue nonempty?
		{ if (n==0) return ANNfalse; else return ANNtrue; }

	void reset()						// make existing queue empty
		{ n = 0; }

	inline void insert(					// insert item (inlined for speed)
		PQkey kv,						// key value
		PQinfo inf)						// item info
		{
			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;
		}

	inline void extr_min(				// extract minimum (inlined for speed)
		PQkey &kv,						// key (returned)
		PQinfo &inf)					// item info (returned)
		{
			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
		}
};

#endif