Sample code -- Iterator class definition (C++)


This code provides the declaration of the Iterator class which is a parent class for all iterators. The Iterator class is an abstract template class and provides a much more general iterator than is found in common practice. Implementation of some methods are provided even though not shown here. Other than minor formatting for HTML presentation, this code is exactly as found in the original source code.


// Copyright (c) 1993..1996 by Michael Lee Finney.  All rights reserved.

/* IteratorOperatorSignatures()
 *
 *    This macro expands the operator signatures which must be redefined
 * for each Iterator subclass, but which have an implementation which
 * varies only the class name.  These operators cannot be placed in the
 * Iterator class because they return instances of the Iterator subclass
 * by value.
 */

#define IteratorOperatorSignatures(ClassName)          \
   ClassName operator+(ClassName & x, signed4 y);      \
   ClassName operator+(signed4 x, ClassName & y);      \
   ClassName operator++(ClassName & x, signed dummy);  \
   ClassName operator-(ClassName & x, signed4 y);      \
   ClassName operator--(ClassName & x, signed dummy)


#pragma pack(1)

/* Iterator
 *
 *    An iterator is formally defined as a tuple...
 *
 *       <L,U,I,P,r,p,O,M,m,A,X,R,D>
 *
 *    where...
 *
 *       L  is the greatest lower bound of the iterator.  If the iterator
 *          is infinite to the left, L is the first negative transfinite 
 *          ordinal -N (aleph).
 *
 *       U  is the least upper bound of the iterator.  If the iterator 
 *          is infinite to the right, U is the first positive transfinite
 *          ordinal N (aleph).
 *
 *       I  is the open interval (L,U) over integers.  I is called the 
 *          indexing set of the iterator.  Notice that I does not contain
 *          either the greatest lower bound or the least upper bound.
 *
 *       P  is the open interval (L-1,U+1) over integers.  If L and U are,
 *          respectively, -N (the first negative transfinite ordinal) and
 *          N (the first positive transfinite ordinal) then P = I.  The
 *          elements of P are called the positions of the iterator.
 *
 *       r  is an element of P and is called the initial position.
 *
 *       p  is an element of P and is called the distinguished position.
 *          Immediately following creation of the iterator and immediately
 *          after the iterator has been reset, p = r.
 *
 *       O  is a set of objects.
 *
 *       M  is the set of positions at which m is defined.  It contains
 *          p when p is an element of I and is a subset of I.
 *
 *       m  is a map from M onto O, m:M->O.
 *
 *       A  is the set of accessible positions.  It always contains p
 *          and is a subset of P.
 *
 *       X  is the set of extensible positions.  It is a subset of P.
 *
 *       R  is the set of replaceable positions.  It is a subset of I.
 *
 *       D  is the set of deletable positions.  It is a subset of I.
 *
 *    An iterator is a sequence if both M = I and A = P.  It is a
 * temporal sequence if M = {p} and A = {p, p+1} (or {p} if p = U).
 *
 *    If the number of elements in the iterator exceeds either the minimum
 * or the maximum value which can be represented by a primitive numeric
 * data element, then the value of origin() and position() are undefined.
 * Further, if the number of elements exceeds the maximum value which can
 * be represented by a primitive signed data element, then the value of
 * distance() is undefined.
 *
 *    This is a problem unless an unbounded numeric data element is used.
 * Unfortunately, C++ does not provide such a primitive type and the
 * efficiency of most iterators would be seriously impaired were such a
 * type to be defined.  The correct approach is to return a reference to
 * a value which is the base of all numeric values, so that the actual
 * return type could be a simple numeric element or an unbounded numeric
 * value, as needed.  But C++ does not consider the primitive data types
 * to be part of the class hierarchy so this approach cannot be used.
 *
 *    Since most or all iterators for which origin(), position() and 
 * distance() are important are not infinite and most or all finite 
 * iterators have far fewer elements than the above limits, it has been
 * elected to return a primitive data type.  This affects other methods
 * which accept a position as a parameter as well.
 *
 *    Like a collection, an iterator does not own the objects in the
 * iterator.
 *
 * The minimum set of methods which must be overridden are...
 *
 *    signed4           origin()
 *    signed4           position()
 *    bool              atLowerBound()
 *    bool              atUpperBound()
 *    bool              isAccessibleAt(signed4 i)
 *    void              moveTo(signed4 i)
 *    bool              isValueAt(signed4 i)
 *    T *               valueAt(signed4 i)
 *    ClassName const & operator=(ClassName const &)
 *                      ClassName()
 *                      ClassName(ClassName const &)
 *                     ~Classname()
 *
 *    If the iterator is to be used with operators, the following set
 * of methods must be also defined (because they must return a ClassName
 * instance by value)...
 *
 *    ClassName operator+(ClassName & x, signed4 y);
 *    ClassName operator+(signed4 x, ClassName & y);
 *    ClassName operator++(ClassName & x, signed dummy);
 *    ClassName operator-(ClassName & x, signed4 y);
 *    ClassName operator--(ClassName & x, signed dummy);
 *
 * the IteratorOperatorSignatures() macro and IteratorOperators() macro
 * can be used to, respectively, declare and define these methods.
 */

SubClassTypeDataTemplate(class, T, Iterator, LinearOrder);
template <class T> class Iterator isa LinearOrder is
      SubClassMethodsTemplate(class, T, Iterator, LinearOrder);
   private:
   protected:
   public:

      /*
       *    This group of methods handle comparisons between iterators.
       * Iterators which are comparable are linearly ordered and support
       * a distance() method.  An iterator is always comparable to itself.
       * The isComparable() method must be overridden if an iterator is
       * to be comparable to any iterator other than itself.
       */

      virtual bool      isComparable(Order const & x) const;

      virtual signed    compare(LinearOrder const & x) const;
      virtual unsigned4 distance(Iterator<T> const & x) const;
      virtual bool      equal(Void const & x) const;
      virtual unsigned4 equalityHash() const;
      virtual bool      greater(PreOrder const & x) const;
      virtual bool      greaterOrEqual(PreOrder const & x) const;
      virtual bool      less(PreOrder const & x) const;
      virtual bool      lessOrEqual(PreOrder const & x) const;
      virtual bool      notEqual(Void const & x) const;
      virtual bool      precede(Order const & x) const;
      virtual bool      unordered(Order const & x) const;

      /*
       *    This group of methods handle queries about the position.
       * The origin(), position(), atLowerBound() and atUpperBound()
       * methods must be overridden.
       */

      virtual signed4 origin() const abstract;
      virtual signed4 position() const abstract;

      virtual bool    atLowerBound() const abstract;
      virtual bool    atUpperBound() const abstract;

      virtual bool    atOrigin() const;

      /*
       *    This group of methods handle "movement" of the iterator.  If
       * the distinguished position can be moved the isAccessibleAt()
       * and moveTo() methods must be overridden.
       */

      virtual bool    isAccessibleAt(signed4 aPosition) const abstract;
      virtual void    moveTo(signed4 aPosition) abstract;

      virtual bool    isAccessible(signed4 i) const;
      virtual void    move(signed4 i);

      virtual void    advance();
      virtual void    retreat();

      /*
       *    This group of methods allow resetting the iterator.  The
       * isResettable() and reset() methods must be overridden if the
       * iterator can be reset.
       */

      virtual bool    isResettable() const;
      virtual void    reset();

      /*
       *    This group of methods handle accessing the elements of
       * an iterator.  The isValueAt() and valueAt() methods must
       * be overridden.
       */

      virtual bool      isValueAt(signed4 aPosition) const;
      virtual T const & valueAt(signed4 aPosition) const;

      virtual bool      isValue(signed4 i) const;
      virtual T const & value(signed4 i) const;

      virtual bool      isValue() const;
      virtual T const & value() const;

      /*
       *    This group of methods handle inserting elements into the
       * iterator.  The isExtensibleAt() and extendAt() methods must
       * be overridden if elements can be inserted into the iterator.
       */

      virtual bool    isExtensibleAt(signed4 aPosition) const;
      virtual void    extendAt(signed4 aPosition, T const * anObject);

      virtual bool    isExtensible(signed4 i = 0) const;
      virtual void    extend(signed4 i, T const * anObject);

      virtual void    extend(T const * anObject);

      /*
       *    This group of methods handle removing elements from the
       * iterator.  The isRemoveableAt() and removeAt() methods must
       * be overridden if elements can be removed from the iterator.
       */

      virtual bool    isRemoveableAt(signed4 aPosition) const;
      virtual void    removeAt(signed4 newPosition);

      virtual bool    isRemoveable(signed4 i = 0) const;
      virtual void    remove(signed4 i = 0);

      /*
       *    This group of methods handle replacing elements in the
       * iterator.  The isReplaceableAt() and replaceAt() methods
       * must be overridden if elements can be replaced in the iterator.
       */

      virtual bool    isReplaceableAt(signed4 aPosition) const;
      virtual void    replaceAt(signed4 aPosition, T const * anObject);

      virtual bool    isReplaceable(signed4 i = 0) const;
      virtual void    replace(signed4 i, T const * anObject);

      virtual void    replace(T const * anObject);

      /*
       *    This group of methods provides operator syntax for frequently
       * used operations.  The operator=() method must be overridden.
       */

      virtual LvIterator<T>       operator*() const;
      virtual Iterator<T> const & operator=(Iterator<T> const & anIterator) abstract;
      virtual LvIterator<T>       operator[](signed4 i) const;
   global
      template <class T> Iterator<T> & operator++(Iterator<T> & anIterator);
      template <class T> Iterator<T> & operator+=(Iterator<T> & xIterator, signed4 yDistance);
      template <class T> signed4       operator-(Iterator<T> & xIterator, Iterator<T> & yIterator);
      template <class T> Iterator<T> & operator--(Iterator<T> & anIterator);
      template <class T> Iterator<T> & operator-=(Iterator<T> & xIterator, signed4 yDistance);
      template <class T> Iterator<T> & operator<<(Iterator<T> & anIterator, T & anObject);
      template <class T> Iterator<T> & operator>>(Iterator<T> & anIterator, T & anObject);

#pragma pack()

#if defined(os2) || defined(pm)
   #elif defined(nt) || defined(win)
      #if !defined(expandIteratorTemplates)
         extern template Iterator<extended>;
         #if defined(_rttiEnabled) && _rttiEnabled
            extern template Iterator<TypeData>;
            #endif
         #endif
   #endif
         

[ Last | Overview | Next ]