From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Binary Search Tree and Treap Functions bst-assq and treap-put Date: Sun, 04 Dec 2016 12:04:19 -0500 Message-ID: References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1480871121 3579 195.159.176.226 (4 Dec 2016 17:05:21 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 4 Dec 2016 17:05:21 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Andy Sonnenburg Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 04 18:05:17 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 1cDaDz-0008P1-SD for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 18:05:15 +0100 Original-Received: from localhost ([::1]:35125 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDaE2-0006ev-3b for ged-emacs-devel@m.gmane.org; Sun, 04 Dec 2016 12:05:18 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58936) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cDaDB-0006ds-F4 for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:04:26 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cDaD8-0002WC-AP for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:04:25 -0500 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:57683) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cDaD8-0002VE-2v for emacs-devel@gnu.org; Sun, 04 Dec 2016 12:04:22 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BHAgALW9BX/50WNJ1dGwEBAQMBAQGDLQEBAQEBHoRNhVCEZasRggOGFgQCAoFpORQBAgEBAQEBAQFeJ4RiAQEDAVYjBQsLNBIUGA0kiFUIvFUBAQgCJYp9ihwFjx2KPJkNhguQSx42gmccgWsehgoBAQE X-IPAS-Result: A0BHAgALW9BX/50WNJ1dGwEBAQMBAQGDLQEBAQEBHoRNhVCEZasRggOGFgQCAoFpORQBAgEBAQEBAQFeJ4RiAQEDAVYjBQsLNBIUGA0kiFUIvFUBAQgCJYp9ihwFjx2KPJkNhguQSx42gmccgWsehgoBAQE X-IronPort-AV: E=Sophos;i="5.30,296,1470715200"; d="scan'208";a="281487617" Original-Received: from 157-52-22-157.cpe.teksavvy.com (HELO pastel.home) ([157.52.22.157]) by smtp.teksavvy.com with ESMTP; 04 Dec 2016 12:04:21 -0500 Original-Received: by pastel.home (Postfix, from userid 20848) id C941964F1D; Sun, 4 Dec 2016 12:04:19 -0500 (EST) In-Reply-To: (Andy Sonnenburg's message of "Sun, 4 Dec 2016 07:14:26 -0500") X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 206.248.154.181 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:210026 Archived-At: > 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