home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
tlx501.zip
/
VPARRAYS.H
< prev
next >
Wrap
C/C++ Source or Header
|
1996-01-05
|
21KB
|
563 lines
/****************************************************************************
$Id: vparrays.h 501.0 1995/03/07 12:26:48 RON Exp $
Copyright (c) 1993-95 Tarma Software Research. All rights reserved.
Project: Tarma Library for C++ V5.0
Author: Ron van der Wal
Declarations of classes that implement array-like collections of (void *):
- TLVPVector
- TLVPArray
- TLVPSeq
- TLVPQueue
- TLVPStack
- TLVPSet
Arrays of (void *) are useful in their own right, and as base for array
templates for other pointer types. Because (void *) and other pointers
do not have constructors and destructors, several operations can be
implemented significantly more efficiently than with a general
TLArray<T> template.
$Log: vparrays.h $
Revision 501.0 1995/03/07 12:26:48 RON
Updated for TLX 5.01
Revision 1.8 1995/01/31 16:32:18 RON
Update for release 012
Added partial support for SunPro C++ compiler
Revision 1.7 1994/09/28 14:29:55 ron
Removed Macintosh-style #include references
Revision 1.6 1994/09/27 20:25:57 ron
Changed path separator from / to \
Revision 1.5 1994/09/26 15:25:51 ron
Renamed SetSize() functions to Resize()
Changed iterator functions for sets
Revision 1.4 1994/09/07 15:34:58 ron
Corrected definitions of VPQueue::Enqueue() and Dequeue
Revision 1.3 1994/09/06 20:23:40 ron
Small formatting changes
Revision 1.2 1994/09/06 13:59:23 ron
Adapted to changes in tlx.h
Revision 1.1 1994/08/16 18:06:56 ron
Initial revision
****************************************************************************/
#ifndef _TLX_VPARRAYS_H
#define _TLX_VPARRAYS_H
#ifndef _TLX_TLX_H
#include <tlx\501\tlx.h>
#endif
/*---------------------------------------------------------------------------
Auxiliary declarations
---------------------------------------------------------------------------*/
typedef int (*tCompareFunc)(const void *, const void *);
typedef void (*tDeleteFunc)(void *);
/*---------------------------------------------------------------------------
TLVPVector -
Class that implements a resizable vector of (void *). Indexing starts
at 0 and is range checked by default.
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPVector
{
void ** mVector; // Points to vector storage
size_t mSize; // Number of elements
bool mOwner; // Nonzero if we own pointed to objects
tDeleteFunc mDeleteFunc; // Element deletion function
public:
// The following functions provide defaults for often-used functions.
static int DefaultCompare(const void *, const void *);
static void DefaultDelete(void *);
public:
// Constructors to cater for the most common situations. Destructor
// cleans up.
TLVPVector(size_t = 0); // Creates sized vector; default = 0
TLVPVector(void *); // Creates single element vector
TLVPVector(void **, size_t); // Creates copy of C-style vector
TLVPVector(const TLVPVector &); // Copies other vector
~TLVPVector();
// Assignment operators for common situations.
TLVPVector & operator =(const TLVPVector &);
TLVPVector & operator =(void *);
// Access to vector elements. We provide both range checked and
// direct access versions (for speed). The operator [] versions have
// range checking; the PeekAt() versions don't.
void *& operator [](index_t);
void * operator [](index_t) const;
void *& PeekAt(index_t);
void * PeekAt(index_t) const;
index_t IndexOf(const void *) const;
// Clear all pointers in the vector, optionally deleting the pointed
// to objects.
void DeletePtr(void *);
tDeleteFunc SetDelete(tDeleteFunc);
void RemoveAll();
bool BecomeOwner(bool = true);
bool IsOwner() const { return mOwner; }
// Information about the size of the vector; can be used to safely run
// through its elements. Also functions to change its size.
index_t Mini() const { return 0; }
index_t Maxi() const { return mSize - 1; }
bool IsValidIndex(index_t) const;
size_t Size() const { return mSize; }
void Resize(size_t);
static size_t MaxSize() { return kMaxAlloc / sizeof(void *); }
void ExpandBy(size_t);
void ShrinkBy(size_t);
// The following function gives access to the implementation vector.
// It should be used with care.
void ** StorageVector() const { return mVector; }
private:
// Helper function for constructor and assignment.
void Copy(size_t, void ** = 0);
};
/*---------------------------------------------------------------------------
TLVPArray -
Class that represents an array of (void *). Indexing may start at any
base; the array is resizable and reindexable. Indexed access is
range checked by default.
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPArray
{
TLVPVector mVector; // The actual storage
index_t mBase; // Index base
public:
// Constructors to cater for the most common situations. Destructor
// cleans up.
TLVPArray(size_t = 0); // Creates 0-based array; default = 0
TLVPArray(index_t, index_t); // Creates array [from, to]
TLVPArray(void *); // Creates single element array
TLVPArray(void **, size_t); // Creates copy of C-style vector
TLVPArray(const TLVPArray &); // Copies other array
virtual ~TLVPArray();
// Assignment operators for common situations.
TLVPArray & operator =(const TLVPArray &);
TLVPArray & operator =(void *);
// Access to array elements. We provide both range checked and
// direct access versions (for speed). The operator [] versions have
// range checking; the PeekAt() versions don't and are implemented inline.
void *& operator [](index_t);
void * operator [](index_t) const;
void *& PeekAt(index_t);
void * PeekAt(index_t) const;
index_t IndexOf(const void *) const;
// Clear all elements in the array.
void DeletePtr(void *aPtr) { mVector.DeletePtr(aPtr); }
tDeleteFunc SetDelete(tDeleteFunc aFunc)
{ return mVector.SetDelete(aFunc); }
void RemoveAll() { mVector.RemoveAll(); }
bool BecomeOwner(bool aFlag = true)
{ return mVector.BecomeOwner(aFlag); }
bool IsOwner() const { return mVector.IsOwner(); }
// Information about the array; can be used to safely run through its
// elements.
index_t Mini() const { return mBase; }
index_t Maxi() const;
bool IsValidIndex(index_t) const;
size_t Size() const { return mVector.Size(); }
static size_t MaxSize() { return TLVPVector::MaxSize(); }
// Functions to change the size and index base of the array.
void Resize(size_t);
void ExpandBy(size_t);
void ShrinkBy(size_t);
void SetMini(index_t);
};
/*---------------------------------------------------------------------------
TLVPSeq -
Class that implements a resizable sequence of (void *). Elements can be
added at any place; access is by index (1-based), by position, or by
value.
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPSeq
{
TLVPVector mVector; // Actual vector
size_t mCount; // Number of elements used
size_t mDelta; // Amount of expansion
tCompareFunc mCompare; // Points to comparison function
public:
TLVPSeq(size_t = 0, size_t = 0); // Creates initial size & expansion
TLVPSeq(void *); // Single element sequence
TLVPSeq(void **, size_t); // Copies C-style vector
TLVPSeq(const TLVPSeq &); // Copy constructor
~TLVPSeq();
// Assignment operators.
TLVPSeq & operator =(const TLVPSeq &);
TLVPSeq & operator =(void *);
TLVPSeq & operator +=(const TLVPSeq &aSeq)
{ Append(aSeq); return *this; }
TLVPSeq & operator +=(void *aPtr)
{ Append(aPtr); return *this; }
// Insertion and removal of elements. Append() functions add the elements
// at the end of the sequence; Prepend() functions doe so at the start;
// the Insert() versions allow the user to specify the index for insertion.
// With the Replace() functions it is possible to replace parts of the
// sequence.
void Append(void *);
void Append(void **, size_t);
void Append(const TLVPSeq &);
void Prepend(void *);
void Prepend(void **, size_t);
void Prepend(const TLVPSeq &);
void InsertAt(index_t, void *);
void InsertAt(index_t, void **, size_t);
void InsertAt(index_t, const TLVPSeq &);
void Insert(void *);
void Replace(index_t, void *);
void Replace(index_t, void **, size_t);
void Replace(index_t, const TLVPSeq &);
void * Extract(void *);
void * Extract(index_t);
TLVPSeq Extract(index_t, size_t);
void * ExtractFirst();
TLVPSeq ExtractFirst(size_t);
void * ExtractLast();
TLVPSeq ExtractLast(size_t);
void DeletePtr(void *aPtr) { mVector.DeletePtr(aPtr); }
tDeleteFunc SetDelete(tDeleteFunc aFunc)
{ return mVector.SetDelete(aFunc); }
void Remove(void *);
void RemoveAt(index_t, size_t = 1);
void RemoveFirst(size_t = 1);
void RemoveLast(size_t = 1);
void RemoveAll();
bool BecomeOwner(bool aFlag = true)
{ return mVector.BecomeOwner(aFlag); }
bool IsOwner() const { return mVector.IsOwner(); }
// Indexed access to the elements. The operator [] versions are range
// checked, while the PeekAt() functions are not and are implemented inline
// for speed.
void *& operator [](index_t);
void * operator [](index_t) const;
void *& PeekAt(index_t);
void * PeekAt(index_t) const;
void *& PeekReverse(index_t);
void * PeekReverse(index_t) const;
void *& PeekFirst();
void * PeekFirst() const;
void *& PeekLast();
void * PeekLast() const;
// Searching and sorting function. Sort() (re-)sorts the sequence;
// Search() executes a binary search for an element. This assumes
// that the sequence is sorted at the time of the search.
// (The IndexOf() member function still performs a linear search
// which will work regardless of sorting order.)
//
// Collating order can be set by means of a function pointer.
void Sort();
bool Search(const void *, index_t &) const;
index_t IndexOf(const void *) const;
bool Contains(const void *) const;
tCompareFunc SetCompare(tCompareFunc);
// Information about the characteristics of the sequence, and functions
// to change them.
index_t Mini() const { return 1; }
index_t Maxi() const { return mCount; }
bool IsValidIndex(index_t) const;
size_t Size() const { return mVector.Size(); }
void Resize(size_t);
static size_t MaxSize() { return TLVPVector::MaxSize(); }
size_t Count() const { return mCount; }
size_t Available() const;
bool IsEmpty() const { return Count() == 0; }
bool IsFull() const { return Available() == 0; }
size_t Delta() const { return mDelta; }
size_t SetDelta(size_t);
void CompactStorage() { Resize(mCount); }
size_t Freeze() { return SetDelta(0); }
bool IsFrozen() const { return mDelta == 0; }
private:
// Implementation helper functions
index_t QPart(index_t, index_t);
void QSort(index_t, index_t);
};
/*---------------------------------------------------------------------------
TLVPQueue -
Class that implements a resizable queue of (void *). The queue can be
used as an ordinary FIFO queue, or as a double-ended one.
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPQueue
{
TLVPVector mVector; // Actual vector
index_t mLeft; // Position of the left end
index_t mRight; // Position of the right end
size_t mDelta; // Amount of expansion
size_t mCount; // Number of items in the queue
public:
TLVPQueue(size_t = 0, size_t = 0); // Creates initial size & expansion
TLVPQueue(void *); // Single element sequence
TLVPQueue(void **, size_t); // Copies C-style vector
TLVPQueue(const TLVPQueue &); // Copy constructor
// Assignment operators.
TLVPQueue & operator =(const TLVPQueue &);
TLVPQueue & operator =(void *);
// Insertion and removal of elements. For a double-ended queue:
//
// - AddLeft() and AddRight() add elements at either end
// - ExtractLeft() and ExtractRight() remove and return them
// - RemoveLeft() and RemoveRight() remove them
// - PeekLeft() and PeekRight() allow access to those elements
void AddLeft(void *);
void AddRight(void *);
void * ExtractLeft();
void * ExtractRight();
void RemoveLeft();
void RemoveRight();
void *& PeekLeft();
void * PeekLeft() const;
void *& PeekRight();
void * PeekRight() const;
// For FIFO queue treatment:
//
// - Enqueue() adds elements at the back end
// - Dequeue() removes and returns elements from the front end
// - PeekHead() and PeekTail() allow inspection
void Enqueue(void *aPtr) { AddRight(aPtr); }
void EnqueueUnique(void *);
void * Dequeue() { return ExtractLeft(); }
void *& PeekHead() { return PeekLeft(); }
void * PeekHead() const { return PeekLeft(); }
void *& PeekTail() { return PeekRight(); }
void * PeekTail() const { return PeekRight(); }
// For additional flexibility, it is also possible to check for
// the presence of an element and remove it if necessary:
//
// - RemoveAll() discards all elements
// - Contains() checks for presence
// - Extract() removes and returns an element
// - Remove() removes an element
void * Extract(void *);
void Remove(void *);
void RemoveAll();
bool Contains(void *) const;
void DeletePtr(void *aPtr) { mVector.DeletePtr(aPtr); }
tDeleteFunc SetDelete(tDeleteFunc aFunc)
{ return mVector.SetDelete(aFunc); }
bool BecomeOwner(bool aFlag = true)
{ return mVector.BecomeOwner(aFlag); }
bool IsOwner() const { return mVector.IsOwner(); }
// Information about the characteristics of the queue, and functions
// to change them.
size_t Size() const { return mVector.Size(); }
void Resize(size_t);
static size_t MaxSize() { return TLVPVector::MaxSize(); }
size_t Count() const;
bool IsEmpty() const { return Count() == 0; }
bool IsFull() const { return Count() == Size(); }
size_t Available() const;
void CompactStorage() { Resize(Count()); }
size_t Delta() const { return mDelta; }
size_t SetDelta(size_t);
size_t Freeze() { return SetDelta(0); }
bool IsFrozen() const { return mDelta == 0; }
private:
void EnsureAvailable(size_t = 1);
};
/*---------------------------------------------------------------------------
TLVPStack -
Class that implements a resizable stack of (void *).
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPStack
{
TLVPSeq mSeq; // Actual storage
public:
TLVPStack(size_t = 0, size_t = 0); // Creates initial size & expansion
TLVPStack(void *); // Single element sequence
TLVPStack(void **, size_t); // Copies C-style vector
TLVPStack(const TLVPStack &); // Copy constructor
// Assignment operators.
TLVPStack & operator =(const TLVPStack &);
TLVPStack & operator =(void *);
// Insertion and removal of elements is on a LIFO basis.
void Push(void *aPtr) { mSeq.Append(aPtr); }
void Push(void **aVector, size_t aSize)
{ mSeq.Append(aVector, aSize); }
void * Pop() { return mSeq.ExtractLast(); }
void * Pop(void *aPtr) { return mSeq.Extract(aPtr); }
TLVPSeq Pop(size_t aSize) { return mSeq.ExtractLast(aSize); }
void Remove(void *aPtr) { mSeq.Remove(aPtr); }
void RemoveTop() { mSeq.RemoveLast(); }
void RemoveMany(size_t aCount) { mSeq.RemoveLast(aCount); }
void *& PeekTop() { return mSeq.PeekLast(); }
void * PeekTop() const { return mSeq.PeekLast(); }
// A few extra member function for additional flexibility.
void RemoveAll() { mSeq.RemoveAll(); }
void DeletePtr(void *aPtr) { mSeq.DeletePtr(aPtr); }
tDeleteFunc SetDelete(tDeleteFunc aFunc)
{ return mSeq.SetDelete(aFunc); }
bool Contains(void *aPtr) { return mSeq.Contains(aPtr); }
bool BecomeOwner(bool aFlag = true)
{ return mSeq.BecomeOwner(aFlag); }
bool IsOwner() const { return mSeq.IsOwner(); }
// Information about the characteristics of the stack, and functions
// to change them.
size_t Size() const { return mSeq.Size(); }
void Resize(size_t aSize) { mSeq.Resize(aSize); }
static size_t MaxSize() { return TLVPVector::MaxSize(); }
void CompactStorage() { mSeq.CompactStorage(); }
bool IsEmpty() const { return mSeq.IsEmpty(); }
bool IsFull() const { return mSeq.IsFull(); }
size_t Count() const { return mSeq.Count(); }
size_t Available() const { return mSeq.Available(); }
size_t Delta() const { return mSeq.Delta(); }
size_t SetDelta(size_t aDelta) { return mSeq.SetDelta(aDelta); }
size_t Freeze() { return mSeq.Freeze(); }
bool IsFrozen() const { return mSeq.IsFrozen(); }
};
/*---------------------------------------------------------------------------
TLVPSet -
Class that implements a set of (void *). Elements can be inserted and
removed.
---------------------------------------------------------------------------*/
class _TLXCLASS TLVPSet
{
TLVPSeq mSeq; // Actual storage
public:
TLVPSet(size_t = 0, size_t = 0); // Creates initial size & expansion
TLVPSet(void *); // Single element set
TLVPSet(void **, size_t); // Copies C-style vector
TLVPSet(const TLVPSet &); // Copy constructor
// Assignment operators.
TLVPSet & operator =(const TLVPSet &);
TLVPSet & operator =(void *);
TLVPSet & operator +=(const TLVPSet &aSeq)
{ Insert(aSeq); return *this; }
TLVPSet & operator +=(void *aPtr)
{ Insert(aPtr); return *this; }
// Insertion and removal of elements. Insert() adds an element; Remove()
// removes and returns it.
void Insert(void *aPtr) { mSeq.Append(aPtr); }
void Insert(void **aVector, size_t aSize)
{ mSeq.Append(aVector, aSize); }
void Insert(const TLVPSet &aSet)
{ mSeq.Append(aSet.mSeq); }
void * Extract(void *aPtr) { return mSeq.Extract(aPtr); }
void Remove(void *aPtr) { mSeq.Remove(aPtr); }
bool Contains(const void *aPtr) const
{ return mSeq.Contains(aPtr); }
void RemoveAll() { mSeq.RemoveAll(); }
void DeletePtr(void *aPtr) { mSeq.DeletePtr(aPtr); }
tDeleteFunc SetDelete(tDeleteFunc aFunc)
{ return mSeq.SetDelete(aFunc); }
// Information about the characteristics of the set, and functions
// to change them.
size_t Size() const { return mSeq.Size(); }
void Resize(size_t aSize) { mSeq.Resize(aSize); }
static size_t MaxSize() { return TLVPSeq::MaxSize(); }
size_t Count() const { return mSeq.Count(); }
size_t Available() const { return mSeq.Available(); }
size_t Delta() const { return mSeq.Delta(); }
size_t SetDelta(size_t aDelta) { return mSeq.SetDelta(aDelta); }
size_t Freeze() { return mSeq.Freeze(); }
void CompactStorage() { mSeq.CompactStorage(); }
bool IsEmpty() const { return mSeq.IsEmpty(); }
bool IsFull() const { return mSeq.IsFull(); }
bool IsOwner() const { return mSeq.IsOwner(); }
bool BecomeOwner(bool aFlag = true)
{ return mSeq.BecomeOwner(aFlag); }
void *& PeekAt(index_t i) { return mSeq.PeekAt(i); }
void * PeekAt(index_t i) const { return mSeq.PeekAt(i); }
index_t Mini() const { return mSeq.Mini(); }
index_t Maxi() const { return mSeq.Maxi(); }
};
#endif // _TLX_VPARRAYS_H