// © Copyright 1995. Joseph Bergin. All rights reserved.

#ifndef __FreeStore__
#define __FreeStore__

#include "Array.h"

typedef int index;

// The class FreeStore illustrates how the free store in
// C++ operates.  If you want to store something, ask a
// FreeStore object for a new cell with getCell.  You
// will get back an index (instead of a pointer).  Use
// the index to set a value into the FreeStore with
//		FS[index] = whatever;
// The left side of this assignment corresponds to
// de-referencing a pointer (i.e. like *index).
// getCell returns -1 when no cells are available.  This
// value corresponds to NULL for pointers.
// When you are done with the cell return it to the
// avaliable list of cells with freeCell(index).
// The maximum number of available cells is defined when
// you create the FreeStore object.

// Indexing into a FreeStore with an index not returned by
// getCell is analogous to using a dangling pointer.

//template <class E> class FreeStore;

template <class E>
union		// uses overlay storage for member variables
//class		// uses sequencial storage for variables
	FreeStoreCell
{//  NO public:
	private:
		FreeStoreCell() // Uninitialized cells
		:	_link(-1)
		{
		}

		E _value;
		index _link;
	friend class FreeStore<E>;
	friend class Array<FreeStoreCell<E> >;
};

template <class E>
class FreeStore
{	public:
		FreeStore(int size = 100)
		:	_storage(size),
			_head(0)
		{	for(int i = 0; i < size - 1; i++)
				_storage[i]._link = i+1;
			_storage[size - 1]._link = -1; //Redundant.
		}

// EXERCISE. Remove the following function
		int length()
		{	int result = 0;
			index ptr = _head;
			while(ptr != -1)
			{	result++;
				ptr = _storage[ptr]._link;
				if(result > _storage.length())
            	userERROR("Illegal linkage in FreeStore.");
			}
         return result;
		}
// EXERCISE. The above function is an exercise

		index getCell()
		{	index result = _head;
			if( _head != -1)
			{	_head = _storage[_head]._link;
				_storage[result]._link = -1;
			}
			return result;
		}

		void freeCell(index loc)
		// Precondition: loc was originally returned by
		// getCell, and has not previously been passed to
		// freeCell. Calling this when loc was not returned
		// by getCell is a disaster.
      // Returns a cell to the list. 
		{	if(loc>=0 && loc < _storage.length())
			{	_storage[loc]._link = _head;
				_head = loc;
			}
			else
				userERROR("Illegal cell in FreeStore.");
		}

		E & operator[](index loc)
		// Precondition: loc was originally returned by
		// getCell, and has not been passed to freeCell
		{	if(loc>=0 && loc < _storage.length())
			{	return _storage[loc]._value;
			}
			else
				userERROR("Illegal cell in FreeStore.");
		}

	private:
		Array<FreeStoreCell<E> > _storage;
		index _head;
//	friend class Array<E>;
//	friend class FreeStoreCell<E>;
};

// Note that each FreeStoreCell has enough room to hold
// the value required by the user.  It has a small amount
// of extra "overhead" room as well, to hold the _link
// index.  
#endif