btpanel.java

The applet illustrates the behaviour of binary search trees, Searching and Sorting Algorithms, Self-

// Source File Name:   BTPanel.java

import java.awt.*;
import java.text.MessageFormat;
import java.util.Random;

class BTPanel extends Panel
    implements Runnable
{

    BTPanel(BTApplet applet)
    {
        this.applet = applet;
        engine = null;
        tree = new BSTree(1);
        treetop = new BTNode();
        pinball = new BTNode();
        pinfall = new BTNode();
        target = null;
        picknode = null;
        lastpick = null;
        rootnode = null;
        swapnode = null;
        lastnode = null;
        fallnode = null;
        order = 0;
        count = 0;
        rotatequeued = false;
        rotating = false;
        message = "Use controls to manage the Tree. ";
        animation = 0;
        xstep = 16;
        ystep = 32;
        speed = SPEED = 10;
        thinkcount = 48;
        thoughtful = false;
        direction = 1;
        classic = true;
        mute = false;
        factors = false;
        minmax = 1;
        tool = new BTTool(applet, 800);
        setToolState();
        setLayout(null);
        setSize(800, 340);
        treetop.setLocation(400, 56);
    }

    public synchronized void animateTree()
    {
        if(!tree.isEmpty())
        {
            if(classic)
                placeClassic(tree.getRoot());
            else
                placeOrdered(tree.getRoot());
            rotating = isRotating();
        }
        if(speed != 0)
        {
            switch(animation)
            {
            case 4: // '\004'
                animateFID();
                break;

            case 5: // '\005'
                animateTDA();
                break;

            case 1: // '\001'
                animateAVL();
                break;

            case 2: // '\002'
                animateSPL();
                break;

            case 3: // '\003'
                animateRBL();
                break;

            case 6: // '\006'
                animateSWP();
                break;
            }
            if(fallnode != null)
                if(!fallnode.arrived())
                    fallnode.fall(speed);
                else
                    fallnode = null;
        }
    }

    public void placeClassic(BTNode root)
    {
        int dx0 = 3 * xstep * tree.getDepth();
        root.setDestination(treetop);
        for(BTNode node = root; node != null; node = node.nextPrO())
        {
            for(BTNode leaf = node.firstPoO(); leaf != node; leaf = leaf.nextPoO())
            {
                BTNode parent = leaf.parent;
                int side = leaf.getSide();
                int depth = leaf.getDepth(root);
                int i = 0;
                int dx = dx0;
                for(; i < depth; i++)
                    dx /= 2;

                leaf.setDestination(node.x() + direction * side * dx, parent.y() + ystep);
            }

            if(node != picknode)
                node.retract(speed);
        }

    }

    public void placeOrdered(BTNode root)
    {
        root.setDestination(treetop);
        for(BTNode node = root; node != null; node = node.nextPrO())
        {
            for(BTNode leaf = node.firstPoO(); leaf != node; leaf = leaf.nextPoO())
            {
                BTNode parent = leaf.parent;
                leaf.setDestination(node.x() + direction * leaf.getWidth(node) * xstep, parent.y() + ystep);
            }

            if(node != picknode)
                node.retract(speed);
        }

    }

    public boolean isRotating()
    {
        BTNode node;
        for(node = tree.getRoot(); node != null; node = node.nextPrO())
            if(node.getMode() == 4)
                break;

        if(node != null)
        {
            if(!node.arrived())
                return true;
            node.resetRotate();
        }
        return false;
    }

    public boolean isThinking()
    {
        return thoughtful && count++ < thinkcount;
    }

    public void stopThinking()
    {
        count = thinkcount;
    }

    public void discard(BTNode node)
    {
        fallnode = node;
        fallnode.setColor(node.getColor());
        fallnode.setDestination(node.x(), 366);
    }

    public BTNode remove(BTNode node)
    {
        discard(node);
        return tree.remove(node);
    }

    public BTNode rotate(BTNode node, int side)
    {
        BTNode child = node.getChild(-side);
        node.setRotate(4, side);
        child.setRotate(4, 0);
        return tree.rotate(node, side);
    }

    public void processEvent()
    {
        if(tree.isAVL())
            processAVL();
        else
        if(tree.isSPL())
            processSPL();
        else
        if(tree.isRBL())
            processRBL();
        else
            processBST();
    }

    public void processBST()
    {
        int emode = pinball.getEvent();
        if(emode == 0 || target == null)
        {
            stopProcess();
            return;
        }
        int pmode = pinball.getMode();
        int side = pinball.getBalance();
        if(pmode == 5 && emode == 105)
        {
            BTNode node = tree.add(target, side, pinball.getData());
            node.setLocation(target.x(), target.y());
            addMessage(node.getKey(), "{0} inserted. ", 2);
            stopProcess();
        } else
        if(pmode == 6 && emode == 104 || emode == 106)
        {
            if(target.hasTwoChildren())
            {
                startSWP();
            } else
            {
                addMessage(target.getKey(), "{0} deleted. ", 0);
                remove(target);
                stopProcess();
            }
        } else
        {
            stopProcess();
        }
    }

    public void processAVL()
    {
        int emode = pinball.getEvent();
        if(emode == 0 || target == null)
        {
            stopProcess();
            return;
        }
        int pmode = pinball.getMode();
        if(pmode == 5 && emode == 105)
        {
            int side = pinball.getBalance();
            BTNode node = tree.add(target, side, pinball.getData());
            node.setLocation(target.x(), target.y());
            addMessage(node.getKey(), "{0} inserted. ", 2);
            pinball.setEvent(101);
            startAVL();
        } else
        if(pmode == 6 && emode == 104 || emode == 106)
        {
            if(target.hasTwoChildren())
            {
                startSWP();
            } else
            {
                addMessage(target.getKey(), "{0} deleted. ", 0);
                pinball.setBalance(target.getSide());
                pinball.setEvent(102);
                target = remove(target);
                if(target != null)
                    startAVL();
                else
                    stopProcess();
            }
        } else
        {
            stopProcess();
        }
    }

    public void processSPL()
    {
        int emode = pinball.getEvent();
        int pmode = pinball.getMode();
        int side = pinball.getBalance();
        if(emode == 0 || target == null)
        {
            stopProcess();
            return;
        }
        if(pmode == 5 && emode == 105)
        {
            pinball.setMode(10);
            pinball.setEvent(5);
            pinfall.setData(pinball.getData());
            addMessage(target.getKey(), "Splaying {0}. ", 0);
            startSPL();
        } else
        if(pmode == 10 && emode == 5)
        {
            pinball.setMode(5);
            pinball.setEvent(101);
            pinball.setData(pinfall.getData());
            pinball.setLocation(treetop.x(), 13);
            addMessage(target.getKey(), "Split at {0}. ", 1);
            target = tree.splitinsert(pinball.getData());
            target.setLocation(treetop);
            target.setFlag(100);
            startSPL();
        } else
        if(pmode == 5 && emode == 101)
        {
            addMessage(target.getKey(), "{0} inserted. ", 2);
            target.setFlag(0);
            stopProcess();
        } else
        if(pmode == 6 && emode == 104)
        {
            pinball.setMode(10);
            pinball.setEvent(6);
            addMessage(target.getKey(), "Splaying {0}. ", 0);
            startSPL();
        } else
        if(pmode == 10 && emode == 6)
        {
            BTNode node = tree.getSuccessor(target, minmax);
            if(node == null)
            {
                addMessage(target.getKey(), "{0} deleted. ", 2);
                remove(target);
                stopProcess();
            } else
            {
                addMessage(target.getKey(), "{0} splayed. ", 0);
                addMessage(target.getKey(), "{0} deleted. ", 2);
                rootnode = target;
                discard(rootnode);
                rootnode.setFlag(100);
                target = node;
                addMessage(target.getKey(), "Splaying {0}. ", 0);
                pinball.setMode(6);
                pinball.setEvent(102);
                startSPL();
            }
        } else
        if(pmode == 6 && emode == 102)
        {
            BTNode node = rootnode.getChild();
            addMessage(target.getKey(), "{0} splayed. ", 0);
            tree.remove(rootnode);
            if(node != null)
                addMessage(target.getKey() + "-" + node.getKey(), "Join {0}. ", 2);
            stopProcess();
        } else
        if(pmode == 10 && emode == 107)
        {
            addMessage(pinball.getKey(), "{0} splayed. ", 0);
            stopProcess();
        } else
        {
            pinball.setData(target.getData());
            pinball.setMode(10);
            pinball.setEvent(107);
            addMessage(target.getKey(), "Splaying {0}. ", 0);
            startSPL();
        }
    }

    public void processRBL()
    {
        int emode = pinball.getEvent();
        int pmode = pinball.getMode();
        if(emode == 0 || target == null)
        {
            stopProcess();
            return;
        }
        if(pmode == 5 && emode == 105)
        {
            int side = pinball.getBalance();
            BTNode node = tree.add(target, side, pinball.getData());
            node.setLocation(target.x(), target.y());
            node.setColor(1);
            target = node;
            addMessage(node.getKey(), "{0} inserted. ", 2);
            pinball.setEvent(101);
            startRBL();
        } else
        if(pmode == 6 && emode == 104 || emode == 106)
        {
            if(target.hasTwoChildren())
            {
                startSWP();
            } else
            {
                addMessage(target.getKey(), "{0} deleted. ", 0);
                pinball.setBalance(target.getSide());
                int color = target.getColor();
                pinball.setEvent(102);
                target = remove(target);
                if(target == null)
                {
                    target = tree.getRoot();
                    if(target != null)
                        target.setColor(2);
                    stopProcess();
                } else
                if(color == 2)
                    startRBL();
                else
                    stopProcess();
            }
        } else
        {
            stopProcess();
        }
    }

    public void stopProcess()
    {
        animation = 0;
        pinball.reset();
    }

    public synchronized void animateFID()
    {
        int x = target.x();
        int y = target.y();
        if(thoughtful)
            y -= 26;
        if(!pinball.arrivedTo(x, y))
        {
            pinball.moveTo(x, y, speed);
            return;
        }
        int mode = pinball.getMode();
        BTData data = pinball.getData();
        BTNode node;
        if(tree.isEmpty() && mode == 5)
        {
            node = tree.insert(data);
            node.setLocation(treetop.x(), treetop.y());
            displayMessage(node.getKey(), "New root {0} created. ", 2);
            stopFID();
            return;
        }
        if(thoughtful)
        {
            pinball.push(0, -6);
            target.push(0, 6);
            if(count++ < 1)
                return;
        } else
        {
            target.hitWith(pinball);
        }
        int side = target.compareSide(data);
        node = target.getChild(side);
        switch(mode)
        {
        default:
            break;

        case 4: // '\004'
            if(node == target)
            {
                addMessage(data.getKey(), "{0} found. ", 2);
                pinball.setEvent(104);
                processEvent();
                break;
            }
            if(node == null)
            {
                addMessage(data.getKey(), "{0} not found. ", 3);
                pinball.setEvent(105);
                processEvent();
            } else
            {
                displayMessage(data.getKey(), "Locating {0}. ", 1);
                target = node;
                continueFID();
            }
            break;

        case 5: // '\005'
            if(node == target)
            {
                addMessage(data.getKey(), "{0} already exists. ", 3);
                pinball.setEvent(104);
                processEvent();
                break;
            }
            if(node == null)
            {
                pinball.setEvent(105);
                pinball.setBalance(side);
                processEvent();
            } else