From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Pascal J. Bourguignon" Newsgroups: gmane.emacs.help Subject: Re: Circular lists/shared structures in org-element parse-tree Date: Fri, 28 Jun 2013 23:26:03 +0200 Organization: Informatimago Message-ID: <87y59u3p1w.fsf@informatimago.com> References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1372455438 7151 80.91.229.3 (28 Jun 2013 21:37:18 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 28 Jun 2013 21:37:18 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Jun 28 23:37:20 2013 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UsgM4-0004xE-HZ for geh-help-gnu-emacs@m.gmane.org; Fri, 28 Jun 2013 23:37:20 +0200 Original-Received: from localhost ([::1]:60034 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UsgM3-0000R3-KH for geh-help-gnu-emacs@m.gmane.org; Fri, 28 Jun 2013 17:37:19 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 83 Original-X-Trace: individual.net sHs51op7IRiMCHsv0qZuZA9F0kJ/QtqLVpcnRM8tSuPSF+pNbr Cancel-Lock: sha1:ODBlMzAxNmVlMWY5ODE2ZDBkZTg0NzIxNWFjZmZlNTE3ZGE1NTExMg== sha1:tKrKm8Uta9H5SNadh5pyswd6ohM= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.2 (gnu/linux) Original-Xref: usenet.stanford.edu gnu.emacs.help:199566 X-Mailman-Approved-At: Fri, 28 Jun 2013 17:37:10 -0400 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:91832 Archived-At: Thorsten Jolitz writes: > [Originally posted on the Org-mode mailing list, but I post it here too > since it is more an elisp oriented mailing list] > > Hi List, > > I wonder how I can find out in a (elisp) program the points in the parse > tree (returned by org-element-parse-buffer) where shared structures are > used. > > In the read-syntax, its easy to see (especially with `print-circle' set > to non-nil): > > #+begin_src emacs-lisp > #2=(org-data nil #1=(headline (:raw-value "header 1" > [...] :parent #2#) [...] > #+end_src > > but when processing the parse tree as a list in elisp, how can I detect the > fact that > > ,------------ > | :parent #2# > `------------ > > refers to > > ,----------------- > | #2=(org-data nil > `----------------- > > i.e. points back to an already existing structure? 1- there is not a unique solution in general: it depends on the order in which you choose to walk the branches. 2- you just walk the cons tree, checking if you've not already visited them. Something like this: (let* ((counter 0) (objects (make-hash-table))) (labels ((walk (object) (let ((reference (gethash object objects)))) (if reference (already-seen object reference)) (progn (new-reference object (setf (gethash object objects) (incf counter))) (cond ((vector object) (dotimes (i (length vector)) (walk (aref vector i)))) ((cons object) (walk (car object)) (walk (cdr object))) ( ; you may also want to walk structures, ; hashtable, etc ))))) (walk root))) If you don't want to generate references for objects present only once, then you can transform this in a two-pass algorithm where you first fill the hash-table with a counter of occurence: (incf (gethash object objects 0)) and then only keep and renumber the entries that have a value greater than 1. -- __Pascal Bourguignon__ http://www.informatimago.com/ A bad day in () is better than a good day in {}. You know you've been lisping too long when you see a recent picture of George Lucas and think "Wait, I thought John McCarthy was dead!" -- Dalek_Baldwin