------ art_28016_26962572.1188870475282 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline On 8/31/07, Ruby Quiz <james / grayproductions.net> wrote: > This week's task is to implement the Rope data structure as a Ruby class. I modified my implementation a bit more and provided results along with the other ruby implementations (sorry Mauricio) submitted. The benchmark test I used is attached. It can run the original build/sort that assumes mutable ropes and a build/sort that can also be used with immutable ropes (in addition to mutable ropes). These tests assume that << can only take another rope. I included some testing to ensure the results are correct. I also used the linux /proc/$$/status to get the memory. Mahurin::StringRope is almost the same as my previous submission. The main change was handling a boundary case better so I don't unecessarily concat an empty rope (a < should have been a < - this almost doubled the performance. I added the class Mahurin::MutableStringRope which is a wrapper around an immutable rope. I just reassign the instance variable (@rope) to make changes. I implemented a bunch of String/Array mutable methods in this class. This wrapper class hurt performance much more than I expected (double the run-time). I also tried out not auto-balancing and using an explicit normalize (Mahurin::DenormalStringRope). This gave much faster build time as expected, but the sort time slowed down just as much. I guess for this random data set (I use a fixed seed), qsort doesn't keep the tree balanced (pivot doesn't necessarily partition equally). The larger depth for the non-auto-balanced rope hurts the slice time. I think biting the bullet for auto-balancing is the better way to go. I added a subclass for handling flattening concatenations of short strings (Mahurin::ShortStringRope) just to be complete. It isn't useful in this benchmark, but also doesn't hurt much (within the 0.01 second error margin). CPU(user+sys,sec) mem(peak,MB) ------------------- ------------ build sort total build sort class ----- ---- ----- ----- ---- ----- 0.10 1.70 1.80 287 1327 String 0.01 0.27 0.28 22 153 Porth::Rope 0.02 0.83 0.85 22 34 Choudhury::Rope * 0.02 0.06 0.08 22 29 Mahurin::StringRope + 0.00 0.08 0.08 22 30 Mahurin::DenormalStringRope + 0.02 0.14 0.16 22 29 Mahurin::MutableStringRope 0.07 0.10 0.17 151 151 Munkby::ArrayRope 0.02 0.73 0.75 22 655 Kalenkovich::Rope * CPU : minimum from 40 iterations mem : peak over the 40 iterations * : self-checking failed + : immutable benchmark needed ------ art_28016_26962572.1188870475282 Content-Type: application/x-ruby; name=test2.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_f65nzmza Content-Disposition: attachment; filename="test2.rb" cmVxdWlyZSAnYmVuY2htYXJrJwoKI1RoaXMgY29kZSBtYWtlIGEgU3RyaW5nL1JvcGUgb2YgIENI VU5LUyBjaHVua3Mgb2YgdGV4dAojZWFjaCBjaHVuY2sgaXMgU0laRSBieXRlcyBsb25nLiAgRWFj aCBjaHVuY2sgc3RhcnRzIHdpdGgKI2FuIDggYnl0ZSBudW1iZXIuICBJbml0aWFsbHkgdGhlIGNo dW5ja3MgYXJlIHNodWZmbGVkIHRoZQojcXNvcnQgbWV0aG9kIHNvcnRzIHRoZW0gaW50byBhc2Nl bmRpbmcgb3JkZXIuCiMKI3Bhc3MgdGhlIG5hbWUgb2YgdGhlIGNsYXNzIHRvIHVzZSBhcyBhIHBh cmFtZXRlcgojcnVieSAtciByb3BlLnJiIHRoaXNfZmlsZSBbLWltbXV0YWJsZV0gUm9wZSBpdGVy YXRpb25zCgpBUkdWLnNoaWZ0IGlmIChpbW11dGFibGUgPSAoQVJHVlswXVswLDJdPT0iLWkiKSkK VGV4dENsYXNzID0gZXZhbChBUkdWLnNoaWZ0IHx8ICJTdHJpbmciKQppdGVyYXRpb25zID0gKEFS R1Yuc2hpZnQgfHwgMSkudG9faQoKZGVmIHFzb3J0X2ltbXV0YWJsZSh0ZXh0KQogcmV0dXJuIFRl eHRDbGFzcy5uZXcgaWYgdGV4dC5sZW5ndGggPT0gMAogcGl2b3QgPSB0ZXh0LnNsaWNlKDAsOCku dG9fcy50b19pCiBsZXNzID0gVGV4dENsYXNzLm5ldwogbW9yZSA9IFRleHRDbGFzcy5uZXcKIG9m ZnNldCA9IDgrU0laRQogd2hpbGUgKG9mZnNldCA8IHRleHQubGVuZ3RoKQogICBpID0gdGV4dC5z bGljZShvZmZzZXQsOCkudG9fcy50b19pCiAgIGlmIGkgPCBwaXZvdAogICAgICAgbGVzcyA8PD0g dGV4dC5zbGljZShvZmZzZXQsOCtTSVpFKQogICBlbHNlCiAgICAgICBtb3JlIDw8PSB0ZXh0LnNs aWNlKG9mZnNldCw4K1NJWkUpCiAgIGVuZAogICBvZmZzZXQgPSBvZmZzZXQgKyA4K1NJWkUKIGVu ZAogcmV0dXJuIHFzb3J0X2ltbXV0YWJsZShsZXNzKSA8PCB0ZXh0LnNsaWNlKDAsOCtTSVpFKSA8 PCBxc29ydF9pbW11dGFibGUobW9yZSkKZW5kCgpkZWYgcXNvcnRfbXV0YWJsZSh0ZXh0KQogcmV0 dXJuIFRleHRDbGFzcy5uZXcgaWYgdGV4dC5sZW5ndGggPT0gMAogcGl2b3QgPSB0ZXh0LnNsaWNl KDAsOCkudG9fcy50b19pCiBsZXNzID0gVGV4dENsYXNzLm5ldwogbW9yZSA9IFRleHRDbGFzcy5u ZXcKIG9mZnNldCA9IDgrU0laRQogd2hpbGUgKG9mZnNldCA8IHRleHQubGVuZ3RoKQogICBpID0g dGV4dC5zbGljZShvZmZzZXQsOCkudG9fcy50b19pCiAgIChpIDwgcGl2b3QgPyBsZXNzIDogbW9y ZSkgPDwgdGV4dC5zbGljZShvZmZzZXQsOCtTSVpFKQogICBvZmZzZXQgPSBvZmZzZXQgKyA4K1NJ WkUKIGVuZAogcmV0dXJuIHFzb3J0X211dGFibGUobGVzcykgPDwgdGV4dC5zbGljZSgwLDgrU0la RSkgPDwgcXNvcnRfbXV0YWJsZShtb3JlKQplbmQKCmRlZiBidWlsZF9tdXRhYmxlKGJ1bGtfdGV4 dCkKIGRhdGEgPSBUZXh0Q2xhc3MubmV3CiAoMC4uQ0hVTktTKS5zb3J0X2J5IHsgcmFuZCB9LmVh Y2ggZG8gfG58CiAgIGRhdGEgPDwgVGV4dENsYXNzLm5ldyhzcHJpbnRmKCIlMDhpIixuKSkgPDwg YnVsa190ZXh0CiBlbmQKIGRhdGEKZW5kCgpkZWYgYnVpbGRfaW1tdXRhYmxlKGJ1bGtfdGV4dCkK ICgwLi5DSFVOS1MpLnNvcnRfYnkgeyByYW5kIH0uaW5qZWN0KFRleHRDbGFzcy5uZXcpIGRvIHxk YXRhLCBufAogICBkYXRhIDw8IFRleHRDbGFzcy5uZXcoc3ByaW50ZigiJTA4aSIsbikpIDw8IGJ1 bGtfdGV4dAogZW5kCmVuZAoKZGVmIG1lbQogIHZtc2l6ZSA9IG5pbAogIHZtcGVhayA9IG5pbAog IEZpbGUubmV3KCIvcHJvYy8jeyQkfS9zdGF0dXMiKS5lYWNoX2xpbmUgeyB8bGluZXwKICAgICAg aWYgbGluZT1+L15WbVNpemVcOlxzKyguKilcbi8KICAgICAgICAgIHZtc2l6ZSA9ICQxCiAgICAg IGVsc2lmIGxpbmU9fi9eVm1QZWFrXDpccysoLiopXG4vCiAgICAgICAgICB2bXBlYWsgPSAkMQog ICAgICBlbmQKICB9CiAgW3Ztc2l6ZSx2bXBlYWtdCmVuZAoKcXNvcnQgPSBtZXRob2QoaW1tdXRh YmxlID8gOnFzb3J0X2ltbXV0YWJsZSA6IDpxc29ydF9tdXRhYmxlKQpidWlsZGl0ID0gbWV0aG9k KGltbXV0YWJsZSA/IDpidWlsZF9pbW11dGFibGUgOiA6YnVpbGRfbXV0YWJsZSkKCnNyYW5kKDEy MzQ1Njc4OSkKU0laRSAgPSA1MTIgKiAxMDI0CkNIVU5LUyA9IDEyOApDSEFSUyA9ICV3W1IgTyBQ IEVdCmJ1bGtfc3RyaW5nID0gQXJyYXkubmV3KFNJWkUpIHsgQ0hBUlNbcmFuZCg0KV0gfS5qb2lu CmJ1bGtfdGV4dCA9IFRleHRDbGFzcy5uZXcoYnVsa19zdHJpbmcpCgpHQy5zdGFydAoKcHV0cyAi SW5pdGlhbDogI3ttZW0uam9pbignICAgJyl9IgoKZGF0YSA9IG5pbApidWlsZCA9IFtdCml0ZXJh dGlvbnMudGltZXMgewogR0Muc3RhcnQKIGJ1aWxkIDw8IEJlbmNobWFyay5tZWFzdXJlIGRvCiAg ZGF0YSA9IGJ1aWxkaXQuY2FsbChidWxrX3RleHQpCiAgZGF0YSA9IGRhdGEubm9ybWFsaXplIGlm IGRhdGEucmVzcG9uZF90bz8gOm5vcm1hbGl6ZQogZW5kCn0KR0Muc3RhcnQKYnVpbGQgPSBidWls ZC5pbmplY3QgeyB8bWluLGN1cnwgKGN1ci50b3RhbDxtaW4udG90YWwpID8gY3VyIDogbWluIH0K cHV0cyAiQnVpbGQ6ICN7YnVpbGQudG9fcy5jaG9wfSAgICN7bWVtLmpvaW4oJyAgICcpfSIKCiMg Y2hlY2sgdGhhdCB0aGUgaW5kaWNlcyBhZGQgdXAKc3VtID0gMAowLnN0ZXAoZGF0YS5sZW5ndGgt MSwgOCtTSVpFKSB7IHxvZmZzZXR8CiAgICBzdW0gKz0gZGF0YS5zbGljZShvZmZzZXQsOCkudG9f cy50b19pCiAgICBidWxrX2RhdGEgPSBkYXRhLnNsaWNlKG9mZnNldCs4LFNJWkUpLnRvX3MKICAg IHdhcm4oIiN7YnVsa19kYXRhWzAsMTBdfS4uLi4gIT0gI3tidWxrX3N0cmluZ1swLDEwXX0uLi4u IikgaWYgYnVsa19kYXRhIT1idWxrX3N0cmluZwp9CmV4cGVjdGVkX3N1bSA9IChDSFVOS1MqKENI VU5LUysxKSkvMgp3YXJuKCIje3N1bX0hPSN7ZXhwZWN0ZWRfc3VtfSIpIGlmIHN1bSE9ZXhwZWN0 ZWRfc3VtCgpzb3J0ZWRfZGF0YSA9IG5pbApzb3J0ID0gW10KaXRlcmF0aW9ucy50aW1lcyB7CiBH Qy5zdGFydAogc29ydCA8PCBCZW5jaG1hcmsubWVhc3VyZSBkbwogIHNvcnRlZF9kYXRhID0gcXNv cnQuY2FsbChkYXRhKQogZW5kCn0Kc29ydCA9IHNvcnQuaW5qZWN0IHsgfG1pbixjdXJ8IChjdXIu dG90YWw8bWluLnRvdGFsKSA/IGN1ciA6IG1pbiB9CnB1dHMgIlNvcnQ6ICN7c29ydC50b19zLmNo b3B9ICAgI3ttZW0uam9pbignICAgJyl9IgoKIyBjaGVjayB0aGUgc29ydGVkIHJlc3VsdAppID0g MAowLnN0ZXAoc29ydGVkX2RhdGEubGVuZ3RoLTEsIDgrU0laRSkgeyB8b2Zmc2V0fAogICAgZGF0 YWkgPSBzb3J0ZWRfZGF0YS5zbGljZShvZmZzZXQsOCkudG9fcwogICAgd2FybigiI3tkYXRhaS50 b19pfSE9I3tpfSIpIGlmIGRhdGFpLnRvX2khPWkKICAgIGJ1bGtfZGF0YSA9IHNvcnRlZF9kYXRh LnNsaWNlKG9mZnNldCs4LFNJWkUpLnRvX3MKICAgIHdhcm4oIiN7YnVsa19kYXRhWzAsMTBdfS4u Li4gIT0gI3tidWxrX3N0cmluZ1swLDEwXX0uLi4uIikgaWYgYnVsa19kYXRhIT1idWxrX3N0cmlu ZwogICAgaSArPSAxCn0Kd2FybigiI3tpfSE9I3tDSFVOS1MrMX0iKSBpZiBpIT1DSFVOS1MrMQoK Cg ------ art_28016_26962572.1188870475282 Content-Type: application/x-ruby; name=mahurin.rb Content-Transfer-Encoding: base64 X-Attachment-Id: f_f65plhz5 Content-Disposition: attachment; filename="mahurin.rb" bW9kdWxlIE1haHVyaW4KCmNsYXNzIFJvcGUKICAgIGluY2x1ZGUgRW51bWVyYWJsZQogICAgIyBm b3JtIGEgYmluYXJ5IHRyZWUgZnJvbSB0d28gcm9wZXMgKHBvc3NpYmx5IHN1Yi10cmVlcykKICAg IGRlZiBpbml0aWFsaXplKGxlZnQscmlnaHQpCiAgICAgICAgQGxlZnQgPSBsZWZ0CiAgICAgICAg QHJpZ2h0ID0gcmlnaHQKICAgICAgICBAbGxlbmd0aCA9IEBsZWZ0Lmxlbmd0aAogICAgICAgIEBs ZW5ndGggPSBAbGxlbmd0aCtAcmlnaHQubGVuZ3RoCiAgICAgICAgQGRlcHRoID0gW2xlZnQuZGVw dGgsIHJpZ2h0LmRlcHRoXS5tYXgrMQogICAgZW5kCiAgICAjIG51bWJlciBvZiBlbGVtZW50cyBp biB0aGlzIHJvcGUKICAgIGRlZiBsZW5ndGgKICAgICAgICBAbGVuZ3RoCiAgICBlbmQKICAgICMg ZGVwdGggb2YgdGhlIHRyZWUgKHRvIGhlbHAga2VlcCB0aGUgdHJlZSBiYWxhbmNlZCkKICAgIGRl ZiBkZXB0aAogICAgICAgIEBkZXB0aAogICAgZW5kCiAgICAjIGxlZnQgcm9wZSAobm90IG5lZWRl ZCB3aGVuIGRlcHRoPT0wKQogICAgZGVmIGxlZnQKICAgICAgICBAbGVmdAogICAgZW5kCiAgICAj IHJpZ2h0IHJvcGUgKG5vdCBuZWVkZWQgd2hlbiBkZXB0aD09MCkKICAgIGRlZiByaWdodAogICAg ICAgIEByaWdodAogICAgZW5kCiAgICAjIGFwcGVuZGVkIHJvcGUgKG5vbi1tb2RpZnlpbmcpCiAg ICBkZWYgKyhvdGhlcikKICAgICAgICAjIGJhbGFuY2UgYXMgYW4gQVZMIHRyZWUKICAgICAgICBi YWxhbmNlID0gb3RoZXIuZGVwdGgtQGRlcHRoCiAgICAgICAgaWYgYmFsYW5jZT4rMQogICAgICAg ICAgICBsZWZ0ID0gb3RoZXIubGVmdAogICAgICAgICAgICByaWdodCA9IG90aGVyLnJpZ2h0CiAg ICAgICAgICAgIGlmIGxlZnQuZGVwdGg+cmlnaHQuZGVwdGgKICAgICAgICAgICAgICAgICMgcm90 YXRlIG90aGVyIHRvIHJpZ2h0IGJlZm9yZSByb3RhdGluZyBzZWxmK290aGVyIHRvIGxlZnQKICAg ICAgICAgICAgICAgIChzZWxmICsgbGVmdC5sZWZ0KSArIChsZWZ0LnJpZ2h0ICsgcmlnaHQpCiAg ICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICMgcm90YXRlIHNlbGYrb3RoZXIgdG8gbGVm dAogICAgICAgICAgICAgICAgKHNlbGYgKyBsZWZ0KSArIHJpZ2h0CiAgICAgICAgICAgIGVuZAog ICAgICAgIGVsc2lmIGJhbGFuY2U8LTEKICAgICAgICAgICAgaWYgQHJpZ2h0LmRlcHRoPkBsZWZ0 LmRlcHRoCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBzZWxmIHRvIGxlZnQgYmVmb3JlIHJvdGF0 aW5nIHNlbGYrb3RoZXIgdG8gcmlnaHQKICAgICAgICAgICAgICAgIChAbGVmdCArIEByaWdodC5s ZWZ0KSArIChAcmlnaHQucmlnaHQgKyBvdGhlcikKICAgICAgICAgICAgZWxzZQogICAgICAgICAg ICAgICAgIyByb3RhdGUgc2VsZitvdGhlciB0byByaWdodAogICAgICAgICAgICAgICAgQGxlZnQg KyAoQHJpZ2h0ICsgb3RoZXIpCiAgICAgICAgICAgIGVuZAogICAgICAgIGVsc2UKICAgICAgICAg ICAgc2VsZi5jbGFzcy5uZXcoc2VsZiwgb3RoZXIpCiAgICAgICAgZW5kCiAgICBlbmQKICAgIGFs aWFzX21ldGhvZCg6PDwsIDorKQogICAgIyBzbGljZSBvZiB0aGUgcm9wZQogICAgZGVmIHNsaWNl KHN0YXJ0LCBsZW4pCiAgICAgICAgcmV0dXJuIHNlbGYgaWYgc3RhcnQuemVybz8gYW5kIGxlbj09 QGxlbmd0aAogICAgICAgIHJzdGFydCA9IHN0YXJ0LUBsbGVuZ3RoCiAgICAgICAgcmV0dXJuIEBy aWdodC5zbGljZShyc3RhcnQsIGxlbikgaWYgcnN0YXJ0Pj0wCiAgICAgICAgbGxlbiA9IEBsbGVu Z3RoLXN0YXJ0CiAgICAgICAgcmxlbiA9IGxlbi1sbGVuCiAgICAgICAgaWYgcmxlbj4wCiAgICAg ICAgICAgIEBsZWZ0LnNsaWNlKHN0YXJ0LCBsbGVuKSArIEByaWdodC5zbGljZSgwLCBybGVuKQog ICAgICAgIGVsc2UKICAgICAgICAgICAgQGxlZnQuc2xpY2Uoc3RhcnQsIGxlbikKICAgICAgICBl bmQKICAgIGVuZAogICAgIyBlbGVtZW50IGF0IGEgY2VydGFpbiBwb3NpdGlvbiBpbiB0aGUgcm9w ZQogICAgZGVmIGF0KGluZGV4KQogICAgICAgIHJpbmRleCA9IGluZGV4LUBsbGVuZ3RoCiAgICAg ICAgaWYgcmluZGV4PDAKICAgICAgICAgICAgQGxlZnQuYXQoaW5kZXgpCiAgICAgICAgZWxzZQog ICAgICAgICAgICBAcmlnaHQuYXQocmluZGV4KQogICAgICAgIGVuZAogICAgZW5kCiAgICAjIGl0 ZXJhdGUgdGhyb3VnaCB0aGUgZWxlbWVudHMgaW4gdGhlIHJvcGUKICAgIGRlZiBlYWNoKCZibG9j aykKICAgICAgICBAbGVmdC5lYWNoKCZibG9jaykKICAgICAgICBAcmlnaHQuZWFjaCgmYmxvY2sp CiAgICBlbmQKICAgICMgZmxhdHRlbiB0aGUgcm9wZSBpbnRvIGEgc3RyaW5nIChvcHRpb25hbGx5 IHN0YXJ0aW5nIHdpdGggYSBwcmVmaXgpCiAgICBkZWYgdG9fcyhzPSIiKQogICAgICAgIEByaWdo dC50b19zKEBsZWZ0LnRvX3MocykpCiAgICBlbmQKZW5kCgpFbXB0eVJvcGUgPSBPYmplY3QubmV3 CmNsYXNzIDw8IEVtcHR5Um9wZQogICAgaW5jbHVkZSBFbnVtZXJhYmxlCiAgICBkZWYgbGVuZ3Ro CiAgICAgICAgMAogICAgZW5kCiAgICBkZWYgZGVwdGgKICAgICAgICAwCiAgICBlbmQKICAgIGRl ZiArKG90aGVyKQogICAgICAgIG90aGVyCiAgICBlbmQKICAgIGFsaWFzX21ldGhvZCg6PDwsIDor KQogICAgZGVmIHNsaWNlKHN0YXJ0LCBsZW4pCiAgICAgICAgc2VsZgogICAgZW5kCiAgICBkZWYg ZWFjaAogICAgZW5kCiAgICBkZWYgdG9fcwogICAgICAgICIiCiAgICBlbmQKZW5kCgpjbGFzcyBT dHJpbmdSb3BlCiAgICBpbmNsdWRlIEVudW1lcmFibGUKICAgIGRlZiBzZWxmLm5ldygqYXJncykK ICAgICAgICBpZiBhcmdzLmVtcHR5PwogICAgICAgICAgICBFbXB0eVJvcGUKICAgICAgICBlbHNl CiAgICAgICAgICAgIHN1cGVyCiAgICAgICAgZW5kCiAgICBlbmQKICAgIGRlZiBpbml0aWFsaXpl KGRhdGEpCiAgICAgICAgQGRhdGEgPSBkYXRhCiAgICBlbmQKICAgIGRlZiBsZW5ndGgKICAgICAg ICBAZGF0YS5sZW5ndGgKICAgIGVuZAogICAgZGVmIGRlcHRoCiAgICAgICAgMAogICAgZW5kCiAg ICBkZWYgKyhvdGhlcikKICAgICAgICBiYWxhbmNlID0gb3RoZXIuZGVwdGgKICAgICAgICBpZiBi YWxhbmNlPjEKICAgICAgICAgICAgbGVmdCA9IG90aGVyLmxlZnQKICAgICAgICAgICAgcmlnaHQg PSBvdGhlci5yaWdodAogICAgICAgICAgICBpZiBsZWZ0LmRlcHRoPnJpZ2h0LmRlcHRoCiAgICAg ICAgICAgICAgICAjIHJvdGF0ZSBvdGhlciB0byByaWdodCBiZWZvcmUgcm90YXRpbmcgc2VsZitv dGhlciB0byBsZWZ0CiAgICAgICAgICAgICAgICAoc2VsZiArIGxlZnQubGVmdCkgKyAobGVmdC5y aWdodCArIHJpZ2h0KQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAjIHJvdGF0ZSBz ZWxmK290aGVyIHRvIGxlZnQKICAgICAgICAgICAgICAgIChzZWxmICsgbGVmdCkgKyByaWdodAog ICAgICAgICAgICBlbmQKICAgICAgICBlbHNlCiAgICAgICAgICAgIFJvcGUubmV3KHNlbGYsIG90 aGVyKQogICAgICAgIGVuZAogICAgZW5kCiAgICBhbGlhc19tZXRob2QoOjw8LCA6KykKICAgIGRl ZiBzbGljZShzdGFydCwgbGVuKQogICAgICAgIHJldHVybiBzZWxmIGlmIHN0YXJ0Lnplcm8/IGFu ZCBsZW49PUBkYXRhLmxlbmd0aAogICAgICAgICMgZGVwZW5kIG9uIHJ1YnkncyBDT1cgbWVjaGFu aXNtIHRvIGp1c3QgcmVmZXJlbmNlIHRoZSBzbGljZSBkYXRhCiAgICAgICAgc2VsZi5jbGFzcy5u ZXcoQGRhdGEuc2xpY2Uoc3RhcnQsIGxlbikpCiAgICBlbmQKICAgIGRlZiBhdChpbmRleCkKICAg ICAgICBAZGF0YVtpbmRleF0KICAgIGVuZAogICAgZGVmIGVhY2goJmJsb2NrKQogICAgICAgIEBk YXRhLmVhY2hfY2hhcigmYmxvY2spCiAgICBlbmQKICAgIGRlZiB0b19zKHM9IiIpCiAgICAgICAg cy5jb25jYXQoQGRhdGEudG9fcykKICAgIGVuZAplbmQKCmNsYXNzIFNob3J0Um9wZSA8IFJvcGUK ICAgIGRlZiArKG90aGVyKQogICAgICAgIGlmIG90aGVyLmRlcHRoLnplcm8/IGFuZCBAZGVwdGg9 PTEKICAgICAgICAgICAgIyBAcmlnaHQrb3RoZXIgbWF5IGZsYXR0ZW4KICAgICAgICAgICAgQGxl ZnQgKyAoQHJpZ2h0ICsgb3RoZXIpCiAgICAgICAgZWxzZQogICAgICAgICAgICBzdXBlcgogICAg ICAgIGVuZAogICAgZW5kCiAgICBhbGlhc19tZXRob2QoOjw8LCA6KykKZW5kCgpjbGFzcyBEZW5v cm1hbFJvcGUgPCBSb3BlCiAgICBkZWYgKyhvdGhlcikKICAgICAgICBzZWxmLmNsYXNzLm5ldyhz ZWxmLCBvdGhlcikKICAgIGVuZAogICAgYWxpYXNfbWV0aG9kKDo8PCwgOispCiAgICBkZWYgbm9y bWFsaXplCiAgICAgICAgc3RhY2sgPSBbXQogICAgICAgIGxlYXZlcyB7IHxub2RlfAogICAgICAg ICAgICB3aGlsZSAhc3RhY2suZW1wdHk/IGFuZCBub2RlLmRlcHRoPT1zdGFjay5sYXN0LmRlcHRo CiAgICAgICAgICAgICAgICBub2RlID0gRGVub3JtYWxSb3BlLm5ldyhzdGFjay5wb3AsIG5vZGUp CiAgICAgICAgICAgIGVuZAogICAgICAgICAgICBzdGFjay5wdXNoKG5vZGUpCiAgICAgICAgfQog ICAgICAgIHJpZ2h0ID0gc3RhY2sucG9wCiAgICAgICAgd2hpbGUgbGVmdD1zdGFjay5wb3AKICAg ICAgICAgICAgcmlnaHQgPSBsZWZ0K3JpZ2h0CiAgICAgICAgZW5kCiAgICAgICAgcmlnaHQKICAg IGVuZAogICAgZGVmIGxlYXZlcygmYmxvY2spCiAgICAgICAgQGxlZnQubGVhdmVzKCZibG9jaykK ICAgICAgICBAcmlnaHQubGVhdmVzKCZibG9jaykKICAgIGVuZAplbmQKCmNsYXNzIERlbm9ybWFs U3RyaW5nUm9wZSA8IFN0cmluZ1JvcGUKICAgIGRlZiArKG90aGVyKQogICAgICAgIERlbm9ybWFs Um9wZS5uZXcoc2VsZiwgb3RoZXIpCiAgICBlbmQKICAgIGFsaWFzX21ldGhvZCg6PDwsIDorKQog ICAgZGVmIG5vcm1hbGl6ZQogICAgICAgIHNlbGYKICAgIGVuZAogICAgZGVmIGxlYXZlcwogICAg ICAgIHlpZWxkIHNlbGYKICAgIGVuZAplbmQKCmNsYXNzIFNob3J0U3RyaW5nUm9wZSA8IFN0cmlu Z1JvcGUKICAgIFNIT1JUID0gNjQKICAgIGRlZiArKG90aGVyKQogICAgICAgIGJhbGFuY2UgPSBv dGhlci5kZXB0aAogICAgICAgIGlmIGJhbGFuY2U+MQogICAgICAgICAgICBsZWZ0ID0gb3RoZXIu bGVmdAogICAgICAgICAgICByaWdodCA9IG90aGVyLnJpZ2h0CiAgICAgICAgICAgIGlmIGxlZnQu ZGVwdGg+cmlnaHQuZGVwdGgKICAgICAgICAgICAgICAgICMgcm90YXRlIG90aGVyIHRvIHJpZ2h0 IGJlZm9yZSByb3RhdGluZyBzZWxmK290aGVyIHRvIGxlZnQKICAgICAgICAgICAgICAgIChzZWxm ICsgbGVmdC5sZWZ0KSArIChsZWZ0LnJpZ2h0ICsgcmlnaHQpCiAgICAgICAgICAgIGVsc2UKICAg ICAgICAgICAgICAgICMgcm90YXRlIHNlbGYrb3RoZXIgdG8gbGVmdAogICAgICAgICAgICAgICAg KHNlbGYgKyBsZWZ0KSArIHJpZ2h0CiAgICAgICAgICAgIGVuZAogICAgICAgIGVsc2lmIG90aGVy Lmxlbmd0aD09MAogICAgICAgICAgICAjIG5vdGhpbmcgdG8gYXBwZW5kLCBzZWxmIHdpbGwgZG8K ICAgICAgICAgICAgc2VsZgogICAgICAgIGVsc2lmIEBkYXRhLmxlbmd0aCtvdGhlci5sZW5ndGg8 PVNIT1JUCiAgICAgICAgICAgICMganVzdCBtZXJnZSB0aGUgc3RyaW5ncyBpZiB0aGUgdG90YWwg bGVuZ3RoIGlzIHNob3J0CiAgICAgICAgICAgIHNlbGYuY2xhc3MubmV3KEBkYXRhK290aGVyLnRv X3MpCiAgICAgICAgZWxzZQogICAgICAgICAgICBTaG9ydFJvcGUubmV3KHNlbGYsIG90aGVyKQog ICAgICAgIGVuZAogICAgZW5kCmVuZAoKY2xhc3MgQXJyYXlSb3BlIDwgU3RyaW5nUm9wZQogICAg ZGVmIGVhY2goJmJsb2NrKQogICAgICAgIEBkYXRhLmVhY2goJmJsb2NrKQogICAgZW5kCmVuZAoK Y2xhc3MgSU9Sb3BlIDwgU3RyaW5nUm9wZQogICAgaW5jbHVkZSBFbnVtZXJhYmxlCiAgICBkZWYg aW5pdGlhbGl6ZShpbywgc3RhcnQ9MCwgbGVuZ3RoPShpby5zZWVrKDAsSU86OlNFRUtfRU5EKTtp by5wb3Mtc3RhcnQpKQogICAgICAgIEBpbyA9IGlvCiAgICAgICAgQHN0YXJ0ID0gc3RhcnQKICAg ICAgICBAbGVuZ3RoID0gbGVuZ3RoCiAgICBlbmQKICAgIGRlZiBsZW5ndGgKICAgICAgICBAbGVu Z3RoCiAgICBlbmQKICAgIGRlZiBzbGljZShzdGFydCwgbGVuKQogICAgICAgIHJldHVybiBzZWxm IGlmIHN0YXJ0Lnplcm8/IGFuZCBsZW49PUBsZW5ndGgKICAgICAgICAjIGp1c3QgcmVmZXJlbmNl IGEgZGlmZmVyZW50IHBhcnQgb2YgdGhlIElPCiAgICAgICAgc2VsZi5jbGFzcy5uZXcoQGlvLCBA c3RhcnQrc3RhcnQsIGxlbikKICAgIGVuZAogICAgZGVmIGF0KGluZGV4KQogICAgICAgIEBpby5w b3MgPSBAc3RhcnQraW5kZXgKICAgICAgICBAaW8uZ2V0YwogICAgZW5kCiAgICBkZWYgZWFjaAog ICAgICAgIEBpby5wb3MgPSBAc3RhcnQKICAgICAgICBAbGVuZ3RoLnRpbWVzIHsgeWllbGQgQGlv LmdldGMgfQogICAgZW5kCiAgICBkZWYgdG9fcyhzPSIiKQogICAgICAgIEBpby5wb3MgPSBAc3Rh cnQKICAgICAgICBzLmNvbmNhdChAaW8ucmVhZChAbGVuZ3RoKSkKICAgIGVuZAplbmQKCmNsYXNz IE11dGFibGVTdHJpbmdSb3BlCiAgICBpbmNsdWRlIEVudW1lcmFibGUKICAgIGRlZiBpbml0aWFs aXplKCphcmdzKQogICAgICAgIEByb3BlID0gU3RyaW5nUm9wZS5uZXcoKmFyZ3MpCiAgICBlbmQK ICAgIGRlZiByb3BlCiAgICAgICAgQHJvcGUKICAgIGVuZAogICAgZGVmIGxlbmd0aAogICAgICAg IEByb3BlLmxlbmd0aAogICAgZW5kCiAgICBkZWYgKyhvdGhlcikKICAgICAgICBzZWxmLmNsYXNz Lm5ldyhAcm9wZStvdGhlci5yb3BlKQogICAgZW5kCiAgICBkZWYgPDwob3RoZXIpCiAgICAgICAg QHJvcGUgPSBAcm9wZStvdGhlci5yb3BlCiAgICAgICAgc2VsZgogICAgZW5kCiAgICBhbGlhc19t ZXRob2QoOnB1c2gsIDo8PCkKICAgIGRlZiA+PihvdGhlcikKICAgICAgICBAcm9wZSA9IG90aGVy LnJvcGUrQHJvcGUKICAgICAgICBzZWxmCiAgICBlbmQKICAgIGFsaWFzX21ldGhvZCg6dW5zaGlm dCwgOjw8KQogICAgZGVmIHNsaWNlKHN0YXJ0LCBsZW4pCiAgICAgICAgc2VsZi5jbGFzcy5uZXco QHJvcGUuc2xpY2Uoc3RhcnQsIGxlbikpCiAgICBlbmQKICAgIGRlZiBzbGljZSEoc3RhcnQsIGxl bikKICAgICAgICBzZWxmLmNsYXNzLm5ldyhAcm9wZS5zbGljZShzdGFydCwgbGVuKSkKICAgIGVu c3VyZQogICAgICAgIHN0YXJ0MiA9IHN0YXJ0K2xlbgogICAgICAgIEByb3BlID0gQHJvcGUuc2xp Y2UoMCwgc3RhcnQpK0Byb3BlLnNsaWNlKHN0YXJ0MiwgQHJvcGUubGVuZ3RoLXN0YXJ0MikKICAg IGVuZAogICAgZGVmIGF0KGluZGV4KQogICAgICAgIEByb3BlLmF0KGluZGV4KQogICAgZW5kCiAg ICBkZWYgZGVsZXRlX2F0KGluZGV4KQogICAgICAgIEByb3BlLmF0KGluZGV4KQogICAgZW5zdXJl CiAgICAgICAgc3RhcnQyID0gaW5kZXgrMQogICAgICAgIEByb3BlID0gQHJvcGUuc2xpY2UoMCwg aW5kZXgpK0Byb3BlLnNsaWNlKHN0YXJ0MiwgQHJvcGUubGVuZ3RoLXN0YXJ0MikKICAgIGVuZAog ICAgZGVmIGluc2VydChpbmRleCwgb3RoZXIpCiAgICAgICAgQHJvcGUgPSBAcm9wZS5zbGljZSgw LCBpbmRleCkrb3RoZXIucm9wZStAcm9wZS5zbGljZShpbmRleCwgQHJvcGUubGVuZ3RoLWluZGV4 KQogICAgICAgIHNlbGYKICAgIGVuZAogICAgZGVmIHNoaWZ0KGxlbj1uaWwpCiAgICAgICAgaWYg bGVuCiAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICBzZWxmLmNsYXNzLm5ldyhAcm9w ZS5zbGljZSgwLCBsZW4pKQogICAgICAgICAgICBlbnN1cmUKICAgICAgICAgICAgICAgIEByb3Bl ID0gQHJvcGUuc2xpY2UobGVuLCBAcm9wZS5sZW5ndGgtbGVuKQogICAgICAgICAgICBlbmQKICAg ICAgICBlbHNlCiAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICBAcm9wZS5hdCgwKQog ICAgICAgICAgICBlbnN1cmUKICAgICAgICAgICAgICAgIEByb3BlID0gQHJvcGUuc2xpY2UoMSwg QHJvcGUubGVuZ3RoLTEpCiAgICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgZW5kCiAgICBk ZWYgcG9wKGxlbj1uaWwpCiAgICAgICAgaWYgbGVuCiAgICAgICAgICAgIGJlZ2luCiAgICAgICAg ICAgICAgICBzZWxmLmNsYXNzLm5ldyhAcm9wZS5zbGljZShAcm9wZS5sZW5ndGgtbGVuLCBsZW4p KQogICAgICAgICAgICBlbnN1cmUKICAgICAgICAgICAgICAgIEByb3BlID0gQHJvcGUuc2xpY2Uo MCwgQHJvcGUubGVuZ3RoLWxlbikKICAgICAgICAgICAgZW5kCiAgICAgICAgZWxzZQogICAgICAg ICAgICBiZWdpbgogICAgICAgICAgICAgICAgQHJvcGUuYXQoQHJvcGUubGVuZ3RoLTEpCiAgICAg ICAgICAgIGVuc3VyZQogICAgICAgICAgICAgICAgQHJvcGUgPSBAcm9wZS5zbGljZSgwLCBAcm9w ZS5sZW5ndGgtMSkKICAgICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICBlbmQKICAgIGRlZiBb XShzdGFydCwgKmxlbikKICAgICAgICBpZiBsZW4uZW1wdHk/CiAgICAgICAgICAgIGF0KHN0YXJ0 KQogICAgICAgIGVsc2UKICAgICAgICAgICAgc2xpY2Uoc3RhcnQsIGxlblswXSkKICAgICAgICBl bmQKICAgIGVuZAogICAgZGVmIFtdPShzdGFydCwgKmxlbikKICAgICAgICB2YWwgPSBsZW4ucG9w CiAgICAgICAgaWYgbGVuLmVtcHR5PwogICAgICAgICAgICBzdGFydDIgPSBzdGFydCsxCiAgICAg ICAgICAgIHZhbCA9IFN0cmluZ1JvcGUubmV3KCIiPDx2YWwpCiAgICAgICAgICAgIEByb3BlID0g QHJvcGUuc2xpY2UoMCwgc3RhcnQpK3ZhbCtAcm9wZS5zbGljZShzdGFydDIsIEByb3BlLmxlbmd0 aC1zdGFydDIpCiAgICAgICAgZWxzZQogICAgICAgICAgICBzdGFydDIgPSBzdGFydCtsZW4KICAg ICAgICAgICAgQHJvcGUgPSBAcm9wZS5zbGljZSgwLCBzdGFydCkrdmFsLnJvcGUrQHJvcGUuc2xp Y2Uoc3RhcnQyLCBAcm9wZS5sZW5ndGgtc3RhcnQyKQogICAgICAgIGVuZAogICAgZW5kCiAgICBk ZWYgZWFjaCgmYmxvY2spCiAgICAgICAgQHJvcGUuZWFjaCgmYmxvY2spCiAgICBlbmQKICAgIGRl ZiB0b19zKHM9IiIpCiAgICAgICAgQHJvcGUudG9fcyhzKQogICAgZW5kCmVuZAoKZW5kCgoK ------ art_28016_26962572.1188870475282--