Animate Change of color of nodes in insertion of b

Question

I already have implemented display of binary search tree . Here's the code , which paints the binary tree in a jpanel .

public void paint(Graphics g) {
    super.paint(g);
    System.out.println(" in paint");
    Graphics2D g2 = (Graphics2D) g;
    g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
            RenderingHints.VALUE_ANTIALIAS_ON);
    int num = bst.size;

    int y = 25;
    int nodes = 1;
    int level = 1;
    int length = getWidth();
    Queue<Node> q = new LinkedList<Node>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    q.add(bst.root);
    while (num > 0) {

        int pX = (int) Math.round(length / (2.0 * nodes));
        int x = pX;
        for (int i = 0; i < nodes; i++) {
            Node n = q.poll();
            //
            if (n != null) {
                num--;
                System.out.println(x);
                g2.setColor(Color.BLUE);
                String str = n.value + "";
                 System.out.println(str);
                //Font f = Font.getFont(str);
                int width = str.length();
                g2.setColor(Color.YELLOW);
                g2.fillOval(x, y, (30 - 2 * level)+width*3, (30 - 2 * level));
                g2.setColor(Color.black);
                g2.drawString(n.value + "", x + 10 - level, y + 15);
                g2.setColor(Color.black);
                if (n.left == null)
                    q.add(null);
                else
                    q.add(n.left);
                if (n.right == null)
                    q.add(null);
                else
                    q.add(n.right);
                if (level != 1) {
                    int xx = q2.poll();
                    int yy = q2.poll();
                    g2.drawLine(xx+width*2, yy, x + (15 - 1 * level)+width*2, y);
                }
            } else {
                q2.poll();
                q2.poll();
                q.add(null);
                q.add(null);
            }
            q2.add(x);
            q2.add(y + 15 - level);
            q2.add(x + 30 - 2 * level);
            q2.add(y + 15 - level);
            x += 2 * pX;

        }
        y += 40;
        nodes = 1 << level;
        level++;
    }

Now as i insert nodes into my tree , I want the parent nodes to change color of the new node progressively , and then ultimate join as a child . or the new node to be inserted moves along the path of it's parent . or something similar Here's an example :

I have no idea how to accomplish that , with timer or likewise .

Answer 1

Conceptually, if each node should have a specific color then each Node instance should have a Color attribute. In the example cited here, the class Node has a number of static updateXxx() methods that traverse the program's (simpler) model, updating nodes as specified. In particular, updateColor() sets each element's Color field to the specified color. Your implementation of paintComponent() can do something similar.

Addendum: As @MadP comments, javax.swing.Timer is well suited to periodic GUI updates, as the timer's actionPerformed() method is executed on the EDT. In this example, the model is updated with each invocation, and the new state is rendered when repaint() (indirectly) calls paintComponent().

Answer 2

Okay, this took a little longer then I wanted (10 month olds don't have any patience)

The basic concept revolves around the idea that you need to change from one state to another over a period of time.

Given a start time and the current time, we can calculate the amount of time that the animation has been running, and given the total animation time, the current progress.

With this (and some clever maths) we can calculate the current state from our start state towards our target state.

I've done movement as well, so that may be a little over kill, but the basic premise remains the same.

I place stateful information about the nodes that need to change in animation properties class and use a javax.swing.Timer to tick over the animation (at a reasonably steady rate). I then update the state of each node as required and repaint the screen.

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.text.NumberFormat;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import javax.management.StringValueExp;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.Timer;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class AnimateNode {

    public static void main(String[] args) {
        new AnimateNode();
    }

    public AnimateNode() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new NodePane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }

        });
    }

    public interface Node {
        public void paint(JComponent parent, Graphics2D g2d);
        public void setColor(Color color);
        public Color getColor();
        public Node getParent();
        public Node getLeft();
        public Node getRight();
        public void setLeftNode(Node node);
        public void setRightNode(Node node);
        public Point getLocation();
        public void setLocation(Point p);
    }

    public class DefaultNode implements Node {

        private int number;
        private Node parent;
        private Node left;
        private Node right;
        private Point location;
        private Color color;

        public DefaultNode(int number, Node parent) {
            this.parent = parent;
            color = UIManager.getColor("Panel.background");
            this.number = number;
        }

        public void setLeftNode(Node left) {
            this.left = left;
        }

        public void setRightNode(Node right) {
            this.right = right;
        }

        public Node getParent() {
            return parent;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        @Override
        public Point getLocation() {
            return location;
        }

        @Override
        public void setLocation(Point location) {
            this.location = location;
        }

        @Override
        public void paint(JComponent parent, Graphics2D g2d) {

            FontMetrics fm = g2d.getFontMetrics();
            int radius = fm.getHeight();

            Point p = getLocation();

            int x = p.x - (radius / 2);
            int y = p.y - (radius / 2);

            Ellipse2D node = new Ellipse2D.Float(x, y, radius, radius);

            g2d.setColor(getColor());
            g2d.fill(node);

            g2d.setColor(Color.GRAY);
            g2d.draw(node);

            String text = String.valueOf(number);
            x = x + ((radius - fm.stringWidth(text)) / 2);
            y = y + (((radius - fm.getHeight()) / 2) + fm.getAscent());

            g2d.drawString(text, x, y);

        }

        @Override
        public void setColor(Color color) {
            this.color = color;
        }

        @Override
        public Color getColor() {
            return color;
        }

        @Override
        public String toString() {
            return number + " @ " + getLocation();
        }

    }

    public class AnimationProperties {

        private Point startPoint;
        private Point targetPoint;
        private Color startColor;
        private Color endColor;
        private Node node;

        public AnimationProperties(Node node) {
            this.node = node;
        }

        public Node getNode() {
            return node;
        }

        public void setTargetColor(Color endColor) {
            this.endColor = endColor;
        }

        public void setStartColor(Color startColor) {
            this.startColor = startColor;
        }

        public void setStartPoint(Point startPoint) {
            this.startPoint = startPoint;
        }

        public void setTargetPoint(Point targetPoint) {
            this.targetPoint = targetPoint;
        }

        public Color getTargetColor() {
            return endColor;
        }

        public Color getStartColor() {
            return startColor;
        }

        public Point getStartPoint() {
            return startPoint;
        }

        public Point getTargetPoint() {
            return targetPoint;
        }

        public Point getLocation(float progress) {
            return calculateProgress(getStartPoint(), getTargetPoint(), progress);
        }

        public Color getColor(float progress) {
            return blend(getStartColor(), getTargetColor(), 1f - progress);
        }

        public void update(float progress) {
            node.setLocation(getLocation(progress));
            node.setColor(getColor(progress));
        }

    }

    public class NodePane extends JPanel {

        private int number;
        private Node root;
        private Map<Node, AnimationProperties> aniProperties;
        private Timer animationTimer;
        private Timer startTimer;
        private long startTime;
        private int runTime = 1000;

        public NodePane() {
            aniProperties = new HashMap<>(25);

            root = addLeftNode(null);
            root.setColor(getBackground());
            addMouseListener(new MouseAdapter() {
                private Random rand;

                @Override
                public void mouseClicked(MouseEvent e) {
                    generateNextNode(root);
                    revalidate();
//                    repaint();
                }

                protected void generateNextNode(Node parent) {
                    Node child = null;
                    if (rand == null) {
                        rand = new Random(System.currentTimeMillis());
                    }
                    boolean left = rand.nextBoolean();
                    if (left) {
                        child = parent.getLeft();
                    } else {
                        child = parent.getRight();
                    }

                    if (child == null) {
                        if (left) {
                            addLeftNode(parent);
                        } else {
                            addRightNode(parent);
                        }
                    } else {
                        generateNextNode(child);
                    }
                }

            });

            startTimer = new Timer(250, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    stopAnimation();
                    startTime = -1;
                    animationTimer.start();
                }

            });
            startTimer.setRepeats(false);

            animationTimer = new Timer(40, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    if (startTime < 0) {
                        startTime = System.currentTimeMillis();
                    }
                    float progress = 1f;
                    long duration = System.currentTimeMillis() - startTime;
                    if (duration >= runTime) {
                        ((Timer) e.getSource()).stop();
                    } else {
                        progress = (float) duration / (float) runTime;
                    }

                    for (AnimationProperties ap : aniProperties.values()) {
                        ap.update(progress);
                    }

                    repaint();

                    if (progress == 1f) {
                        aniProperties.clear();
                    }

                }

            });
            animationTimer.setRepeats(true);
            animationTimer.setCoalesce(true);
        }

        protected void stopAnimation() {
            if (animationTimer.isRunning()) {
                animationTimer.stop();
                for (AnimationProperties ap : aniProperties.values()) {
                    Node node = ap.getNode();
                    ap.setStartColor(node.getColor());
                    ap.setStartPoint(node.getLocation());
                }
            }
        }

        public Point getStartPoint(Node node) {

            Point startPoint = node.getLocation();
            while (startPoint == null) {
                node = node.getParent();
                startPoint = node.getLocation();
            }

            return startPoint;

        }

        protected void layoutNode(Node node, int x, int y) {

            if (node != null) {

                FontMetrics fm = getFontMetrics(getFont());
                int nodeHeight = fm.getHeight();

                if (node.getParent() != null) {

                    Point p = new Point(x, y);
                    Point sp = getStartPoint(node);

                    if (node.getLocation() == null) {
                        System.out.println("new node " + node);
                    }

                    if (node.getLocation() == null || !p.equals(node.getLocation())) {
                        AnimationProperties ap = new AnimationProperties(node);
                        ap.setStartColor(node.getColor());
                        ap.setTargetColor(getBackground());
                        ap.setStartPoint(sp);
                        ap.setTargetPoint(new Point(x, y));
                        node.setLocation(sp);
                        aniProperties.put(node, ap);
                        System.out.println("New Node to " + node);
                    } else {
                        aniProperties.remove(node);
                    }

                } else {

                    nodeHeight *= 2;

                }

                layoutNode(node.getLeft(), x - nodeHeight, y + nodeHeight);
                layoutNode(node.getRight(), x + nodeHeight, y + nodeHeight);

            }

        }

        @Override
        public void doLayout() {

            System.out.println("DoLayout");
            stopAnimation();

            FontMetrics fm = getFontMetrics(getFont());
            int nodeHeight = fm.getHeight();

            int x = getWidth() / 2;
            int y = nodeHeight;

            if (root != null) {

                root.setLocation(new Point(x, y));
                layoutNode(root, x, y);
//                Node node = root.getLeft();
//                while (node != null) {
//                    x -= nodeHeight;
//                    y += nodeHeight;
//                    layout(node, x, y);
//                    node = node.getLeft();
//                }
//                node = root.getRight();
//                x = getWidth() / 2;
//                y = nodeHeight;
//                while (node != null) {
//                    x += nodeHeight;
//                    y += nodeHeight;
//                    layout(node, x, y);
//                    node = node.getRight();
//                }

            }

            startTimer.restart();

        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        protected Node createNode(Node parent) {
            DefaultNode child = new DefaultNode(++number, parent);
            child.setColor(Color.GREEN);
            System.out.println("Create new node " + child);
            return child;
        }

        protected Node addLeftNode(Node parent) {
            Node node = createNode(parent);
            if (parent != null) {
                System.out.println("Add " + node + " to left of " + parent);
                parent.setLeftNode(node);
            }
            return node;
        }

        protected Node addRightNode(Node parent) {
            Node node = createNode(parent);
            if (parent != null) {
                System.out.println("Add " + node + " to right of " + parent);
                parent.setRightNode(node);
            }
            return node;
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            if (root != null) {

                Graphics2D g2d = (Graphics2D) g.create();

                paintConnectors(root, g2d);
                paintNode(root, g2d);

                g2d.dispose();

            }

        }

        protected void paintNode(Node node, Graphics2D g2d) {
            if (node != null && node.getLocation() != null) {
                node.paint(this, g2d);
                paintNode(node.getLeft(), g2d);
                paintNode(node.getRight(), g2d);
            }
        }

        protected void paintConnectors(Node node, Graphics2D g2d) {
            if (node != null && node.getLocation() != null) {
                Node parent = node.getParent();
                if (parent != null) {
                    g2d.setColor(Color.GRAY);
                    if (parent.getLocation() != null && node.getLocation() != null) {
                        g2d.draw(new Line2D.Float(parent.getLocation(), node.getLocation()));
                    }
                }

                paintConnectors(node.getLeft(), g2d);
                paintConnectors(node.getRight(), g2d);
            }
        }

    }

    public static Point calculateProgress(Point startPoint, Point targetPoint, double progress) {

        Point point = new Point();

        if (startPoint != null && targetPoint != null) {

            point.x = calculateProgress(startPoint.x, targetPoint.x, progress);
            point.y = calculateProgress(startPoint.y, targetPoint.y, progress);

        }

        return point;

    }

    public static int calculateProgress(int startValue, int endValue, double fraction) {

        int value = 0;
        int distance = endValue - startValue;
        value = (int) Math.round((double) distance * fraction);
        value += startValue;

        return value;

    }

    public static Color calculateProgress(Color start, Color target, double progress) {

        return blend(start, target, progress);

    }

    public static Color blend(Color color1, Color color2, double ratio) {
        float r = (float) ratio;
        float ir = (float) 1.0 - r;

        float rgb1[] = new float[3];
        float rgb2[] = new float[3];

        color1.getColorComponents(rgb1);
        color2.getColorComponents(rgb2);

        float red = rgb1[0] * r + rgb2[0] * ir;
        float green = rgb1[1] * r + rgb2[1] * ir;
        float blue = rgb1[2] * r + rgb2[2] * ir;

        if (red < 0) {
            red = 0;
        } else if (red > 255) {
            red = 255;
        }
        if (green < 0) {
            green = 0;
        } else if (green > 255) {
            green = 255;
        }
        if (blue < 0) {
            blue = 0;
        } else if (blue > 255) {
            blue = 255;
        }

        Color color = null;
        try {

            color = new Color(red, green, blue);

        } catch (IllegalArgumentException exp) {

            NumberFormat nf = NumberFormat.getNumberInstance();
            System.err.println(nf.format(red) + "; " + nf.format(green) + "; " + nf.format(blue));

        }
        return color;
    }

}

Update with simple example ;)

Okay, this is a simple example. Basically, it just blinks the node...

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Ellipse2D;
import java.text.NumberFormat;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;

public class BlinkNode {

    public static void main(String[] args) {
        new BlinkNode();
    }

    public BlinkNode() {
        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException | InstantiationException | IllegalAccessException | UnsupportedLookAndFeelException ex) {
                }

                JFrame frame = new JFrame("Testing");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(new TestPane());
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public class TestPane extends JPanel {

        // Animation stuff
        private Timer aniTimer;
        // The amount of time that each animation cycle plays for 
        // in millis
        private int aniRunTime = 1000;
        // The time the animation was started
        private long startTime = -1;

        // Our color ranges, where to start and where
        // we want to get to and the current state...
        private Color startColor;
        private Color targetColor;
        private Color color;

        public TestPane() {
            // Initial state
            startColor = getBackground();
            targetColor = Color.GREEN;
            color = startColor;
            aniTimer = new Timer(40, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    // Set the start time it hasn't already
                    if (startTime < 0) {
                        startTime = System.currentTimeMillis();
                    }
                    // We're always finished if we run over time...
                    float progress = 1f;
                    // Calculate the duration of play
                    long duration = System.currentTimeMillis() - startTime;
                    // Have we reached the end yet??
                    if (duration >= aniRunTime) {
                        // Reset the start time, this allows the 
                        // animation to cycle.  Normally you would stop
                        // the timer, see the previous example
                        startTime = -1;
                        // Swap the start and target colors...
                        Color tmp = startColor;
                        startColor = targetColor;
                        targetColor = tmp;
                        color = startColor;
                    } else {
                        // Calculate the progress
                        progress = (float) duration / (float) aniRunTime;
                        // Blend the colors
                        color = blend(startColor, targetColor, 1f - progress);
                    }
                    // update the ui
                    repaint();
                }
            });
            aniTimer.setRepeats(true);
            aniTimer.setCoalesce(true);
            aniTimer.start();
        }

        @Override
        public Dimension getPreferredSize() {
            return new Dimension(200, 200);
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);
            Graphics2D g2d = (Graphics2D) g.create();

            int x = (getWidth() - 20) / 2;
            int y = (getHeight() - 20) / 2;
            g2d.setColor(color);
            Ellipse2D node = new Ellipse2D.Float(x, y, 20, 20);
            g2d.fill(node);
            g2d.setColor(Color.GRAY);
            g2d.draw(node);

            g2d.dispose();
        }
    }

    public static Color blend(Color color1, Color color2, double ratio) {
        float r = (float) ratio;
        float ir = (float) 1.0 - r;

        float rgb1[] = new float[3];
        float rgb2[] = new float[3];

        color1.getColorComponents(rgb1);
        color2.getColorComponents(rgb2);

        float red = rgb1[0] * r + rgb2[0] * ir;
        float green = rgb1[1] * r + rgb2[1] * ir;
        float blue = rgb1[2] * r + rgb2[2] * ir;

        if (red < 0) {
            red = 0;
        } else if (red > 255) {
            red = 255;
        }
        if (green < 0) {
            green = 0;
        } else if (green > 255) {
            green = 255;
        }
        if (blue < 0) {
            blue = 0;
        } else if (blue > 255) {
            blue = 255;
        }

        Color color = null;
        try {

            color = new Color(red, green, blue);

        } catch (IllegalArgumentException exp) {

            NumberFormat nf = NumberFormat.getNumberInstance();
            System.err.println(nf.format(red) + "; " + nf.format(green) + "; " + nf.format(blue));

        }
        return color;
    }
}