Polaris: Iterator.h Source File

Iterator.h Go to the documentation of this file. /// /// #ifndef _ITERATOR_H #define _ITERATOR_H /// #include <stdlib.h> /// #include "Assign.h" #include "BaseIter.h" #include "TypedCollection.h" #include "ghost_enum.h" /// #include "../macros.h" /// #define CLEAN_ITERATOR 1 /* */ /// /// \class Iterator /// \brief /// Iterator class that works on various Collection-related classes. /// /// These Iterators can operate on any structure derived from Collection /// (which doesn't violate a couple of simple rules discussed at /// the end). An Iterator declared to be of type T can iterate over /// any of Collection structure also of type T. A single Iterator /// can also be used to Iterate over multiple Collection-classes /// as long as they are all of type T. That is, an Iterator<Expression>, /// ExIter, can Iterate over a Set<Expression>, then a List<Expression> /// and then a RefList<Expression>. /// /// Note that in the following, if _last_elem_ptr comes before _first_elem_ptr /// in the list, the iteration space will be empty /// /// Declare an iterator: /// \code /// Iterator<T> Li = some_coll; /// /// (will iterate from the first to the last elements in the list. /// Note when previously declared iterators are assigned to a /// different list, they loose all of there specifications /// including the iteration space and the conditional function.) /// /// --or-- /// /// Iterator<T> Li(some_coll) /// (same as above) /// /// --or-- /// /// Iterator<T> Li(some_coll, first_elem_ptr, last_elem_ptr); /// (will iterate from first_elem_ptr to last_elem_ptr, inclusive) /// /// --or-- /// /// Iterator<T> Li(some_coll, cond_proc, extra_data); /// (will iterate only over those (in order) where the call /// (*cond_proc)(Li.current(), extra_data) returns non-zero) /// /// --or-- /// /// Iterator<T> Li(some_coll, first_elem_ptr, last_elem_ptr, /// cond_proc, extra_data); /// (will iterate only over those (in order) from first_elem_ptr to /// last_elem_ptr where the call (*cond_proc)(Li.current(), extra_data) /// returns non-zero) /// \endcode /// /// Example: /// /// \code /// Iterator<IntElem> Li(some_coll, first_ptr, last_ptr); /// /// while (!Li.end()) { /* or use valid() */ /// cout << Li.current() << ", "; /// if (f(Li.current())) /// some_coll.del(Li.current()); /// Li.next(); /* or use ++Li */ /// } /// \endcode /// /// Resetting the iterator to the start of the subrange: /// \code /// Li.reset() /// \endcode /// /// \endcode /// \section List List Modifications /// /// This implementation works with the reference counting /// scheme of Collections. Thus, it is not possible for an /// element of a Collection to be deleted out from under /// an iterator. It is possible, however, for the current() /// node to suddenly become invalid--that is for the object /// suddenly being made inaccessable, turning the current /// node into a ghost-node. It is illegal to try to access /// the current node if it is a ghost-node. This can be /// checked by calling current_valid(). /// /// Ghost nodes can only be encountered in live structures by /// loosing ownership of the current node, but they are more /// frequent in reference structures. If an object is /// deleted from a live structure, references to it will /// remain. These, too, become "ghost-nodes". /// By default, ghost-nodes are skipped over by the iterator. /// For example, all of the Iterators described above skip /// over ghost-nodes. However, if an iterator is declared as /// the default, it is still possible to check for ghost nodes /// within the iteration space /// by calling next() and prev() using the argument: /// next(STOP_ON_GHOSTS) --or-- prev(STOP_ON_GHOSTS) /// /// Also, it is possible to declare an iterator which will /// always stop on the ghost nodes. This is done by passing /// a flag in the constructor after the name of the /// list. This can be done as follows: /// /// \code /// Iterator Li<type>(some_collection, STOP_ON_GHOSTS) /// /// --or-- /// /// Iterator Li<type>(some_collection, STOP_ON_GHOSTS, /// first_elem_ptr, last_elem_ptr); /// (will iterate from first_elem_ptr to last_elem_ptr, including ghosts) /// \endcode /// /// If the iterators are declared with this flag, ++ and -- /// will automatically stop on ghost-nodes. next() and prev(), /// however, will still stop on ghost-nodes only if they have /// a positive flag. The general rule is /// that the ++ and -- operators behave according to how the /// Iterator was declared, while next and prev behave according to /// whether they have an argument. /// /// The iterator does not communicate with the collection /// which it is iterating over except in the form of /// indicating references. However, the Collection must /// adhere to some behavior rules in order for the iterators /// to work properly. Specifically, when an element is /// removed from the collection Collection::_unlink_wrapper() /// should be called to do the unlinking. The iterator /// depenends on the fact that an unlinked wrapper\'s next /// and prev fields are left untouched until the wrapper /// deletes itself (which will happen automatically when /// its ref count is 0). The iterator depends on these /// ghost-nodes maintaining their contact with the Collection. /// /// It should be noted that each Collection-based structure /// which is going to make use of iterators must have its own /// set of constructors within the ITerator class. /// template <class T> class Iterator { protected: BaseIter _iter; public: INLINE Iterator( ); INLINE Iterator(const TypedCollection<T> &l, const T *first_elem = 0, const T *last_elem = 0, cond_proc func = 0, void *extra_data = 0); INLINE Iterator(const TypedCollection<T> &l, cond_proc func, void *extra_data = 0); INLINE Iterator(const TypedCollection<T> &l, iter_option option, const T *first_elem = 0, const T *last_elem = 0); INLINE Iterator(const TypedCollection<T> *l); INLINE Iterator<T> & operator = (const TypedCollection<T> &list); INLINE Iterator(const Iterator<T> &other); ///< This method copies the entire state (including current element) ///< of the iterator. If you don't like this, then immediately follow ///< this constructor with a call to reset() ~Iterator(); INLINE Iterator<T> & operator = (const Iterator<T> &other); ///< This method copies the entire state (including current element) ///< of the iterator. If you don't like this, then immediately follow ///< this constructor with a call to reset() INLINE void reset(); ///< Go back to the beginning of the iteration space INLINE void set_to_last(); ///< Set the iterator to the last value ///< Useful if you need to iterator backwards INLINE void next(iter_option option = STOP_ON_GHOSTS); ///< go to the next valid element, or if stop_at_ghosts ///< to the next element INLINE void operator++ (); ///< go to previous element according to how Iterator was ///< defined INLINE void prev(iter_option option = STOP_ON_GHOSTS); ///< go to the previous valid element, or if stop_at_ghosts ///< to the previous element INLINE void operator-- (); ///< go to previous element according to how Iterator was ///< defined ///< #ifdef CLEAN_ITERATOR ///< INLINE const T &current() const; ///< // Return a reference to the current element ///< // If there is no current, this results in an error ///< #else INLINE T &current(); ///< Return a reference to the current element ///< If there is no current, this results in an error ///< #endif INLINE Boolean end(); ///< Return true if there no more Nodes to iterate on INLINE Boolean valid(); ///< Equivalent to NOT end() INLINE Boolean current_valid() const; ///< Return true iff valid() would return True AND the current node is ///< still valid. This function will return False even if valid() ///< returns True if the current node is invalid, which will happen if ///< the current node has become a ghost node by being deleted from ///< its Collection. ///< In the event that the current node is invalid, it is ///< a checked run-time error to make a call to current(). ///< However, the valid() method still returns True since ///< the end of the iteration space has not yet been reached. ///< Also, the operator++/--/prev()/next() methods ///< will all work correctly and properly find the next element in ///< the iteration space. ///< If there is any chance that the current element pointed to ///< by a BaseIter can be deleted, both valid() and ///< current_valid() must return True for a call to current() to be ///< acceptable. INLINE Boolean current_invalid() const; ///< Equivalent to ( ! current_valid() ) #ifndef CLEAN_ITERATOR INLINE void modify( const T &el ); ///< Useful for RefMutators ///< This sets the current reference to el and results ///< in an error if called on a live collection. INLINE void modify( T *el ); ///< Useful for Mutators ///< This sets current to el and results in an error ///< if called on a ref-collection. INLINE void modify_in_place(modify_proc mod, void *extra_data GIV(0)); ///< Modify current in place by calling mod(obj, extra_data) where ///< obj is the pointer which owns current. The procedure 'mod' is ///< expected to do it's own garbage collection. ///< The procedure must be of the form: ///< (*mod)(T *& object, void *extra_data) ///< This results in an error if current is invalid or if it is ///< called on a ref-collection. INLINE void del(); ///< Delete the current element, useful for Mutators ///< and RefMutators. This results in an error if the ///< current node has already been deleted. ///< \note current will now be invalid. INLINE T *grab(); ///< Grab the current element, useful for Mutators. ///< Results in an error if called on a ref-collection. ///< \note current will now be invalid. INLINE Assign<T> assign(); INLINE T *pull(); ///< 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. The assign() is meant to be executed first, to ///< capture the original position in the under-lying list for the element. ///< The Assign<T> object returned by assign() stores the position information ///< of the element. Then, pull() is used to remove the element from the ///< list, without losing its position in 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 by assigning to the Assign<T> object ///< (the one created by the original assign() call). ///< ///< The user, of course, is responsible for garbage collecting any ///< intermediate forms of the pulled object which may be created. A ///< complete use would be as follows: ///< ///< \code ///< { ///< Assign<Expression> a = iter.assign(); ///< a = function(iter.pull() ); ///< } // "a" is removed by leaving the scope ///< \endcode ///< ///< 'function' is simply a function 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. ///< #endif }; ///< implementation template <class T> INLINE Iterator<T>::Iterator( ) : _iter( ) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator ctor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> Iterator<T>::~Iterator( ) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator dtor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> INLINE Iterator<T>::Iterator(const TypedCollection<T> &l, const T *first_elem GIV(0), const T *last_elem GIV(0), cond_proc func GIV(0), void *extra_data GIV(0)) : _iter(l._base_collection(), first_elem, last_elem, func, extra_data) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator ctor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> INLINE Iterator<T>::Iterator(const TypedCollection<T> &l, cond_proc func, void *extra_data GIV(0)) : _iter(l._base_collection(), func, extra_data) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator ctor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> INLINE Iterator<T>::Iterator(const TypedCollection<T> &l, iter_option option, const T *first_elem GIV(0), const T *last_elem GIV(0)) : _iter(l._base_collection(), option, first_elem, last_elem) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator ctor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> INLINE Iterator<T>::Iterator(const TypedCollection<T> *l) : _iter(l->_base_collection()) { #ifdef MEMORY_LEAK_PRINT cout << "Iterator ctor: " << this << " : size=" << sizeof(Iterator) << endl; #endif } template <class T> INLINE Iterator<T> & Iterator<T> ::operator = (const TypedCollection<T> &list) { _iter = list._base_collection(); return *this; } template <class T> INLINE Iterator<T>::Iterator(const Iterator<T> &other) : _iter(other._iter) { ///< nothing else to do } template <class T> INLINE Iterator<T> & Iterator<T>::operator = (const Iterator<T> &other) { _iter = other._iter; return *this; } template <class T> INLINE void Iterator<T>::reset() { _iter.reset(); } template <class T> INLINE void Iterator<T>::set_to_last() { _iter.set_to_last(); } template <class T> INLINE void Iterator<T>::next(iter_option option GIV(STOP_ON_GHOSTS)) { _iter.next(option); } template <class T> INLINE void Iterator<T>::operator++ () { _iter.next(_iter.skip_ghosts() ? SKIP_GHOSTS : STOP_ON_GHOSTS); } template <class T> INLINE void Iterator<T>::prev(iter_option option GIV(STOP_ON_GHOSTS)) { _iter.prev(option); } template <class T> INLINE void Iterator<T>::operator-- () { _iter.prev(_iter.skip_ghosts() ? SKIP_GHOSTS : STOP_ON_GHOSTS); } ///< #ifdef CLEAN_ITERATOR ///< ///< template <class T> ///< INLINE const T & ///< Iterator<T>::current() const ///< { ///< return (T &) _iter.current(); ///< } ///< #else ///< template <class T> INLINE T & Iterator<T>::current() { return (T &) _iter.current(); } ///< #endif template <class T> INLINE Boolean Iterator<T>::end() { return _iter.end(); } template <class T> INLINE Boolean Iterator<T>::valid() { return _iter.valid(); } template <class T> INLINE Boolean Iterator<T>::current_valid() const { return _iter.current_valid(); } template <class T> INLINE Boolean Iterator<T>::current_invalid() const { return _iter.current_invalid(); } #ifndef CLEAN_ITERATOR template <class T> INLINE void Iterator<T>::modify(const T &el) { _iter.modify(el); } template <class T> INLINE void Iterator<T>::modify(T *el) { _iter.modify(el); } template <class T> INLINE void Iterator<T>::modify_in_place(modify_proc mod, void *extra_data GIV(0)) { _iter.modify_in_place(mod, extra_data); } template <class T> INLINE void Iterator<T>::del() { _iter.del(); } template <class T> INLINE T * Iterator<T>::grab() { return (T *) _iter.grab(); } template <class T> INLINE Assign<T> Iterator<T>::assign() { Assign<T> a(_iter.assign()); return a; } template <class T> INLINE T * Iterator<T>::pull() { return (T *) _iter.pull(); } #endif #endif

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:57 2005