The latest instance of the course can be found at: O1: 2024

Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.

Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit.

Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.

# Chapter 5.5: Looping through Elements

Questions Answered: How do I process a lot of data in one go? How do I repeat an operation on each of the elements in a collection?

Topics: Iterating over a collection with a `for` loop. Implementing algorithms by combining loops with local variables.

What Will I Do? Read and work on a few pocket-sized assignments. There will be more practice problems on these topics in the next chapter.

Rough Estimate of Workload:? A bit over an hour.

Points Available: A30.

Related Modules: AuctionHouse1, ForLoops (new).

## Background for Example: Items Whose Price Changes

In Chapter 5.1, you hopefully wrote at least a `FixedPriceSale` class that represents items put up for sale at a set price. The same chapter also featured two optional activities that tasked you to implement classes `EnglishAuction` and `DutchAuction`. In this chapter, we’ll work with `EnglishAuction`.

If you didn’t implement `EnglishAuction` earlier, no problem. Much like a `FixedPriceSale` object, an `EnglishAuction` too represents an item put up for sale. An auction, too, has a `price`, a potential `buyer`, and an `advanceOneDay` method just like a `FixedPriceSale` does. The difference is that in an `EnglishAuction`, the item’ price goes up as potential buyers place higher bids on it. That’s pretty much all you need to know about `EnglishAuction`s.

Still, if you have the time and inclination...

... go ahead and do the optional `EnglishAuction` assignment from Chapter 5.1 now or look at its solution below.

An implementation of `EnglishAuction`

```class EnglishAuction(val description: String, val startingPrice: Int, duration: Int):

private var highest = Bid(None, startingPrice)
private var secondHighest = Bid(None, startingPrice)
private var remainingDays = duration

def daysLeft = this.remainingDays

if this.isOpen then
this.remainingDays -= 1

def isOpen = this.remainingDays > 0

def hasNoBids = this.highest.isInitialBid

def isExpired = !this.isOpen && this.hasNoBids

def price =
if this.secondHighest.isInitialBid then
this.startingPrice
else
min(this.secondHighest.limit + 1, this.highest.limit)

def requiredBid = if this.hasNoBids then this.startingPrice else this.price + 1

def bid(bidder: String, amount: Int) =
val newBid = Bid(Some(bidder), amount)
if this.isOpen && amount >= this.requiredBid then
this.secondHighest = if newBid.beats(this.highest) then this.highest
else newBid.winner(this.secondHighest)
this.highest = newBid.winner(this.highest)
end if
this.highest == newBid

override def toString = this.description

end EnglishAuction
```

For this chapter, the relevant bit is that an item’s price isn’t fixed but determined by the bids that have been placed on the item.

There’s a `bid` method for placing a bid. It affects the item’s current price.

The auxiliary class `Bid` comes in the AuctionHouse1 module. It’s used internally by `EnglishAuction` and isn’t important for this chapter.

## Chapter Goal: An `AuctionHouse` Class

So, let’s assume we have an existing `EnglishAuction` class that represents individual items. We’ll now look into implementing a class `AuctionHouse`. The plan is that each `AuctionHouse` instance should represent a site that runs auctions and contains a number of `EnglishAuction`s.

Here’s an outline for the class:

```class AuctionHouse(val name: String):

private val items = Buffer[EnglishAuction]()

this.items += item

def removeItem(item: EnglishAuction) =
this.items -= item

override def toString = this.name

// We'll add more methods here.

end AuctionHouse
```

Each `AuctionHouse` object has its own buffer that we can access through the `items` variable. We may add items to the buffer, and we may remove them, too.

Suppose we’d now like to add the following methods:

• a method that advances every auction in the auction house (i.e., calls `advanceOneDay` on every `EnglishAuction` object stored in the `items` buffer;

• a method for computing the total price of all auctions;

• a method for computing the average price of all auctions;

• a method for finding the auction with the highest current price;

• a method for counting how many auctions are currently open; and

• a method that produces all the auctions that a given buyer has won.

See below for examples of how these methods should work.

### Usage examples

We should be able to create a new `AuctionHouse` instance like this:

```val house = AuctionHouse("ReBay")house: AuctionHouse = ReBay
```

The `priciest` method should return the most expensive item. We’ll have it return `None` if the auction house contains no items, which is initially the case:

```house.priciestres0: Option[EnglishAuction] = None
```

Let’s set up three auctions and use `addItem` to add them to the auction house. Each auction has a description, an initial price, and a duration in days.

```val bag = EnglishAuction("A glorious handbag", 100, 14)bag: EnglishAuction = A glorious handbag
house.addItem(bag)val camera = EnglishAuction("Nikon COOLPIX", 150, 3)camera: EnglishAuction = Nikon COOLPIX

As illustrated in the output below, calling `nextDay` on the `AuctionHouse` shortens the remaining duration (`daysLeft`) of both the bag and the camera (and indeed all the open auctions in the auction house) by one.

```println(bag.daysLeft + ", " + camera.daysLeft)14, 3
house.nextDay()
house.nextDay()
println(bag.daysLeft + ", " + camera.daysLeft)12, 1
```

`totalPrice` and `averagePrice` return some basic statistics:

```house.totalPriceres1: Int = 251
house.averagePriceres2: Double = 83.66666666666667
```

As prospective buyers bid on items, the prices go up. This shows up in the statistics:

```bag.bid("Olivia", 200)res3: Boolean = true
bag.bid("Mehdi", 170)res4: Boolean = false
camera.bid("Olivia", 190)res5: Boolean = true
house.totalPriceres6: Int = 322
```

The `bid` method places a bid on an item. Competing bids can raise the price of an `EnglishAuction`. (The exact bidding procedure is irrelevant for present purposes; see class `EnglishAuction` for that. All you need to know here is that an item’s price can change when `bid` is called.)

An `AuctionHouse` should know how to compute and return the updated total price.

The bidding raised the bag’s price and it is now the item with with the highest current price:

```house.priciestres7: Option[EnglishAuction] = Some(A glorious handbag)
```

All three auctions are still open but the camera has only one day left and will close the next time we call `nextDay`. This shows in how the `AuctionHouse` object responds when we ask it to count the open auctions:

```house.numberOfOpenItemsres8: Int = 3
house.nextDay()house.numberOfOpenItemsres9: Int = 2
```

```house.purchasesOf("Olivia")res10: Vector[EnglishAuction] = Vector(A glorious handbag, Nikon COOLPIX)
house.purchasesOf("Mehdi")res11: Vector[EnglishAuction] = Vector()
```

`purchasesOf` returns a vector that contains these auctions that the person has already won (such as the camera, whose high bidder was Olivia when the item closed) as well as any open auctions where the person is currently the high bidder (such as Olivia’s bag).

### What do we need?

What do the `AuctionHouse` methods have in common?

1. Each of the methods needs to work through all the items of the `AuctionHouse`, that is, all the elements in the `items` buffer.

2. Each of the methods should repeat a particular operation multiple times, once per item.

Performing an operation on each element in a collection is an extremely common thing for a program to do. Nearly all interesting computer programs repeat operations, one way or another.

In this chapter, you’ll learn to use a Scala command that enables you to do just that. We’ll use this command to implement the `AuctionHouse` methods one by one.

## Implementing `nextDay`

Let’s sketch out `nextDay`:

```def nextDay() =
For each of the elements in this auction house’s list of items in turn, do this:
- Call advanceOneDay on the item.```

A refined pseudocode:

```def nextDay() =
For each of the elements in this auction house’s list of items in turn, do this:
- Take that element (i.e., a reference to auction being processed)
and store it in a local variable.
- Call advanceOneDay on that element.```

Refining further we get:

```def nextDay() =
For each of the elements in this.items in turn, do this:
- Store the element in a most-recent holder named, say, current.

Even though this is just pseudocode, the animation illustrates how the same section of the program gets executed multiple times: a so-called loop (silmukka) forms within the method and repeats a particular operation. During each loop cycle, a new `current` variable with a new value is created as the loop iterates over the collection’s elements.

## `for` Loops

### From pseudocode to Scala

Here’s one way to implement `nextDay`. This implementation works exactly as illustrated in the animation above.

```def nextDay() =
for current <- this.items do

```

The keywords `for` and `do` define a loop like this.

You can read the beginning as “for each item `current` in `this.items`, do”.

We choose a name for our variable; here we’ve chosen to name it `current`. This name refers to a different element during each iteration of the loop. The elements are fetched from a collection that...

... we specify using a left-pointing arrow `<-`.

The loop body will be executed once per element in `this.items`. The body is indented further right in the usual fashion.

You may write an end marker on the loop. In most cases, people prefer to leave them out, but when a method is a bit complicated, an end marker may clarify it. Feel free to write `end for` on every loop if you prefer.

### The structure of a `for` loop

Here’s a more generic pseudocode for performing an operation on every element of a collection:

```for variable <- collectionOfElements do
Do something with the element stored in the variable.
end for    // This last line is optional.```

A `for` loop contains a variable definition; the variable stores the element being currently processed, and therefore has the role of a most-recent holder.

You can loop over any collection, such as a buffer (as in our first example above), a vector, a string (Chapter 5.6), an array (Chapter 12.1), a lazy-list (Chapter 7.2), or a map (Chapter 9.2).

When you apply a `for` loop to a numerically indexed collection such as a buffer or a vector, as we did above, the loop traverses the elements in order, from index zero upwards.

## On the Roles of Variables

In Chapter 2.6, we noted that variables can be classified by the role they have in the program.

That earlier chapter featured examples of what we labeled most-recent holders. For example, we replaced the value of an employee’s instance variable `name` with a new one so that only the most recently assigned name remained in memory:

```class Employee(var name: String, val yearOfBirth: Int, var monthlySalary: Double):
// ...
end Employee
```

In this chapter, we just used a local variable (`current`) that we also called a most-recent holder, despite this variable appearing in a completely different sort of context than `name`.

```for current <- this.items do
```

Outwardly, these two variables have little in common, but their purpose is similar in one sense. In both cases, we use the variable to store the latest in a sequence of data items: in one case, it’s the latest name assigned to the object; in the other, it’s the latest auction object that we’ve picked out for processing. The main reason why the two examples look so different is that one of our variables is an instance variable and the other is a local variable within a method. Each example illustrates a typical scenario where a most-recent holder comes in useful:

• A “settable property of an object” such as `name` is a typical way to use an instance variable as a most-recent holder. An instance variable makes sense when we need to store the variable’s value as part of the object even between method calls.

• A “latest value to be processed in a loop” such as `current` is a typical way to use a local variable as a most-recent holder. A local variable makes sense when we need the most recent value only to make a particular method work right.

You’ve already seen a number of different roles for instance variables. The same roles will also turn out to be useful for local variables as we use loops to implement methods. You’re about see that for yourself as we implement the other methods of class `AuctionHouse`.

## A Local Gatherer + A Loop

### Implementing `totalPrice`

Here is a pseudocode sketch of `totalPrice`:

```def totalPrice =
For each of the auctions in this.items in turn, do this:
- Determine the current price of the item and add it to the sum.
Finally, return the sum.```

What local variables do we need?

• A most-recent holder (of type `EnglishAuction`) that stores the current element (auction), just like the one we used in `nextDay`.

• A gatherer (of type `Int`) that tallies up the gradually increasing sum of prices.

Let’s refine our pseudocode.

```def totalPrice =
Let totalSoFar be a gatherer whose value is initially zero.
For each of the auctions in this.items in turn, do this:
- Determine the current price of the item and increment totalSoFar by that amount.
Finally, return the value of the gatherer totalSoFar.```

The same in Scala:

```def totalPrice =
var totalSoFar = 0
for current <- this.items do
totalSoFar += current.price
totalSoFar
```

### Umm

Was that strictly necessary? We wouldn’t have even needed a loop if we had done this instead:

```class AuctionHouse(val name: String):

private val items = Buffer[EnglishAuction]()
private var priceSoFar = 0

this.items += item
this.priceSoFar += item.price

def removeItem(item: EnglishAuction) =
this.items -= item
this.priceSoFar -= item.price

def totalPrice = this.priceSoFar

end AuctionHouse
```

In this solution, our gatherer is an instance variable: the total price of items is stored as part of every `AuctionHouse` object.

We update the gatherer as we add an auction to the auction house or remove one.

`totalPrice`’s implementation is trivial.

Does the above implementation work, too? Answer the question for yourself by considering the following code

```val house = AuctionHouse("BuyBuyBuyBuy.net")
val item = EnglishAuction("TV", 5000, 10)
println(house.totalPrice)
item.bid("Karen", 10000)
item.bid("Richard", 15000)
println(house.totalPrice)
```

If you can’t locate the problem, send a note through the end-of-chapter feedback form and we’ll discuss it in one of the weekly bulletins.

### Implementing `averagePrice`

The averaging method is trivial to implement now that we have a summing method:

```def averagePrice = this.totalPrice.toDouble / this.items.size
```

## A Local Stepper + A Loop (feat.`if`)

Here is `numberOfOpenItems` in pseudocode:

```def numberOfOpenItems =
For each of the auctions in this.items in turn, do this:
- If the auction is open, increment a counter by one.
Finally, return the counter’s value.```

This refined pseudocode uses a variable as a stepper:

```def numberOfOpenItems =
Let openCount be a stepper that starts at 0 and increases by one at a time.
For each of the auctions in this.items in turn, do this:
- Store the auction in a most-recent holder named current.
- If isOpen returns true on the auction, increment openCount.
Finally, return the value in openCount.```

A+ presents the exercise submission form here.

## A Local Container + A Loop

We want `purchasesOf` to return a vector containing the given buyer’s purchases, by which we mean the items that the given buyer either has already bought or is currently the high bidder for.

Here’s a sketch:

```def purchasesOf(buyer: String) =
Create a new, empty buffer and a variable purchases that refers to it.
For each of the itemin this.items in turn, do this:
- If the item’s been bought by the given buyer,
Finally, return a vector that contains the elements collected in purchases.```

A+ presents the exercise submission form here.

Why just `EnglishAuction`s?

What if we want our `AuctionHouse` to contain not just `EnglishAuction`s but `FixedPriceSale`s and `DutchAuction`s, too? We can’t put them in a `Buffer[EnglishAuction]`, which is the type of `items` and `purchases`?

It would be nice to have a buffer that contains items put up for sale in all sorts of ways. We could then have the methods operate on this mix of items. Can we do that?

Yes, we can. We’ll need some tools from Chapter 7.3, though, after which you get to create a new, better AuctionHouse.

## A Local Most-Wanted Holder + A Loop

Here is a pseudocode implementation for `priciest`:

```def priciest =
Initially, the priciest auction we’ve found is the first element in this.items.
For each of the auctions in this.items in turn, do this:
- Compare the auction with the priciest one we found so far and record which is the pricier of the two.
Finally return the auction that we’ve recorded as being the priciest.```

What local variables do we need?

• A most-recent holder (of type `EnglishAuction`) that stores the current element (auction).

• A most-wanted holder (also of type `EnglishAuction`) that stores the priciest auction that we’ve encountered so far.

This refined pseudocode uses those local variables:

```def priciest =
Let priciestSoFar be a most-wanted holder with an initial value of this.items.head.
For each of the auctions in this.items in turn, do this:
1. Store the auction in a most-recent holder named current.
2. Determine whether current is more expensive than priciestSoFar. If it is:
- Replace the old value of priciestSoFar with current.
Finally, return the value that ended up in priciestSoFar.```

And here’s the Scala equivalent:

```def priciest =
for current <- this.items do
if current.price > priciestSoFar.price then
priciestSoFar = current
priciestSoFar
```

What did we just forget?

Earlier, we specified that this method should return an `Option[EnglishAuction]` and not fail even if the auction house contains zero items. Instead, what we have here is a return value of `EnglishAuction` and a method that crashes if `items` is empty (since there is no value at index zero). This is analogous to the problem we had in Chapter 4.2 when we first used a most-wanted holder: we wrote `addExperience` but failed to account for the scenario where the category did not yet have any previous favorite experience.

Let’s fix the method. One way to do that is to handle the problematic case separately with an `if`.

```def priciest =
if this.items.isEmpty then
None
else
for current <- this.items do
if current.price > priciestSoFar.price then
priciestSoFar = current
Some(priciestSoFar)
```

We return `None` if there’s nothing to loop over.

Otherwise, we can do what we did before, since we’re sure to have at least one element in the buffer.

We wrap the result in a `Some`.

Not quite satisfied?

In this implementation, `priciestSoFar` and `current` refer to the same object when the loop body is executed for the first time. There is no point in comparing the first item with itself. In practice, our solution works fine, but it does feel a bit unclean.

You may wish to keep this problem in mind as we move to later chapters. There are various ways of implementing this method, and some of them avoid the unnecessary first comparison.

### What about our old `Category` class?

In Chapter 4.3, we wrote several implementations of `Category`. Like this one:

```class Category(val name: String, val unit: String):

private val experiences = Buffer[Experience]()
private var fave: Option[Experience] = None

def favorite = this.fave

this.experiences += newExperience
this.fave match
case None =>
this.fave = Some(newExperience)
case Some(oldFave) =>
val newFave = newExperience.chooseBetter(oldFave)
this.fave = Some(newFave)

end Category
```

We can apply the ideas that we just used in `priciest` to `Category` as well. We’ll still use a most-wanted-holder, but instead of it being an instance variable, we’ll make it a local variable and add a `for` loop:

```class Category(val name: String, val unit: String):

private val experiences = Buffer[Experience]()

def favorite =
if this.experiences.isEmpty then
None
else
var fave = this.experiences(0)
for current <- this.experiences do
fave = current.chooseBetter(fave)
Some(fave)

this.experiences += newExperience

end Category
```

This alternative solution works, too.

Comparing the solutions

Since both solutions work but have their own strengths and weaknesses, we have an opportunity to discuss some quality criteria for assessing programs.

Criterion

Solution with `fave` as instance `var`

Solution with local `fave` and a loop

Intuitiveness

It is natural to think of “favorite experience“ as a property of category objects.

It is also natural to think of favorites as something that is determined by a `favorite` method upon request.

Ease of implementation

`favorite` is trivial to implement. `addExperience` is more complex.

`addExperience` is trivial. `favorite` is more complex.

Speed (of execution by computer)

The program is, in principle, faster, at least if there are a lot of experiences and `favorite` is called frequently. (However, this has no practical significance whatsoever in this application.)

The computer goes through all the elements in the buffer whenever `favorite` is called, which may make this implementation slower, in principle.

Memory usage

Each category object takes up a small amount of additional memory to store a reference to the favorite object. (However, this has no practical significance whatsoever in this application.)

Only what is needed is stored in memory, as part of the category objects. The favorite experience can be obtained by searching through the buffer.

Code that deals with favorite experiences appears in several places: the instance variables, the `favorite` method, and `addExperience`. Each of these pieces depends on the others. This makes the program somewhat harder to read and modify.

All the code that deals with favorite experiences is within `favorite`. There are fewer dependencies between parts of the class. The code is somewhat easier to extend and modify.

As far as this program is concerned, there is little to choose between the alternative approaches, but the loop-based solution edges it. Readability and modifiability are important!

## Practice on Loops

Study the code below. The first line creates a vector. What does the rest of the code do?

```val words = Vector("function", "method", "subprogram", "procedure", "routine")
var result = 0
for word <- words do
if word.length > result then
result = word.length
println(result)
```

Here we don’t loop through a buffer but a vector. The principle is just the same, though.

Please list all the different numbers that `result` stores during a run of the above program. Enter each number on a separate line, in order. Don’t repeat the same number. Remember to include the variable’s initial value.

### Loop-writing practice

Open the ForLoops module and its `o1.looptest` package. You’ll find `task1.scala`. Read the code and rewrite it so that the program produces precisely the same output as before but uses a `for` loop to do so. Your program should be substantially shorter than the given one.

A+ presents the exercise submission form here.

Abstraction, again

A loop is an abstraction, too. In the above task, you took the given, specific lines of code and generalized them into a more generic solution.

### More code: loops and variables

```def incrementEach(numbers: Buffer[Int]) =
for number <- numbers do
number = number + 1
```

Is that function definition valid? (Assume that `Buffer` has been `import`ed.) Think about it, try it, or take an educated guess.

Consider this little class:

```class Adder(val elements: Buffer[Int]):

var sum = 0

// The method computes the sum of the buffer’s current elements,
// then appends that sum as a new element at the end of the buffer.
for number <- this.elements do
sum += number
this.elements += sum

```

Which of the following claims about the `addSum` method are correct? Select all that apply.

## Summary of Key Points

• You can use a `for` loop to repeat one or more commands on each element in a collection.

• You can use a `for` loop and local variables in different combinations.

• Links to the glossary: loop, `for` loop, iteration; collection; role.

## Feedback

Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.

## Credits

Thousands of students have given feedback and so contributed to this ebook’s design. Thank you!

The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.

The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.

The automatic assessment of the assignments has been developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Anna Valldeoriola Cardó, and Aleksi Vartiainen.

The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.

The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio did the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.

The other diagrams and interactive presentations in the ebook are by Juha Sorva.

The O1Library software has been developed by Aleksi Lukkarinen and Juha Sorva. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using O1Library for simple graphical programming (such as `Pic`) is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and Krishnamurthi and Picturing Programs by Stephen Bloch.

The course platform A+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services. Markku Riekkinen is the current lead developer; dozens of Aalto students and others have also contributed.

The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.

For O1’s current teaching staff, please see Chapter 1.1.

Additional credits appear at the ends of some chapters.

Posting submission...