// -*- c++ -*-
//------------------------------------------------------------------------------
//                        PriorityQueue_Heap.h
//------------------------------------------------------------------------------
//  Copyright (c) 1999 by Vladislav Grinchenko
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Library General Public
//  License as published by the Free Software Foundation; either
//  version 2 of the License, or (at your option) any later version.
//------------------------------------------------------------------------------
#ifndef PRIORITY_QUEUE_HEAP_H
#define PRIORITY_QUEUE_HEAP_H

#include <sys/types.h>
#include <string.h>

#include "assa/PriorityQueue_Impl.h"

namespace ASSA {

/** @file PriorityQueue_Heap.h

    Heap-based implementation of PriorityQueue algorithm based on
	Robert Sedgewick's "Algorithms in C++", Ch. 11.
*/

template< class T, class Compare >
class PriorityQueue_Heap : public PriorityQueue_Impl< T, Compare >
{
public:
	PriorityQueue_Heap (size_t max_ = 0);
	PriorityQueue_Heap (size_t, const Compare&);
	PriorityQueue_Heap (const PriorityQueue_Heap&);
	~PriorityQueue_Heap ();

	PriorityQueue_Heap& operator= (const PriorityQueue_Heap&);

	void     insert (const T&);
	T        pop ();
	const T& top () const;
	bool     remove (T);
	size_t   size ();
	T&       operator[] (int idx);

protected:
	void upheap (size_t);
	void downheap (size_t);
	bool resize (size_t);

	Compare m_comp;
	
private:
	void allocate (size_t);

	T* m_queue;					/// Array of queued pointers
	size_t  m_size;				/// Array's size
	size_t  m_curr;				/// Next free slot in array
	size_t  m_lwm;				/// Low water mark
};

template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (size_t maxsz_)
	: m_curr (1), m_lwm (20)
{
	trace("PriorityQueue_Heap::PriorityQueue_Heap");
	allocate (maxsz_);
}

template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (size_t maxsz_, const Compare& x_)
	: m_comp (x_), m_curr (1), m_lwm (20)
{
	allocate (maxsz_);
}

template< class T, class Compare>
inline void
PriorityQueue_Heap<T, Compare>::
allocate (size_t s_)
{
	m_size = s_ > m_lwm ? s_ : m_lwm;
	m_queue = new T [m_size];
}

template< class T, class Compare>
inline 
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (const PriorityQueue_Heap& h_)
	: m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
	  m_lwm (h_.m_lwm)
{
	allocate (m_size);
	::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
}

template< class T, class Compare>
PriorityQueue_Heap<T, Compare>&
PriorityQueue_Heap<T, Compare>::
operator= (const PriorityQueue_Heap& h_)
{
	delete [] m_queue;
	m_comp = h_.m_comp;
	m_size = h_.m_size;
	m_curr = h_.m_curr;
	m_lwm  = h_.m_lwm;
	allocate (m_size);
	::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
	return *this;
}

template< class T, class Compare>
inline 
PriorityQueue_Heap<T, Compare>::
~PriorityQueue_Heap ()
{
	delete [] m_queue;
}

template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
insert (const T& t_)
{
	if (m_curr+1 == m_size)	 // if array filled up 
		resize (m_size*2); // then resize array

	m_queue [m_curr] = t_;
	upheap (m_curr);
	m_curr++;
}

template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
upheap (size_t k_)
{
	T v = m_queue[k_];
	m_queue[0] = 0;

	while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
		m_queue[k_] = m_queue[k_/2];
		k_ = k_/2;
	}
	m_queue[k_] = v;
}

template< class T, class Compare>
T
PriorityQueue_Heap<T, Compare>::
pop ()
{
	T v = m_queue[1];
	m_queue[1] = m_queue[--m_curr];
	
	downheap (1);
	if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
		resize (m_curr*2);
	}
	return v;
}

template< class T, class Compare>
inline const T&
PriorityQueue_Heap<T, Compare>::
top () const
{
	return (const T&) m_queue[1];
}

template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
downheap (size_t k_)
{
	register size_t j;
	T v = m_queue[k_];

	while (k_ <= m_curr/2) {
		j = 2*k_;
		if (j < m_curr && m_comp (m_queue[j+1], m_queue[j])) 
			j++;
		if (m_comp (v, m_queue[j])) 
			break;
		m_queue[k_] = m_queue[j];
		k_ = j;
	}
	m_queue[k_] = v;
}

template< class T, class Compare>
bool
PriorityQueue_Heap<T, Compare>::
remove (T t_)
{
	register size_t i;

	for (i=1; i < m_curr; i++) 
		if (m_queue[i] == t_)
			break;

	if (i == m_curr)	// not found
		return false;

	m_curr--;
	if (i == m_curr)	// last element in queue
		return true;

	m_queue[i] = m_queue[m_curr];
	downheap (i);

	return true;
}

template< class T, class Compare>
inline size_t
PriorityQueue_Heap<T, Compare>::
size ()
{
	return m_curr-1;
}

template< class T, class Compare>
bool
PriorityQueue_Heap<T, Compare>::
resize (size_t newsz_)
{
	if (m_size == newsz_)
		return true;

	T* new_chunk = new T[newsz_];
 	::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
	delete [] m_queue;
	m_queue = new_chunk;
	m_size = newsz_;
	return true;
}

template< class T, class Compare>
T&
PriorityQueue_Heap<T, Compare>::
operator[] (int idx)
{
	return m_queue[idx+1];
}

} // end namespace ASSA

#endif /* PRIORITY_QUEUE_HEAP_H */