// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.

#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SPARSE_SYSTEMS_HEAP
#define CA_UWATERLOO_ALUMNI_DWHARDER_SPARSE_SYSTEMS_HEAP

#include <cassert>

class Heap {
	private:
		int capacity;

		int *row;
		int *column;
		double *value;

		int size;

	public:
		Heap( int n ):
		capacity( n + 1 ),
		row( new int[capacity + 1] ),
		column( new int[capacity + 1] ),
		value( new double[capacity + 1] ),
		size( 0 ) {
			// empty constructor
		}

		~Heap() {
			delete [] row;
			delete [] column;
			delete [] value;
		}

		void push( int i, int j, double val ) {
			++size;

			int posn = size;

			while ( posn > 1 ) {
				int parent = posn/2;

				if ( row[parent] > i || (row[parent] == i && column[parent] > j ) ) {
					row[posn] = row[parent];
					column[posn] = column[parent];
					value[posn] = value[parent];

					posn = parent;
				} else {
					break;
				}
			}

			row[posn] = i;
			column[posn] = j;
			value[posn] = val;
		}

		int top_row() const {
			assert( size != 0 );
			return row[1];
		}

		int top_column() const {
			assert( size != 0 );
			return column[1];
		}

		double top_value() const {
			assert( size != 0 );
			return value[1];
		}

		void pop() {
			int i = row[size];
			int j = column[size];
			double val = value[size];

			--size;

			int posn = 1;

			while ( 2*posn < size ) {
				if (
					( i < row[2*posn]     || (i == row[2*posn]     && j < column[2*posn]     ) ) &&
					( i < row[2*posn + 1] || (i == row[2*posn + 1] && j < column[2*posn + 1] ) )
				) {
					row[posn]    = i;
					column[posn] = j;
					value[posn]  = val;

					return;
				}

				if ( row[2*posn] < row[2*posn + 1] || (row[2*posn] == row[2*posn + 1] && column[2*posn] < column[2*posn + 1] ) ) {
					row[posn]    = row[2*posn];
					column[posn] = column[2*posn];
					value[posn]  = value[2*posn];

					posn = 2*posn;
				} else {
					row[posn]    = row[2*posn + 1];
					column[posn] = column[2*posn + 1];
					value[posn]  = value[2*posn + 1];

					posn = 2*posn + 1;
				}
			}

			if ( 2*posn == size && (i > row[2*posn] || (i == row[2*posn] && j > column[2*posn] ) ) ) {
				row[posn] = row[2*posn];
				column[posn] = column[2*posn];
				value[posn] = value[2*posn];

				row[2*posn]    = i;
				column[2*posn] = j;
				value[2*posn]  = val;
			} else {
				row[posn]    = i;
				column[posn] = j;
				value[posn]  = val;

			}
		}
};

#endif