Bidirectional iterators, seeking advices

ruby-talk
1

“Simon Strandgaard” qj5nd7l02@sneakemail.com schrieb im Newsbeitrag
news:pan.2003.10.01.13.12.04.930935@sneakemail.com…

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 :slight_smile:

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

See further changes below

Regards

robert

–
Simon Strandgaard

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

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

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