//
// Basic Summary:
//
// implementation file for class circular_buffer
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description:
// 
// A fixed array of elements where the top and bottom chase each other
// as you set and get elements. This is also known as a circular buffer.
// As you add elements to the bottom you increment the bottom location
// in a special way. This increment is done in a circular fashion with
// module arithmetic. Initially the buffer is empty and top=bottom=0
// top is the location to the top element.
// bottom is the location of the next available space.
// we allocate CHUNK_SIZE location. This means that the potential logical locations
// are from 0 to CHUNK_SIZE-1. The physical location of the 0th element
// is at top. There is an error condition that could occur. If we used all
// CHUNK_SIZE locations then size == length. 
// The algorithm is soft fail. This means that if you ask for an element
// that just does not exists, the algorithm will give you the zero or null
// element.
//
// Include files:
// 
// 

#include <oops.h>
#include "standard.h"
#include "circular_buffer.h"

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

pool circular_buffer::ThePool (sizeof(circular_buffer)) ;

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

char * circular_buffer::version = "Objects Plus Circular Buffer Version 1.0" ;


//
// function: 	standard constructor
// parameters: 	none
// goal:		create and initialize the class
// returns:		object of the class
//				
circular_buffer::circular_buffer() {
	for(natural i=0;i<CHUNK_SIZE;i++) {storage[i] = nil ; };
	top = 0 ;
	bottom = 0 ;
	size = 0 ;
}
//
// function: 	standard destructor
// parameters: 	none
// goal:		delete the class
// returns:		memory to the heap
//				
circular_buffer::~circular_buffer() {
	for(natural i=0;i<CHUNK_SIZE;i++) {storage[i] = nil ; };
	top = 0 ;
	bottom = 0 ;
	size = 0 ;
}

//
// function: 	length
// parameters: 	none
// goal:		calculate the current used space
// returns:		a natural number
//				
natural circular_buffer::length() { return size ; } ;

//
// function: 	full
// parameters: 	none
// goal:		are all the locations in use?
// returns:		true or false
//		
Boolean circular_buffer::full() { return length() == CHUNK_SIZE ; } ;

//
// function: 	empty
// parameters: 	none
// goal:		are all the locations available?
// returns:		true or false
//		
Boolean circular_buffer::empty() { return size == 0 ; } ;

//
// function: 	bounds
// parameters: 	the nth location 
// goal:		Is the nth location in this chunk?
// returns:		true or false
//		
Boolean circular_buffer::bounds(natural n) { return ((0 <= n) && (n<length())) ? true : false ; }

//
// function: 	location
// parameters: 	the logical nth location 
// goal:		calculate the physical nth location
// returns:		the physical location 
// note:		the logical chunk ranges from 0 to max
//				the logical 0 is located at physical location top 
//		
natural circular_buffer::location(natural n) { return PLUS(top,n) ; } ;

//
// function: 	peak
// parameters: 	the logical nth location 
// goal:		look at the nth location without changing the structure
// returns:		the element at the nth location 
// note:		If you ask to see an element that is outside of the bounds
//				the algorithm returns nil, this is a fail soft feature
//		
void * circular_buffer::peak(natural n) {
	if (!bounds(n)) return nil ;
	if (empty()) return nil ;
	return storage[location(n)] ;
}

//
// function: 	shrink
// parameters: 	the logical nth location 
// goal:		remove the nth location from the array
// returns:		a chunk, with one less element 
// note:		this is optimized for removals at the top and bottom
//		
void circular_buffer::shrink (natural n) {
	// did we just remove the first element?
	if (n == 0) {top = PLUS(top,1) ; return ;}
	
	// did we just remove the last element?
	if (n == length()-1) { bottom = MINUS(bottom,1) ; return ;}
	
	// the element is some where in the middle, must move things up or down
	// depending on which is the smaller move.
	natural top_half = n;
	natural bottom_half = length() - n - 1;
	if ( top_half < bottom_half ) {
		for(natural i=n;i>0;i--) {
			storage[location(i)] = storage[location(i-1)] ;
		}
		top = PLUS(top,1) ;
	} else {
		for(natural i=n;i<length()-1;i++) {
			storage[location(i)] = storage[location(i+1)] ;
		}
		bottom = MINUS(bottom,1) ;
	}
}

//
// function: 	expand
// parameters: 	make room for the logical nth location 
// goal:		expand the storage by one
// returns:		a chunk, with one more element 
// note:		this is optimized for removals at the top and bottom
//		
void circular_buffer::expand (natural n) {
	// did we just add the location at the top?
	if (n == 0) {top = MINUS(top,1) ; return ;}
	
	// did we just add the element at the end?
	if (n == length()) { bottom = PLUS(bottom,1) ; return ;}
	
	// the element fixs somewhere in the middle, make room by moving up or down
	natural top_half = n + 1 ;
	natural bottom_half = length() - n ;
	if ( top_half < bottom_half ) {
		top = MINUS(top,1) ;
		for(natural i=0;i<n;i++) {
			storage[location(i)] = storage[location(i+1)] ;
		}
	} else {
		for(natural i=length();i>n;i--) {
			storage[location(i)] = storage[location(i-1)] ;
		}
		bottom = PLUS(bottom,1);
	}
}

//
// function: 	get
// parameters: 	the logical nth location 
// goal:		distructive get of the nth element
// returns:		the nth element, and an array with one less member 
// note:		distructive get
//				this algorithm is fail soft
//		
void * circular_buffer::get(natural n) {
	void * e ;
	if (!bounds(n)) return nil ;
	if (empty()) return nil ;
	e = storage[location(n)] ;
	shrink(n);
	size-- ;
	return e;
}


//
// function: 	set
// parameters: 	the logical nth location 
//				the element to store
// goal:		put of the nth element
// returns:		an array with one more member 
// note:		this acts like an inset at nth location. Space is made
//				available and elements are moved.
//				this algorithm is fail soft
//		
void circular_buffer::set(natural n,void * e) {

	if (n > length()) return ;
	if (full()) return ;
	expand(n);
	size++;
	storage[location(n)] = e ;
}

//
// function: 	replace
// parameters: 	the logical nth location 
//				the element to store
// goal:		replace of the nth element
// returns:		an array with exactly the same number of members 
// note:		No new space is allocated, the nth element is now replaced
//				no garbage collection is done of the removed element
//				this algorithm is fail soft
//		
void circular_buffer::replace(natural n,void * e) {

	if (n >= length()) return ;
	storage[location(n)] = e ;
}

//
// function: 	test
// parameters: 	none 
// goal:		quality test for the circular_buffer algorithm
// returns:		true or false 
// note			a series of test each test checking the conditions
//				there should be no memory leaks
//		
Boolean circular_buffer::test(){
	Boolean results ;
	natural i;
	circular_buffer * cp ;
	void* a[CHUNK_SIZE] ;
	natural length;
	Boolean full ;
	Boolean empty ;
	
	results = true ;
	
	// simple create and delete test
	cp = new circular_buffer();
	length = cp->length();
	empty = cp->empty();
	full = cp->full();
	results &= (empty == true) ;
	results &= (full == false) ;
	results &= (length==0) ;
	delete cp ;
	
	// set the elements to be all nil, make sure they remain nil
	// note that this also test the fail soft feature
	cp = new circular_buffer();
	for(i=0;i<CHUNK_SIZE;i++) {cp->set(2*i,nil) ;}
	for(i=0;i<CHUNK_SIZE;i++) {results = results && (nil == cp->peak(i)) ;}
	for(i=0;i<CHUNK_SIZE;i++) {results = results && (nil == cp->get(i)) ;}
	delete cp ;
	
	// set the elements to be all nil and make sure they remain nil
	// make sure that all support functions are correct
	cp = new circular_buffer();
	for(i=0;i<CHUNK_SIZE;i++) {cp->set(i,nil) ;}
	for(i=0;i<CHUNK_SIZE;i++) {results = results && (nil == cp->peak(i)) ;}
	length = cp->length();
	results &= (length==CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == true) ;
	delete cp ;
	
	// set the ith loction to hold i and verify this
	cp = new circular_buffer();
	for(i=0;i<CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
		a[i] = cp->peak(i) ;
	}
	for(i=0;i<CHUNK_SIZE;i++) {
		results = results && (a[i] == cp->peak(i)) ;
	}
	length = cp->length();
	results &= (length==CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == true) ;
	delete cp ;
	
	// a series of sets at 0 followed by a get at 0 making sure the
	// storage works correctly
	void * e ;
	cp = new circular_buffer();
	for(i=0;i<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 ;
	
	// populate the array with a series of sets at zero. These act like
	// enques on the storage. The array is now full with n,n-1,...,0
	// now dequeue the elements.
	cp = new circular_buffer();
	for(i=0;i<CHUNK_SIZE;i++) {
		cp->set(0,(void *)i) ;
	}
	length = cp->length();
	results &= (length==CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == true) ;
	for(i=0;i<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 ;
	
	// populate the array with 0,1,...,N
	// walk the array replacing each element with 2*i
	// this changes the array to contain 0,2,...,2*N
	cp = new circular_buffer();
	for(i=0;i<CHUNK_SIZE;i++) {
		cp->set(i,(void *)i) ;
	}
	for(i=0;i<(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<(CHUNK_SIZE);i++) {
		e = cp->peak(i) ;
		results &= (e == (void *)(2*i)) ;
	}
	length = cp->length();
	results &= (length==CHUNK_SIZE) ;
	empty = cp->empty();
	full = cp->full();
	results &= (empty == false) ;
	results &= (full == true) ;
	delete cp ;

	// done
	return results ;
}