Looping in R

What is a loop?

Process of iteration:

  • automating a certain multi step process by organizing sequences of actions (‘batch’ processes)
  • grouping the parts in need of repetition


When do you know you need a loop?

-> When you seem to be repeating the same code.

Let’s have a look at some data and code:

air.data <- airquality
head(air.data)
  Ozone Solar.R Wind Temp Month Day
1    41     190  7.4   67     5   1
2    36     118  8.0   72     5   2
3    12     149 12.6   74     5   3
4    18     313 11.5   62     5   4
5    NA      NA 14.3   56     5   5
6    28      NA 14.9   66     5   6

Say I wanted to calculate the mean of each column in the air.data data.frame. When I first started coding I would have probably done something like this:

mean.1 <- mean(air.data[,1], na.rm = T)
mean.2 <- mean(air.data[,2], na.rm = T)
mean.3 <- mean(air.data[,3], na.rm = T)
mean.4 <- mean(air.data[,4], na.rm = T)
mean.5 <- mean(air.data[,5], na.rm = T)
mean.6 <- mean(air.data[,1], na.rm = T)

means <- c(mean.1, mean.2, mean.3, mean.4, mean.4, mean.6)

means
[1]  42.129310 185.931507   9.957516  77.882353  77.882353  42.129310

Why is the above bad?




Types of loops

  • for loops: Loops that execute for a prescribed number of times.
    • controlled by a counter or an index
    • incremented at each iteration cycle
  • while or repeat loops: Loops based on the onset and verification of a logical condition (for example, the value of a control variable)
    • tested at the start (while) or at the end (repeat) of the loop construct.


for loops

for loops are used when the number of iterations required can be defined: eg iterating a calculation across each row of a data.frame.

General construct of a for loop:

for (val in sequence) {
    statement
}

Say we wanted to scale and center each variable in the air.data dataset. We can iterate the process over of each column of the dataframe in a number of ways.

1. We can use numeric indices:

for(i in 1:ncol(air.data)){
    air.data[,i] <- scale(air.data[,i], scale = T, center = T)
}

head(air.data)    
        Ozone     Solar.R       Wind       Temp     Month       Day
1 -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
2 -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
3 -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
4 -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
5          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
6 -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973


2. We can use character indices:

for(var in names(air.data)){
    air.data[,var] <- scale(air.data[,var], scale = T, center = T)
}

head(air.data)
        Ozone     Solar.R       Wind       Temp     Month       Day
1 -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
2 -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
3 -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
4 -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
5          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
6 -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973



while loops

while loops can be used when the exact number of iterations is not known a priori, for example when calculating the convergence of a cost function.

General construct of a while loop:

while (test_expression) {
   statement
}

Example of a while loop

i <- 1

while (i < 6) {
   print(i)
   i = i+1
}
[1] 1
[1] 2
[1] 3
[1] 4
[1] 5

nested loops

We can even nest loops within loops.

mat = matrix(nrow=5, ncol=5) # create a 30 x 30 matrix (of 30 rows and 30 columns)

for(i in 1:nrow(mat))  # for each row
{
  for(j in 1:ncol(mat)) # for each column
  {
    mat[i,j] = i*j     # assign values based on position: product of two indexes
  }
}

i iterates over each row while j interates over each column. What have we made? The all too familiar multiplication table!

mat
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    5
[2,]    2    4    6    8   10
[3,]    3    6    9   12   15
[4,]    4    8   12   16   20
[5,]    5   10   15   20   25



collecting the output of loops

individual values

Individual values can be collected in a named vector by combining functions c() and setNames().

For example we could collect the means of each column of the air.data data.frame in a vector.

mu <- NULL

for(var in names(air.data)){
    mu <- c(mu, setNames(mean(air.data[,var], na.rm = T), var))
}

mu
     Ozone    Solar.R       Wind       Temp      Month        Day 
 42.129310 185.931507   9.957516  77.882353   6.993464  15.803922 


vectors

Vectors of the same size can be collected in a data.frame.

In the scaling example before we were iterating through the air.data data.frame and overwriting the original values. But what if we wanted to retain the original data. We then need to collect the outputs in a new data.frame.

require(dplyr)

scaled_data <- NULL

for(var in names(air.data)){
    
    scaled_data <- cbind(scaled_data, 
                         scale(air.data[,var], 
                               scale = T, 
                               center = T))
}

# convert to data.frame and name
scaled_data <- as.data.frame(scaled_data) %>% setNames(names(air.data))

head(scaled_data)
        Ozone     Solar.R       Wind       Temp     Month       Day
1 -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
2 -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
3 -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
4 -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
5          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
6 -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973


other

more complex outputs can be collected in lists. For example, say we wanted to fit a linear model with "Ozone" as the response variable and each of the other variables as single predictors. We can loop the process and collect the outputs of the lm() function in a list.

predictors <- names(air.data)[names(air.data) != "Ozone"]
air_mods <- NULL

for(predictor in predictors){
    
    air_mods <- c(air_mods,
    list(lm(as.formula(paste("Ozone ~", predictor)), data = air.data)))
}

str(air_mods, max.level = 1)
List of 5
 $ :List of 13
  ..- attr(*, "class")= chr "lm"
 $ :List of 13
  ..- attr(*, "class")= chr "lm"
 $ :List of 13
  ..- attr(*, "class")= chr "lm"
 $ :List of 13
  ..- attr(*, "class")= chr "lm"
 $ :List of 13
  ..- attr(*, "class")= chr "lm"




Altering looping sequences

break

break is a bit like stop() but for a loop. It is usually used with a conditional statement and if triggered, breaks out of the current loop.

x <- 1:5

for (val in x) {
    if (val == 3){
        break
    }
    print(val)
}
[1] 1
[1] 2

In this example, we iterate over the vector x, which has consecutive numbers from 1 to 5. Inside the for loop we have used a condition to break if the current value is equal to 3. As we can see from the output, the loop terminates when it encounters the break statement.

vectorisation (the apply function family)

It’s always good to start learning the principles of iteration through loops. Simple loops can be more understandable to a human reader

However, loops can be slow, and in cases were computation time of a loop becomes a bottleneck, it is good to know a bit about vectorisation.

So let’s see what our for loop examples look like vectorised:


apply

apply iterates over the margins of an array. We can use it to calculate the means of each column:

mu <- apply(air.data, MARGIN = 2, FUN = function(x){mean(x, na.rm = T)})


lapply

The lapply takes a list as an input (data.frames are lists) and apply a function over each element of the list:

scaled_data <- lapply(air.data, FUN = function(x){
    scale(x, scale = T, center = T)}) %>% 
    data.frame() %>%
    setNames(names(air.data))

head(scaled_data)
        Ozone     Solar.R       Wind       Temp     Month       Day
1 -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
2 -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
3 -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
4 -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
5          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
6 -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973


mapply

The mapply allows us to pass multiple iterated arguments to a function. It has a different structure as the function is the first argument, any arguments to be passed to the function and iterated over are specified in ... and any arguments to be used as is by the function are supplied in the argument MoreArgs.

As an example, we will replicate the default behaviour of scale to center on the mean by supply are own vector of calculated means mu.

scaled_data <- mapply(FUN = function(x, center){scale(x, scale = T, 
                                              center = center)},
                      x = air.data, center = mu) %>% 
    data.frame() %>%
    setNames(names(air.data))

head(scaled_data)
        Ozone     Solar.R       Wind       Temp     Month       Day
1 -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
2 -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
3 -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
4 -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
5          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
6 -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973

Things to remember:

  • loops are evaluated in the global environment -> can get messy!
  • if you’ve got a lot of code within your loop, consider writing a function



Cheats

A lot of the examples I showed are actually addressed by these or other functions.

eg scale() can be applied directly to a data.frame:

head(scale(air.data))
           Ozone     Solar.R       Wind       Temp     Month       Day
[1,] -0.03423409  0.04517615 -0.7259482 -1.1497140 -1.407294 -1.670019
[2,] -0.18580489 -0.75430487 -0.5556388 -0.6214670 -1.407294 -1.557210
[3,] -0.91334473 -0.41008388  0.7500660 -0.4101682 -1.407294 -1.444401
[4,] -0.73145977  1.41095624  0.4378323 -1.6779609 -1.407294 -1.331592
[5,]          NA          NA  1.2326091 -2.3118573 -1.407294 -1.218782
[6,] -0.42831817          NA  1.4029185 -1.2553634 -1.407294 -1.105973

and there are in-built functions for calculating the mean of columns:

colMeans(air.data, na.rm = T)
     Ozone    Solar.R       Wind       Temp      Month        Day 
 42.129310 185.931507   9.957516  77.882353   6.993464  15.803922 

But the principles of applying functions over loops are still the same.




Exercises

source: http://r-exercises.com/2016/06/01/scripting-loops-in-r/

Exercise 3

With, i <- 1, write a while() loop that prints the odd numbers from 1 through 7.

Exercise 4

Using the following variables:

msg <- c(“Hello”) i <- 1

Write a while() loop that increments the variable, i, 6 times, and prints msg at every iteration.

Exercise 5

Write a for() loop that prints the first four numbers of this sequence:

x <- c(7, 4, 3, 8, 9, 25)

Exercise 6

For the next exercise, write a for() loop that prints all the letters in:

y <- c("q", "w", "e", "r", "z", "c")

Exercise 7

Using i <- 1, write a while() loop that prints the variable, i, (that is incremented from 1 – 5), and uses break to exit the loop if i equals 3.

Exercise 8

Write a nested loop, where the outer for() loop increments a 3 times, and the inner for() loop increments b 3 times. The break statement exits the inner for() loop after 2 incrementations. The nested loop prints the values of variables, a and b.

Exercise 9

Write a while() loop that prints the variable, i, that is incremented from 2 – 5, and uses the next statement, to skip the printing of the number 3.

Exercise 10

Write a for() loop that uses next to print all values except 3 in the following variable: i <- 1:5

IyAqKkxvb3BpbmcgaW4gUioqCgojIyMgKipBbm5hIEtyeXN0YWxsaSoqCiMjIyMjICoqKkluc3RpdHV0ZSBkZSBFY29sb2dpYSwgVU5BTSAzMCBBdWcuIDIwMTYqKioKCiMjIyMjIyA8aHR0cHM6Ly9hbm5ha3J5c3RhbGxpLmdpdGh1Yi5pby9VTkFNL0xvb3BpbmdfaW5fUi5uYi5odG1sPgoKCjxicj4KCioqQGFubmFrcnlzdGFsbGkgfCBhbm5ha3J5c3RhbGxpQGdvb2dsZW1haWwuY29tKioKCioqKgo8YnI+CgojIyBXaGF0IGlzIGEgbG9vcD8KCioqUHJvY2VzcyBvZiBpdGVyYXRpb246KioKCi0gYXV0b21hdGluZyBhIGNlcnRhaW4gbXVsdGkgc3RlcCBwcm9jZXNzIGJ5IG9yZ2FuaXppbmcgc2VxdWVuY2VzIG9mIGFjdGlvbnMgKCdiYXRjaCcgcHJvY2Vzc2VzKSAKLSBncm91cGluZyB0aGUgcGFydHMgaW4gbmVlZCBvZiByZXBldGl0aW9uCgo8YnI+CgojIyMgV2hlbiBkbyB5b3Uga25vdyB5b3UgbmVlZCBhIGxvb3A/CgojIyMjICoqLT4gV2hlbiB5b3Ugc2VlbSB0byBiZSByZXBlYXRpbmcgdGhlIHNhbWUgY29kZS4qKgoKTGV0J3MgaGF2ZSBhIGxvb2sgYXQgc29tZSBkYXRhIGFuZCBjb2RlOgoKCmBgYHtyfQphaXIuZGF0YSA8LSBhaXJxdWFsaXR5CmhlYWQoYWlyLmRhdGEpCmBgYAoKU2F5IEkgd2FudGVkIHRvIGNhbGN1bGF0ZSB0aGUgbWVhbiBvZiBlYWNoIGNvbHVtbiBpbiB0aGUgYGFpci5kYXRhYCBkYXRhLmZyYW1lLiBXaGVuIEkgZmlyc3Qgc3RhcnRlZCBjb2RpbmcgSSB3b3VsZCBoYXZlIHByb2JhYmx5IGRvbmUgc29tZXRoaW5nIGxpa2UgdGhpczoKCmBgYHtyfQptZWFuLjEgPC0gbWVhbihhaXIuZGF0YVssMV0sIG5hLnJtID0gVCkKbWVhbi4yIDwtIG1lYW4oYWlyLmRhdGFbLDJdLCBuYS5ybSA9IFQpCm1lYW4uMyA8LSBtZWFuKGFpci5kYXRhWywzXSwgbmEucm0gPSBUKQptZWFuLjQgPC0gbWVhbihhaXIuZGF0YVssNF0sIG5hLnJtID0gVCkKbWVhbi41IDwtIG1lYW4oYWlyLmRhdGFbLDVdLCBuYS5ybSA9IFQpCm1lYW4uNiA8LSBtZWFuKGFpci5kYXRhWywxXSwgbmEucm0gPSBUKQoKbWVhbnMgPC0gYyhtZWFuLjEsIG1lYW4uMiwgbWVhbi4zLCBtZWFuLjQsIG1lYW4uNCwgbWVhbi42KQoKbWVhbnMKYGBgCgojIyMjICoqV2h5IGlzIHRoZSBhYm92ZSBiYWQ/KioKCioqKgo8YnI+Cjxicj4KCiMjIFR5cGVzIG9mIGxvb3BzCgotICoqYGZvcmAgbG9vcHM6KiogTG9vcHMgdGhhdCBleGVjdXRlIGZvciBhIHByZXNjcmliZWQgbnVtYmVyIG9mIHRpbWVzLiAKICAgIC0gY29udHJvbGxlZCBieSBhIGNvdW50ZXIgb3IgYW4gaW5kZXgKICAgIC0gaW5jcmVtZW50ZWQgYXQgZWFjaCBpdGVyYXRpb24gY3ljbGUKICAgIAotICoqYHdoaWxlYCBvciBgcmVwZWF0YCBsb29wczoqKiBMb29wcyBiYXNlZCBvbiB0aGUgb25zZXQgYW5kIHZlcmlmaWNhdGlvbiBvZiBhIGxvZ2ljYWwgY29uZGl0aW9uIChmb3IgZXhhbXBsZSwgdGhlIHZhbHVlIG9mIGEgY29udHJvbCB2YXJpYWJsZSkKICAgIC0gdGVzdGVkIGF0IHRoZSBzdGFydCAoYHdoaWxlYCkgb3IgYXQgdGhlIGVuZCAoYHJlcGVhdGApIG9mIHRoZSBsb29wIGNvbnN0cnVjdC4KCjxpbWcgc3JjPWFzc2V0cy9mbG93Y2hhcnQxLnBuZyBoZWlnaHQgPSI0MDBweCIgd2lkdGg9IjYwMHB4Ij4gICAgCgo8YnI+CgoKIyMgKipgZm9yYCBsb29wcyoqCgoqKmBmb3JgKiogbG9vcHMgYXJlIHVzZWQgd2hlbiB0aGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgcmVxdWlyZWQgY2FuIGJlIGRlZmluZWQ6IGVnIGl0ZXJhdGluZyBhIGNhbGN1bGF0aW9uIGFjcm9zcyBlYWNoIHJvdyBvZiBhIGRhdGEuZnJhbWUuCgo8aW1nIHNyYz1hc3NldHMvZm9yTG9vcC5qcGcgaGVpZ2h0ID0iMTUwcHgiIHdpZHRoPSIxNTBweCI+IAoKKipHZW5lcmFsIGNvbnN0cnVjdCBvZiBhIGBmb3JgIGxvb3A6KioKYGBge3IsIGV2YWw9RkFMU0V9CmZvciAodmFsIGluIHNlcXVlbmNlKSB7CiAgICBzdGF0ZW1lbnQKfQpgYGAKCgpTYXkgd2Ugd2FudGVkIHRvIHNjYWxlIGFuZCBjZW50ZXIgZWFjaCB2YXJpYWJsZSBpbiB0aGUgYGFpci5kYXRhYCBkYXRhc2V0LiBXZSBjYW4gaXRlcmF0ZSB0aGUgcHJvY2VzcyBvdmVyIG9mIGVhY2ggY29sdW1uIG9mIHRoZSBkYXRhZnJhbWUgaW4gYSBudW1iZXIgb2Ygd2F5cy4KCiMjIyMgMS4gV2UgY2FuIHVzZSBudW1lcmljIGluZGljZXM6CmBgYHtyfQpmb3IoaSBpbiAxOm5jb2woYWlyLmRhdGEpKXsKICAgIGFpci5kYXRhWyxpXSA8LSBzY2FsZShhaXIuZGF0YVssaV0sIHNjYWxlID0gVCwgY2VudGVyID0gVCkKfQoKaGVhZChhaXIuZGF0YSkgICAgCmBgYAoKYGBge3IsIGVjaG8gPSBGfQphaXIuZGF0YSA8LSBhaXJxdWFsaXR5CmBgYAoKPGJyPgoKIyMjIyAyLiBXZSBjYW4gdXNlIGNoYXJhY3RlciBpbmRpY2VzOgpgYGB7cn0KZm9yKHZhciBpbiBuYW1lcyhhaXIuZGF0YSkpewogICAgYWlyLmRhdGFbLHZhcl0gPC0gc2NhbGUoYWlyLmRhdGFbLHZhcl0sIHNjYWxlID0gVCwgY2VudGVyID0gVCkKfQoKaGVhZChhaXIuZGF0YSkKCmBgYAoKCgoqKioKPGJyPgo8YnI+CgojIyAqKmB3aGlsZWAgbG9vcHMqKgoKd2hpbGUgbG9vcHMgY2FuIGJlIHVzZWQgd2hlbiB0aGUgZXhhY3QgbnVtYmVyIG9mIGl0ZXJhdGlvbnMgaXMgbm90IGtub3duIGEgcHJpb3JpLCBmb3IgZXhhbXBsZSB3aGVuIGNhbGN1bGF0aW5nIHRoZSBjb252ZXJnZW5jZSBvZiBhIGNvc3QgZnVuY3Rpb24uCgo8aW1nIHNyYz1hc3NldHMvd2hpbGVMb29wRmxvd2NoYXJ0LmpwZyBoZWlnaHQgPSIxNTBweCIgd2lkdGg9IjE1MHB4Ij4gCgoqKkdlbmVyYWwgY29uc3RydWN0IG9mIGEgYHdoaWxlYCBsb29wOioqCmBgYHtyIGV2YWw9RkFMU0V9CndoaWxlICh0ZXN0X2V4cHJlc3Npb24pIHsKICAgc3RhdGVtZW50Cn0KYGBgCgpFeGFtcGxlIG9mIGEgd2hpbGUgbG9vcApgYGB7cn0KaSA8LSAxCgp3aGlsZSAoaSA8IDYpIHsKICAgcHJpbnQoaSkKICAgaSA9IGkrMQp9CmBgYAoKCiMjIyBuZXN0ZWQgbG9vcHMKCldlIGNhbiBldmVuIG5lc3QgbG9vcHMgd2l0aGluIGxvb3BzLgpgYGB7cn0KbWF0ID0gbWF0cml4KG5yb3c9NSwgbmNvbD01KSAjIGNyZWF0ZSBhIDMwIHggMzAgbWF0cml4IChvZiAzMCByb3dzIGFuZCAzMCBjb2x1bW5zKQoKZm9yKGkgaW4gMTpucm93KG1hdCkpICAjIGZvciBlYWNoIHJvdwp7CiAgZm9yKGogaW4gMTpuY29sKG1hdCkpICMgZm9yIGVhY2ggY29sdW1uCiAgewogICAgbWF0W2ksal0gPSBpKmogICAgICMgYXNzaWduIHZhbHVlcyBiYXNlZCBvbiBwb3NpdGlvbjogcHJvZHVjdCBvZiB0d28gaW5kZXhlcwogIH0KfQpgYGAKYGlgIGl0ZXJhdGVzIG92ZXIgZWFjaCByb3cgd2hpbGUgYGpgIGludGVyYXRlcyBvdmVyIGVhY2ggY29sdW1uLgpXaGF0IGhhdmUgd2UgbWFkZT8gVGhlIGFsbCB0b28gZmFtaWxpYXIgKm11bHRpcGxpY2F0aW9uIHRhYmxlKiEKCmBgYHtyfQptYXQKYGBgCgoqKioKPGJyPgo8YnI+CgoKCiMjICoqY29sbGVjdGluZyB0aGUgb3V0cHV0IG9mIGxvb3BzKioKCiMjIyAqKmluZGl2aWR1YWwgdmFsdWVzKioKCkluZGl2aWR1YWwgdmFsdWVzIGNhbiBiZSBjb2xsZWN0ZWQgaW4gYSBuYW1lZCAqKnZlY3RvcioqIGJ5IGNvbWJpbmluZyBmdW5jdGlvbnMgYGMoKWAgYW5kIGBzZXROYW1lcygpYC4KCkZvciBleGFtcGxlIHdlIGNvdWxkIGNvbGxlY3QgdGhlIG1lYW5zIG9mIGVhY2ggY29sdW1uIG9mIHRoZSBgYWlyLmRhdGFgIGRhdGEuZnJhbWUgaW4gYSB2ZWN0b3IuCgpgYGB7ciwgZWNobyA9IEZ9CmFpci5kYXRhIDwtIGFpcnF1YWxpdHkKYGBgCgpgYGB7cn0KbXUgPC0gTlVMTAoKZm9yKHZhciBpbiBuYW1lcyhhaXIuZGF0YSkpewogICAgbXUgPC0gYyhtdSwgc2V0TmFtZXMobWVhbihhaXIuZGF0YVssdmFyXSwgbmEucm0gPSBUKSwgdmFyKSkKfQoKbXUKCmBgYAoKPGJyPgoKIyMjICoqdmVjdG9ycyoqCgpWZWN0b3JzIG9mIHRoZSBzYW1lIHNpemUgY2FuIGJlIGNvbGxlY3RlZCBpbiBhICoqZGF0YS5mcmFtZSoqLiAKCkluIHRoZSBzY2FsaW5nIGV4YW1wbGUgYmVmb3JlIHdlIHdlcmUgaXRlcmF0aW5nIHRocm91Z2ggdGhlIGBhaXIuZGF0YWAgZGF0YS5mcmFtZSBhbmQgb3ZlcndyaXRpbmcgdGhlIG9yaWdpbmFsIHZhbHVlcy4gQnV0IHdoYXQgaWYgd2Ugd2FudGVkIHRvIHJldGFpbiB0aGUgb3JpZ2luYWwgZGF0YS4gV2UgdGhlbiBuZWVkIHRvIGNvbGxlY3QgdGhlIG91dHB1dHMgaW4gYSBuZXcgZGF0YS5mcmFtZS4KCmBgYHtyLCBtZXNzYWdlPUYsIHdhcm5pbmc9Rn0KcmVxdWlyZShkcGx5cikKCnNjYWxlZF9kYXRhIDwtIE5VTEwKCmZvcih2YXIgaW4gbmFtZXMoYWlyLmRhdGEpKXsKICAgIAogICAgc2NhbGVkX2RhdGEgPC0gY2JpbmQoc2NhbGVkX2RhdGEsIAogICAgICAgICAgICAgICAgICAgICAgICAgc2NhbGUoYWlyLmRhdGFbLHZhcl0sIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2NhbGUgPSBULCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNlbnRlciA9IFQpKQp9CgojIGNvbnZlcnQgdG8gZGF0YS5mcmFtZSBhbmQgbmFtZQpzY2FsZWRfZGF0YSA8LSBhcy5kYXRhLmZyYW1lKHNjYWxlZF9kYXRhKSAlPiUgc2V0TmFtZXMobmFtZXMoYWlyLmRhdGEpKQoKaGVhZChzY2FsZWRfZGF0YSkKYGBgCgo8YnI+CgojIyMgKipvdGhlcioqCgptb3JlIGNvbXBsZXggb3V0cHV0cyBjYW4gYmUgY29sbGVjdGVkIGluICoqbGlzdHMqKi4gRm9yIGV4YW1wbGUsIHNheSB3ZSB3YW50ZWQgdG8gZml0IGEgbGluZWFyIG1vZGVsIHdpdGggYCJPem9uZSJgIGFzIHRoZSByZXNwb25zZSB2YXJpYWJsZSBhbmQgZWFjaCBvZiB0aGUgb3RoZXIgdmFyaWFibGVzIGFzIHNpbmdsZSBwcmVkaWN0b3JzLiBXZSBjYW4gbG9vcCB0aGUgcHJvY2VzcyBhbmQgY29sbGVjdCB0aGUgb3V0cHV0cyBvZiB0aGUgYGxtKClgIGZ1bmN0aW9uIGluIGEgbGlzdC4KYGBge3J9CgpwcmVkaWN0b3JzIDwtIG5hbWVzKGFpci5kYXRhKVtuYW1lcyhhaXIuZGF0YSkgIT0gIk96b25lIl0KYWlyX21vZHMgPC0gTlVMTAoKZm9yKHByZWRpY3RvciBpbiBwcmVkaWN0b3JzKXsKICAgIAogICAgYWlyX21vZHMgPC0gYyhhaXJfbW9kcywKICAgIGxpc3QobG0oYXMuZm9ybXVsYShwYXN0ZSgiT3pvbmUgfiIsIHByZWRpY3RvcikpLCBkYXRhID0gYWlyLmRhdGEpKSkKfQoKc3RyKGFpcl9tb2RzLCBtYXgubGV2ZWwgPSAxKQpgYGAKPGJyPgo8YnI+CgoqKioKCiMjICoqQWx0ZXJpbmcgbG9vcGluZyBzZXF1ZW5jZXMqKgoKIyMjIGJyZWFrCgpicmVhayBpcyBhIGJpdCBsaWtlIGBzdG9wKClgIGJ1dCBmb3IgYSBsb29wLiBJdCBpcyB1c3VhbGx5IHVzZWQgd2l0aCBhIGNvbmRpdGlvbmFsIHN0YXRlbWVudCBhbmQgaWYgdHJpZ2dlcmVkLCBicmVha3Mgb3V0IG9mIHRoZSBjdXJyZW50IGxvb3AuCgo8aW1nIHNyYz1hc3NldHMvYnJlYWtGbG93Y2hhcnQuanBnIGhlaWdodCA9IjE1MHB4IiB3aWR0aD0iMTUwcHgiPiAKCmBgYHtyfQp4IDwtIDE6NQoKZm9yICh2YWwgaW4geCkgewogICAgaWYgKHZhbCA9PSAzKXsKICAgICAgICBicmVhawogICAgfQogICAgcHJpbnQodmFsKQp9CmBgYAoKSW4gdGhpcyBleGFtcGxlLCB3ZSBpdGVyYXRlIG92ZXIgdGhlIHZlY3RvciBgeGAsIHdoaWNoIGhhcyBjb25zZWN1dGl2ZSBudW1iZXJzIGZyb20gMSB0byA1LiBJbnNpZGUgdGhlIGZvciBsb29wIHdlIGhhdmUgdXNlZCBhIGNvbmRpdGlvbiB0byAqKmJyZWFrIGlmIHRoZSBjdXJyZW50IHZhbHVlIGlzIGVxdWFsIHRvIDMqKi4gQXMgd2UgY2FuIHNlZSBmcm9tIHRoZSBvdXRwdXQsIHRoZSBsb29wIHRlcm1pbmF0ZXMgd2hlbiBpdCBlbmNvdW50ZXJzIHRoZSBicmVhayBzdGF0ZW1lbnQuCgoKIyMjIG5leHQKCioqYG5leHRgKiogaXMgc2ltaWxhcmx5IHVzZWQgaW4gY29uanVuY3Rpb24gd2l0aCBhIGNvbmRpdGlvbmFsIHN0YXRlbWVudCBidXQgaWYgdHJpZ2dlcmVkIGp1c3QgbW92ZXMgb24gdG8gdGhlIG5leHQgaXRlcmF0aW9uLgoKPGltZyBzcmM9YXNzZXRzL25leHRGbG93Y2hhcnQuanBnIGhlaWdodCA9IjE1MHB4IiB3aWR0aD0iMTUwcHgiPiAKCmBgYHtyfQp4IDwtIDE6NQoKZm9yICh2YWwgaW4geCkgewogICAgaWYgKHZhbCA9PSAzKXsKICAgICAgICBuZXh0CiAgICB9CiAgICBwcmludCh2YWwpCn0KYGBgCgpJbiB0aGlzIGV4YW1wbGUsIHdlIHVzZSB0aGUgYG5leHRgIHN0YXRlbWVudCBpbnNpZGUgYSBjb25kaXRpb24gdG8gY2hlY2sgaWYgdGhlIHZhbHVlIGlzIGVxdWFsIHRvIDMuIElmIHRoZSB2YWx1ZSBpcyBlcXVhbCB0byAzLCB0aGUgKipjdXJyZW50IGV2YWx1YXRpb24gc3RvcHMqKiAodmFsdWUgaXMgbm90IHByaW50ZWQpIGJ1dCB0aGUgKipsb29wIGNvbnRpbnVlcyoqIHdpdGggdGhlIG5leHQgaXRlcmF0aW9uLiBUaGUgb3V0cHV0IHJlZmxlY3RzIHRoaXMuCgpUaGlzIGNhbiBiZSBwYXJ0aWN1bGFybHkgdXNlZnVsIGlmIHdlIHdhbnQgdG8sIGZvciBleGFtcGxlLCB0ZXN0IGZvciBhbiBlcnJvciBhbmQgZGlzY2FyZCBhbiBpdGVyYXRpb24gaWYgdGhlIGVycm9yIG9jY3VycwoKCjxicj4KPGJyPgoKKioqCgojIyB2ZWN0b3Jpc2F0aW9uICh0aGUgYXBwbHkgZnVuY3Rpb24gZmFtaWx5KQoKSXQncyBhbHdheXMgZ29vZCB0byBzdGFydCBsZWFybmluZyB0aGUgcHJpbmNpcGxlcyBvZiBpdGVyYXRpb24gdGhyb3VnaCBsb29wcy4gKipTaW1wbGUgbG9vcHMgY2FuIGJlIG1vcmUgdW5kZXJzdGFuZGFibGUgdG8gYSBodW1hbiByZWFkZXIqKgoKSG93ZXZlciwgbG9vcHMgY2FuIGJlIHNsb3csIGFuZCBpbiBjYXNlcyB3ZXJlIGNvbXB1dGF0aW9uIHRpbWUgb2YgYSBsb29wIGJlY29tZXMgYSBib3R0bGVuZWNrLCBpdCBpcyBnb29kIHRvIGtub3cgYSBiaXQgYWJvdXQgdmVjdG9yaXNhdGlvbi4gCgpTbyBsZXQncyBzZWUgd2hhdCBvdXIgYGZvcmAgbG9vcCBleGFtcGxlcyBsb29rIGxpa2UgdmVjdG9yaXNlZDoKCjxicj4KCiMjIyBhcHBseQoKKipgYXBwbHlgKiogaXRlcmF0ZXMgb3ZlciB0aGUgbWFyZ2lucyBvZiBhbiBhcnJheS4gV2UgY2FuIHVzZSBpdCB0byBjYWxjdWxhdGUgdGhlIG1lYW5zIG9mIGVhY2ggY29sdW1uOgoKYGBge3J9Cm11IDwtIGFwcGx5KGFpci5kYXRhLCBNQVJHSU4gPSAyLCBGVU4gPSBmdW5jdGlvbih4KXttZWFuKHgsIG5hLnJtID0gVCl9KQoKYGBgCgo8YnI+CgojIyMgbGFwcGx5CgpUaGUgKipgbGFwcGx5YCoqIHRha2VzIGEgKipgbGlzdGAqKiBhcyBhbiBpbnB1dCAoZGF0YS5mcmFtZXMgYXJlIGxpc3RzKSBhbmQgYXBwbHkgYSBmdW5jdGlvbiBvdmVyIGVhY2ggZWxlbWVudCBvZiB0aGUgbGlzdDoKCmBgYHtyfQoKc2NhbGVkX2RhdGEgPC0gbGFwcGx5KGFpci5kYXRhLCBGVU4gPSBmdW5jdGlvbih4KXsKICAgIHNjYWxlKHgsIHNjYWxlID0gVCwgY2VudGVyID0gVCl9KSAlPiUgCiAgICBkYXRhLmZyYW1lKCkgJT4lCiAgICBzZXROYW1lcyhuYW1lcyhhaXIuZGF0YSkpCgpoZWFkKHNjYWxlZF9kYXRhKQpgYGAKCjxicj4KCiMjIyBtYXBwbHkKClRoZSAqKmBtYXBwbHlgKiogYWxsb3dzIHVzIHRvIHBhc3MgbXVsdGlwbGUgaXRlcmF0ZWQgYXJndW1lbnRzIHRvIGEgZnVuY3Rpb24uIEl0IGhhcyBhIGRpZmZlcmVudCBzdHJ1Y3R1cmUgYXMgdGhlIGZ1bmN0aW9uIGlzIHRoZSBmaXJzdCBhcmd1bWVudCwgYW55IGFyZ3VtZW50cyB0byBiZSBwYXNzZWQgdG8gdGhlIGZ1bmN0aW9uIGFuZCBpdGVyYXRlZCBvdmVyIGFyZSBzcGVjaWZpZWQgaW4gYC4uLmAgYW5kIGFueSBhcmd1bWVudHMgdG8gYmUgdXNlZCBhcyBpcyBieSB0aGUgZnVuY3Rpb24gYXJlIHN1cHBsaWVkIGluIHRoZSBhcmd1bWVudCBgTW9yZUFyZ3NgLgoKQXMgYW4gZXhhbXBsZSwgd2Ugd2lsbCByZXBsaWNhdGUgdGhlIGRlZmF1bHQgYmVoYXZpb3VyIG9mIGBzY2FsZWAgdG8gY2VudGVyIG9uIHRoZSBtZWFuIGJ5IHN1cHBseSBhcmUgb3duIHZlY3RvciBvZiBjYWxjdWxhdGVkIG1lYW5zIGBtdWAuCgpgYGB7cn0KCnNjYWxlZF9kYXRhIDwtIG1hcHBseShGVU4gPSBmdW5jdGlvbih4LCBjZW50ZXIpe3NjYWxlKHgsIHNjYWxlID0gVCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjZW50ZXIgPSBjZW50ZXIpfSwKICAgICAgICAgICAgICAgICAgICAgIHggPSBhaXIuZGF0YSwgY2VudGVyID0gbXUpICU+JSAKICAgIGRhdGEuZnJhbWUoKSAlPiUKICAgIHNldE5hbWVzKG5hbWVzKGFpci5kYXRhKSkKCmhlYWQoc2NhbGVkX2RhdGEpCmBgYAoKCiMjIyBUaGluZ3MgdG8gcmVtZW1iZXI6CgotIGxvb3BzIGFyZSBldmFsdWF0ZWQgaW4gdGhlIGdsb2JhbCBlbnZpcm9ubWVudCAtPiBjYW4gZ2V0IG1lc3N5IQotIGlmIHlvdSd2ZSBnb3QgYSBsb3Qgb2YgY29kZSB3aXRoaW4geW91ciBsb29wLCAqKmNvbnNpZGVyIHdyaXRpbmcgYSBmdW5jdGlvbioqCgoqKioKCjxicj4KPGJyPgoKCgojIyMgQ2hlYXRzCgpBIGxvdCBvZiB0aGUgZXhhbXBsZXMgSSBzaG93ZWQgYXJlIGFjdHVhbGx5IGFkZHJlc3NlZCBieSB0aGVzZSBvciBvdGhlciBmdW5jdGlvbnMuIAoKZWcgYHNjYWxlKClgIGNhbiBiZSBhcHBsaWVkIGRpcmVjdGx5IHRvIGEgZGF0YS5mcmFtZToKYGBge3J9CmhlYWQoc2NhbGUoYWlyLmRhdGEpKQpgYGAKCmFuZCB0aGVyZSBhcmUgaW4tYnVpbHQgZnVuY3Rpb25zIGZvciBjYWxjdWxhdGluZyB0aGUgbWVhbiBvZiBjb2x1bW5zOgpgYGB7cn0KY29sTWVhbnMoYWlyLmRhdGEsIG5hLnJtID0gVCkKYGBgCgpCdXQgdGhlIHByaW5jaXBsZXMgb2YgYXBwbHlpbmcgZnVuY3Rpb25zIG92ZXIgbG9vcHMgYXJlIHN0aWxsIHRoZSBzYW1lLgoKCioqKgoKPGJyPgo8YnI+CgojIyMgKipFeGVyY2lzZXMqKgoKIyMjIyAqKnNvdXJjZTogPGh0dHA6Ly9yLWV4ZXJjaXNlcy5jb20vMjAxNi8wNi8wMS9zY3JpcHRpbmctbG9vcHMtaW4tci8+KioKCioqRXhlcmNpc2UgMyoqCgpXaXRoLCBpIDwtIDEsIHdyaXRlIGEgd2hpbGUoKSBsb29wIHRoYXQgcHJpbnRzIHRoZSBvZGQgbnVtYmVycyBmcm9tIDEgdGhyb3VnaCA3LgoKKipFeGVyY2lzZSA0KioKClVzaW5nIHRoZSBmb2xsb3dpbmcgdmFyaWFibGVzOgoKbXNnIDwtIGMoIkhlbGxvIikKaSA8LSAxCgpXcml0ZSBhIGB3aGlsZSgpYCBsb29wIHRoYXQgaW5jcmVtZW50cyB0aGUgdmFyaWFibGUsIGBpYCwgNiB0aW1lcywgYW5kIHByaW50cyBgbXNnYCBhdCBldmVyeSBpdGVyYXRpb24uCgoqKkV4ZXJjaXNlIDUqKgoKV3JpdGUgYSBgZm9yKClgIGxvb3AgdGhhdCBwcmludHMgdGhlIGZpcnN0IGZvdXIgbnVtYmVycyBvZiB0aGlzIHNlcXVlbmNlOiAKYGBge3J9CnggPC0gYyg3LCA0LCAzLCA4LCA5LCAyNSkKYGBgCgoqKkV4ZXJjaXNlIDYqKgoKRm9yIHRoZSBuZXh0IGV4ZXJjaXNlLCB3cml0ZSBhIGZvcigpIGxvb3AgdGhhdCBwcmludHMgYWxsIHRoZSBsZXR0ZXJzIGluOgpgYGB7cn0KeSA8LSBjKCJxIiwgInciLCAiZSIsICJyIiwgInoiLCAiYyIpCmBgYAoKCioqRXhlcmNpc2UgNyoqCgpVc2luZyBgaSA8LSAxYCwgd3JpdGUgYSBgd2hpbGUoKWAgbG9vcCB0aGF0IHByaW50cyB0aGUgdmFyaWFibGUsIGBpYCwgKHRoYXQgaXMgaW5jcmVtZW50ZWQgZnJvbSAxIOKAkyA1KSwgYW5kIHVzZXMgYnJlYWsgdG8gZXhpdCB0aGUgbG9vcCBpZiBgaWAgZXF1YWxzIDMuCgoqKkV4ZXJjaXNlIDgqKgoKV3JpdGUgYSBuZXN0ZWQgbG9vcCwgd2hlcmUgdGhlICoqb3V0ZXIgYGZvcigpYCBsb29wKiogaW5jcmVtZW50cyBgYWAgMyB0aW1lcywgYW5kIHRoZSAqKmlubmVyIGBmb3IoKWAgbG9vcCoqIGluY3JlbWVudHMgYGJgIDMgdGltZXMuIFRoZSBgYnJlYWtgIHN0YXRlbWVudCBleGl0cyB0aGUgaW5uZXIgYGZvcigpYCBsb29wIGFmdGVyIDIgaW5jcmVtZW50YXRpb25zLiBUaGUgbmVzdGVkIGxvb3AgcHJpbnRzIHRoZSB2YWx1ZXMgb2YgdmFyaWFibGVzLCBgYWAgYW5kIGBiYC4KCioqRXhlcmNpc2UgOSoqCgpXcml0ZSBhIGB3aGlsZSgpYCBsb29wIHRoYXQgKipwcmludHMgdGhlIHZhcmlhYmxlLCBgaWAqKiwgdGhhdCBpcyBpbmNyZW1lbnRlZCBmcm9tIDIg4oCTIDUsIGFuZCB1c2VzIHRoZSBuZXh0IHN0YXRlbWVudCwgdG8gc2tpcCB0aGUgcHJpbnRpbmcgb2YgdGhlIG51bWJlciAzLgoKKipFeGVyY2lzZSAxMCoqCgpXcml0ZSBhIGZvcigpIGxvb3AgdGhhdCB1c2VzIG5leHQgdG8gcHJpbnQgYWxsIHZhbHVlcyBleGNlcHQgYDNgIGluIHRoZSBmb2xsb3dpbmcgdmFyaWFibGU6IGBpYCA8LSAxOjUKCiMjIyMgWyoqU09MVVRJT05TKipdKGh0dHA6Ly9yLWV4ZXJjaXNlcy5jb20vMjAxNi8wNi8wMS9zY3JpcHRpbmctbG9vcHMtaW4tci1zb2x1dGlvbnMvKQoKCgoqKioKCjxicj4KPGJyPgojIyMgLlJtZCBmaWxlCgo8aHR0cHM6Ly9naXRodWIuY29tL2FubmFrcnlzdGFsbGkvVU5BTS9ibG9iL21hc3Rlci9Db25kaXRpb25hbHNfJTI2X2xvb3BpbmcuUm1kPg==