Polaris: BaseList Class Reference

BaseList Class Reference

A class to create BaseLists of Listable objects. More...

#include <BaseList.h>

Inheritance diagram for BaseList:

[legend]List of all members.


Public Member Functions
void	_del (LiveWrapper *w)
	This function is used by TypedBaseMap<S,T> so it is public.
	BaseList ()
	BaseList (const BaseList &l)
virtual	~BaseList ()
void	ins (const Listable *new_element, int loc)
	Insert new_element at location loc, where 0 <= loc <= entries() This results in an error if the List is static sized.
virtual void	del (int loc)
	Random Access Delete Delete the Node in position loc where 0 <= loc <= entries()-1 If references to the deleted element exist in RefStructures, the references will now be invalid, making their access illegal.
void	del (Listable &el)
	Delete node 'el'.
Listable *	grab (int loc)
	Random Access Grab Grab (i.e.
Listable *	grab (Listable &el)
	Grab (i.e.
Listable *	modify_and_grab (Listable &el, Listable *replacement)
	Modify the BaseList by grabbing 'el' out of the BaseList and replacing it with 'replacement' in the spot which 'el' had taken in the BaseList.
void	modify (Listable &el, Listable *replacement)
	Modify the BaseList by grabbing 'el' out of the BaseList and replacing it with 'replacement' in the spot which 'el' had taken in the BaseList.
void	modify (int loc, Listable *replacement)
	Modify the list by grabbing the locth element out of the list and replacing it with 'replacement'.
void	ins_before (const Listable new_element, const Listable ref)
	Insert new_element before the reference element 'ref' (if ref == 0, insert at END of BaseList) ref MUST be in the BaseList (this is not necessarily checked).
void	ins_after (const Listable new_element, const Listable ref)
	Insert new_element after the reference element 'ref' (if ref == 0, insert at BEGINNING of BaseList) ref MUST be in the BaseList (this is not necessarily checked).
Listable *	pull (int loc)
	Temporarily remove the locth element from the list so that it can be operated on by assign and replaced.
Listable *	pull (Listable &el)
	Temporarily remove the element el from the list so that it can be operated on by assign and replaced.
Assign< Listable >	assign (int loc)
	Return control of a pulled element to its list in its original position.
Assign< Listable >	assign (Listable &el)
	Return control of a pulled element to its list in its original position.
const Listable *	next_ref (const Listable &el) const
Listable *	next_ref (const Listable &el)
	Return the element after 'el' (return 0 if none).
const Listable *	prev_ref (const Listable &el) const
Listable *	prev_ref (const Listable &el)
	Return the element before 'el' (return 0 if none).
BaseList &	operator= (const BaseList &l)
	Copy operator copies a collection.
void	make_static_list (int static_size)
	Clear the list and set it to a static list of size static_size with all elements invalid.
Friends
class	BaseMap
ostream &	operator<< (ostream &o, const BaseList &l)
	This interface is for testing purposes only.

Detailed Description

A class to create BaseLists of Listable objects.

Polaris C++ VDL

See also:

BaseList.h

BaseList.cc

Overview

The BaseList class creates the underlying structure for lists for the type 'obj' which must be derived from Listable. Since the List is derived from Collection it works with Iterators. When an object is placed into a List, the List assumes ownership of the object and that object can not be placed in any other live structure. This class is not meant to be used directly but is used to build usable structures like List and Set.

Description

The BaseList supports all of the functionality of the structures intended for use by the public, however, since the class is not templatized, it cannot provide all of the error checking facilities which may be desired. Although, all functionality herein is duplicated in the final classes, it is still described here:

If a list is static, its size must remain constant. Thus, calls to either ins or del methods result in errors. If an element is grabbed from a static list, the element's position becomes invalid (a state which can be checked). That position can then be modified to another object which will revalidate it. All modify routines operate on static lists.

Note that Lists are indexed from 0.

These BaseLists provide reference counting so BaseList elements, if deleted or grabbed from the owner list while still being referenced by some reference structures, will become \'invalid\'--a state which can be checked by the ref. structure before any dereferencing takes place.

Assign Operation

assign/pull is designed to allow the functionality of modifying an element of a list to be some function of the old value of that position. In, general: pull() is used to release control of an object without losing its position in the list, assign() is used to give control back to the list.

The 'pull' method removes the specified object from its list (like grab) but maintains it's 'place' in the list. Once an object has been pulled, it is no longer possible to access the List using the pulled object as a reference. Once an object has been pulled it can be modified in any way. Once the modification is complete, the object can be returned to its position in the list using the 'assign' method. The user, however, is responsible for garbage collecting any intermediate forms of the pulled object which may be created. A complete use would be as follows:

           loc = list.index(el);
    
           list.assign(loc) = function( list.pull(loc) )   --or--
           list.assign(el) = function( list.pull(el) )     --or--
                             a combination of the forms....

'function' is simply a funtion which returns the modified value. If the modified value is a different object than the original, function is responsible for garbage collecting the original. In this case, the specified object is pulled from the list, modified somehow by function and the returned value takes it's place in the list.

 "assign" MUST be used as part of an assignment statement *
    
 These functions approximate the functionality of the late
       modify_in_place. *

IMPORTANT

Note:: Due to the order in which C++ evaluates assignment statements, the call:

               list.assign(el) = f(list.pull(el));

will function correctly while

                x = list.pull(el);
                list.assign(el) = f(x);

will result in a run-time error. This is because the left-hand side of an assignment statement is evaluated first so in the first case when 'assign' is called, 'el' is in the list while in the second case it is not. Thus,

 assign(Listable &el) MUST be used on the same line as its
       corresponding pull call *

Hierarchy Structure

Final collections do not actually inherit from BaseList. Instead the final collections simply contain BaseLists. 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

BaseList::BaseList ( ) [inline]

< nothing to do
Definition at line 311 of file BaseList.h.

BaseList::BaseList ( const BaseList & l )

Definition at line 20 of file BaseList.cc.

BaseList::~BaseList ( ) [virtual]

... nothing to do
Definition at line 29 of file BaseList.cc.

Member Function Documentation

void BaseList::_del ( LiveWrapper * w )

This function is used by TypedBaseMap<S,T> so it is public.
... delete first since unlink will deallocate w
Definition at line 312 of file BaseList.cc.
References Collection::_unlink_wrapper(), and Wrapper::delete_object().
Referenced by TypedBaseMap< S, T >::_list_delete().

void BaseList::ins ( const Listable * new_element,

int loc

)

Insert new_element at location loc, where 0 <= loc <= entries() This results in an error if the List is static sized.

Definition at line 116 of file BaseList.cc.
References Collection::_check_subscript(), ins_after(), ins_before(), and Wrapper::object().
Referenced by Set< T >::ins(), List< T >::ins(), List< T >::ins_first(), List< T >::ins_last(), List< T >::List(), Set< T >::modify(), and operator=().

void BaseList::del ( int loc ) [virtual]

Random Access Delete Delete the Node in position loc where 0 <= loc <= entries()-1 If references to the deleted element exist in RefStructures, the references will now be invalid, making their access illegal.
If the list is static, an error is raised.
Implements Collection.
Definition at line 173 of file BaseList.cc.
References Collection::_check_subscript().
Referenced by Set< T >::_del(), Set< T >::_modify(), Set< T >::del(), and List< T >::del().

void BaseList::del ( Listable & el )

Delete node 'el'.
el MUST be in the BaseList (this is not necessarily checked). If the list is static a error is raised. If references to the deleted element exist in RefStructures, the references will now be invalid, making access illegal.
Definition at line 133 of file BaseList.cc.
References Collection::_unlink_wrapper(), LiveWrapper::delete_object(), and Collection::get_wrapper().

Listable * BaseList::grab ( int loc )

Random Access Grab Grab (i.e.
unlink and return the pointer to, but DO NOT delete) the element at location loc. If references to the grabbed element exist in RefStructures, the references will now be invalid, making access illegal. If the list is static the locth node will become invalid.
Definition at line 163 of file BaseList.cc.
References Collection::_check_subscript().
Referenced by TypedBaseMap< S, T >::_list_remove(), Set< T >::grab(), and List< T >::grab().

Listable * BaseList::grab ( Listable & el )

Grab (i.e.
unlink and return the pointer to, but DO NOT delete) the element 'el', which MUST be in the BaseList (this is not necessarily checked). If references to the grabbed element exist in RefStructures, the references will now be invalid, making access illegal. If the list is static el becomes invalid.
Definition at line 147 of file BaseList.cc.
References Collection::_unlink_wrapper(), Collection::get_wrapper(), and LiveWrapper::loose_object().

Listable * BaseList::modify_and_grab ( Listable & el,

Listable * replacement

) [inline]

Modify the BaseList by grabbing 'el' out of the BaseList and replacing it with 'replacement' in the spot which 'el' had taken in the BaseList.
A pointer to 'el' is returned, and the user becomes responsible for deleting 'el'. If 'el' is the same element as 'replacement', a run-time error message occurs.
Definition at line 369 of file BaseList.h.
References Collection::get_wrapper(), and LiveWrapper::modify_and_grab().
Referenced by List< T >::modify_and_grab().

void BaseList::modify ( Listable & el,

Listable * replacement

) [inline]

Modify the BaseList by grabbing 'el' out of the BaseList and replacing it with 'replacement' in the spot which 'el' had taken in the BaseList.
'el' is deleted. 'el' MAY be the same element as 'replacement'. In this case, the call is simply ignored.
Definition at line 379 of file BaseList.h.
References Collection::get_wrapper(), and LiveWrapper::object().
Referenced by Set< T >::_modify(), Set< T >::ins(), and List< T >::modify().

void BaseList::modify ( int loc,

Listable * replacement

)

Modify the list by grabbing the locth element out of the list and replacing it with 'replacement'.
If the locth element is valid, it is deleted, if it is not valid, 'replacement' takes the locth position. 'el' MAY be the same element as teh locth element. In this case, the call is simply ignored. This is the only method of revalidating invalid elements.
Definition at line 183 of file BaseList.cc.
References Collection::_check_subscript(), Wrapper::next_ref(), and Wrapper::object().

void BaseList::ins_before ( const Listable * new_element,

const Listable * ref

)

Insert new_element before the reference element 'ref' (if ref == 0, insert at END of BaseList) ref MUST be in the BaseList (this is not necessarily checked).
This is illegal for static lists.
Definition at line 226 of file BaseList.cc.
References Collection::get_wrapper(), Wrapper::next(), Wrapper::next_ref(), Wrapper::object(), Wrapper::prev(), Wrapper::prev_ref(), Wrapper::ref_dec(), and Wrapper::ref_inc().
Referenced by ins(), ins_after(), and List< T >::ins_before().

void BaseList::ins_after ( const Listable * new_element,

const Listable * ref

)

Insert new_element after the reference element 'ref' (if ref == 0, insert at BEGINNING of BaseList) ref MUST be in the BaseList (this is not necessarily checked).
This raises an error in static lists.
Definition at line 290 of file BaseList.cc.
References ins_before(), next_ref(), and Wrapper::object().
Referenced by ins(), and List< T >::ins_after().

Listable * BaseList::pull ( int loc ) [inline]

Temporarily remove the locth element from the list so that it can be operated on by assign and replaced.
The pulled element must be replaced using an assign call which must be on the same line. See detailed description in the above section "Assign Operation".
Definition at line 389 of file BaseList.h.
References Collection::_check_subscript().
Referenced by List< T >::pull().

Listable * BaseList::pull ( Listable & el ) [inline]

Temporarily remove the element el from the list so that it can be operated on by assign and replaced.
The pulled element must be replaced using an assign call which must be on the same line. See detailed description in the above section "Assign Operation".
Definition at line 397 of file BaseList.h.
References Collection::get_wrapper(), LiveWrapper::loose_object(), and Listable::pulled().

Assign< Listable > BaseList::assign ( int loc )

Return control of a pulled element to its list in its original position.
The assign call must be on the same line as the pull operation. See detailed description in the above section "Assign Operation".
Definition at line 321 of file BaseList.cc.
References Collection::_check_subscript(), Wrapper::next_ref(), Wrapper::object(), ProtoWrapper::object_address(), Wrapper::prev_ref(), and sub().
Referenced by List< T >::assign().

Assign< Listable > BaseList::assign ( Listable & el )

Return control of a pulled element to its list in its original position.
The assign call must be on the same line as the pull operation. See detailed description in the above section "Assign Operation".
Definition at line 351 of file BaseList.cc.
References Collection::get_wrapper().

const Listable * BaseList::next_ref ( const Listable & el ) const [inline]

Definition at line 317 of file BaseList.h.
References Collection::get_wrapper(), Wrapper::next_ref(), and Wrapper::object().
Referenced by BaseMap::_insert_after(), ins_after(), and List< T >::next_ref().

Listable * BaseList::next_ref ( const Listable & el ) [inline]

Return the element after 'el' (return 0 if none).

Definition at line 330 of file BaseList.h.
References Collection::get_wrapper(), Wrapper::next_ref(), and Wrapper::object().

const Listable * BaseList::prev_ref ( const Listable & el ) const [inline]

Definition at line 343 of file BaseList.h.
References Collection::get_wrapper(), Wrapper::object(), and Wrapper::prev_ref().
Referenced by List< T >::prev_ref().

Listable * BaseList::prev_ref ( const Listable & el ) [inline]

Return the element before 'el' (return 0 if none).

Definition at line 356 of file BaseList.h.
References Collection::get_wrapper(), Wrapper::object(), and Wrapper::prev_ref().

BaseList & BaseList::operator= ( const BaseList & l )

Copy operator copies a collection.
If the LHS list is static, the RHS list must be of equal size or smaller. If both lists are static, invalid nodes are copied.
Definition at line 77 of file BaseList.cc.
References Collection::clear(), BaseIter::current(), BaseIter::current_valid(), ins(), Listable::listable_clone(), BaseIter::modify(), BaseIter::next(), STOP_ON_GHOSTS, and BaseIter::valid().

void BaseList::make_static_list ( int static_size )

Clear the list and set it to a static list of size static_size with all elements invalid.
... gain ref from _first and _last
... Insert at end
... new last gains ref
... old last looses ref
Definition at line 35 of file BaseList.cc.
References Collection::clear(), Collection::fix_size(), Wrapper::next(), Wrapper::object(), Wrapper::prev(), Wrapper::prev_ref(), Wrapper::ref_dec(), and Wrapper::ref_inc().
Referenced by List< T >::List(), and List< T >::make_static_list().

Friends And Related Function Documentation

friend class BaseMap [friend]

Definition at line 177 of file BaseList.h.

ostream& operator<< ( ostream & o,

const BaseList & l

) [friend]

This interface is for testing purposes only.

Definition at line 14 of file BaseList.cc.

The documentation for this class was generated from the following files:

Fri Mar 25 23:06:58 2005