From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andy Sonnenburg Newsgroups: gmane.emacs.devel Subject: Re: Binary Search Tree and Treap Functions bst-assq and treap-put Date: Sun, 4 Dec 2016 12:13:21 -0500 Message-ID: References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a1147a2f0ca58800542d84982 X-Trace: blaine.gmane.org 1480871641 9596 195.159.176.226 (4 Dec 2016 17:14:01 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 4 Dec 2016 17:14:01 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 04 18:13:57 2016 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cDaMP-0001hf-4S for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 18:13:57 +0100 Original-Received: from localhost ([::1]:35151 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDaMT-0000KN-3c for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 12:14:01 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:60843) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDaLs-0000J3-5v for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:13:25 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cDaLr-000538-3O for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:13:24 -0500 Original-Received: from mail-qk0-x235.google.com ([2607:f8b0:400d:c09::235]:33300) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cDaLq-00052t-T3 for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:13:23 -0500 Original-Received: by mail-qk0-x235.google.com with SMTP id x190so325617234qkb.0 for ; Sun, 04 Dec 2016 09:13:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=7zI8CZtRDzfVl25ImU5WA82tahhUdxKZXtYnFRb+vkU=; b=HKrQO1Xj6xve2B4uDsC31sMpU3MP5NtQ+/TAyiSwWma+5Q/t4Deq8i7y9UcGeEn/tE MP5CZ7Rw5BT2Elk0qIrz1W+QTYqG4dI/6vMKidu80qIUBTHSJYqUIbRl2zYwOjqsS7wC VgjD4bw77fDLvtTBM4ZfxAh5vveOsJAkDATq4AsJMIVD6Z9K76hyg7LWJY0nicST29pw qz+DfnTqA2reDdOw/3MqVO5KauPW/xJo444PbszN1RtuhPhZnPMivPFAH7HNRlO20ROA SrlP2Jk3ShMs8X2Nl4z76IDyPx7h6G+naJIniUE3Q082ySe15vvdo6jCt1eysBEvkzmk LENA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=7zI8CZtRDzfVl25ImU5WA82tahhUdxKZXtYnFRb+vkU=; b=Ecqw6n2nelaFNamalwIhrg+ObBSlCmIDby3KQ6rOeH47F83ZaFGN6BYKQVz80pjSOW 1bTtQwUer7j3NKrj9m6GFM9ekv3yPHrpaZ7uyyNe29SIrSdckZnXMLWOZWY99AAmfPrn T+aO6sNaHpwSFUyhuiK9DlriUo7f3v9CVKN921BRkvf6eK7GrnC7pIS5SBht1loFQI0B Y4y8LcTSKhRgH7D4aj5PpjDSEPNSZgEcfYjGFGBhYDD2aKGIOCmgqa+AxCspz37ksicP teBkxonCbmqsNIKu/xmJOHsT+x6JGfw9iq4s0feSKtAGO+yG72rrsVYGPr7RYsLc7r9D Tnjw== X-Gm-Message-State: AKaTC01PMn34mVmrvSelrAmYeXDZgTY9wMmMoWiY5Tk9lR9wsURSet6qO/DelFymXA9v+AgJPK/TLUmfPsEBrQ== X-Received: by 10.55.23.213 with SMTP id 82mr47186951qkx.40.1480871601917; Sun, 04 Dec 2016 09:13:21 -0800 (PST) Original-Received: by 10.12.171.81 with HTTP; Sun, 4 Dec 2016 09:13:21 -0800 (PST) Original-Received: by 10.12.171.81 with HTTP; Sun, 4 Dec 2016 09:13:21 -0800 (PST) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:400d:c09::235 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:210028 Archived-At: --001a1147a2f0ca58800542d84982 Content-Type: text/plain; charset=UTF-8 It is written in C. The only real reason C was used was performance concerns, real or imagined. I can post a diff of the changes - it isn't that many lines. On Dec 4, 2016 12:04 PM, "Stefan Monnier" wrote: > > That's too bad (I mean, its good for performance, but unfortunate one of > > the use cases doesn't exist). However, the treap functions may still be > of > > general use. Let me know if there is any interest. They are documented > > and tested. They fill a gap between alists (persistent, linear lookup) > and > > hash tables (ephemeral, constant lookup) by being persistent while > > providing average case logarithmic lookup. > > Is it written in C or Elisp? If it's Elisp, then we definitely would > welcome it into GNU ELPA (there is already an avl-tree implementation in > Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier). > If it's written C, I'll let others decide whether we want to include it. > > > Stefan > --001a1147a2f0ca58800542d84982 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

It is written in C.=C2=A0 The only real reason C was used wa= s performance concerns, real or imagined.=C2=A0 I can post a diff of the ch= anges - it isn't that many lines.


On Dec 4, 2016 12= :04 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:
> That's too bad (I mean, its good for p= erformance, but unfortunate one of
> the use cases doesn't exist).=C2=A0 However, the treap functions m= ay still be of
> general use.=C2=A0 Let me know if there is any interest.=C2=A0 They ar= e documented
> and tested.=C2=A0 They fill a gap between alists (persistent, linear l= ookup) and
> hash tables (ephemeral, constant lookup) by being persistent while
> providing average case logarithmic lookup.

Is it written in C or Elisp?=C2=A0 If it's Elisp, then we definitely wo= uld
welcome it into GNU ELPA (there is already an avl-tree implementation in Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier).
If it's written C, I'll let others decide whether we want to includ= e it.


=C2=A0 =C2=A0 =C2=A0 =C2=A0 Stefan
--001a1147a2f0ca58800542d84982--