CS代考 CSE 10

Implementing an Iterator
18 October 2021 OSU CSE 1

Loose Ends

Copyright By PowCoder代写 加微信 powcoder

• In implementing several kernel interfaces so far, you have been given code in the
skeletons for the iterator method
• The code for this method is stylized and sometimes easy to adapt to a new situation, even if the code itself is hardly transparent!
– Several new Java issues arise …
18 October 2021 OSU CSE 2

• Recall: iterators offer a special way of getting sequential access to all elements/entries of a collection
• Because linked data structures are particularly appropriate for sequential
access, the List2 code is a good place to examine how iterators can be
implemented
18 October 2021 OSU CSE 3

iterator Contract for List Iterator iterator()
• Returns an iterator over the elements.
• Ensures:
~this.seen * ~this.unseen = this.left * this.right
18 October 2021 OSU CSE

iterator Contract for List Iterator iterator()
• Returns an iterator over the elements. • Ensures:
Iterator is an ~this.seen * ~this.unseen =
18 October 2021
this.left * this.right
libraries (in the package
java.util).
interface in the Java

iterator Contract for List These two variables stand for
• Returns an iterator over the elements.
• Ensures:
~this.seen * ~this.unseen = this.left * this.right
Iterator iterator()
18 October 2021 OSU CSE
the string of T already seen and the string of T not yet seen
while using the iterator.

For-Each Loops
• Since List extends the interface Iterable, you may write a for-each loop to “see” all elements of List s :
for (T x : s) {
// do something with x, but do // not call methods on s or // change the value of x
18 October 2021 OSU CSE 7

For-Each Loops
on each iteration, x is • Since List extends the interface
This declares x as a local
variable of type T in the loop;
aliased to a different element Iterable, you may write a for-each
loop to “see” all elements of List s :
for (T x : s) {
// do something with x, but do // not call methods on s or // change the value of x
18 October 2021 OSU CSE 8

For-Each Loops
The restrictions on what you may do withxandsin the
• Since List extends the interface loop body are critical; do not
Iterable, you may write a for-each loop to “see” all elements of List s :
for (T x : s) {
// do something with x, but do // not call methods on s or
// change the value of x
18 October 2021 OSU CSE 9
forget about them!

How a For-Each Loop Works
• The for-each loop above is actually syntactic sugar for the following code:
Iterator it = s.iterator(); while (it.hasNext()) {
T x = it.next();
// do something with x, but do // not call methods on s or
// change the value of x
18 October 2021 OSU CSE 10

How a For-Ea
• The for-each loop above is actually syntactic sugar for the following code:
Iterator it = s.iterator();
while (it.hasNext()) {
T x = it.next();
// do something with x, but do // not call methods on s or
// change the value of x
18 October 2021 OSU CSE 11
List returns a value of type
te Iterator.

How a For-Eac
methods of this Iterator
variable are used in the iteration.
• The for-each loop above is actually syntactic sugar for the following code:
Iterator it = s.iterator(); while (it.hasNext()) {
T x = it.next();
// do something with x, but do // not call methods on s or
// change the value of x
18 October 2021 OSU CSE 12

Iterating With iterator • This code has the following properties:
– It introduces aliases, so you must be careful to “follow the rules”; specifically, the loop body should not call any methods on s
– If what you want to do to each element is to change it (when T is a mutable type), then the
approach does not work because the loop body should not change the value of x
• With List, you could just use the kernel methods to visit the entries in the same order
18 October 2021 OSU CSE 13

The Iterator Interface • For the iterator method, the kernel
class returns a reference to an instance of a nested class (List2Iterator) that
implements the Iterator interface
• The code in that class implements these methods:
– boolean hasNext() – T next()
– void remove()
18 October 2021 OSU CSE 14

The remove method is The Iterator Interface
described as “optional” in the interface Iterator, and
• Fortheiterator
class returns a reference to an instance of
l a nested class (List2Iterator) that
implements the Iterator interface
• The code in that class implements these methods:
– boolean hasNext() – T next()
– void remove()
use doing so can cause serious
18 October 2021 OSU CSE 15

hasNext boolean hasNext()
• Returns true iff the iteration has more elements (i.e., there are any “unseen” elements).
• Ensures:
hasNext = (~this.unseen /= < >)
18 October 2021 OSU CSE

• Returns the next element in the iteration (i.e., the next “unseen” element, which becomes a “seen” element).
• Aliases: reference returned by next
• Updates: ~this (i.e., the iterator, not the collection)
• Requires:
~this.unseen /= < >
• Ensures:
~this.seen * ~this.unseen = #~this.seen * #~this.unseen and
~this.seen = #~this.seen * 18 October 2021 OSU CSE

Iterator for List2 this = (<18>, <6>)
preStart lastLeft
finish leftLen
data data data next next next
18 October 2021
OSU CSE 18

Iterator for List2 The object created by a call
to iterator is an instance this = (<18>, <6>)
of the nested class List2Iterator …
preStart lastLeft
finish leftLen
data data data next next next
18 October 2021
result of iterator OSU CSE

Iterator for List2 … and it holds a reference to
data data data next next next
entry in ~this.unseen.
preStart lastLeft
finish leftLen
18 October 2021
result of iterator OSU CSE

for List2 ns
The next m
the data in that node, also
this = (<18>, <6>) advancing current to the
next node.
preStart lastLeft
finish leftLen
data data data next next next
18 October 2021
result of iterator OSU CSE

The hasNext method
Iterator for List2
checks whether current is
indicates that the last entry has been seen already).
preStart lastLeft
finish leftLen
data data data next next next
18 October 2021
result of iterator OSU CSE

A New Java Issue
• In the code inside the nested class List2Iterator, there are two references named this, so the name is ambiguous!
– The name this denotes the object of type List2Iterator (the nested class)
– The qualified name List2.this denotes the object of type List2 (the enclosing class)
• See this line of code in the List2Iterator constructor:
this.current = List2.this.preStart.next; 18 October 2021 OSU CSE 23

A New Java Issue
The class List2Iterator has an instance variable named
• In the code inside the nested class
current, and this is it. List2Iterator, there are two references
named this, so the name is ambiguous! – The name this denotes the object of type
List2Iterator (the nested class)
– The qualified name List2.this denotes the object
of type List2 (the enclosing class)
• See this line of code in the List2Iterator
constructor:
this.current = List2.this.preStart.next; 18 October 2021 OSU CSE 24

A New Java Issue
The class List2 has an instance variable named
• In the code inside the nested class
preStart, and this is it. List2Iterator, there are two references
named this, so the name is ambiguous! – The name this denotes the object of type
List2Iterator (the nested class)
– The qualified name List2.this denotes the object
of type List2 (the enclosing class)
• See this line of code in the List2Iterator
constructor:
this.current = List2.this.preStart.next; 18 October 2021 OSU CSE 25

• JavaLibrariesAPI:IterableandIterator
– http://docs.oracle.com/javase/8/docs/api/
18 October 2021 OSU CSE 26

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com