UT/UT_Iterator.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Simon Parent
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_Iterator.h (UT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __UT_Iterator__
#define __UT_Iterator__

#include "UT_Notifier.h"

class UT_API UT_IteratorEvent 
{
public:
    enum TYPE {
        ADD,
        REMOVE,
        INVALID,
    };
    TYPE type;

    /// NOTE: the range includes both endpoints.
    int lo, hi;

    UT_IteratorEvent(TYPE type_, int lo_, int hi_) :
        type(type_), lo(lo_), hi(hi_) { }
};

/// Generic iterator class for containers.
///
/// The container class *must* have the following:
///   an "ELEMENT operator(int index) const" method
///   an "int entries() const" method
///   a  "const ELEMENT &null() const" method
///
/// The container class should have the following:
/// a typedef of the form "typedef UT_Iterator<ELEMENT, MyContainer> Iterator;"
/// an iterator(int index = 0) method that returns a new (forward) iterator.
/// optionally also an iteratorReverse(int index = 0) method.
///
/// See UT_Pointers for an example implementation.
template <typename ELEMENT, typename CONTAINER>
class UT_Iterator 
{
public:

    /// NOTE: index counts from the *end* if reverse is true.
    ///       This is to preserve old UT_Pointers behaviour.
    UT_Iterator(const CONTAINER &container,
                UT_NotifierImpl<UT_IteratorEvent &> *notifier, 
                int idx = 0, bool reverse = false)
        : myContainer(container),
          myIndex((!reverse) ? idx : myContainer.entries() - idx - 1),
          myDirection((!reverse) ? 1 : -1),
          myIsInvalid(false),
          myIsAlreadyAtNext(false),
          myIsFirstTime(true)
    {
        if(notifier)
        {
            // Register the callback.
            UT_Functor1<void, UT_IteratorEvent &>
                functor(this, &UT_Iterator::onEvent);
            notifier->addObserver(myNotifierList, functor);
        }
    }

    /// Returns true if the iterator points to a valid element.
    bool isValid()
    {
        return !myIsInvalid && myIndex >= 0 && myIndex < myContainer.entries();
    }
    
    /// Do not call this function on invalid iterators,
    ///   as there is no sensible value to return in that case.
    ELEMENT current()
    {
        UT_ASSERT(isValid());
        return myContainer(myIndex);
    }

    /// This function returns true if the iterator was valid before the next()
    /// operation.
    /// Note that it may be invalid after the next() operation.
    ///   (because it just moved off the end of the list, for example)
    bool next()
    {
        if(myIsAlreadyAtNext)
        {
            myIsAlreadyAtNext = false;
            return isValid();
        }
        if(!isValid())
        {
            return false;
        }
        myIndex += myDirection; 
        return true;
    }

    /// Do not call this function on invalid iterators,
    ///   as there is no sensible value to return in that case.
    int index()
    {
        UT_ASSERT(isValid());
        return myIndex;
    }

    /// This is for code that wants to loop like:
    /// for(CONTAINER::Iterator it=p.iterator(); it.get(s); ) {
    ///  // do stuff
    /// }
    ///
    /// instead of:
    /// for(CONTAINER::Iterator it=p.iterator(); it.isValid(); it.next()) {
    ///   ELEMENT e = it.current();
    ///   // do stuff
    /// }
    ///
    /// Note that this function is templated so that the type can be inferred.
    template <typename ELEMENT_OUT>
    bool get(ELEMENT_OUT &e)
    {
        if(!myIsFirstTime)
        {
            if(!next())
            {
                e = (ELEMENT_OUT) myContainer.null();
                return false;
            }
        }
        myIsFirstTime = false;
        if(!isValid())
        {
            e = (ELEMENT_OUT) myContainer.null();
            return false;
        }
        e = (ELEMENT_OUT)current();
        return true;
    }


private:
    const CONTAINER &myContainer;
    UT_NotifierList myNotifierList;
    
    int myIndex;
    int myDirection;

    /// true if the iterator's container is gone.
    bool myIsInvalid;

    /// this is to make iteration work properly if the current element is
    /// removed.
    bool myIsAlreadyAtNext;
    
    /// this is to make get() work properly.
    bool myIsFirstTime;
 
    void onEvent(UT_IteratorEvent &event)
    {
        switch(event.type)
        {
            // elements have been inserted into the range [lo, hi].
            case UT_IteratorEvent::ADD:
                if( myIndex >= event.lo )
                {
                    myIndex += (event.hi - event.lo + 1);
                }    
                break;

            // elements in the range [lo, hi] have been removed.
            case UT_IteratorEvent::REMOVE:
                if( myIndex > event.hi )
                {
                    myIndex -= (event.hi - event.lo + 1);
                }
                else if( myIndex >= event.lo )
                {
                    // The current position was deleted!
                    myIndex = event.lo;
                    if( myDirection == -1 )
                        myIndex--;
                    myIsAlreadyAtNext = true;
                }
                break;

            // this iterator's container has deleted its elements
            // or has been deleted itself.
            case UT_IteratorEvent::INVALID:
                myIsInvalid = true; 
                break;

            default:
                UT_ASSERT(!"Unknown enumeration value!");
                break;
        }
    }
};

#endif

---