From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Juri Linkov Newsgroups: gmane.emacs.devel Subject: Re: breadcrumbs for Info . . . . . . Date: Sun, 15 Jun 2008 21:19:43 +0300 Organization: JURTA Message-ID: <87iqwatxj4.fsf@jurta.org> References: <009d01c8cb55$13d53e20$0200a8c0@us.oracle.com> <87fxrkltma.fsf@jurta.org> <00ae01c8cb71$c26aeef0$0200a8c0@us.oracle.com> <873ankqou6.fsf@jurta.org> <00d901c8cbc9$7df36fb0$0200a8c0@us.oracle.com> <87tzfzk331.fsf@jurta.org> <00a501c8ccdd$93328720$c2b22382@us.oracle.com> <002401c8cd1f$98631650$0200a8c0@us.oracle.com> <87hcbxd8t8.fsf@ambire.localdomain> <004201c8cd5d$1baa0900$0200a8c0@us.oracle.com> <87y759b6fv.fsf@ambire.localdomain> <008f01c8cd7e$3208a5a0$0200a8c0@us.oracle.com> <87prqlaz3p.fsf@ambire.localdomain> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1213554277 7265 80.91.229.12 (15 Jun 2008 18:24:37 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 15 Jun 2008 18:24:37 +0000 (UTC) Cc: Drew Adams , emacs-devel@gnu.org To: Thien-Thi Nguyen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Jun 15 20:25:21 2008 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 1K7wum-0005c4-Ak for ged-emacs-devel@m.gmane.org; Sun, 15 Jun 2008 20:25:20 +0200 Original-Received: from localhost ([127.0.0.1]:58885 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1K7wty-0005hw-28 for ged-emacs-devel@m.gmane.org; Sun, 15 Jun 2008 14:24:30 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1K7wtB-0005JU-JX for emacs-devel@gnu.org; Sun, 15 Jun 2008 14:23:41 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1K7wt9-0005IJ-EA for emacs-devel@gnu.org; Sun, 15 Jun 2008 14:23:40 -0400 Original-Received: from [199.232.76.173] (port=54099 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1K7wt9-0005IC-Aa for emacs-devel@gnu.org; Sun, 15 Jun 2008 14:23:39 -0400 Original-Received: from anti-4.kiev.sovam.com ([62.64.120.202]:54493) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1K7wt8-0003r5-V6 for emacs-devel@gnu.org; Sun, 15 Jun 2008 14:23:39 -0400 Original-Received: from [83.170.232.243] (helo=smtp.svitonline.com) by anti-4.kiev.sovam.com with esmtp (Exim 4.67) (envelope-from ) id 1K7wt6-0007oS-7r; Sun, 15 Jun 2008 21:23:36 +0300 In-Reply-To: <87prqlaz3p.fsf@ambire.localdomain> (Thien-Thi Nguyen's message of "Fri, 13 Jun 2008 21:55:54 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.60 (x86_64-pc-linux-gnu) X-Scanner-Signature: b36477657b07eb27dc67b07df918f397 X-DrWeb-checked: yes X-SpamTest-Envelope-From: juri@jurta.org X-SpamTest-Group-ID: 00000000 X-SpamTest-Header: Trusted X-SpamTest-Info: Profiles 3134 [June 15 2008] X-SpamTest-Info: {received from trusted relay: common white list} X-SpamTest-Info: {HEADERS: header Content-Type found without required header Content-Transfer-Encoding} X-SpamTest-Method: white ip list X-SpamTest-Rate: 10 X-SpamTest-Status: Trusted X-SpamTest-Status-Extended: trusted X-SpamTest-Version: SMTP-Filter Version 3.0.0 [0278], KAS30/Release X-detected-kernel: by monty-python.gnu.org: FreeBSD 6.x (1) 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:99265 Archived-At: > Even if the "cache" consisted only of a set of node+parent pairs > (regardless of the order among pairs), that would be sufficient. > > A slight twist on that data structure will give us a "reverse trie", > which is a set of elements (NODE PARENT PARENT^2...), with elements' > tails sharing storage (i.e, being other elements of the set). This is too complex structure for shallow short trees of Info manuals. Now the cache has the structure (NODE PARENT CHILDREN) that allows optimal navigating the tree in both directions: bottom-up to build the breadcrumbs, and top-down to build the TOC node. -- Juri Linkov http://www.jurta.org/emacs/