//
// Basic Summary: partial order tree
//
// Include file for pot definition
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description: partial order tree based on a balanced binary tree layered
// ontop of a dynamic array. 
//
//
// Data elemnents:
// root - the dynamic array, location 0 is the root, 
// if location n is a parent then 2n is the left child, 2n+1 the right child
// last - the last used location
//
// Methods:
//
// The methods are
//	pot(); - standard constructor
//	~pot(); - standard disctructor
//  void bubble_up(natural n); add element to end, and re-order tree
// 	void bubble_down(natural n); remove element at top, and re-order tree
//	Boolean compare(pair * p1, pair * p2 ); is key1 < key2 for minimum tree
//											is key1 > key2 for maximum tree
// 	void set(pair * p); add element to the tree, automatic re-order
//	pair * get(); get am element from the tree, automatic re-order
//	static Boolean test(); = quality assurance test
//
// Macro definitions:
// given N, calculate the left child = 2N
// given N, calculate the right child = 2N+1
// given child N, calculate the parent (N-1)/2
// 
// 

#ifndef _OP_POT
#define _OP_POT

#include <oops.h>
#include "standard.h"
#include "pair.h"
#include "circular_buffer.h"
#include "linked_chunk.h"
#include "dynamic_array.h"
#include "pool.h"

#define LEFT_CHILD(n) (2*n+1)
#define RIGHT_CHILD(n) (2*n+2)
#define PARENT(n) ((n-1)/2)

// Class definition:
// 
// pot
//
class pot {
	private:
		dynamic_array * root ;
		natural last ;
		void bubble_up(natural n);
		void bubble_down(natural n);

	public:

		static char * version ;
		static pool ThePool ;
		pot();
		~pot();
		void set(pair * p);
		pair * get();

		virtual Boolean compare(pair * p1, pair * p2 );

		static Boolean test();

		void * operator new(size_t) { return ThePool.alloc(); };
		void operator delete(void * p) { ThePool.free(p); };
};

#endif