//
// Basic Summary:
//
// implementation file for linked_chunk definition
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description:
// 
// This is a simple linked list implementation of fixed chunks
// the array is logically from 0 to n,  split into fixed chunks
// The fixed chunks are of a fixed storage allocation but may
// very in the number of used locations. There is a daughter class
// that acts like a cursor to the linked list. It contains the information
// as to where each location is materilized. 
//
//
// 
// Include files:
//
#include <oops.h>
#include "standard.h"
#include "circular_buffer.h"
#include "linked_chunk.h"

pool linked_chunk::ThePool (sizeof(linked_chunk)) ;
pool cursor::ThePool (sizeof(cursor)) ;

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

char * linked_chunk::version = "Objects Plus Linked Chunk Version 1.0" ;
char * cursor::version = "Objects Plus Cursor Version 1.0" ;

//
// function: 	linked_chunk
// parameters: 	none 
// goal:		basic constructor
// returns:		new element 
//		
linked_chunk::linked_chunk() {
	next = nil ;
	storage = new circular_buffer() ;
}

//
// function: 	~linked_chunk
// parameters: 	none 
// goal:		basic destructor
// returns:		element to the heap
//		
linked_chunk::~linked_chunk() {
	next = nil ;
	delete storage ;
}

//
// function: 	bounds
// parameters: 	nth location 
// goal:		is this location in the bounds of the variable array?
// returns:		true or false 
//		
Boolean linked_chunk::bounds(natural n) { return ((0<=n)&&(n<length())) ; } ;

//
// function: 	location
// parameters: 	location n 
// goal:		find the fixed chunk that contains this location
// returns:		the fixed chunk 
// note:		this algorith is fail soft
//		
linked_chunk * linked_chunk::location(natural n) {
	natural l = storage->length() ;
	if (n >= l) {return (next) ? next->location(n - l) : nil ;};
	return this;
}

//
// function: 	length
// parameters: 	none 
// goal:		calculate the current length
// returns:		the length 
//		
natural linked_chunk::length() { return storage->length() + ( next ? next->length() : 0 ) ; } ;

//
// function: 	full
// parameters: 	none 
// goal:		is the array full? this cann't happen
// returns:		true / false 
//		
Boolean linked_chunk::full() { return false; } ;

//
// function: 	empth
// parameters: 	none 
// goal:		is the array empty?
// returns:		true/false
//		
Boolean linked_chunk::empty() { return storage->empty() && ( next ? next->empty() : true ) ; } ;

//
// function: 	peak
// parameters: 	location n 
// goal:		get a look at the nth element with out changing the arry
// returns:		the nth element
// note:		this algorithm is fail soft 
//		
void * linked_chunk::peak(natural n) {
	natural l = storage->length() ;
	if (n >= l) {return (next) ? next->peak(n - l) : nil ;};
	return storage->peak(n) ;
}

//
// function: 	get
// parameters: 	location n 
// goal:		get a look at the nth element and change the arry
// returns:		the nth element
// note:		this algorithm is fail soft and distructive 
//		
void * linked_chunk::get(natural n) {
	natural l = storage->length() ;
	if ( n >= l ) { return next ? next->get(n-l) : nil ; }
	return storage->get(n) ;
}

//
// function: 	expand
// parameters: 	location n 
// goal:		make room for one more element
// returns:		an expanded array
//		
void linked_chunk::expand(natural n) {

	// get a new fixed chunk of storage and add to the end of this chunk
	linked_chunk * c = new linked_chunk () ;
	c->next = next ;
	next = c ;
	
	// special case, if the next insert is at the begining
	// swap storage buffers, this saves a copy
	if (n == 0) {
		circular_buffer * f = c->storage;
		c->storage = storage ;
		storage = f ; 
		return ;
	}
	
	// otherwise, move half of the storage to the new chunk, leaving
	// room in each chunk
	natural l = storage->length() ;
	natural limit = (l+1)/2 ;
	for(natural i=0 ; i<= limit ; i++ ) {
		c->storage->set(i,storage->get(limit));
	}
	
}

//
// function: 	set
// parameters: 	location n, element e
// goal:		set the element, making room
// returns:		the new array
// note:		this algorithm is fail soft 
//		
void linked_chunk::set(natural n,void * e) {

	// does it belong here and there is room?
	natural l = storage->length() ;
	if ((! storage->full()) && (0 <= n) && ( n <= l )) {
		storage->set(n,e);
		return;
	}
	
	// does it belong in the next chunk?
	if ((n >= l)&&(next)) { 
		next->set(n-l,e) ;
		return ; 
	}
	
	// does it belong at the end of the array? if so, make room and store
	if ((n == l)&&(!next)) { 
		next = new linked_chunk()  ;
		next->set(n-l,e) ;
		return ; 
	}
	
	// fail soft, out of bounds store, just ignore
	if ((n > l)&&(!next)) { 
		return ; 
	}
	
	// make room and store
	expand(n);
	set(n,e);
	
}

//
// function: 	replace
// parameters: 	location n , element e
// goal:		replace the current nth element with a new one
// returns:		updated array
// note:		this algorithm is fail soft 
//		
void linked_chunk::replace(natural n,void * e) {

	// is this the chunk or is it the next one?
	natural l = storage->length() ;
	if ((0 <= n) && ( n < l )) {
		storage->replace(n,e);
		return;
	}
	
	// this is the chunk, replace this one element
	if ((n >= l)&&(next)) { 
		next->replace(n-l,e) ;
		return ; 
	}
	
}


//
// function: 	shrink
// parameters: 	none 
// goal:		remove empty chunks
// returns:		modified array
// note:		this algorithm is fail soft 
//		
linked_chunk * linked_chunk::shrink(){
	if (empty()) {
		linked_chunk * n = next ;
		delete this ;
		return (n ? n->shrink() : nil) ;
	}
	if (next) next = next->shrink() ;
	return this;
}

//
// function: 	offset
// parameters: 	one of the chunks in the chain 
// goal:		count the number of elements in use upto the given element
// returns:		the count or offset
// note:		this algorithm is fail soft 
//		
natural linked_chunk::offset(linked_chunk * c) {
	if (this==c) return 0;
	return storage->length() + ( next ? next->offset(c) : 0 ) ;
}
		
//
// function: 	test
// parameters: 	none 
// goal:		test the class
// returns:		true/false
// note:		there should be no memory leaks 
//		
Boolean linked_chunk::test(){
	Boolean results ;
	natural i;
	linked_chunk * cp ;
	void* a[7*CHUNK_SIZE] ;
	natural length;
	Boolean empty ;
	Boolean full ;
	
	results = true ;
	
	// simple create and delete test
	cp = new linked_chunk();
	length = cp->length();
	results &= (length==0) ;
	delete cp ;
	
	// store all nils and check to see if they all come back nil
	// test set,peak,length,offset
	cp = new linked_chunk();
	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) ;
	natural base = cp->offset(cp) ;
	results &= (base==0) ;
	base = cp->offset(cp->next) ;
	results &= (base==cp->storage->length()) ;
	base = cp->offset(nil) ;
	results &= (base==cp->length()) ;
	
	delete cp ;
	
	// store more unique data in each cell and check
	cp = new linked_chunk();
	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) ;
	delete cp ;

	// store nils and check, test empty, full, length
	cp = new linked_chunk();
	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 ;
	
	// store interesting unique data in each cell
	// use a standard array to verify the content
	cp = new linked_chunk();
	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 ;
	
	// set and get at location 0, verify results
	void * e ;
	cp = new linked_chunk();
	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 ;
	
	// store a series of number at location 0
	// this will create the list n,n-1,...,0
	// verify that this is so
	cp = new linked_chunk();
	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) ;
	cp = cp->shrink();
	results &= (cp == nil);
	delete cp ;
	
	// set the list with unique numbers and verify
	// now remove each number, change it, and resore, and then verify
	cp = new linked_chunk();
	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 ;
	
	// calculate the chunk in the list that materilizes the location
	cp = new linked_chunk();
	for(i=0;i<7*CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
	}
	cursor * c ;
	linked_chunk * temp ;
	natural j ;
	for(i=0;i<7*CHUNK_SIZE;i++) {
		c = cp->point(0,i) ;
		results &= (c->offset == (CHUNK_SIZE)*(i / (CHUNK_SIZE))) ;
		temp = cp ;
		j = i ;
		while (j> CHUNK_SIZE-1) {
			temp = temp->next ;
			j -= CHUNK_SIZE ;
		}
		results &= (c->base == temp);
		delete c ;
	}
	delete cp ;

	// done
	return results ;
}

//
// function: 	point
// parameters: 	a location and a offset
// goal:		find the chunk that has this location and its base
// returns:		the chunk and the base location of the chunk 
// note:		this algorith is fail soft
//		
cursor * linked_chunk::point(natural offset, natural n){
	natural l = storage->length() ;
	if ((n >= l)&&(next)) return next->point(offset+l, n - l) ;
	cursor * c = new cursor() ;
	c->offset = offset ;
	c->base = this ;
	return c;
};

//
// function: 	cursor
// parameters: 	none 
// goal:		basic constructor
// returns:		new element 
//		
cursor::cursor(){
	offset = 0 ;
	base = nil ;
};

//
// function: 	~cursor
// parameters: 	none 
// goal:		basic destructor
// returns:		element to the heap
//		
cursor::~cursor(){
	offset = 0 ;
	base = nil ;
};