bidirectional iterators, seeking advices

[Simon Strandgaard]

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?


suggestions for improving the code is very welcome

--
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 BidirectionalIterator
class Error < StandardError; end
class NotComparable < Error; end
def first; nil end
def successor; nil end
def has_successor?; false end
def last; nil end
def predecessor; nil end
def has_predecessor?; false end
def current; nil end
def current=(value); nil end
def each
first
while has_successor?
successor
yield(self)
end
end
include Enumerable
def <=>(other); raise NotComparable end
include Comparable
end

# purpose:
# iterate over a collection (Array and similar classes)
class CollectionIterator < BidirectionalIterator
attr_reader osition
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 osition
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 osition
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>

 

[Thomas Sondergaard]

question#1: any ideas if it makes sense not having a sentinel element?

I'd say no. Feel free to have one internally, but you don't have to show it
to the user of your iterator API. Encapsulate it in your Iterator#next
method. In STL it is exposed to make ordinary pointers work as iterators, as

question#3: which implementation of iterators do you think is ideal?
where do I have to look? java, stl, python?

Why? The history and nature of the implementation language/platform is
important. For instance in STL there are some hoops that the implementation
jumps through to make ordinary pointers (to a contiguous block of memory)
iterators. Including the use of trait classes (because you cannot assign
traits directly to a pointer class, there is no such class) and the use of
operator overloading, and the way the end is checked, ie. it !=
container.end(). These design considerations are invalid for ruby. The STL
iterator concept is finer grained with ForwardIterators,
BlahBlahIterators... Iterators in .net and Java are extremely simple, and
follows the basic GoF pattern pretty much to the letter, without anything
fancy.

Have you noticed that ruby's iterator concept (using each) is less general
than the concepts in java, STL, .net? In rubydotnet I can easily detect when
an object passed to ruby from .net is IEnumerable and implement 'each' on
the proxy in terms of the IEnumerable interface and mixin Enumerable, but
the reverse is not true, because the iteration state in ruby is "on the
stack", it is not encapsulated in an object. The same problem is causing
some headaches if you want to iterate in parallel over 2 or more
Enumerables. Less flexible, but more elegant.

What prompted you to look into this?

Cheers,

Tom

 

[Robert Klemme]

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 osition
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 osition
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 osition
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>

 

[Simon Strandgaard]

I'd say no. Feel free to have one internally, but you don't have to show it
to the user of your iterator API. Encapsulate it in your Iterator#next
method. In STL it is exposed to make ordinary pointers work as iterators, as
used in std::vector<> and ordinary contigious blocks of memory. It could
have been abstracted away in C++ too, but for STL performance is king!

Yes.. sentinels is ofthen introduced because of speed and less POLS.
Does any of you have a scheme where no sentinels are used (I prefer
POLS instead of speed) ???

I cannot find any resources on google describing how to do bidirectional
iterators without sentinels. Any ideas ???

Why? The history and nature of the implementation language/platform is
important.

[snip]

Damn I forgot to mention that intutitive code is prefered and that
speed does'nt matter to me. Is there an iterator scheme around which
doesn't make use of sentinels ?
[snip stl+dotnet]

Have you noticed that ruby's iterator concept (using each) is less general
than the concepts in java, STL, .net?

I consider rubys yield concept more as a higher order function call, than
an iterator. Yes the yield construction is less general than GOF-iterators.
[snip more dotnet]

What prompted you to look into this?

I am experimenting with a new datastructure for AEditor. When I
insert/remove stuff in the buffer the iterators has to follow, every
iterator is a observer of the model they iterate.

 

[Simon Strandgaard]

Silly me, Now I have removed the sentinels completely.
Much easier to understand.

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.

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 osition
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 osition
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>