Polaris: Collection Class Reference

Collection Class Reference

an abstract structure to build related data structures More...

#include <Collection.h>

Inheritance diagram for Collection:

[legend]List of all members.


Public Member Functions
	Collection ()
	Set up an empty Collection.
virtual	~Collection ()
	Delete all elements of Collection which are not aliased.
int	entries () const
	Return the number of entries in the collection.
Boolean	static_size () const
	Is the size of the collection static?
void	fix_size ()
	Make the size constant.
void	unfix_size ()
	Make the size variable.
const Listable &	operator[] (int sub) const
virtual Listable &	operator[] (int sub)
	return object corresponding to subth element where the first element is indexed as 0
const Listable *	first_ref () const
Listable *	first_ref ()
	Return the first element of the collection or NULL.
const Listable *	last_ref () const
Listable *	last_ref ()
	Return the last element of the collection or NULL.
virtual void	clear ()
	Delete all elements of the collection.
virtual void	del (int loc)=0
	Delete the Node in position loc where 0 <= loc <= entries()-1.
virtual Boolean	member (const Listable &el) const
	Check to see if node 'el' is a member of the collection.
virtual int	index (const Listable &el) const
	Check to see if node 'el' is a member of the collection.
Boolean	aliased (const Listable &el) const
	Return true if el is aliased by 1 or more structures--i.e., there are structures refering to el in addition to the owner-structure.
Boolean	valid (const int loc) const
	is the locth element valid?
Boolean	valid (const Listable &l) const
	Is l a valid element owned by the collection? This raises an error if l is not in the Collection, valid or otherwise.
virtual void	print (ostream &out, char *sep) const
	print Collection seperated by sep.
LiveWrapper *	get_wrapper (const Listable &obj) const
	Return obj\'s wrapper.
virtual int	structures_OK () const
	Check the structure of the data for errors or inconsistency Return 0 and print error message if problems found, otherwise return 1 without message.
Protected Member Functions
void	_check_subscript (int sub, int validlo, int valid_hi, char *method_name) const
void	_subscript_error (int sub, int valid_lo, int valid_hi, char *method_name) const
void	_unlink_wrapper (Listable *element)
	Remove element\'s wrapper from it\'s list and adjust _first and _last if necessary.
void	_unlink_wrapper (Wrapper *wrap)
	Remove wrap from it's list as above.
Protected Attributes
Wrapper *	_first
	First and last elements of the list.
Wrapper *	_last
int	_entries
	Number of entries in the list.
Boolean	_static
	Is the size constant?
Friends
class	BaseIter
ostream &	operator<< (ostream &o, const Collection &c)

Detailed Description

an abstract structure to build related data structures

Polaris C++ VDL

See also:

Collection.h

Collection.cc

Overview

This describes the Collection class which can be used as the base for more specific template collections of data. The Collection class can not be used on it's own.

Description

The Collection class is the upper-most class in the Collection hierarchy which includes a wide variety of data structures.

These structures each exist in two forms: ownership and reference. An ownership structure takes control of---and responsibility for---all objects which are inserted into it. Ownership structures insure, through reference counting, that, for instance, objects are not prematurely deleted and that memory is properly deallocated when an object is deleted. Once an object has been placed in an ownership collection, the collection is responsible for its maintenance. An object can only be ``owned'' by one collection. If a collection is required to contain elements already owned by other structures, a reference structure is used. Reference structures do not take ownership of objects and, in fact, require that inserted objects are already owned.

Essentially all of the classes used in Polaris are derived from the class Listable which contributes information necessary to indicate ownership of an object and allows the object to be placed in any collection. However, all of the Collection classes, including the reference collections, are class templates. This templatization allows additional type-checking.

Collections maintain inserted objects through Wrappers. The Wrappers provide all of the functionality needed to manipulate objects, perform all necessary operations and reference counting and allow iterators to function properly. Since the Collection class is the most general, it contains only a list of generic Wrappers. The actual instantiated classes would eventually be further specified as either Live or Reference structures and would contain LiveWrappers or RefWrappers accordingly.

Collections also keep track of invalid elements. An invalid element (sometimes ghost nodes or zombies as they are 'partially alive Listable objects') exists when an element is deleted but there are still references to it. Attempts to access these "ghosts" of old elements result in errors. It is not an error for ghost nodes to exist within a Collection and they can be dealt with by checking an element's validity (ghost nodes return false). However, continued presence of ghost-nodes is usually indicative of poorly designed code or the continued presence of data-structures which should have been deallocated.

The Collection class specifies some of the general principles which are maintained by all Collection classes. For example, Collection specifies the abillity of a derived class to be made static, that Collection classes are intended to be indexed begining with 0 and specifies a number of functions which will be used by all derived classes.

Hierarchy Structure

Specific collections do not actually inherit from Collection. Instead base collections inherit from Collection and these are contained in specific classes. The hierarchy can be represented by:

                        --- :    inherited from relationship
                        -c- :    contained in relationship
   
   
                            Collection
                           /          \                                          //
                          /            \                                         //
                  BaseList   Listable   BaseRefList
                  |  \          |             /  |
                  |   \         |            /   |
                  |    c  TypedCollection   c    |
                  |     \     /     \      /     |
                  |      \   /       \    /      |
                  |      LIST        RefList     |
                  |      Set         RefSet      |
                  c                              c
                  |          Listable            |
                  |             |                |
                  |             |                |
                  |        BaseMapRoot           |
                  |       /           \          |
                  |      /             \         |
                  BaseMap               BaseRefMap
                     |                       |
                     |                       |                            
                TypedBaseMap          TypedBaseRefMap
                  /     \                /         \                             //
                 /       \              /           \                            //
       ProtoDatabase      ProtoMap   ProtoRefMap    ProtoRefDatabase
            /  \           |    |      |     |         |         \               //
           /    \          |    |      |     |         |          \              //
    Database KeyDatabase  Map KeyMap  RefMap KeyMap  RefDatabase RefKeyDatabase

Constructor & Destructor Documentation

Collection::Collection ( ) [inline]

Set up an empty Collection.

Definition at line 266 of file Collection.h.
References _entries, _first, _last, and _static.

Collection::~Collection ( ) [virtual]

Delete all elements of Collection which are not aliased.
May be virtual and overrided by derived classes.
Definition at line 21 of file Collection.cc.
References _static, and clear().

Member Function Documentation

void Collection::_check_subscript ( int sub,

int validlo,

int valid_hi,

char * method_name

) const [inline, protected]

Definition at line 256 of file Collection.h.
References _subscript_error(), and sub().
Referenced by BaseList::assign(), BaseRefList::del(), BaseList::del(), BaseList::grab(), BaseRefList::ins(), BaseList::ins(), BaseList::modify(), operator[](), BaseList::pull(), and valid().

void Collection::_subscript_error ( int sub,

int valid_lo,

int valid_hi,

char * method_name

) const [protected]

Definition at line 163 of file Collection.cc.
References _entries, and sub().
Referenced by _check_subscript().

void Collection::_unlink_wrapper ( Listable * element ) [protected]

Remove element\'s wrapper from it\'s list and adjust _first and _last if necessary.
In order for iterators to work properly, wrappers must be removed using this!
Definition at line 179 of file Collection.cc.
Referenced by BaseRefList::_del(), BaseList::_del(), clear(), BaseList::del(), and BaseList::grab().

void Collection::_unlink_wrapper ( Wrapper * wrap ) [protected]

Remove wrap from it's list as above.
ANOTHER IMPORTANT unlink
Note:
Caution!!! If a wrapper is being unlinked to delete, the order of the operations is very important, since one may result in the object being deleted and causing a crash when the next method is called. BEWARE.

Definition at line 187 of file Collection.cc.
References _entries, _first, _last, Wrapper::next_ref(), Wrapper::prev_ref(), Wrapper::ref_dec(), Wrapper::ref_inc(), and Wrapper::unlink().

int Collection::entries ( ) const [inline]

Return the number of entries in the collection.

Definition at line 274 of file Collection.h.
References _entries.
Referenced by RefSet< T >::any_valid(), Set< T >::empty(), RefSet< T >::empty(), Set< T >::entries(), RefSet< T >::entries(), RefList< T >::entries(), List< T >::entries(), Set< T >::grab(), RefSet< T >::grab(), Set< T >::ins(), RefSet< T >::ins(), RefList< T >::ins_last(), List< T >::ins_last(), and Set< T >::modify().

Boolean Collection::static_size ( ) const [inline]

Is the size of the collection static?

Definition at line 280 of file Collection.h.
References _static.
Referenced by BaseIter::del(), BaseIter::grab(), and List< T >::static_size().

void Collection::fix_size ( ) [inline]

Make the size constant.

Definition at line 286 of file Collection.h.
References _static.
Referenced by List< T >::fix_size(), List< T >::List(), and BaseList::make_static_list().

void Collection::unfix_size ( ) [inline]

Make the size variable.

Definition at line 292 of file Collection.h.
References _static.
Referenced by List< T >::unfix_size().

const Listable & Collection::operator[] ( int sub ) const [inline]

Definition at line 298 of file Collection.h.
References sub().

Listable & Collection::operator[] ( int sub ) [virtual]

return object corresponding to subth element where the first element is indexed as 0

Definition at line 116 of file Collection.cc.
References _check_subscript(), _entries, _first, _last, Wrapper::next_ref(), Wrapper::object(), Wrapper::prev_ref(), sub(), and ProtoWrapper::valid().

const Listable * Collection::first_ref ( ) const [inline]

Definition at line 304 of file Collection.h.
References _first, and Wrapper::object().
Referenced by List< T >::first_ref().

Listable * Collection::first_ref ( ) [inline]

Return the first element of the collection or NULL.

Definition at line 310 of file Collection.h.
References _first, and Wrapper::object().

const Listable * Collection::last_ref ( ) const [inline]

Definition at line 316 of file Collection.h.
References _last, and Wrapper::object().
Referenced by List< T >::last_ref().

Listable * Collection::last_ref ( ) [inline]

Return the last element of the collection or NULL.

Definition at line 322 of file Collection.h.
References _last, and Wrapper::object().

void Collection::clear ( ) [virtual]

Delete all elements of the collection.
... delete (or null) _ptr
... remove object
Definition at line 28 of file Collection.cc.
References _entries, _first, _last, _static, _unlink_wrapper(), Wrapper::delete_object(), Wrapper::is_live_wrapper(), Wrapper::next_ref(), ProtoWrapper::object_address(), Wrapper::ref_dec(), and ProtoWrapper::valid().
Referenced by Set< T >::clear(), RefSet< T >::clear(), RefList< T >::clear(), List< T >::clear(), BaseList::make_static_list(), BaseRefList::operator=(), BaseList::operator=(), and ~Collection().

virtual void Collection::del ( int loc ) [pure virtual]

Delete the Node in position loc where 0 <= loc <= entries()-1.

Implemented in BaseList, and BaseRefList.

Boolean Collection::member ( const Listable & el ) const [virtual]

Check to see if node 'el' is a member of the collection.
Return 0 if the element was not found, else return 1.
Definition at line 65 of file Collection.cc.
References index().
Referenced by Set< T >::_modify(), Set< T >::member(), RefSet< T >::member(), RefList< T >::member(), and List< T >::member().

int Collection::index ( const Listable & el ) const [virtual]

Check to see if node 'el' is a member of the collection.
Return -1 if the element was not found, else return the index of the element. Collections are indexed beginning with 0.
Definition at line 71 of file Collection.cc.
References _first, Wrapper::next_ref(), and ProtoWrapper::object_address().
Referenced by Set< T >::_member(), RefSet< T >::_member(), Set< T >::del(), RefSet< T >::del(), RefList< T >::index(), List< T >::index(), Set< T >::ins(), RefSet< T >::ins(), and member().

Boolean Collection::aliased ( const Listable & el ) const [inline]

Return true if el is aliased by 1 or more structures--i.e., there are structures refering to el in addition to the owner-structure.
Note that this says nothing about whether or not \'el\' is owned by *this collection.
Definition at line 328 of file Collection.h.

Boolean Collection::valid ( const int loc ) const

is the locth element valid?

Definition at line 87 of file Collection.cc.
References _check_subscript(), _entries, _first, Wrapper::next_ref(), and ProtoWrapper::valid().
Referenced by RefSet< T >::any_valid(), RefSet< T >::grab(), RefSet< T >::valid(), RefList< T >::valid(), and List< T >::valid().

Boolean Collection::valid ( const Listable & l ) const

Is l a valid element owned by the collection? This raises an error if l is not in the Collection, valid or otherwise.

Definition at line 102 of file Collection.cc.
References _first, Wrapper::next_ref(), ProtoWrapper::object_address(), and ProtoWrapper::valid().

void Collection::print ( ostream & out,

char * sep

) const [virtual]

print Collection seperated by sep.

Reimplemented in BaseRefList.
Definition at line 142 of file Collection.cc.
References BaseIter::current(), BaseIter::current_valid(), BaseIter::next(), Listable::print(), and BaseIter::valid().
Referenced by Set< T >::print(), List< T >::print(), and BaseRefList::print().

LiveWrapper * Collection::get_wrapper ( const Listable & obj ) const [inline]

Return obj\'s wrapper.
This method is not meant to be used by users of derived Collection classes but it is necessary as it is the only way for derived collections to get at Wrappers.
Definition at line 336 of file Collection.h.
Referenced by BaseList::assign(), BaseList::del(), BaseList::grab(), BaseList::ins_before(), BaseList::modify(), BaseList::modify_and_grab(), BaseList::next_ref(), BaseList::prev_ref(), and BaseList::pull().