//
// Basic Summary:
//
// Include file for dynamic array definition
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description:
//
// dynamic array, no upper bounds in size
// grows and shrinks automaticly
// 
// Include files:
//
#include <oops.h>
#include <stdio.h>
#include "standard.h"
#include "circular_buffer.h"
#include "linked_chunk.h"
#include "dynamic_array.h"

pool dynamic_array::ThePool (sizeof(dynamic_array)) ;

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

char * dynamic_array::version = "Objects Plus Dynamic Array Version 1.0" ;

//
// function: 	dynamic_array
// parameters: 	none 
// goal:		basic constructor
// returns:		new element 
//		
dynamic_array::dynamic_array(){
	TheHead = new linked_chunk() ;
	TheCursor = nil ;
	Modifications = 0 ;
}

//
// function: 	~dynamic_array
// parameters: 	none 
// goal:		basic destructor
// returns:		element to the heap
//		
dynamic_array::~dynamic_array(){
	delete TheHead ;
	TheHead = nil ;
	delete TheCursor ;
	TheCursor = nil ;
	Modifications = 0 ;
}

//
// function: 	gut
// parameters: 	a new dyanmic array 
// goal:		gut the current internals of this class and replace with new ones
// returns:		the same object but with new internals
//
void dynamic_array::gut(dynamic_array * d) {
	Modifications = 0 ;
	delete TheCursor ;
	delete TheHead ;
	
	Modifications = d->Modifications ;
	TheCursor = d->TheCursor ;
	TheHead = d->TheHead ;
	
	d->TheCursor = nil ;
	d->TheHead = nil ;
}

// function: 	optimize
// parameters: 	the location n 
// goal:		find the chunk in the linked list that materilizes
//				this location. 
// returns:		a cursor to the chunk and the base offset that starts the chunk 
//		
void dynamic_array::optimize (natural n) {
	
	// no cursor, just set one
	if (TheCursor==nil) {
		TheCursor = TheHead->point(0,n);
		return;
	}
	
	// the cursor points past the element, reset the cursor
	if(TheCursor->offset > n) {
		delete TheCursor ;
		TheCursor = TheHead->point(0,n);
		return ;
	}
	
	// find a new cursor (may even be the same) down stream
	cursor * temp;
	temp = TheCursor->base->point(TheCursor->offset,n-TheCursor->offset);
	delete TheCursor ;
	TheCursor = temp;
	return;
}
	

//
// function: 	peak
// parameters: 	the nth location 
// goal:		get the nth element, but do not remove from the list
// returns:		the nth element 
// note:		this algorith is fail soft
//		
void * dynamic_array::peak(natural n) {
	if (n >= length() ) { return nil ; } ;
	optimize(n);
	return TheCursor->base->peak(n - TheCursor->offset);
}

//
// function: 	shrink
// parameters: 	none 
// goal:		remove empty chunks
// returns:		a compact array with no empty chunks
//				a partial filled chunk is not removed or altered
//				we always leave at least one chunk
//				only do this ever so often, so the dynamic array is only
//				partially compact at any one time 
// note:		this algorith is fail soft
//		
void dynamic_array::shrink () {
	Modifications++ ;
	if (Modifications > THRESHOLD) {		
		if (TheHead->next) TheHead->next = TheHead->next->shrink() ; 
		Modifications = 0;
		delete TheCursor ;
		TheCursor = TheHead->point(0,0) ;
	}
}
		

//
// function: 	get
// parameters: 	the nth location 
// goal:		get and remove the element at the nth location
// returns:		the algorithm 
// note:		this algorith is fail soft
//		
void * dynamic_array::get(natural n) {
	shrink();
	optimize(n);
	return TheCursor->base->get(n- TheCursor->offset);
}


//
// function: 	set
// parameters: 	the nth location, the element 
// goal:		store at the nth location the new element
//				move things around to make room
// returns:		a list that is 1 element larger 
// note:		this algorith is fail soft
//		
void dynamic_array::set(natural n, void * element) {
	shrink();
	optimize(n);
	TheCursor->base->set(n - TheCursor->offset,element);
}

//
// function: 	replace
// parameters: 	the nth location, the new element 
// goal:		replace the old element with the new element
// returns:		updated list 
// note:		the old element is lost, it is up to the user to keep track
//		
void dynamic_array::replace(natural n, void * element) {
	optimize(n);
	TheCursor->base->replace(n - TheCursor->offset,element);
}


//
// function: 	length
// parameters: 	none 
// goal:		calculate the current length
// returns:		natural number 
//		
natural dynamic_array::length ()  { return TheHead->length() ; }

//
// function: 	empty
// parameters: 	none 
// goal:		is the list empty?
// returns:		true or false 
// note:		this algorith is fail soft
//		
Boolean dynamic_array::empty() {return TheHead->empty() ;}

//
// function: 	full
// parameters: 	none 
// goal:		is the list full? this is always false
// returns:		true or false 
// note:		this algorith is fail soft
//		
Boolean dynamic_array::full() {return false;}

//
// function: 	test
// parameters: 	none 
// goal:		qa test
// returns:		true or false 
// note:		this algorith self test the dyanmic array and should
//				have no memory leaks
//		
Boolean dynamic_array::test(){
	Boolean results ;
	natural i;
	dynamic_array * cp ;
	void* a[7*CHUNK_SIZE] ;
	natural length;
	Boolean empty ;
	Boolean full ;
	natural temp;
	
	results = true ;
	
	// test the two support classes first
	results &= circular_buffer::test();
	results &= linked_chunk::test() ;
	
	// simple create/delete test
	cp = new dynamic_array();
	length = cp->length();
	results &= (length==0) ;
	delete cp ;
	
	// set the array to be all nil and verify that this is so
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {cp->set(i,nil) ;}
	for(i=0;i<7*CHUNK_SIZE;i++) {results = results && (nil == cp->peak(i)) ;}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	delete cp ;
	
	// set the array to be the integers from 0 ... N and verify
	// then replace with twice its value and verify
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
		a[i] = cp->peak(i) ;
	}
	for(i=0;i<7*CHUNK_SIZE;i++) {
		results = results && (a[i] == cp->peak(i)) ;
	}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->replace(i,(void *)(2*i)) ;
	}
	for(i=0;i<7*CHUNK_SIZE;i++) {
		temp = (natural)cp->peak(i) ;
		results = results && ((2*i) == temp) ;
	}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;

	
	delete cp ;

	// set the array to be all nil and verify
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {cp->set(i,nil) ;}
	for(i=0;i<7*CHUNK_SIZE;i++) {results = results && (nil == cp->peak(i)) ;}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == false) ;
	delete cp ;
	
	// set the array to be from 0 ... N and verify
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
		a[i] = cp->peak(i) ;
	}
	for(i=0;i<7*CHUNK_SIZE;i++) {
		results = results && (a[i] == cp->peak(i)) ;
	}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == false) ;
	delete cp ;
	
	// do a series of pushes followed by a series of pops
	void * e ;
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(0,(void *)i) ;
		length = cp->length();
		results &= (length==1) ;
		empty = cp->empty();
		full = cp->full();
		results &= (empty == false) ;
		results &= (full == false) ;
		e = cp->get(0);
		results &= e == (void *)i ;
		length = cp->length();
		results &= (length==0) ;
		empty = cp->empty();
		full = cp->full();
		results &= (empty == true) ;
		results &= (full == false) ;
	}
	delete cp ;
	
	// do a series of enqueues to get the list N, ..., 0
	// do a series of dequeues and verify
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(0,(void *)i) ;
	}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == false) ;
	for(i=0;i<7*CHUNK_SIZE;i++) {
		e = cp->get(cp->length()-1);
		results &= e == (void *)i ;
	}
	length = cp->length();
	results &= (length==0) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == true) ;
	results &= (full == false) ;
	delete cp ;
	
	// set the array to be 0, ..., N
	// get and set the array to build 0, 2, ..., 2N
	// and verify
	cp = new dynamic_array();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
	}
	for(i=0;i<(7*CHUNK_SIZE);i++) {
		e = cp->peak(i) ;
		results &= (e == (void *)i) ;
		e = cp->get(i) ;
		results &= (e == (void *)i) ;
		cp->set(i,(void *)(2*i)) ;
	}
	for(i=0;i<(7*CHUNK_SIZE);i++) {
		e = cp->peak(i) ;
		results &= (e == (void *)(2*i)) ;
	}
	length = cp->length();
	results &= (length==7*CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == false) ;
	delete cp ;
	
	return results ;
}