Borland C++ template class uses a linked list of TArrayAsVector to allow creation of large arrays

myarrays.h

/*	myarrays.h			6-21-00
	Copyright (C)1997, 2000 Steven Whitney.
	Published under GNU GPL (General Public License) Version 3, with ABSOLUTELY NO WARRANTY.

	Changed or extended versions of the basic Borland BIDS array container classes.

------
To Do:

The 1 array holding a Detached or Destroyed element is compacted automatically.
You could also compact the SGiantArray, pulling elements down 1 slot from succeeding
arrays, and then delete the Tail array if it is left empty.  Time consuming.
Could make Pack() a function or do it automatically only periodically, such as when
the total # of elements is sufficiently reduced from the total capacity that packing
would allow deleting the Tail array.

*/
#ifndef __MYARRAYS_H
#define __MYARRAYS_H

#include <classlib\arrays.h>
#include "c:\bcs\my.h"

//////////////////////////////////////////////////////////////////////////////
// An array (node) in a linked list of TArrayAsVectors.
template <class T> class SArrayAsVector : public TArrayAsVector<T>
{
public:
	SArrayAsVector(int upper = 0, int lower = 0, int delta = 1)
		: TArrayAsVector<T>(upper, lower, delta) { Next = 0; }

	SArrayAsVector<T>* Next;
};
//////////////////////////////////////////////////////////////////////////////
// An ordinary TArray has only 1 Data block, which cannot exceed 64k.
// This class allows arrays of unlimited size by creating a linked list of
// multiple arrays and treating them as though they were one big array.
// It omits some of the TArray member functions.  It is mainly for storage;
// for example, Destroy does not compact the arrays, so this would not
// be a good choice for a program that creates and destroys many elements.
// An SGiantArray of T uses less memory than a linked list of T because
// each element doesn't need a *Next, and it should allow much faster access.
// Each of the arrays is automatically sized to the maximum # of T that about 64k will hold.
template <class T> class SGiantArrayAsVector
{
public:
	SGiantArrayAsVector();
	~SGiantArrayAsVector();

	typedef void (*IterFunc)(T&, void *);
	typedef int  (*CondFunc)(const T&, void *);

	int Add(const T& t);
	int Destroy(const T& t);
	int Destroy(long loc);
	long Find(const T& t) const;
	void Flush();
	int GetArrayCount() const;
	long GetItemsInContainer() const;
	int GetElementsPerArray() const { return(ElementsPerArray); }
	int HasMember(const T& t) const;
	int IsEmpty() const { return(GetItemsInContainer() == 0); }

	T& operator [](long loc) const;

	void ForEach(IterFunc iter, void *args);
	T *FirstThat(CondFunc cond, void *args) const;
	T *LastThat(CondFunc cond, void *args) const;

protected:
	BOOL AddArray();

	SArrayAsVector<T> *Head;	// first in list of arrays
	SArrayAsVector<T> *Tail;	// last array, which new additions go into
	int ElementsPerArray;		// number of T objects that fit into about 64k.
	T InternalT;				// Used for return value in case of negative index error
								// it's an alternative to throwing an exception.
};
//----------------------------------------------------------------------------
template <class T> SGiantArrayAsVector<T>::SGiantArrayAsVector()
{
Head = Tail = 0;

// The maximum # of elements a TArray can manage is 32k because some functions
// take or return ints as array indexes, so the minimum size for our calc is 2.
int tsize = max((int)sizeof(T),2);
ElementsPerArray = (int)(64000L / tsize);
AddArray();
}                      		// constructor
//----------------------------------------------------------------------------
template <class T> SGiantArrayAsVector<T>::~SGiantArrayAsVector()
{
Flush();      				// Flush deletes all but Head
delete Head;
}                        	// destructor
//----------------------------------------------------------------------------
// flushes all the arrays, AND deletes them all except Head
template <class T> void SGiantArrayAsVector<T>::Flush()
{
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	listptr->Flush();
listptr = Head->Next;
while(listptr)
{
	Tail = listptr;          	// Tail used as a temp
	listptr = listptr->Next;
	delete Tail;
}
Head->Next = 0;		// important, and wasn't here during early use of this class
Tail = Head;
}                    			//Flush
//----------------------------------------------------------------------------
template <class T> BOOL SGiantArrayAsVector<T>::AddArray()
{
SArrayAsVector<T>* newnode = new SArrayAsVector<T>(ElementsPerArray,0,0);
if(!Head)
	Head = newnode;
else
	Tail->Next = newnode;
Tail = newnode;
return(TRUE);
}                         	//AddArray
//----------------------------------------------------------------------------
template <class T> int SGiantArrayAsVector<T>::GetArrayCount() const
{
int total = 0;
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	total++;
return(total);
}                          	//GetArrayCount
//----------------------------------------------------------------------------
template <class T> long SGiantArrayAsVector<T>::GetItemsInContainer() const
{
long total = 0;
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	total += listptr->GetItemsInContainer();
return(total);
}                          	//GetItemsInContainer
//----------------------------------------------------------------------------
// You could change this so that additions go into the first array that has
// an available slot, but then overall array order would not be the order elements
// were added.
template <class T> int SGiantArrayAsVector<T>::Add(const T& t)
{
if(Tail->Add(t)) 			// add to current array?
	return(TRUE);
AddArray();                 // full: make a new array
return(Tail->Add(t));    	// and add it there
}                         	//Add
//----------------------------------------------------------------------------
// untested
template <class T> int SGiantArrayAsVector<T>::Destroy(const T& t)
{
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	if(listptr->Destroy(t))	// relies on Destroy returning nonzero if t found and destroyed
		return(TRUE);
return(FALSE);
}                           	//Destroy
//----------------------------------------------------------------------------
// untested
template <class T> int SGiantArrayAsVector<T>::Destroy(long loc)
{
if((loc < 0) || (loc >= GetItemsInContainer()))
	return(FALSE);
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
{
	if(loc < listptr->GetItemsInContainer())
		return(listptr->Destroy((int)loc));
	loc -= listptr->GetItemsInContainer();
}
return(FALSE);
}                         		//Destroy
//----------------------------------------------------------------------------
// untested
template <class T> int SGiantArrayAsVector<T>::HasMember(const T& t) const
{
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	if(listptr->HasMember(t))
		return(TRUE);
return(FALSE);
}                        		//HasMember
//----------------------------------------------------------------------------
// untested
// returns MAXLONG if not found
template <class T> long SGiantArrayAsVector<T>::Find(const T& t) const
{
long index = 0;
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
{
	int found = listptr->Find(t);
	if(found != INT_MAX)
		return(index + found);
	index += listptr->GetItemsInContainer();
}
return(MAXLONG);
}                    			//Find
//----------------------------------------------------------------------------
// To use operator[] within the class and within a class derived from this,
// use (*this)[i].  Parentheses required for proper grouping.
// In derived, you can also use SGiantArrayAsVector<const char*>::operator[](i)
template <class T> T& SGiantArrayAsVector<T>::operator [](long loc) const
{
// you can't do this because there are lots of problems if operator[] isn't const
// while(loc >= GetItemsInContainer())		// expand to make loc legal, if necessary
// 	Add(InternalT);
if((loc >= 0) && (loc < GetItemsInContainer()))
	for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	{
		if(loc < listptr->GetItemsInContainer())
			return((*listptr)[(int)loc]);
		loc -= listptr->GetItemsInContainer();
	}

logerror("SGiantArrayAsVector<T>::operator [] received out-of-bounds index");

// because the function is const, InternalT is also(?), but we must return a
// T&, not a const T&.  Caller can do anything it wants with InternalT (change is ok).
// Other solutions (making this fn nonconst), produce even worse problems:
// (widespread "nonconst fn called for const object" warnings)
// Not sure if the duplicate const/nonconst versions in the container class exist
// because of this, and why I've never seen this problem before.

return(const_cast<T&>(InternalT));	// return something legal, although useless
}                          		//operator []
//----------------------------------------------------------------------------
// untested
template <class T> void SGiantArrayAsVector<T>::ForEach(IterFunc iter, void *args)
{
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
	listptr->ForEach(iter, args);
}                             	//ForEach
//----------------------------------------------------------------------------
// untested
template <class T> T* SGiantArrayAsVector<T>::FirstThat(CondFunc cond, void *args) const
{
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
{
	T* found = listptr->FirstThat(cond, args);
	if(found)
		return(found);
}
return(0);
}                            	//FirstThat
//----------------------------------------------------------------------------
// untested
template <class T> T* SGiantArrayAsVector<T>::LastThat(CondFunc cond, void *args) const
{
T* found = 0;
for(SArrayAsVector<T> *listptr = Head ; listptr ; listptr = listptr->Next)
{
	T* temp = listptr->LastThat(cond, args);
	if(temp)
		found = temp;
}
return(found);
}                             	//LastThat
//----------------------------------------------------------------------------
// 					end class SGiantArrayAsVector
//////////////////////////////////////////////////////////////////////////////
#endif	// __MYARRAYS_H

	Search the web Search this site
Copyright ©2012 Steven Whitney. Last modified Sun 07/29/2012 11:10:48 -0700.