Introduction

The aim of this analysis is to explore the feasibility of locating and monitoring a public transit system by aggregating the GPS data of everyday commuters. This would be in the context of a phone app which providers commuters with information about the public transport system while at the same time, recording the user’s route through the city.

Since the users will not provide any input aside from the location which is tracked automatically the system will need to differentiate when a commuter is driving their car, walking or riding on and bus and determining which one.

The implementation of the system won’t assume that information about the network such as bus locations and schedules will be provided from the onset, so the system would also need to map the network from scratch.

In this initial analysis, we will focus on a key element of the mapping process: finding bus stops.

Since the system hasn’t been implemented and it depends on a large number of users, we’ve generated a transit simulation using SUMO (sumo.dlr.de) which will simulate a large population of commuters that will walk, drive, and get on buses in a virtual city.

To achieve a high degree of accuracy, new commuter traces need to be compared with prior ones, which the system has labeled with a high degree of certainty. Since we don’t have a pre-existing data when searching for the stops, we are aiming ti narrow the possible options knowing that as more data is added, accuracy will improve until only true stops are mapped.

Data Generation

Although it’s possible to create a fictional city in SUMO, it’s much more convenient and useful to simualte traffic on an existing city by importing the data from Open Street Maps. For our study, we used Berlin since the public transit data is very complete for that area.

As we can see in the preview, we have vehice information included, which won’t use since the point of the study is to infer this strictly from the pedestrian data.

Parsed with column specification:
cols(
  timestep_time = col_double(),
  vehicle_angle = col_double(),
  vehicle_id = col_character(),
  vehicle_lane = col_character(),
  vehicle_pos = col_double(),
  vehicle_slope = col_double(),
  vehicle_speed = col_double(),
  vehicle_type = col_character(),
  vehicle_x = col_double(),
  vehicle_y = col_double(),
  person_angle = col_double(),
  person_edge = col_character(),
  person_id = col_character(),
  person_pos = col_double(),
  person_slope = col_double(),
  person_speed = col_double(),
  person_x = col_double(),
  person_y = col_double()
)

Data Cleaning & Transformation

We are only interested in the pedestrian activity so we will filter out any data that has a vehicle ID and we’ll remove columns that don’t have pedestrian data.

We still have several columns which we should remove, we’ll only focus on the time steps, location, speed and pedestrian ID.

When passengers are traveling together, the simulation places them in exactly that same position. Although this is unrealistic, it serves as appropriate simplification at this early stage of the project. So, one way we can narrow down the possible places where buses are located is to find groups of people who are very close together and moving at the same speed.

To reflect this in the data we will form clusters of pedestrians that share the same location and time and name this column cluster. We may also be interested in the size of the cluster since that may give us a hint of what type of transportation they are using and of any changes in the size of the clusters.

Now that we have the cluster count for each time step and location we can add an additional variable which tells us if, at a particular location and time, the cluster size changed. This will help us filter good candidates for possible bus stop locations.

Before we continue with our exploration and analysis, lets save our original and tranformed data.

Once the connections are established we can upload the data to the new database.

Exploration:

If we take a random snapshot of pedenstrian clusters ( which are already a small subset) we see that obtaining reliable data will be a challenge.

When comparing speeds between vehicles and pedesntrians we find a key differencitor. Besides total standstill, will do most of their waling at around 1m/s, a speed that rarely seen in vehicles.

Although not our main goal, we can use this information to find roads (and train tracks). BY filtering for groups moving at over 7m/s most become easy to see.

plot(dfc$person_x[dfc$person_speed >7],jitter(dfc$person_y[dfc$person_speed > 7]))

Let’s now graph cluster that aren’t moving and which are larger than 10.

smoothScatter(
  dfc$person_x[dfc$person_speed == 0 | dfc$ccount > 10],
  dfc$person_y[dfc$person_speed == 0 | dfc$ccount > 10],
  nbin = 1000,
  bandwidth = 5)

Many of the bus stops are visible under the dark blots but we have alot of noise. Let instead focus on cluster changes while at rest. The transformation below calculates the absolute change in cluster size for clusters that share the same location and time.

dfc2 <- dfc %>%  
  filter(person_speed == 0) %>% 
  mutate(abscc = abs(cchange)) %>% 
  filter(abscc > 0) %>% 
  dplyr::group_by(person_x, person_y) %>% 
  count(person_x, person_y)
  
smoothScatter(
  dfc2$person_x,
  dfc2$person_y,
  nbin = 1000,
  bandwidth = 5)

This is an improvement. We have more defined spots but we still many more spots than stops.

Analysis & Conclusion

As we’ve seen, analyzing the speed and collective behavior of pedestrians can give us many clues about the layout of the city, and their mode of transportation. Although the results are very promising they are clearly lacking as we are still getting many false positives. Most of these are likely train stops, pedestrian crossings and any other place where pedestrians may agglomerate in close groups.

An obvious extension of this model which should greatly enhance its capabilities is to extract “cluster chains” from the data. In our current analysis, we rely on instantaneous changes in group size which are both unrealistic and limiting. If we identify consecutive timesteps in which two or more pedestrians are present, complete routes could be linked which would also allow us to analyze the acceleration profile of each chain. All the public transport routes could be easily obtained by linking chains. The acceleration profile would not only enhance the location of stops, it would likely differentiate all modes of transport, from walking to taking riding on a ferry.

As mentioned above, the simulation introduces a major simplification by setting the location of bus passengers exactly the same. It will eventually be necessary to introduce a degree of randomness to account for different seat location and GPS inaccuracy. In this case, determining which pedestrian belong to a cluster will be more difficult but should be possible by constructing some kind of localized cointegration test on possible cluster chains.

It was my intention to incorporate cluster chains from the onset but the data manipulation was unfortunately beyond my capabilities at the time. I consulted with several researchers but they were also unable to help although the logic of the transformation is fairly straightforward. In spite of this, the results suggest that meaningful information can be extracted from random GPS traces, and thus additional work on this topic seems warranted.

References

Krajzewicz, D., Erdmann, J., Behrisch, M., & Bieker, L. (2012). Recent development and applications of SUMO-Simulation of Urban MObility. International Journal On Advances in Systems and Measurements, 5, 128–138. Retrieved from https://elib.dlr.de/80483/

LS0tDQp0aXRsZTogIkRBVEEgNjA3OiBGaW5hbCBQcm9qZWN0Ig0KYXV0aG9yOiAiRmVybmFuZG8gRmlndWVyZXMiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQoNCiMgSW50cm9kdWN0aW9uDQoNClRoZSBhaW0gb2YgdGhpcyBhbmFseXNpcyBpcyB0byBleHBsb3JlIHRoZSBmZWFzaWJpbGl0eSBvZiBsb2NhdGluZyBhbmQgbW9uaXRvcmluZyBhIHB1YmxpYyB0cmFuc2l0IHN5c3RlbSBieSBhZ2dyZWdhdGluZyB0aGUgR1BTIGRhdGEgb2YgZXZlcnlkYXkgY29tbXV0ZXJzLiBUaGlzIHdvdWxkIGJlIGluIHRoZSBjb250ZXh0IG9mIGEgcGhvbmUgYXBwIHdoaWNoIHByb3ZpZGVycyBjb21tdXRlcnMgd2l0aCBpbmZvcm1hdGlvbiBhYm91dCB0aGUgcHVibGljIHRyYW5zcG9ydCBzeXN0ZW0gd2hpbGUgYXQgdGhlIHNhbWUgdGltZSwgcmVjb3JkaW5nIHRoZSB1c2VyJ3Mgcm91dGUgdGhyb3VnaCB0aGUgY2l0eS4NCg0KU2luY2UgdGhlIHVzZXJzIHdpbGwgbm90IHByb3ZpZGUgYW55IGlucHV0IGFzaWRlIGZyb20gdGhlIGxvY2F0aW9uIHdoaWNoIGlzIHRyYWNrZWQgYXV0b21hdGljYWxseSB0aGUgc3lzdGVtIHdpbGwgbmVlZCB0byBkaWZmZXJlbnRpYXRlIHdoZW4gYSBjb21tdXRlciBpcyBkcml2aW5nIHRoZWlyIGNhciwgd2Fsa2luZyBvciByaWRpbmcgb24gYW5kIGJ1cyBhbmQgZGV0ZXJtaW5pbmcgd2hpY2ggb25lLg0KDQpUaGUgaW1wbGVtZW50YXRpb24gb2YgdGhlIHN5c3RlbSB3b24ndCBhc3N1bWUgdGhhdCBpbmZvcm1hdGlvbiBhYm91dCB0aGUgbmV0d29yayBzdWNoIGFzIGJ1cyBsb2NhdGlvbnMgYW5kIHNjaGVkdWxlcyB3aWxsIGJlIHByb3ZpZGVkIGZyb20gdGhlIG9uc2V0LCBzbyB0aGUgc3lzdGVtIHdvdWxkIGFsc28gbmVlZCB0byBtYXAgdGhlIG5ldHdvcmsgZnJvbSBzY3JhdGNoLg0KDQpJbiB0aGlzIGluaXRpYWwgYW5hbHlzaXMsIHdlIHdpbGwgZm9jdXMgb24gYSBrZXkgZWxlbWVudCBvZiB0aGUgbWFwcGluZyBwcm9jZXNzOiBmaW5kaW5nIGJ1cyBzdG9wcy4NCg0KU2luY2UgdGhlIHN5c3RlbSBoYXNuJ3QgYmVlbiBpbXBsZW1lbnRlZCBhbmQgaXQgZGVwZW5kcyBvbiBhIGxhcmdlIG51bWJlciBvZiB1c2Vycywgd2UndmUgZ2VuZXJhdGVkIGEgdHJhbnNpdCBzaW11bGF0aW9uIHVzaW5nIFNVTU8gKHN1bW8uZGxyLmRlKSB3aGljaCB3aWxsIHNpbXVsYXRlIGEgbGFyZ2UgcG9wdWxhdGlvbiBvZiBjb21tdXRlcnMgdGhhdCB3aWxsIHdhbGssIGRyaXZlLCBhbmQgZ2V0IG9uIGJ1c2VzIGluIGEgdmlydHVhbCBjaXR5Lg0KDQpUbyBhY2hpZXZlIGEgaGlnaCBkZWdyZWUgb2YgYWNjdXJhY3ksIG5ldyBjb21tdXRlciB0cmFjZXMgbmVlZCB0byBiZSBjb21wYXJlZCB3aXRoIHByaW9yIG9uZXMsIHdoaWNoIHRoZSBzeXN0ZW0gaGFzIGxhYmVsZWQgd2l0aCBhIGhpZ2ggZGVncmVlIG9mIGNlcnRhaW50eS4gU2luY2Ugd2UgZG9uJ3QgaGF2ZSBhIHByZS1leGlzdGluZyBkYXRhIHdoZW4gc2VhcmNoaW5nIGZvciB0aGUgc3RvcHMsIHdlIGFyZSBhaW1pbmcgdGkgbmFycm93IHRoZSBwb3NzaWJsZSBvcHRpb25zIGtub3dpbmcgdGhhdCBhcyBtb3JlIGRhdGEgaXMgYWRkZWQsIGFjY3VyYWN5IHdpbGwgaW1wcm92ZSB1bnRpbCBvbmx5IHRydWUgc3RvcHMgYXJlIG1hcHBlZC4NCg0KIyBEYXRhIEdlbmVyYXRpb24NCg0KQWx0aG91Z2ggaXQncyBwb3NzaWJsZSB0byBjcmVhdGUgYSBmaWN0aW9uYWwgY2l0eSBpbiBTVU1PLCBpdCdzIG11Y2ggbW9yZSBjb252ZW5pZW50IGFuZCB1c2VmdWwgdG8gc2ltdWFsdGUgdHJhZmZpYyBvbiBhbiBleGlzdGluZyBjaXR5IGJ5IGltcG9ydGluZyB0aGUgZGF0YSBmcm9tIE9wZW4gU3RyZWV0IE1hcHMuIEZvciBvdXIgc3R1ZHksIHdlIHVzZWQgQmVybGluIHNpbmNlIHRoZSBwdWJsaWMgdHJhbnNpdCBkYXRhIGlzIHZlcnkgY29tcGxldGUgZm9yIHRoYXQgYXJlYS4NCg0KDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLGVjaG89RkFMU0V9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkobWFncml0dHIpDQpsaWJyYXJ5KHBsb3RseSkNCmxpYnJhcnkobW9uZ29saXRlKQ0KYGBgDQoNCg0KQXMgd2UgY2FuIHNlZSBpbiB0aGUgcHJldmlldywgd2UgaGF2ZSB2ZWhpY2UgaW5mb3JtYXRpb24gaW5jbHVkZWQsIHdoaWNoIHdvbid0IHVzZSBzaW5jZSB0aGUgcG9pbnQgb2YgdGhlIHN0dWR5IGlzIHRvIGluZmVyIHRoaXMgc3RyaWN0bHkgZnJvbSB0aGUgcGVkZXN0cmlhbiBkYXRhLg0KDQpgYGB7ciBlY2hvPUZBTFNFfQ0KbG9jIDwtICJDOlxcVXNlcnNcXGZmaWd1XFxTdW1vXFwyMDE5LTA0LTMwLTIzLTI3LTIzXFxzdW1vVHJhY2UuY3N2Ig0KZGZ0b3QgPC0gcmVhZF9kZWxpbShsb2MsIGNvbF9uYW1lcyA9IFRSVUUsIGRlbGltID0gIjsiKQ0KaGVhZChkZnRvdCkNCmBgYA0KDQoNCg0KIyBEYXRhIENsZWFuaW5nICYgVHJhbnNmb3JtYXRpb24NCg0KV2UgYXJlIG9ubHkgaW50ZXJlc3RlZCBpbiB0aGUgcGVkZXN0cmlhbiBhY3Rpdml0eSBzbyB3ZSB3aWxsIGZpbHRlciBvdXQgYW55IGRhdGEgdGhhdCBoYXMgYSB2ZWhpY2xlIElEIGFuZCB3ZSdsbCByZW1vdmUgY29sdW1ucyB0aGF0IGRvbid0IGhhdmUgcGVkZXN0cmlhbiBkYXRhLg0KDQpgYGB7ciBlY2hvPUZBTFNFfQ0KZGZwZWQgPC0gZmlsdGVyKGRmdG90LCBpcy5uYSh2ZWhpY2xlX2lkKSkgJT4lIA0KICBzZWxlY3QoLWMoMjoxMCkpDQpoZWFkKGRmcGVkKQ0KYGBgDQoNCldlIHN0aWxsIGhhdmUgc2V2ZXJhbCBjb2x1bW5zIHdoaWNoIHdlIHNob3VsZCByZW1vdmUsIHdlJ2xsIG9ubHkgZm9jdXMgb24gdGhlIHRpbWUgc3RlcHMsIGxvY2F0aW9uLCBzcGVlZCBhbmQgcGVkZXN0cmlhbiBJRC4NCg0KYGBge3IgZWNobz1GQUxTRX0NCmRmcGVkICU8PiUgDQogIHNlbGVjdCh0aW1lc3RlcF90aW1lLCBwZXJzb25faWQsIHBlcnNvbl9zcGVlZCwgcGVyc29uX3gsIHBlcnNvbl95KQ0KDQpoZWFkKGRmcGVkKQ0KYGBgDQoNCg0KV2hlbiBwYXNzZW5nZXJzIGFyZSB0cmF2ZWxpbmcgdG9nZXRoZXIsIHRoZSBzaW11bGF0aW9uIHBsYWNlcyB0aGVtIGluIGV4YWN0bHkgdGhhdCBzYW1lIHBvc2l0aW9uLiBBbHRob3VnaCB0aGlzIGlzIHVucmVhbGlzdGljLCBpdCBzZXJ2ZXMgYXMgYXBwcm9wcmlhdGUgc2ltcGxpZmljYXRpb24gYXQgdGhpcyBlYXJseSBzdGFnZSBvZiB0aGUgcHJvamVjdC4gU28sIG9uZSB3YXkgd2UgY2FuIG5hcnJvdyBkb3duIHRoZSBwb3NzaWJsZSBwbGFjZXMgd2hlcmUgYnVzZXMgYXJlIGxvY2F0ZWQgaXMgdG8gZmluZCBncm91cHMgb2YgcGVvcGxlIHdobyBhcmUgdmVyeSBjbG9zZSB0b2dldGhlciBhbmQgbW92aW5nIGF0IHRoZSBzYW1lIHNwZWVkLiANCg0KVG8gcmVmbGVjdCB0aGlzIGluIHRoZSBkYXRhIHdlIHdpbGwgZm9ybSBjbHVzdGVycyBvZiBwZWRlc3RyaWFucyB0aGF0IHNoYXJlIHRoZSBzYW1lIGxvY2F0aW9uIGFuZCB0aW1lIGFuZCBuYW1lIHRoaXMgY29sdW1uIGBjbHVzdGVyYC4gV2UgbWF5IGFsc28gYmUgaW50ZXJlc3RlZCBpbiB0aGUgc2l6ZSBvZiB0aGUgY2x1c3RlciBzaW5jZSB0aGF0IG1heSBnaXZlIHVzIGEgaGludCBvZiB3aGF0IHR5cGUgb2YgdHJhbnNwb3J0YXRpb24gdGhleSBhcmUgdXNpbmcgYW5kIG9mIGFueSBjaGFuZ2VzIGluIHRoZSBzaXplIG9mIHRoZSBjbHVzdGVycy4NCg0KYGBge3IgZWNobz1GQUxTRX0NCmRmYyA8LSBkZnBlZCAlPiUgDQogIGdyb3VwX2J5KHRpbWVzdGVwX3RpbWUscGVyc29uX3gscGVyc29uX3kscGVyc29uX3NwZWVkLHBlcnNvbl9zcGVlZCkgJT4lIA0KICBzdW1tYXJpc2UoY2x1c3RlciA9IGxpc3QodW5pcXVlKHBlcnNvbl9pZCkpKSAlPiUgDQogIG11dGF0ZShjY291bnQgPSBsZW5ndGhzKGNsdXN0ZXIpKQ0KYGBgDQoNCg0KTm93IHRoYXQgd2UgaGF2ZSB0aGUgY2x1c3RlciBjb3VudCBmb3IgZWFjaCB0aW1lIHN0ZXAgYW5kIGxvY2F0aW9uIHdlIGNhbiBhZGQgYW4gYWRkaXRpb25hbCB2YXJpYWJsZSB3aGljaCB0ZWxscyB1cyBpZiwgYXQgYSBwYXJ0aWN1bGFyIGxvY2F0aW9uIGFuZCB0aW1lLCB0aGUgY2x1c3RlciBzaXplIGNoYW5nZWQuIFRoaXMgd2lsbCBoZWxwIHVzIGZpbHRlciBnb29kIGNhbmRpZGF0ZXMgZm9yIHBvc3NpYmxlIGJ1cyBzdG9wIGxvY2F0aW9ucy4NCg0KYGBge3IgZWNobz1GQUxTRX0NCmRmYyAlPD4lIA0KICBncm91cF9ieShwZXJzb25feCxwZXJzb25feSxwZXJzb25fc3BlZWQpICU+JQ0KICBhcnJhbmdlKHRpbWVzdGVwX3RpbWUpICU+JQ0KICBtdXRhdGUoY2NoYW5nZSA9IGNjb3VudCAtIGxhZyhjY291bnQpKQ0KDQpoZWFkKGRmYykNCmBgYA0KDQpCZWZvcmUgd2UgY29udGludWUgd2l0aCBvdXIgZXhwbG9yYXRpb24gYW5kIGFuYWx5c2lzLCBsZXRzIHNhdmUgb3VyIG9yaWdpbmFsIGFuZCB0cmFuZm9ybWVkIGRhdGEuDQoNCmBgYHtyIG1vbmdvZGItY29ubmVjdGlvbnMsIGVjaG89RkFMU0V9DQptb25nb2RiMSA8LSBtb25nbyhjb2xsZWN0aW9uID0gInN1bW9yYXciLGRiID0gInN1bW9kYXRhIiwgdXJsID0gIm1vbmdvZGI6Ly9sb2NhbGhvc3QiLA0KICB2ZXJib3NlID0gRkFMU0UsIG9wdGlvbnMgPSBzc2xfb3B0aW9ucygpKQ0KbW9uZ29kYjIgPC0gbW9uZ28oY29sbGVjdGlvbiA9ICJzdW1vY2x1c3RlcnMiLGRiID0gInN1bW9kYXRhIiwgdXJsID0gIm1vbmdvZGI6Ly9sb2NhbGhvc3QiLA0KICB2ZXJib3NlID0gRkFMU0UsIG9wdGlvbnMgPSBzc2xfb3B0aW9ucygpKQ0KYGBgDQoNCk9uY2UgdGhlIGNvbm5lY3Rpb25zIGFyZSBlc3RhYmxpc2hlZCB3ZSBjYW4gdXBsb2FkIHRoZSBkYXRhIHRvIHRoZSBuZXcgZGF0YWJhc2UuDQpgYGB7ciBVcGxvYWQgdG8gTW9uZ29EQiwgZWNobz1GQUxTRX0NCm1vbmdvZGIxJGluc2VydChkZmN0b3QpDQptb25nb2RiMiRpbnNlcnQoZGZjKQ0KYGBgDQoNCiMgRXhwbG9yYXRpb246IA0KDQpJZiB3ZSB0YWtlIGEgcmFuZG9tIHNuYXBzaG90IG9mIHBlZGVuc3RyaWFuIGNsdXN0ZXJzICggd2hpY2ggYXJlIGFscmVhZHkgYSBzbWFsbCBzdWJzZXQpIHdlIHNlZSB0aGF0IG9idGFpbmluZyByZWxpYWJsZSBkYXRhIHdpbGwgYmUgYSBjaGFsbGVuZ2UuDQoNCmBgYHtyIGVjaG89RkFMU0V9DQpwbG90KGppdHRlcihkZmMkcGVyc29uX3hbZGZjJHRpbWVzdGVwX3RpbWUgPT0gMTc1Nl0pLGppdHRlcihkZmMkcGVyc29uX3lbZGZjJHRpbWVzdGVwX3RpbWUgPT0gMTc1Nl0pKQ0KYGBgDQoNCldoZW4gY29tcGFyaW5nIHNwZWVkcyBiZXR3ZWVuIHZlaGljbGVzIGFuZCBwZWRlc250cmlhbnMgd2UgZmluZCBhIGtleSBkaWZmZXJlbmNpdG9yLiBCZXNpZGVzIHRvdGFsIHN0YW5kc3RpbGwsIHdpbGwgZG8gbW9zdCBvZiB0aGVpciB3YWxpbmcgYXQgYXJvdW5kIDFtL3MsIGEgc3BlZWQgdGhhdCByYXJlbHkgc2VlbiBpbiB2ZWhpY2xlcy4NCg0KYGBge3IgZWNobz1GQUxTRSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCnAxIDwtIGRmdG90ICU+JSANCiAgc2FtcGxlX24oMTAwMCkgJT4lIA0KICBwbG90X2x5KGFscGhhID0gMC42KSAlPiUNCiAgYWRkX2hpc3RvZ3JhbSh4ID0gfmRmdG90JHZlaGljbGVfc3BlZWRbZGZ0b3QkdmVoaWNsZV90eXBlID09ICdwdF9idXMnIHwgZGZ0b3QkdmVoaWNsZV90eXBlID09ICdidXNfYnVzJ10sIG5hbWUgPSAiUHVibGljIEJ1cyIpICU+JQ0KICBhZGRfaGlzdG9ncmFtKHggPSB+ZGZ0b3QkdmVoaWNsZV9zcGVlZFtkZnRvdCR2ZWhpY2xlX3R5cGUgPT0gJ3ZlaF9wYXNzZW5nZXInXSwgbmFtZSA9ICJQYXNzZW5nZXIgVmVoaWNsZSIpICU+JQ0KICBsYXlvdXQoYmFybW9kZSA9ICJvdmVybGF5IikNCg0KcDENCmBgYA0KDQoNCg0KYGBge3IgZWNobz1GQUxTRX0NCkRhdGFFeHBsb3Jlcjo6cGxvdF9kZW5zaXR5KGRmYyRwZXJzb25fc3BlZWQsbmNvbCA9IDEpDQpgYGANCg0KQWx0aG91Z2ggbm90IG91ciBtYWluIGdvYWwsIHdlIGNhbiB1c2UgdGhpcyBpbmZvcm1hdGlvbiB0byBmaW5kIHJvYWRzIChhbmQgdHJhaW4gdHJhY2tzKS4gQlkgZmlsdGVyaW5nIGZvciBncm91cHMgbW92aW5nIGF0IG92ZXIgN20vcyBtb3N0IGJlY29tZSBlYXN5IHRvIHNlZS4gDQoNCmBgYHtyfQ0KcGxvdChkZmMkcGVyc29uX3hbZGZjJHBlcnNvbl9zcGVlZCA+N10saml0dGVyKGRmYyRwZXJzb25feVtkZmMkcGVyc29uX3NwZWVkID4gN10pKQ0KYGBgDQoNCkxldCdzIG5vdyBncmFwaCBjbHVzdGVyIHRoYXQgYXJlbid0IG1vdmluZyBhbmQgd2hpY2ggYXJlIGxhcmdlciB0aGFuIDEwLiANCg0KYGBge3J9DQpzbW9vdGhTY2F0dGVyKA0KICBkZmMkcGVyc29uX3hbZGZjJHBlcnNvbl9zcGVlZCA9PSAwIHwgZGZjJGNjb3VudCA+IDEwXSwNCiAgZGZjJHBlcnNvbl95W2RmYyRwZXJzb25fc3BlZWQgPT0gMCB8IGRmYyRjY291bnQgPiAxMF0sDQogIG5iaW4gPSAxMDAwLA0KICBiYW5kd2lkdGggPSA1KQ0KYGBgDQoNCk1hbnkgb2YgdGhlIGJ1cyBzdG9wcyBhcmUgdmlzaWJsZSB1bmRlciB0aGUgZGFyayBibG90cyBidXQgd2UgaGF2ZSBhbG90IG9mIG5vaXNlLiBMZXQgaW5zdGVhZCBmb2N1cyBvbiBjbHVzdGVyIGNoYW5nZXMgd2hpbGUgYXQgcmVzdC4gVGhlIHRyYW5zZm9ybWF0aW9uIGJlbG93IGNhbGN1bGF0ZXMgdGhlIGFic29sdXRlIGNoYW5nZSBpbiBjbHVzdGVyIHNpemUgZm9yIGNsdXN0ZXJzIHRoYXQgc2hhcmUgdGhlIHNhbWUgbG9jYXRpb24gYW5kIHRpbWUuDQoNCmBgYHtyfQ0KZGZjMiA8LSBkZmMgJT4lICANCiAgZmlsdGVyKHBlcnNvbl9zcGVlZCA9PSAwKSAlPiUgDQogIG11dGF0ZShhYnNjYyA9IGFicyhjY2hhbmdlKSkgJT4lIA0KICBmaWx0ZXIoYWJzY2MgPiAwKSAlPiUgDQogIGRwbHlyOjpncm91cF9ieShwZXJzb25feCwgcGVyc29uX3kpICU+JSANCiAgY291bnQocGVyc29uX3gsIHBlcnNvbl95KQ0KICANCmBgYA0KDQoNCmBgYHtyfQ0Kc21vb3RoU2NhdHRlcigNCiAgZGZjMiRwZXJzb25feCwNCiAgZGZjMiRwZXJzb25feSwNCiAgbmJpbiA9IDEwMDAsDQogIGJhbmR3aWR0aCA9IDUpDQpgYGANCg0KVGhpcyBpcyBhbiBpbXByb3ZlbWVudC4gV2UgaGF2ZSBtb3JlIGRlZmluZWQgc3BvdHMgYnV0IHdlIHN0aWxsIG1hbnkgbW9yZSBzcG90cyB0aGFuIHN0b3BzLg0KDQoNCiMgQW5hbHlzaXMgJiBDb25jbHVzaW9uDQoNCkFzIHdlJ3ZlIHNlZW4sIGFuYWx5emluZyB0aGUgc3BlZWQgYW5kIGNvbGxlY3RpdmUgYmVoYXZpb3Igb2YgcGVkZXN0cmlhbnMgY2FuIGdpdmUgdXMgbWFueSBjbHVlcyBhYm91dCB0aGUgbGF5b3V0IG9mIHRoZSBjaXR5LCBhbmQgdGhlaXIgbW9kZSBvZiB0cmFuc3BvcnRhdGlvbi4gQWx0aG91Z2ggdGhlIHJlc3VsdHMgYXJlIHZlcnkgcHJvbWlzaW5nIHRoZXkgYXJlIGNsZWFybHkgbGFja2luZyBhcyB3ZSBhcmUgc3RpbGwgZ2V0dGluZyBtYW55IGZhbHNlIHBvc2l0aXZlcy4gTW9zdCBvZiB0aGVzZSBhcmUgbGlrZWx5IHRyYWluIHN0b3BzLCBwZWRlc3RyaWFuIGNyb3NzaW5ncyBhbmQgYW55IG90aGVyIHBsYWNlIHdoZXJlIHBlZGVzdHJpYW5zIG1heSBhZ2dsb21lcmF0ZSBpbiBjbG9zZSBncm91cHMuDQoNCkFuIG9idmlvdXMgZXh0ZW5zaW9uIG9mIHRoaXMgbW9kZWwgd2hpY2ggc2hvdWxkIGdyZWF0bHkgZW5oYW5jZSBpdHMgY2FwYWJpbGl0aWVzIGlzIHRvIGV4dHJhY3QgImNsdXN0ZXIgY2hhaW5zIiBmcm9tIHRoZSBkYXRhLiBJbiBvdXIgY3VycmVudCBhbmFseXNpcywgd2UgcmVseSBvbiBpbnN0YW50YW5lb3VzIGNoYW5nZXMgaW4gZ3JvdXAgc2l6ZSB3aGljaCBhcmUgYm90aCB1bnJlYWxpc3RpYyBhbmQgbGltaXRpbmcuIElmIHdlIGlkZW50aWZ5IGNvbnNlY3V0aXZlIHRpbWVzdGVwcyBpbiB3aGljaCB0d28gb3IgbW9yZSBwZWRlc3RyaWFucyBhcmUgcHJlc2VudCwgY29tcGxldGUgcm91dGVzIGNvdWxkIGJlIGxpbmtlZCB3aGljaCB3b3VsZCBhbHNvIGFsbG93IHVzIHRvIGFuYWx5emUgdGhlIGFjY2VsZXJhdGlvbiBwcm9maWxlIG9mIGVhY2ggY2hhaW4uIEFsbCB0aGUgcHVibGljIHRyYW5zcG9ydCByb3V0ZXMgY291bGQgYmUgZWFzaWx5IG9idGFpbmVkIGJ5IGxpbmtpbmcgY2hhaW5zLiBUaGUgYWNjZWxlcmF0aW9uIHByb2ZpbGUgd291bGQgbm90IG9ubHkgZW5oYW5jZSB0aGUgbG9jYXRpb24gb2Ygc3RvcHMsIGl0IHdvdWxkIGxpa2VseSBkaWZmZXJlbnRpYXRlIGFsbCBtb2RlcyBvZiB0cmFuc3BvcnQsIGZyb20gd2Fsa2luZyB0byB0YWtpbmcgcmlkaW5nIG9uIGEgZmVycnkuDQoNCkFzIG1lbnRpb25lZCBhYm92ZSwgdGhlIHNpbXVsYXRpb24gaW50cm9kdWNlcyBhIG1ham9yIHNpbXBsaWZpY2F0aW9uIGJ5IHNldHRpbmcgdGhlIGxvY2F0aW9uIG9mIGJ1cyBwYXNzZW5nZXJzIGV4YWN0bHkgdGhlIHNhbWUuIEl0IHdpbGwgZXZlbnR1YWxseSBiZSBuZWNlc3NhcnkgdG8gaW50cm9kdWNlIGEgZGVncmVlIG9mIHJhbmRvbW5lc3MgdG8gYWNjb3VudCBmb3IgZGlmZmVyZW50IHNlYXQgbG9jYXRpb24gYW5kIEdQUyBpbmFjY3VyYWN5LiBJbiB0aGlzIGNhc2UsIGRldGVybWluaW5nIHdoaWNoIHBlZGVzdHJpYW4gYmVsb25nIHRvIGEgY2x1c3RlciB3aWxsIGJlIG1vcmUgZGlmZmljdWx0IGJ1dCBzaG91bGQgYmUgcG9zc2libGUgYnkgY29uc3RydWN0aW5nIHNvbWUga2luZCBvZiBsb2NhbGl6ZWQgY29pbnRlZ3JhdGlvbiB0ZXN0IG9uIHBvc3NpYmxlIGNsdXN0ZXIgY2hhaW5zLg0KDQpJdCB3YXMgbXkgaW50ZW50aW9uIHRvIGluY29ycG9yYXRlIGNsdXN0ZXIgY2hhaW5zIGZyb20gdGhlIG9uc2V0IGJ1dCB0aGUgZGF0YSBtYW5pcHVsYXRpb24gd2FzIHVuZm9ydHVuYXRlbHkgYmV5b25kIG15IGNhcGFiaWxpdGllcyBhdCB0aGUgdGltZS4gSSBjb25zdWx0ZWQgd2l0aCBzZXZlcmFsIHJlc2VhcmNoZXJzIGJ1dCB0aGV5IHdlcmUgYWxzbyB1bmFibGUgdG8gaGVscCBhbHRob3VnaCB0aGUgbG9naWMgb2YgdGhlIHRyYW5zZm9ybWF0aW9uIGlzIGZhaXJseSBzdHJhaWdodGZvcndhcmQuIEluIHNwaXRlIG9mIHRoaXMsIHRoZSByZXN1bHRzIHN1Z2dlc3QgdGhhdCBtZWFuaW5nZnVsIGluZm9ybWF0aW9uIGNhbiBiZSBleHRyYWN0ZWQgZnJvbSByYW5kb20gR1BTIHRyYWNlcywgYW5kIHRodXMgYWRkaXRpb25hbCB3b3JrIG9uIHRoaXMgdG9waWMgc2VlbXMgd2FycmFudGVkLg0KDQojIFJlZmVyZW5jZXMNCg0KS3Jhanpld2ljeiwgRC4sIEVyZG1hbm4sIEouLCBCZWhyaXNjaCwgTS4sICYgQmlla2VyLCBMLiAoMjAxMikuIFJlY2VudCBkZXZlbG9wbWVudCBhbmQgYXBwbGljYXRpb25zIG9mIFNVTU8tU2ltdWxhdGlvbiBvZiBVcmJhbiBNT2JpbGl0eS4gSW50ZXJuYXRpb25hbCBKb3VybmFsIE9uIEFkdmFuY2VzIGluIFN5c3RlbXMgYW5kIE1lYXN1cmVtZW50cywgNSwgMTI44oCTMTM4LiBSZXRyaWV2ZWQgZnJvbSBodHRwczovL2VsaWIuZGxyLmRlLzgwNDgzLw==