Simon Strandgaard
10/2/2003 1:01:00 PM
On Wed, 01 Oct 2003 18:20:28 +0200, Robert Klemme wrote:
>
> "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 ?
Silly me, Now I have removed the sentinels completely.
Much easier to understand.
>> 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.
thanks :-)
> 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.)
I wait breaking it up into more specific classes/modules.
First I want the bidirectional iterator to do what it is suppose to in a
nice way. Then yes, It should probably be spitted up into something like
this.
>> suggestions for improving the code is very welcome :-)
>
> I'm missing a most basic forward readonly iterator or did I overlook
> something?
see above.
> See further changes below
[snip policies for iteration]
I now do the yield(current) instead of yield(self).. thanks.
I have abandoned the sentinel concept.
I now use a #is_done? method instead of #has_successor?.
testcase for Iterator::Range is now passing OK.
Any suggestions for what more a typical bidirectional iterator should do?
--
Simon Strandgaard
server> ruby test_iterator.rb
Loaded suite TestIterator
Started
....................
Finished in 0.022675 seconds.
19 tests, 21 assertions, 0 failures, 0 errors
server> expand -t2 iterator.rb
module Iterator
# issues:
# * should each/reverse_each reset the position ?
class Base
def first; nil end
def successor; nil end
def is_done?; true end
def last; nil end
def predecessor; nil end
def current; nil end
def current=(value); nil end
def each
first # perhaps we want to continue from current position ?
until is_done?
yield(current)
successor
end
end
def reverse_each
last
until is_done?
yield(current)
predecessor
end
end
def reverse
Reverse.new(self)
end
include Enumerable
end
# purpose:
# iterate over a collection (Array and similar classes)
class Collection < Iterator::Base
attr_reader :position
def initialize(data)
@data = data
first
end
def first; @position = 0 end
def successor; @position += 1 end
def last; @position = @data.size-1 end
def predecessor; @position -= 1 end
def is_done?; (@position < 0) or (@position >= @data.size) end
def current; @data[@position] end
def current=(value); @data[@position] = value end
end
# purpose:
# a decorator which reverses the direction of an iterator
class Reverse < Iterator::Base
def initialize(iterator); @i = iterator end
def position; @i.position end
def first; @i.last end
def successor; @i.predecessor end
def last; @i.first end
def predecessor; @i.successor end
def is_done?; @i.is_done? end
def current; @i.current end
def current=(value); @i.current = value end
end
# purpose:
# make one iterator out of to iterators
class Range < Iterator::Base
def initialize(start, stop)
super()
@start = start
@stop = stop
first
end
def position; @i.position end
def first; @i = @start.clone end
def successor; @i.successor end
def last; @i = @stop.clone end
def predecessor; @i.predecessor end
def is_done?
(@i.position < @start.position) or (@i.position > @stop.position)
end
def current; @i.current; end
def current=(value); @i.current = value; end
end
# purpose:
# concat many iterators into one
class Iterator < Iterator::Base
def initialize(iterators)
@iterators = iterators
first
end
def skip_successors
while @iterators[@position].is_done?
@position += 1
return if @position >= @iterators.size
@iterators[@position].first
end
end
def first
@position = 0
@iterators[@position].first
skip_successors
end
def successor
@iterators[@position].successor
skip_successors
end
def skip_predecessors
while @iterators[@position].is_done?
@position -= 1
return if @position < 0
@iterators[@position].last
end
end
def last
@position = @iterators.size-1
@iterators[@position].last
skip_predecessors
end
def predecessor
@iterators[@position].predecessor
skip_predecessors
end
def is_done?
(@position < 0) or (@position >= @iterators.size)
end
def current
@iterators[@position].current
end
def current=(value)
@iterators[@position].current = value
end
end
end # module Iterator
class Array
def create_iterator
Iterator::Collection.new(self)
end
end
server> expand -t2 test_iterator.rb
require 'test/unit'
require 'iterator'
class TestIterator < Test::Unit::TestCase
def test_collection_compare
b = (0..8).to_a.create_iterator
class << b; alias p position end
b.successor
a = b.clone
b.successor
assert_equal([true, true, false], [a.p<b.p, a.p<=b.p, a.p==b.p])
a.successor
assert_equal([false, true, true], [a.p<b.p, a.p<=b.p, a.p==b.p])
a.successor
assert_equal([false, false, false], [a.p<b.p, a.p<=b.p, a.p==b.p])
end
def test_collection_is_done
input = [-1, 0, 1, 2, 3]
exp = [true, false, false, false, true]
i = (0..2).to_a.create_iterator
i.first
class << i
attr_writer :position
end
res = input.map{|p| i.position=p; i.is_done?}
assert_equal(exp, res)
end
def test_collection_empty
iterator = [].create_iterator
iterator.first
assert_equal(true, iterator.is_done?)
end
def test_collection_exercise_successor
iterator = (1..5).to_a.create_iterator
res = []
iterator.first
until iterator.is_done?
res << iterator.current
iterator.successor
end
assert_equal((1..5).to_a, res)
end
def test_collection_exercise_predecessor
iterator = (1..5).to_a.create_iterator
res = []
iterator.last
until iterator.is_done?
res << iterator.current
iterator.predecessor
end
assert_equal((1..5).to_a.reverse, res)
end
def test_collection_each
iterator = (1..5).to_a.create_iterator
assert_equal((1..5).to_a, iterator.to_a)
end
def test_collection_reverse_each
iterator = (1..5).to_a.create_iterator
res = []
iterator.reverse_each{|i| res << i }
assert_equal((1..5).to_a.reverse, res)
end
def test_collection_assignment
data = (1..5).to_a
iterator = data.create_iterator
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
res = []
res << i.current
i.successor
res << i.current
i.successor
res << i.current
res << i.is_done?
i.predecessor
res << i.current
i.predecessor
res << i.current
res << i.is_done?
assert_equal([0, 1, 2, false, 1, 0, false], res)
end
def test_collection_exercise_position
iterator = (0..3).to_a.create_iterator
res = []
iterator.first
until iterator.is_done?
res << iterator.position
iterator.successor
end
assert_equal((0..3).to_a, res)
end
def test_reverse_exercise_successor
iterator = (1..5).to_a.create_iterator.reverse
assert_equal((1..5).to_a, iterator.to_a.reverse)
end
def test_reverse_exercise_predecessor
iterator = (1..5).to_a.create_iterator.reverse.reverse
assert_equal((1..5).to_a, iterator.to_a)
end
def test_reverse_exercise_position
iterator = (0..3).to_a.create_iterator.reverse
res = []
iterator.first
until iterator.is_done?
res << iterator.position
iterator.successor
end
assert_equal((0..3).to_a.reverse, res)
end
def test_range_exercise_successor
data = (0..4).to_a
i = data.create_iterator
i.successor
a = i.clone
i.successor
i.successor
b = i.clone
iterator = Iterator::Range.new(a, b)
assert_equal((1..3).to_a, iterator.to_a)
end
def test_range_exercise_predecessor
data = (0..4).to_a
i = data.create_iterator
i.successor
a = i.clone
i.successor
i.successor
b = i.clone
iterator = Iterator::Reverse.new(Iterator::Range.new(a, b))
assert_equal((1..3).to_a.reverse, iterator.to_a)
end
def test_iterator_exercise_successor
i0 = [].create_iterator # an obstacle which should be ignored
i1 = (1..3).to_a.create_iterator
i2 = [].create_iterator # an obstacle which should be ignored
i3 = (5..7).to_a.create_iterator
i4 = [].create_iterator # an obstacle which should be ignored
iterator = Iterator::Iterator.new([i0, i1, i2, i3, i4])
assert_equal((1..3).to_a + (5..7).to_a, iterator.to_a)
end
def test_iterator_exercise_predecessor
i0 = [].create_iterator # an obstacle which should be ignored
i1 = (1..3).to_a.create_iterator
i2 = [].create_iterator # an obstacle which should be ignored
i3 = (5..7).to_a.create_iterator
i4 = [].create_iterator # an obstacle which should be ignored
iterator = Iterator::Reverse.new(
Iterator::Iterator.new([i0, i1, i2, i3, i4]))
assert_equal((1..3).to_a + (5..7).to_a, iterator.to_a.reverse)
end
def test_iterator_assignment
data1 = (1..3).to_a
data2 = (5..7).to_a
i1 = data1.create_iterator
i2 = data2.create_iterator
iterator = Iterator::Iterator.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
def test_iterator_sort
i1 = [5, 3, 1].create_iterator
i2 = [2, 4, 6].create_iterator
iterator = Iterator::Iterator.new([i1, i2])
assert_equal((1..6).to_a, iterator.sort)
end
end
if $0 == __FILE__
require 'test/unit/ui/console/testrunner'
Test::Unit::UI::Console::TestRunner.run(TestIterator)
end
server>