iterator.hpp

ncbi源码

/*
 * ===========================================================================
 * PRODUCTION $Log: iterator.hpp,v $
 * PRODUCTION Revision 1000.1  2004/06/01 19:38:38  gouriano
 * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.30
 * PRODUCTION
 * ===========================================================================
 */

#ifndef ITERATOR__HPP
#define ITERATOR__HPP

/*  $Id: iterator.hpp,v 1000.1 2004/06/01 19:38:38 gouriano Exp $
* ===========================================================================
*
*                            PUBLIC DOMAIN NOTICE
*               National Center for Biotechnology Information
*
*  This software/database is a "United States Government Work" under the
*  terms of the United States Copyright Act.  It was written as part of
*  the author's official duties as a United States Government employee and
*  thus cannot be copyrighted.  This software/database is freely available
*  to the public for use. The National Library of Medicine and the U.S.
*  Government have not placed any restriction on its use or reproduction.
*
*  Although all reasonable efforts have been taken to ensure the accuracy
*  and reliability of the software and data, the NLM and the U.S.
*  Government do not and cannot warrant the performance or results that
*  may be obtained by using this software or data. The NLM and the U.S.
*  Government disclaim all warranties, express or implied, including
*  warranties of performance, merchantability or fitness for any particular
*  purpose.
*
*  Please cite the author in any work or product based on this material.
*
* ===========================================================================
*
* Author: Eugene Vasilchenko
*
* File Description:
*   Iterators through object hierarchy
*/

#include <corelib/ncbistd.hpp>
#include <corelib/ncbiutil.hpp>
#include <serial/exception.hpp>
#include <serial/objecttype.hpp>
#include <serial/serialutil.hpp>
#include <serial/serialbase.hpp>
#include <set>
#include <stack>


/** @addtogroup ObjHierarchy
 *
 * @{
 */


BEGIN_NCBI_SCOPE

class CTreeIterator;

// class holding information about root of non-modifiable object hierarchy
// Do not use it directly
class NCBI_XSERIAL_EXPORT CBeginInfo : public pair<TObjectPtr, TTypeInfo>
{
    typedef pair<TObjectPtr, TTypeInfo> CParent;
public:
    typedef CObjectInfo TObjectInfo;

    CBeginInfo(TObjectPtr objectPtr, TTypeInfo typeInfo,
               bool detectLoops = false)
        : CParent(objectPtr, typeInfo), m_DetectLoops(detectLoops)
        {
        }
    CBeginInfo(const CObjectInfo& object,
               bool detectLoops = false)
        : CParent(object.GetObjectPtr(), object.GetTypeInfo()),
          m_DetectLoops(detectLoops)
        {
        }
    CBeginInfo(CSerialObject& object, bool detectLoops = false)
        : CParent(&object, object.GetThisTypeInfo()),
          m_DetectLoops(detectLoops)
        {
        }

    bool m_DetectLoops;
};

// class holding information about root of non-modifiable object hierarchy
// Do not use it directly
class NCBI_XSERIAL_EXPORT CConstBeginInfo : public pair<TConstObjectPtr, TTypeInfo>
{
    typedef pair<TConstObjectPtr, TTypeInfo> CParent;
public:
    typedef CConstObjectInfo TObjectInfo;

    CConstBeginInfo(TConstObjectPtr objectPtr, TTypeInfo typeInfo,
                    bool detectLoops = false)
        : CParent(objectPtr, typeInfo), m_DetectLoops(detectLoops)
        {
        }
    CConstBeginInfo(const CConstObjectInfo& object,
                    bool detectLoops = false)
        : CParent(object.GetObjectPtr(), object.GetTypeInfo()),
          m_DetectLoops(detectLoops)
        {
        }
    CConstBeginInfo(const CSerialObject& object,
                    bool detectLoops = false)
        : CParent(&object, object.GetThisTypeInfo()),
          m_DetectLoops(detectLoops)
        {
        }
    CConstBeginInfo(const CBeginInfo& beginInfo)
        : CParent(beginInfo.first, beginInfo.second),
          m_DetectLoops(beginInfo.m_DetectLoops)
        {
        }

    bool m_DetectLoops;
};

// class describing stack level of traversal
// do not use it directly
class NCBI_XSERIAL_EXPORT CConstTreeLevelIterator {
public:
    typedef CConstBeginInfo TBeginInfo;
    typedef TBeginInfo::TObjectInfo TObjectInfo;
    
    virtual ~CConstTreeLevelIterator(void);

    virtual bool Valid(void) const = 0;
    virtual void Next(void) = 0;
    virtual bool CanGet(void) const
    {
        return true;
    }
    virtual TObjectInfo Get(void) const = 0;

    static CConstTreeLevelIterator* Create(const TObjectInfo& object);
    static CConstTreeLevelIterator* CreateOne(const TObjectInfo& object);

    static bool HaveChildren(const CConstObjectInfo& object);
};

class NCBI_XSERIAL_EXPORT CTreeLevelIterator
{
public:
    typedef CBeginInfo TBeginInfo;
    typedef TBeginInfo::TObjectInfo TObjectInfo;

    virtual ~CTreeLevelIterator(void);

    virtual bool Valid(void) const = 0;
    virtual void Next(void) = 0;
    virtual bool CanGet(void) const
    {
        return true;
    }
    virtual TObjectInfo Get(void) const = 0;

    static CTreeLevelIterator* Create(const TObjectInfo& object);
    static CTreeLevelIterator* CreateOne(const TObjectInfo& object);

    virtual void Erase(void);
};

// CTreeIterator is base class for all iterators over non-modifiable object
// Do not use it directly
template<class LevelIterator>
class CTreeIteratorTmpl
{
    typedef CTreeIteratorTmpl<LevelIterator> TThis;
public:
    typedef typename LevelIterator::TObjectInfo TObjectInfo;
    typedef typename LevelIterator::TBeginInfo TBeginInfo;
    typedef set<TConstObjectPtr> TVisitedObjects;

    // construct object iterator
    CTreeIteratorTmpl(void)
        {
            _DEBUG_ARG(m_LastCall = eNone);
        }
    CTreeIteratorTmpl(const TBeginInfo& beginInfo)
        {
            _DEBUG_ARG(m_LastCall = eNone);
            Init(beginInfo);
        }
    virtual ~CTreeIteratorTmpl(void)
        {
            Reset();
        }


    // get information about current object
    TObjectInfo& Get(void)
        {
            _ASSERT(CheckValid());
            return m_CurrentObject;
        }
    // get information about current object
    const TObjectInfo& Get(void) const
        {
            _ASSERT(CheckValid());
            return m_CurrentObject;
        }
    // get type information of current object
    TTypeInfo GetCurrentTypeInfo(void) const
        {
            return Get().GetTypeInfo();
        }

    // reset iterator to initial state
    void Reset(void)
        {
            m_CurrentObject.Reset();
            m_VisitedObjects.reset(0);
            _DEBUG_ARG(m_LastCall = eNone);
            while ( !m_Stack.empty() )
                m_Stack.pop();
            _ASSERT(!*this);
        }

    void Next(void)
        {
            _ASSERT(CheckValid());
            m_CurrentObject.Reset();

            _ASSERT(!m_Stack.empty());
            if ( Step(m_Stack.top()->Get()) )
                Walk();
        }

    void SkipSubTree(void)
        {
            _ASSERT(CheckValid());
            m_Stack.push(AutoPtr<LevelIterator>(LevelIterator::CreateOne(TObjectInfo())));
        }

    // check whether iterator is not finished
    operator bool(void) const
        {
            _DEBUG_ARG(m_LastCall = eValid);
            return CheckValid();
        }
    // check whether iterator is not finished
    bool operator!(void) const
        {
            _DEBUG_ARG(m_LastCall = eValid);
            return !CheckValid();
        }
    // go to next object
    TThis& operator++(void)
        {
            Next();
            return *this;
        }

    // initialize iterator to new root of object hierarchy
    TThis& operator=(const TBeginInfo& beginInfo)
        {
            Init(beginInfo);
            return *this;
        }

protected:
    bool CheckValid(void) const
        {
#if _DEBUG
            if ( m_LastCall != eValid)
                ReportNonValid();
#endif
            return m_CurrentObject;
        }

    void ReportNonValid(void) const
        {
            ERR_POST("Object iterator was used without checking its validity");
        }

    virtual bool CanSelect(const CConstObjectInfo& obj)
        {
            if ( !obj )
                return false;
            TVisitedObjects* visitedObjects = m_VisitedObjects.get();
            if ( visitedObjects ) {
                if ( !visitedObjects->insert(obj.GetObjectPtr()).second ) {
                    // already visited
                    return false;
                }
            }
            return true;
        }

    virtual bool CanEnter(const CConstObjectInfo& object)
        {
            return CConstTreeLevelIterator::HaveChildren(object);
        }

protected:
    // have to make these methods protected instead of private due to
    // bug in GCC
#ifdef NCBI_OS_MSWIN
    CTreeIteratorTmpl(const TThis&) { NCBI_THROW(CSerialException,eIllegalCall, "cannot copy"); }
    TThis& operator=(const TThis&) { NCBI_THROW(CSerialException,eIllegalCall, "cannot copy"); }
#else
    CTreeIteratorTmpl(const TThis&);
    TThis& operator=(const TThis&);
#endif

    void Init(const TBeginInfo& beginInfo)
        {
            Reset();
            if ( !beginInfo.first || !beginInfo.second )
                return;
            if ( beginInfo.m_DetectLoops )
                m_VisitedObjects.reset(new TVisitedObjects);
            m_Stack.push(AutoPtr<LevelIterator>(LevelIterator::CreateOne(beginInfo)));
            Walk();
        }

private:
    bool Step(const TObjectInfo& current)
        {
            if ( CanEnter(current) ) {
                AutoPtr<LevelIterator> nextLevel(LevelIterator::Create(current));
                if ( nextLevel && nextLevel->Valid() ) {
                    m_Stack.push(nextLevel);
                    return true;
                }
            }
            // skip all finished iterators
            _ASSERT(!m_Stack.empty());
            do {
                m_Stack.top()->Next();
                if ( m_Stack.top()->Valid() ) {
                    // next child on this level
                    return true;
                }
                m_Stack.pop();
            } while ( !m_Stack.empty() );
            return false;
        }

    void Walk(void)
        {
            _ASSERT(!m_Stack.empty());
            TObjectInfo current;
            do {
                while (!m_Stack.top()->CanGet()) {
                    for(;;) {
                        m_Stack.top()->Next();
                        if (m_Stack.top()->Valid()) {
                            break;
                        }
                        m_Stack.pop();
                        if (m_Stack.empty()) {
                            return;
                        }
                    }
                }
                current = m_Stack.top()->Get();
                if ( CanSelect(current) ) {
                    m_CurrentObject = current;
                    return;
                }
            } while ( Step(current) );
        }

#if _DEBUG
    mutable enum { eNone, eValid, eNext, eErase } m_LastCall;
#endif
    // stack of tree level iterators
    stack< AutoPtr<LevelIterator> > m_Stack;
    // currently selected object
    TObjectInfo m_CurrentObject;
    auto_ptr<TVisitedObjects> m_VisitedObjects;

    friend class CTreeIterator;
};

typedef CTreeIteratorTmpl<CConstTreeLevelIterator> CTreeConstIterator;

// CTreeIterator is base class for all iterators over modifiable object
class NCBI_XSERIAL_EXPORT CTreeIterator : public CTreeIteratorTmpl<CTreeLevelIterator>
{
    typedef CTreeIteratorTmpl<CTreeLevelIterator> CParent;
public:
    typedef CParent::TObjectInfo TObjectInfo;
    typedef CParent::TBeginInfo TBeginInfo;

    // construct object iterator
    CTreeIterator(void)
        {
        }
    CTreeIterator(const TBeginInfo& beginInfo)
        {
            Init(beginInfo);
        }

    // initialize iterator to new root of object hierarchy
    CTreeIterator& operator=(const TBeginInfo& beginInfo)
        {
            Init(beginInfo);
            return *this;
        }

    // delete currently pointed object (throws exception if failed)
    void Erase(void);
};

// template base class for CTypeIterator<> and CTypeConstIterator<>
// Do not use it directly
template<class Parent>
class CTypeIteratorBase : public Parent
{
    typedef Parent CParent;
protected:
    typedef typename CParent::TBeginInfo TBeginInfo;

    CTypeIteratorBase(TTypeInfo needType)
        : m_NeedType(needType)
        {
        }
    CTypeIteratorBase(TTypeInfo needType, const TBeginInfo& beginInfo)
        : m_NeedType(needType)
        {
            Init(beginInfo);
        }

    virtual bool CanSelect(const CConstObjectInfo& object)
        {
            return CParent::CanSelect(object) &&
                object.GetTypeInfo()->IsType(m_NeedType);
        }
    virtual bool CanEnter(const CConstObjectInfo& object)
        {
            return CParent::CanEnter(object) &&
                object.GetTypeInfo()->MayContainType(m_NeedType);
        }

    TTypeInfo GetIteratorType(void) const
        {
            return m_NeedType;
        }

private:
    TTypeInfo m_NeedType;
};

// template base class for CTypeIterator<> and CTypeConstIterator<>
// Do not use it directly
template<class Parent>
class CLeafTypeIteratorBase : public CTypeIteratorBase<Parent>
{
    typedef CTypeIteratorBase<Parent> CParent;
protected:
    typedef typename CParent::TBeginInfo TBeginInfo;

    CLeafTypeIteratorBase(TTypeInfo needType)
        : CParent(needType)
        {
        }
    CLeafTypeIteratorBase(TTypeInfo needType, const TBeginInfo& beginInfo)
        : CParent(needType)
        {
            Init(beginInfo);
        }

    virtual bool CanSelect(const CConstObjectInfo& object);
};

// template base class for CTypesIterator and CTypesConstIterator
// Do not use it directly
template<class Parent>
class CTypesIteratorBase : public Parent
{
    typedef Parent CParent;
public:
    typedef typename CParent::TBeginInfo TBeginInfo;
    typedef list<TTypeInfo> TTypeList;

    CTypesIteratorBase(void)
        {
        }
    CTypesIteratorBase(TTypeInfo type)
        {
            m_TypeList.push_back(type);
        }
    CTypesIteratorBase(TTypeInfo type1, TTypeInfo type2)
        {
            m_TypeList.push_back(type1);
            m_TypeList.push_back(type2);
        }
    CTypesIteratorBase(const TTypeList& typeList)
        : m_TypeList(typeList)