Archived

This topic is now archived and is closed to further replies.

Serializing with constraints

This topic is 5127 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

As a part of my compression system, I''ve got a tree of nodes that I need to write to file. However, it must abide by the following rules:
1. The root node must be the first node in the stream.
2. Child nodes must always be after their parents in the stream.
3. The distance, in bytes, between any child and its parent must be less than or equal to 126 bytes.
It''s that last one that''s giving me problems. What algorithm can I use to make it true for any tree, or if it''s not possible to report that? Richard "Superpig" Fine - saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5 ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu Preserve wildlife: pickle a squirrel today!

Share on other sites
A node''s children must be added to the file before the children of the nodes that were written to the file after that node. So use a queue where you put the children to wait for their turn. If the queue''s size grows bigger than 126, return failure. And the distance to the child nodes of the currently processed node is just the queue''s size at that time.

Share on other sites
Um... I don't understand. Could you explain in a little more detail, please?

Edit: I should also mention that nodes aren't all the same size - leaf nodes are 1 byte and non-leaf nodes are 2 bytes.

[edited by - Superpig on February 6, 2004 11:00:35 AM]

Share on other sites
I think what civguy means and what i would recommend is the level-order traversal of a tree. That means traversing at first the root (level 0), root's children (level 1), the children of root's children (level 2) and so on. Before inserting an object you check the size of the queue. If it contains more than 126 bytes of data then rule 3 cannot be fulfilled.

Possible code may look like this:

QUEUE q;
Node n;
q.put(ROOTNODE);
int s = ROOTNODE.size();
while(!q.empty())
{
n = q.pop();
visit(n);
s -= n.size();
foreach(child of n)
{
if(s > 126)
{
/* guess what */
return false;
}

q.push(child);
s += child.size();
}
}

Btw. is that for Enginuity ? What about the next article ?

[edited by - nydian on February 6, 2004 12:30:28 PM]

Share on other sites
Ya, nYdian's pseudocode looks like what I said, with added offset counter (or tried to say . sorry I'm pretty out of it today). The fact that the nodes have different sizes shouldn't affect the order in which they're inserted to the stream. If you decided to be 'cunning' and chose not to use some node from the queue's top because it's a 2-byte non-leaf node and there are some 1-byte leafs in the queue too, you'd just be putting off the eventually required 2-byte non-leaf node even farther away from it's root even though it's more urgent than those 1-byte leafs whose root was inserted to the stream later. I hope that makes sense at all. If it doesn't just use nYdian's code

[edited by - civguy on February 6, 2004 12:38:59 PM]

Share on other sites
Ah, ok. But if a single level of the tree is greater than 126 bytes in size, then the last node in the previous level might not be able to get to its children... that''s the sort of problem I might be facing, because there are 256 leaf nodes in this tree and it''s possible that they''ll all be on the same level. However, it *should* still be possible...

I''m starting to think that the solution will be something iterative - something which takes a best-guess at the solution (like the one you suggested) and then continually moves parent/child pairs closer together until the constraint is satisfied for all relationships. It''s a little like a rigid body system in a way - keeping a given spatial relationship between elements of a tree. The only difference between that physics basis and this is that this is one-dimensional.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5
ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
Preserve wildlife: pickle a squirrel today!

Share on other sites
What algorithm can I use to make it true for any tree, or if it's not possible to report that?
It seems quite obvious to me that predicate 3, lets you answer no in general.

I think you'll have to change your predicates since a counter examples can easilly be found and proven uncompatible with your set of rules specially 3. So unless you restrict your algorithm to a certain class of trees, which you did not give any clue about your attempt is vain.

Can you tell us a bit more on the particular context of your algo. What kind of "trees" are we talking about ?

Anticipating your answer I find that if your constraints are a bit relaxed it might be possible to do something valuable. I assume that your tree is analoguous to a tree-graph used as a hierarchical db for a 3D scene containing separate geometry (this could be a BSP or an octree for instance).

Then this means a dual structure exists that can exploit a spatial neighboorhood. Just see an octree as both a graph and a space partition (topology). I hope you can visualize what I mean. Then I can't help thinking of a technique I found ten years ago, and others found/exploited too in //, could be used. It was aimed at exploiting Level one Cache in software texturing.

Textures could be modified so that texel indices (adresses)appear in this manner in texture space :
0  1  4  52  3  6  78  9  12 1410 11 13 15

This is basically done by interleaving the bits of the u and v indices. The index transformation is ;

u0u1...un + n * v0v1...vn -> u0v0u1v1...unvn
(n=2^e), e=log2(texture width) assuming it's square for simplicity.

The texture can be seen as a quadtree fully expanded up to level e. So it's easy to extrapolate the scheme in 3D for an octree.

With a similar concept it's probably possible to make your predicates 1, 2, 3 respected inside clusters .

In one word what is not feasible for the whole tree may become possible for a partition into clustered subsets of this tree.

[edited by - Charles B on February 7, 2004 8:41:54 AM]

Share on other sites
It''s a binary tree.

But don''t worry, I''ve decided to relax the constraint. I''m using an extra byte per non-leaf node now, which gives me 11 bits to represent the address of a child - and the total size of the tree is just under 2^9, so 2^11 will be more than enough space.

Thanks anyway, everyone.