| |
|
|
|
3 REFERENCE
3.1 Functions and classes
This section contains the man pages for all the functions and classes provided by the FND library.
The following diagram shows the hierarchy of the available classes.
The fndABST_ARRAY class provides the basic support for defining dynamic
arrays, i.e. arrays whose dimension changes dynamically by adding and
removing elements.
This array can contain heterogeneous collections of objects of subclasses
of fndOBJECT and provides range checking and definition of upper and
lower bounds. In particular the definition of a lower bound allows
to instantiate an array with a first element != 0 without having to
use dangerous C pointer and allocation tricks.
fndABST_ARRAY( int upper, int lower = 0, sizeType aDelta = 0 );
fndABST_ARRAY();
Constructors.
The empty contructors build a new generic array, with index starting
from 0 and whose size can be dynamically changed based on the number of
allocated elements.
The constructor with parameters allows to define lower and upper limits
for the array and the block size used to dynamically reallocate the
array. This allows to optimize memory allocation depending on the type
of access
virtual ~fndABST_ARRAY();
Destructor. Deallocates all the dynamically allocated memory and, if
requested, the objects containet in the array.
int LowerBound() const;
int UpperBound() const;
sizeType ArraySize() const;
Return respectively the lower and upper bounds of the array, i.e.
the lower and upper valid subscript indexes, and the total number
of elements in the array.
virtual fndCONTAINER_ITERATOR& InitIterator() const;
Allocates and return a new iterator to navigate inside the array.
The user must take care of deallocating the iterator when no more
necessary.
virtual void Add( fndOBJECT& ) = 0;
Add the given fndOBJECT to the array.
This is a pure virtual method and must be implemented in sub-classes
(see fndARRAY(4) for an example).
virtual void Destroy( int i ) { Detach( i, 1 ); }
virtual void Destroy( const fndOBJECT& o ) { Detach( o, 1 ); }
Destroy the given element removing it from the array and
freeing the allocated memory by calling delete.
virtual void Detach( int i, int destroy = FALSE );
virtual void Detach( const fndOBJECT& o, int destroy = FALSE );
Detach the given element removing it from the array.
If the second parameter is TRUE, also frees the allocated memory
by calling delete (this is equivalend to Destroy()).
The first implementation directly destroies the elemnt at the given position.
The second implementation takes a reference to the element to be destroied
and searches for it in the array.
virtual void Empty( int destroy = FALSE );
Removes all the elements from the array.
If destroy==TRUE also deletes the elements by calling delete
virtual int IsEqual( const fndOBJECT& ) const;
Returns TRUE if the fndABST_ARRAY is identical to the given fndOBJECT.
virtual void PrintContentsOn( ostream& ) const;
Prints the contents of the whole array, by calling in sequence the
PrintContentsOn() method for all contained items.
Used mainly for debugging purposes.
fndOBJECT& operator []( int atIndex ) const { return ObjectAt( atIndex ); };
Subscript operator [] allows to retrieve each array element by passing
its index in the array itself
fndOBJECT &ObjectAt( int i ) const;
fndOBJECT *PtrAt( int i ) const;
Return a reference or a pointer to the fndOBJECT
at the requested position
void SetData( int, fndOBJECT * );
Put the given fndOBJECT in the assigned position inside
the array. The memory must have been already allocated
for the array entry.
void InsertEntry( int );
Creates space for a new array item at the given position moving
up of one position all the elements from there to the end of the
array. The array must already have enough allocated entries.
void RemoveEntry( int );
Clean up the given array entry slot.
If the slot is in a position lower than the current insertion point
it calls SqueezeEntry()
void SqueezeEntry( int );
Clean up the given array entry slot and moves back all the following
elements sqeezing the array and making it one element smaller.
int Find( const fndOBJECT & );
Searches in the array for the given element and returns its index
or INT_MIN if not found.
void Reallocate( sizeType );
Reallocates the whole array to the given size.
To optimize allocation, the actual array size is rounded up to the
nearest multiple of the delta block allocation size.
Arrays are never reallocated to a smaller size.
sizeType delta;
Memory allocation block size.
New elements are always allocated as multiples of delta to optimize
memory allocation and reduce fragmentation
int lowerbound;
Lower valid array index.
int upperbound;
Upper valid array index
int whereToAdd;
Insertion point. Where a new element will be inserted
fndOBJECT **theArray;
Physical array, dynamically allocated
int ZeroBase( int loc ) const;
Given a logical array position, returns the corresponding physical
position removing the offset defined by lowerbound
int BoundBase( unsigned loc ) const;
Given a physical array position returns the corresponding
logical position taking into account the lowerbound deifnition
fndARRAY( int upper, int lower = 0, sizeType aDelta = 0 )
fndARRAY()
Constructor to create a new empty array.
Array are fully dynamic in size, unless specified.
If limits are specified, the range for array indexing goes from
the lower to the upper values included and can contain not more
than these elements.
int upper specifies an optional upper limit for the array index
int lower specifies an optional lowr limit for the array index
sizeType aDelta to optimize performances, element are allocated
not one at the time, but in bunches. aDelta
specifies the bunch size. 0 means to use
the default value 10.
~fndARRAY();
Destructor.
virtual void Add( fndOBJECT& );
Add an element in the array at the first free position
virtual void AddAt( fndOBJECT&, int index, int deleteToo = FALSE);
Add an element in the array at the specified position, eventually
replacing an already existing one. If deleteToo==TRUE and when
the new element replaces an already existing one at the same
position, the old element is deleted and not just detached from the
array.
The fndARRAY_ITERATOR class implements an iterator over the elements
of an fndABST_ARRAY or subclasses.
When instantiated it points to the first element inthe array and can be
incremented to retrieve in a sequence all the elements.
fndARRAY_ITERATOR( const fndABST_ARRAY& );
Creates a new iterator for the given array.
The class provides a specific implementation for all the pure
virtual methods of the basic fndCONTAINER_ITERATOR class.
int currentIndex;
Current position in the array
const fndABST_ARRAY &beingIterated;
Array on which the iterator works
The fndASSOCIATION class is used to handle associantions of instances
of fndOBJECT subclasses.
An association is a couple (key, value) or (key,definition) and is
used to build dictionaries (fndDICTIONARY(4)), deifnition tables,
hash tables or relations in databases.
fndASSOCIATION();
fndASSOCIATION(fndOBJECT &k, fndOBJECT &v);
fndASSOCIATION( const fndASSOCIATION &a );
Constructors.
The first constructor creates and empty association; the second an association
between the given key and value; the third an association identical to the
given one (copy constructor)
virtual ~fndASSOCIATION();
Deletes the association and (if required by calling DelItemsOnDelete())
also the elements in the association.
fndOBJECT &Key() const;
fndOBJECT &Value() const;
Returns respectively a reference to the key or the value of the
association
virtual void SetKey(fndOBJECT &k);
virtual void SetValue(fndOBJECT &v);
Sets respectively a new key or value for the association
virtual hashValueType HashValue() const { return aKey->HashValue(); }
Return the hash value for the key of the association
virtual int IsEqual( const fndOBJECT &toTest) const;
Returns TRUE if the given fndOBJECT is identical to the association
virtual int IsAssociation() const;
Returns TRUE. It implements a basic method of the fndOBJECT
base class and is used to identify associations with respect
to other fndOBJECT instances.
virtual void PrintOn( ostream& outputStream)const;
Print the associan content, mainly for test and debugging purposes,
by calling the PrintOn() method of the key and value objects.
virtual void DelItemsOnDelete(int destroy = TRUE)
If destroy=TRUE instruct the object to destroy also the key and
value object when it is deleted.
The fndAUTO_PTR template class implements the concept of
"automatic pointer", i.e. of a pointer that automatically deletes its contained
object when it exits out of scope.
The class is very handy if the user wants to be sure that an object is deleted
when its pointer exits of scope, and is in particular essential when there
is no explicit control over the return point of a function, for example when
using exceptions.
The class implements the concept of "object ownership".
When an object is given to the fndAUTO_POINTER, it gets the ownership of the
object itself, i.e. the right of deleting it when it is deleted itself.
The ownership can be released on request or passed to another instance of
fndAUTO_POINTER, ensuring that only one fndAUTO_POINTER at the time can
have the ownership of an object, avoiding multiple deletion of dynamically
allocated memory.
The implementation as a template class allows any valid type to be handled
via fndAUTO_POINTER instances.
The contents operator (*) and the de-reference operator (->) make the
fndAUTO_POINTER mimic the behaviour of a normal pointer to the type of the
owned object. Still there are some small differences in behaviour and sometimes
it is necessary to retrieve the owned object via the explicit Get() method.
Refer to the mentioned paper on the C/C++ User Journal for details on the
limitations (see CAUTIONS section).
fndAUTO_PTR(T *p = NULL);
Createas an fndAUTO_POINTER and optionally gives it in ownership
the object passed vie the p pointer
fndAUTO_PTR(fndAUTO_PTR& rhs);
Copy constructor. It also takes the ownership of the object
previously owned by the copied fndAUTO_POINTER
fndAUTO_PTR &operator=(fndAUTO_PTR& rhs);
Assignement operator. It also takes the ownership of the object
previously owned by the copied fndAUTO_POINTER
~fndAUTO_PTR();
Destructor. In it owns an object, this is deleted as well.
T& operator*() const;
Contents operator.
Returns a reference to the owned object, like with a normal C pointer.
It is undefined if no object is owned.
T *operator->() const;
Dereference operator.
Usable to directly access methods and members of the owned object
like with a normal C pointer.
T *Get() const;
Explicitly return the pointer to the owned object.
T *Release();
Returned the pointer to the owned object and releases ownership.
T *Take(T *p=0);
Takes ownership of a new object.
If it already owns an object, it is first deleted.
(this method is not part of the ANSI C++ Draft Standard implementation)
The template is defined in the ISO C++ Draft Standard, but is not implemented in
the GNU C++ compiler and in many other implementations of the C++ Standard Library.
This implementation is very similar to the one presented by B.Schnidt
in the C/C++ User Journal, August 1997, pp.81-85
An fndBAG is the simplest collection.
It is just a non organized goup of objects. It allows many copies of the
same object or of identical objects and provides basic features for adding,
removing and searching inside the collection.
It also allows to apply an action iteratively on all the objects
of the collection.
All methods are just specific implementations of methods defined
in the ancestor classes fndCONTAINER and fndCOLLECTION.
From the implementation point of view, it has been necessary to overwrite
most of the methods inherited from the base classes to hide the fact that the
elements are in reality stored inside an fndHASH_TABLE that is a data
member of the class.
fndBAG( sizeType bagSize = fndDEFAULT_BAG_SIZE );
Creates a new fndBAG. The bag size changes dynamically as requested
based on the same rules os dynamical arrays, but an initial size can be
given to optimize allocation.
~fndBAG();
Delete the bag and, if defined by calling the inherited DelItemsOnDelete()
method, all the contained objects.
A collection is a container where it is possible to add, remove and search
objects, as instances of fndOBJECT subclasses.
As such it inherits all the methods defined in the parent class fndCONTANER
and adds all necessary methods to perform insertion, deletion and search.
It is a pure virtual class, since many of these methods are only defined and will
be implemented in the derived classes, where the specific insertion, deletion and
search algorithms and strategies can be defined.
This allows to easily change collection implementation (for example from fndARRAY
to fndQUEUE) in applications, just accessing elements via the basic fndCOLLECTION
methods without taking care of the actual subclass used.
virtual ~fndCOLLECTION();
Destructor
virtual void Add( fndOBJECT &o );
Add a new fndOBJECT to the bag.
This method is defined in the base class fndCOLLECTION.
virtual void Detach( const fndOBJECT &o, int dt=0) ;
virtual void Destroy( const fndOBJECT& o );
Detach the given fndOBJECT from the bag and, if dt==TRUE, also
delete it.
This method is defined in the base class fndCOLLECTION.
Destroy() is equivalent to Detach(obj,TRUE)
virtual int HasMember( const fndOBJECT &o ) const;
Returns TRUE if the given fndOBJECT is part of the fndBAG
This method is defined in the base class fndCOLLECTION.
virtual fndOBJECT &FindMember( const fndOBJECT &o ) const;
This method is defined in the base class fndCOLLECTION.
This is the basic class to handle containers.
A container is an object able to manage a group of other objects
providing functions to navigate, search, add, remove elements and so on.
In this implementation any container can handle instances of objects
derived from the fndOBJECT class. The same container can handle objects
of different classes at the same time, provided that they are all
subclasses of fndOBJECT.
When an object is added to the contained, only a reference to it
is stored in the container itself. The object must not be deleted
before detaching (removing) it from the container. If this is done
there will be hanging pointers in the container.
When an object is detached from the container, it is not deleted, unless
this is explicitly requested.
In the same way, when a container is deleted the contained objects
are not deleted, unless explicitly requested by calling
DelItemsOnDelete(TRUE) before deleting the container.
This allows an optimized handling of objects and allows storing
the same object in more than one container at the same time.
It is important to remember that automatic deletion of objects
when they are removed from the container can be performed only
on dynamically allocated objects and not on objects allocated on the stack.
As a consequence it is very important not to mix statically and dynamically
allocated objects in the same container and clearly document if an instance
of a container in an application is meant to be the master/owner of the contained
objects, i.e. if it wants to get full responsibility over them and delete
them when needed. In this case it is important to pass only dynamic
objects and to pay attention to leave the responsibility for deleting
the items to this container.
It is a pure virtual class, since some methods are only defined and will
be implemented in the derived classes, where the specific
container algorithms and strategies can be defined.
The class fndCONTAINER_ITERATOR provides a basic class for building
iterators on a container, i.e. objects that behave like a pointer
running on the items in the container, backward and forward.
fndCONTAINER()
fndCONTAINER( const fndCONTAINER& );
virtual ~fndCONTAINER();
If it has been called DelItemsOnDelete(TRUE) the contained.
items are also physically deleted and not just detached.
This feature can be used only with dynamically allocated
elements. The behaviour is unpredictable if trying to delete
elements not dynamically allocated.
virtual hashValueType HashValue() const;
Return the specific hash value for the fndCONTAINER.
virtual int IsEqual( const fndOBJECT& ) const;
Return TRUE if the given object is equal to the fndCONTAINER
virtual void ForEach( iterFuncType, void* ) const;
Executes the given iterative function for each fndOBJECT in the bag.
An iterFuncType is a function with the following prototype:
void func( fndOBJECT&, void* );
It takes an fndOBJECT reference and a pointer to
a list of parameters to the function. The parameter list pointer
may be NULL.
This method is defined in the base class fndCONTAINER.
virtual void PrintOn( ostream& ) const;
virtual void PrintHeader( ostream& ) const;
virtual void PrintSeparator( ostream& ) const;
virtual void PrintTrailer( ostream& ) const;
Set of utility functions to print on the specified stream the
content of the container.
The first method prints the whole content of the container, while
the other methods print respectively a header for the object, a separator
between each contained object and a footer after the last object.
Each contained fndOBJECT is printed by calling its PrintOn() method.
virtual const fndOBJECT& FirstThat( condFuncType, void* ) const;
virtual const fndOBJECT& LastThat( condFuncType, void* ) const;
Applies the given conditional function and returns a reference to
the first (last) fndOBJECT in the fndBAG that satisfy the condition or
NOOBJECT is none.
An condFuncType is a function with the following prototype:
int condFuncType( const fndOBJECT&, void* );
It takes a reference to an fndOBJECT as first parameter and
implements a conditional test and returns 0 if the condition was met,
non-zero otherwise. The non-zero values are defined by the individual
function.
This methods are defined in the base class fndCONTAINER.
virtual fndCONTAINER_ITERATOR& InitIterator() const = 0;
Returns a new iterator dynamically allocated.
The user must make sure of deleting the iterator when no more needed.
int IsEmpty() const
Returns a 1 (TRUE) if the container has no member.
virtual void Empty( int destroy = FALSE )
Remove all the items from the container. If destroy==TRUE the
items are also physically deleted and not just detached.
This parameter can be used only with dynamically allocated
elements. The behaviour is unpredictable if trying to delete
elements not dynamically allocated.
virtual void DelItemsOnDelete(int destroy = TRUE)
If called with TRUE, instructs the fndCONTAINER to delete also
all the contained fndOBJECT instances when it is deleted.
This can be used only with dynamically allocated
elements. The behaviour is unpredictable if trying to delete
elements not dynamically allocated.
countType GetItemsInContainer() const
Returns the current number of objects in any container.
countType itemsInContainer; Number of items in the ocntainer
int delItemsOnDelete; Flag for deleting contained items
on delete.
It is important to remember that automatic deletion of objects
when they are removed from the container can be performed only
on dynamically allocated objects and not on object allocated on the stack.
Read the DESCRIPTION section for details.
The class fndCONTAINER_ITERATOR provides a basic class for building
iterators on a container, i.e. objects that behave like a pointer
running on the items in the container, backward and forward.
It is a pure virtual class, since most methods are only defined and will
be implemented in the derived classes, parallel to the
corresponding container classes, where the specific
container algorithms and strategies can be defined.
virtual ~fndCONTAINER_ITERATOR();
Destruct the iterator
virtual operator int() = 0;
Cast operator to integer.
To be used in logical espressions to transparently query the
iterator for the existence of other ilements in the array.
Returns TRUE if there are other elements in the array
or FALSE if there are no more elements.
virtual operator fndOBJECT&() = 0;
virtual fndOBJECT &GetCurrent() = 0;
Cast operator and normal method to retrieve a reference
to the current object from the array. It returns NOOBJECT
if there is no object.
virtual fndOBJECT& operator ++(int) = 0;
Post increment operator
Returns a reference to the current object and then
increments the iterator to point to the next one.
(NOOBJECT if none)
virtual fndOBJECT& operator ++() = 0;
Pre increment operator.
Increments the iterator to point to the next array element
and returns a reference to this new object (NOOBJECT if none)
virtual void Restart() = 0;
Reset the iterator to point to the first element int he array
The fndDEQUE class implements a double queue container, i.e. a collection of
fndOBJECT instances where it is possible to insert and extract objects
from both ends.
Consider the queue as a list of elements one behind the other.
A simple queue implements the basic FIFO (First In First Out) retrieval
concept: onjects are inserted in the queue from the left side and are
extracted from the queue from the right side.
The double queue allows to insert and extract both from the left and right
side, by using the PutLeft() and PutRight() methods to insert and
GetLeft() and GetRight() methods to extract.
The PeekLeft() and PeekRight() methods can be used just to inspect
the first element to the left or to the right, without actually extract them
from the queue.
The simple Get()/Put() FIFO algorithm is implemented in
fndQUEUE subclass, that is just a simple wrapper to implement
the standard interface and hide the methods not to be used.
A part from an implementation of the pure virtual methods defined in the
fndCONTAINER(4) class, the following public methods are provided:
fndOBJECT &PeekLeft() const
Returns for inspection the fndOBJECT at the left/right end
of the queue
Returns for inspection the fndOBJECT at the left/right end
of the queue
Returns for inspection the fndOBJECT at the left/right end
of the queue
fndOBJECT &PeekRight() const
Returns for inspection a reference to the fndOBJECT at the left/right end
of the queue
fndOBJECT &GetLeft()
fndOBJECT &GetRight()
Returns a reference the fndOBJECT at the left/right end
of the queue and remove it from the queue itself
void PutLeft( fndOBJECT &o )
void PutRight( fndOBJECT &o )
Insert the given fndOBJECT in the queue from the left/right side
The fndDICTIONARY class implements the concept of dictionary, i.e.
of a set of objects for which a definition and a description are provided
and for which it is possible, given the definition, to retrieve the
description.
This is a very commonly used concept and this is one of the most
usefull class in the library.
The Add() method is used to insert pair (definition,description)
in the dictionary, in the forms of fndASSOCIATION(4) instancies,
while the Lookup() method gets a definition and returns, if it exist,
the corresponding fndASSOCIATION(4) inside the fndDICTIONARY(4)
For the rest, it ihnerits all the methods provided by the base class
fndSET(4) and its own other anchestors.
virtual void Add( fndOBJECT &toAdd );
This method is used to insert a new fndASSOCIATION(4) in the dictionary.
The prototype declares an fndOBJECT& generic reference parameter to
overload the base class virtual Add() method, but the passed object
must be an fndASSOCIATION (or subclass).
If not, no item is added to the fndDICTIONARY.
The "definition" is the Key() of the fndASSOCIATION(4), while the
"description" if the Value() of the fndASSOCIATION(4)
fndASSOCIATION &Lookup( const fndOBJECT &toLookup ) const;
Searches inside the dictionary for an fndASSOCIATION with the
given Key(), if found returns a reference to the fndASSOCIATION(4),
if not returns NOOBJECT.
This fndFLOAT class provides a wrapper for the float fundamental C++
type as a subclass of fndOBJECT.
This is necessary in order to provide the possibility of putting
simple floating point numbers inside containers, for example to build
dynamical arrays (fndARRAY(4)) or lists (fndLIST(4)) of floating points.
The class if a subclass of the basic fndSORTABLE class an implementes
all the pure virtual methods defined there, since an order relation (<)
is a basic property of floating point numbers.
The need of providing wrappers for the fundamental types of the
language puts in evidence the main limitation and annoyance of the fnd
containers library: an object can go inside a container ONLY IF it is
an fndOBJECT.
A part from the implementation of the methods defined by the fndSORTABLE
class and anchestors, the fndFLOAT class provides a constructor, an
assignement and a cast to float operator that make as much transparent
as possible its usage whenever a normal float would be used:
fndFLOAT( const float aFloat=0 );
fndFLOAT &operator =( const fndFLOAT& );
operator const float() const;
fndHASH_TABLE, fndHASH_TABLE_ITERATOR - Hash table collection class
and correpconding iterator class
The hash table is a very efficient way of storing objects in a
collection and of retrieving them, since provide in effect
direct access to most elements without wasting memory, if properly used.
Every algorithm book provides a description of the hash table concept.
An object to be inserted inside an hash table must provide an
hashing method (the fndOBJECT::HashValue() pure virtual method), i.e
a method able to generate an integer value called "the hash value".
The hash value is used to convert a search key in a table address.
Ideally, different keys should be transformed in different addresses,
but since no hashing algorithm is perfect, it is always possible that two
or more keys produce the same address. The second part of the hashing
search consists in the resolution of the collisions.
The efficiency of the hashing search depends on the quality of the
hashing function and on the size of the table: the smaller the table,
the higher the probability of collisions; the bigger the table, the smaller
the probability of collisions: a faster search but with higher memory
consumption.
This implementation of the fndHASH_TABLE class, stores the entries
in lists, one per each address in the table, containing all elements
with the same table address.
This means that when searching an element, the key is generated
and the corresponding list is accessed direclty and very fast, then the
element must be searched inside the list among all the other colliding
elements.
The class allows to define the size of the table in order to balance
memory consumption and search speed while a proper selection of hashing
algorithms allows to reduce the probability of collisions.
All fndOBJECT subclasses provided with the library implement carefully
selected and efficient hashing algorithms from the literature.
From the usage point of view, an fndHASH_TABLE provides only the
basic interface defined by the fndCOLLECTION base class and the
whole implementation is hidded.
It is always possible to replace one fndCOLLECTION with any other
one without changing other code than the declaration.
this is one of the biggest advantages of using a container/collection
class library.
The InitIterator() implementation returns in reality an fndHASH_TABLE_ITERATOR(4),
i.e. a special fndCONTAINER_ITERATOR(4) able to navigate inside an
fndHASH_TABLE(4).
A part from the implementation of the methods defined by the fndCOLLECTION
class and anchestors, the fndHASH_TABLE class provides just a constructor
the gets as optional parameter the desired hash table size.
fndHASH_TABLE( sizeType = fndDEFAULT_HASH_TABLE_SIZE );
The fndHASH_TABLE_ITERATOR class provides only a specific implementation
of the methods required by the fndCONTAINER_ITERATOR(4) class.
hashValueType GetHashValue( const fndOBJECT & ) const;
Extract the hash value from the given object and maps
it to the internal table, as a function of its size.
sizeType size;
Size of the internal table
fndARRAY table;
The internal table is actually implemented as a dynamic array.
Inside the array every element is a list, but lists are dynamically
allocated only when necessary, to optimize memory usage.
This fndINT class provides a wrapper for the int fundamental C++
type as a subclass of fndOBJECT.
This is necessary in order to provide the possibility of putting
simple integer numbers inside containers, for example to build
dynamical arrays (fndARRAY(4)) or lists (fndLIST(4)) of integers.
The class if a subclass of the basic fndSORTABLE class an implementes
all the pure virtual methods defined there, since an order relation (<)
is a basic property of integer numbers.
The need of providing wrappers for the fundamental types of the
language puts in evidence the main limitation and annoyance of the fnd
containers library: an object can go inside a container ONLY IF it is
an fndOBJECT.
A part from the implementation of the methods defined by the fndSORTABLE
class and anchestors, the fndINT class provides a constructor, an
assignement and a cast to int operator that make as much transparent
as possible its usage whenever a normal int would be used:
fndINT( const int aInt=0 );
fndINT &operator =( const fndINT& );
operator const int() const;
The fndLIST class is one of the most important classes in the fnd class
library.
It implements the concept of a double linked "list of objects",
i.e. a dynamic collection of objects where it is possible to add and remove elements
and to efficiently navigate fro one element to the previous or the following
one.
Elements are typically added at the end of the list (this is the
behaviour of the standard Add() method.
A part from all the methods inherited from the base classes fndCONTAINER
and fndCOLLECTION (when necessary, implemented here for the specific
implementation issues), it provides also the possibility of explicitly
adding and deleting elements from the head ot from the tail of the
list.
The friend class fndLIST_ITERATOR provides an fndLIST specific
implementation of the iterator concept, extending the concept to
the revers iterator: a "normal iterator" runs from the head to the tail
of the list, while a "reverse iterator" runs from the tail to the
head, allowing for the implementation of both FIFO or LIFO algotithms.
From the implementation point of view, the class contains mainly
pointers to elements of type fndLIST_ELEMENT, corresponding
to the head and to the tail of the list.
Every instance of fndLIST_ELEMENT contains a pointer to the fndOBJECT
in that place in the list and two other pointers to fndLIST_ELEMENT:
one to the place holder for the next and one to the previous element
of the list.
In this way it is easy to implement efficient insertion and deletion
of elements just allocating/deallocating instances of the fndLIST_ELEMENT
class and reorganizing properly the links to the next and previous.
The double linked list data handling concept is very well described
in all algorithm books.
virtual void AddAtHead( fndOBJECT& );
virtual void AddAtTail( fndOBJECT& );
Add the given fndOBJECT respectively to the head or to the
tail of the fndLIST
virtual void DestroyFromHead( const fndOBJECT& );
virtual void DestroyFromTail( const fndOBJECT& );
Searches for the given object in the fndLIST, starting from the head
or from the tail. If it exist it is removed from the fndLIST and deleted
virtual void Detach( int pos, int delToo= 0 );
Detach the element at the requested position in the list (from the
head) and if delToo==TRUE also deletes it.
virtual void DetachFromHead( const fndOBJECT&, int delToo= 0 );
virtual void DetachFromTail( const fndOBJECT&, int delToo= 0 );
Searches for the given object in the fndLIST, starting from the head
or from the tail. If it exist it is detachet from the fndLIST and
if delToo==TRUE also deleted.
virtual fndCONTAINER_ITERATOR& InitIterator() const;
virtual fndCONTAINER_ITERATOR& InitReverseIterator() const;
Returns a reference to a new dynamically allocated iterator or
reverse iterator able to run on the elements of the fndLIST.
It actually returns an instance of fndLIST_ITERATOR(4).
The user must take of deleting the iterator when not needed any more.
virtual fndOBJECT &PeekAtHead() const;
virtual fndOBJECT &PeekAtTail() const;
Peek the fndOBJECT at the head/tail of the fndLIST, i.e. returns
a reference to the fndOBJECT but does not remove it from the fndLIST.
fndLIST_ELEMENT* head;
fndLIST_ELEMENT* tail;
Pointer to the instances of the fndLIST_ELEMENT(4) class that handle
the head and the tail of the fndLIST
The fndLIST_ELEMENT class is just a support class, used for the implementation
of the fndLIST class: elements of an fndLIST are not stored directly in the list, but
for every object to be put in the list there is a corresponding instance
of fndLIST_ELEMENT, that is responsible for maintaining also the
pointers to the next and previous elements of the douple linked list.
fndLIST_ELEMENT();
fndLIST_ELEMENT( fndOBJECT* o );
~fndLIST_ELEMENT()
The only implemented methods are these simple constructors and
destuctor.
fndLIST_ELEMENT* next;
fndLIST_ELEMENT* previous;
Pointers to the next and previous elemnts in the double linked list.
fndOBJECT* data;
Pointer to the real fndOBJECT instance in the list for this position.
The class fndLIST_ITERATOR provides an fndLIST specific
implementation of the iterator concept, extending the concept to
the revers iterator: a "normal iterator" runs from the head to the tail
of the list, while a "reverse iterator" runs from the tail to the
head, allowing for the implementation of both FIFO or LIFO algotithms.
A part from the methods defined in the fndCONTAINER_ITERATOR class, it
provides the following methods:
fndLIST_ITERATOR( const fndLIST&, int atHead = 1 );
This specific contructor has an extra otional parameter to define
the iterator starting point: by default (atHead=TRUE) it will start
from the head of the fndLIST, if FALSE it will start from the tail,
allowing a proper initializzation of the reverse iterator.
virtual fndOBJECT& operator ++(int);
virtual fndOBJECT& operator --(int);
Post increment and de-crement operators
Returns a reference to the current object and then
increment/de-crement the iterator to point to the next/previous one.
(NOOBJECT if none)
virtual fndOBJECT& operator ++();
virtual fndOBJECT& operator --();
Increment/de-crement the iterator to point to the next/previous one.
(NOOBJECT if none) and returns a reference to this new object.
fndLIST_ELEMENT* currentElement;
Current element in the list
fndLIST_ELEMENT* startingElement;
Initial element (head or tail) in the list,
used to be able to Reset().
The fndNAME_MAP class provides an easy way to build and query maps
of index/name couples, where the index is an unsigned integer.
This is very usefull when enumerations have a double representation:
a numerical index and a conventional name in the form of a string
(for example, an application state is handled internally to an
application by using an index, but is if reported to client
applications in the form of a readable string).
The fndNAME_MAP provide the methods for converting from name to
index and viceversa, while the map itself is easily built
as an array of fndNAME_AND_INDEX structures, where:
struct fndNAME_AND_INDEX {
const char *name;
unsigned int index;
};
and the fndNELEM(array) macro can be used to conveniently pass
to the fndNAME_AND_INDEX object the size of the table.
fndNAME_MAP(fndNAME_AND_INDEX *array, unsigned int nelem);
The constructor gets a pointer to an array of fndNAME_AND_INDEX
objects, containing the definitions of the couples (index,name)
and the number of elements in the array.
For performance considerations, the array is NOT copied internally,
so it is required that the given array is not deallocated for
at least the whole lifetime of the fndNAME_MAP.
const char *String(unsigned int index) const;
Given the index, returns the corresponding string (or NULL
if not found).
int Index(const char *string) const;
Given the string, returns the corresponding index (an unsigned int)
or -1 if not found.
static int compString(const void *, const void *);
static int compIndex(const void *, const void *);
String and index comparison functions.
The search in the array is implemented by calling the standard
POSIX lfind() function, that requires a comparison function.
fndNAME_AND_INDEX *data;
Pointer to the external array of fndNAME_AND_INDEX structures
unsigned int nelem;
Number of elements in the array.
fndNELEM(array)
Convenience macro to calculate the number of entries
in a statically allocated array.
#include "fndNAME_MAP.h"
fndNAME_AND_INDEX testMap[] = { {"CTR1",2},
{"CTR2",4},
{"AAABBB",0},
{"ABABBB",10},
{"G",3} };
fndNAME_MAP testClass(testMap, fndNELEM(testMap));
int main (int, char *[])
{
int index;
const char *string;
index = testClass.Index("ABABBB");
index = testClass.Index("CTR1");
index = testClass.Index("NOTEXIST"); // Not exist
string = testClass.String(0);
string = testClass.String(3);
string = testClass.String(10); // Not exist
return(EXIT_SUCCESS);
}
This is the base class for the whole fnd library.
All classes in the library are derived from this one.
This man page contains also a basic description of general features
provided by the class library as a whole.
All objects handled by container classes must be instances of
subclasses of fndOBJECT.
The "OBJECT" root class, from which all other classes are hierarchically
derived, is typical of many generic foundation libraries in C++
and is the foundation of the inheritance scheme in many other OO languages
like SmallTalk or Java.
A complete fndOBJECT subclass must implement all the compulsory methods,
as described later on, possibly using the provided convenience macros.
fndOBJECT();
fndOBJECT( fndOBJECT& );
virtual ~fndOBJECT();
virtual void ForEach( iterFuncType, void* ) const;
This method is available to support container classes.
Applies the given function to each contained object, if any.
For a container every contained object is called, recursively
up to when a leaf object is found. In this case
the actual given function is called passing the to it the
object and the user given parameter.
virtual hashValueType HashValue() const;
Returns an hash value to identify the object
The default implementation just return the object's address.
virtual int IsSortable()const;
Returns TRUE if the object is an instance of a subclass of fndSORTABLE
virtual int IsSubclassOf(classType toTest) const;
Returns TRUE if the object is of a subclass of the specified class.
virtual int IsAssociation()const;
Returns TRUE if the object is an instance of a subclass of fndASSOCIATION
virtual const fndOBJECT &FirstThat( condFuncType, void* )const;
virtual const fndOBJECT &LastThat( condFuncType, void* )const;
This methods are available to support container classes.
In a container it applies the given function to all the contained
objects, recursively up to when a leaf object is found. In this case
the actual given function is called passing the to it the
object and the user given parameter. The first(last) object
for wich the condition is satisfied is returned back.
void *operator new( size_t s );
void operator delete( void* );
Overloaded implementation for the new() and delete() operators
*=====================================================*
* These methods MUST be overloaded for each sub-class *
* Please, use the provide macros: *
* fndStdObjectDef() fndStdObjectSource() *
*=====================================================*
static fndOBJECT *CreateNew();
Creates a new instance of the class itself.
The CreateNew() method CANNOT BE INLINE
virtual classType IsA() const;
Returns the class of the object, using a unique identifier
virtual int IsEqual( const fndOBJECT& )const;
Returns TRUE if the object is equal to the given one, i.e.
if they are at the same memory address.
virtual char *NameOf() const;
Returns the name of the object. The default implementation
returns the name of the class of the object
*=====================================================*
* These methods MUST be overloaded for each sub-class *
* only if they are used for the subclass itself *
*=====================================================*
virtual void PrintOn( ostream& outputStream)const;
Prints the content of the object on the given output stream.
Must be overloaded in sub classes to provide a meaningfull
behaviour.
static fndOBJECT *ZERO; Static variable to identify a pointer to
a non existing object, like in case
of search failure for an item inside a container
The following special macros are used while defining fndOBJECT subclasses
to make easier the implementation of standard methods that must be
overloaded in any class.
#define fndStdObjectDef(Class, ParentClass)
#define fndStdObjectSource(Class, ParentClass)
They get as parameter the name of the class we are defining and the
name of the parent class.
fndStdObjectDef() must be called inside the class definition
at the end of any scope section
fndStdObjectSource() must be called inside the file containing the
source code for the class at any place.
The macros provide a standard implementation for the following
methods:
CreateNew()
IsA()
IsSubclassOf()
NameOf()
fndOBJECT_CLASS Is a unique identifier for the class that
can be used whenever a classType is required
to identify the class.
Every subclass should have a define like this to identify
itself, called <className>_CLASS and with the following
structure:
#define <className>_CLASS (classType) <className>::CreateNew
NOOBJECT Is a special macro to identify an instance of a
non valid/ non existing object, like in case of search
failure for an item inside a container. It is
defined as *(fndOBJECT::ZERO)
What follows is a list of usefull types defined for the fnd library:
typedef char *caddr_t;
Generic address
typedef unsigned int hashValueType;
An hash value for an object.
typedef unsigned int sizeType;
Defines the size of a storage area.
typedef int countType;
A counter for counting things in the class librery.
typedef void(*iterFuncType )( fndOBJECT&, void* );
Defines a pointer to an iteration function.The iteration
function takes an fndOBJECT reference and a point
to a list of parameters to the function. The parameter
list pointer may be NULL.
typedef int(*condFuncType )( const fndOBJECT&, void* );
Defines a pointer to a function which implements a conditional
test and returns 0 if the condition was met, non-zero otherwise.
The non-zero values are defined by the individual function.
typedef char Boolean;
A boolean type
typedef fndOBJECT *(*creator )( );
The type to define the prototype of the CreateNew() method
typedef fndOBJECT* func_type();
The type for the prototype of a simple function returning an
object
enum ObjectInit { objectInit };
Enum to implement a trick for selecting special constructors
#define classType caddr_t
classType is a type definition (here implemented as a define)
for a class identifier, i.e. for variables unique to a whole
class and that can be used to uniquely identify the class
of an object.
A comlete fndOBJECT subclass must implement all the compulsory methods.
The asiest way to accomplish this duty is to use the provided
fndStdObjectDef() and fndStdObjectSource() macros.
If this is not done, it a good behaviour in all container classes
cannot be warrantied, in particular for what concern object comparison
operations, like the ones involved in container searching.
This fndPOINTER class provides a wrapper for the pointer fundamental C++
type as a subclass of fndOBJECT.
This is necessary in order to provide the possibility of putting
simple pointers inside containers, for example to build
dynamical arrays (fndARRAY(4)) or lists (fndLIST(4)) of pointer.
A generic pointer is defined in fndOBJECT.h by the typedef caddr_t
The need of providing wrappers for the fundamental types of the
language puts in evidence the main limitation and annoyance of the fnd
containers library: an object can go inside a container ONLY IF it is
an fndOBJECT.
A part from the implementation of the methods defined by the fndOBJECT
class, the fndPOINTER class provides a constructor, an
assignement and a cast to pointer operator that make as much transparent
as possible its usage whenever a normal pointer would be used:
fndPOINTER( const int aPointer=0 );
fndPOINTER &operator =( const fndPOINTER& );
operator const int() const;
The fndPOS_ARRAY class is a subclass of the fnsSORT_ARRAY class
and has all its methods and properties, plus the possibility of explicitly
inserting an fndOBJECT at a specified position, moding the other items
to create space for it is necessary.
virtual void Add( fndOBJECT &obj, int pos);
This is the only new method implemented by the class.
It inserts the given object in the specified position, moving
up one slot all the following objects to create an empty slot, if
necessary.
The fndQUEQUE class implements a simple queue container, i.e. a collection of
fndOBJECT instances where it is possible to insert and extract objects
A simple queue implements the basic Get()/Put() FIFO (First In First Out)
retrieval concept: objects are inserted in the queue from the left side and are
extracted from the queue from the right side.
The fndQUEUE class is implemented by inheriting from the more
general fndDQUEUE class and:
- adding Get()/Put() FIFO methods
- hiding the double queue insertion and extraction
methods.
The internal machinery is exactely the same and only the public
interface changes.
A part from an implementation of the pure virtual methods defined in the
fndCONTAINER(4) class, the following public methods are provided:
fndOBJECT &Get() { return fndDEQUE::GetRight(); }
Returns a reference the first inserted fndOBJECT in the queue
and remove it from the queue itself
void Put(fndOBJECT &o) { fndDEQUE::PutLeft( o ); }
Insert the given fndOBJECT at the end of the queue
fndOBJECT &GetLeft()
fndOBJECT &GetRight()
void PutLeft( fndOBJECT &o )
void PutRight( fndOBJECT &o )
These method are just made private to hide them from fndQUEUE
users.
The fndSET class implements the concept of set, i.e. a collection that
can contain only one instance of a given fndOBJECT(4).
This is the only difference between the fndSET and the fndBAG(4), that can
contain multiple instances of the same object.
The interface of the two classes is identical and the only implementation
difference is in the Add() method, that has been rewritten in order
to refuse adding an fndOBJECT(4) to the fndSET if it already exist.
The fndSORT_ARRAY class implements a dynamical array where the
elements, that MUST be subclasses of fndSORTABLE(4) are always
kept in order on the basis of the order relation defined defined
by the specific subclass of fndSORTABLE used to fill the array.
This means that whenever an fndSORTABLE(4) x is added to the
array, it is inserted in the correct position (after
all elements for which a < x and before all elements for which
x <= b).
If an element is detached from the array, the hole is filled
moving back all the following elements.
This class is very convenient to keep orderer collections of
objects, while beeing able of accessing them via the simple []
operator.
At the same time, the user as to pay attention to the fact that
after an Add()/Detach() operation the indexes of elements
can in general be different because of insertion or deletion
of elements.
The interface of the class is exactely the same of the
fndABST_ARRAY(4) class and the implementation
only overwrites some methods to provide the specific
algorithms.
The fndSORTABLE class implements the basic interface for
all classes where it is defined an order relation between
instances, i.e. for which it is possible to say that one instance
"is less than" another instance or not and that can be sorted.
Typical cases are all kind of numbers (fndINT(4), fndFLOAT(4)) or
strings, that can have a lexicographic order (fndSTRING(4)).
It just inherits all the methods of the base class fndOBJECT(4),
but overwrite the IsSortable() method so that it always returm TRUE.
Subclasses HAVE TO provide an implementation for the IsLessThan().
method that defines the older relation between instances.
This method should have been a pure virtual method, but this was
not possible for implementation reasons.
The fndSORTABLE.h include file provides also generic comparison
operators.
virtual int IsLessThan( const fndOBJECT& ) const;
Every subclass has to provide an implementation for this method,
that defines the order relation.
virtual int IsSortable() const;
Returns always TRUE
inline bool operator < ( const fndSORTABLE& test1, const fndSORTABLE& test2 )
inline bool operator > ( const fndSORTABLE& test1, const fndSORTABLE& test2 )
inline bool operator >=( const fndSORTABLE& test1, const fndSORTABLE& test2 )
inline bool operator <=( const fndSORTABLE& test1, const fndSORTABLE& test2 )
These operators allow to compare two fndSORTABLE objects, just as if
they were fundamental C++ types.
The fndSTACK class implements the fundamental concept of a
stack container, the basic Last In First Out (LIFO) data handling
algorithm.
The basic Push() and Pop() methods are used to add elements on
top of the stack and to extract them from the stack, while the Top()
methods allows just to inspect the top of the stack without detaching
the element from the stack itself.
A part from these methods, it just provides a proper implementation
of the methods defined in the fndCONTAINER(4) base class.
void Push( fndOBJECT & );
Add the given fndOBJECT(4) at the top of the fndSTACK
fndOBJECT &Pop();
Extract the first fndOBJECT(4) from the top of the fndSTACK
fndOBJECT &Top() const;
Inspect the top of the fndSTACK, i.e. return a reference
to the fndOBJECT(4) at the top of the stack, but does not detach
it.
The fndSTRING class provides a very convenient interface for
character strings and a wrap-around to character arrays to
allow the usage of strings in fndCONTAINERs.
One of the most important characteristics of the class is
that it handles dynamical size strings, i.e. it is not
necessary to allocate in advance the memory necessary
to store all the characters that will go in the string,
but memory is allocated dynamically and transparently
whenever needed.
At the time, the fndSTRING behaves as much as possible
as a char[] and can be used transparently almost
everywhere a char[] would be used. Remember anyway that:
- the fndSTRING class can be assigned to a
const char* and not to a char*,
i.e. the pointer to char* returned is constant
and cannot be used to modify the string.
- Some types of assignment can lead to ambiguous
expressions and can be necessary to explicitly
cast the fndSTRING to a (const char*) to disambiguate
the expression.
It is a subclass of fndSORTABLE(4) because it implementes a
lexicographic order relation.
It implements a whide set of methods on top of the basic features
defined in the base classes fndOBJECT(4) and fndSORTABLE(4).
fndSTRING( const char* source = NULL );
This constructor creates an instance of fndSTRING and, if
source != NULL, initialyses it with the passed C character
string. It is used transparently whenever a char* is
passed to a function that requires an fndSTRING as argument.
fndSTRING( const fndSTRING& );
Copy contructor
fndSTRING(char fillCh, unsigned int count);
This constructor build a new fndSTRING object initialyzed
with count characters and filled with the fillCh character.
sizeType GetLen() const;
Returns the number of allocated bytes (including '\0').
This is NOT the lenght of the string in characters, that could
be smaller, but the real number of allocated bytes.
fndSTRING& operator =( const fndSTRING& );
Assignement operator.
Thanks to the conversion constructor, it works also
with standard C strings.
operator const char*() const;
Returns the fndSTRING contents as a CONSTANT C string.
Allows to transparently use fndSTRING instances whenever a
const char[] would be used.
Pay attention to the fact that this pointer could change after
other calls to fndSTRING methods and cannot be stored
and reused and the string cannot be directly modified
using this pointer.
If this is necessary, the pointer must be used to copy the
string somewhere else.
friend fndSTRING operator + (const fndSTRING & str1, const fndSTRING & str2);
void operator += (const fndSTRING& str);
Concatenation operators.
With this operators a string can be easily concatenated to another:
fndSTRING str = "AAA" + "BBB" + str2;
str += "CCC";
bool operator < (const fndSTRING & str);
bool operator > (const fndSTRING & str);
bool operator <= (const fndSTRING & str);
bool operator >= (const fndSTRING & str);
bool operator == (const fndSTRING & str);
bool operator != (const fndSTRING & str);
String comparison methods
int Compare(const fndSTRING & str, fndSTR_CMP_MODE caseChk= fndSTR_IGNORE);
Compare the fndSTRING with another fndSTRING.
By default ignores the case.
If caseChk==fndSTR_SENSITIVE, string comparison is case sensitive.
int Find(const fndSTRING & str, unsigned int *pos,
fndSTR_CMP_MODE caseChk = fndSTR_IGNORE);
Searches inside an fndSTRING a substring, by default case
insensitive, and returns the starting position of the substring
in the pos parameter.
The return value is TRUE is found, FALSE if not found.
void Delete(unsigned int pos, unsigned int count);
Deletes the characters starting from position pos
for the number of characters defined by the parameter count.
void Insert(unsigned int pos, char ch);
void Insert(unsigned int pos, const fndSTRING & str);
Insert a character or a substring starting from the given
position.
fndSTRING SubStr(unsigned int start, unsigned int count);
Returns a substring with the characters startign from
start position and containing as many characters as defined
by count.
char operator [] (unsigned int pos);
Sub-script operator: returns the character at given position
like with a normal character array.
fndSTRING ToUpper();
fndSTRING ToLower();
Returns a new string converting to upper or lower case
sizeType len;
Number of allocated bytes for the string
char *theString;
Actual string storage. Dynamically allocated and reallocated
as needed.
These are some simple but usefull convenience string handling functions,
that can be used both by C and C++ programs (but for C++ programs
it is suggested to make use of the fndSTRING(4) class.
int fndStrcmp(const char *s1, const char *s2, enum fndSTR_CMP_MODE caseChk);
Compares two strings.
It is similar to the standard C function strcmp() but le last parameter
enum fndSTR_CMP_MODE caseChk allows to perform case insensitive comparisons.
char *fndStrlower(char *str);
char *fndStrupper(char *str);
Convert the given string to lower or upper case.
 Quadralay Corporation http://www.webworks.com Voice: (512) 719-3399 Fax: (512) 719-3606 sales@webworks.com |
| |
|
|
|
