Basic Mapping

Preliminaries: load in libraries

library(rgdal) #manipulating shape files (.shp)
library(ggplot2) #very advanced plotting/graphics library
library(sp) #spatial data utility
library(maptools) #mapping utility
library(rgeos) #additional geographic utility
library(raster) #raster data
library(spatstat) #spatial statistics
#library(ggmap) #interfacing with Google Maps (VPN required)
library(OpenStreetMap)

Reading in Map Data

#chinaMap<-getData('GADM',country="CHN",level=1) #download data from GADM; getData is part of package raster
ChinaRD0<-readRDS("data/CHN_adm0.rds") #Country outline; data folder is local
ChinaRD1<-readRDS("data/CHN_adm1.rds") #provinces
ChinaRD2<-readRDS("data/CHN_adm2.rds") #prefectures
ChinaRD3<-readRDS("data/CHN_adm3.rds") #counties
plot(ChinaRD0,main="Mainland China country outline") #Plot Mainland China 

Look at properties of data frame

ChinaRD1@data[1:5,1:7] #shows first 5 rows 7 cols of ChinaRD1; could also use: slot(ChinaRD1,"data")[1:10,]
names(ChinaRD3) #names of columns in data
 [1] "OBJECTID"  "ID_0"      "ISO"       "NAME_0"    "ID_1"      "NAME_1"    "ID_2"     
 [8] "NAME_2"    "ID_3"      "NAME_3"    "CCN_3"     "CCA_3"     "TYPE_3"    "ENGTYPE_3"
[15] "NL_NAME_3" "VARNAME_3"
shanghaiCities<-ChinaRD3[ChinaRD3$NAME_2=="Shanghai",] #Selects only cities in Shanghai municipality

Plot geographic subset of data with names

plot(shanghaiCities)
plot(shanghaiCities[shanghaiCities$NAME_3=="Shanghai",],border="blue",add=TRUE) #add=T draws on current plot
text(coordinates(shanghaiCities),
     labels=shanghaiCities$NAME_3,col="red",cex=0.7) #Adds names

Merge population data onto map

popData<-read.table("data/china_pop_9293.csv",header=T,sep=",",stringsAsFactors=FALSE) #examine: str(popData)
ChinaData2 <- slot(ChinaRD2, "data")
names(ChinaData2)[c(6,8)]<-c("province_name","city_name")
table(ChinaData2$province_name) #Show frequency table of prefectures by province
prefectureData<-merge(ChinaData2, popData, by=c("province_name", "city_name"),all.x=TRUE) #merging by two columns
prefectureData$city_name[is.na(prefectureData$pop92)] #not a great way to match
names(ChinaRD2)[c(6,8)]<-c("province_name","city_name") #SP package allows merging onto SpatialPolygonsDataFrame
popDataSP<-merge(ChinaRD2, popData, by=c("province_name", "city_name"),all.x=TRUE)
#rm(ChinaRD2) #Removes old object--not really necessary
summary(popDataSP) #shows summary statistics on new object

Plot Population Data with ggplot2 (chloropleth plot)

gg_map_obj<-fortify(ChinaRD2, region= "OBJECTID")
china_map<-ggplot() + geom_map(data = slot(popDataSP, "data"),
    aes(map_id = OBJECTID, fill = pop92), map = gg_map_obj) + 
  expand_limits(x = gg_map_obj$long, y = gg_map_obj$lat) + ggtitle("Population in 1992, Selected Prefectures")
china_map

#ggsave("china_pop92.pdf", china_map, width = 10, height = 6)

Points Data: which prefecture contains province’s centroid?

provinceCentroids<-coordinates(ChinaRD1) #gets coordinates
plot(ChinaRD1)
points(provinceCentroids,col="red") #adds points to current plot

#plot(ChinaRD3,border="blue",add=T) #draws borders of prefectures

Geographic Projections, Spatial Overlays, Write to CSV

spdf_pts <- SpatialPointsDataFrame(coords=provinceCentroids, data=data.frame(ChinaRD1$NAME_1))
proj4string(spdf_pts) <-proj4string(popDataSP) #Make sure projection is the same (should be since comes from same data source)
#proj4string(spdf_pts)<-CRS(" +proj=longlat +datum=WGS84 +ellps=WGS84 +towgs84=0,0,0") #could use this code to adjust
pref_pts<-over(spdf_pts,popDataSP)
pref_pts$x<-slot(spdf_pts,"coords")[,1]
pref_pts$y<-slot(spdf_pts,"coords")[,2]
#write.table(pref_pts, file = "centroids_in_cities.CSV", sep = ",", col.names=names(pref_pts),row.names=FALSE,na="") #write CSV

Plot Province Centroids with Prefecture Name

plot(ChinaRD1)
points(provinceCentroids,col="red") #adds points to current plot
text(pref_pts$x,pref_pts$y, labels=pref_pts$city_name,col="blue",cex=0.7) #Add names

Using Open Street Map Tiles

sufe_names="SUFE"
sufe_pts<-SpatialPointsDataFrame(coords=cbind(121.5153883,31.2948375), data=data.frame(sufe_names))
sufe_pts$lon<-coordinates(sufe_pts)[1,1]
sufe_pts$lat<-coordinates(sufe_pts)[1,2]
sufe_map <- invisible(openmap(c(sufe_pts$lat+0.03,sufe_pts$lon-0.03), c(sufe_pts$lat-0.03,sufe_pts$lon+0.03),
               minNumTiles=10,type="osm")) #invisible suppresses warning messages

SUFE Plot from Open Street Map

plot(sufe_map)

Geocoding

  • Geocoding is the process of converting street addresses to latitude and longitude

  • This can be done with a geodatabase or by calling a service (ex: Google, Baidu)

  • In R, there are multiple packages to do this, including geoChina and ggmap

  • You will need an API and the output will often come back as a JSON; Google gives 2500 free requests per day, Baidu seems to allow even more

  • Google will also allow network analysis (distance between two points by travel mode)

  • Note that Chinese maps use a shifted coordinate system (GCJ02) that may require additional work to use

Working with Point Pattern Data

Bring in restaurants point data and plot

We use a projection (NAD1983 Long Island, feet) to do simple distance calcuations

rest_data<-read.table("data/menupages_Wb126.csv", header=T, sep=",",stringsAsFactors =FALSE)
nyc_tracts<-readOGR("data","manhattan_tracts") #Read shapefiles with readOGR  
OGR data source with driver: ESRI Shapefile 
Source: "C:\Users\nschiff\Dropbox\notShared\teaching\graduate_urban\SUFE_2018\lectures\11_spatial_methods\data", layer: "manhattan_tracts"
with 221 features
It has 46 fields
ggplot() + geom_polygon(data = nyc_tracts, aes(x=long, y = lat, group = group), fill = NA, color = "black") + 
   geom_point(data=rest_data,aes(x=x_feet, y=y_feet), size=1, color = "blue") + ggtitle("Manhattan Restaurants")
Regions defined for each Polygons

Subset Plot: Chinese Restaurants

ggplot() + geom_polygon(data = nyc_tracts, aes(x=long, y = lat, group = group), fill = NA, color = "black") + 
   geom_point(data=rest_data[rest_data$cuisName1=="Chinese",],aes(x=x_feet, y=y_feet), size=1, color = "red") + ggtitle("Chinese Restaurants")
Regions defined for each Polygons

Convert to Point Pattern Object for Analysis

min_x<-min(rest_data$x_feet)
max_x<-max(rest_data$x_feet)
min_y<-min(rest_data$y_feet)
max_y<-max(rest_data$y_feet)
W <- owin(xrange=c(min_x,max_x),yrange=c(min_y,max_y)) #a window defined by limits of data
allrests.ppp<-ppp(rest_data$x_feet,rest_data$y_feet,window=W)
italian.ppp<-allrests.ppp[rest_data$cuisName1=="Italian",]
chinese.ppp<-allrests.ppp[rest_data$cuisName1=="Chinese",]
pizza.ppp<-allrests.ppp[rest_data$cuisName1=="Pizza",]

Look at count of Chinese restaurants within given radii

neighDist<-pairdist(chinese.ppp)
radii_set<-seq(200,3600,200)
chinese_mat<-array(,c(length(radii_set),2))
for (i in 1:length(radii_set)) {
  chinese_mat[i,1]<-radii_set[i]
  chinese_mat[i,2]<-mean(rowSums((neighDist<radii_set[i]), na.rm=TRUE))-1 #remove own distance
}
plot(chinese_mat,xlab="radius",ylab="Count",main="Count Chinese Restaurants within Radius")

Compare to pizza restaurants

Now compare Chinese to simulated measure

numSims<-1000
sim_mat<-array(,c(length(chinese_mat[,1]),numSims))
for (i in 1:numSims) {
  sim.ppp<-allrests.ppp[sample(1:length(allrests.ppp$x),length(chinese.ppp$x),replace=F)]
  neighDist_sim<-pairdist(sim.ppp)
  for (j in 1:length(radii_set)) {
    sim_mat[j,i]<-mean(rowSums(neighDist_sim<radii_set[j], na.rm=TRUE))-1
  }
}
conf_mat<-array(,c(length(chinese_mat[,1]),2))
for (j in 1:length(radii_set)) {
  conf_mat[j,1]<-quantile(sim_mat[j,],probs=.025,na.rm=TRUE)
  conf_mat[j,2]<-quantile(sim_mat[j,],probs=.975,na.rm=TRUE)
}
chinese_mat<-cbind(chinese_mat,conf_mat)

Plot with Confidence Bands

Compare to pizza

LS0tDQp0aXRsZTogIjIwMTggU3BhdGlhbCBNZXRob2RzIExlY3R1cmUiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KI0Jhc2ljIE1hcHBpbmcNCg0KIyMgUHJlbGltaW5hcmllczogbG9hZCBpbiBsaWJyYXJpZXMNCmBgYHtyIG1lc3NhZ2U9RkFMU0V9DQpsaWJyYXJ5KHJnZGFsKSAjbWFuaXB1bGF0aW5nIHNoYXBlIGZpbGVzICguc2hwKQ0KbGlicmFyeShnZ3Bsb3QyKSAjdmVyeSBhZHZhbmNlZCBwbG90dGluZy9ncmFwaGljcyBsaWJyYXJ5DQpsaWJyYXJ5KHNwKSAjc3BhdGlhbCBkYXRhIHV0aWxpdHkNCmxpYnJhcnkobWFwdG9vbHMpICNtYXBwaW5nIHV0aWxpdHkNCmxpYnJhcnkocmdlb3MpICNhZGRpdGlvbmFsIGdlb2dyYXBoaWMgdXRpbGl0eQ0KbGlicmFyeShyYXN0ZXIpICNyYXN0ZXIgZGF0YQ0KbGlicmFyeShzcGF0c3RhdCkgI3NwYXRpYWwgc3RhdGlzdGljcw0KI2xpYnJhcnkoZ2dtYXApICNpbnRlcmZhY2luZyB3aXRoIEdvb2dsZSBNYXBzIChWUE4gcmVxdWlyZWQpDQpsaWJyYXJ5KE9wZW5TdHJlZXRNYXApDQpgYGANCg0KIyMgUmVhZGluZyBpbiBNYXAgRGF0YQ0KYGBge3J9DQojY2hpbmFNYXA8LWdldERhdGEoJ0dBRE0nLGNvdW50cnk9IkNITiIsbGV2ZWw9MSkgI2Rvd25sb2FkIGRhdGEgZnJvbSBHQURNOyBnZXREYXRhIGlzIHBhcnQgb2YgcGFja2FnZSByYXN0ZXINCkNoaW5hUkQwPC1yZWFkUkRTKCJkYXRhL0NITl9hZG0wLnJkcyIpICNDb3VudHJ5IG91dGxpbmU7IGRhdGEgZm9sZGVyIGlzIGxvY2FsDQpDaGluYVJEMTwtcmVhZFJEUygiZGF0YS9DSE5fYWRtMS5yZHMiKSAjcHJvdmluY2VzDQpDaGluYVJEMjwtcmVhZFJEUygiZGF0YS9DSE5fYWRtMi5yZHMiKSAjcHJlZmVjdHVyZXMNCkNoaW5hUkQzPC1yZWFkUkRTKCJkYXRhL0NITl9hZG0zLnJkcyIpICNjb3VudGllcw0KcGxvdChDaGluYVJEMCxtYWluPSJNYWlubGFuZCBDaGluYSBjb3VudHJ5IG91dGxpbmUiKSAjUGxvdCBNYWlubGFuZCBDaGluYSANCmBgYA0KICANCiMjIExvb2sgYXQgcHJvcGVydGllcyBvZiBkYXRhIGZyYW1lDQoNCmBgYHtyIGVjaG89VFJVRX0NCkNoaW5hUkQxQGRhdGFbMTo1LDE6N10gI3Nob3dzIGZpcnN0IDUgcm93cyA3IGNvbHMgb2YgQ2hpbmFSRDE7IGNvdWxkIGFsc28gdXNlOiBzbG90KENoaW5hUkQxLCJkYXRhIilbMToxMCxdDQpuYW1lcyhDaGluYVJEMykgI25hbWVzIG9mIGNvbHVtbnMgaW4gZGF0YQ0Kc2hhbmdoYWlDaXRpZXM8LUNoaW5hUkQzW0NoaW5hUkQzJE5BTUVfMj09IlNoYW5naGFpIixdICNTZWxlY3RzIG9ubHkgY2l0aWVzIGluIFNoYW5naGFpIG11bmljaXBhbGl0eQ0KYGBgDQoNCiMjIFBsb3QgZ2VvZ3JhcGhpYyBzdWJzZXQgb2YgZGF0YSB3aXRoIG5hbWVzDQoNCmBgYHtyfQ0KcGxvdChzaGFuZ2hhaUNpdGllcykNCnBsb3Qoc2hhbmdoYWlDaXRpZXNbc2hhbmdoYWlDaXRpZXMkTkFNRV8zPT0iU2hhbmdoYWkiLF0sYm9yZGVyPSJibHVlIixhZGQ9VFJVRSkgI2FkZD1UIGRyYXdzIG9uIGN1cnJlbnQgcGxvdA0KdGV4dChjb29yZGluYXRlcyhzaGFuZ2hhaUNpdGllcyksDQogICAgIGxhYmVscz1zaGFuZ2hhaUNpdGllcyROQU1FXzMsY29sPSJyZWQiLGNleD0wLjcpICNBZGRzIG5hbWVzDQpgYGANCg0KIyMgTWVyZ2UgcG9wdWxhdGlvbiBkYXRhIG9udG8gbWFwDQpgYGB7ciByZXN1bHRzPSdoaWRlJ30NCnBvcERhdGE8LXJlYWQudGFibGUoImRhdGEvY2hpbmFfcG9wXzkyOTMuY3N2IixoZWFkZXI9VCxzZXA9IiwiLHN0cmluZ3NBc0ZhY3RvcnM9RkFMU0UpICNleGFtaW5lOiBzdHIocG9wRGF0YSkNCkNoaW5hRGF0YTIgPC0gc2xvdChDaGluYVJEMiwgImRhdGEiKQ0KbmFtZXMoQ2hpbmFEYXRhMilbYyg2LDgpXTwtYygicHJvdmluY2VfbmFtZSIsImNpdHlfbmFtZSIpDQp0YWJsZShDaGluYURhdGEyJHByb3ZpbmNlX25hbWUpICNTaG93IGZyZXF1ZW5jeSB0YWJsZSBvZiBwcmVmZWN0dXJlcyBieSBwcm92aW5jZQ0KcHJlZmVjdHVyZURhdGE8LW1lcmdlKENoaW5hRGF0YTIsIHBvcERhdGEsIGJ5PWMoInByb3ZpbmNlX25hbWUiLCAiY2l0eV9uYW1lIiksYWxsLng9VFJVRSkgI21lcmdpbmcgYnkgdHdvIGNvbHVtbnMNCnByZWZlY3R1cmVEYXRhJGNpdHlfbmFtZVtpcy5uYShwcmVmZWN0dXJlRGF0YSRwb3A5MildICNub3QgYSBncmVhdCB3YXkgdG8gbWF0Y2gNCm5hbWVzKENoaW5hUkQyKVtjKDYsOCldPC1jKCJwcm92aW5jZV9uYW1lIiwiY2l0eV9uYW1lIikgI1NQIHBhY2thZ2UgYWxsb3dzIG1lcmdpbmcgb250byBTcGF0aWFsUG9seWdvbnNEYXRhRnJhbWUNCnBvcERhdGFTUDwtbWVyZ2UoQ2hpbmFSRDIsIHBvcERhdGEsIGJ5PWMoInByb3ZpbmNlX25hbWUiLCAiY2l0eV9uYW1lIiksYWxsLng9VFJVRSkNCiNybShDaGluYVJEMikgI1JlbW92ZXMgb2xkIG9iamVjdC0tbm90IHJlYWxseSBuZWNlc3NhcnkNCnN1bW1hcnkocG9wRGF0YVNQKSAjc2hvd3Mgc3VtbWFyeSBzdGF0aXN0aWNzIG9uIG5ldyBvYmplY3QNCmBgYA0KDQojIyBQbG90IFBvcHVsYXRpb24gRGF0YSB3aXRoIGdncGxvdDIgKGNobG9yb3BsZXRoIHBsb3QpDQpgYGB7cn0NCmdnX21hcF9vYmo8LWZvcnRpZnkoQ2hpbmFSRDIsIHJlZ2lvbj0gIk9CSkVDVElEIikNCmNoaW5hX21hcDwtZ2dwbG90KCkgKyBnZW9tX21hcChkYXRhID0gc2xvdChwb3BEYXRhU1AsICJkYXRhIiksDQogICAgYWVzKG1hcF9pZCA9IE9CSkVDVElELCBmaWxsID0gcG9wOTIpLCBtYXAgPSBnZ19tYXBfb2JqKSArIA0KICBleHBhbmRfbGltaXRzKHggPSBnZ19tYXBfb2JqJGxvbmcsIHkgPSBnZ19tYXBfb2JqJGxhdCkgKyBnZ3RpdGxlKCJQb3B1bGF0aW9uIGluIDE5OTIsIFNlbGVjdGVkIFByZWZlY3R1cmVzIikNCmNoaW5hX21hcA0KI2dnc2F2ZSgiY2hpbmFfcG9wOTIucGRmIiwgY2hpbmFfbWFwLCB3aWR0aCA9IDEwLCBoZWlnaHQgPSA2KQ0KDQpgYGANCg0KIyMgUG9pbnRzIERhdGE6IHdoaWNoIHByZWZlY3R1cmUgY29udGFpbnMgcHJvdmluY2UncyBjZW50cm9pZD8NCmBgYHtyfQ0KcHJvdmluY2VDZW50cm9pZHM8LWNvb3JkaW5hdGVzKENoaW5hUkQxKSAjZ2V0cyBjb29yZGluYXRlcw0KcGxvdChDaGluYVJEMSkNCnBvaW50cyhwcm92aW5jZUNlbnRyb2lkcyxjb2w9InJlZCIpICNhZGRzIHBvaW50cyB0byBjdXJyZW50IHBsb3QNCiNwbG90KENoaW5hUkQzLGJvcmRlcj0iYmx1ZSIsYWRkPVQpICNkcmF3cyBib3JkZXJzIG9mIHByZWZlY3R1cmVzDQpgYGANCg0KIyMgR2VvZ3JhcGhpYyBQcm9qZWN0aW9ucywgU3BhdGlhbCBPdmVybGF5cywgV3JpdGUgdG8gQ1NWDQpgYGB7cn0NCnNwZGZfcHRzIDwtIFNwYXRpYWxQb2ludHNEYXRhRnJhbWUoY29vcmRzPXByb3ZpbmNlQ2VudHJvaWRzLCBkYXRhPWRhdGEuZnJhbWUoQ2hpbmFSRDEkTkFNRV8xKSkNCnByb2o0c3RyaW5nKHNwZGZfcHRzKSA8LXByb2o0c3RyaW5nKHBvcERhdGFTUCkgI01ha2Ugc3VyZSBwcm9qZWN0aW9uIGlzIHRoZSBzYW1lIChzaG91bGQgYmUgc2luY2UgY29tZXMgZnJvbSBzYW1lIGRhdGEgc291cmNlKQ0KI3Byb2o0c3RyaW5nKHNwZGZfcHRzKTwtQ1JTKCIgK3Byb2o9bG9uZ2xhdCArZGF0dW09V0dTODQgK2VsbHBzPVdHUzg0ICt0b3dnczg0PTAsMCwwIikgI2NvdWxkIHVzZSB0aGlzIGNvZGUgdG8gYWRqdXN0DQpwcmVmX3B0czwtb3ZlcihzcGRmX3B0cyxwb3BEYXRhU1ApDQpwcmVmX3B0cyR4PC1zbG90KHNwZGZfcHRzLCJjb29yZHMiKVssMV0NCnByZWZfcHRzJHk8LXNsb3Qoc3BkZl9wdHMsImNvb3JkcyIpWywyXQ0KI3dyaXRlLnRhYmxlKHByZWZfcHRzLCBmaWxlID0gImNlbnRyb2lkc19pbl9jaXRpZXMuQ1NWIiwgc2VwID0gIiwiLCBjb2wubmFtZXM9bmFtZXMocHJlZl9wdHMpLHJvdy5uYW1lcz1GQUxTRSxuYT0iIikgI3dyaXRlIENTVg0KYGBgDQoNCiMjIFBsb3QgUHJvdmluY2UgQ2VudHJvaWRzIHdpdGggUHJlZmVjdHVyZSBOYW1lDQpgYGB7cn0NCnBsb3QoQ2hpbmFSRDEpDQpwb2ludHMocHJvdmluY2VDZW50cm9pZHMsY29sPSJyZWQiKSAjYWRkcyBwb2ludHMgdG8gY3VycmVudCBwbG90DQp0ZXh0KHByZWZfcHRzJHgscHJlZl9wdHMkeSwgbGFiZWxzPXByZWZfcHRzJGNpdHlfbmFtZSxjb2w9ImJsdWUiLGNleD0wLjcpICNBZGQgbmFtZXMNCmBgYA0KDQojIyBVc2luZyBPcGVuIFN0cmVldCBNYXAgVGlsZXMNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHJlc3VsdHM9J2hpZGUnfQ0Kc3VmZV9uYW1lcz0iU1VGRSINCnN1ZmVfcHRzPC1TcGF0aWFsUG9pbnRzRGF0YUZyYW1lKGNvb3Jkcz1jYmluZCgxMjEuNTE1Mzg4MywzMS4yOTQ4Mzc1KSwgZGF0YT1kYXRhLmZyYW1lKHN1ZmVfbmFtZXMpKQ0Kc3VmZV9wdHMkbG9uPC1jb29yZGluYXRlcyhzdWZlX3B0cylbMSwxXQ0Kc3VmZV9wdHMkbGF0PC1jb29yZGluYXRlcyhzdWZlX3B0cylbMSwyXQ0Kc3VmZV9tYXAgPC0gaW52aXNpYmxlKG9wZW5tYXAoYyhzdWZlX3B0cyRsYXQrMC4wMyxzdWZlX3B0cyRsb24tMC4wMyksIGMoc3VmZV9wdHMkbGF0LTAuMDMsc3VmZV9wdHMkbG9uKzAuMDMpLA0KICAgICAgICAgICAgICAgbWluTnVtVGlsZXM9MTAsdHlwZT0ib3NtIikpICNpbnZpc2libGUgc3VwcHJlc3NlcyB3YXJuaW5nIG1lc3NhZ2VzDQpgYGANCg0KIyMgU1VGRSBQbG90IGZyb20gT3BlbiBTdHJlZXQgTWFwDQpgYGB7cn0NCnBsb3Qoc3VmZV9tYXApDQpgYGANCg0KIyMgR2VvY29kaW5nDQotIEdlb2NvZGluZyBpcyB0aGUgcHJvY2VzcyBvZiBjb252ZXJ0aW5nIHN0cmVldCBhZGRyZXNzZXMgdG8gbGF0aXR1ZGUgYW5kIGxvbmdpdHVkZQ0KDQotIFRoaXMgY2FuIGJlIGRvbmUgd2l0aCBhIGdlb2RhdGFiYXNlIG9yIGJ5IGNhbGxpbmcgYSBzZXJ2aWNlIChleDogR29vZ2xlLCBCYWlkdSkNCg0KLSBJbiBSLCB0aGVyZSBhcmUgbXVsdGlwbGUgcGFja2FnZXMgdG8gZG8gdGhpcywgaW5jbHVkaW5nIGdlb0NoaW5hIGFuZCBnZ21hcA0KDQotIFlvdSB3aWxsIG5lZWQgYW4gQVBJIGFuZCB0aGUgb3V0cHV0IHdpbGwgb2Z0ZW4gY29tZSBiYWNrIGFzIGEgSlNPTjsgR29vZ2xlIGdpdmVzIDI1MDAgZnJlZSByZXF1ZXN0cyBwZXIgZGF5LCBCYWlkdSBzZWVtcyB0byBhbGxvdyBldmVuIG1vcmUNCg0KLSBHb29nbGUgd2lsbCBhbHNvIGFsbG93IG5ldHdvcmsgYW5hbHlzaXMgKGRpc3RhbmNlIGJldHdlZW4gdHdvIHBvaW50cyBieSB0cmF2ZWwgbW9kZSkNCg0KLSBOb3RlIHRoYXQgQ2hpbmVzZSBtYXBzIHVzZSBhIHNoaWZ0ZWQgY29vcmRpbmF0ZSBzeXN0ZW0gKEdDSjAyKSB0aGF0IG1heSByZXF1aXJlIGFkZGl0aW9uYWwgd29yayB0byB1c2UNCg0KI1dvcmtpbmcgd2l0aCBQb2ludCBQYXR0ZXJuIERhdGENCg0KIyMgQnJpbmcgaW4gcmVzdGF1cmFudHMgcG9pbnQgZGF0YSBhbmQgcGxvdA0KV2UgdXNlIGEgcHJvamVjdGlvbiAoTkFEMTk4MyBMb25nIElzbGFuZCwgZmVldCkgdG8gZG8gc2ltcGxlIGRpc3RhbmNlIGNhbGN1YXRpb25zDQpgYGB7cn0NCnJlc3RfZGF0YTwtcmVhZC50YWJsZSgiZGF0YS9tZW51cGFnZXNfV2IxMjYuY3N2IiwgaGVhZGVyPVQsIHNlcD0iLCIsc3RyaW5nc0FzRmFjdG9ycyA9RkFMU0UpDQpueWNfdHJhY3RzPC1yZWFkT0dSKCJkYXRhIiwibWFuaGF0dGFuX3RyYWN0cyIpICNSZWFkIHNoYXBlZmlsZXMgd2l0aCByZWFkT0dSICANCmdncGxvdCgpICsgZ2VvbV9wb2x5Z29uKGRhdGEgPSBueWNfdHJhY3RzLCBhZXMoeD1sb25nLCB5ID0gbGF0LCBncm91cCA9IGdyb3VwKSwgZmlsbCA9IE5BLCBjb2xvciA9ICJibGFjayIpICsgDQogICBnZW9tX3BvaW50KGRhdGE9cmVzdF9kYXRhLGFlcyh4PXhfZmVldCwgeT15X2ZlZXQpLCBzaXplPTEsIGNvbG9yID0gImJsdWUiKSArIGdndGl0bGUoIk1hbmhhdHRhbiBSZXN0YXVyYW50cyIpDQpgYGANCg0KIyMgU3Vic2V0IFBsb3Q6IENoaW5lc2UgUmVzdGF1cmFudHMNCmBgYHtyfQ0KZ2dwbG90KCkgKyBnZW9tX3BvbHlnb24oZGF0YSA9IG55Y190cmFjdHMsIGFlcyh4PWxvbmcsIHkgPSBsYXQsIGdyb3VwID0gZ3JvdXApLCBmaWxsID0gTkEsIGNvbG9yID0gImJsYWNrIikgKyANCiAgIGdlb21fcG9pbnQoZGF0YT1yZXN0X2RhdGFbcmVzdF9kYXRhJGN1aXNOYW1lMT09IkNoaW5lc2UiLF0sYWVzKHg9eF9mZWV0LCB5PXlfZmVldCksIHNpemU9MSwgY29sb3IgPSAicmVkIikgKyBnZ3RpdGxlKCJDaGluZXNlIFJlc3RhdXJhbnRzIikNCmBgYA0KDQojIyBDb252ZXJ0IHRvIFBvaW50IFBhdHRlcm4gT2JqZWN0IGZvciBBbmFseXNpcw0KYGBge3IgcmVzdWx0cz0naGlkZSd9DQptaW5feDwtbWluKHJlc3RfZGF0YSR4X2ZlZXQpDQptYXhfeDwtbWF4KHJlc3RfZGF0YSR4X2ZlZXQpDQptaW5feTwtbWluKHJlc3RfZGF0YSR5X2ZlZXQpDQptYXhfeTwtbWF4KHJlc3RfZGF0YSR5X2ZlZXQpDQpXIDwtIG93aW4oeHJhbmdlPWMobWluX3gsbWF4X3gpLHlyYW5nZT1jKG1pbl95LG1heF95KSkgI2Egd2luZG93IGRlZmluZWQgYnkgbGltaXRzIG9mIGRhdGENCmFsbHJlc3RzLnBwcDwtcHBwKHJlc3RfZGF0YSR4X2ZlZXQscmVzdF9kYXRhJHlfZmVldCx3aW5kb3c9VykNCml0YWxpYW4ucHBwPC1hbGxyZXN0cy5wcHBbcmVzdF9kYXRhJGN1aXNOYW1lMT09Ikl0YWxpYW4iLF0NCmNoaW5lc2UucHBwPC1hbGxyZXN0cy5wcHBbcmVzdF9kYXRhJGN1aXNOYW1lMT09IkNoaW5lc2UiLF0NCnBpenphLnBwcDwtYWxscmVzdHMucHBwW3Jlc3RfZGF0YSRjdWlzTmFtZTE9PSJQaXp6YSIsXQ0KYGBgDQoNCiMjIExvb2sgYXQgY291bnQgb2YgQ2hpbmVzZSByZXN0YXVyYW50cyB3aXRoaW4gZ2l2ZW4gcmFkaWkNCmBgYHtyfQ0KbmVpZ2hEaXN0PC1wYWlyZGlzdChjaGluZXNlLnBwcCkNCnJhZGlpX3NldDwtc2VxKDIwMCwzNjAwLDIwMCkNCmNoaW5lc2VfbWF0PC1hcnJheSgsYyhsZW5ndGgocmFkaWlfc2V0KSwyKSkNCmZvciAoaSBpbiAxOmxlbmd0aChyYWRpaV9zZXQpKSB7DQogIGNoaW5lc2VfbWF0W2ksMV08LXJhZGlpX3NldFtpXQ0KICBjaGluZXNlX21hdFtpLDJdPC1tZWFuKHJvd1N1bXMoKG5laWdoRGlzdDxyYWRpaV9zZXRbaV0pLCBuYS5ybT1UUlVFKSktMSAjcmVtb3ZlIG93biBkaXN0YW5jZQ0KfQ0KcGxvdChjaGluZXNlX21hdCx4bGFiPSJyYWRpdXMiLHlsYWI9IkNvdW50IixtYWluPSJDb3VudCBDaGluZXNlIFJlc3RhdXJhbnRzIHdpdGhpbiBSYWRpdXMiKQ0KYGBgDQoNCiMjIENvbXBhcmUgdG8gcGl6emEgcmVzdGF1cmFudHMNCmBgYHtyIGVjaG89RkFMU0V9DQpuZWlnaERpc3Q8LXBhaXJkaXN0KHBpenphLnBwcCkNCnBpenphX21hdDwtYXJyYXkoLGMobGVuZ3RoKHJhZGlpX3NldCksMSkpDQpwaXp6YV9tYXQ8LWNiaW5kKGNoaW5lc2VfbWF0WywxXSxwaXp6YV9tYXQpDQpmb3IgKGkgaW4gMTpsZW5ndGgocmFkaWlfc2V0KSkgew0KICBwaXp6YV9tYXRbaSwyXTwtbWVhbihyb3dTdW1zKChuZWlnaERpc3Q8cmFkaWlfc2V0W2ldKSwgbmEucm09VFJVRSkpLTEgI3JlbW92ZSBvd24gZGlzdGFuY2UNCn0NCnBsb3QoY2hpbmVzZV9tYXQseGxhYj0icmFkaXVzIix5bGFiPSJDb3VudCIsbWFpbj0iQ2hpbmVzZSAocmVkKSBhbmQgUGl6emEgKGdyZWVuKSIsDQogICAgIHlsaW09cmFuZ2UoYyhjaGluZXNlX21hdFssMl0scGl6emFfbWF0WywyXSkpLGNvbD0icmVkIikNCnBhcihuZXc9VCkNCnBsb3QocGl6emFfbWF0LHhsYWI9IiIseWxhYj0iIixheGVzPUZBTFNFLGNvbD0iZ3JlZW4iKQ0KYGBgDQoNCiMjIE5vdyBjb21wYXJlIENoaW5lc2UgdG8gc2ltdWxhdGVkIG1lYXN1cmUNCmBgYHtyIHJlc3VsdHM9J2hpZGUnfQ0KbnVtU2ltczwtMTAwMA0Kc2ltX21hdDwtYXJyYXkoLGMobGVuZ3RoKGNoaW5lc2VfbWF0WywxXSksbnVtU2ltcykpDQpmb3IgKGkgaW4gMTpudW1TaW1zKSB7DQogIHNpbS5wcHA8LWFsbHJlc3RzLnBwcFtzYW1wbGUoMTpsZW5ndGgoYWxscmVzdHMucHBwJHgpLGxlbmd0aChjaGluZXNlLnBwcCR4KSxyZXBsYWNlPUYpXQ0KICBuZWlnaERpc3Rfc2ltPC1wYWlyZGlzdChzaW0ucHBwKQ0KICBmb3IgKGogaW4gMTpsZW5ndGgocmFkaWlfc2V0KSkgew0KICAgIHNpbV9tYXRbaixpXTwtbWVhbihyb3dTdW1zKG5laWdoRGlzdF9zaW08cmFkaWlfc2V0W2pdLCBuYS5ybT1UUlVFKSktMQ0KICB9DQp9DQpjb25mX21hdDwtYXJyYXkoLGMobGVuZ3RoKGNoaW5lc2VfbWF0WywxXSksMikpDQpmb3IgKGogaW4gMTpsZW5ndGgocmFkaWlfc2V0KSkgew0KICBjb25mX21hdFtqLDFdPC1xdWFudGlsZShzaW1fbWF0W2osXSxwcm9icz0uMDI1LG5hLnJtPVRSVUUpDQogIGNvbmZfbWF0W2osMl08LXF1YW50aWxlKHNpbV9tYXRbaixdLHByb2JzPS45NzUsbmEucm09VFJVRSkNCn0NCmNoaW5lc2VfbWF0PC1jYmluZChjaGluZXNlX21hdCxjb25mX21hdCkNCmBgYA0KDQojIyBQbG90IHdpdGggQ29uZmlkZW5jZSBCYW5kcw0KYGBge3IgZWNobz1GQUxTRX0NCnBsb3QoY2hpbmVzZV9tYXRbLDFdLGNoaW5lc2VfbWF0WywyXSx5bGltPXJhbmdlKGMoY2hpbmVzZV9tYXRbLDJdLGNoaW5lc2VfbWF0WywzXSxjaGluZXNlX21hdFssNF0pKSwNCiAgICAgeGxhYj0iUmFkaXVzIix5bGFiPSJDb3VudCIscGNoPTIwLGNvbD0icmVkIikNCnBhcihuZXc9VCkNCnBsb3QoY2hpbmVzZV9tYXRbLDFdLGNoaW5lc2VfbWF0WywzXSx5bGltPXJhbmdlKGMoY2hpbmVzZV9tYXRbLDJdLGNoaW5lc2VfbWF0WywzXSxjaGluZXNlX21hdFssNF0pKSwNCiAgICAgYXhlcz1GQUxTRSx4bGFiPSIiLHlsYWI9IiIsbWFpbj0iQ291bnQgQ2hpbmVzZSBSZXN0YXVyYW50cyB3aXRoaW4gUmFkaXVzIixwY2g9MjUsY2V4PTAuNSkNCnBhcihuZXc9VCkNCnBsb3QoY2hpbmVzZV9tYXRbLDFdLGNoaW5lc2VfbWF0Wyw0XSx5bGltPXJhbmdlKGMoY2hpbmVzZV9tYXRbLDJdLGNoaW5lc2VfbWF0WywzXSxjaGluZXNlX21hdFssNF0pKSwNCiAgICAgYXhlcz1GQUxTRSx4bGFiPSIiLHlsYWI9IiIscGNoPTI0LGNleD0wLjUpDQpgYGANCg0KIyMgQ29tcGFyZSB0byBwaXp6YQ0KYGBge3IgZWNobz1GQUxTRX0NCnNpbV9tYXQ8LWFycmF5KCxjKGxlbmd0aChwaXp6YV9tYXRbLDFdKSxudW1TaW1zKSkNCmZvciAoaSBpbiAxOm51bVNpbXMpIHsNCiAgc2ltLnBwcDwtYWxscmVzdHMucHBwW3NhbXBsZSgxOmxlbmd0aChhbGxyZXN0cy5wcHAkeCksbGVuZ3RoKHBpenphLnBwcCR4KSxyZXBsYWNlPUYpXQ0KICBuZWlnaERpc3Rfc2ltPC1wYWlyZGlzdChzaW0ucHBwKQ0KICBmb3IgKGogaW4gMTpsZW5ndGgocmFkaWlfc2V0KSkgew0KICAgIHNpbV9tYXRbaixpXTwtbWVhbihyb3dTdW1zKG5laWdoRGlzdF9zaW08cmFkaWlfc2V0W2pdLCBuYS5ybT1UUlVFKSktMQ0KICB9DQp9DQpjb25mX21hdDwtYXJyYXkoLGMobGVuZ3RoKHBpenphX21hdFssMV0pLDIpKQ0KZm9yIChqIGluIDE6bGVuZ3RoKHJhZGlpX3NldCkpIHsNCiAgY29uZl9tYXRbaiwxXTwtcXVhbnRpbGUoc2ltX21hdFtqLF0scHJvYnM9LjAyNSxuYS5ybT1UUlVFKQ0KICBjb25mX21hdFtqLDJdPC1xdWFudGlsZShzaW1fbWF0W2osXSxwcm9icz0uOTc1LG5hLnJtPVRSVUUpDQp9DQpwaXp6YV9tYXQ8LWNiaW5kKHBpenphX21hdCxjb25mX21hdCkNCnBsb3QocGl6emFfbWF0WywxXSxwaXp6YV9tYXRbLDJdLHlsaW09cmFuZ2UoYyhwaXp6YV9tYXRbLDJdLHBpenphX21hdFssM10scGl6emFfbWF0Wyw0XSkpLA0KICAgICB4bGFiPSJSYWRpdXMiLHlsYWI9IkNvdW50Iixjb2w9InJlZCIsY2V4PTEscGNoPTIwKQ0KcGFyKG5ldz1UKQ0KcGxvdChwaXp6YV9tYXRbLDFdLHBpenphX21hdFssM10seWxpbT1yYW5nZShjKHBpenphX21hdFssMl0scGl6emFfbWF0WywzXSxwaXp6YV9tYXRbLDRdKSksDQogICAgIGF4ZXM9RkFMU0UseGxhYj0iIix5bGFiPSIiLG1haW49IkNvdW50IFBpenphIFJlc3RhdXJhbnRzIHdpdGhpbiBSYWRpdXMiLHBjaD0yNSxjZXg9MC41KQ0KcGFyKG5ldz1UKQ0KcGxvdChwaXp6YV9tYXRbLDFdLHBpenphX21hdFssNF0seWxpbT1yYW5nZShjKHBpenphX21hdFssMl0scGl6emFfbWF0WywzXSxwaXp6YV9tYXRbLDRdKSksDQogICAgIGF4ZXM9RkFMU0UseGxhYj0iIix5bGFiPSIiLHBjaD0yNCxjZXg9MC41KQ0KYGBgDQoNCg==