Scribd
Upload
7 views30 pages

Lecture 3

3

Uploaded by

dovanminh253
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views30 pages

Lecture 3

3

Uploaded by

dovanminh253
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 30

61FIT3SE1 - Software Engineering 1

Lecture 3
Iteration Abstraction
Outline
• Iteration
• Why iteration abstraction?
• Generator
• Iteration in Java
• Implement an iteration
• Using iteration
References

• Guttag, Liskov, Program development in Java, chapter 6


Why iteration abstraction?

• Problem: how to conveniently and efficiently iterate over a generic


collection of objects?
• Requirements: to support
• incremental (run-time) access
• unlimited collection size
• all types of collections
• index-based (e.g. arrays)
• non-index-based collections (e.g. sets)
Example: Elements of a Set

• How to sum the elements of a set?


• Basic algorithm:
Some intuitive solutions
• Add a method to return an array of elements
• Add an index-based access method
• Add an observer that returns vector elements
❑None is really suitable!

Figure: Abstract function of an IntSet


Return an array of elements
• This method is is inefficient
• …especially if the set is large
• it needs to make a copy of the list
Other two alternatives
• Add an index-based access method
• Similar to get(int index) method in java.util.ArrayList
• No improvement over for loop iteration

• Add an observer that returns vector elements


• May destroy Collection by exposing the rep
Iteration abstraction as a solution

• An abstraction that provides generic access to a collection's elements


• Incremental access:
• ask & get
• get: can also generate elements
• Supports unlimited collection size:
• no bounds on size
• Supports all types of collections:
• assumes no knowlege of the collection's rep
• specified as an interface
Generator

• Generates the “elements” incrementally


• Same public API but different internal mechanism depending on the
collection
• Pre-populated collections:
• generate indices over the elements incrementally
• Auto-populated collections:
• generate elements (and indices) incrementally
• often has a bound condition
Pre-populated generator
Auto-populated generator

• Elements (possibly up to a max value) are generated (or obtained from


another source) into the set when accessed via the generator

bound condition: elements are ≤ max


Iteration abstraction in Java framework

• Generators implement interface


java.util.Iterator
• Collections implement an iterator() method:
• returns an Iterator object
• Iterator defines 3 methods:
• hasNext: ask
• next: get
• remove
iterator() method & Iterator
Types with built-in iterators in Java framework

• Those that are subtype of : java.lang.Iterable


• Some common examples:
• Collection
• Lists: ArrayList, LinkedList
• Set
• Queue
Implements Iteration abstraction

• Specify an iterator() method


• Specify a generator as sub-type that implements Iterator
Specify an iterator method

• Common names: elements(), iterator()


• Effect: return an object of generator.

public Iterator iterator(){


return new Generator();
}
Specify a generator

• A private inner class of the collection class


• Implements java.util.Iterator
• Attribute
• keep track of the iteration state
• Operations:
• hasNext() and next()
• remove():optional
java.util.Iterator
Iterator.hasNext()
Iterator.next()
Iterator.remove()
Notes

• Notes:
• hasNext() and next() both check if there are more results to return
• next(): modifies the state of generator if a new result is returned
• remove(): only used for modifiable collections
Multiple iterators

iterator()

rIterator()
An independent reverse iterator
Example: LinkedList
Example: LinkedList

LinkedList

• iterator() returns a new instance of LinkedListGen


• LinkedListGen
• hasNext() checks ind against LinkedList.size()
• next() if still have element, returns element at index ind and increments
ind else throws an exception
Using iteration

• Generator object is used via iterator() methods


• Use while loop to iterate the elements
• Loop condition is controlled by:
❑ hasNext() or
❑ NoSuchElementException thrown by next()
Example using iteration

// Create an even number list


LinkedList list = new LinkedList<>();
for (int i = 0; i < 100; i++)
// even numbers
if (i % 2 == 0) list.add(i);
Iterator<Integer> g = list.iterator();
// loop controlled by hasNext
while (g.hasNext()) {
Integer x = g.next(); // use x
}
Example using iteration

// ...create list (as before)


Iterator g = list.iterator();
try {
while (true) {
Integer x = g.next(); // use x
}
} catch (NoSuchElementException e) {
// no more elements
}
Summary

• Iteration abstraction provides a convenient and efficient generic


method to iterate the elements of a collection
• Iteration abstraction is defined by a combination of an iterator
method and a generator
• iterator method creates a new generator
• Generator implements java.util.Iterator and is specified as an
inner class
• Java’s collection classes inherit java.lang.Iterable

You might also like