//
// Basic Summary: partial order tree
//
// Implementation file for pot definition
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description:
// This is a partial order tree based on a dynamic array
// the tree is a binary tree. if a root is at location n, then
// the left child is at 2n and the right child is at 2n+1
// both the left and right child are < the parent
// here < is really the function compare
// The root is always the smallest(largest) element
// you remove the the root, replace the root with the last element
// and re-order the tree, You add a new element as the last node
// and re-order the tree.
//
// Include files:
//
#include "pot.h"

//
// there is one pool for this class
//

pool pot::ThePool (sizeof(pot)) ;

// 
// define the version of this structure
//

char * pot::version = "Objects Plus Partial Order Tree Version 1.0" ;

//
// function: 	compare
// parameters: 	two elements represented as (key,data) pairs 
// goal:		is one < the other ?
// returns:		true/false 
// note:		based on the key being an integer
//		
Boolean pot::compare(pair * p1, pair * p2) {
	if ((p1==nil)||(p2==nil)) return false ;
	
	int k1 = *(int*)(p1->key) ;
	int k2 = *(int*)(p2->key) ;
	return k1 > k2 ; 
	
}

	
//
// function: 	bubble up
// parameters: 	location n 
// goal:		re-order the tree
// returns:		partial order tree 
// note:		we have just placed an element at location n
//				we need to check if element is in the correct location
//				based on the parent
//		
void pot::bubble_up(natural n){
	if (n==0) return ;
	
	pair * parent = (pair*)root->peak(PARENT(n)) ;
	pair * child = (pair*)root->peak(n);
	if ( compare(child,parent) ) {
		root->replace(n,parent);
		root->replace(PARENT(n),child);
		bubble_up(PARENT(n));
	};
}

//
// function: 	bubble down
// parameters: 	location n 
// goal:		re-order a tree
// returns:		pot 
// note:		we have just placed an element at location n 
//				and need to check if the tree is still in order
//		
void pot::bubble_down(natural n){
	pair * left_child ;
	pair * right_child ;
	pair * parent ;
	
	// no more nodes
	if (n==last) return ;
		
	// no children for this node
	if((LEFT_CHILD(n) >= last) && (RIGHT_CHILD(n) >= last)) return ;
	
	//get parent and left child
	parent = (pair*)root->peak(n);
	left_child = (pair*)root->peak(LEFT_CHILD(n)) ;
	
	// special case, no right child so check only left child
	if (RIGHT_CHILD(n) >= last) {
		if (compare(left_child,parent)) {
			root->replace(n,left_child);
			root->replace(LEFT_CHILD(n),parent);
		}
		return;
	};
	
	// both left and right child
	right_child = (pair*)root->peak(RIGHT_CHILD(n)) ;
	
	
	// check to see if tree is already in order
	if ( compare(parent,left_child) && compare(parent,right_child)) return ;
	
	// tree out of order, pick the correct child, and reorder
	if ( compare(left_child,right_child) ){
		root->replace(n,left_child);
		root->replace(LEFT_CHILD(n),parent);
		bubble_down(LEFT_CHILD(n));
	} else {
		root->replace(n,right_child);
		root->replace(RIGHT_CHILD(n),parent);
		bubble_down(RIGHT_CHILD(n));
	};
}

//
// function: 	pot
// parameters: 	none 
// goal:		basic constructor
// returns:		new element 
//		
pot::pot(){
	root = new dynamic_array() ;
	last = 0 ;
}

//
// function: 	~pot
// parameters: 	none 
// goal:		basic destructor
// returns:		element to the heap
//		
pot::~pot(){
	delete root ;
	last = 0 ;
}

//
// function: 	set
// parameters: 	a new (key,data) pair 
// goal:		add a new element to the tree and re-order
// returns:		new pot 
//		
void pot::set(pair * p){
	root->set(last,p);
	bubble_up(last);
	last++;
}

//
// function: 	get
// parameters: 	none 
// goal:		get the smallest(largest) element and re-order
// returns:		modified pot
// note:		this algorithm is fail soft
//		
pair * pot::get(){
	if (last==0) return nil ;
	
	pair * temp = (pair*)root->peak(0) ;
	last--;
	root->replace(0,root->get(last)) ;
	bubble_down(0) ;
	return temp;
}

//
// function: 	QA test
// parameters: 	none 
// goal:		self test of pot, should return true, with no memory creap
// returns:		true/false
//		
Boolean pot::test() {
	Boolean results = true ;
	pot * p ;
	pair * ThePair ;
	int * TheInt ;
	natural limit = 200 ;
	natural l ;
	
	// store a bunch of unique pairs
	p = new pot();
	for(int i=0;i<=limit;i++){
		ThePair = new pair();
		TheInt =  new ;
		*TheInt = i ;
		ThePair->key = (void*)TheInt ;
		p->set(ThePair);
	}

	// look at the tree as an array
	l = p->root->length();
	for(i=0;i<l;i++){
		ThePair = (pair *)p->root->peak(i);
		TheInt = (int*)ThePair->key ;
	}
	
	// verify that the elements come out in the correct order
	for(i=limit;i>=0;i--) {
		ThePair = p->get();
		TheInt = (int*)ThePair->key ;
		results &= (i == *TheInt ) ;
		delete TheInt ;
		delete ThePair ;
	
	}
	
	// done
	return results ;
}