From: Daniel Lucraft <dan@...>
Date: 2007-08-02T19:43:50+09:00
Subject: Re: Deep YAML

Hans Fugal wrote:
> I'm toying with GEDCOM again, and trying to write out the YAML
> equivalent of a GEDCOM file (just for kicks, mainly).
> 
> It might look like this (edited for brevity):
> 
> 0 @I1@ INDI
> 1 WIFE @I1@
> 1 CHIL @I3@
> 
> 
> Is there no way to have yaml break deep nesting with an ID reference? Or
> better yet, use an ID at any point other than the shallowest point where
> that object occurs?

YAML will make an ID reference rather than inserting the object if it 
has already encountered that object as it traverses the object tree. You 
just have to make sure that it encounters the objects in the correct 
order.

Here's my reasoning. We are trying to dump a really deep tree to YAML:

# first build the tree:
deeptree = []
curr = deeptree
refs = []
5000.times do |i|
  n = [i, []]
  curr << n
  curr = n[1]
  refs << n
end

# then try and dump it:
deeptree.to_yaml       #=> fails with stack error
refs.to_yaml           #=> fails with stack error
refs.reverse.to_yaml   #=> succeeds!

Deeptree looks like:
[1, [2, [3, [4, []]]]]
which fails because its so deep.

Refs looks like:
[
  [1, [2, [3, [4, []]]]],
  [2, [3, [4, []]]],
  [3, [4, []]],
  [4, []],
  []
]
which fails because the first element is so deep.

refs.reverse looks like:
[
  [],
  [4, []],
  [3, [4, []]],
  [2, [3, [4, []]]],
  [1, [2, [3, [4, []]]]]
]

which works because at each step YAML can insert an object reference 
because it has already encountered the second array element in the 
previous step.

So in your case, instead of just saving the family tree, save an array 
containing references to all members of the tree. Make sure to start 
with the leaves of the tree and work your way up through the ancestors. 
When you reload the last element of the array is your complete tree.

hope this helps,
Dan

--------------------
Illustrations:

irb> arr
=> [0, [1, [2, [3, [4, []]]]]]

irb> refs
=> [[1, [2, [3, [4, []]]]], [2, [3, [4, []]]], [3, [4, []]], [4, []], 
[]]

irb> puts arr.to_yaml
---
- 0
- - 1
  - - 2
    - - 3
      - - 4
        - []
=> nil

irb> puts refs.to_yaml
---
- - 1
  - &id001
    - 2
    - &id002
      - 3
      - &id003
        - 4
        - &id004 []

- *id001
- *id002
- *id003
- *id004
=> nil

irb> puts refs.reverse.to_yaml
---
- &id001 []

- &id002
  - 4
  - *id001
- &id003
  - 3
  - *id002
- &id004
  - 2
  - *id003
- - 1
  - *id004
=> nil
-- 
Posted via http://www.ruby-forum.com/.