Iterator

Part of TemplatesCategory

Description

An iterator with a list class

Example

/*
 * Copyright (c) 2004
 * Sean Kelly
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Author makes no representations about
 * the suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */


//
// simple list type

//
// this is defined kind of oddly to get around scoping problems
//
template List( Ty )
{
public:
    alias Ty        Value;
    alias size_t    Size;


    class Node
    {
    public:
        alias List!(Ty).Value   Value;
    
        this()
        {
            prev = this;
            next = this;
        }

        this( Value v )
        {
            val = v;
            this();
        }

    private:
        Value   val;
        Node    prev,
                next;
    }


    class Iterator
    {
    public:
        alias List!(Ty).Value   Value;
    
        this( Node n )
        {
            ref = n;
        }

        Iterator opAddAssign( int unused )
        {
            ref = ref.next;
            return this;
        }

/*
        Iterator opPostInc()
        {
            iterator tmp( ref );
            ref = ref.next;
            return tmp;
        }
*/
        Iterator opSubAssign( int unused )
        {
            ref = ref.prev;
            return this;
        }
/*
        Iterator opPostDec()
        {
            iterator tmp( ref );
            ref = ref.prev;
            return tmp;
        }
*/
        int opEquals( Iterator rhs )
        {
            return ref == rhs.ref;
        }

        void val( Value v )
        {
            ref.val = v;
        }

        Value val()
        {
            return ref.val;
        }
        
    private:
        Node    ref;
    }


    class Container
    {
    public:
        alias List!(Ty).Iterator Iterator;
        alias List!(Ty).Value    Value;
        alias List!(Ty).Size     Size;
        
        this()
        {
            m_head  = new Node();
            m_size  = 0;


        }
    
        Size size()
        {
            return m_size;
        }
    
        bit empty()
        {
            return m_size == 0;

        }
    
        Iterator begin()
        {
            return new Iterator( m_head.next );
        }
    
        Iterator end()
        {
            return new Iterator( m_head );
        }

        Value front()
        {
            return m_head.next.val;
        }

        Value back()
        {
            return m_head.prev.val;
        }

        void pushFront( Value val )
        {
            insert( begin(), val );
        }

        void pushBack( Value val )
        {
            insert( end(), val );
        }

        Iterator insert( Iterator pos, Value val )
        {
            Node n = new Node( val );
            n.next = pos.ref;
            n.prev = pos.ref.prev;
            pos.ref.prev.next = n;
            pos.ref.prev = n;
            ++m_size;
            return --pos;
        }

    protected:
        Node    m_head;
        Size    m_size;
    }
}



//
// default iterator definitions that apply
// to all user-defined containers
//
template IterImpl( Ty )
{
    alias Ty            Container;
    alias Ty.Iterator   Iterator;    
    alias Ty.Value      Value;
    alias Ty.Size       Size;

    Iterator begin( Container cont )
    {
        return cont.begin();
    }

    Iterator end( Container cont )
    {
        return cont.end();
    }
}



//
// iterator specialization for primitive array
//
template IterImpl( Ty : Ty[] )
{
    alias Ty[]      Container;
    alias Ty        Value;
    alias size_t    Size;
    
    class Iterator
    {
    public:
        this( Ty* pos )
        {
            m_pos = pos;
        }

        Iterator opAddAssign( int unused )
        {
            if( m_pos )
                ++m_pos;
            return this;
        }

        Iterator opSubAssign( int unused )
        {
            if( m_pos )
                --m_pos;
            return this;
        }

        int opEquals( Iterator rhs )
        {
            return m_pos == rhs.m_pos;
        }

        void val( Value val )
        {
            if( m_pos )
                *m_pos = val;
        }

        Value val()
        {
            return m_pos ? *m_pos : Ty.init;
        }
    
    private:
        Value*  m_pos;
    }

    Iterator begin( Container cont )
    {
        return new Iterator( cont.length ? &cont[0] : null );
    }

    Iterator end( Container cont )
    {
        return new Iterator( cont.length ? &cont[0] + cont.length : null );
    }
}



//
// convenience wrappers to reduce type length
//
template Iterator( Ty )
{
    alias IterImpl!(Ty).Iterator Iterator;
}


template begin( Ty )
{
    alias IterImpl!(Ty).begin begin;
}



template end( Ty )
{
    alias IterImpl!(Ty).end end;
}


//
// slightly lame sample algorithm that only works for int value types
//
template print( Iter )
{
    void print( Iter begin, Iter end )
    {
        for( ; begin != end; ++begin )
            printf( "%d\n", begin.val );
    }
}



int main( char[][] args )
{
    alias List!(int).Container  IntList;
    alias int[]                 IntArray;

    IntList     list    = new IntList();
    IntArray    array;

    list.insert( list.begin(), 1 );
    list.insert( list.begin(), 2 );
    list.insert( list.begin(), 3 );
    
    array.length = 3;
    array[0] = 7;
    array[1] = 8;
    array[2] = 9;

    Iterator!(IntList)  l_begin = begin!(IntList)( list ),
                        l_end   = end!(IntList)( list );
    
    Iterator!(IntArray) a_begin = begin!(IntArray)( array ),
                        a_end   = end!(IntArray)( array );

    print!(Iterator!(IntList))( l_begin, l_end );
    printf( "\n" );
    print!(Iterator!(IntArray))( a_begin, a_end );
    return 0;
}

Source

From digitalmars.D:7583: http://home.f4.ca/sean/d/iterator.d.