/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Based on the original sources
 *   Faery Tale II -- The Halls of the Dead
 *   (c) 1993-1996 The Wyrmkeep Entertainment Co.
 */

#ifndef SAGA2_PRIQUEUE_H
#define SAGA2_PRIQUEUE_H

namespace Saga2 {

template <class ITEM, int size>
class PriorityQueue {
	int16           _tail;                   // end index of queue
	ITEM            _queue[size + 1];

	static int16 parentIndex(int16 index) {
		return index >> 1;
	}
	static int16 child1Index(int16 index) {
		return index << 1;
	}
	static int16 child2Index(int16 index) {
		return (index >> 1) + 1;
	}

public:
	PriorityQueue() {                    // constructor
		_tail = 1;
	}

	bool insert(ITEM &newItem);              // insert an item
	bool remove(ITEM &result);           // remove an item
	void clear() {
		_tail = 1;    // clear the queue
	}
	int16 getCount() {
		return _tail - 1;
	}
};

//  Function to insert an element into the queue

template <class ITEM, int size>
bool PriorityQueue<ITEM, size>::insert(ITEM &newItem) {
	int16           index,
	                parentIndex,
	                newVal = (int)newItem;
	ITEM            *qi,
	                *parentItem;

	if (_tail >= size + 1) return false;

	for (index = _tail, qi = &_queue[index];
	        index > 1;
	        index = parentIndex, qi = parentItem) {
		parentIndex = PriorityQueue::parentIndex(index);
		parentItem = &_queue[parentIndex];

		if ((int)*parentItem <= newVal) break;
		*qi = *parentItem;
	}
	*qi = newItem;
	_tail++;

	return true;
}

//  Function to remove the lowest element from the queue

template <class ITEM, int size>
bool PriorityQueue<ITEM, size>::remove(ITEM &result) {
	ITEM            *item = &_queue[1],
	                 *child;
	int16           itemNum = 1,
	                childNum,
	                tailVal;

	if (_tail <= 1) return false;

	result = *item;
	_tail--;
	tailVal = (int)_queue[_tail];

	for (;;) {
		childNum = child1Index(itemNum);
		if (childNum >= _tail) break;

		child = &_queue[childNum];

		//  Select the lowest of the two children
		if (childNum + 1 < _tail
		        && (int)child[0] > (int)child[1]) {
			childNum++;
			child++;
		}

		if ((int)*child >= tailVal) break;
		*item = *child;
		item = child;
		itemNum = childNum;
	}

	if (itemNum != _tail) {
		*item = _queue[_tail];
	}
	return true;
}

} // end of namepsace Saga2

#endif