From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: tomas@tuxteam.de Newsgroups: gmane.emacs.devel Subject: Re: van Emde Boas hash. Date: Mon, 23 Nov 2009 05:06:49 +0100 Message-ID: <20091123040649.GA22386@tomas> References: <24670838.273241258699275844.JavaMail.www@wwinf4616> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; x-action=pgp-signed Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1258949651 23248 80.91.229.12 (23 Nov 2009 04:14:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 23 Nov 2009 04:14:11 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Nov 23 05:14:04 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NCQJP-0000zb-G7 for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 05:14:03 +0100 Original-Received: from localhost ([127.0.0.1]:58063 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCQJO-0003LQ-PS for ged-emacs-devel@m.gmane.org; Sun, 22 Nov 2009 23:14:02 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCQJI-0003L3-95 for emacs-devel@gnu.org; Sun, 22 Nov 2009 23:13:56 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCQJD-0003Jk-Bg for emacs-devel@gnu.org; Sun, 22 Nov 2009 23:13:55 -0500 Original-Received: from [199.232.76.173] (port=59827 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCQJC-0003Jc-T8 for emacs-devel@gnu.org; Sun, 22 Nov 2009 23:13:50 -0500 Original-Received: from alextrapp1.equinoxe.de ([217.22.192.104]:37098 helo=www.elogos.de) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NCQJC-0004ey-IO for emacs-devel@gnu.org; Sun, 22 Nov 2009 23:13:50 -0500 Original-Received: by www.elogos.de (Postfix, from userid 1000) id F0C5B90048; Mon, 23 Nov 2009 05:06:49 +0100 (CET) Content-Disposition: inline In-Reply-To: <24670838.273241258699275844.JavaMail.www@wwinf4616> User-Agent: Mutt/1.5.15+20070412 (2007-04-11) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 2) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:117554 Archived-At: -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Fri, Nov 20, 2009 at 07:41:15AM +0100, A. Soare wrote: >=20 > Van Emde Boas arrays are hashed arrays [...] >=20 > For example, for an array of length 2^32, the complexity is O(0), and > the number of steps is less than log_2 (32) =3D "maximum 5 steps" for e= very operation. >=20 > The operations are: >=20 > * insert a new number > * delete a number > * seek for a number > * find the successor of a number > * find the predecessor of a number If I understood the Wikipedia page correctly (thnks, Deniz), you can find "next" and "previous" to a number not in the hash? Then they look like a good candidate to represent markers and boundaries of overlays, no? Regards - -- tom=C3=A1s -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFLCgpZBcgs9XrR2kYRAvh6AJ9TxH4v/4jFSN90gK/X/QHgJQuf/wCfUYYU mZjOWuTH3spYQJWvZ3HtWzg=3D =3D7Ccl -----END PGP SIGNATURE-----