From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 93D9EBBC1 for ; Fri, 7 Mar 2008 18:13:40 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AiQBADAG0UfAXQInh2dsb2JhbACQeAEBAQgKKYENmXk X-IronPort-AV: E=Sophos;i="4.25,463,1199660400"; d="ml'?scan'208";a="23494928" Received: from concorde.inria.fr ([192.93.2.39]) by mail4-smtp-sop.national.inria.fr with ESMTP; 07 Mar 2008 18:13:40 +0100 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m27HDdQN009919 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Fri, 7 Mar 2008 18:13:39 +0100 X-IronPort-AV: E=Sophos;i="4.25,463,1199660400"; d="ml'?scan'208";a="23494926" Received: from unknown (HELO mga02.intel.com) ([134.134.136.20]) by mail4-smtp-sop.national.inria.fr with ESMTP; 07 Mar 2008 18:13:38 +0100 Received: from orsmga002.jf.intel.com ([10.7.209.21]) by orsmga101.jf.intel.com with ESMTP; 07 Mar 2008 09:13:33 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.25,463,1199692800"; d="ml'?scan'208";a="261372019" Received: from unknown (HELO azsmsx602.amr.corp.intel.com) ([10.2.163.6]) by orsmga002.jf.intel.com with ESMTP; 07 Mar 2008 09:13:32 -0800 Received: from azsmsx501.amr.corp.intel.com ([10.2.167.99]) by azsmsx602.amr.corp.intel.com ([10.2.163.6]) with mapi; Fri, 7 Mar 2008 10:13:32 -0700 From: "Harrison, John R" To: Berke Durak Cc: Caml-list List Date: Fri, 7 Mar 2008 10:13:32 -0700 Subject: RE: [Caml-list] Canonical Set/Map datastructure? Thread-Topic: [Caml-list] Canonical Set/Map datastructure? Thread-Index: AciAO1J8eLa069K6RCGvKgQstQz+KwAOvo8g Message-ID: References: <47CECF23.1020508@exalead.com> <47CFBF04.9030703@exalead.com> <47D11442.6090409@exalead.com> In-Reply-To: <47D11442.6090409@exalead.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: yes X-MS-TNEF-Correlator: acceptlanguage: en-US Content-Type: multipart/mixed; boundary="_002_DCC19446A892D84FBB89AE7C94F0C04E01D99539DCazsmsx501amrc_" MIME-Version: 1.0 X-Miltered: at concorde with ID 47D177C3.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; berke:01 hash:01 worst-case:01 hash:01 hashtbl:01 proble:01 worst-case:01 bounded:01 nodes:01 pervasives:01 pet:98 correlated:98 cubic:98 striking:98 graph:01 X-Attachments: type="application/octet-stream" name="map.ml" name="map.ml" --_002_DCC19446A892D84FBB89AE7C94F0C04E01D99539DCazsmsx501amrc_ Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Hi Berke, | Thanks for your code. I'm sorry I thought you maintained a separate | hash table. It's very interesting code and I'll give it a try. It would in fact have been more efficient to use Jean-Christophe Filliatre's implementation of Patricia trees instead of writing my own. However, it was important to me to release the code under a BSD-like license. For what it's worth, I attach a version of my code that's extracted from its context so it can be used independently. (I replaced a few of my pet functions with standard library ones, and I hope I didn't screw anything up in the process.) | - The theoretical worst-case performance of hash-based data structures | can be attained if the hash function has bad dispersal. As the code | relies on Hashtbl.hash, which does not hash deeply, this could | potentially be a proble, in particular if your keys have long "common | prefixes" that are not distinguished by the hash function. It might | work well in practice but I feel a little uncomfortable. Yes, sure. My applications are mainly in theorem proving and symbolic computation where this isn't an issue, and I can imagine it might not be suitable elsewhere. | - Also, it does not preserve the natural order for keys, and that | is particularly bad, because I often use, for instance, | float-indexed maps or sets as a substitute for heaps. When I was looking at this area last time (maybe just following the references from the paper I cited) I came across a kind of mixed heap/tree structure with distinct "horizontal" and "vertical" orderings. That might be something to consider. But once again there is a bad worst-case performance if the two orders happen to be correlated. | The paper with the inverse cubic lower bound is *very* interesting; we | don't see plausible lower bounds often in complexity theory, | especially with such large assumptions (just bounded out-degree for | the graph nodes). | | So it seems there is little hope to have a drop-in replacement for Set | or Map that is compatible with the natural order of things, a.k.a., | Pervasives.compare. Yes, I really found it striking that in a fundamental sense, you need to pay the price of noncanonicality in order to get the guaranteed O(log n) lookup. John. --_002_DCC19446A892D84FBB89AE7C94F0C04E01D99539DCazsmsx501amrc_ Content-Type: application/octet-stream; name="map.ml" Content-Description: map.ml Content-Disposition: attachment; filename="map.ml"; size=10766; creation-date="Wed, 05 Mar 2008 10:18:10 GMT"; modification-date="Fri, 07 Mar 2008 09:58:40 GMT" Content-Transfer-Encoding: base64 KCogLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLSAqKQooKiBQb2x5bW9ycGhpYyBmaW5pdGUgcGFydGlhbCBmdW5j dGlvbnMgdmlhIFBhdHJpY2lhIHRyZWVzLiAgICAgICAgICAgICAgICAgICopCigqICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgKikKKCogVGhlIHBvaW50IG9mIHRoaXMgc3RyYW5nZSByZXByZXNlbnRhdGlvbiBp cyB0aGF0IGl0IGlzIGNhbm9uaWNhbCAoZXF1YWwgICAqKQooKiBmdW5jdGlvbnMgaGF2ZSB0aGUg c2FtZSBlbmNvZGluZykgeWV0IHJlYXNvbmFibHkgZWZmaWNpZW50IG9uIGF2ZXJhZ2UuICAgICop CigqICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgKikKKCogICAgICAgICAgICAgICAgICAoYykgSm9obiBIYXJy aXNvbiAyMDAzLiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQooKiAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICopCigqICAgIFNlZSBodHRwOi8vd3d3LmNsLmNhbS5hYy51ay9+anJoMTMvYXRw L09DYW1sL0xJQ0VOU0UudHh0ICAgICAgICAgICAgICAgKikKKCogICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAq KQooKiBJZGVhIGR1ZSB0byBEaWVnbyBPbGl2aWVyIEZlcm5hbmRleiBQb25zIChPQ2FtbCBsaXN0 LCAyMDAzLzExLzEwKS4gICAgICAgICopCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKCnR5cGUgKCdh LCdiKWZ1bmMgPQogICBFbXB0eQogfCBMZWFmIG9mIGludCAqICgnYSonYilsaXN0CiB8IEJyYW5j aCBvZiBpbnQgKiBpbnQgKiAoJ2EsJ2IpZnVuYyAqICgnYSwnYilmdW5jOzsKCigqIC0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0gKikKKCogVW5kZWZpbmVkIGZ1bmN0aW9uLiAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQooKiAtLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tICop CgpsZXQgdW5kZWZpbmVkID0gRW1wdHk7OwoKKCogLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAqKQooKiBJbiBj YXNlIG9mIGVxdWFsaXR5IGNvbXBhcmlzb24gd29ycmllcywgYmV0dGVyIHVzZSB0aGlzLiAgICAg ICAgICAgICAgICAgICopCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKCmxldCBpc191bmRlZmluZWQg ZiA9CiAgbWF0Y2ggZiB3aXRoCiAgICBFbXB0eSAtPiB0cnVlCiAgfCBfIC0+IGZhbHNlOzsKCigq IC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0gKikKKCogT3BlcmF0aW9uIGFuYWxvZ291cyB0byAibWFwIiBmb3Ig bGlzdHMuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQooKiAtLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tICopCgpsZXQgbWFwZiA9CiAgbGV0IHJlYyBtYXBfbGlzdCBmIGwgPQogICAgbWF0Y2gg bCB3aXRoCiAgICAgIFtdIC0+IFtdCiAgICB8ICh4LHkpOjp0IC0+ICh4LGYoeSkpOjoobWFwX2xp c3QgZiB0KSBpbgogIGxldCByZWMgbWFwZiBmIHQgPQogICAgbWF0Y2ggdCB3aXRoCiAgICAgIEVt cHR5IC0+IEVtcHR5CiAgICB8IExlYWYoaCxsKSAtPiBMZWFmKGgsbWFwX2xpc3QgZiBsKQogICAg fCBCcmFuY2gocCxiLGwscikgLT4gQnJhbmNoKHAsYixtYXBmIGYgbCxtYXBmIGYgcikgaW4KICBt YXBmOzsKCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKKCogT3BlcmF0aW9ucyBhbmFsb2dvdXMgdG8g ImZvbGQiIGZvciBsaXN0cy4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQooKiAt LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tICopCgpsZXQgZm9sZGwgPQogIGxldCByZWMgZm9sZGxfbGlzdCBmIGEg bCA9CiAgICBtYXRjaCBsIHdpdGgKICAgICAgW10gLT4gYQogICAgfCAoeCx5KTo6dCAtPiBmb2xk bF9saXN0IGYgKGYgYSB4IHkpIHQgaW4KICBsZXQgcmVjIGZvbGRsIGYgYSB0ID0KICAgIG1hdGNo IHQgd2l0aAogICAgICBFbXB0eSAtPiBhCiAgICB8IExlYWYoaCxsKSAtPiBmb2xkbF9saXN0IGYg YSBsCiAgICB8IEJyYW5jaChwLGIsbCxyKSAtPiBmb2xkbCBmIChmb2xkbCBmIGEgbCkgciBpbgog IGZvbGRsOzsKCmxldCBmb2xkciA9CiAgbGV0IHJlYyBmb2xkcl9saXN0IGYgbCBhID0KICAgIG1h dGNoIGwgd2l0aAogICAgICBbXSAtPiBhCiAgICB8ICh4LHkpOjp0IC0+IGYgeCB5IChmb2xkcl9s aXN0IGYgdCBhKSBpbgogIGxldCByZWMgZm9sZHIgZiB0IGEgPQogICAgbWF0Y2ggdCB3aXRoCiAg ICAgIEVtcHR5IC0+IGEKICAgIHwgTGVhZihoLGwpIC0+IGZvbGRyX2xpc3QgZiBsIGEKICAgIHwg QnJhbmNoKHAsYixsLHIpIC0+IGZvbGRyIGYgbCAoZm9sZHIgZiByIGEpIGluCiAgZm9sZHI7OwoK KCogLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLSAqKQooKiBBcHBsaWNhdGlvbi4gICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICopCigqIC0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0gKikKCmxldCBhcHBseWQgPQogIGxldCByZWMgYXBwbHlfbGlzdGQgbCBkIHggPQog ICAgbWF0Y2ggbCB3aXRoCiAgICAgIChhLGIpOjp0IC0+IGxldCBjID0gUGVydmFzaXZlcy5jb21w YXJlIHggYSBpbgogICAgICAgICAgICAgICAgICBpZiBjID0gMCB0aGVuIGIgZWxzZSBpZiBjID4g MCB0aGVuIGFwcGx5X2xpc3RkIHQgZCB4IGVsc2UgZCB4CiAgICB8IFtdIC0+IGQgeCBpbgogIGZ1 biBmIGQgeCAtPgogICAgbGV0IGsgPSBIYXNodGJsLmhhc2ggeCBpbgogICAgbGV0IHJlYyBsb29r IHQgPQogICAgICBtYXRjaCB0IHdpdGgKICAgICAgICBMZWFmKGgsbCkgd2hlbiBoID0gayAtPiBh cHBseV9saXN0ZCBsIGQgeAogICAgICB8IEJyYW5jaChwLGIsbCxyKSB3aGVuIChrIGx4b3IgcCkg bGFuZCAoYiAtIDEpID0gMAogICAgICAgICAgICAgICAgLT4gbG9vayAoaWYgayBsYW5kIGIgPSAw IHRoZW4gbCBlbHNlIHIpCiAgICAgIHwgXyAtPiBkIHggaW4KICAgIGxvb2sgZjs7CgpsZXQgYXBw bHkgZiA9IGFwcGx5ZCBmIChmdW4geCAtPiBmYWlsd2l0aCAiYXBwbHkiKTs7CgpsZXQgdHJ5YXBw bHlkIGYgYSBkID0gYXBwbHlkIGYgKGZ1biB4IC0+IGQpIGE7OwoKbGV0IHRyeWFwcGx5bCBmIHgg PSB0cnlhcHBseWQgZiB4IFtdOzsKCmxldCBkZWZpbmVkIGYgeCA9IHRyeSBhcHBseSBmIHg7IHRy dWUgd2l0aCBGYWlsdXJlIF8gLT4gZmFsc2U7OwoKKCogLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSAqKQooKiBV bmRlZmluaXRpb24uICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICopCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKCmxldCB1bmRlZmluZSA9 CiAgbGV0IHJlYyB1bmRlZmluZV9saXN0IHggbCA9CiAgICBtYXRjaCBsIHdpdGgKICAgICAgKGEs YiBhcyBhYik6OnQgLT4KICAgICAgICAgIGxldCBjID0gUGVydmFzaXZlcy5jb21wYXJlIHggYSBp bgogICAgICAgICAgaWYgYyA9IDAgdGhlbiB0CiAgICAgICAgICBlbHNlIGlmIGMgPCAwIHRoZW4g bCBlbHNlCiAgICAgICAgICBsZXQgdCcgPSB1bmRlZmluZV9saXN0IHggdCBpbgogICAgICAgICAg aWYgdCcgPT0gdCB0aGVuIGwgZWxzZSBhYjo6dCcKICAgIHwgW10gLT4gW10gaW4KICBmdW4geCAt PgogICAgbGV0IGsgPSBIYXNodGJsLmhhc2ggeCBpbgogICAgbGV0IHJlYyB1bmQgdCA9CiAgICAg IG1hdGNoIHQgd2l0aAogICAgICAgIExlYWYoaCxsKSB3aGVuIGggPSBrIC0+CiAgICAgICAgICBs ZXQgbCcgPSB1bmRlZmluZV9saXN0IHggbCBpbgogICAgICAgICAgaWYgbCcgPT0gbCB0aGVuIHQK ICAgICAgICAgIGVsc2UgaWYgbCcgPSBbXSB0aGVuIEVtcHR5CiAgICAgICAgICBlbHNlIExlYWYo aCxsJykKICAgICAgfCBCcmFuY2gocCxiLGwscikgd2hlbiBrIGxhbmQgKGIgLSAxKSA9IHAgLT4K ICAgICAgICAgIGlmIGsgbGFuZCBiID0gMCB0aGVuCiAgICAgICAgICAgIGxldCBsJyA9IHVuZCBs IGluCiAgICAgICAgICAgIGlmIGwnID09IGwgdGhlbiB0CiAgICAgICAgICAgIGVsc2UgaWYgaXNf dW5kZWZpbmVkIGwnIHRoZW4gcgogICAgICAgICAgICBlbHNlIEJyYW5jaChwLGIsbCcscikKICAg ICAgICAgIGVsc2UKICAgICAgICAgICAgbGV0IHInID0gdW5kIHIgaW4KICAgICAgICAgICAgaWYg cicgPT0gciB0aGVuIHQKICAgICAgICAgICAgZWxzZSBpZiBpc191bmRlZmluZWQgcicgdGhlbiBs CiAgICAgICAgICAgIGVsc2UgQnJhbmNoKHAsYixsLHInKQogICAgICB8IF8gLT4gdCBpbgogICAg dW5kOzsKCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKKCogUmVkZWZpbml0aW9uIGFuZCBjb21iaW5h dGlvbi4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQooKiAt LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tICopCgpsZXQgKHwtPiksY29tYmluZSA9CiAgbGV0IGxkYiB4IHkgPSBs ZXQgeiA9IHggbHhvciB5IGluIHogbGFuZCAoLXopIGluCiAgbGV0IG5ld2JyYW5jaCBwMSB0MSBw MiB0MiA9CiAgICBsZXQgYiA9IGxkYiBwMSBwMiBpbgogICAgbGV0IHAgPSBwMSBsYW5kIChiIC0g MSkgaW4KICAgIGlmIHAxIGxhbmQgYiA9IDAgdGhlbiBCcmFuY2gocCxiLHQxLHQyKQogICAgZWxz ZSBCcmFuY2gocCxiLHQyLHQxKSBpbgogIGxldCByZWMgZGVmaW5lX2xpc3QgKHgseSBhcyB4eSkg bCA9CiAgICBtYXRjaCBsIHdpdGgKICAgICAgKGEsYiBhcyBhYik6OnQgLT4KICAgICAgICAgIGxl dCBjID0gUGVydmFzaXZlcy5jb21wYXJlIHggYSBpbgogICAgICAgICAgaWYgYyA9IDAgdGhlbiB4 eTo6dAogICAgICAgICAgZWxzZSBpZiBjIDwgMCB0aGVuIHh5OjpsCiAgICAgICAgICBlbHNlIGFi OjooZGVmaW5lX2xpc3QgeHkgdCkKICAgIHwgW10gLT4gW3h5XQogIGFuZCBjb21iaW5lX2xpc3Qg b3AgeiBsMSBsMiA9CiAgICBtYXRjaCAobDEsbDIpIHdpdGgKICAgICAgW10sXyAtPiBsMgogICAg fCBfLFtdIC0+IGwxCiAgICB8ICgoeDEseTEgYXMgeHkxKTo6dDEsKHgyLHkyIGFzIHh5Mik6OnQy KSAtPgogICAgICAgICAgbGV0IGMgPSBQZXJ2YXNpdmVzLmNvbXBhcmUgeDEgeDIgaW4KICAgICAg ICAgIGlmIGMgPCAwIHRoZW4geHkxOjooY29tYmluZV9saXN0IG9wIHogdDEgbDIpCiAgICAgICAg ICBlbHNlIGlmIGMgPiAwIHRoZW4geHkyOjooY29tYmluZV9saXN0IG9wIHogbDEgdDIpIGVsc2UK ICAgICAgICAgIGxldCB5ID0gb3AgeTEgeTIgYW5kIGwgPSBjb21iaW5lX2xpc3Qgb3AgeiB0MSB0 MiBpbgogICAgICAgICAgaWYgeih5KSB0aGVuIGwgZWxzZSAoeDEseSk6OmwgaW4KICBsZXQgKHwt PikgeCB5ID0KICAgIGxldCBrID0gSGFzaHRibC5oYXNoIHggaW4KICAgIGxldCByZWMgdXBkIHQg PQogICAgICBtYXRjaCB0IHdpdGgKICAgICAgICBFbXB0eSAtPiBMZWFmIChrLFt4LHldKQogICAg ICB8IExlYWYoaCxsKSAtPgogICAgICAgICAgIGlmIGggPSBrIHRoZW4gTGVhZihoLGRlZmluZV9s aXN0ICh4LHkpIGwpCiAgICAgICAgICAgZWxzZSBuZXdicmFuY2ggaCB0IGsgKExlYWYoayxbeCx5 XSkpCiAgICAgIHwgQnJhbmNoKHAsYixsLHIpIC0+CiAgICAgICAgICBpZiBrIGxhbmQgKGIgLSAx KSA8PiBwIHRoZW4gbmV3YnJhbmNoIHAgdCBrIChMZWFmKGssW3gseV0pKQogICAgICAgICAgZWxz ZSBpZiBrIGxhbmQgYiA9IDAgdGhlbiBCcmFuY2gocCxiLHVwZCBsLHIpCiAgICAgICAgICBlbHNl IEJyYW5jaChwLGIsbCx1cGQgcikgaW4KICAgIHVwZCBpbgogIGxldCByZWMgY29tYmluZSBvcCB6 IHQxIHQyID0KICAgIG1hdGNoICh0MSx0Mikgd2l0aAogICAgICBFbXB0eSxfIC0+IHQyCiAgICB8 IF8sRW1wdHkgLT4gdDEKICAgIHwgTGVhZihoMSxsMSksTGVhZihoMixsMikgLT4KICAgICAgICAg IGlmIGgxID0gaDIgdGhlbgogICAgICAgICAgICBsZXQgbCA9IGNvbWJpbmVfbGlzdCBvcCB6IGwx IGwyIGluCiAgICAgICAgICAgIGlmIGwgPSBbXSB0aGVuIEVtcHR5IGVsc2UgTGVhZihoMSxsKQog ICAgICAgICAgZWxzZSBuZXdicmFuY2ggaDEgdDEgaDIgdDIKICAgIHwgKExlYWYoayxsaXMpIGFz IGxmKSwoQnJhbmNoKHAsYixsLHIpIGFzIGJyKSAtPgogICAgICAgICAgaWYgayBsYW5kIChiIC0g MSkgPSBwIHRoZW4KICAgICAgICAgICAgaWYgayBsYW5kIGIgPSAwIHRoZW4KICAgICAgICAgICAg ICBsZXQgbCcgPSBjb21iaW5lIG9wIHogbGYgbCBpbgogICAgICAgICAgICAgIGlmIGlzX3VuZGVm aW5lZCBsJyB0aGVuIHIgZWxzZSBCcmFuY2gocCxiLGwnLHIpCiAgICAgICAgICAgIGVsc2UKICAg ICAgICAgICAgICBsZXQgcicgPSBjb21iaW5lIG9wIHogbGYgciBpbgogICAgICAgICAgICAgIGlm IGlzX3VuZGVmaW5lZCByJyB0aGVuIGwgZWxzZSBCcmFuY2gocCxiLGwscicpCiAgICAgICAgICBl bHNlCiAgICAgICAgICAgIG5ld2JyYW5jaCBrIGxmIHAgYnIKICAgIHwgKEJyYW5jaChwLGIsbCxy KSBhcyBiciksKExlYWYoayxsaXMpIGFzIGxmKSAtPgogICAgICAgICAgaWYgayBsYW5kIChiIC0g MSkgPSBwIHRoZW4KICAgICAgICAgICAgaWYgayBsYW5kIGIgPSAwIHRoZW4KICAgICAgICAgICAg ICBsZXQgbCcgPSBjb21iaW5lIG9wIHogbCBsZiBpbgogICAgICAgICAgICAgIGlmIGlzX3VuZGVm aW5lZCBsJyB0aGVuIHIgZWxzZSBCcmFuY2gocCxiLGwnLHIpCiAgICAgICAgICAgIGVsc2UKICAg ICAgICAgICAgICBsZXQgcicgPSBjb21iaW5lIG9wIHogciBsZiBpbgogICAgICAgICAgICAgIGlm IGlzX3VuZGVmaW5lZCByJyB0aGVuIGwgZWxzZSBCcmFuY2gocCxiLGwscicpCiAgICAgICAgICBl bHNlCiAgICAgICAgICAgIG5ld2JyYW5jaCBwIGJyIGsgbGYKICAgIHwgQnJhbmNoKHAxLGIxLGwx LHIxKSxCcmFuY2gocDIsYjIsbDIscjIpIC0+CiAgICAgICAgICBpZiBiMSA8IGIyIHRoZW4KICAg ICAgICAgICAgaWYgcDIgbGFuZCAoYjEgLSAxKSA8PiBwMSB0aGVuIG5ld2JyYW5jaCBwMSB0MSBw MiB0MgogICAgICAgICAgICBlbHNlIGlmIHAyIGxhbmQgYjEgPSAwIHRoZW4KICAgICAgICAgICAg ICBsZXQgbCA9IGNvbWJpbmUgb3AgeiBsMSB0MiBpbgogICAgICAgICAgICAgIGlmIGlzX3VuZGVm aW5lZCBsIHRoZW4gcjEgZWxzZSBCcmFuY2gocDEsYjEsbCxyMSkKICAgICAgICAgICAgZWxzZQog ICAgICAgICAgICAgIGxldCByID0gY29tYmluZSBvcCB6IHIxIHQyIGluCiAgICAgICAgICAgICAg aWYgaXNfdW5kZWZpbmVkIHIgdGhlbiBsMSBlbHNlIEJyYW5jaChwMSxiMSxsMSxyKQogICAgICAg ICAgZWxzZSBpZiBiMiA8IGIxIHRoZW4KICAgICAgICAgICAgaWYgcDEgbGFuZCAoYjIgLSAxKSA8 PiBwMiB0aGVuIG5ld2JyYW5jaCBwMSB0MSBwMiB0MgogICAgICAgICAgICBlbHNlIGlmIHAxIGxh bmQgYjIgPSAwIHRoZW4KICAgICAgICAgICAgICBsZXQgbCA9IGNvbWJpbmUgb3AgeiB0MSBsMiBp bgogICAgICAgICAgICAgIGlmIGlzX3VuZGVmaW5lZCBsIHRoZW4gcjIgZWxzZSBCcmFuY2gocDIs YjIsbCxyMikKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgIGxldCByID0gY29tYmluZSBv cCB6IHQxIHIyIGluCiAgICAgICAgICAgICAgaWYgaXNfdW5kZWZpbmVkIHIgdGhlbiBsMiBlbHNl IEJyYW5jaChwMixiMixsMixyKQogICAgICAgICAgZWxzZSBpZiBwMSA9IHAyIHRoZW4KICAgICAg ICAgICAgbGV0IGwgPSBjb21iaW5lIG9wIHogbDEgbDIgYW5kIHIgPSBjb21iaW5lIG9wIHogcjEg cjIgaW4KICAgICAgICAgICAgaWYgaXNfdW5kZWZpbmVkIGwgdGhlbiByCiAgICAgICAgICAgIGVs c2UgaWYgaXNfdW5kZWZpbmVkIHIgdGhlbiBsIGVsc2UgQnJhbmNoKHAxLGIxLGwscikKICAgICAg ICAgIGVsc2UKICAgICAgICAgICAgbmV3YnJhbmNoIHAxIHQxIHAyIHQyIGluCiAgKHwtPiksY29t YmluZTs7CgooKiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tICopCigqIFNwZWNpYWwgY2FzZSBvZiBwb2ludCBm dW5jdGlvbi4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKikKKCog LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLSAqKQoKbGV0ICh8PT4pID0gZnVuIHggeSAtPiAoeCB8LT4geSkgdW5k ZWZpbmVkOzsKCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKKCogR3JhYiBhbiBhcmJpdHJhcnkgZWxl bWVudC4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAqKQoo KiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tICopCgpsZXQgcmVjIGNob29zZSB0ID0KICBtYXRjaCB0IHdpdGgK ICAgIEVtcHR5IC0+IGZhaWx3aXRoICJjaG9vc2U6IGNvbXBsZXRlbHkgdW5kZWZpbmVkIGZ1bmN0 aW9uIgogIHwgTGVhZihoLGwpIC0+IExpc3QuaGQgbAogIHwgQnJhbmNoKGIscCx0MSx0MikgLT4g Y2hvb3NlIHQxOzsKCigqIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gKikKKCogTWFwcGluZyB0byBzb3J0ZWQt bGlzdCByZXByZXNlbnRhdGlvbiBvZiB0aGUgZ3JhcGgsIGRvbWFpbiBhbmQgcmFuZ2UuICAgICAq KQooKiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tICopCgpsZXQgcmVjIHVuaXEgbCA9CiAgbWF0Y2ggbCB3aXRo CiAgICB4OjooeTo6XyBhcyB0KSAtPiBsZXQgdCcgPSB1bmlxIHQgaW4KICAgICAgICAgICAgICAg ICAgICAgIGlmIFBlcnZhc2l2ZXMuY29tcGFyZSB4IHkgPSAwIHRoZW4gdCcgZWxzZQogICAgICAg ICAgICAgICAgICAgICAgaWYgdCc9PXQgdGhlbiBsIGVsc2UgeDo6dCcKIHwgXyAtPiBsOzsKCmxl dCBzZXRpZnkgbCA9IHVuaXEoTGlzdC5zb3J0IFBlcnZhc2l2ZXMuY29tcGFyZSBsKTs7CgpsZXQg Z3JhcGggZiA9IHNldGlmeSAoZm9sZGwgKGZ1biBhIHggeSAtPiAoeCx5KTo6YSkgW10gZik7OwoK bGV0IGRvbSBmID0gc2V0aWZ5KGZvbGRsIChmdW4gYSB4IHkgLT4geDo6YSkgW10gZik7OwoKbGV0 IHJhbiBmID0gc2V0aWZ5KGZvbGRsIChmdW4gYSB4IHkgLT4geTo6YSkgW10gZik7OwoKKCogLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLSAqKQooKiBJZGlvbSBmb3IgYSBtYXBwaW5nIHppcHBpbmcgZG9tYWluIGFu ZCByYW5nZSBsaXN0cy4gICAgICAgICAgICAgICAgICAgICAgICopCigqIC0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0gKikKCmxldCBmcGYgeHMgeXMgPSBMaXN0LmZvbGRfcmlnaHQyICh8LT4pIHhzIHlzIHVuZGVm aW5lZDs7CgooKiAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tICopCigqIEluc3RhbGwgYSAodHJpdmlhbCkgcHJp bnRlciBmb3IgZmluaXRlIHBhcnRpYWwgZnVuY3Rpb25zLiAgICAgICAgICAgICAgICAgKikKKCog LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLSAqKQoKbGV0IHByaW50X2ZwZiAoZjooJ2EsJ2IpZnVuYykgPSBwcmlu dF9zdHJpbmcgIjxmdW5jPiI7OwoKI2luc3RhbGxfcHJpbnRlciBwcmludF9mcGY7Owo= --_002_DCC19446A892D84FBB89AE7C94F0C04E01D99539DCazsmsx501amrc_--