 |
AppletTalk.com
Java discussions newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Alex
Guest
|
 Posted: Thu Sep 21, 2006 8:17 pm Post subject: Specific Cloning Question |
 |
|
Hi,
I have a rather specific question to do with cloning. I am trying to
write a program which involves tree-like data. The trees consist of
nodes, and each node has a reference to its parent node and any child
nodes it has (this is a binary tree so either 2 or 0 children).
Now, during the program I want to make a change to my tree, test some
condition on it and then either keep the changed tree or go back to the
old tree. It seemed to me that a reasonably simple way to do this would
be to clone the tree, then change the clone. If I accept the new tree
that's fine, if I don't I still have the original unchanged one.
However, cloning my trees has so far proved impossible for me. Every
time I try to do it I get exceptions (usually null pointer exceptions).
I am not sure how to go about cloning the structure that has references
to other things which themselves reference other things and so on.
I realise it is hard to help without seeing the code but I am looking
for general advice on whether cloning is a sensible way to achieve what
I want. If so...how do you go about it? If you think you can help I am
happy to send you my code but it seems silly to post it all here as
it's quite big.
Thanks
Alex |
|
| Back to top |
|
 |
Oliver Wong
Guest
|
| Posted: Thu Sep 21, 2006 8:46 pm Post subject: Re: Specific Cloning Question |
|
|
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158851851.624976.93170 (AT) h48g2000cwc (DOT) googlegroups.com...
| Quote: | Hi,
I have a rather specific question to do with cloning. I am trying to
write a program which involves tree-like data. The trees consist of
nodes, and each node has a reference to its parent node and any child
nodes it has (this is a binary tree so either 2 or 0 children).
Now, during the program I want to make a change to my tree, test some
condition on it and then either keep the changed tree or go back to the
old tree. It seemed to me that a reasonably simple way to do this would
be to clone the tree, then change the clone. If I accept the new tree
that's fine, if I don't I still have the original unchanged one.
However, cloning my trees has so far proved impossible for me. Every
time I try to do it I get exceptions (usually null pointer exceptions).
I am not sure how to go about cloning the structure that has references
to other things which themselves reference other things and so on.
I realise it is hard to help without seeing the code but I am looking
for general advice on whether cloning is a sensible way to achieve what
I want. If so...how do you go about it? If you think you can help I am
happy to send you my code but it seems silly to post it all here as
it's quite big.
|
Have you considered using recursion to clone your tree?
- Oliver |
|
| Back to top |
|
|
Thomas Weidenfeller
Guest
|
| Posted: Thu Sep 21, 2006 9:10 pm Post subject: Re: Specific Cloning Question |
|
|
Alex wrote:
| Quote: | I realise it is hard to help without seeing the code
|
It is actually a waste of our time.
| Quote: | but I am looking
for general advice on whether cloning is a sensible way to achieve what
I want.
|
No, it is not.
How do I know? I don't, I am just guessing, because you haven't shown us
how you do things, haven't given us important information like the size
of the tree or the complexity of the operations you intend to do on the
clone and you eventually want to undo.
The reason why I still say it is not a sensible way is because you have
not devised (or not told us) a sensible way of what should happen if you
are satisfied with the changes to the clone and you decide to keep the
cloned tree. Then you might have to "magically" change references to the
old tree all over your program. Might, because we don't know your
program. That's manageable with another level of indirection, but
without you mentioning it, and without seeing your code I simply state
cloning is not a good idea in this case.
| Quote: | If so...how do you go about it? If you think you can help I am
happy to send you my code but it seems silly to post it all here as
it's quite big.
|
If you can't be bothered to invest some time to cut down your code to
some useful demo of the problem, and if you can't be bothered to even
copy the exception error messages verbatim, why should we invest our
time to second-guess? Is your time more valuable than ours?
/Thomas
--
The comp.lang.java.gui FAQ:
http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq |
|
| Back to top |
|
|
Alex
Guest
|
| Posted: Fri Sep 22, 2006 3:14 pm Post subject: Re: Specific Cloning Question |
|
|
Thomas Weidenfeller wrote:
| Quote: | Alex wrote:
I realise it is hard to help without seeing the code
It is actually a waste of our time.
but I am looking
for general advice on whether cloning is a sensible way to achieve what
I want.
No, it is not.
How do I know? I don't, I am just guessing, because you haven't shown us
how you do things, haven't given us important information like the size
of the tree or the complexity of the operations you intend to do on the
clone and you eventually want to undo.
The reason why I still say it is not a sensible way is because you have
not devised (or not told us) a sensible way of what should happen if you
are satisfied with the changes to the clone and you decide to keep the
cloned tree. Then you might have to "magically" change references to the
old tree all over your program. Might, because we don't know your
program. That's manageable with another level of indirection, but
without you mentioning it, and without seeing your code I simply state
cloning is not a good idea in this case.
If so...how do you go about it? If you think you can help I am
happy to send you my code but it seems silly to post it all here as
it's quite big.
If you can't be bothered to invest some time to cut down your code to
some useful demo of the problem, and if you can't be bothered to even
copy the exception error messages verbatim, why should we invest our
time to second-guess? Is your time more valuable than ours?
/Thomas
--
The comp.lang.java.gui FAQ:
http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
|
Clearly I don't think my time is more valuable and you are perfectly
welcome to not spent time replying. My point was simply that if someone
has the time to help me then I would be able to provide more in depth
detail. It seems rather unhelpful and rude to respond in this way.
In answer to some of your questions:
1) Size: The number of leaves in the tree may vary between small (i.e
3/4 to possibly quite large 20+)
2) Operations: The sort of operations is not clear cut yet. Probably
there will be subtree prune and regraft type operations and simple
changing of the lengths of branches within the tree
3) If I am satisfied with the new tree can I not simple set the old
tree equal to the new tree?
The reason I have not managed to cut down the program is that I am not
sure how to do that without losing the complexity that is causing the
problem. I have made smaller versions of things and tried cloning
things that contain lists of references but I don't seem to get the
problems in these oversimplified examples.
Anyway, if your time is too valuable there is no pressure on you or
anyone else to help or to even read this. However, I fail to see that
there is much harm in asking, just in case someone out there knows how
to help and has some time to do it.
Thanks,
Alex |
|
| Back to top |
|
|
Oliver Wong
Guest
|
| Posted: Fri Sep 22, 2006 7:08 pm Post subject: Re: Specific Cloning Question |
|
|
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158920061.757641.292170 (AT) k70g2000cwa (DOT) googlegroups.com...
| Quote: |
3) If I am satisfied with the new tree can I not simple set the old
tree equal to the new tree?
|
Probably not. You can't "set" an object. You can set the value of a
reference (i.e. to point to the new tree instead of the old tree), but that
will not update all the other references to the old tree.
There are more time-optimal ways of doing this, but without further
information, the best I can come up with is to clone the tree, apply the
operation on the clone, test if it satisfies whatever you want, and if it
does, re-apply the operation on the old tree. Discard the clone in either
cases.
| Quote: |
The reason I have not managed to cut down the program is that I am not
sure how to do that without losing the complexity that is causing the
problem. I have made smaller versions of things and tried cloning
things that contain lists of references but I don't seem to get the
problems in these oversimplified examples.
|
What's this about "lists of references"? This is the first time you
mention it, AFAIK. Previously you said only that the tree has a reference to
its parent, and its children. Being a binary tree, this means exactly 3
references in every node.
| Quote: |
Anyway, if your time is too valuable there is no pressure on you or
anyone else to help or to even read this. However, I fail to see that
there is much harm in asking, just in case someone out there knows how
to help and has some time to do it.
|
Have you considered a recursive solution?
- Oliver |
|
| Back to top |
|
|
Alex
Guest
|
| Posted: Fri Sep 22, 2006 7:16 pm Post subject: Re: Specific Cloning Question |
|
|
Oliver Wong wrote:
| Quote: | "Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158920061.757641.292170 (AT) k70g2000cwa (DOT) googlegroups.com...
3) If I am satisfied with the new tree can I not simple set the old
tree equal to the new tree?
Probably not. You can't "set" an object. You can set the value of a
reference (i.e. to point to the new tree instead of the old tree), but that
will not update all the other references to the old tree.
There are more time-optimal ways of doing this, but without further
information, the best I can come up with is to clone the tree, apply the
operation on the clone, test if it satisfies whatever you want, and if it
does, re-apply the operation on the old tree. Discard the clone in either
cases.
The reason I have not managed to cut down the program is that I am not
sure how to do that without losing the complexity that is causing the
problem. I have made smaller versions of things and tried cloning
things that contain lists of references but I don't seem to get the
problems in these oversimplified examples.
What's this about "lists of references"? This is the first time you
mention it, AFAIK. Previously you said only that the tree has a reference to
its parent, and its children. Being a binary tree, this means exactly 3
references in every node.
Anyway, if your time is too valuable there is no pressure on you or
anyone else to help or to even read this. However, I fail to see that
there is much harm in asking, just in case someone out there knows how
to help and has some time to do it.
Have you considered a recursive solution?
- Oliver
|
No,
The trees consist of nodes, and each node has a reference to its parent
and children. Each tree is made up of lots of nodes, hence a list of
them.
Sorry if that was unclear.
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
Alex |
|
| Back to top |
|
|
Oliver Wong
Guest
|
| Posted: Fri Sep 22, 2006 9:56 pm Post subject: Re: Specific Cloning Question |
|
|
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158934564.874336.109020 (AT) m7g2000cwm (DOT) googlegroups.com...
| Quote: |
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
|
If you only clone in "one direction", you can avoid this problem. For
example, cloning a node Foo wil clone it, and all of its children, but none
of its parents.
Alternatively, you could wrap all your nodes in an actual Tree object,
and put a clone method on the tree, and not on any of the nodes themselves,
and have the tree orchestrating the cloning of the nodes.
- Oliver |
|
| Back to top |
|
|
Alex
Guest
|
| Posted: Mon Sep 25, 2006 3:45 pm Post subject: Re: Specific Cloning Question |
|
|
Oliver Wong wrote:
| Quote: | "Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158934564.874336.109020 (AT) m7g2000cwm (DOT) googlegroups.com...
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
If you only clone in "one direction", you can avoid this problem. For
example, cloning a node Foo wil clone it, and all of its children, but none
of its parents.
Alternatively, you could wrap all your nodes in an actual Tree object,
and put a clone method on the tree, and not on any of the nodes themselves,
and have the tree orchestrating the cloning of the nodes.
- Oliver
|
Ok, so I think it's the second thing that I have tried to do. But the
problem is I still need to clone the actual nodes otherwise the cloned
tree with have references to the same original nodes and when I change
one, it will change the other. And it's the cloning of the nodes that
seems to cause the problem.
With the first suggestion, it sounds good. I am not entirely sure how
to work my way down the tree from the top and make sure I clone all
nodes since at each point, we branch and have two more nodes to clone.
I guess if the tree isn't too big it's not too bad to keep a list of
things that need to be cloned. Any idea?
Alex |
|
| Back to top |
|
|
Oliver Wong
Guest
|
| Posted: Mon Sep 25, 2006 6:57 pm Post subject: Re: Specific Cloning Question |
|
|
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1159181125.560249.98400 (AT) b28g2000cwb (DOT) googlegroups.com...
| Quote: |
Oliver Wong wrote:
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158934564.874336.109020 (AT) m7g2000cwm (DOT) googlegroups.com...
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
If you only clone in "one direction", you can avoid this problem. For
example, cloning a node Foo wil clone it, and all of its children, but
none
of its parents.
Alternatively, you could wrap all your nodes in an actual Tree
object,
and put a clone method on the tree, and not on any of the nodes
themselves,
and have the tree orchestrating the cloning of the nodes.
- Oliver
Ok, so I think it's the second thing that I have tried to do. But the
problem is I still need to clone the actual nodes otherwise the cloned
tree with have references to the same original nodes and when I change
one, it will change the other. And it's the cloning of the nodes that
seems to cause the problem.
|
Right, when you ask the tree to clone itself, the new tree would scan
the old tree, perhaps in a depth first traversal, and recreate in itself the
exact same node structure (by creating entirely new nodes, not by
referencing the old existing nodes).
| Quote: |
With the first suggestion, it sounds good. I am not entirely sure how
to work my way down the tree from the top and make sure I clone all
nodes since at each point, we branch and have two more nodes to clone.
I guess if the tree isn't too big it's not too bad to keep a list of
things that need to be cloned. Any idea?
|
You don't need to keep an explicit list if you use a recursive solution
instead (I know, I'm beginning to sound like a broken record). There are (at
least) two ways to implement a tree structure. There's the one where "Tree"
is a seperate class which hosts a bunch of nodes (as above); and then
there's the one where there is no explicit "Tree" object, and every "Node"
is itself a tree, and trees can be sub-trees of other trees. So for example
the leaves themselves are trees (of height 0). If you use the latter
implementation, then you can implementing cloning a tree by recursively
cloning the subtrees, and then assembling them together into a bigger tree.
- Oliver |
|
| Back to top |
|
|
Alex
Guest
|
| Posted: Mon Sep 25, 2006 8:26 pm Post subject: Re: Specific Cloning Question |
|
|
Oliver Wong wrote:
| Quote: | "Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1159181125.560249.98400 (AT) b28g2000cwb (DOT) googlegroups.com...
Oliver Wong wrote:
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158934564.874336.109020 (AT) m7g2000cwm (DOT) googlegroups.com...
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
If you only clone in "one direction", you can avoid this problem. For
example, cloning a node Foo wil clone it, and all of its children, but
none
of its parents.
Alternatively, you could wrap all your nodes in an actual Tree
object,
and put a clone method on the tree, and not on any of the nodes
themselves,
and have the tree orchestrating the cloning of the nodes.
- Oliver
Ok, so I think it's the second thing that I have tried to do. But the
problem is I still need to clone the actual nodes otherwise the cloned
tree with have references to the same original nodes and when I change
one, it will change the other. And it's the cloning of the nodes that
seems to cause the problem.
Right, when you ask the tree to clone itself, the new tree would scan
the old tree, perhaps in a depth first traversal, and recreate in itself the
exact same node structure (by creating entirely new nodes, not by
referencing the old existing nodes).
With the first suggestion, it sounds good. I am not entirely sure how
to work my way down the tree from the top and make sure I clone all
nodes since at each point, we branch and have two more nodes to clone.
I guess if the tree isn't too big it's not too bad to keep a list of
things that need to be cloned. Any idea?
You don't need to keep an explicit list if you use a recursive solution
instead (I know, I'm beginning to sound like a broken record). There are (at
least) two ways to implement a tree structure. There's the one where "Tree"
is a seperate class which hosts a bunch of nodes (as above); and then
there's the one where there is no explicit "Tree" object, and every "Node"
is itself a tree, and trees can be sub-trees of other trees. So for example
the leaves themselves are trees (of height 0). If you use the latter
implementation, then you can implementing cloning a tree by recursively
cloning the subtrees, and then assembling them together into a bigger tree.
- Oliver
|
Thanks, this makes a lot of sense now. I shall have another go. Thanks
very much for your help!
Alex |
|
| Back to top |
|
|
Patricia Shanahan
Guest
|
| Posted: Mon Sep 25, 2006 8:28 pm Post subject: Re: Specific Cloning Question |
|
|
Alex wrote:
| Quote: | Oliver Wong wrote:
"Alex" <alexander.webb (AT) gmail (DOT) com> wrote in message
news:1158934564.874336.109020 (AT) m7g2000cwm (DOT) googlegroups.com...
I am not entirely sure what you mean by a "recursive solution". I have
tried cloning the tree by cloning all the nodes in it. However the
problem here is that when I try to clone Node A it has a reference to
Node B as its parent so Node B gets cloned. But when I am cloning Node
B, it has a reference to Node A as its child it goes back to trying to
clone A again.
If you only clone in "one direction", you can avoid this problem. For
example, cloning a node Foo wil clone it, and all of its children, but none
of its parents.
Alternatively, you could wrap all your nodes in an actual Tree object,
and put a clone method on the tree, and not on any of the nodes themselves,
and have the tree orchestrating the cloning of the nodes.
- Oliver
Ok, so I think it's the second thing that I have tried to do. But the
problem is I still need to clone the actual nodes otherwise the cloned
tree with have references to the same original nodes and when I change
one, it will change the other. And it's the cloning of the nodes that
seems to cause the problem.
With the first suggestion, it sounds good. I am not entirely sure how
to work my way down the tree from the top and make sure I clone all
nodes since at each point, we branch and have two more nodes to clone.
I guess if the tree isn't too big it's not too bad to keep a list of
things that need to be cloned. Any idea?
Alex
|
Here's a rough cut at one way of doing it, without explicit bookkeeping:
DANGER! DANGER! UNTESTED CODE AHEAD!
public MyNode subtreeCopy(MyNode root, MyNode parent){
if(root == null){
return null;
}
MyNode copy = new MyNode();
copy.parent = parent;
copy.left = subtreeCopy(root.left,copy);
copy.right = subtreeCopy(root.right,copy);
return copy;
}
public MyNode treeCopy(MyNode root){
return subtreeCopy(root,null);
}
This probably isn't exactly what you need, but if you get the idea, you
should be able to apply it to your problem.
Patricia |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
