[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Circular lists/shared structures in org-element parse-tree
From: |
Thorsten Jolitz |
Subject: |
Re: Circular lists/shared structures in org-element parse-tree |
Date: |
Sat, 29 Jun 2013 00:06:00 +0200 |
User-agent: |
Gnus/5.130002 (Ma Gnus v0.2) Emacs/24.3 (gnu/linux) |
"Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> Thorsten Jolitz <tjolitz@gmail.com> 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.
Thank you for the detailled instructions, very helpful indeed! I thought
Emacs might have some inbuilt functionality to deal with circular list,
but it seems to require some individual effort.
--
cheers,
Thorsten