btpanel.java

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

                break;
            }
            continueRBL();
        } else
        if(event == 102)
        {
            BTNode node = target.getChild(pinball.getBalance());
            if(node != null && node.getColor() == 1)
            {
                node.setColor(2);
                addMessage("", "P " + node.getKey() + "B. ", 0);
                stopRBL();
            } else
            {
                pinball.setParent(target);
                target = null;
                pinball.setEvent(112);
                continueRBL();
            }
        } else
        if(event == 112)
        {
            int side = 0;
            int mode = 0;
            if(target == tree.getRoot() || target != null && target.getColor() == 1)
            {
                target.setColor(2);
                addMessage("", "P " + target.getKey() + "B. ", 0);
                stopRBL();
                return;
            }
            BTNode parent;
            if(target == null)
            {
                parent = pinball.getParent();
                side = pinball.getBalance();
            } else
            {
                parent = target.getParent();
                side = target.getSide();
            }
            BTNode sibling = parent.getChild(-side);
            BTNode nephew = sibling.getChild(side);
            BTNode niece = sibling.getChild(-side);
            if(sibling.getColor() == 1)
                mode = 1;
            else
            if((nephew == null || nephew.getColor() == 2) && (niece == null || niece.getColor() == 2))
                mode = 2;
            else
            if((niece == null || niece.getColor() == 2) && nephew != null && nephew.getColor() == 1)
                mode = 3;
            else
            if(niece != null && niece.getColor() == 1)
                mode = 4;
            if(isThinking())
            {
                switch(mode)
                {
                case 1: // '\001'
                    sibling.setPaint(2);
                    parent.setPaint(1);
                    parent.setRotate(1, side);
                    break;

                case 2: // '\002'
                    sibling.setPaint(1);
                    break;

                case 3: // '\003'
                    sibling.setPaint(1);
                    nephew.setPaint(2);
                    sibling.setRotate(1, -side);
                    break;

                case 4: // '\004'
                    sibling.setPaint(parent.getColor());
                    parent.setPaint(2);
                    niece.setPaint(2);
                    parent.setRotate(1, side);
                    break;
                }
                return;
            }
            sibling.reset();
            parent.reset();
            if(nephew != null)
                nephew.reset();
            if(niece != null)
                niece.reset();
            switch(mode)
            {
            case 1: // '\001'
                sibling.setColor(2);
                parent.setColor(1);
                rotate(parent, side);
                addMessage("", "P " + sibling.getKey() + "B " + parent.getKey() + "R. ", 0);
                addMessage(parent.getKey(), "R {0} " + getSideName(side), 0);
                break;

            case 2: // '\002'
                sibling.setColor(1);
                target = target != null ? target.getParent() : parent;
                addMessage("", "P " + sibling.getKey() + "R. ", 0);
                break;

            case 3: // '\003'
                sibling.setColor(1);
                nephew.setColor(2);
                rotate(sibling, -side);
                addMessage("", "P " + sibling.getKey() + "R " + nephew.getKey() + "B. ", 0);
                addMessage(sibling.getKey(), "R {0} " + getSideName(-side), 0);
                break;

            case 4: // '\004'
                int color = parent.getColor();
                sibling.setColor(color);
                parent.setColor(2);
                niece.setColor(2);
                rotate(parent, side);
                target = tree.getRoot();
                addMessage("", "P " + parent.getKey() + "B " + sibling.getKey() + MSG.RBNAME[color] + niece.getKey() + "B. ", 0);
                addMessage(parent.getKey(), "R {0} " + getSideName(side), 0);
                break;
            }
            continueRBL();
        }
    }

    public void startRBL()
    {
        animation = 3;
        pinball.setMode(0);
        continueRBL();
    }

    public void continueRBL()
    {
        count = 0;
    }

    public void stopRBL()
    {
        animation = 0;
        pinball.setParent(null);
        pinball.reset();
    }

    public void paint(Graphics g)
    {
        bg.drawImage(backImage, 0, 0, null);
        drawLines(bg);
        drawNodes(bg);
        tool.draw(bg);
        bg.drawString(tool.getHelp(), tool.getHelpX(), tool.getHelpY());
        bg.drawString(message, 16, 324);
        g.drawImage(mainImage, 0, 0, null);
    }

    public void drawLines(Graphics g)
    {
        if(tree.isEmpty())
            return;
        BTNode root = tree.getRoot();
        BTNode leaf = root.firstPoO();
        if(!classic)
        {
            g.setColor(GRAYCOLOR);
            for(BTNode node = leaf; node != root; node = node.nextPoO())
                g.drawLine(node.x(), 1, node.x(), node.y());

        }
        g.setColor(Color.black);
        if(root.getFlag() != 100)
            g.drawLine(treetop.x(), 0, tree.root.x(), tree.root.y());
        for(BTNode node = leaf; node != root; node = node.nextPoO())
        {
            BTNode parent = node.getParent();
            if(parent.getFlag() != 100 && node.getFlag() != 100)
                g.drawLine(node.x(), node.y(), parent.x(), parent.y());
        }

    }

    public void drawNodes(Graphics g)
    {
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
            drawNode(g, node);

        if(fallnode != null)
            drawNode(g, fallnode);
        if(pinball.getMode() != 0)
            drawPinball(g, pinball);
        if(pinfall.getMode() != 0)
            drawPinball(g, pinfall);
    }

    public void drawNode(Graphics g, BTNode node)
    {
        int x = node.x();
        int y = node.y();
        int w = fm.stringWidth(node.getKey());
        int h = fm.getHeight();
        int mode = node.getMode();
        int color = node.getColor();
        int flag = node.getFlag();
        if(flag == 100)
            return;
        if(node == picknode)
            color = 3;
        drawBall(g, color, x, y);
        if(flag != 0)
            g.drawImage(applet.getCircle(flag), x - 18, y - 18, null);
        if(mode != 0)
            if(mode == 3)
                g.drawImage(applet.getCircle(3), x - 18, y - 18, null);
            else
            if(mode == 4)
            {
                int i = direction * node.getRSide();
                if(i != 0)
                    g.drawImage(applet.getArrow(i), x - 18, y - 18, null);
            } else
            if(mode == 1 || mode == 2)
            {
                int i = direction * node.getRSide();
                g.drawImage(applet.getArrow(i + 1), x - 18, y - 18, null);
                g.drawString(String.valueOf(mode), (x + i * 13) - 4, y - 13 - 2);
            }
        g.drawString(node.getKey(), x - w / 2, (y - h / 2) + fm.getAscent());
        if(factors)
        {
            int balance = node.getBalance();
            String s = String.valueOf(balance);
            if(balance > 0)
                s = "+" + s;
            g.setColor(Color.red);
            g.drawString(s, x - fm.stringWidth(s) / 2, y - 13 - 2);
            g.setColor(Color.black);
        }
    }

    public void drawPinball(Graphics g, BTNode pinball)
    {
        int mode = pinball.getMode();
        int x = pinball.x();
        int y = pinball.y();
        int w = fm.stringWidth(pinball.getKey());
        int h = fm.getHeight();
        if(mode == 11)
            g.drawImage(applet.getCircle(0), x - 18, y - 18, null);
        else
            drawBall(g, mode, x, y);
        g.drawString(pinball.getKey(), x - w / 2, (y - h / 2) + fm.getAscent());
    }

    public void drawBall(Graphics g, int mode, int x, int y)
    {
        int color = MODE.COLOR[mode];
        g.drawImage(applet.getBall(color), x - 13, y - 13, null);
    }

    public void resetModes()
    {
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
            node.setMode(0);

    }

    public void resetColors()
    {
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
            node.setColor(0);

    }

    public void resetNodes()
    {
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
            node.setLocation(400, 0);

    }

    public void shakeNodes()
    {
        resetModes();
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
            node.shake();

        displayMessage("", "GET DOWN TONIGHT... ", 2);
    }

    public void displayMessage(String msg, String format, int sound)
    {
        Object args[] = {
            msg
        };
        message = MessageFormat.format(format, args);
        if(sound == 1 || sound == 2 || sound == 3)
            applet.playSound(sound);
    }

    public void addMessage(String msg, String format, int sound)
    {
        Object args[] = {
            msg
        };
        message = message + MessageFormat.format(format, args);
        if(sound == 1 || sound == 2 || sound == 3)
            applet.playSound(sound);
    }

    public synchronized boolean mouseMove(Event event, int x, int y)
    {
        tool.setHelp(x, y);
        return true;
    }

    public synchronized boolean mouseDown(Event event, int x, int y)
    {
        applet.clearText();
        stopThinking();
        if(animation == 0)
            displayMessage("", "", 0);
        if(tool.contains(x, y))
            processTool();
        picknode = null;
        int r2 = 169;
        for(BTNode node = tree.getRoot(); node != null; node = node.nextPrO())
        {
            int dx = node.x() - x;
            int dy = node.y() - y;
            if(dx * dx + dy * dy >= r2)
                continue;
            picknode = node;
            break;
        }

        if(picknode != null)
        {
            applet.setText(picknode.getKey());
            lastpick = picknode;
        }
        return true;
    }

    public synchronized boolean mouseDrag(Event event, int x, int y)
    {
        picknode.setLocation(x, y);
        picknode.setDestination(x, y);
        return true;
    }

    public synchronized boolean mouseUp(Event event, int x, int y)
    {
        picknode.setMode(0);
        picknode = null;
        return true;
    }

    public void find(BTData data)
    {
        if(!getPermission(4))
            return;
        if(pinball.getMode() == 4)
            tree.find(pinball.getData());
        target = tree.getRoot();
        pinball.setData(data);
        pinball.setLocation(treetop.x(), 0);
        displayMessage(data.getKey(), "Locating {0}. ", 1);
        startFID(4);
    }

    public void insert(BTData data)
    {
        if(!getPermission(5))
            return;
        if(pinball.getMode() == 5)
        {
            BTNode node = tree.insert(pinball.getData());
            if(node != null)
            {
                BTNode parent = node.getParent();
                if(parent != null)
                    node.setLocation(parent.x(), parent.y());
                else
                    node.setLocation(treetop.x(), 0);
            }
        }
        target = tree.getRoot();
        if(target == null)
            target = treetop;
        pinball.setData(data);
        pinball.setLocation(treetop.x(), 0);
        displayMessage(data.getKey(), "Inserting {0}. ", 1);
        startFID(5);
    }

    public void delete(BTData data)
    {
        if(!getPermission(6))
            return;
        if(pinball.getMode() == 6)
        {
            tree.delete(pinball.getData(), minmax);
            if(tree.isEmpty())
            {
                displayMessage("", "All nodes deleted. ", 2);
                stopFID();
                return;
            }
        }
        target = tree.getRoot();
        pinball.setData(data);
        pinball.setLocation(treetop.x(), 0);
        displayMessage(data.getKey(), "Locating {0}. ", 1);
        startFID(6);
    }

    public void flipMinMax()
    {
        minmax = -minmax;
        int state = minmax != 1 ? 1 : 0;
        displayMessage("", MSG.MINMAX[state], 1);
    }

    public void deleteAll()
    {
        if(!getPermission(7))
            return;
        if(pinball.getMode() == 7)
        {
            tree.deleteAll();
            displayMessage("", "All nodes deleted. ", 2);
            stopTDA();
            return;
        } else
        {
            target = tree.root.firstPoO();
            pinball.setData(target.getData());
            pinball.setLocation(treetop.x(), 0);
            displayMessage("", "Deleting the tree. ", 1);
            startTDA(7);
            return;
        }
    }

    public void setOrder(int order, String name)
    {
        this.order = order;
        displayMessage(name, "Traversal order changed to {0}. ", 1);
    }

    public void traverse(BTData data)
    {
        if(!getPermission(8))
            return;
        if(pinball.getMode() == 8)
        {
            target = lastnode;
            pinball.setData(target.getData());
            return;
        }
        BTNode node = tree.locateBST(data);
        if(node == null)
            node = tree.getRoot();
        lastnode = node.getLastIn(order);
        target = node.getFirstIn(order);
        pinball.setData(target.getData());
        pinball.setLocation(treetop.x(), 0);
        displayMessage(pinball.getKey(), "Traversing the tree. Next node {0}... ", 1);
        startTDA(8);
    }

    public void processTool()
    {
        int command = tool.getCommand();
        int cmd = tool.processCommand();
        switch(command)
        {
        default:
            break;

        case 0: // '\0'
        {
            setTreeSize(cmd);
            break;
        }