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