// Esempio 3: Heap

template<class T> class Heap {
	private:
		// Node
		// un nodo dell'heap
		class Node {
			private:
				unsigned int key;
				T *data;
			public:
				// metodi
				const T *get_data() { return data; };
				void set_data(const T &ndata) {
					if(data) // questo nodo ha gia' un elemento!
						delete data;

					data = new T(ndata); // costruisce una copia privata per questo Nodo utilizzando il costruttore di copia
				}
				unsigned int get_key() { return key; };
				void set_key(unsigned int nkey) { key = nkey; };
				void free_data() {
					if(data) {
						delete data;
						data = NULL;
					}
				}
				
				// operatori
				bool operator>(const Node &a) {
					return key > a.key;
				}
				bool operator>=(const Node &a) {
					return key >= a.key;
				}
				bool operator<(const Node &a) {
					return key < a.key;
				}
				bool operator<=(const Node &a) {
					return key <= a.key;
				}
				const Node &operator=(const Node &copy) {
					if(&copy == this)
						return *this;

					free_data();

					key = copy.key;

					if(copy.data)
						data = new T(*(copy.data));
					else
						data = NULL;
				}

				// costruttori
				Node()
				: data(NULL), key(0) { };

				Node(const Node &copy)
				: key(copy.key) {
					if(copy.data)
						data = new T(*(copy.data));
					else
						data = NULL;
				}

				Node(const T &ndata, unsigned int nkey)
				: key(nkey) { 
					data = new T(ndata); // costruisce una copia privata per questo Nodo utilizzando il costruttore di copia
				};

				// distruttore
				~Node() { 
					free_data();
				};
		};

		Node *nodes; // puntatore all'array di nodi
		unsigned int array_size; // numero di elementi dell'array nodes
		unsigned int heap_size; // numero di elementi attualmente nell'heap

		// metodi privati
		Node &at(unsigned int n) {
			return nodes[n - 1];
		}

		// relazioni fra i nodi
		unsigned int parent(unsigned int n) {
			return (unsigned int)floor((float)n / 2);
		}
		unsigned int left(unsigned int n) {
			return 2 * n;
		}
		unsigned int right(unsigned int n) {
			return 2 * n + 1;
		}
		
		// scambia due nodi
		void exchange(Node &a, Node &b) {
			Node c(a);

			a = b;
			b = c;
		}

		// ripristina l'heap dal nodo n in basso
		void heapify(unsigned int n) {
			unsigned int largest;

			if ((left(n) < heap_size) && (at(left(n)) > at(n)))
				largest = left(n);
			else
				largest = n;

			if ((right(n) < heap_size) && (at(right(n)) > at(largest)))
				largest = right(n);

			if (largest != n) {
				// il nodo non rispetta le proprieta' dell'heap, scambia largest e n
				exchange(at(n), at(largest));

				// ricorsivamente controlla il figlio scambiato
				heapify(largest);
			}
		}

	public:
		// Costanti statiche
		static const int heap_overflow;
		static const int heap_underflow;
				  
		// Metodi
		void push(const T &element, unsigned int priority) {
			if(heap_size < array_size) {
				int i = heap_size;

				// incrementa heap_size
				heap_size++;
				
				// inserisce il nuovo elemento nella corretta posizione
				while((i > 1) && (at(parent(i)).get_key() < priority)) {
					at(i) = at(parent(i));
					i = parent(i);
				}

				// imposta i dati del nuovo elemento
				at(i).set_key(priority);
				at(i).set_data(element);
			} else
				throw(heap_overflow);
		};

		const T pop() {
			if(heap_size - 1) {
				// istanzia l'oggeto da ritornare
				T returned(*(at(1).get_data()));

				// libera i dati alla radice
				at(1).free_data();

				// decrementa la dimensione dell'heap
				heap_size--;

				// scambia la radice con l'ultimo elemento dell'heap
				exchange(at(1), at(heap_size));

				// esegue heapify sulla nuova radice
				heapify(1);

				return returned;
			} else
				throw(heap_underflow);
		};

		// costruttori
		Heap(unsigned int nsize) 
		: heap_size(1) {
			nodes = new Node[nsize + 1]; // inizializza l'array nodes
			array_size = nsize + 1; // imposta il numero di elementi dell'array nodes
			heap_size = 1; // imposta a zero il numero di elementi attualmente nell'heap
		}

		// distruttore
		~Heap() {
			delete nodes;
		}
};

// Inizializzazione dei membri statici di Heap
template<class T>const int Heap<T>::heap_overflow = 0x0;
template<class T>const int Heap<T>::heap_underflow = 0x1;