hspersongroup.java

本软件是使用java 开发的

package datastructure;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: </p>
 * @author unascribed
 * @version 1.0
 */

import java.awt.*;
import java.util.*;

class hsPersonGroup {
  private CodeAnimationPanel codePanel;
  private Vector input;
  private Vector output;
  private Vector heapTree;
  private Vector animationInput;
  private Node animationNode;
  private Node animationNode1;
  private int codePart1;
  private int codePart2;
  private int length;
  private int record;
  private int s;
  private int m;
  private int j;
  private int t;
  private int rc;
  private int label;
  //doneFlag记录演示是否完成,为真是表示已经完成
  private boolean doneFlag;
  int a[];
  private int record1;

  public hsPersonGroup(CodeAnimationPanel codePanel) {
    this.codePanel = codePanel;
    codePanel.highlight(12);
    a = hsFrame.data.a;
    hsSort.text2.setText("     " + String.valueOf(a.length));
    input = new Vector();
    output = new Vector();
    codePart1 = 0;
    codePart2 = 0;
    doneFlag = false;
    record1 = 0;
    s = 0;
    label = 0;
    init();
  }

  public void init() {
    int x = 70;
    int y = 20;
    for (int i = 0; i < a.length; i++) {
      animationNode = new Node(a[i]);
      animationNode.y = y;
      animationNode.x = x;
      input.add(animationNode);
      x = x + 22;
    }
    Base(a);
    length = heapTree.size();
    record = length / 2 - 1;
  }

  public boolean getDoneFlag() {
    return doneFlag;
  }

  public void Base(int a[]) {
    animationInput = new Vector();
    heapTree = new Vector();
    int x = 70;
    int y = 60;
    for (int i = 0; i < a.length; i++) {
      animationNode = new Node(a[i]);
      animationNode.x = x;
      animationNode.y = y;
      animationInput.add(animationNode);
      x = x + 22;
    }
    int depth = 0;
    int p = 1;
    x = 200;
    y = 110;
    for (int i = 0; i < a.length; i++) {
      animationNode = new Node(a[i]);
      if ( (i + 1) % p == 0) {
        depth++;
        p = p * 2;
      }
      animationNode.depth = depth;
      if (animationNode.depth == 2) {
        y = 160;
        if (i == 1)
          x = 120;
        else
          x = 280;
        animationNode.x = x;
        animationNode.y = y;

      }
      else if (animationNode.depth == 3) {
        y = 220;
        if (i == 3)
          x = 80;
        else
          x = x + 80;
        animationNode.x = x;
        animationNode.y = y;
      }
      else if (animationNode.depth == 4) {
        y = 280;
        if (i == 7)
          x = 60;
        else
          x = x + 40;
      }
      else if (animationNode.depth == 5) {
        y = 340;
        if (i == 15)
          x = 50;
        else
          x = x + 22;
      }
      animationNode.x = x;
      animationNode.y = y;
      //设置节点的父节点
      heapTree.add(animationNode);
    }
    //该循环用于设置节点的左，右孩子节点
    for (int i = 0; i < heapTree.size() / 2; i++) {
      animationNode = (Node) heapTree.elementAt(i);
      if (i < heapTree.size() / 2 - 1) {
        animationNode.setLeftNode( (Node) heapTree.elementAt(2 * (i + 1) - 1));
        animationNode.setRightNode( (Node) heapTree.elementAt(2 * (i + 1)));
      }
      else if (i == heapTree.size() / 2 - 1) {
        if (heapTree.size() % 2 == 0)
          animationNode.setLeftNode( (Node) heapTree.elementAt(2 * (i + 1) - 1));
        else {
          animationNode.setLeftNode( (Node) heapTree.elementAt(2 * (i + 1) - 1));
          animationNode.setRightNode( (Node) heapTree.elementAt(2 * (i + 1)));
        }
      }
      heapTree.set(i, animationNode);
    }
  }

  public void draw(Graphics g) {
    g.setColor(new Color(0, 0, 140));
    g.fillRoundRect(10, 20, 50, 30, 5, 5);
    g.setColor(Color.black);
    g.drawRoundRect(10, 20, 50, 30, 5, 5);
    g.setColor(Color.yellow);
    g.drawString("输入数据", 13, 38);
    for (int i = 0; i < input.size(); i++) {
      animationNode = (Node) input.elementAt(i);
      drawLeafNode(g, animationNode);
    }
    if (!doneFlag) {
      if (codePart2 == 6 || codePart2 == 7)
        g.setColor(Color.blue);
      else
        g.setColor(Color.white);
      g.fill3DRect(75 + 20 * 16, 160, 20, 30, true);
      g.setColor(Color.white);
      g.setColor(Color.black);
      g.draw3DRect(75 + 20 * 16, 160, 20, 30, true);
      if (codePart1 <= 3 && codePart1 != 2)
        g.drawString("建初始大顶堆", 370, 150);
      g.setColor(Color.red);
      if (label == 1) {
        if (codePart1 > 3) {
          g.setColor(Color.black);
          g.drawString("重新调整为大顶堆", 355, 150);
        }
        g.setColor(Color.red);
        g.drawString(String.valueOf(rc), 400, 178);
      }
      g.drawString("rc", 400, 205);
    }
    for (int i = 0; i < animationInput.size(); i++) {
      g.setColor(new Color(0, 0, 140));
      g.fillRoundRect(10, 60, 50, 30, 5, 5);
      g.setColor(Color.black);
      g.drawRoundRect(10, 60, 50, 30, 5, 5);
      g.setColor(Color.yellow);
      g.drawString("当前数据", 13, 78);
      animationNode = (Node) animationInput.elementAt(i);
      drawLeafNode(g, animationNode);
    }
    for (int i = 0; i < heapTree.size(); i++) {
      animationNode = (Node) heapTree.elementAt(i);
      drawTreeNode(g, animationNode);
    }
    for (int i = 0; i < output.size(); i++) {
      g.setColor(new Color(0, 0, 140));
      g.fillRoundRect(10, 380, 50, 30, 5, 5);
      g.setColor(Color.black);
      g.drawRoundRect(10, 380, 50, 30, 5, 5);
      g.setColor(Color.yellow);
      g.drawString("输出数据", 13, 400);
      Node node = (Node) output.elementAt(i);
      drawLeafNode(g, node);
    }
  }

  public void drawLeafNode(Graphics g, Node node) {
    int i = node.x;
    int j = node.y;
    int k = node.getWeight();
    if (node.getHighlight())
      g.setColor(Color.black);
    else
      g.setColor(Color.blue);
    g.fillRect(i, j, 20, 30);
    g.setColor(Color.black);
    g.drawRect(i, j, 20, 30);
    g.setColor(Color.yellow);
    g.drawString(String.valueOf(k), i + 5, j + 22);
  }

  public void drawTreeNode(Graphics g, Node node) {
    if (node.getHighlight())
      g.setColor(Color.black);
    else
      g.setColor(new Color(105, 190, 171));
    g.fillRect(node.x, node.y, 20, 30);
    g.setColor(Color.black);
    g.drawRect(node.x, node.y, 20, 30);
    g.setColor(Color.white);
    g.drawString(String.valueOf(node.getWeight()), node.x + 5, node.y + 22);
    if (node.getLeftNode() != null) {
      g.setColor(Color.black);
      g.drawLine(node.x + 6, node.y + 30, node.getLeftNode().x + 10,
                 node.getLeftNode().y);
      if (node.getHighlightLeft()) {
        g.drawLine(node.x + 5, node.y + 30, node.getLeftNode().x + 9,
                   node.getLeftNode().y);
        g.drawLine(node.x + 4, node.y + 30, node.getLeftNode().x + 8,
                   node.getLeftNode().y);
      }
    }
    if (node.getRightNode() != null) {
      g.drawLine(node.x + 14, node.y + 30, node.getRightNode().x + 10,
                 node.getRightNode().y);
      if (node.getHighlighthighlightRight()) {
        g.drawLine(node.x + 15, node.y + 30, node.getRightNode().x + 11,
                   node.getRightNode().y);
        g.drawLine(node.x + 16, node.y + 30, node.getRightNode().x + 12,
                   node.getRightNode().y);
      }
    }
  }

  public void HeapSort() {
    label = 0;
    switch (codePart1) {
      case 0:
        codePanel.highlight(13);
        this.highlight(s, false);
        hsSort.text3.setText("     " + String.valueOf(record + 1));
        if (record >= 0)
          codePart1 = 1;
        else
          codePart1 = 2;
        break;
      case 1:
        codePanel.highlight(14);
        s = record;
        m = length - 1;
        j = 2 * s + 1;
        codePart1 = 3;
        break;
      case 3:
        HeapAdjust();
        break;
      case 2:
        codePanel.highlight(15);
        record = length - 1;
        hsSort.text3.setText("     " + String.valueOf(record + 1));
        codePart1 = 4;
      case 4:
        codePanel.highlight(15);
        if (record >= 1)
          codePart1 = 5;
        else
          codePart1 = 8;
        break;
      case 5:
        codePanel.highlight(16);
        swap(0, record);
        codePart1 = 6;
        break;
      case 6:
        codePanel.highlight(17);
        s = 0;
        m = record - 1;
        j = 2 * s + 1;
        codePart1 = 7;
        break;
      case 7:
        HeapAdjust();
        break;
      case 8:
        swap(0, record);
        codePanel.highlight(18);
        codePart1 = 9;
        break;
      case 9:
        doneFlag = true;
        break;
    }
  }

  public void HeapAdjust() {
    label = 1;
    switch (codePart2) {
      case 0:
        hsSort.text5.setText("     " + String.valueOf(s + 1));
        hsSort.text6.setText("     " + String.valueOf(m + 1));
        codePanel.highlight(3);
        animationNode = (Node) heapTree.elementAt(s);
        rc = animationNode.getWeight();
        codePart2 = 1;
        break;
      case 1:
        codePanel.highlight(4);
        hsSort.text4.setText("     " + String.valueOf(j + 1));
        this.highlight(s, true);
        if (j <= m) {
          codePart2 = 2;
          this.highlight(j, true);
        }
        else
          codePart2 = 3;
        break;
      case 2:
        codePanel.highlight(5);
        if (j < m) {
          this.highlight(j + 1, true);
          if (LT(j, j + 1, true))
            codePart2 = 4;
          else
            codePart2 = 51;
        }
        else
          codePart2 = 5;
        break;
      case 3:
        codePanel.highlight(10);
        changeValue1(s, rc);
        record--;
        hsSort.text3.setText("     " + String.valueOf(record + 1));
        hsSort.text5.setText(" ");
        hsSort.text6.setText(" ");
        if (codePart1 == 3)
          codePart1 = 0;
        if (codePart1 == 7)
          codePart1 = 4;
        codePart2 = 0;
        break;
      case 4:
        codePanel.highlight(6);
        this.highlight(j, false);
        j++;
        hsSort.text4.setText("     " + String.valueOf(j + 1));
        codePart2 = 5;
        break;
      case 51:
        this.highlight(j + 1, false);
      case 5:
        codePanel.highlight(7);
        if (!LT(rc, j, false))
          codePart2 = 6;
        else
          codePart2 = 7;
        break;
      case 6:
        codePanel.highlight(8);
        this.highlight(j, false);
        codePart2 = 3;
        break;
      case 7:
        codePanel.highlight(9);
        this.highlight(s, false);
        changeValue(j, s);
        s = j;
        j = 2 * s + 1;
        hsSort.text5.setText("     " + String.valueOf(s + 1));
        codePart2 = 1;
        break;
    }
  }

  public void swap(int i, int j) {
    this.highlight(i, true);
    this.highlight(j, true);
    addOutput(i);
    changeValue(j, i);
    heapTree.removeElementAt(j);
    animationInput.removeElementAt(j);
    int c[] = new int[heapTree.size()];
    for (int p = 0; p < heapTree.size(); p++) {
      animationNode = (Node) animationInput.elementAt(p);
      int weight = animationNode.getWeight();
      c[p] = weight;
    }
    Base(c);
  }

  public void addOutput(int t) {
    Node no = (Node) heapTree.elementAt(t);
    int wei = no.getWeight();
    Node node11 = new Node(wei);
    node11.y = 380;
    int x = (20 * a.length + (a.length - 1) * 2) + 70 -
        ( (record1 + 1) * 20 + record1 * 2);
    record1++;
    node11.x = x;
    output.addElement(node11);
  }

  public void changeValue1(int s, int rc) {
    animationNode = (Node) heapTree.elementAt(s);
    animationNode.setWeight(rc);
    heapTree.set(s, animationNode);
    animationNode = (Node) animationInput.elementAt(s);
    animationNode.setWeight(rc);
    animationInput.set(s, animationNode);
  }

  public void changeValue(int j, int s) {
    animationNode1 = (Node) heapTree.elementAt(j);
    animationNode = (Node) heapTree.elementAt(s);
    animationNode.setWeight(animationNode1.getWeight());
    heapTree.set(s, animationNode);
    animationNode1 = (Node) animationInput.elementAt(j);
    animationNode = (Node) animationInput.elementAt(s);
    animationNode.setWeight(animationNode1.getWeight());
    animationInput.set(s, animationNode);
  }

  public void highlight(int i, boolean flag) {
    if (flag) {
      animationNode = (Node) heapTree.elementAt(i);
      animationNode.setHighlight(true);
      heapTree.set(i, animationNode);
      animationNode = (Node) animationInput.elementAt(i);
      animationNode.setHighlight(true);
      animationInput.set(i, animationNode);
    }
    else {
      animationNode = (Node) heapTree.elementAt(i);
      animationNode.setHighlight(false);
      heapTree.set(i, animationNode);
      animationNode = (Node) animationInput.elementAt(i);
      animationNode.setHighlight(false);
      animationInput.set(i, animationNode);
    }
  }

  public boolean LT(int i, int j, boolean flag) {
    if (flag) {
      Node node1 = (Node) heapTree.elementAt(i);
      Node node2 = (Node) heapTree.elementAt(j);
      if (node1.getWeight() < node2.getWeight())
        return true;
      else
        return false;
    }
    else {
      Node node1 = (Node) heapTree.elementAt(j);
      if (i < node1.getWeight())
        return true;
      else
        return false;
    }
  }
}