- Joined
- Feb 22, 2006
- Messages
- 752
Lesson: Iteration
Probably one of the most important abilities of any program is to carry out repetitive tasks over and over. This might seem silly, but without repetition we would be left with only the simplest of programs. Almost every programming algorithm (an algorithm is a set of purely mechanical instructions guaranteed to produce the correct result every time it is executed) ever written relies on repetition.
In JASS the most basic method of executing repetitive code is iteration.
A Model of Iteration
Iteration is the first (and in many ways the simpler) method of executing repetitive code in JASS. To put it simply, iteration is the execution of a block of code repeatedly while some condition (the loop condition) is true. Code that is iterated over is often said to be in a loop. A model of iteration might look something like this:
- Enter loop.
- If the loop condition is true then go to 3. Otherwise go to 4.
- Execute code within the loop, then go back to 2.
- Exit loop.
Graphically this can be represented as:
In the above image, circles link to squares of the same color (as shown by the arrows). So whenever we encounter a circle we jump to the place indicated by the square of the same color. The teal box represents of the section of code that checks if the loop condition is true. The yellow box represents the section of code that is iterated over, often called the loop body.
Iteration in JASS
JASS offers a single control structure for iteration: the loop/endloop block. Let's take a look at one:
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1
endloop
call BJDebugMsg("Done.")
endfunction
The above function prints out the numerals one through ten using iteration, then prints out "Done." Let's go through the function to see how it works step by step.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1 // <==
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1
call BJDebugMsg("Done.")
endloop
endfunction
The marked line is called the initialization of the loop. Basically we are setting the local variable i to a value of 1.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop // <==
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1
endloop
call BJDebugMsg("Done.")
endfunction
The loop keyword denotes the start of a loop block (loop body).
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10) // <==
call BJDebugMsg(I2S(i))
set i = i + 1
endloop
call BJDebugMsg("Done.")
endfunction
The exitwhen statement is what JASS uses to check a loop condition. However, instead of continuing the iteration when some condition (the loop condition) is true, it breaks the iteration (exits the loop) if some condition is false. Therefore, instead of placing the loop condition in the exitwhen statement, we would need to place the negation of the loop condition in the statement.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i)) // <==
set i = i + 1
endloop
call BJDebugMsg("Done.")
endfunction
This line is really the meat of the loop. It prints out the number stored in the local variable i.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1 // <==
endloop
call BJDebugMsg("Done.")
endfunction
This line increments the value stored in the local variable i up by one.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1
endloop // <==
call BJDebugMsg("Done.")
endfunction
The endloop keyword marks the end of a loop block. When code execution within the loop block reaches the endloop keyword, it jumps back to the loop keyword and will continue to do so forever unless the execution exits the loop via an exitwhen statement.
JASS:
function PrintOneToTen takes nothing returns nothing
local integer i = 1
loop
exitwhen (i > 10)
call BJDebugMsg(I2S(i))
set i = i + 1
endloop
call BJDebugMsg("Done.") // <==
endfunction
This is the first line of code after the loop block. It is the first line of code to be executed when code execution exits the loop.
Building Iterative Code
Now that we've seen how iteration works in JASS, let's create an iterative function. We'll start off simple. Our function will calculate the sum of the squares of all integers from 0 to n, where n is some non-negative integer. In other words, it will calculate the value of:
02 + 12 + 22 + 32 + ... + n2
Before we even start an attempt to write code for this, let's think first about how we would do something like this without using programming. We would begin by taking 0 and squaring it. Then we would take 1 and square it and add it to the square of 0. Then we would take 2 and square it and add it to the sum of the square of 1 and the square of 0. And we would continue doing this for every integer until we got to n. Remember this description well because we will keep coming back to it when trying to figure out what our code should be.
Now we begin coding. We start off with just the function declaration:
JASS:
function SumOfSquares takes integer n returns integer
endfunction
We already know we want to create a loop, so the first thing we need to do is to initialize the loop. What is an appropriate initialization? Looking back to our non-coding description of the task, we see that we repeatedly calculate the squares of integers. Well for a program to calculate the square of an integer it needs to know the value of said integer; in other words we need a local integer variable to keep track of which integer we are squaring. We will also need another local integer variable to keep track of the sum of the squares we have already calculated.
JASS:
function SumOfSquares takes integer n returns integer
local integer sum
local integer i
endfunction
Our initialization is not done yet. We know that we need to calculate the squares of integers from 0 to some non-negative integer n. And no matter what, the first square we calculate is going to be 0 squared. So we need to initialize i to 0. We must also initialize sum to 0 because at this point, we haven't calculated any squares yet and the sum of nothing is simply 0.
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
endfunction
Initialization is now finished. Now to add the loop body:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
endloop
endfunction
Our model of iteration says that we need some condition such that when the condition is true, the loop continues to iterate and otherwise code execution exits the loop. Well, in our non-coding description, we said that we only repeatedly calculate the squares of integers if the integers are between 0 and n. So our condition for the continued execution of the loop is i >= 0 and i <= n. But remember that in JASS, loop conditions are dealt with using exitwhen statements, which take the negation of the condition as it would appear in our model. So what goes into our code is actually:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
exitwhen (i < 0 or i > n)
endloop
endfunction
Now to think about what goes in the meat of the loop body. Well remember what we did non-codewise was to take the square of an integer and add it to the sum of all the squares of the integers that came before it. So to do it in our code we need to add two things. Firstly we need another local variable to keep track of the sum. Secondly we add a line inside the loop body to calculate the square of an integer and add it to the sum:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
exitwhen (i < 0 or i > n)
set sum = sum + i * i
endloop
endfunction
We are almost done with the loop. The last thing we need to do is to take into account the fact that once we are finished calculating the square of some integer and adding it to the sum, we must move on to the next greatest integer and repeat the process. Well our loop takes care of the repetition part since that's what a loop does. However, we must make sure to change i in such a way that every time the loop repeats, i is bumped up to the next greatest integer. We can achieve this simply by adding 1 to i at the very end of the loop body:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
exitwhen (i < 0 or i > n)
set sum = sum + i * i
set i = i + 1
endloop
endfunction
Now all that is left is to return the answer:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
exitwhen (i < 0 or i > n)
set sum = sum + i * i
set i = i + 1
endloop
return sum
endfunction
There! We have created a function that returns the sum of the squares of all integers from 1 to some positive integer n. There is actually one last thing we can do. If we look closely at the code, we see that i can never be less than 1. We initialize it to 1 and then all we ever do to it is add 1. Therefore, we can clean up the exitwhen statement since it is pointless to check to see if i is less than 1 if it is always greater than or equal to 1.
So the following is our final function:
JASS:
function SumOfSquares takes integer n returns integer
local integer sum = 0
local integer i = 0
loop
exitwhen (i > n)
set sum = sum + i * i
set i = i + 1
endloop
return sum
endfunction
Unconditionally Exiting a Loop
Unlike most languages, JASS does not provide a separate keyword for unconditionally exiting a loop (often called "breaking" the loop). However, we can use the following syntax to simulate an unconditional break:
JASS:
loop
// some code ...
exitwhen (true) // <==
// some more code ...
endloop
By using the boolean literal true we are guaranteeing that this exit condition is true under all circumstances. Therefore whenever code execution reaches this line, it will exit the loop.
Homework
Short Answer Problems
Give a one to two sentence answer to the following questions. Writing up code is not necessary unless you feel it helps to illustrate your answer.
- What is the loop condition (not the exit condition) for the following loop?
JASS:loop exitwhen (i > 100) endloop
- How many iterations will the following loop go through? (A single iteration is defined as one complete execution of the entire loop body.)
JASS:local integer i = 0 loop exitwhen (i > 10) set i = i + 1 endloop
- What does the following function do?
JASS:function Foo takes integer j, integer k returns integer // j and k are both positive local integer m = j loop exitwhen (ModuloInteger(m, k) == 0) set m = m + j endloop return m endfunction
Coding Problems
Write up JASS code for each problem that meets the given specifications.
- Write an iterative function that prints out every pair of integer (x, y) coordinates that lies on or is contained within the square whose four vertices are (0,0), (0, 20), (20, 0), and (20, 20).
- Write an iterative function that computes the factorial of a non-negative integer n (n!).
- Write an iterative function that computes the product of two non-negative integers j and k. You may not use the multiplication operator (*).
- Write an iterative function that computes the exponent a raised to the b power (ab) for some integer a and some non-negative integer b. You may not use the Pow() function.
Challenge Problems
These are optional problems that you may try at your own discretion. They are often far more difficult than the other types of problems.
- Write an iterative function that computes integer division between two non-negative integers j and k, where j is the dividend and k is the divisor (in other words j / k). Remember that integer division always truncates (rounds down) the quotient to the nearest integer. You may not use the division operator (/)
- Suppose you are given the function
function GetInteger takes integer i returns integer
. The function takes in an integer parameter i from 0 to some non-negative number n and returns a unique arbitrary integer m such that the larger the value of i, the larger the value of m. In other words:
GetInteger(0) < GetInteger(1) < GetInteger(2) < ... < GetInteger(n)
Write an iterative function that takes some integer m and some non-negative integer n and finds the integer 0 <= i < n such that GetInteger(i) = m. If there is no such integer i, the function should return -1. For some extra challenge, implement your function so that it does not have to iterate over every i from 0 to n. - Write an iterative function that approximates the value of the mathematical constant e. The accuracy of your approximation is up to you, but you should be accurate to at least 2 or 3 decimal places. You may use your factorial function from Coding Problem 1. (Hint: use the MacLaurin series of ex.)
Attachments
Last edited: