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==