#ifdef __WDONG_ARRAY__
#ifndef __WDONG_HEAP__
#define __WDONG_HEAP__

/* works directly on an array.  Need array.h included */

#define HEAP_EMPTY(heap)	((heap).len == 0)
#define HEAP_HEAD(heap)		(heap).data[0]

#define HEAP_ENQUEUE(heap, d, ge)			\
	do {					\
		int _i_ = (heap).len, _j_;	\
		(heap).len++;			\
		ARRAY_EXPAND(heap,(heap).len);\
		while (_i_ > 0) {		\
			_j_ = _i_ >> 1;		\
			if (ge(&d, &(heap).data[_j_])) break; \
			(heap).data[_i_] = (heap).data[_j_]; \
			_i_ = _j_;		\
		}				\
		(heap).data[_i_] = d;		\
	} while(0)

#define HEAP_ENQUEUE_UPDATE(heap, d, ge, update)\
	do {					\
		int _i_ = (heap).len, _j_;	\
		(heap).len++;			\
		ARRAY_EXPAND(heap,(heap).len);\
		while (_i_ > 0) {		\
			_j_ = _i_ >> 1;		\
			if (ge(&d, &(heap).data[_j_])) break; \
			(heap).data[_i_] = (heap).data[_j_]; \
			update(&(heap).data[_i_], _i_); \
			_i_ = _j_;		\
		}				\
		(heap).data[_i_] = d;		\
		update(&(heap).data[_i_], _i_);	\
	} while(0)

#define HEAP_DEQUEUE(heap, ge)			\
	do {					\
		int _i_, _l_, _r_,  _e_;	\
		assert((heap).len > 0);		\
		(heap).len--;			\
		_e_ = (heap).len;		\
		_i_ = 0;			\
		for (;;) {			\
			_l_ = (_i_ << 1) + 1;	\
			if (_l_ >= _e_) break;	\
			_r_ = _l_ + 1;		\
			if ((_r_ < _e_) && (ge(&(heap).data[_l_], &(heap).data[_r_]))) _l_  = _r_; \
			if (ge(&(heap).data[_l_], &(heap).data[_e_])) break; \
			(heap).data[_i_] = (heap).data[_l_]; \
			_i_ = _l_;		\
		}				\
		(heap).data[_i_] = (heap).data[_e_]; \
	} while (0)

#define HEAP_DEQUEUE_UPDATE(heap, ge, update)	\
	do {					\
		int _i_, _l_, _r_,  _e_;	\
		assert((heap).len > 0);		\
		(heap).len--;			\
		_e_ = (heap).len;		\
		_i_ = 0;			\
		update(&(heap).data[0], -1);	\
		for (;;) {			\
			_l_ = (_i_ << 1) + 1;	\
			if (_l_ >= _e_) break;	\
			_r_ = _l_ + 1;		\
			if ((_r_ < _e_) && (ge(&(heap).data[_l_], &(heap).data[_r_]))) _l_  = _r_; \
			if (ge(&(heap).data[_l_], &(heap).data[_e_])) break; \
			(heap).data[_i_] = (heap).data[_l_]; \
			update(&(heap).data[_i_], _i_);	\
			_i_ = _l_;		\
		}				\
		(heap).data[_i_] = (heap).data[_e_]; \
		update(&(heap).data[_i_], _i_);	\
	} while (0)

#endif
#endif