------art_42361_32297987.1179175046637
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here's an interim solution.  I'm working on writing and reading binary
huffman encoded files.  There is code here which isn't used yet by the
demo code. I figured that the time had come to publish my approach to
building the tree, and encoding and decoding.  The current code is
more pedagogical than useful since the 'compressed' data is
represented by a string representation of the bit string.

There are three files attached.  huffman.rb is a module and some core
extensions.  huffman_demo1.rb runs the example from the quiz, dumping
the tree and various computed data.  Then 'compresses' and
'decompresses' the sample string.  huffman_wikipedia.rb is an earlier
version which uses the algorithm in the wikipedia article.

A few remarks.

I started out using the wikipedia algorithm.  Once I got that working,
I decided that it would be better to use a priority queue instead of
two separate queues. For this I used Brian Schroeder's PriorityQueue
gem.

To handle the problem of padding to a given word length, I add an
artificial 'character' to the tree with an occurrence count of 0. This
should ensure that it doesn't take a shorter encoding away from a
character which actually occurs in the input data.

In order to decode the compressed data, I use a regex which is a
simple alternation of all of the string representations of the codes,
anchored at the begining of the string.  Since the huffman encoding
algorithm ensures that no code is a prefix of any other code, this
regex can be used to find the code at the head of the input stream.

So walking through a string representation of a huffman encoded bit
stream can be done by matching this pattern against the string, the
match will be the code.  After this match, the string can be replaced
by the string remaining after the match.

Extending this to binary data will involve making an input stream
class which reads the binary data and converts it into reasonably
sized binary string representations, and an output stream which
accumulates the string representation of the codes and writes them as
binary as enough data is produced.  The huffman.rb file contains these
classes in an embrionic form.


-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

------art_42361_32297987.1179175046637
Content-Type: application/x-ruby; name=huffman_demo1.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f1pdncyy
Content-Disposition: attachment; filename="huffman_demo1.rb"

cmVxdWlyZSAnaHVmZm1hbicKCnRnID0gSHVmZm1hbjo6VHJlZUdlbmVyYXRvci5uZXcKdGcuYW5h
bHlzZSgiQUJSUktCQUFSQUEiKSAKY29kZWMgPSBIdWZmbWFuOjpDb2RlYy5uZXcodGcuZ2VuZXJh
dGVfdHJlZSkKcHV0cyBjb2RlYy5yb290LnRvX3MKcHV0cyAiY29kZV9wYXR0ZXJuID0gI3tjb2Rl
Yy5jb2RlX3BhdHRlcm4uaW5zcGVjdH0iCgplbmNvZGVkID0gY29kZWMuZW5jb2RlX3N0cmluZygi
QUJSUktCQUFSQUEiKQpwdXRzICJlbmNvZGVkID0gI3tlbmNvZGVkfSIKcHV0cyAiZGVjb2RlZCA9
ICN7Y29kZWMuZGVjb2RlX3N0cmluZyhlbmNvZGVkLCAiIil9IgoKcmVxdWlyZSAneWFtbCcKCnkg
PSBZQU1MLmR1bXAodGcuZ2VuZXJhdGVfdHJlZSkKY29kZWMgPSBIdWZmbWFuOjpDb2RlYy5uZXco
WUFNTC5sb2FkKHkpKQpwdXRzIGNvZGVjLnJvb3QudG9fcwpwdXRzICJjb2RlX3BhdHRlcm4gPSAj
e2NvZGVjLmNvZGVfcGF0dGVybi5pbnNwZWN0fSIKCmVuY29kZWQgPSBjb2RlYy5lbmNvZGVfc3Ry
aW5nKCJBQlJSS0JBQVJBQSIpCnB1dHMgImVuY29kZWQgPSAje2VuY29kZWR9IgpwdXRzICJkZWNv
ZGVkID0gI3tjb2RlYy5kZWNvZGVfc3RyaW5nKGVuY29kZWQsICIiKX0iCgoKCg------art_42361_32297987.1179175046637
Content-Type: application/x-ruby; name=huffman_wikipedia.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f1pdo3ir
Content-Disposition: attachment; filename="huffman_wikipedia.rb"

bW9kdWxlIEh1ZmZtYW4KCiAgY2xhc3MgTm9kZQoKICAgIGF0dHJfcmVhZGVyIDpzeW0sIDp3dCwg
OnBhcmVudAogICAgZGVmICsob3RoZXJfbm9kZSkKICAgICAgSW50ZXJuYWxOb2RlLm5ldyhzZWxm
LCBvdGhlcl9ub2RlKQogICAgZW5kCgogICAgZGVmIHRvX3MKICAgICAgIk5vZGUoI0BzeW0sICNA
d3QpIgogICAgZW5kCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgd3QgPD0+IG90aGVyLnd0CiAg
ICBlbmQKCiAgICBwcm90ZWN0ZWQKICAgIGF0dHJfd3JpdGVyIDpwYXJlbnQKCiAgZW5kCgogIGNs
YXNzIEludGVybmFsTm9kZSA8IE5vZGUKICAgIGF0dHJfcmVhZGVyIDpsZWZ0LCA6cmlnaHQKICAg
IGRlZiBpbml0aWFsaXplKGNoaWxkMSwgY2hpbGQyKQogICAgICBAbGVmdCwgQHJpZ2h0ID0gKihb
Y2hpbGQxLCBjaGlsZDJdLnNvcnQpCiAgICAgIGNoaWxkMS5wYXJlbnQgPSBjaGlsZDIucGFyZW50
ID0gc2VsZgogICAgICBAd3QgPSBjaGlsZDEud3QgKyBjaGlsZDIud3QKICAgICAgQHN5bSA9IEBs
ZWZ0LnN5bSArIEByaWdodC5zeW0KICAgIGVuZAoKPWJlZ2luCiAgICBkZWYgPD0+KG90aGVyX25v
ZGUpCiAgICAgIG90aGVyX25vZGUuY21wX3dpdGhfaW50ZXJuYWwoc2VsZikKICAgIGVuZAoKICAg
IGRlZiBjbXBfd2l0aF9pbnRlcm5hbChvdGhlcl9ub2RlKQogICAgICBvdGhlcl9ub2RlLnd0IDw9
PiB3dAogICAgZW5kCgogICAgZGVmIGNtcF93aXRoX2xlYWYobGVhZikKICAgICAgcmV0dXJuIDEg
aWYgbGVhZi53dCA9PSB3dAogICAgICBsZWFmLnd0IDw9PiB3dAogICAgZW5kCj1lbmQKCiAgICBk
ZWYgaW5zcGVjdAogICAgICAiTm9kZSgjQHN5bSwgI0B3dCkiCiAgICBlbmQKCiAgICBkZWYgdG9f
cwogICAgICBpbmRlbnRlZCgwKQogICAgZW5kCgogICAgZGVmIGluZGVudGVkKGluZGVudCkKICAg
ICAgIiN7KCIgICIgKiBpbmRlbnQpfSN7aW5zcGVjdH1cbiN7bGVmdC5pbmRlbnRlZChpbmRlbnQg
KyAxKX1cbiN7cmlnaHQuaW5kZW50ZWQoaW5kZW50ICsgMSl9IgogICAgZW5kCgogICAgZGVmIGNv
bXB1dGVfaGFzaGVzKGVuY29kZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aD0iIikKICAgICAgbGVm
dC5jb21wdXRlX2hhc2hlcyhlbmNvZGVfaGFzaCwgZGVjb2RlX2hhc2gsIHBhdGggKyAiMCIpCiAg
ICAgIHJpZ2h0LmNvbXB1dGVfaGFzaGVzKGVuY29kZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aCAr
ICIxIikKICAgIGVuZAoKICBlbmQKCiAgY2xhc3MgTGVhZk5vZGUgPCBOb2RlCgogICAgZGVmIGlu
aXRpYWxpemUoc3ltLHd0KQogICAgICBAc3ltLCBAd3QgPSBzeW0sIHd0CiAgICBlbmQKCiAgICBk
ZWYgaW5kZW50ZWQoaW5kZW50KQogICAgICAiI3soIiAgIiAqIGluZGVudCl9I3tpbnNwZWN0fSIK
ICAgIGVuZAoKICAgIGRlZiBpbnNwZWN0CiAgICAgIHRvX3MKICAgIGVuZAoKICAgIGRlZiBjb21w
dXRlX2hhc2hlcyhlbmNvZGVfaGFzaCwgZGVjb2RlX2hhc2gsIHBhdGg9IjAiKQogICAgICBlbmNv
ZGVfaGFzaFtzeW1dID0gcGF0aAogICAgICBkZWNvZGVfaGFzaFtwYXRoXSA9IHN5bQogICAgZW5k
Cgo9YmVnaW4KICAgIGRlZiA8PT4ob3RoZXJfbm9kZSkKICAgICAgb3RoZXJfbm9kZS5jbXBfd2l0
aF9sZWFmKHNlbGYpCiAgICBlbmQKCiAgICBkZWYgY21wX3dpdGhfaW50ZXJuYWwob3RoZXJfbm9k
ZSkKICAgICAgcmV0dXJuIDEgaWYgb3RoZXJfbm9kZS53dCA9PSB3dAogICAgICBvdGhlcl9ub2Rl
Lnd0IDw9PiB3dAogICAgZW5kCgogICAgZGVmIGNtcF93aXRoX2xlYWYobGVhZikKICAgICAgd3Qg
PD0+IGxlYWYud3QKICAgIGVuZAo9ZW5kCgogIGVuZAoKICBtb2R1bGUgQ29tcGFyYWJsZVF1ZXVl
CgogICAgaW5jbHVkZSBDb21wYXJhYmxlCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgZW1wdHk/
ID8gMSA6IG90aGVyLnd0X2NtcChmaXJzdC53dCkKICAgIGVuZAoKICAgIGRlZiB3dF9jbXAob3Ro
ZXJfd3QpCiAgICAgIGVtcHR5PyA/IC0xIDogb3RoZXJfd3QgPD0+IGZpcnN0Lnd0CiAgICBlbmQK
ICBlbmQKCiAgY2xhc3MgVHJlZUdlbmVyYXRvcgoKICAgIHByaXZhdGUKICAgIGF0dHJfYWNjZXNz
b3IgOmhpc3RvZ3JhbQoKICAgIGRlZiBoaXN0b2dyYW0KICAgICAgQGhpc3RvZ3JhbSB8fD0gSGFz
aC5uZXcge3xoLGt8IGhba10gPSAwfQogICAgZW5kCgogICAgZGVmIHNvcnRlZF9wYWlycwogICAg
ICBoaXN0b2dyYW0udG9fYS5zb3J0X2J5IHt8YXwgYS5sYXN0fQogICAgZW5kCgogICAgcHVibGlj
CiAgICBkZWYgYW5hbHlzZShzdHIpCiAgICAgIEByb290ID0gQHNvcnRlZCA9IEBlbmNvZGVfaGFz
aCA9IEBkZWNvZGVfaGFzaCA9IEBjb2RlX3BhdHRlcm4gPSBuaWwKICAgICAgc3RyLnNjYW4oLy4v
KS5lYWNoIHsgfCBjaGFyIHxoaXN0b2dyYW1bY2hhcl0gKz0gMX0KICAgIGVuZAoKICAgIGRlZiBz
b3J0ZWRfbm9kZXMKICAgICAgQHNvcnRlZCB8fD0gc29ydGVkX3BhaXJzCiAgICAgIEBzb3J0ZWQu
aW5qZWN0KFtdKSB7fG5vZGVzLCBwYWlyfCBub2RlcyA8PCBMZWFmTm9kZS5uZXcoKnBhaXIpfQog
ICAgZW5kCgogICAgZGVmIGxvd2VzdChxMSwgcTIpCiAgICAgIHExIDwgcTIgPyBxMS5zaGlmdCA6
IHEyLnNoaWZ0CiAgICBlbmQKCiAgICBkZWYgZ2VuZXJhdGVfdHJlZQogICAgICBxMSxxMiA9IHNv
cnRlZF9ub2RlcywgW10KICAgICAgcTEuZXh0ZW5kKENvbXBhcmFibGVRdWV1ZSkKICAgICAgcTIu
ZXh0ZW5kKENvbXBhcmFibGVRdWV1ZSkKICAgICAgd2hpbGUgKHExLnNpemUgKyBxMi5zaXplKSA+
IDEKCXEyIDw8IEludGVybmFsTm9kZS5uZXcobG93ZXN0KHExLHEyKSwgbG93ZXN0KHExLHEyKSkK
ICAgICAgZW5kCiAgICAgIChxMStxMikuZmlyc3QKICAgIGVuZAoKICAgIGRlZiByb290CiAgICAg
IEByb290IHx8PSBnZW5lcmF0ZV90cmVlCiAgICBlbmQKCiAgICBkZWYgY29tcHV0ZV9oYXNoZXMK
ICAgICAgQHJvb3QgfHw9IGdlbmVyYXRlX3RyZWUKICAgICAgQGVuY29kZV9oYXNoID0ge30KICAg
ICAgQGRlY29kZV9oYXNoID0ge30KICAgICAgQHJvb3QuY29tcHV0ZV9oYXNoZXMoQGVuY29kZV9o
YXNoLCBAZGVjb2RlX2hhc2gpCiAgICBlbmQKCiAgICBkZWYgZW5jb2RlX2hhc2gKICAgICAgY29t
cHV0ZV9oYXNoZXMgdW5sZXNzIEBlbmNvZGVfaGFzaAogICAgICBAZW5jb2RlX2hhc2gKICAgIGVu
ZAoKICAgIGRlZiBkZWNvZGVfaGFzaAogICAgICBjb21wdXRlX2hhc2hlcyB1bmxlc3MgQGRlY29k
ZV9oYXNoCiAgICAgIEBkZWNvZGVfaGFzaAogICAgZW5kCgogICAgZGVmIGNvZGVfcGF0dGVybgog
ICAgICBAY29kZV9wYXR0ZXJuIHx8PSAlcnteKCN7ZGVjb2RlX2hhc2gua2V5cy5qb2luKCd8Jyl9
KX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGUoc3RyKQogICAgICBzdHIuc3BsaXQoLy8pLmluamVj
dCgiIikge3xyZXN1bHQsIGNofCByZXN1bHQgPDwgZW5jb2RlX2hhc2hbY2hdfQogICAgZW5kCgog
ICAgZGVmIGRlY29kZShzdHIpCiAgICAgIHRtcCA9IHN0ci5kdXAKICAgICAgcmVzdWx0ID0gIiIK
ICAgICAgcGF0ID0gY29kZV9wYXR0ZXJuCiAgICAgIHB1dHMgInBhdCBpcyAje3BhdH0iCiAgICAg
IHVudGlsIHRtcC5lbXB0eT8KCW1hdGNoID0gdG1wLm1hdGNoKHBhdCkKCXJlc3VsdCA8PCBkZWNv
ZGVfaGFzaFttYXRjaFsxXV0KCXRtcCA9IG1hdGNoLnBvc3RfbWF0Y2gKICAgICAgZW5kCiAgICAg
IHJlc3VsdAogICAgZW5kCiAgZW5kCmVuZAoKdGcgPSBIdWZmbWFuOjpUcmVlR2VuZXJhdG9yLm5l
dwp0Zy5hbmFseXNlKCJBQlJSS0JBQVJBQSIpIApyb290ID0gdGcuZ2VuZXJhdGVfdHJlZQpwdXRz
IHJvb3QudG9fcwpwdXRzICJlbmNvZGVfaGFzaCA9ICN7dGcuZW5jb2RlX2hhc2guaW5zcGVjdH0i
CnB1dHMgImRlY29kZV9oYXNoID0gI3t0Zy5kZWNvZGVfaGFzaC5pbnNwZWN0fSIKcHV0cyAiY29k
ZV9wYXR0ZXJuID0gI3t0Zy5jb2RlX3BhdHRlcm4uaW5zcGVjdH0iCgplbmNvZGVkID0gdGcuZW5j
b2RlKCJBQlJSS0JBQVJBQSIpCnB1dHMgImVuY29kZWQgPSAje2VuY29kZWR9IgpwdXRzICJkZWNv
ZGVkID0gI3t0Zy5kZWNvZGUoZW5jb2RlZCl9Igo------art_42361_32297987.1179175046637
Content-Type: application/x-ruby; name=huffman.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f1pec081
Content-Disposition: attachment; filename="huffman.rb"

IyEvdXNyL21hdGgvYmluL3J1YnkKCgptb2R1bGUgSHVmZm1hbgoKICByZXF1aXJlICdydWJ5Z2Vt
cycKICByZXF1aXJlICdwcmlvcml0eV9xdWV1ZScKICByZXF1aXJlICdzdHJpbmdpbycKCiAgRW5k
U3ltYm9sID0gIkVORCIKCiAgY2xhc3MgTm9kZQoKICAgIGF0dHJfcmVhZGVyIDpzeW0sIDp3dCwg
OnBhcmVudAogICAgZGVmICsob3RoZXJfbm9kZSkKICAgICAgSW50ZXJuYWxOb2RlLm5ldyhzZWxm
LCBvdGhlcl9ub2RlKQogICAgZW5kCgogICAgZGVmIHRvX3MKICAgICAgIk5vZGUoI0BzeW0sICNA
d3QpIgogICAgZW5kCgogICAgZGVmIDw9PihvdGhlcikKICAgICAgd3QgPD0+IG90aGVyLnd0CiAg
ICBlbmQKCiAgICBwcm90ZWN0ZWQKICAgIGF0dHJfd3JpdGVyIDpwYXJlbnQKCiAgZW5kCgogIGNs
YXNzIEludGVybmFsTm9kZSA8IE5vZGUKICAgIGF0dHJfcmVhZGVyIDpsZWZ0LCA6cmlnaHQKICAg
IGRlZiBpbml0aWFsaXplKGNoaWxkMSwgY2hpbGQyKQogICAgICBAbGVmdCwgQHJpZ2h0ID0gKihb
Y2hpbGQxLCBjaGlsZDJdLnNvcnQpCiAgICAgIGNoaWxkMS5wYXJlbnQgPSBjaGlsZDIucGFyZW50
ID0gc2VsZgogICAgICBAd3QgPSBjaGlsZDEud3QgKyBjaGlsZDIud3QKICAgICAgQHN5bSA9IEBs
ZWZ0LnN5bSArIEByaWdodC5zeW0KICAgIGVuZAoKICAgIGRlZiBpbnNwZWN0CiAgICAgICJOb2Rl
KCNAc3ltLCAjQHd0KSIKICAgIGVuZAoKICAgIGRlZiB0b19zCiAgICAgIGluZGVudGVkKDApCiAg
ICBlbmQKCiAgICBkZWYgaW5kZW50ZWQoaW5kZW50KQogICAgICAiI3soIiAgIiAqIGluZGVudCl9
I3tpbnNwZWN0fVxuI3tsZWZ0LmluZGVudGVkKGluZGVudCArIDEpfVxuI3tyaWdodC5pbmRlbnRl
ZChpbmRlbnQgKyAxKX0iCiAgICBlbmQKCiAgICBkZWYgY29tcHV0ZV9oYXNoZXMoZW5jb2RlX2hh
c2gsIGRlY29kZV9oYXNoLCBwYXRoPSIiKQogICAgICBsZWZ0LmNvbXB1dGVfaGFzaGVzKGVuY29k
ZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aCArICIwIikKICAgICAgcmlnaHQuY29tcHV0ZV9oYXNo
ZXMoZW5jb2RlX2hhc2gsIGRlY29kZV9oYXNoLCBwYXRoICsgIjEiKQogICAgZW5kCgogICAgZGVm
IGRlcHRoCiAgICAgIDEgKyBbbGVmdC5kZXB0aCwgcmlnaHQuZGVwdGhdLm1heAogICAgZW5kCgog
IGVuZAoKICBjbGFzcyBMZWFmTm9kZSA8IE5vZGUKCiAgICBkZWYgaW5pdGlhbGl6ZShzeW0sd3Qp
CiAgICAgIEBzeW0sIEB3dCA9IHN5bSwgd3QKICAgIGVuZAoKICAgIGRlZiBpbmRlbnRlZChpbmRl
bnQpCiAgICAgICIjeygiICAiICogaW5kZW50KX0je2luc3BlY3R9IgogICAgZW5kCgogICAgZGVm
IGluc3BlY3QKICAgICAgdG9fcwogICAgZW5kCgogICAgZGVmIGNvbXB1dGVfaGFzaGVzKGVuY29k
ZV9oYXNoLCBkZWNvZGVfaGFzaCwgcGF0aD0iMCIpCiAgICAgIGVuY29kZV9oYXNoW3N5bV0gPSBw
YXRoCiAgICAgIGRlY29kZV9oYXNoW3BhdGhdID0gc3ltCiAgICBlbmQKCiAgICBkZWYgZGVwdGgK
ICAgICAgMQogICAgZW5kCgogIGVuZAoKICBjbGFzcyBOb2RlUXVldWUKICAgIGRlZiBpbml0aWFs
aXplCiAgICAgIEBxID0gQ1ByaW9yaXR5UXVldWUubmV3CiAgICBlbmQKCiAgICBkZWYgPDwobm9k
ZSkKICAgICAgcVtub2RlXSA9IG5vZGUud3QKICAgIGVuZAoKICAgIGRlZiBuZXh0CiAgICAgIHEu
ZGVsZXRlX21pbl9yZXR1cm5fa2V5CiAgICBlbmQKCiAgICBkZWYgc2l6ZQogICAgICBxLmxlbmd0
aAogICAgZW5kCgogICAgZGVmIGZpcnN0CiAgICAgIHEubWluX2tleQogICAgZW5kCgogICAgcHJp
dmF0ZQogICAgYXR0cl9yZWFkZXIgOnEKCiAgZW5kCgogIGNsYXNzIElucHV0U3RyZWFtCiAgICBk
ZWYgaW5pdGlhbGl6ZShwYXR0ZXJuLCBsZW5ndGgsIHNlbnRpbmVsKQogICAgICBAcGF0LCBAbGVu
LCBAc2VudGluZWwgPSBwYXR0ZXJuLCBsZW5ndGgsIHNlbnRpbmVsCiAgICBlbmQKCiAgICBkZWYg
ZW9mPwogICAgICBjaHVuay5tYXRjaChwYXQpWzFdID09IHNlbnRpbmVsCiAgICBlbmQKCiAgICBk
ZWYgbmV4dAogICAgICBtYXRjaCA9IGNodW5rLm1hdGNoKHBhdCkKICAgICAgc2VsZi5jaHVuayA9
IG1hdGNoLnBvc3RfbWF0Y2gKICAgICAgbWF0Y2hbMV0KICAgIGVuZAoKICAgIHByb3RlY3RlZAog
ICAgYXR0cl9hY2Nlc3NvciA6Y2h1bmssIDpwYXQsIDpzZW50aW5lbAogIGVuZAogIGNsYXNzIEVu
Y29kZXJPdXRwdXRTdHJlYW0KCiAgICBkZWYgaW5pdGlhbGl6ZShzZW50aW5lbCkKICAgICAgQHNl
bnRpbmVsID0gc2VudGluZWwKICAgICAgQGJ1ZmZlciA9ICIiCiAgICBlbmQKCiAgICBwcm90ZWN0
ZWQgCiAgICBhdHRyX3JlYWRlciA6c2VudGluZWwKICAgIGF0dHJfYWNjZXNzb3IgOmJ1ZmZlcgog
IGVuZAogIGNsYXNzIEZpbGVPdXRwdXRTdHJlYW0gPCBFbmNvZGVyT3V0cHV0U3RyZWFtCgogICAg
ZGVmIGluaXRpYWxpemUoZmlsZSwgc2VudGluZWwpCiAgICAgIHN1cGVyKHNlbnRpbmVsKQogICAg
ICBzZWxmLmZpbGUgPSBmaWxlCiAgICBlbmQKCiAgICBkZWYgc2VsZi5vcGVuKGZpbGVfbmFtZSwg
c2VudGluZWwsICZibG9jaykKICAgICAgRmlsZS5vcGVuKGZpbGVfbmFtZSwgInciKSBkbyB8Zmls
ZXwKCWZvcyA9IG5ldyhmaWxlLCBzZW50aW5lbCkKCWJlZ2luCgkgIGJsb2NrLmNhbGwoZm9zKQoJ
ZW5zdXJlCgkgIGZvcy5mbHVzaAoJZW5kCiAgICAgIGVuZAogICAgZW5kCgogICAgZGVmIDw8KHN0
cikKICAgICAgYnVmZmVyIDw8IHN0cgogICAgICB3cml0ZV9idWZmZXIKICAgIGVuZAoKICAgIGRl
ZiBmbHVzaAogICAgICB3cml0ZV9idWZmZXIKICAgICAgdW5sZXNzIEBidWZmZXIuZW1wdHk/Cgli
dWZmZXIgPDwgc2VudGluZWwgPDwgIjAiKjgKCXdyaXRlX2J1ZmZlcgogICAgICBlbmQKICAgIGVu
ZAoKICAgIHByaXZhdGUKICAgIGRlZiB3cml0ZV9idWZmZXIKICAgICAgd2hpbGUgc2VsZi5idWZm
ZXIubGVuZ3RoID49IDgKCXNlbGYuZmlsZSA8PCBzZWxmLmJ1ZmZlclswLi43XS50b19pCglzZWxm
LmJ1ZmZlciA9IHNlbGYuYnVmZmVyWzguLi0xXQogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICBj
bGFzcyBTdHJpbmdJbnB1dCA8IElucHV0U3RyZWFtCiAgICBkZWYgaW5pdGlhbGl6ZShzdHJpbmcs
IHBhdHRlcm4sIGxlbmd0aCwgZW5kX3NlbnRpbmVsKQogICAgICBAY2h1bmsgPSBzdHJpbmcKICAg
ICAgc3VwZXIocGF0dGVybiwgbGVuZ3RoLCBlbmRfc2VudGluZWwpCiAgICBlbmQKICBlbmQKCgog
IGNsYXNzIFRyZWVHZW5lcmF0b3IKCiAgICBwcml2YXRlCiAgICBhdHRyX2FjY2Vzc29yIDpoaXN0
b2dyYW0KCiAgICBkZWYgaGlzdG9ncmFtCiAgICAgIEBoaXN0b2dyYW0gfHw9IEhhc2gubmV3IHt8
aCxrfCBoW2tdID0gMH0KICAgIGVuZAoKICAgIGRlZiBpbml0aWFsX3F1ZXVlCiAgICAgIHEgPSBO
b2RlUXVldWUubmV3CiAgICAgIHEgPDwgTGVhZk5vZGUubmV3KEVuZFN5bWJvbCwwKSAjIFNwZWNp
YWwgZW5kIHN5bWJvbAogICAgICBoaXN0b2dyYW0udG9fYS5lYWNoIGRvIHxzeW1fd3R8CglxIDw8
IExlYWZOb2RlLm5ldygqc3ltX3d0KQogICAgICBlbmQKICAgICAgcQogICAgZW5kCgogICAgcHVi
bGljCiAgICBkZWYgYW5hbHlzZShzdHIpCiAgICAgIEByb290ID0gQGVuY29kZV9oYXNoID0gQGRl
Y29kZV9oYXNoID0gQGNvZGVfcGF0dGVybiA9IG5pbAogICAgICBzdHIuc2NhbigvLi8pLmVhY2gg
eyB8IGNoYXIgfGhpc3RvZ3JhbVtjaGFyXSArPSAxfQogICAgZW5kCgoKICAgIGRlZiBnZW5lcmF0
ZV90cmVlCiAgICAgIHF1ZXVlID0gaW5pdGlhbF9xdWV1ZQogICAgICB3aGlsZSAocXVldWUuc2l6
ZSkgPiAxCglxdWV1ZSA8PCBJbnRlcm5hbE5vZGUubmV3KHF1ZXVlLm5leHQsIHF1ZXVlLm5leHQp
CiAgICAgIGVuZAogICAgICBxdWV1ZS5maXJzdAogICAgZW5kCgogIGVuZAoKICBjbGFzcyBDb2Rl
YwoKICAgIGF0dHJfcmVhZGVyIDpyb290CgoKICAgIGRlZiBpbml0aWFsaXplKHRyZWUpCiAgICAg
IEByb290ID0gdHJlZQogICAgZW5kCgogICAgZGVmIGNvbXB1dGVfaGFzaGVzCiAgICAgIEBlbmNv
ZGVfaGFzaCA9IHt9CiAgICAgIEBkZWNvZGVfaGFzaCA9IHt9CiAgICAgIHJvb3QuY29tcHV0ZV9o
YXNoZXMoQGVuY29kZV9oYXNoLCBAZGVjb2RlX2hhc2gpCiAgICBlbmQKCiAgICBkZWYgZW5jb2Rl
X2hhc2gKICAgICAgY29tcHV0ZV9oYXNoZXMgdW5sZXNzIEBlbmNvZGVfaGFzaAogICAgICBAZW5j
b2RlX2hhc2gKICAgIGVuZAoKICAgIGRlZiBkZWNvZGVfaGFzaAogICAgICBjb21wdXRlX2hhc2hl
cyB1bmxlc3MgQGRlY29kZV9oYXNoCiAgICAgIEBkZWNvZGVfaGFzaAogICAgZW5kCgogICAgZGVm
IGNvZGVfcGF0dGVybgogICAgICBAY29kZV9wYXR0ZXJuIHx8PSAlcnteKCN7ZGVjb2RlX2hhc2gu
a2V5cy5qb2luKCd8Jyl9KX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGVfc3RyaW5nKHN0cikKICAg
ICAgKHN0ci5zcGxpdCgvLykgPDwgRW5kU3ltYm9sKS5pbmplY3QoIiIpIHt8cmVzdWx0LCBjaHwg
cmVzdWx0IDw8IGVuY29kZV9oYXNoW2NoXX0KICAgIGVuZAoKICAgIGRlZiBlbmNvZGUoaW5wdXQs
IG91dHB1dCkKICAgICAgaW5wdXQuZWFjaF9ieXRlIHt8Ynl0ZXwgb3V0cHV0IDw8IGVuY29kZV9o
YXNoW2J5dGUuY2hyXX0KICAgIGVuZAoKICAgIGRlZiBkZWNvZGUoaW5wdXQsIG91dHB1dCkKICAg
ICAgb3V0cHV0IDw8IGRlY29kZV9oYXNoW2lucHV0Lm5leHRdIHVudGlsIGlucHV0LmVvZj8KICAg
IGVuZAoKICAgIGRlZiBkZWNvZGVfc3RyaW5nKHNvdXJjZSwgc2luaz0iIikKICAgICAgaW5wdXQg
PSBzb3VyY2UuaHVmZm1hbl9kZWNvZGVyX2lucHV0X3N0cmVhbShjb2RlX3BhdHRlcm4sIHJvb3Qu
ZGVwdGgsIGVuY29kZV9oYXNoW0VuZFN5bWJvbF0pCiAgICAgIG91dHB1dCA9IHNpbmsuaHVmZm1h
bl9kZWNvZGVyX291dHB1dF9zdHJlYW0KICAgICAgZGVjb2RlKGlucHV0LCBvdXRwdXQpCiAgICAg
IG91dHB1dC5zdHJpbmcKICAgIGVuZAogIGVuZAplbmQKCmNsYXNzIFN0cmluZwogIGRlZiBodWZm
bWFuX2RlY29kZXJfaW5wdXRfc3RyZWFtKHBhdCwgbGVuZ3RoLCBlbmRfc2VudGluZWwpCiAgICBI
dWZmbWFuOjpTdHJpbmdJbnB1dC5uZXcoc2VsZiwgcGF0LCBsZW5ndGgsIGVuZF9zZW50aW5lbCkK
ICBlbmQKCiAgZGVmIGh1ZmZtYW5fZGVjb2Rlcl9vdXRwdXRfc3RyZWFtCiAgICBTdHJpbmdJTy5u
ZXcoc2VsZikKICBlbmQKCmVuZAoK
------art_42361_32297987.1179175046637--