Relational Data with Dplyr

Three families of verbs designed to work with relational data:
  • Mutating Joins
  • Filtering Joins
  • Set Operations
  • Pre requisites

    library(tidyverse)
    library(nycflights13)

    Primay keys should be unique. This is how to verify that there is only one record per key

    library(tidyverse)
    package <U+393C><U+3E31>tidyverse<U+393C><U+3E32> was built under R version 3.3.3Loading tidyverse: ggplot2
    Loading tidyverse: tibble
    Loading tidyverse: tidyr
    Loading tidyverse: readr
    Loading tidyverse: purrr
    Loading tidyverse: dplyr
    Conflicts with tidy packages ------------------------------------------------------------------------------------
    filter(): dplyr, stats
    lag():    dplyr, stats
    library(nycflights13)
    package <U+393C><U+3E31>nycflights13<U+393C><U+3E32> was built under R version 3.3.3
    planes %>%
      count(tailnum) %>%
      filter(n > 1)
    weather %>%
      count(year,month,day, hour, origin) %>%
      filter(n > 1)
    When a table lacks a unique key, it might be useful to create a surrogate key from mutate() and row_number() to make it easier to match observatins if you’ve done some filtering and want to check back in with the original data.

    # excercie add a surrogate key to flights
    flights %>% 
      arrange(year, month, day, sched_dep_time, carrier, flight) %>%
      mutate(flight_id = row_number()) %>%
      glimpse()
    Observations: 336,776
    Variables: 20
    $ year           <int> 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013, 2013...
    $ month          <int> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1...
    $ day            <int> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1...
    $ dep_time       <int> 517, 533, 542, 544, 554, 559, 558, 559, 558, 558, 557, NA, 601, 600, 555, 554, 557, 608,...
    $ sched_dep_time <int> 515, 529, 540, 545, 558, 559, 600, 600, 600, 600, 600, 600, 600, 600, 600, 600, 600, 600...
    $ dep_delay      <dbl> 2, 4, 2, -1, -4, 0, -2, -1, -2, -2, -3, NA, 1, 0, -5, -6, -3, 8, 0, -2, 11, -2, -1, -3, ...
    $ arr_time       <int> 830, 850, 923, 1004, 740, 702, 753, 941, 849, 853, 838, NA, 844, 851, 913, 812, 709, 807...
    $ sched_arr_time <int> 819, 830, 850, 1022, 728, 706, 745, 910, 851, 856, 846, 901, 850, 858, 854, 837, 723, 73...
    $ arr_delay      <dbl> 11, 20, 33, -18, 12, -4, 8, 31, -2, -3, -8, NA, -6, -7, 19, -25, -14, 32, 12, 7, 14, -14...
    $ carrier        <chr> "UA", "UA", "AA", "B6", "UA", "B6", "AA", "AA", "B6", "B6", "B6", "B6", "B6", "B6", "B6"...
    $ flight         <int> 1545, 1714, 1141, 725, 1696, 1806, 301, 707, 49, 71, 79, 125, 343, 371, 507, 461, 5708, ...
    $ tailnum        <chr> "N14228", "N24211", "N619AA", "N804JB", "N39463", "N708JB", "N3ALAA", "N3DUAA", "N793JB"...
    $ origin         <chr> "EWR", "LGA", "JFK", "JFK", "EWR", "JFK", "LGA", "LGA", "JFK", "JFK", "JFK", "JFK", "EWR...
    $ dest           <chr> "IAH", "IAH", "MIA", "BQN", "ORD", "BOS", "ORD", "DFW", "PBI", "TPA", "MCO", "FLL", "PBI...
    $ air_time       <dbl> 227, 227, 160, 183, 150, 44, 138, 257, 149, 158, 140, NA, 147, 152, 158, 116, 53, 139, 1...
    $ distance       <dbl> 1400, 1416, 1089, 1576, 719, 187, 733, 1389, 1028, 1005, 944, 1069, 1023, 1076, 1065, 76...
    $ hour           <dbl> 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6...
    $ minute         <dbl> 15, 29, 40, 45, 58, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 7, 8, 10, ...
    $ time_hour      <dttm> 2013-01-01 05:00:00, 2013-01-01 05:00:00, 2013-01-01 05:00:00, 2013-01-01 05:00:00, 201...
    $ flight_id      <int> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 2...
    Lahman::Batting %>%
    group_by(playerID, yearID) %>%
      filter(n() > 1) 
    # since there are multiple records above, we need to add one more variable to make n() >1 return no records.
    Lahman::Batting %>%
    group_by(playerID, yearID, stint) %>%
      filter(n() > 1)

    Mutating Joins

    Like mutate() the join functions add variables to the right. First we create a narrower dataset.

    flights2 <- flights %>%
      select(year:day, hour, origin, dest, tailnum, carrier)
    flights2

    Imagine you want to add the full airline name to the flights2 data. You can combine the airlines and the flights 2 data framew ith left_join()

    # look at what airlines table contain
    View(airlines)
    # then combine it with the flights2 table, but since we don't need origin and dest 
    # we take it out with -origin, -dest
    flights2 %>%
      select(-origin, -dest) %>%
      left_join(airlines, by = "carrier")

    Notice the name of the airline is now added as a new column., Another way is to use mutate()

    flights2 %>%
      select(-origin, -dest) %>%
      mutate(name = airlines$name[match(carrier,airlines$carrier)])

    Understanding Joins

    x <-  tribble( ~key, ~val_x,
                   1,"x1",
                   2,"x2",
                   3,"x3"
                   )
    x
    y <-  tribble(
      ~key, ~val_y,
      1,"y1",
      2,"y2",
      4,"y3"
    )
    y

    A join is a way of connecting each row in x to zero, one or more rows in y.

    Inner Join

    x %>%
      inner_join(y, by ="key")

    Outer Joins

    A left join keeps all observations in x.
    A right join keeps all observations in y.
    A full join keeps all observationsin x and y

    Duplicate Keys

    x <-  tribble( ~key, ~val_x,
                   1,"x1",
                   2,"x2",
                   2,"x3",
                   1, "x4"
                   )
    x
    y <-  tribble(
      ~key, ~val_y,
      1,"y1",
      2,"y2"
    )
    y
    left_join(x,y, by="key")
    x <-  tribble( ~key, ~val_x,
                   1,"x1",
                   2,"x2",
                   2,"x3",
                   3, "x4"
                   )
    x
    y <-  tribble(
      ~key, ~val_y,
      1,"y1",
      2,"y2",
      2,"y3",
      3,"y4"
    )
    y
    left_join(x,y, by="key")

    Defining Key Columns

    The default join by=NULL uses all variables that appear in both tables, the so-called natural jin. for example, the flights and weeather tables match on their common variables, year, month, day, hour and origin

    flights2 %>%
      left_join(weather)
    Joining, by = c("year", "month", "day", "hour", "origin")

    Join using a character vecto by =“x” This is like a natural join, but uses only some of the common variables. For example, flights and planes have year variables, but they mean different things so we only want to join by tailnum

    flights2 %>% 
      left_join(planes, by = "tailnum")

    Using a named character vector (variables names do not match ) bu = c(“a” =“b”)

    flights2 %>%
      left_join(airports, c("dest" = "faa"))

    Exercise: Compute the average delay by destination, then join on the air ports data frame so you can show the spatial distribution of delays.

    View(flights)
    airports %>%
      semi_join(flights, c("faa" = "dest")) %>%
      ggplot(aes(lon,lat)) +
      borders("state") +
      geom_point() +
      coord_quickmap()

    avg_dest_delays <-  flights %>%
      group_by(dest) %>%
      summarise(delay = mean(arr_delay, na.rm = TRUE)) %>%
      inner_join(airports, by = c(dest = "faa"))
    avg_dest_delays %>%
      ggplot(aes(lon,lat, colour = delay)) +
      borders("state") +
      geom_point() +
      coord_quickmap()

    Add location of the origin and destination to flights

    flights %>%
      left_join(airports, by = c(dest = "faa")) %>%
      left_join(airports, by = c(origin = "faa")) %>%
      head()

    Is there a relationship between the age of the plane and its delays?

    plane_ages <- 
      planes %>%
      mutate(age = 2013 - year) %>%
      select(tailnum,age)
    flights %>%
      inner_join(plane_ages, by ="tailnum") %>%
      group_by(age) %>%
      filter(!is.na(dep_delay)) %>%
      summarise(delay = mean(dep_delay)) %>%
      ggplot(aes(x =age, y =delay)) + 
      geom_point()+
      geom_line()

    What weather conditions make it more likely to see a delay?

    flight_weather <-
      flights %>%
      inner_join(weather, by = c("origin" = "origin",
                                "year" = "year",
                                "month" = "month",
                                "day" = "day",
                                "hour" = "hour"))
    flight_weather %>%
      group_by(precip) %>%
      summarise(delay = mean(dep_delay, na.rm = TRUE)) %>%
      ggplot(aes(x = precip, y = delay)) +
        geom_line() + geom_point()

    What happened on June 13, 2013 display the spatial pattern of delays and then use Google to cross-reference with the weather.

    flights %>%
      filter(year == 2013, month == 6, day == 13) %>%
      group_by(dest) %>%
      summarise(delay = mean(arr_delay, na.rm = TRUE)) %>%
      inner_join(airports, by = c("dest" = "faa")) %>%
      ggplot(aes(y = lat, x = lon, size = delay, colour = delay)) +
      borders("state") +
      geom_point() +
      coord_quickmap() + 
    Error: 

    Filtering Joins

    Filtering Joins match observations in the same way as mutating joins, but affect the number of observations, not the variables. There are two types:

    semi_join(x,y) keeps all observations in x that have a match in y.
    anti_join(x,y) drops all observation in x that have a match in y.

    Why semi_joins are important: imagine you’ve found the top 10 most popular destinations:

    top_dest <-  flights %>%
      count(dest, sort = TRUE) %>%
      head(10)
    top_dest

    Now you want to find each flight that went to one of those destinations. You could contrsuct a filter yourself:

    flights %>%
      filter(dest %in% top_dest$dest)

    It is difficult to extend that approach to multiple variables. How would you construct the filter statement that used year, month, and day to match it back to flights??

    flights %>%
      semi_join(top_dest)
    Joining, by = "dest"

    Anti join

    Anti joins are useful for diagnosing join mismatches. For example, when connecting flights and planes, you might be interested to know that there are many flights that don’t have a match in planes:

    flights %>%
      anti_join(planes, by = "tailnum") %>%
                count(tailnum, sort=TRUE)

    Exercises:

    What does it mean for a flight to have a missing tailnum? What do the tail numbers that don’t have a matching record in plances have in common? (Hint: one variable explains ~90% of the problems)

    flights %>%
      anti_join(planes, by = "tailnum") %>%
      count(carrier, sort = TRUE)

    So we find that Envoy Airlines (MQ) and American Airlines(AA) don’t report tail numbers.

    Filter flights to show flights with planes that have flown at least 100 flights

    planes_gt100 <- 
      filter(flights) %>%
      group_by(tailnum) %>%
      count() %>%
      filter(n > 100)
    flights %>%
      semi_join(planes_gt100, by = "tailnum")

    Join Problems

    Your own data is unlikely to be so nice. So there are a few things that you should do with your own data to make your joins go smoothly:

    1. Start by identifying the variables that form the primary key in each table. You should usually do this based on your understanding of the data. Not empirically by looking for a combination of variables that give a unique identifier.
    2. Check that none of the variables in the primary key are missing. If a value is missing then it can’t identify an observation!
    3. Check that your foreign keys match primary keys in another table. The best way to do this is with an anti_join()

    Set Operations

    Least used of the 3 types of verbs but occasionally useful when you want to break a single complex filter into simpler pieces. All these operations work with a complete row, comparing the values of every variable. These expect the x an dy inputs to have the same variables, and treat the observations like sets:

    intersect(x,y) returns only observations in both x and y.
    union(x,y) return unique observations in x and y
    setdiff(x,y) return observations in x, but not in y.

    df1 <-  tribble(~x, ~y,
                    1,1,
                    2,1)
    df2 <-  tribble( ~x, ~y,
                     1,1,
                     1,2)
    df1
    df2

    The four possibilities are:

    # intersect(x,y)
    intersect(df1,df2)
    # union 
    union(df1,df2)
    # setdiff
    # return observations in x but not in y
    setdiff(df1,df2)
    setdiff(df2,df1)
    LS0tDQp0aXRsZTogIlIgRm9yIERhdGEgU2NpZW5jZSBDaGFwdGVyIDEwICINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCjxoMT4gUmVsYXRpb25hbCBEYXRhIHdpdGggRHBseXIgPC9oMT4NCg0KVGhyZWUgZmFtaWxpZXMgb2YgdmVyYnMgZGVzaWduZWQgdG8gd29yayB3aXRoIHJlbGF0aW9uYWwgZGF0YTogPC9icj4NCjxsaT4gTXV0YXRpbmcgSm9pbnMgPC9saT4NCjxsaT4gRmlsdGVyaW5nIEpvaW5zIDwvbGk+DQo8bGk+IFNldCBPcGVyYXRpb25zPC9saT4NCg0KPGgyPiBQcmUgcmVxdWlzaXRlcyA8L2gyPg0KbGlicmFyeSh0aWR5dmVyc2UpIDwvYnI+DQpsaWJyYXJ5KG55Y2ZsaWdodHMxMykgPC9icj4NCg0KPGltZyBzcmM9Imh0dHA6Ly9yNGRzLmhhZC5jby5uei9kaWFncmFtcy9yZWxhdGlvbmFsLW55Y2ZsaWdodHMucG5nIj4gPC9pbWc+DQoNClByaW1heSBrZXlzIHNob3VsZCBiZSB1bmlxdWUuIFRoaXMgaXMgaG93IHRvIHZlcmlmeSB0aGF0IHRoZXJlIGlzIG9ubHkgb25lIHJlY29yZCBwZXIga2V5DQoNCmBgYHtyfQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KG55Y2ZsaWdodHMxMykNCg0KcGxhbmVzICU+JQ0KICBjb3VudCh0YWlsbnVtKSAlPiUNCiAgZmlsdGVyKG4gPiAxKQ0KDQp3ZWF0aGVyICU+JQ0KICBjb3VudCh5ZWFyLG1vbnRoLGRheSwgaG91ciwgb3JpZ2luKSAlPiUNCiAgZmlsdGVyKG4gPiAxKQ0KDQoNCg0KYGBgDQoNCldoZW4gYSB0YWJsZSBsYWNrcyBhIHVuaXF1ZSBrZXksIGl0IG1pZ2h0IGJlIHVzZWZ1bCB0byBjcmVhdGUgYSBzdXJyb2dhdGUga2V5IGZyb20gbXV0YXRlKCkgYW5kIHJvd19udW1iZXIoKSB0byBtYWtlIGl0IGVhc2llciB0byBtYXRjaCBvYnNlcnZhdGlucyBpZiB5b3UndmUgZG9uZSBzb21lIGZpbHRlcmluZyBhbmQgd2FudCB0byBjaGVjayBiYWNrIGluIHdpdGggdGhlIG9yaWdpbmFsIGRhdGEuIDwvcD4NCg0KDQpgYGB7cn0NCiMgZXhjZXJjaWUgYWRkIGEgc3Vycm9nYXRlIGtleSB0byBmbGlnaHRzDQpmbGlnaHRzICU+JSANCiAgYXJyYW5nZSh5ZWFyLCBtb250aCwgZGF5LCBzY2hlZF9kZXBfdGltZSwgY2FycmllciwgZmxpZ2h0KSAlPiUNCiAgbXV0YXRlKGZsaWdodF9pZCA9IHJvd19udW1iZXIoKSkgJT4lDQogIGdsaW1wc2UoKQ0KYGBgDQoNCmBgYHtyfQ0KIyBmaW5kaW5nIHRoZSB1bmlxdWUgcHJpbWFyeSBrZXkNCkxhaG1hbjo6QmF0dGluZyAlPiUNCmdyb3VwX2J5KHBsYXllcklELCB5ZWFySUQpICU+JQ0KICBmaWx0ZXIobigpID4gMSkgDQpgYGAgDQoNCmBgYHtyfQ0KIyBzaW5jZSB0aGVyZSBhcmUgbXVsdGlwbGUgcmVjb3JkcyBhYm92ZSwgd2UgbmVlZCB0byBhZGQgb25lIG1vcmUgdmFyaWFibGUgdG8gbWFrZSBuKCkgPjEgcmV0dXJuIG5vIHJlY29yZHMuDQpMYWhtYW46OkJhdHRpbmcgJT4lDQpncm91cF9ieShwbGF5ZXJJRCwgeWVhcklELCBzdGludCkgJT4lDQogIGZpbHRlcihuKCkgPiAxKQ0KDQpgYGANCg0KPGgyPiBNdXRhdGluZyBKb2lucyA8L2gyPg0KDQpMaWtlIG11dGF0ZSgpIHRoZSBqb2luIGZ1bmN0aW9ucyBhZGQgdmFyaWFibGVzIHRvIHRoZSByaWdodC4gRmlyc3Qgd2UgY3JlYXRlIGEgbmFycm93ZXIgZGF0YXNldC4NCg0KYGBge3J9DQpmbGlnaHRzMiA8LSBmbGlnaHRzICU+JQ0KICBzZWxlY3QoeWVhcjpkYXksIGhvdXIsIG9yaWdpbiwgZGVzdCwgdGFpbG51bSwgY2FycmllcikNCmZsaWdodHMyDQoNCmBgYA0KDQpJbWFnaW5lIHlvdSB3YW50IHRvIGFkZCB0aGUgZnVsbCBhaXJsaW5lIG5hbWUgdG8gdGhlIGZsaWdodHMyIGRhdGEuIFlvdSBjYW4gY29tYmluZSB0aGUgYWlybGluZXMgYW5kIHRoZSBmbGlnaHRzIDIgZGF0YSBmcmFtZXcgaXRoIGxlZnRfam9pbigpDQoNCmBgYHtyfQ0KIyBsb29rIGF0IHdoYXQgYWlybGluZXMgdGFibGUgY29udGFpbg0KVmlldyhhaXJsaW5lcykNCiMgdGhlbiBjb21iaW5lIGl0IHdpdGggdGhlIGZsaWdodHMyIHRhYmxlLCBidXQgc2luY2Ugd2UgZG9uJ3QgbmVlZCBvcmlnaW4gYW5kIGRlc3QgDQojIHdlIHRha2UgaXQgb3V0IHdpdGggLW9yaWdpbiwgLWRlc3QNCg0KDQoNCmBgYA0KDQoNCg0KYGBge3J9DQpmbGlnaHRzMiAlPiUNCiAgc2VsZWN0KC1vcmlnaW4sIC1kZXN0KSAlPiUNCiAgbGVmdF9qb2luKGFpcmxpbmVzLCBieSA9ICJjYXJyaWVyIikNCg0KYGBgDQoNCk5vdGljZSB0aGUgbmFtZSBvZiB0aGUgYWlybGluZSBpcyBub3cgYWRkZWQgYXMgYSBuZXcgY29sdW1uLiwgQW5vdGhlciB3YXkgaXMgdG8gdXNlIG11dGF0ZSgpIA0KDQpgYGB7cn0NCmZsaWdodHMyICU+JQ0KICBzZWxlY3QoLW9yaWdpbiwgLWRlc3QpICU+JQ0KICBtdXRhdGUobmFtZSA9IGFpcmxpbmVzJG5hbWVbbWF0Y2goY2FycmllcixhaXJsaW5lcyRjYXJyaWVyKV0pDQoNCmBgYA0KPGgyPiBVbmRlcnN0YW5kaW5nIEpvaW5zIDwvaDI+DQoNCmBgYHtyfQ0KeCA8LSAgdHJpYmJsZSggfmtleSwgfnZhbF94LA0KICAgICAgICAgICAgICAgMSwieDEiLA0KICAgICAgICAgICAgICAgMiwieDIiLA0KICAgICAgICAgICAgICAgMywieDMiDQogICAgICAgICAgICAgICApDQoNCngNCmBgYA0KYGBge3J9DQp5IDwtICB0cmliYmxlKA0KICB+a2V5LCB+dmFsX3ksDQogIDEsInkxIiwNCiAgMiwieTIiLA0KICA0LCJ5MyINCikNCnkNCg0KYGBgDQoNCkEgam9pbiBpcyBhIHdheSBvZiBjb25uZWN0aW5nIGVhY2ggcm93IGluIHggdG8gemVybywgb25lIG9yIG1vcmUgcm93cyBpbiB5Lg0KDQo8aDM+IElubmVyIEpvaW4gPC9oMz4NCg0KYGBge3J9DQojIHVubWF0Y2hlZCByb3dzIGFyZSBub3QgaW5jbHVkZWQgaW4gdGhlIHJlc3VsdA0KeCAlPiUNCiAgaW5uZXJfam9pbih5LCBieSA9ImtleSIpDQoNCmBgYA0KDQo8aDM+IE91dGVyIEpvaW5zIDwvaDM+DQogQSBsZWZ0IGpvaW4ga2VlcHMgYWxsIG9ic2VydmF0aW9ucyBpbiB4LiA8L2JyPg0KIEEgcmlnaHQgam9pbiBrZWVwcyBhbGwgb2JzZXJ2YXRpb25zIGluIHkuICA8L2JyPg0KIEEgZnVsbCBqb2luIGtlZXBzIGFsbCBvYnNlcnZhdGlvbnNpbiB4IGFuZCB5IDwvcD4NCg0KDQo8aDI+IER1cGxpY2F0ZSBLZXlzIDwvaDI+DQoNCmBgYHtyfQ0KDQp4IDwtICB0cmliYmxlKCB+a2V5LCB+dmFsX3gsDQogICAgICAgICAgICAgICAxLCJ4MSIsDQogICAgICAgICAgICAgICAyLCJ4MiIsDQogICAgICAgICAgICAgICAyLCJ4MyIsDQogICAgICAgICAgICAgICAxLCAieDQiDQogICAgICAgICAgICAgICApDQoNCngNCg0KDQp5IDwtICB0cmliYmxlKA0KICB+a2V5LCB+dmFsX3ksDQogIDEsInkxIiwNCiAgMiwieTIiDQopDQp5DQpgYGANCg0KYGBge3J9DQpsZWZ0X2pvaW4oeCx5LCBieT0ia2V5IikNCmBgYA0KDQpgYGB7cn0NCnggPC0gIHRyaWJibGUoIH5rZXksIH52YWxfeCwNCiAgICAgICAgICAgICAgIDEsIngxIiwNCiAgICAgICAgICAgICAgIDIsIngyIiwNCiAgICAgICAgICAgICAgIDIsIngzIiwNCiAgICAgICAgICAgICAgIDMsICJ4NCINCiAgICAgICAgICAgICAgICkNCg0KeA0KDQp5IDwtICB0cmliYmxlKA0KICB+a2V5LCB+dmFsX3ksDQogIDEsInkxIiwNCiAgMiwieTIiLA0KICAyLCJ5MyIsDQogIDMsInk0Ig0KKQ0KeQ0KDQpsZWZ0X2pvaW4oeCx5LCBieSA9ICJrZXkiKQ0KDQpgYGANCg0KPGgyPiBEZWZpbmluZyBLZXkgQ29sdW1ucyA8L2gyPg0KDQpUaGUgZGVmYXVsdCBqb2luIGJ5PU5VTEwgdXNlcyBhbGwgdmFyaWFibGVzIHRoYXQgYXBwZWFyIGluIGJvdGggdGFibGVzLCB0aGUgc28tY2FsbGVkIG5hdHVyYWwgamluLiBmb3IgZXhhbXBsZSwgdGhlIGZsaWdodHMgYW5kIHdlZWF0aGVyIHRhYmxlcyBtYXRjaCBvbiB0aGVpciBjb21tb24gdmFyaWFibGVzLCB5ZWFyLCBtb250aCwgZGF5LCBob3VyIGFuZCBvcmlnaW4NCg0KYGBge3J9DQpmbGlnaHRzMiAlPiUNCiAgbGVmdF9qb2luKHdlYXRoZXIpDQpgYGANCg0KSm9pbiB1c2luZyBhIGNoYXJhY3RlciB2ZWN0byBieSA9IngiIFRoaXMgaXMgbGlrZSBhIG5hdHVyYWwgam9pbiwgYnV0IHVzZXMgb25seSBzb21lIG9mIHRoZSBjb21tb24gdmFyaWFibGVzLiBGb3IgZXhhbXBsZSwgZmxpZ2h0cyBhbmQgcGxhbmVzIGhhdmUgeWVhciB2YXJpYWJsZXMsIGJ1dCB0aGV5IG1lYW4gZGlmZmVyZW50IHRoaW5ncyBzbyB3ZSBvbmx5IHdhbnQgdG8gam9pbiBieSB0YWlsbnVtDQoNCmBgYHtyfQ0KZmxpZ2h0czIgJT4lIA0KICBsZWZ0X2pvaW4ocGxhbmVzLCBieSA9ICJ0YWlsbnVtIikNCg0KYGBgDQoNCg0KVXNpbmcgYSBuYW1lZCBjaGFyYWN0ZXIgdmVjdG9yICh2YXJpYWJsZXMgbmFtZXMgZG8gbm90IG1hdGNoICkgYnUgPSBjKCJhIiA9ImIiKQ0KDQpgYGB7cn0NCmZsaWdodHMyICU+JQ0KICBsZWZ0X2pvaW4oYWlycG9ydHMsIGMoImRlc3QiID0gImZhYSIpKQ0KYGBgDQoNCkV4ZXJjaXNlOg0KQ29tcHV0ZSB0aGUgYXZlcmFnZSBkZWxheSBieSBkZXN0aW5hdGlvbiwgdGhlbiBqb2luIG9uIHRoZSBhaXIgcG9ydHMgZGF0YSBmcmFtZSBzbyB5b3UgY2FuIHNob3cgdGhlIHNwYXRpYWwgZGlzdHJpYnV0aW9uIG9mIGRlbGF5cy4gDQoNCg0KYGBge3J9DQpWaWV3KGZsaWdodHMpDQpgYGANCg0KYGBge3J9DQphaXJwb3J0cyAlPiUNCiAgc2VtaV9qb2luKGZsaWdodHMsIGMoImZhYSIgPSAiZGVzdCIpKSAlPiUNCiAgZ2dwbG90KGFlcyhsb24sbGF0KSkgKw0KICBib3JkZXJzKCJzdGF0ZSIpICsNCiAgZ2VvbV9wb2ludCgpICsNCiAgY29vcmRfcXVpY2ttYXAoKQ0KDQpgYGANCg0KYGBge3J9DQphdmdfZGVzdF9kZWxheXMgPC0gIGZsaWdodHMgJT4lDQogIGdyb3VwX2J5KGRlc3QpICU+JQ0KICBzdW1tYXJpc2UoZGVsYXkgPSBtZWFuKGFycl9kZWxheSwgbmEucm0gPSBUUlVFKSkgJT4lDQogIGlubmVyX2pvaW4oYWlycG9ydHMsIGJ5ID0gYyhkZXN0ID0gImZhYSIpKQ0KDQphdmdfZGVzdF9kZWxheXMgJT4lDQogIGdncGxvdChhZXMobG9uLGxhdCwgY29sb3VyID0gZGVsYXkpKSArDQogIGJvcmRlcnMoInN0YXRlIikgKw0KICBnZW9tX3BvaW50KCkgKw0KICBjb29yZF9xdWlja21hcCgpDQpgYGANCg0KQWRkIGxvY2F0aW9uIG9mIHRoZSBvcmlnaW4gYW5kIGRlc3RpbmF0aW9uIHRvIGZsaWdodHMNCg0KYGBge3J9DQoNCmZsaWdodHMgJT4lDQogIGxlZnRfam9pbihhaXJwb3J0cywgYnkgPSBjKGRlc3QgPSAiZmFhIikpICU+JQ0KICBsZWZ0X2pvaW4oYWlycG9ydHMsIGJ5ID0gYyhvcmlnaW4gPSAiZmFhIikpICU+JQ0KDQogIGhlYWQoKQ0KDQpgYGANCg0KSXMgdGhlcmUgYSByZWxhdGlvbnNoaXAgYmV0d2VlbiB0aGUgYWdlIG9mIHRoZSBwbGFuZSBhbmQgaXRzIGRlbGF5cz8NCg0KYGBge3J9DQpwbGFuZV9hZ2VzIDwtIA0KICBwbGFuZXMgJT4lDQogIG11dGF0ZShhZ2UgPSAyMDEzIC0geWVhcikgJT4lDQogIHNlbGVjdCh0YWlsbnVtLGFnZSkNCg0KZmxpZ2h0cyAlPiUNCiAgaW5uZXJfam9pbihwbGFuZV9hZ2VzLCBieSA9InRhaWxudW0iKSAlPiUNCiAgZ3JvdXBfYnkoYWdlKSAlPiUNCiAgZmlsdGVyKCFpcy5uYShkZXBfZGVsYXkpKSAlPiUNCiAgc3VtbWFyaXNlKGRlbGF5ID0gbWVhbihkZXBfZGVsYXkpKSAlPiUNCiAgZ2dwbG90KGFlcyh4ID1hZ2UsIHkgPWRlbGF5KSkgKyANCiAgZ2VvbV9wb2ludCgpKw0KICBnZW9tX2xpbmUoKQ0KDQpgYGANCg0KV2hhdCB3ZWF0aGVyIGNvbmRpdGlvbnMgbWFrZSBpdCBtb3JlIGxpa2VseSB0byBzZWUgYSBkZWxheT8NCg0KYGBge3J9DQpmbGlnaHRfd2VhdGhlciA8LQ0KICBmbGlnaHRzICU+JQ0KICBpbm5lcl9qb2luKHdlYXRoZXIsIGJ5ID0gYygib3JpZ2luIiA9ICJvcmlnaW4iLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICJ5ZWFyIiA9ICJ5ZWFyIiwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAibW9udGgiID0gIm1vbnRoIiwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAiZGF5IiA9ICJkYXkiLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICJob3VyIiA9ICJob3VyIikpDQoNCmZsaWdodF93ZWF0aGVyICU+JQ0KICBncm91cF9ieShwcmVjaXApICU+JQ0KICBzdW1tYXJpc2UoZGVsYXkgPSBtZWFuKGRlcF9kZWxheSwgbmEucm0gPSBUUlVFKSkgJT4lDQogIGdncGxvdChhZXMoeCA9IHByZWNpcCwgeSA9IGRlbGF5KSkgKw0KICAgIGdlb21fbGluZSgpICsgZ2VvbV9wb2ludCgpDQpgYGANCg0KDQpXaGF0IGhhcHBlbmVkIG9uIEp1bmUgMTMsIDIwMTMgZGlzcGxheSB0aGUgc3BhdGlhbCBwYXR0ZXJuIG9mIGRlbGF5cyBhbmQgdGhlbiB1c2UgR29vZ2xlIHRvIGNyb3NzLXJlZmVyZW5jZSB3aXRoIHRoZSB3ZWF0aGVyLiANCg0KYGBge3J9DQpmbGlnaHRzICU+JQ0KICBmaWx0ZXIoeWVhciA9PSAyMDEzLCBtb250aCA9PSA2LCBkYXkgPT0gMTMpICU+JQ0KICBncm91cF9ieShkZXN0KSAlPiUNCiAgc3VtbWFyaXNlKGRlbGF5ID0gbWVhbihhcnJfZGVsYXksIG5hLnJtID0gVFJVRSkpICU+JQ0KICBpbm5lcl9qb2luKGFpcnBvcnRzLCBieSA9IGMoImRlc3QiID0gImZhYSIpKSAlPiUNCiAgZ2dwbG90KGFlcyh5ID0gbGF0LCB4ID0gbG9uLCBzaXplID0gZGVsYXksIGNvbG91ciA9IGRlbGF5KSkgKw0KICBib3JkZXJzKCJzdGF0ZSIpICsNCiAgZ2VvbV9wb2ludCgpICsNCiAgY29vcmRfcXVpY2ttYXAoKSArIA0KDQoNCg0KYGBgDQoNCjxoMj4gRmlsdGVyaW5nIEpvaW5zIDwvaDI+DQoNCkZpbHRlcmluZyBKb2lucyBtYXRjaCBvYnNlcnZhdGlvbnMgaW4gdGhlIHNhbWUgd2F5IGFzIG11dGF0aW5nIGpvaW5zLCBidXQgYWZmZWN0IHRoZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zLCBub3QgdGhlIHZhcmlhYmxlcy4gVGhlcmUgYXJlIHR3byB0eXBlczogPC9icj4NCg0Kc2VtaV9qb2luKHgseSkga2VlcHMgYWxsIG9ic2VydmF0aW9ucyBpbiB4IHRoYXQgaGF2ZSBhIG1hdGNoIGluIHkuIDwvYnI+DQphbnRpX2pvaW4oeCx5KSBkcm9wcyBhbGwgb2JzZXJ2YXRpb24gaW4geCB0aGF0IGhhdmUgYSBtYXRjaCBpbiB5LiA8L3A+DQoNCg0KV2h5IHNlbWlfam9pbnMgYXJlIGltcG9ydGFudDogaW1hZ2luZSB5b3UndmUgZm91bmQgdGhlIHRvcCAxMCBtb3N0IHBvcHVsYXIgZGVzdGluYXRpb25zOg0KDQpgYGB7cn0NCnRvcF9kZXN0IDwtICBmbGlnaHRzICU+JQ0KICBjb3VudChkZXN0LCBzb3J0ID0gVFJVRSkgJT4lDQogIGhlYWQoMTApDQp0b3BfZGVzdA0KYGBgDQoNCk5vdyB5b3Ugd2FudCB0byBmaW5kIGVhY2ggZmxpZ2h0IHRoYXQgd2VudCB0byBvbmUgb2YgdGhvc2UgZGVzdGluYXRpb25zLiBZb3UgY291bGQgY29udHJzdWN0IGEgZmlsdGVyIHlvdXJzZWxmOg0KDQpgYGB7cn0NCmZsaWdodHMgJT4lDQogIGZpbHRlcihkZXN0ICVpbiUgdG9wX2Rlc3QkZGVzdCkNCmBgYA0KDQpJdCBpcyBkaWZmaWN1bHQgdG8gZXh0ZW5kIHRoYXQgYXBwcm9hY2ggdG8gbXVsdGlwbGUgdmFyaWFibGVzLiAgSG93IHdvdWxkIHlvdSBjb25zdHJ1Y3QgdGhlIGZpbHRlciBzdGF0ZW1lbnQgdGhhdCB1c2VkIHllYXIsIG1vbnRoLCBhbmQgZGF5IHRvIG1hdGNoIGl0IGJhY2sgdG8gZmxpZ2h0cz8/DQoNCg0KYGBge3J9DQpmbGlnaHRzICU+JQ0KICBzZW1pX2pvaW4odG9wX2Rlc3QpDQpgYGANCg0KDQo8aDM+IEFudGkgam9pbiA8L2gzPg0KDQpBbnRpIGpvaW5zIGFyZSB1c2VmdWwgZm9yIGRpYWdub3Npbmcgam9pbiBtaXNtYXRjaGVzLiBGb3IgZXhhbXBsZSwgd2hlbiBjb25uZWN0aW5nIGZsaWdodHMgYW5kIHBsYW5lcywgeW91IG1pZ2h0IGJlIGludGVyZXN0ZWQgdG8ga25vdyB0aGF0IHRoZXJlIGFyZSBtYW55IGZsaWdodHMgdGhhdCBkb24ndCBoYXZlIGEgbWF0Y2ggaW4gcGxhbmVzOg0KDQpgYGB7cn0NCmZsaWdodHMgJT4lDQogIGFudGlfam9pbihwbGFuZXMsIGJ5ID0gInRhaWxudW0iKSAlPiUNCiAgICAgICAgICAgIGNvdW50KHRhaWxudW0sIHNvcnQ9VFJVRSkNCmBgYA0KDQpFeGVyY2lzZXM6DQoNCldoYXQgZG9lcyBpdCBtZWFuIGZvciBhIGZsaWdodCB0byBoYXZlIGEgbWlzc2luZyB0YWlsbnVtPyBXaGF0IGRvIHRoZSB0YWlsIG51bWJlcnMgdGhhdCBkb24ndCBoYXZlIGEgbWF0Y2hpbmcgcmVjb3JkIGluIHBsYW5jZXMgaGF2ZSBpbiBjb21tb24/IChIaW50OiBvbmUgdmFyaWFibGUgZXhwbGFpbnMgfjkwJSBvZiB0aGUgcHJvYmxlbXMpDQoNCmBgYHtyfQ0KZmxpZ2h0cyAlPiUNCiAgYW50aV9qb2luKHBsYW5lcywgYnkgPSAidGFpbG51bSIpICU+JQ0KICBjb3VudChjYXJyaWVyLCBzb3J0ID0gVFJVRSkNCg0KYGBgDQoNClNvIHdlIGZpbmQgdGhhdCBFbnZveSBBaXJsaW5lcyAoTVEpIGFuZCBBbWVyaWNhbiBBaXJsaW5lcyhBQSkgZG9uJ3QgcmVwb3J0IHRhaWwgbnVtYmVycy4gDQoNCg0KRmlsdGVyIGZsaWdodHMgdG8gc2hvdyBmbGlnaHRzIHdpdGggcGxhbmVzIHRoYXQgaGF2ZSBmbG93biBhdCBsZWFzdCAxMDAgZmxpZ2h0cw0KDQpgYGB7cn0NCnBsYW5lc19ndDEwMCA8LSANCiAgZmlsdGVyKGZsaWdodHMpICU+JQ0KICBncm91cF9ieSh0YWlsbnVtKSAlPiUNCiAgY291bnQoKSAlPiUNCiAgZmlsdGVyKG4gPiAxMDApDQoNCmZsaWdodHMgJT4lDQogIHNlbWlfam9pbihwbGFuZXNfZ3QxMDAsIGJ5ID0gInRhaWxudW0iKQ0KDQoNCmBgYA0KDQo8aDI+IEpvaW4gUHJvYmxlbXMgPC9oMj4NCg0KWW91ciBvd24gZGF0YSBpcyB1bmxpa2VseSB0byBiZSBzbyBuaWNlLiBTbyB0aGVyZSBhcmUgYSBmZXcgdGhpbmdzIHRoYXQgeW91IHNob3VsZCBkbyB3aXRoIHlvdXIgb3duIGRhdGEgdG8gbWFrZSB5b3VyIGpvaW5zIGdvIHNtb290aGx5OiA8L3A+DQoxLiBTdGFydCBieSBpZGVudGlmeWluZyB0aGUgdmFyaWFibGVzIHRoYXQgZm9ybSB0aGUgcHJpbWFyeSBrZXkgaW4gZWFjaCB0YWJsZS4gWW91IHNob3VsZCB1c3VhbGx5IGRvIHRoaXMgYmFzZWQgb24geW91ciB1bmRlcnN0YW5kaW5nIG9mIHRoZSBkYXRhLiBOb3QgZW1waXJpY2FsbHkgYnkgbG9va2luZyBmb3IgYSBjb21iaW5hdGlvbiBvZiB2YXJpYWJsZXMgdGhhdCBnaXZlIGEgdW5pcXVlIGlkZW50aWZpZXIuIDwvYnI+DQoyLiBDaGVjayB0aGF0IG5vbmUgb2YgdGhlIHZhcmlhYmxlcyBpbiB0aGUgcHJpbWFyeSBrZXkgYXJlIG1pc3NpbmcuICBJZiBhIHZhbHVlIGlzIG1pc3NpbmcgdGhlbiBpdCBjYW4ndCBpZGVudGlmeSBhbiBvYnNlcnZhdGlvbiEgPC9icj4NCjMuIENoZWNrIHRoYXQgeW91ciBmb3JlaWduIGtleXMgbWF0Y2ggcHJpbWFyeSBrZXlzIGluIGFub3RoZXIgdGFibGUuIFRoZSBiZXN0IHdheSB0byBkbyB0aGlzIGlzIHdpdGggYW4gYW50aV9qb2luKCkgPC9icj4NCg0KPGgyPiBTZXQgT3BlcmF0aW9ucyA8L2gyPg0KTGVhc3QgdXNlZCBvZiB0aGUgMyB0eXBlcyBvZiB2ZXJicyBidXQgb2NjYXNpb25hbGx5IHVzZWZ1bCB3aGVuIHlvdSB3YW50IHRvIGJyZWFrIGEgc2luZ2xlIGNvbXBsZXggZmlsdGVyIGludG8gc2ltcGxlciBwaWVjZXMuIEFsbCB0aGVzZSBvcGVyYXRpb25zIHdvcmsgd2l0aCBhIGNvbXBsZXRlIHJvdywgY29tcGFyaW5nIHRoZSB2YWx1ZXMgb2YgZXZlcnkgdmFyaWFibGUuIFRoZXNlIGV4cGVjdCB0aGUgeCBhbiBkeSBpbnB1dHMgdG8gaGF2ZSB0aGUgc2FtZSB2YXJpYWJsZXMsIGFuZCB0cmVhdCB0aGUgb2JzZXJ2YXRpb25zIGxpa2Ugc2V0czogPC9icj4NCg0KaW50ZXJzZWN0KHgseSkgcmV0dXJucyBvbmx5IG9ic2VydmF0aW9ucyBpbiBib3RoIHggYW5kIHkuIDwvYnI+DQp1bmlvbih4LHkpIHJldHVybiB1bmlxdWUgb2JzZXJ2YXRpb25zIGluIHggYW5kIHkgPC9icj4NCnNldGRpZmYoeCx5KSByZXR1cm4gb2JzZXJ2YXRpb25zIGluIHgsIGJ1dCBub3QgaW4geS4gPC9wPg0KDQpgYGB7cn0NCmRmMSA8LSAgdHJpYmJsZSh+eCwgfnksDQogICAgICAgICAgICAgICAgMSwxLA0KICAgICAgICAgICAgICAgIDIsMSkNCg0KZGYyIDwtICB0cmliYmxlKCB+eCwgfnksDQogICAgICAgICAgICAgICAgIDEsMSwNCiAgICAgICAgICAgICAgICAgMSwyKQ0KDQpkZjENCmRmMg0KYGBgDQoNCg0KVGhlIGZvdXIgcG9zc2liaWxpdGllcyBhcmU6DQoNCmBgYHtyfQ0KIyBpbnRlcnNlY3QoeCx5KQ0KIyByZXR1cm5zIG9ubHkgb2JzZXJ2ZWF0aW9uIGluIGJvdGggZGYxIGFuZCBkZjINCmludGVyc2VjdChkZjEsZGYyKQ0KYGBgDQoNCmBgYHtyfQ0KIyB1bmlvbiByZXR1cm5zIHVuaXF1ZSBvYnNlcnZhdGlvbnMgaW4gZGYxIGFuZCBkZjINCiMgc28gMSwxLCBzaG93cyB1cCBvbmNlIA0KDQp1bmlvbihkZjEsZGYyKQ0KDQpgYGANCg0KDQpgYGB7cn0NCiMgc2V0ZGlmZg0KIyByZXR1cm4gb2JzZXJ2YXRpb25zIGluIHggYnV0IG5vdCBpbiB5DQpzZXRkaWZmKGRmMSxkZjIpDQpzZXRkaWZmKGRmMixkZjEpDQoNCmBgYA0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQo=