Deep copy an Expression tree

[strong escarp]

I want to deep copy an expression tree. I know the traditional way of doing it which works for the most part. Heres the basic version of the Expression tree:

    private Expression left;
    private String operator;
    private Expression right;
    private Expression parent;

    public Expression(Expression left, String operator, Expression right, Expression parent) {
        this.left = left;
        this.operator = operator;
        this.right = right;
        this.parent = parent;

        if (left != null) {
            left.setParent(this);
        }
        if (right != null) {
            right.setParent(this);
        }
    }

    // Other methods and functionalities...

    // Setters with parent update
    public void setLeft(Expression left) {
        this.left = left;
        if (left != null) {
            left.setParent(this);
        }
    }

    public void setRight(Expression right) {
        this.right = right;
        if (right != null) {
            right.setParent(this);
        }
    }

    // Other getters and setters...
}

```  Now the basic version of deep copying is as follows: ```public Expression copy() {
        Expression leftCopy = (left != null) ? left.copy() : null;
        Expression rightCopy = (right != null) ? right.copy() : null;
        
        return new Expression(leftCopy, operator, rightCopy, null);
    }``` Now this works nicely but I want another deep copy function which copies the parent hierarchy as well. The current deep copy only copies the expression and makes it the root regardless of if it was actually the root or not. Now how would I go about making a full deep copy function which would make sure the entire structure is copied including the parent hierarchy. I am fairly certain that this new deep copy function would make use of the previous one.

[hollow token]

⌛ This post has been reserved for your question.

Hey @strong escarp! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

[copper plume]

a copy constructor .......

public class Expression {
  public Expression(Extression toCopy) {
    ...
  }
}

pass the entire expression to copy it

its called a copy constructor ...... far better than trying to use the old school java native .clone() method

[strong escarp]

you cant use a copy constructor. this requires recursion

clone() performs shallow copy

[sudden ember]

Expression newExpression = ...;
leftCopy.setParent(newExpression);
rightCopy.setParent(newExpression);
return newExpression;

newExpression being the one you'd normally return

left and right copy as you already have

[copper plume]

if clone works at all.....

[sudden ember]

you don't seem to be using clone() in the above code

[strong escarp]

im sorry, can u put the entire function, so its clearer

[strong escarp]

i dont want to

it doesnt do what i want

[sudden ember]

public Expression copy() {
        Expression leftCopy = (left != null) ? left.copy() : null;
        Expression rightCopy = (right != null) ? right.copy() : null;
        
        Expression newExpression = new Expression(leftCopy, operator, rightCopy, null);
if(leftCopy != null) {
    leftCopy.setParent(newExpression);
}
if(rightCopy != null) {
    rightCopy.setParent(newExpression);
}
return newExpression;
}

sorry for the formatting

[copper plume]

if u can get clone to work at all.....

and it doesnt need recursion ....... in fact even though recursion is taught completely manically, its actually counter indicated to modern practices

ANYTHING u can do with recursion u can do with a for or while loop and a queue
and its actually more performant in a loop than recursion because CPU's need to preload cache data ahead of time and the recursion causes cache misses

[sudden ember]

sure you mean queue any not stack?

also when have multiple recursive calls in a method, it can get bit difficult when replacing recursion with loops

[copper plume]

Aaaaarrrrggghhhhhh
My Internet keeps cutting out

[copper plume]

Most languages implement a deque and just wrap it in a stack or queue interface as needed

So the differance between a stack and a queue is largely hypothetical

[sudden ember]

even if it's theoretical, there is a big difference

and Java has various implementations so it makes a big difference

if you use Queue, you don't have stack operations

[copper plume]

Recursion is used on directed graphs so any and all recursion can be replaced with BFS (or DFS which is what recursion replicates)

[sudden ember]

I said can be difficult, not impossible

and I see StackOverflowErrors as functionality in some cases

[copper plume]

DFS and BFS are designed for undirected graphs so it can handle any directed graph, and u don't even need an alrdy visited set because directed graphs can't go backwards

[sudden ember]

well if the recursive call is in some loop, it can get a bit ugly

[copper plume]

Yeah avoiding stack overflow is one reason why recursion is counter indicated these days.... But the reduction in cache misses by having more predictable code flow for prefetching data is the big reason

[sudden ember]

premature optimization os the root of all evil

don't optimize stuff that isn't a performance issue

[copper plume]

Loool, that's not premature optimisation, that's getting out of the way of the all powerful JIT and letting it do it's job

[sudden ember]

that is a premature optimization

[copper plume]

Is a naming scheme or abstraction or seperation of concerns 'premature optimisation'?

It's implementing best practices to let the tools do the hvy lifting for u

Best practices are best practices because they reduce the possibilities of needing to optimise/refactor/redo/etc in the first place

[strong escarp]

this is exactly what i already have lol. the leftCopy.setParent(newExpression) and rightCopy.setParent(newExpression) is already done when u call the new Expression() constructor. it takes care of that.

i am taking about the parent of the current expression.

the current expression's children have already been parented when u initialize the new Expression().

[sudden ember]

changing the code you write (especially at the cost of readability) in order for it to run faster without finding it being a hot spot using a profiler before

[copper plume]

sry @strong escarp we hijacked ur thread

[strong escarp]

nw lmao. at least its getting some action

[sudden ember]

ah ok

[sudden ember]

you could make 2 copy methods

[copper plume]

There is NOTHING readable about recursion

Most people need 10 reams of paper and more than 4 examples to work out wtf is happening in recursion

[sudden ember]

a private method that doesn't touch the parent

[strong escarp]

thats what I need. one standard copy() function which copies the expression and all its descendants. then another copyFull() function which does the standard copy() as well as copy all its parents.

[sudden ember]

and a public method that also takes cares avout the parent

for the public method, you could

• call the private method
• call a second private method that
  • recursively calls itself propagating to the parents
  • it finds the other child of the parent and makes a copy of that
  • then it makes a new parent with these two children copies

[strong escarp]

recursion isnt that bad. seems very readable to me

makes sense too. before I had the same view as you, but now im built different

[strong escarp]

yeah thats exactly what I have in mind. its the implementation that im stuck on.

[sudden ember]

I want to note my opinion: I don't like recursion in most cases but in some cases (where it feels more natural to me), I like it more

[copper plume]

i think the problem here is that even though u call the class Expression its actually just a node

and ur actual Expression is implicit, not explicit and thats why ur confused/concerned about copying the root node?

public class Expression {
  private class Node {
    Node parent;
    Node left;
    Node right;
  }

  Node root;
}

if u make an explicit Expression instead of just 'hoping' that u have the root node
ur deep copy will always start from the root and leave root as root

[strong escarp]

an expression is a root if its parent == null

[sudden ember]

private Expression createParentCopy(){
    if(parent == this || parent == null){
        return parent;
    }
    Expression newLeft = parent.left;
    if(newLeft != this){
        newLeft = newLeft
copyWithChildren();//the copy method ignoring parents
    }
    //do the same with right
    Expression parentCopy = new Expression(newLeft, operator, newRight, null);
    parentCopy.setParent(parent.createParentCopy());//you might need to do this with setLeft/setRight
}

[sudden ember]

maybe something like this?

for the second private method

[copper plume]

also the implicit expression is not OOP
ur exposing ur implementation details and allowing uncontrolled modifications of ur structure

[strong escarp]

thanks, i will try this

[hollow token]

If you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

[strong escarp]

what lol. this is a fairly common way of making an expression tree / ast.

[sudden ember]

I wrote this on my phone so it will probably not work 1:1

use it as a concept

[strong escarp]

for sure, thank you!

[hollow token]

💤 Post marked as dormant

This post has been inactive for over 300 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping.
Warning: abusing this will result in moderative actions taken against you.

[sudden ember]

have fun replacing this recursion with a loop and a stack

    private void deleteOldMessagesInChannel(TextChannel helpNotificationChannel, MessageHistory history, List<Message> foundSoFar) {
        history.retrievePast(50).queue(msgs -> {
            boolean deleteMore = addMessagesToDelete(foundSoFar, msgs);
            if (deleteMore) {
                deleteOldMessagesInChannel(helpNotificationChannel, history, foundSoFar);
            }else {
                helpNotificationChannel.purgeMessages(foundSoFar);
            }
        }, e -> {
            ExceptionLogger.capture(e, getClass().getName());
            helpNotificationChannel.purgeMessages(foundSoFar);
        });
    }

in a way that stays asynchronous xd

[copper plume]

well since that doesnt show the search criteria i cant even try
r u deleting all messages? the ones older than a day?
@sudden ember

[sudden ember]

essentially all messages from the self user in a specific time

but the only relevant thing is it being asynchronous

[copper plume]

as for how a simple loop should handle it just fine??
i mean all u need to delete messages is the message id right?
(i'm guessing this is JDA)

[sudden ember]

could also be

void myMethod(){
  runSomeTimeLaterAsynchronously(()->{
    if(ThreadLocalRandom.current().nextBoolean()){
      myMethod();
    }
  });
}

[sudden ember]

as I said, it should be asynchronously

that is the one interesting requirement

oh I didn't realize that one is a help post