base_nest.hh

Go to the documentation of this file.

/*
 * LEGAL:   COPYRIGHT (C) 2006 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
 *****************************************************************************/

#ifndef BASE_NEST_HH
#define BASE_NEST_HH 1

#include "base_common.hh"

namespace base {

template<typename T>
class Nest
{
private:
    typedef Dlist<T>            InnerDlist;  // inner list (links items)
    typedef Dlink<T>            InnerDlink;  // link in inner list that points to actual object
    typedef Dlist<InnerDlist>   OuterDlist;  // outer list (links inner lists)
    typedef Dlink<InnerDlist>   OuterDlink;  // link in outer dlist that points to inner list

public:
    class GroupId
    {
    
    public:         GroupId( void )  
                    :   mInnerDlist(NULL),
                        mOuterDlink(NULL)
                    { }
    private:        GroupId( InnerDlist* innerDlist, OuterDlink* outerDlink )
                    :   mInnerDlist(innerDlist),
                        mOuterDlink(outerDlink)
                    { }
    public:         ~GroupId() { }  // NOP, this doesn't own Dlist/Dlink
    private: InnerDlist* GetInnerDlist( void ) const { ASSERT(*this); return mInnerDlist; }
    private: OuterDlink* GetOuterDlink( void ) const { ASSERT(*this); return mOuterDlink; }
    public: void    operator=( bool f )  // eg groupId = false;
                    {
                        ASSERT( not f );  // assigning true is nonsensical
                        mInnerDlist = NULL;
                        mOuterDlink = NULL;
                    }
    public:         operator bool() const  
                    {
                        return mInnerDlist != NULL
                            && mOuterDlink != NULL;
                    }
    friend bool     operator==( const GroupId& a, const GroupId& b )
                    {
                        return a.mInnerDlist == b.mInnerDlist
                            && b.mOuterDlink == b.mOuterDlink;
                    }
    friend bool     operator!=( const GroupId& a, const GroupId& b )
                    {
                        return a.mInnerDlist != b.mInnerDlist
                            || b.mOuterDlink != b.mOuterDlink;
                    }
    public:         bool IfEmpty( void ) const  
                    {
                        ASSERT( *this );
                        return mInnerDlist == NULL || mInnerDlist->IfEmpty();
                    }
    private:
        InnerDlist*     mInnerDlist;  // Nest<> should use Get*() methods
        OuterDlink*     mOuterDlink;  // which do checking
    friend class Nest<T>;
    };

public:
    class ItemId
    {
    
    public:         ItemId( void )
                    :   mInnerDlink(NULL) { }
    private:        ItemId( InnerDlink* innerDlink )
                    :   mInnerDlink(innerDlink) { }
    public:         ~ItemId() { }  // NOP, doesn't own the pointed-to objects
    private: InnerDlink* GetInnerDlink( void )  const { ASSERT(*this); return mInnerDlink; }
    public: void    operator=( bool f )  // eg itemId = false;
                    {
                        ASSERT( not f );  // assigning true is nonsensical
                        mInnerDlink = NULL;
                    }
    public:         operator bool() const  
                    {
                        return mInnerDlink != NULL;
                    }
    friend bool     operator==( const ItemId& a, const ItemId& b )
                    {
                        return a.mInnerDlink == b.mInnerDlink;
                    }
    friend bool     operator!=( const ItemId& a, const ItemId& b )
                    {
                        return a.mInnerDlink != b.mInnerDlink;
                    }
    private:
        InnerDlink*     mInnerDlink;   // Nest<> should use Get*() methods which do checking
    friend class Nest<T>;
    };

public:
    enum eDestroy { DESTROY = Dlist<T>::DESTROY,
                    KEEP    = Dlist<T>::KEEP };

    // OuterDlist always has DESTROY/SCALAR.
    // The user-specified destroy args apply to inner dlists.
    Nest( void )
    :   mDestroy(DESTROY),
        mOuterDlist(OuterDlist::DESTROY)
    {
        // NOP
    }

    Nest( eDestroy destroy )
    :   mDestroy(destroy),
        mOuterDlist(OuterDlist::DESTROY)  // independent of ctor arg
    {
        // NOP
    }

    ~Nest()
    {
        // NOP.  mOuterDlist destroys itself and its sub-lists.
        // Whether items are destroyed depends whether user passed DESTROY/KEEP.
    }

    bool
    IfEmpty( void ) const
    {
        return mOuterDlist.IfEmpty();
    }

    GroupId
    AddGroup( void )
    {
        InnerDlist* innerDlist = new InnerDlist( (typename InnerDlist::eDestroy)mDestroy );
        OuterDlink* outerDlink = mOuterDlist.Append( innerDlist );
        return GroupId( innerDlist, outerDlink );
    }

    bool
    IfEmptyGroup( const GroupId& groupId ) const
    {
      //ASSERT( groupId );
        return groupId && groupId.IfEmpty();
    }

    GroupId
    FirstGroup( void ) const
    {
        if ( not mOuterDlist.IfEmpty() )
        {
            InnerDlist* innerDlist = mOuterDlist.First()->Obj();
            OuterDlink* outerDlink = mOuterDlist.First();
            return GroupId( innerDlist, outerDlink );
        }
        else
        {
            return GroupId();  // invalid ID, no groups exist
        }
    }

    GroupId
    NextGroup( const GroupId& groupId ) const
    {
        ASSERT( groupId );  // valid ID must be passed
        ASSERT( not mOuterDlist.IfEmpty() );  // how could an ID be passed if none exists?
        OuterDlink* outerDlink = groupId.GetOuterDlink();
        OuterDlink* nextOuterDlink = mOuterDlist.Next( outerDlink );
        InnerDlist* nextInnerDlist = nextOuterDlink->Obj();
        return GroupId( nextInnerDlist, nextOuterDlink );
    }

    T*
    GetItem( const ItemId& itemId ) const
    {
        ASSERT( itemId );
        return itemId.GetInnerDlink()->Obj();
    }

    ItemId
    AddItem( const GroupId& groupId, T* item )
    {
        ASSERT( groupId );
        InnerDlink* innerDlink = groupId.GetInnerDlist()->Append( item );
        return ItemId( innerDlink );
    }

    void
    RemoveItem( GroupId& groupId, ItemId& itemId )
    {
        ASSERT( groupId );
        ASSERT( itemId );

        // Unlink item from inner list.
        // itemId has a GroupId which has inner list.
        InnerDlist* innerDlist = groupId.GetInnerDlist();
        innerDlist->Unlink( itemId.GetInnerDlink() );  // unlink item (doesn't delete item)

        // If inner list has become empty, unlink it out of outer list, and delete it.
        if ( innerDlist->IfEmpty() )
        {
            mOuterDlist.Unlink( groupId.GetOuterDlink() );
            delete innerDlist;
            groupId = false;  // invalidate
        }

        itemId = false;  // invalidate
    }

    ItemId
    FirstItem( const GroupId& groupId ) const
    {
        ASSERT( groupId );
        InnerDlist* innerDlist = groupId.GetInnerDlist();
        if ( not innerDlist->IfEmpty() )
        {
            InnerDlink* innerDlink = innerDlist->First();
            return ItemId(innerDlink);
        }
        else
        {
            // This group is empty.
            return ItemId();
        }
    }

    ItemId
    NextItem( const GroupId& groupId, const ItemId& itemId ) const
    {
        ASSERT( groupId );
        ASSERT( itemId );
        InnerDlist* innerDlist = groupId.GetInnerDlist();
        ASSERT( not innerDlist->IfEmpty() );  // how can item ID be obtained from empty inner list?
        InnerDlink* nextInnerDlink = innerDlist->Next( itemId.GetInnerDlink() );
        return ItemId( nextInnerDlink );
    }

    template<typename FUNCTOR>
    void
    ForEachItem( FUNCTOR& functor )
    {
        const GroupId groupId1 = FirstGroup();
              GroupId groupId  = groupId1;
        while ( groupId )
        {
            const ItemId itemId1 = FirstItem( groupId );
                  ItemId itemId  = itemId1;
            while ( itemId )
            {
                // Pass this item to functor.
                functor( GetItem(itemId) );

                // To next item.  Stop at circling back to first item.
                itemId = NextItem( groupId, itemId );
                if ( itemId == itemId1 ) break;
            }
            // To next group likewise.
            groupId = NextGroup( groupId );
            if ( groupId == groupId1 ) break;
        }
    }

private:
    eDestroy    mDestroy;  // applies to inner Dlists
    OuterDlist  mOuterDlist;
};

} // namespace base

#endif // BASE_NEST_HH

Palomino 3D Engine documents generated by doxygen 1.5.3 on Fri Nov 23 11:26:06 2007