Hello again. Thanks for your suggestion.
Den 03. jan. 2012 00:38, skrev Kevin R. Coombes:
Your last few posts have confused me as to the actual requirements.
Suppose I have the following tree, where the numbers on the nodes are
arbitrary IDs that i have assigned.
[1]
|
-----------
| |
[2] [3]
| |
----------------- ---------
| | | | |
[4] [X] [5] [6] [7]
But if I want to insert a branch between 2 and 3 and still keep it
ordered? Wouldn't I then have to give a new path to 3, 6 and 7? One
solution that has been suggested is to use decimal values, so that I
could do 2+3/2 to get 2.5 and use that as its path. Then, if I wanted to
add a node between 2.5 and 3, I would do 2.5+3/2=2,75 and the tree would
look like this:
[1]
|
--------------------------------
| | | |
[2] [2,5] [2,75] [3]
The paths for 2 and 3, including all their child nodes would stay the
same. If there are more siblings on that level, then they would also be
intact with no change. However, this would be limited because there's a
finite number of decimals. And there is another problem. If I now want
to move 2.75 before 2.5, then I would do 2+2,5/2=2.25. The first level
below the root would now be [2, 2.25, 2.5, 3], but since 2.75 is now
called 2.25, I would also need to update the paths of all nodes under
it. This would also mean that the tree would be in an inconsistent state
between updating 2.75 itself and the updates to its child nodes. If
there is a large number of elements, then this can take a considerable
amount of time.
So, the current idea (that I got from Lena Herrman) is that each element
only points to its direct parent and to its next sibling. That way, any
operation would only require two writes, regardless of the size of the tree:
[1]
|
-----------------------------
| |
[2] [3]
| |
--------------- ------------
| | | |
[4] [5] [6] [7]
(Yes, same tree, just repeated for your convenience:))
In this case, the JSON would look something like:
{"_id" : "uuid1", "label" : "1", "parent" : null, "next_sibling" : null,
"root_node" : true }
{"_id" : "uuid2", "label" : "2", "parent" : "uuid1", "next_sibling" :
"uuid3", "first_child" : true }
{"_id" : "uuid3", "label" : "3", "parent" : "uuid1", "next_sibling" : null }
{"_id" : "uuid4", "label" : "4", "parent" : "uuid2", "next_sibling" :
"uuid5", "first_child" :true }
{"_id" : "uuid5", "label" : "5", "parent" : "uuid2", "next_sibling" : null }
{"_id" : "uuid6", "label" : "6", "parent" : "uuid3", "next_sibling" :
"uuid7", "first_child" : true }
{"_id" : "uuid7", "label" : "7", "parent" : "uuid3", "next_sibling" : null }
So now, if I wanted to move 2 to 7, then I would do
{"_id" : "uuid2", "label" : "2", "parent" : "uuid7", "next_sibling" :
null, "first_child" : true }
{"_id" : "uuid3", "label" : "3", "parent" : "uuid1", "next_sibling":
null, "first_child": true }
If, instead, I wanted to move 5 before 4, then I would do
{"_id" : "uuid5", "label" : "5", "parent" : "uuid2", "next_sibling" :
"uuid4", "first_child" : true }
{"_id" : "uuid4", "label" : "4", "parent" : "uuid2", "next_sibling":
null, "first_child": false }
No other writes would be necessary, no matter what you do, or how large
the changes are. There are also no problems with decimals. You can
reorder the tree how many times you want. That is a huge improvement,
but it would still mean that the tree is broken between the first write
and the second. I think I can do this by adding a field that signifies
that the first is the beginning of an operation and that the second
write finishes it.
The problem is how to get the tree in an ordered state from the
database. I currently sort by root_node, then parent, then first_child.
This means I can always get the starting points quickly, but I'll have
to rebuild the tree on the client. It's not really a big problem, but if
I use the tree in one Python desktop app and one JavaScript browser app,
then I'll have to do that work twice. I would much rather do it on the
server so I could just loop through on the client. That would also
reduce the amount of work that is necessary.
It feels like there should be a better way to do it, but I can't really
get it to the front of my mind. :)
Jo-Erlend
