path: root/src/inc/iterator.h

//
// Copyright (c) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
//
// ---------------------------------------------------------------------------
// Iterator.h
// ---------------------------------------------------------------------------

// ================================================================================
// Iterator pattern:
//
// This pattern is similar to the STL iterator pattern.  It basically consists of
// wrapping an "iteration variable" in an object, and providing pointer-like operators
// on the iterator. Example usage:
//
// for (Iterator start = foo->Begin(), end = foo->End(); start != end; start++)
// {
//      // use foo, start
// }
//
// There are 3 levels of iterator functionality
//      1. Enumerator (STL forward) - only go forward one at a time
//          Enumerators have the following operations:
//              operator * : access current element as ref
//              operator -> : access current element as ptr
//              operator++ : go to the next element
//              operator==, operator!= : compare to another enumerator
//
//
//      2. Scanner (STL bidirectional) - backward or forward one at a time
//          Scanners have all the functionality of enumerators, plus:
//              operator-- : go backward one element
//
//      3. Indexer (STL random access)  - skip around arbitrarily
//          Indexers have all the functionality of scanners, plus:
//              operator[] : access the element at index from iterator as ref
//              operator+= : advance iterator by index 
//              operator+ : return new iterator at index from iterator
//              operator-= : rewind iterator by index 
//              operator- : return new iterator at index back from iterator
//              operator <, operator <=, operator >, operator>= :
//                  range comparison on two indexers    
//
// The object being iterated should define the following methods:
//      Begin()             return an iterator starting at the first element
//      End()               return an iterator just past the last element
//
// Iterator types are normally defined as member types named "Iterator", no matter
// what their functionality level is.
// ================================================================================


#ifndef ITERATOR_H_
#define ITERATOR_H_

#include "contract.h"

namespace HIDDEN {
// These prototypes are not for direct use - they are only here to illustrate the 
// iterator pattern

template <typename CONTAINER, typename ELEMENT>
class ScannerPrototype
{
  public:

    typedef ScannerPrototype<CONTAINER, ELEMENT> Iterator;

    ELEMENT &operator*();
    ELEMENT *operator->();

    Iterator &operator++();
    Iterator operator++(int);
    Iterator &operator--();
    Iterator operator--(int);

    bool operator==(const Iterator &i);
    bool operator!=(const Iterator &i);
};

template <typename CONTAINER, typename ELEMENT>
class EnumeratorPrototype
{
  public:
    
    typedef EnumeratorPrototype<CONTAINER, ELEMENT> Iterator;

    ELEMENT &operator*();
    ELEMENT *operator->();

    Iterator &operator++();
    Iterator operator++(int);

    bool operator==(const Iterator &i);
    bool operator!=(const Iterator &i);
};

template <typename CONTAINER, typename ELEMENT>
class IndexerPrototype
{
  public:
    typedef IndexerPrototype<CONTAINER, ELEMENT> Iterator;

    ELEMENT &operator*();
    ELEMENT *operator->();
    ELEMENT &operator[](int index);

    Iterator &operator++();
    Iterator operator++(int);
    Iterator &operator--();
    Iterator operator--(int);

    Iterator &operator+=(SCOUNT_T index);
    Iterator &operator-=(SCOUNT_T index);

    Iterator operator+(SCOUNT_T index);
    Iterator operator-(SCOUNT_T index);

    SCOUNT_T operator-(Iterator &i);

    bool operator==(const Iterator &i);
    bool operator!=(const Iterator &i);
    bool operator<(const Iterator &i);
    bool operator<=(const Iterator &i);
    bool operator>(const Iterator &i);
    bool operator>=(const Iterator &i);
};

template <typename ELEMENT>
class EnumerablePrototype
{
    typedef EnumeratorPrototype<EnumerablePrototype, ELEMENT> Iterator;

    Iterator Begin();
    Iterator End();
};

template <typename ELEMENT>
class ScannablePrototype
{
    typedef ScannerPrototype<ScannablePrototype, ELEMENT> Iterator;

    Iterator Begin();
    Iterator End();
};

template <typename ELEMENT>
class IndexablePrototype
{
    typedef IndexerPrototype<IndexablePrototype, ELEMENT> Iterator;

    Iterator Begin();
    Iterator End();
};

};

// --------------------------------------------------------------------------------
// EnumeratorBase, ScannerBase, and IndexerBase are abstract classes 
// describing basic operations for iterator functionality at the different levels.
// 
// You
// 1. Use the classes as a pattern (don't derive from them), and plug in your own 
//      class into the Enumerator/Scanner/Indexer templates below.
// 2. Subclass the AbstractEnumerator/AbstractScanner/AbstractIndexer classes
// --------------------------------------------------------------------------------

namespace HIDDEN
{
// These prototypes are not for direct use - they are only here to illustrate the 
// pattern of the BASE class for the Iterator templates

template <typename ELEMENT, typename CONTAINER>
class EnumeratorBasePrototype
{
  protected:
    EnumeratorBasePrototype(CONTAINER *container, BOOL begin);
    ELEMENT &Get() const;
    void Next();
    BOOL Equal(const EnumeratorBasePrototype &i) const;
    CHECK DoCheck() const;
};

template <typename ELEMENT, typename CONTAINER>
class ScannerBasePrototype
{
 protected:
    ScannerBasePrototype(CONTAINER *container, BOOL begin);
    ELEMENT &Get() const;
    void Next();
    void Previous();
    BOOL Equal(const ScannerBasePrototype &i) const;
    CHECK DoCheck() const;
};

template <typename ELEMENT, typename CONTAINER>
class IndexerBasePrototype
{
 protected:
    IndexerBasePrototype(CONTAINER *container, SCOUNT_T delta);
    ELEMENT &GetAt(SCOUNT_T delta) const;
    void Skip(SCOUNT_T delta);
    SCOUNT_T Subtract(const IndexerBasePrototype &i) const;
    CHECK DoCheck(SCOUNT_T delta) const;
};

};


template <typename CONTAINER>
class CheckedIteratorBase
{
  protected:
#if defined(_DEBUG)
    const CONTAINER *m_container;
    int m_revision;
#endif

    CHECK CheckRevision() const
    {
        LIMITED_METHOD_CONTRACT;
        SUPPORTS_DAC;
#if defined(_DEBUG)
        __if_exists(CONTAINER::m_revision)
        {
            CHECK_MSG(m_revision == m_container->m_revision, 
                      "Use of Iterator after container has been modified");
        }
#endif
        CHECK_OK;
    }

    CheckedIteratorBase()
    {
        LIMITED_METHOD_DAC_CONTRACT;
#if defined(_DEBUG)
        m_container = NULL;
#endif
    }

    CheckedIteratorBase(const CONTAINER *container)
    {
        LIMITED_METHOD_CONTRACT;
#if defined(_DEBUG)
        m_container = container;
        __if_exists(CONTAINER::m_revision)
        {
            m_revision = m_container->m_revision;
        }
#endif
    }

    void Resync(const CONTAINER *container)
    {
        LIMITED_METHOD_DAC_CONTRACT;

#if defined(_DEBUG)
        __if_exists(CONTAINER::m_revision)
        {
            m_revision = m_container->m_revision;
        }
#endif
    }
    
#if defined(_DEBUG)
    const CONTAINER *GetContainerDebug() const
    {
        LIMITED_METHOD_CONTRACT;
        return m_container;
    }
#endif

  public:
    CHECK Check() const
    {
        WRAPPER_NO_CONTRACT;
        SUPPORTS_DAC;
        CHECK(CheckRevision());
        CHECK_OK;
    }

    CHECK CheckContainer(const CONTAINER *container) const
    {
        WRAPPER_NO_CONTRACT;
#if defined(_DEBUG)
        CHECK(container == m_container);
#endif
        CHECK_OK;
    }

};


// --------------------------------------------------------------------------------
// Enumerator, Scanner, and Indexer provide a template to produce an iterator 
// on an existing class with a single iteration variable.
//
// The template takes 3 type parameters:
// CONTAINER - type of object being interated on 
// ELEMENT - type of iteration
// BASE - base type of the iteration.  This type must follow the pattern described 
//      by the above Prototypes
// --------------------------------------------------------------------------------

template <typename ELEMENT, typename SUBTYPE>
class Enumerator
{
 private:
    const SUBTYPE *This() const
    {
        return (const SUBTYPE *) this;
    }

    SUBTYPE *This()
    {
        return (SUBTYPE *)this;
    }

  public:

    Enumerator()
    {
    }

    CHECK CheckIndex() const
    {
#if defined(_DEBUG)
        CHECK(This()->DoCheck());
#endif
        CHECK_OK;
    }

    ELEMENT &operator*() const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex());

        return This()->Get();
    }
    ELEMENT *operator->() const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex());

        return &(This()->Get());
    }
    SUBTYPE &operator++()
    {
        PRECONDITION(CheckPointer(This()));

        This()->Next();
        return *This();
    }
    SUBTYPE operator++(int)
    {
        PRECONDITION(CheckPointer(This()));

        SUBTYPE i = *This();
        This()->Next();
        return i;
    }
    bool operator==(const SUBTYPE &i) const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return This()->Equal(i);
    }
    bool operator!=(const SUBTYPE &i) const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return !This()->Equal(i);
    }
};

template <typename ELEMENT, typename SUBTYPE>
class Scanner 
{
 private:
    const SUBTYPE *This() const
    {
        return (const SUBTYPE *)this;
    }

    SUBTYPE *This()
    {
        return (SUBTYPE *)this;
    }

  public:

    Scanner()
    {
    }

    CHECK CheckIndex() const
    {
#if defined(_DEBUG)
        CHECK(This()->DoCheck());
#endif
        CHECK_OK;
    }

    ELEMENT &operator*() const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex());

        return This()->Get();
    }
    ELEMENT *operator->() const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex());

        return &This()->Get();
    }
    SUBTYPE &operator++()
    {
        PRECONDITION(CheckPointer(This()));

        This()->Next();
        return *This();
    }
    SUBTYPE operator++(int)
    {
        PRECONDITION(CheckPointer(This()));

        SUBTYPE i = *This();
        This()->Next();
        return i;
    }
    SUBTYPE &operator--()
    {
        PRECONDITION(CheckPointer(This()));

        This()->Previous();
        return *This();
    }
    SUBTYPE operator--(int)
    {
        PRECONDITION(CheckPointer(this));

        SUBTYPE i = *This();
        This()->Previous();
        return i;
    }
    bool operator==(const SUBTYPE &i) const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return This()->Equal(i);
    }
    bool operator!=(const SUBTYPE &i) const
    {
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return !This()->Equal(i);
    }
};

template <typename ELEMENT, typename SUBTYPE>
class Indexer
{
 private:
    const SUBTYPE *This() const
    {
        return (const SUBTYPE *)this;
    }

    SUBTYPE *This()
    {
        return (SUBTYPE *)this;
    }

  public:

    Indexer()
    {
        LIMITED_METHOD_DAC_CONTRACT;
    }
    
    CHECK CheckIndex() const
    {
#if defined(_DEBUG)
        CHECK(This()->DoCheck(0));
#endif
        CHECK_OK;
    }

    CHECK CheckIndex(int index) const
    {
#if defined(_DEBUG)
        CHECK(This()->DoCheck(index));
#endif
        CHECK_OK;
    }

    ELEMENT &operator*() const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex(0));

        return *(ELEMENT*)&This()->GetAt(0);
    }
    ELEMENT *operator->() const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex(0));

        return &This()->GetAt(0);
    }
    ELEMENT &operator[](int index) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(This()->CheckIndex(index));
        return *(ELEMENT*)&This()->GetAt(index);
    }
    SUBTYPE &operator++()
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        This()->Skip(1);
        return *This();
    }
    SUBTYPE operator++(int)
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        SUBTYPE i = *This();
        This()->Skip(1);
        return i;
    }
    SUBTYPE &operator--()
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        This()->Skip(-1);
        return *This();
    }
    SUBTYPE operator--(int)
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        SUBTYPE i = *This();
        This()->Skip(-1);
        return i;
    }
    SUBTYPE &operator+=(SCOUNT_T index)
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        This()->Skip(index);
        return *This();
    }
    SUBTYPE operator+(SCOUNT_T index) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        SUBTYPE i = *This();
        i.Skip(index);
        return i;
    }
    SUBTYPE &operator-=(SCOUNT_T index)
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        This()->Skip(-index);
        return *This();
    }
    SUBTYPE operator-(SCOUNT_T index) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        SUBTYPE i = *This();
        i.Skip(-index);
        return i;
    }
    SCOUNT_T operator-(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());
        
        return This()->Subtract(i);
    }
    bool operator==(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return This()->Subtract(i) == 0;
    }
    bool operator!=(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());

        return This()->Subtract(i) != 0;
    }
    bool operator<(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());
        return This()->Subtract(i) < 0;
    }
    bool operator<=(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());
        return This()->Subtract(i) <= 0;
    }
    bool operator>(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());
        return This()->Subtract(i) > 0;
    }
    bool operator>=(const SUBTYPE &i) const
    {
        WRAPPER_NO_CONTRACT;
        PRECONDITION(CheckPointer(This()));
        PRECONDITION(i.Check());
        return This()->Subtract(i) >= 0;
    }
};

#endif  // ITERATOR_H_