反復子を自作するには

反復子を自作するには

 >> NGL >> リファレンス >> Iteratorカテゴリ >> 反復子に関する注意事項 >> 反復子を自作するには

言語: Visual Basic    C#

最終更新日付:2012/07/05 17:44:02

ここでは、反復子を自作する方法について説明します。

 

どんな反復子を作るのか?

まず最初にすべきことは、作成する反復子の種類を決めることです。これはどんな反復子を作りたいかによっておのずと決まってくることでしょう。コンテナの反復子であれば、その種類によって前方向反復子、双方向反復子、ランダムアクセス反復子のいずれかになるでしょう。コンテナの反復子でないのなら、大体は入力反復子か出力反復子になります。

反復子の種類が決まると、どのインターフェースを実装するか、あるいはどの抽象クラスから派生するかが決まります。以下にその一覧を示します。

反復子の種類 実装/派生対象
入力反復子 InputIterator(Of T)
出力反復子 OutputIterator(Of T)
前方向反復子 ForwardIterator(Of T)
双方向反復子 BidirectionalIterator(Of T)
ランダムアクセス反復子 RandomAccessIterator(Of T)
反復子の種類 実装/派生対象
入力反復子 InputIterator<T>
出力反復子 OutputIterator<T>
前方向反復子 ForwardIterator<T>
双方向反復子 BidirectionalIterator<T>
ランダムアクセス反復子 RandomAccessIterator<T>

 

実装の例

正直に書くと細かい説明は面倒なので、それぞれの反復子ごとに例を示します。どこに何を書けば良いかは、この例から読みとってください。

それぞれのクラスのパブリックなインターフェースが個別にありつつ、多態的に振舞うという要件を満たす実装としてあまりキレイなものではありませんが、他にもっと良い方法が思いつきません。より良い方法の提案をお待ちしております。

(ついでに書いておくと、このページのサンプルコードは完全にはテストできていません。せいぜいコンパイルに通るようになっただけ、というレベルのものです。)

 

入力反復子の例

Public Class SampleInputIterator(Of T)

    Inherits InputIterator(Of T)

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Public Shadows Function Clone() As SampleInputIterator(Of T)
        Dim ret As InputIterator(Of T) = Nothing
        Call CloneImp(ret)
        Return CType(ret, SampleInputIterator(Of T))
    End Function

    Public Shared Shadows Operator =(ByVal lhs As SampleInputIterator(Of T), _
                                     ByVal rhs As SampleInputIterator(Of T)) As Boolean
        Return lhs.CompareImp(rhs)
    End Operator

    Public Shared Shadows Operator <>(ByVal lhs As SampleInputIterator(Of T), _
                                      ByVal rhs As SampleInputIterator(Of T)) As Boolean
        Return Not lhs.CompareImp(rhs)
    End Operator

    Public Shadows Function MoveNext() As SampleInputIterator(Of T)
        Call MoveNextImp()
        Return Me
    End Function


    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Protected Overrides Function ReadValueImp() As T
        Dim ret As T
        '//TODO : implement...

        Return ret
    End Function

    Protected Overrides Sub CloneImp(ByRef itr As InputIterator(Of T))
        Dim ret As InputIterator(Of T) = Nothing
        '//TODO : implement...

        itr = ret
    End Sub

    Protected Overrides Function CompareImp(ByVal itr As InputIterator(Of T)) As Boolean
        Dim ret As Boolean = False
        '//TODO : implement...

        Return False
    End Function

    Protected Overrides Sub MoveNextImp()
        '//TODO : implement...

    End Sub

End Class

public class SampleInputIterator<T> : InputIterator<T> {

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    public new SampleInputIterator<T> Clone( ) {
        InputIterator<T> itr = null;
        CloneImp( ref itr );
        return (SampleInputIterator<T>)itr;
    }

    public static bool operator ==( SampleInputIterator<T> itr1,
                                    SampleInputIterator<T> itr2 ) {
        return itr1.CompareImp( itr2 );
    }

    public static bool operator !=( SampleInputIterator<T> itr1,
                                    SampleInputIterator<T> itr2 ) {
        return !( itr1.CompareImp( itr2 ) );
    }

    public new SampleInputIterator<T> MoveNext( ) {
        MoveNextImp( );
        return this;
    }

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    protected override T ReadValueImp() {
        T ret = default( T );
        //TODO : implement...

        return ret;
    }
    protected override void CloneImp( ref InputIterator<T> itr ) {
        InputIterator<T> ret = null;
        //TODO : implement...

        itr = ret;
    }
    protected override bool CompareImp( InputIterator<T> itr ) {
        bool ret = false;
        //TODO : implement...

        return ret;
    }
    protected override void MoveNextImp( ) {
        //TODO : implement...

    }
}

 

出力反復子の例

Public Class SampleOutputIterator(Of T)

    Implements OutputIterator(Of T)

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Public ReadOnly Property Category() As IteratorCategory _
                                Implements OutputIterator(Of T).Category
        Get
            Return IteratorCategory.ITERATORCATEGORY_OUTPUT
        End Get
    End Property

    Public WriteOnly Property Value() As T Implements OutputIterator(Of T).Value
        Set(ByVal value As T)
            '//TODO : implement...

        End Set
    End Property

    Public Function Clone() As SampleOutputIterator(Of T)
        Dim ret As SampleOutputIterator(Of T) = Nothing
        '//TODO : implement...

        Return ret
    End Function

    Public Function MoveNext() As SampleOutputIterator(Of T)
        '//TODO : implement...

        Return Me
    End Function

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Private Function CloneForOutputIterator() As OutputIterator(Of T) _
                                      Implements OutputIterator(Of T).Clone
        Return Me.Clone()
    End Function

    Private Function MoveNextForOutputIterator() As OutputIterator(Of T) _
                                         Implements OutputIterator(Of T).MoveNext
        Return Me.MoveNext()
    End Function

End Class

public class SampleOutputIterator<T> : OutputIterator<T> {

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    public IteratorCategory Category {
        get {
            return IteratorCategory.ITERATORCATEGORY_OUTPUT;
        }
    }
    T OutputIterator<T>.Value {
        set {
            //TODO : implement...

        }
    }
    public SampleOutputIterator<T> Clone( ) {
        SampleOutputIterator<T> itr = null;
        //TODO : implement...

        return itr;
    }
    public SampleOutputIterator<T> MoveNext( ) {
        //TODO : implement...

        return this;
    }

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    OutputIterator<T> OutputIterator<T>.Clone( ) {
        return this.Clone( );
    }
    OutputIterator<T> OutputIterator<T>.MoveNext( ) {
        return this.MoveNext( );
    }

}

 

前方向反復子の例

Public Class SampleForwardIterator(Of T)

    Inherits ForwardIterator(Of T)

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Public Overrides Property Value() As T
        Get
            '//TODO : implement...

        End Get
        Set(ByVal value As T)
            '//TODO : implement...

        End Set
    End Property

    Public Shadows Function Clone() As SampleForwardIterator(Of T)
        Dim ret As InputIterator(Of T) = Nothing
        Call CloneImp(ret)
        Return CType(ret, SampleForwardIterator(Of T))
    End Function

    Public Shared Shadows Operator =(ByVal lhs As SampleForwardIterator(Of T), _
                                     ByVal rhs As SampleForwardIterator(Of T)) As Boolean
        Return lhs.CompareImp(rhs)
    End Operator

    Public Shared Shadows Operator <>(ByVal lhs As SampleForwardIterator(Of T), _
                                      ByVal rhs As SampleForwardIterator(Of T)) As Boolean
        Return Not lhs.CompareImp(rhs)
    End Operator

    Public Shadows Function MoveNext() As SampleForwardIterator(Of T)
        Call MoveNextImp()
        Return Me
    End Function

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Protected Overrides Sub CloneImp(ByRef itr As ForwardIterator(Of T))
        Dim ret As ForwardIterator(Of T) = Nothing
        '//TODO : implement...

        itr = ret
    End Sub

    Protected Overrides Function CompareImp(ByVal itr As InputIterator(Of T)) As Boolean
        Dim ret As Boolean = False
        '//TODO : implement...

        Return False
    End Function

    Protected Overrides Sub MoveNextImp()
        '//TODO : implement...

    End Sub

End Class

public class SampleForwardIterator<T> : ForwardIterator<T> {

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    public override T Value {
        get {
            //TODO : implement...

            return default( T );
        }
        set {
            //TODO : implement...

        }
    }
    public new SampleForwardIterator<T> Clone( ) {
        ForwardIterator<T> itr = null;
        CloneImp( ref itr );
        return (SampleForwardIterator<T>)itr;
    }
    public static bool operator ==( SampleForwardIterator<T> itr1,
                                    SampleForwardIterator<T> itr2 ) {
        return itr1.CompareImp( itr2 );
    }
    public static bool operator !=( SampleForwardIterator<T> itr1,
                                    SampleForwardIterator<T> itr2 ) {
        return !( itr1.CompareImp( itr2 ) );
    }
    public new SampleForwardIterator<T> MoveNext( ) {
        MoveNextImp( );
        return this;
    }

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    protected override void CloneImp( ref ForwardIterator<T> itr ) {
        ForwardIterator<T> ret = null;
        //TODO : implement...

        itr = ret;
    }
    protected override bool CompareImp( InputIterator<T> itr ) {
        bool ret = false;
        //TODO : implement...

        return ret;
    }
    protected override void MoveNextImp( ) {
        //TODO : implement...

    }

}

 

双方向反復子の例

Public Class SampleBidirectionalIterator(Of T)

    Inherits BidirectionalIterator(Of T)

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Public Overrides Property Value() As T
        Get
            '//TODO : implement...

        End Get
        Set(ByVal value As T)
            '//TODO : implement...

        End Set
    End Property

    Public Shadows Function Clone() As SampleBidirectionalIterator(Of T)
        Dim ret As InputIterator(Of T) = Nothing
        Call CloneImp(ret)
        Return CType(ret, SampleBidirectionalIterator(Of T))
    End Function

    Public Shared Shadows Operator =(ByVal lhs As SampleBidirectionalIterator(Of T), _
                                     ByVal rhs As SampleBidirectionalIterator(Of T)) As Boolean
        Return lhs.CompareImp(rhs)
    End Operator

    Public Shared Shadows Operator <>(ByVal lhs As SampleBidirectionalIterator(Of T), _
                                      ByVal rhs As SampleBidirectionalIterator(Of T)) As Boolean
        Return Not lhs.CompareImp(rhs)
    End Operator

    Public Shadows Function MoveNext() As SampleBidirectionalIterator(Of T)
        MoveNextImp()
        Return Me
    End Function

    Public Shadows Function MovePrev() As SampleBidirectionalIterator(Of T)
        MovePrevImp()
        Return Me
    End Function

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Protected Overrides Sub CloneImp(ByRef itr As BidirectionalIterator(Of T))
        Dim ret As BidirectionalIterator(Of T) = Nothing
        '//TODO : implement...

        itr = ret
    End Sub

    Protected Overrides Function CompareImp(ByVal itr As InputIterator(Of T)) As Boolean
        Dim ret As Boolean = False
        '//TODO : implement...

        Return ret
    End Function

    Protected Overrides Sub MoveNextImp()
        '//TODO : implement...

    End Sub

    Protected Overrides Sub MovePrevImp()
        '//TODO : implement...

    End Sub

End Class

public class SampleBidirectionalIterator<T> : BidirectionalIterator<T> {

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    public override T Value {
        get {
            //TODO : implement...

            return default( T );
        }
        set {
            //TODO : implement...

        }
    }
    public new SampleBidirectionalIterator<T> Clone( ) {
        BidirectionalIterator<T> itr = null;
        CloneImp( ref itr );
        return (SampleBidirectionalIterator<T>)itr;
    }
    public static bool operator ==( SampleBidirectionalIterator<T> itr1,
                                    SampleBidirectionalIterator<T> itr2 ) {
        return itr1.CompareImp( itr2 );
    }
    public static bool operator !=( SampleBidirectionalIterator<T> itr1,
                                    SampleBidirectionalIterator<T> itr2 ) {
        return !( itr1.CompareImp( itr2 ) );
    }
    public new SampleBidirectionalIterator<T> MoveNext( ) {
        MoveNextImp( );
        return this;
    }
    public new SampleBidirectionalIterator<T> MovePrev( ) {
        MovePrevImp( );
        return this;
    }

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    protected override void CloneImp( ref BidirectionalIterator<T> itr ) {
        BidirectionalIterator<T> ret = null;
        //TODO : implement...

        itr = ret;
    }
    protected override bool CompareImp( InputIterator<T> itr ) {
        bool ret = false;
        //TODO : implement...

        return ret;
    }
    protected override void MoveNextImp( ) {
        //TODO : implement...

    }
    protected override void MovePrevImp( ) {
        //TODO : implement...

    }
}

 

ランダムアクセス反復子の例

Public Class SampleRandomAccessIterator(Of T)

    Inherits RandomAccessIterator(Of T)

    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Public Overrides Property Value() As T
        Get
            '//TODO : implement...

        End Get
        Set(ByVal value As T)
            '//TODO : implement...

        End Set
    End Property

    Public Shadows Function Clone() As SampleRandomAccessIterator(Of T)
        Dim ret As InputIterator(Of T) = Nothing
        Call CloneImp(ret)
        Return CType(ret, SampleRandomAccessIterator(Of T))
    End Function

    Public Shared Shadows Operator =(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return lhs.CompareImp(rhs)
    End Operator

    Public Shared Shadows Operator <>(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                      ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return Not lhs.CompareImp(rhs)
    End Operator

    Public Shadows Function MoveNext() As SampleRandomAccessIterator(Of T)
        MoveNextImp()
        Return Me
    End Function

    Public Shadows Function MovePrev() As SampleRandomAccessIterator(Of T)
        MovePrevImp()
        Return Me
    End Function

    Public Overrides Sub Advance(ByVal idx As Integer)
        '//TODO : implement...

    End Sub

    Default Public Overrides Property At(ByVal idx As Integer) As T
        Get
            '//TODO : implement...

        End Get
        Set(ByVal value As T)
            '//TODO : implement...

        End Set
    End Property

    Public Shadows Shared Operator +(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal n As Integer) As SampleRandomAccessIterator(Of T)
        Dim ret As SampleRandomAccessIterator(Of T) = lhs.Clone()
        Call ret.Advance(n)
        Return ret
    End Operator

    Public Shadows Shared Operator -(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal n As Integer) As SampleRandomAccessIterator(Of T)
        Dim ret As SampleRandomAccessIterator(Of T) = lhs.Clone()
        Call ret.Advance(-1 * n)
        Return ret
    End Operator

    Public Shared Shadows Operator -(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal rhs As SampleRandomAccessIterator(Of T)) As Integer
        Return rhs.DistanceImp(lhs)
    End Operator

    Public Shared Shadows Operator <(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return (lhs - rhs) < 0
    End Operator

    Public Shared Shadows Operator >(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                     ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return (lhs - rhs) > 0
    End Operator

    Public Shared Shadows Operator <=(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                      ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return (lhs - rhs) <= 0
    End Operator

    Public Shared Shadows Operator >=(ByVal lhs As SampleRandomAccessIterator(Of T), _
                                      ByVal rhs As SampleRandomAccessIterator(Of T)) As Boolean
        Return (lhs - rhs) >= 0
    End Operator


    '//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    Protected Overrides Sub CloneImp(ByRef itr As RandomAccessIterator(Of T))
        Dim ret As RandomAccessIterator(Of T) = Nothing
        '//TODO : implement...

        itr = ret
    End Sub

    Protected Overrides Function CompareImp(ByVal itr As InputIterator(Of T)) As Boolean
        Dim ret As Boolean = False
        '//TODO : implement...

        Return ret
    End Function

    Protected Overrides Sub MoveNextImp()
        '//TODO : implement...

    End Sub

    Protected Overrides Sub MovePrevImp()
        '//TODO : implement...

    End Sub

    Protected Overrides Function DistanceImp(ByVal itr As RandomAccessIterator(Of T)) As Integer
        Dim ret As Integer = 0
        '//TODO : implement...

        Return ret
    End Function

End Class

public class SampleRandomAccessIterator<T> : RandomAccessIterator<T> {

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    public override T Value {
        get {
            //TODO : implement...

            return default( T );
        }
        set {
            //TODO : implement...

        }
    }
    public new SampleRandomAccessIterator<T> Clone( ) {
        RandomAccessIterator<T> itr = null;
        CloneImp( ref itr );
        return (SampleRandomAccessIterator<T>)itr;
    }
    public static bool operator ==( SampleRandomAccessIterator<T> itr1,
                                    SampleRandomAccessIterator<T> itr2 ) {
        return itr1.CompareImp( itr2 );
    }
    public static bool operator !=( SampleRandomAccessIterator<T> itr1,
                                    SampleRandomAccessIterator<T> itr2 ) {
        return !( itr1.CompareImp( itr2 ) );
    }
    public new SampleRandomAccessIterator<T> MoveNext( ) {
        MoveNextImp( );
        return this;
    }
    public new SampleRandomAccessIterator<T> MovePrev( ) {
        MovePrevImp( );
        return this;
    }
    public override void Advance( int idx ) {
        //TODO : implement...

    }
    public override T this[int idx] {
        get {
            //TODO : implement...

            return default( T );
        }
        set {
            //TODO : implement...

        }
    }
    public static SampleRandomAccessIterator<T> operator +( SampleRandomAccessIterator<T> lhs, int n ) {
        var ret = lhs.Clone( );
        ret.Advance( n );
        return ret;
    }
    public static SampleRandomAccessIterator<T> operator -( SampleRandomAccessIterator<T> lhs, int n ) {
        var ret = lhs.Clone( );
        ret.Advance( -1 * n );
        return ret;
    }
    public static int operator -( SampleRandomAccessIterator<T> lhs,
                                  SampleRandomAccessIterator<T> rhs ) {
        return rhs.DistanceImp( lhs );
    }
    public static bool operator <( SampleRandomAccessIterator<T> lhs,
                                   SampleRandomAccessIterator<T> rhs ) {
        return ( lhs - rhs ) < 0;
    }
    public static bool operator >( SampleRandomAccessIterator<T> lhs,
                                   SampleRandomAccessIterator<T> rhs ) {
        return ( lhs - rhs ) > 0;
    }
    public static bool operator <=( SampleRandomAccessIterator<T> lhs,
                                    SampleRandomAccessIterator<T> rhs ) {
        return ( lhs - rhs ) <= 0;
    }
    public static bool operator >=( SampleRandomAccessIterator<T> lhs,
                                    SampleRandomAccessIterator<T> rhs ) {
        return ( lhs - rhs ) >= 0;
    }

    //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    protected override void CloneImp( ref RandomAccessIterator<T> itr ) {
        RandomAccessIterator<T> ret = null;
        //TODO : implement...

        itr = ret;
    }
    protected override bool CompareImp( InputIterator<T> itr ) {
        bool ret = false;
        //TODO : implement...

        return ret;
    }
    protected override void MoveNextImp( ) {
        //TODO : implement...

    }
    protected override void MovePrevImp( ) {
        //TODO : implement...

    }
    protected override int DistanceImp( RandomAccessIterator<T> itr ) {
        int ret = 0;
        //TODO : implement...

        return ret;
    }

}

 

 


Copyright(C) 2011-2012 Show MATSUOKA.
Powered by Prefab.