help-gnu-emacs
[Top][All Lists]
Advanced

[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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]