Re: Circular lists/shared structures in org-element parse-tree

[Pascal J. Bourguignon]

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.



                    
                        
-- 
__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