Re: bidirectional iterators, seeking advices

"Simon Strandgaard" <[e-mail]> schrieb im Newsbeitrag
news:[e-mail]...
> The last 2 days I have been fooling around, making my own
> iterator hierarchy.
>
> question#1: any ideas if it makes sense not having a sentinel element?
>
> question#2: do you allways have it in the front?  or
> do you have it in both the front+back ?
>
> question#3: which implementation of iterators do you think is ideal?
> where do I have to look?   java, stl, python?

Dunno about Python, but I would only carefully use Java iterators as
model.  Though ListIterator is quite ok with respect to random access and
bidirectional iteration, they do not obey command query separation (i.e.
namely method next()).  C++ is better apart from the fact that I would not
use +, - etc. which you didn't.

IMHO C++ does a quite good job at separating the different aspects one
has:

 - iteration (forward, bidirectional, random access)
 - element access (read only, writable / deletable)

So in theory one could come up with 5 modules and combine them to classes.
Unfortunately one would not gain much by the modules other than the test
iter.kind_of? ModifyableIterator etc. because methods would have to be
implemented down the hierarchy... (This reminds me of the traits approach
that was referred to recently.  There was a paper about Traits for
Smalltalk.)

> suggestions for improving the code is very welcome :-)

I'm missing a most basic forward readonly iterator or did I overlook
something?

See further changes below

Regards

    robert


> --
> Simon Strandgaard
>
> server> ruby test_iterator.rb
> Loaded suite TestIterator
> Started
> .............F
> Finished in 0.019339 seconds.
>
>   1) Failure!!!
> test_reverse_range_each(TestIterator) [test_iterator.rb:136]:
> <[3, 2, 1]> expected but was
> <[2, 1, 0]>
>
> 14 tests, 16 assertions, 1 failures, 0 errors
> server> expand -t2 iterator.rb

class Iterator
   class Error < StandardError; end
   class NotComparable < Error; end

   def successor; nil end
   def has_successor?; false end

   def current; nil end

   def each
     first
     while has_successor?
       successor
       yield(current) # note: not self
     end
   end

  include Enumerable
end

class BidirectionalIterator < Iterator
  def predecessor; nil end
  def has_predecessor?; false end
end

module ModifiableIterator
  def current=(value); nil end
end

class RandomAccessIterator < BidirectionalIterator
  def first; nil ; end
  def last; nil ; end
  def set_position(pos); nil; end
end

> # purpose:
> # iterate over a collection (Array and similar classes)
> class CollectionIterator < BidirectionalIterator

  include ModifyableIterator

>   attr_reader :position
>   def initialize(data)
>     @data = data
>     first
>   end
>   def first
>     @position = -1 # a sentinel element
>   end
>   def successor
>     @position += 1
>   end
>   def has_successor?
>     @position < @data.size-1
>   end
>   def last
>     @position = @data.size  # a sentinel element
>   end
>   def predecessor
>     @position -= 1
>   end
>   def has_predecessor?
>     @position > 0
>   end
>   def current
>     @data[@position]
>   end
>   def current=(value)
>     @data[@position] = value
>   end
>   def <=>(other)
>     #raise NotComparable
>     @position <=> other.position
>   end
> end
>
> # purpose:
> # a decorator which reverses the direction of an iterator
> class ReverseIterator < BidirectionalIterator
>   def initialize(iterator); @i = iterator; end
>   def first; @i.last; end
>   def successor; @i.predecessor; end
>   def has_successor?; @i.has_predecessor?; end
>   def last; @i.first; end
>   def predecessor; @i.successor; end
>   def has_predecessor?; @i.has_successor?; end
>   def current; @i.current; end
>   def current=(value); @i.current = value; end
> end
>
> # purpose:
> # make one iterator out of to iterators
> #
> # first element is considered to be sentinel
> # and will therefore be ignored.
> class RangeIterator < BidirectionalIterator
>   def initialize(start, stop)
>     @start = start
>     @stop = stop
>     first
>   end
>   def first; @i = @start.clone end
>   def successor; @i.successor end
>   def has_successor?; @i < @stop end
>   def last; @i = @stop.clone end
>   def predecessor; @i.predecessor end
>   def has_predecessor?; @i > @start end
>   def current; @i.current; end
>   def current=(value); @i.current = value; end
> end
>
> class IteratorIterator < BidirectionalIterator
>   def initialize(iterators)
>     @iterators = iterators
>     first
>   end
>   def first
>     @position = 0
>     @iterators[@position].first
>   end
>   def successor
>     @iterators[@position].successor
>     unless @iterators[@position].has_successor?
>       @position += 1
>       @iterators[@position].first if has_successor?
>     end
>   end
>   def has_successor?
>     not (@position >= @iterators.size)
>   end
>   def current
>     @iterators[@position].current
>   end
>   def current=(value)
>     @iterators[@position].current = value
>   end
> end
>
> class Array
>   def create_iterator
>     CollectionIterator.new(self)
>   end
> end
> server> expand -t2 test_iterator.rb
> require 'test/unit'
> require 'iterator'
>
> class TestIterator < Test::Unit::TestCase
>   def test_base_notcomparable
>     i = BidirectionalIterator.new
>     assert_raises(BidirectionalIterator::NotComparable) { i > i }
>   end
>   def test_collection_compare
>     b = (0..8).to_a.create_iterator
>     b.successor # skip sentinel
>     b.successor
>     a = b.clone
>     b.successor
>     assert_equal([true, true, false], [a<b, a<=b, a==b])
>     a.successor
>     assert_equal([false, true, true], [a<b, a<=b, a==b])
>     a.successor
>     assert_equal([false, false, false], [a<b, a<=b, a==b])
>   end
>   def test_collection_has_successor
>     input = [-1, 0, 1, 2, 3]
>     exp = [true, true, true, false, false]
>     i = (0..2).to_a.create_iterator
>     i.first
>     class << i
>       attr_writer :position
>     end
>     res = input.map{|p| i.position=p; i.has_successor?}
>     assert_equal(exp, res)
>   end
>   def test_collection_has_predecessor
>     input = [-1, 0, 1, 2, 3]
>     exp = [false, false, true, true, true]
>     i = (0..2).to_a.create_iterator
>     i.last
>     class << i
>       attr_writer :position
>     end
>     res = input.map{|p| i.position=p; i.has_predecessor?}
>     assert_equal(exp, res)
>   end
>   def test_collection_successor_empty
>     iterator = [].create_iterator
>     iterator.first
>     assert_equal(false, iterator.has_successor?)
>   end
>   def test_collection_successor_elements
>     iterator = (1..5).to_a.create_iterator
>     res = []
>     iterator.first
>     while iterator.has_successor?
>       iterator.successor
>       res << iterator.current
>     end
>     assert_equal((1..5).to_a, res)
>   end
>   def test_collection_predecessor_elements
>     iterator = (1..5).to_a.create_iterator
>     res = []
>     iterator.last
>     while iterator.has_predecessor?
>       iterator.predecessor
>       res << iterator.current
>     end
>     assert_equal((1..5).to_a.reverse, res)
>   end
>   def test_collection_each
>     iterator = (1..5).to_a.create_iterator
>     ary = iterator.map{|i| i.current }
>     assert_equal((1..5).to_a, ary)
>   end
>   def test_collection_assignment
>     data = (1..5).to_a
>     iterator = data.create_iterator
>     iterator.successor # skip sentinel
>     iterator.successor
>     iterator.current = 5
>     assert_equal([1, 5, 3, 4, 5], data)
>   end
>   def test_collection_bidirectional
>     i = (0..2).to_a.create_iterator
>     i.first
>     i.successor # skip sentinel
>     res = []
>     res << i.current
>     i.successor
>     res << i.current
>     i.successor
>     res << i.current
>     res << i.has_successor?
>     i.predecessor
>     res << i.current
>     i.predecessor
>     res << i.current
>     res << i.has_predecessor?
>     assert_equal([0, 1, 2, false, 1, 0, false], res)
>   end
>   def test_reverse_each1
>     iterator = (1..5).to_a.create_iterator
>     ri = ReverseIterator.new(iterator)
>     ary = ri.map{|i| i.current }
>     assert_equal((1..5).to_a.reverse, ary)
>   end
>   def test_reverse_each2
>     iterator = (1..5).to_a.create_iterator
>     ri0 = ReverseIterator.new(iterator)
>     ri = ReverseIterator.new(ri0)
>     ary = ri.map{|i| i.current }
>     assert_equal((1..5).to_a, ary)
>   end
>   def test_range_each
>     data = (0..4).to_a
>     i = data.create_iterator
>     i.successor # skip sentinel
>     a = i.clone
>     i.successor
>     i.successor
>     i.successor
>     b = i.clone
>     iterator = RangeIterator.new(a, b)
>     res = iterator.map{|i| i.current}
>     assert_equal((1..3).to_a, res)
>   end
>   def test_reverse_range_each
>     data = (0..4).to_a
>     i = data.create_iterator
>     i.successor # skip sentinel
>     a = i.clone
>     i.successor
>     i.successor
>     i.successor
>     b = i.clone
>     iterator = ReverseIterator.new(RangeIterator.new(a, b))
>     res = iterator.map{|i| i.current}
>     assert_equal((1..3).to_a.reverse, res)
>   end
>   def xtest_iterator_iterator_each
>     i1 = (1..3).to_a.create_iterator
>     i2 = (5..7).to_a.create_iterator
>     iterator = IteratorIterator.new([i1, i2])
>     ary = iterator.map{|i| i.current }
>     assert_equal((1..3).to_a + (5..7).to_a, ary)
>   end
>   def xtest_iterator_iterator_assignment
>     data1 = (1..3).to_a
>     data2 = (5..7).to_a
>     i1 = data1.create_iterator
>     i2 = data2.create_iterator
>     iterator = IteratorIterator.new([i1, i2])
>     iterator.successor
>     iterator.current = 5
>     iterator.successor
>     iterator.successor
>     iterator.successor
>     iterator.current = 3
>     assert_equal([1, 5, 3, 5, 3, 7], data1 + data2)
>   end
> end
>
> if $0 == __FILE__
>   require 'test/unit/ui/console/testrunner'
>   Test::Unit::UI::Console::TestRunner.run(TestIterator)
> end
> server>