adaptivetree.java

用java实现的自适应哈夫曼算法

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



public abstract class AdaptiveTree extends Template
{
    /*
     * AdaptiveTree
     *
     * Creates a single-node tree with the rootnumber as the root
     * inside the displayRect.
     */
    public void AdaptiveTree(int rootnumber, Rectangle displayRect)
    {

        SQUARE_WIDTH = _height + _descent;
        SQUARE_VSPACE = _height + _descent;

        for (int i=0; i < 2*ALPH_SIZE; i++)
        {
           tree[i] = new Node();
        }

        root = rootnumber;
        tree[root].letter = NYT;

        dispRect = displayRect;

       	drawTrie(dispRect, null);

       	gc = this.getGraphics();
       	update(gc);

    }


    /**
     *  Swap
     *
     * swaps two nodes in the tree. Make sure its not an ancestor
     */

    public synchronized void swap(int first, int second)
    {

        int temp;
        char tempchar;

        beg = first;
        end = second;
        drawTrie(dispRect, null);
        update(gc);
        beg = 0;
        end = 0;


        // swap return pointers

        tree[tree[first].left].parent = second;
        tree[tree[first].right].parent = second;
        tree[tree[second].left].parent = first;
        tree[tree[second].right].parent = first;

        // swap left pointers

        temp = tree[second].left;
        tree[second].left = tree[first].left;
        tree[first].left = temp;

        // swap right pointers

        temp = tree[second].right;
        tree[second].right = tree[first].right;
        tree[first].right = temp;

        // swap data

        tempchar = tree[second].letter;
        tree[second].letter = tree[first].letter;
        tree[first].letter = tempchar;

        temp = tree[second].count;
        tree[second].count = tree[first].count;
        tree[first].count = temp;

    }


    /**
     * findChar
     *
     * Returns the index of the character
     *
     */

     public int findChar (char letter) throws NoSuchElementException
     {

        for (int i=0; i < 2*ALPH_SIZE; i++) {
            if (tree[i].letter == letter) return i;
        }

        throw new NoSuchElementException(" in findChar");
     }

    /**
     * code2char
     *
     * Returns the character associated with the binary code
     *
     */

    public char code2char(String bincode) throws NoSuchElementException
    {

        Node current = tree[root];

        for (int i=0; i < bincode.length(); i++) {

            // check if current binary digit is valid
            if  (bincode.charAt(i) != '0'  && bincode.charAt(i) != '1')
                throw new NoSuchElementException("Has a non-binary digit at " + i);

            // go left
            if (bincode.charAt(i) == '0') {
                if (current.left == 0) throw new NoSuchElementException();
                else current = tree[current.left];

            //go right
            } else if (bincode.charAt(i) == '1') {
                if (current.right == 0) throw new NoSuchElementException();
                else current = tree[current.right];
            }

        }

        if (current.letter == none) throw new NoSuchElementException("Not a leaf node");
        else return current.letter;

    }

    /**
     *  char2code
     *
     * Returns the code associated with the character
     *
     */

     public String char2code(char letter) throws NoSuchElementException
     {

        StringBuffer bincode = new StringBuffer("");
        Node current = null;

        // find the letter

        current = tree[findChar(letter)];

        // Make the binary string

        while (current != tree[root]) {

            // is a left child
            if (tree[tree[current.parent].left] == current) {
                bincode.insert(0, '0');

            // is a right child
            } else if (tree[tree[current.parent].right] == current) {
                bincode.insert(0, '1');

            // huh?
            } else throw new NoSuchElementException ("something is fucked");

            // move  up

            current = tree[current.parent];
        }

        return ("" + bincode);

     }

     /**
      * char2binary
      *
      * Returns the binary representation of the character
      */

      public String char2binary(char letter)
      {

        int num = (int)letter;
        StringBuffer backwards = new StringBuffer(10);
        StringBuffer binary = new StringBuffer(10);

        while (num > 0)
        {
            backwards.append( num % 2 );
            num /= 2;
        }

        binary.setLength( backwards.length() );

        for (int i=backwards.length()-1; i >= 0 ; i--)
        {
            binary.setCharAt( backwards.length()-1 - i, backwards.charAt(i) );
        }

        return (binary.toString());
      }

     /**
      * spawn
      *
      * Gives birth to new NYT and external node from old NYT node
      *  returns the value of the new NYT node
      */

     public int spawn (char newchar)
     {

        int oldNYTindex;
        Node oldNYT;

        // Find the current NYT node

        oldNYTindex = findChar(NYT);
        oldNYT = tree[oldNYTindex];

        // create new nodes

        oldNYT.letter = none;

        oldNYT.right = oldNYTindex - 1;
        tree[oldNYT.right].letter = newchar;
        tree[oldNYT.right].count = 1;
        tree[oldNYT.right].parent = oldNYTindex;

        oldNYT.left = oldNYTindex - 2;
        tree[oldNYT.left].letter = NYT;
        tree[oldNYT.left].parent = oldNYTindex;

        return oldNYTindex - 2;


     }

     /*
      * HighestInBlock
      *
      * Returns the value of the node that is the highest in the block
      * i.e. of all nodes with the same count
      *
      */

      public int highestInBlock (int count)
      {

        int highest = -1;

        for (int i=0; i < 2*ALPH_SIZE; i++)
        {
            if (tree[i].count == count) highest=i;
        }

        if (highest == -1) throw new NoSuchElementException("No such node with count of " + count);

        return highest;
      }


    /**
     * blank
     *
     * Clears the offscreen graphics image.
     */
    public void blank (Rectangle dispRect)
    {
        Dimension d = size();

        // clear out the background
        _offGraphics.setColor(Color.white);
        _offGraphics.fillRect(0, 0, d.width, d.height);
        _offGraphics.setColor(Color.black);
        title("Adaptive Huffman", "Compression");
	_offGraphics.drawRect(dispRect.x, dispRect.y, dispRect.width, dispRect.height);
    }

    /**
     * refresh
     *
     * Force repaint event and pause briefly for event to be received by applet.
     */
    public synchronized void refresh() {
    	repaint();
    	try {
    	    this.wait(REFRESH_DELAY);
    	} catch (InterruptedException e) { }
    }


    /**
     * drawTrie
     *
     * Draws a graphical representation of the entire encoding trie.
     */
    public synchronized void drawTrie(Rectangle dispRect, Vector path)
    {

	Color oldColor;

	blank(dispRect);

	oldColor = _offGraphics.getColor();

	_offGraphics.setColor(COLOR_TRIE);

	/* Draw entire subtree rooted at our root */
	drawNode(dispRect.width, -1, -1, dispRect.width / 2, dispRect.y + 5, path, root);

	_offGraphics.setColor(oldColor);

	if(path != null) {
	    try {
	        this.wait(DRAWTRIE_DELAY);
	    } catch(InterruptedException e) { }
	}
    }


    /**
     * drawNode
     *
     * Draws a graphical representation of the specified node and all its
     * children.  Hilights the character, nodes and edges along the
     * specified path in the tree.
     */
    public void drawNode(int width, int old_h, int old_v, int hloc, int vloc,
		  Vector path, int cur_node)
	{

	int i;
	boolean found;
	Font oldFont;

	/* Choose appropriate color for this node */
	found = false;
	if(path != null) {
	    i = 0;
	    while(found == false && i < path.size()) {
		found = (((Integer) path.elementAt(i)).intValue() == cur_node);
		i++;
	    }

	    if(found == true)
		_offGraphics.setColor(COLOR_NODE_HILIGHT);
	    else
		_offGraphics.setColor(COLOR_NODE_NORM);
	}

	/* Draw swap line, if exists. This is a hack and extrememly bad coding style,
	   but it was added as an afterthought. Anybody know a better way                */

	if (beg != 0 && end != 0 ) {
	    if (cur_node == beg) {
	        begp = new Point(hloc, vloc);
  	        if (endp != null) {
	            _offGraphics.setColor(Color.blue);
	            _offGraphics.drawLine(begp.x, begp.y, endp.x, endp.y);
	            _offGraphics.setColor(COLOR_NODE_NORM);
	            endp =  null; begp = null;
	        }

	    }
	    if (cur_node == end) {
	        endp = new Point(hloc, vloc);
	        if (begp != null) {
	            _offGraphics.setColor(Color.blue);
	            _offGraphics.drawLine(begp.x, begp.y, endp.x, endp.y);
	            _offGraphics.setColor(COLOR_NODE_NORM);
	            endp =  null; begp = null;
	        }
	    }
	}


	/* Draw self */

     _offGraphics.drawRect(hloc, vloc, SQUARE_WIDTH, SQUARE_WIDTH);
     _offGraphics.drawString(tree[cur_node].count + "", hloc + 5, vloc + _height);
     _offGraphics.drawString(cur_node + "", hloc + 3, vloc + SQUARE_WIDTH + _height);

     _offGraphics.setColor(Color.black);

    /* Switch to bigger font */

	 oldFont = _offGraphics.getFont();
     _offGraphics.setFont(new Font(oldFont.getName(), Font.BOLD, oldFont.getSize()+2));

	/* Draw line from current node to parent */
	if(tree[cur_node].parent != 0) {
	    if(old_h < hloc) {
	        /* parent was to our left */
	        if (tree[cur_node].letter != none) _offGraphics.drawString(tree[cur_node].letter + "", hloc + SQUARE_WIDTH + 5, vloc + _height);
	        _offGraphics.drawLine(old_h + SQUARE_WIDTH - 1, old_v + SQUARE_WIDTH - 1, hloc + (SQUARE_WIDTH / 2), vloc);
	    } else {
	        /* parent was to our right */
	        if (tree[cur_node].letter != none)
	            if (tree[cur_node].letter == NYT)
	                _offGraphics.drawString("NYT", hloc - SQUARE_WIDTH - _height, vloc + _height);
	            else _offGraphics.drawString(tree[cur_node].letter + "", hloc - SQUARE_WIDTH / 2 - 3, vloc + _height);
	        _offGraphics.drawLine(old_h + 1, old_v + SQUARE_WIDTH - 1, hloc + (SQUARE_WIDTH / 2), vloc);
	    }
	}

    _offGraphics.setFont(oldFont);


	/* Find children, if any */
	    if(tree[cur_node].left != 0) {

		/* Found left child */

		// check
		    if (cur_node != tree[tree[cur_node].left].parent)
		        System.out.println("Broken left child link at node :" + cur_node);

	        drawNode(width / 2, hloc, vloc, hloc - (width / 4), vloc + SQUARE_WIDTH + SQUARE_VSPACE, path, tree[cur_node].left);

	    }

	    if(tree[cur_node].right != 0) {

		/* Found right child */

		// check
		    if (cur_node != tree[tree[cur_node].right].parent)
		        System.out.println("Broken right child link at node :" + cur_node);

	        drawNode(width / 2, hloc, vloc, hloc + (width / 4), vloc + SQUARE_WIDTH + SQUARE_VSPACE, path, tree[cur_node].right);

	}
    }


    public abstract void run();



    /* Adaptive Tree data members */

    private Rectangle dispRect;                         // rectangle to display tree in

    Node tree[] = new Node[2*ALPH_SIZE];
    int root;
    Graphics gc;
    boolean waitforclick;

    int beg, end;               // variables for swap line (bad coding style)
    Point begp, endp;


    /* Adaptive Tree constants */

    static final int ALPH_SIZE = 127;       // size of the alphabet
    static final char none = (char) 256;      // not a character
    static final char NYT = (char) 257;      // Not Yet transmitted code
    int SQUARE_WIDTH;     // width of node drawing in pixels
    int SQUARE_VSPACE;   // vert. space between node drawings

    static final Color COLOR_TRIE = Color.black;
    static final Color COLOR_NODE_HILIGHT = Color.red;
    static final Color COLOR_NODE_NORM = Color.black;

    static final String ALPH_STRING = " !\"#$%&`()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";

    static final int DRAWTRIE_DELAY = 400; // ms delay for repaint in drawTrie
    static final int REFRESH_DELAY = 5;    // min ms delay for repaint



}

class Node {
        public char letter;     // the character of each code
        public int  count;      // frequency of each character
        public int left;        // the left child of each node
        public int right;        // the right child of each node
        public int parent;       // the parent of each node
    }