package hartech.kids.huffman;

/**
 * <p>Title: 哈夫曼編/譯碼器</p>
 *
 * <p>Description:
 * 利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。
 * 但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，
 * 在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），
 * 每端都需要一個(gè)完整的編／譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編／譯碼系統(tǒng)。
 * </p>
 *
 * <p>Website: www.hartech.cn </p>
 * <p>Page: http://www.hartech.cn/blog/blogview.asp?logID=87 </p>
 * <p>Date: 2006-09-05 </p>
 */
public class Huffman {

  class Elem {
    char chara;
    int weight;
    int parent;
    int lchild;
    int rchild;
    public Elem(char c, int w, int p, int l, int r) {
      chara = c;
      weight = w;
      parent = p;
      lchild = l;
      rchild = r;
    }
  }

  // 哈夫曼樹
  private Elem[] huffmanTree;
  // 哈夫曼編碼表
  private String[] huffmanCode;
  // 字符個(gè)數(shù)
  int charNum;

  // 給出 in 構(gòu)造哈夫曼樹 huffmanTree、哈夫曼編碼表huffmanCode
  // in 格式為{'字符1',對應(yīng)權(quán)值,'字符2',對應(yīng)權(quán)值,  ...}
  public Huffman(char[] in) {
    if (in == null || in.length == 0 || in.length % 2 != 0) {
      System.err.println("dd");
      return;
    }
    charNum = in.length / 2;
    // 0 單元不用，要用到 0 來標(biāo)記是否有孩子、父親
    huffmanTree = new Elem[charNum * 2];
// 初始化
    for (int i = 1; i < charNum + 1; i++) {
      huffmanTree[i] = new Elem(in[ (i - 1) * 2], in[i * 2 - 1], 0, 0, 0);
    }
    for (int i = charNum + 1; i < charNum * 2; i++) {
      huffmanTree[i] = new Elem( (char) 0, 0, 0, 0, 0);
    }

// 構(gòu)造哈夫曼樹
    huffmanTree[0] = new Elem( (char) 0, Integer.MAX_VALUE, 0, 0, 0);
    int minNo1, minNo2;
    for (int i = charNum + 1; i < charNum * 2; i++) {
      // 找出weight最小且無父節(jié)點(diǎn)的兩個(gè)
      minNo1 = 0;
      minNo2 = 0;
      for (int j = 1; j < i; j++) {
        if (huffmanTree[j].parent == 0) {
          if (huffmanTree[j].weight < huffmanTree[minNo1].weight ||
              huffmanTree[j].weight < huffmanTree[minNo2].weight) {
            if (huffmanTree[minNo1].weight < huffmanTree[minNo2].weight) {
              minNo2 = j;
            }
            else {
              minNo1 = j;
            }
          }
        }
      }

      huffmanTree[minNo1].parent = i;
      huffmanTree[minNo2].parent = i;
      // 保持葉子節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩，如書上圖6.26
      if (minNo1 <= charNum) {
        huffmanTree[i].lchild = minNo1;
        huffmanTree[i].rchild = minNo2;
      }
      else {
        huffmanTree[i].lchild = minNo2;
        huffmanTree[i].rchild = minNo1;
      }
      huffmanTree[i].weight = huffmanTree[minNo1].weight +
          huffmanTree[minNo2].weight;
    }

// 求出每個(gè)字符編碼，從葉子到根，保存至 huffmanCode
    huffmanCode = new String[charNum + 1];
    char[] temp = new char[charNum + 1];
    int start, pa, ch;
    for (int i = 1; i <= charNum; i++) {
      start = charNum;
      ch = i;
      pa = huffmanTree[i].parent;
      while (pa != 0) {
        if (huffmanTree[pa].lchild == ch) {
          temp[start] = '0';
        }
        else {
          temp[start] = '1';
        }
        start--;
        ch = pa;
        pa = huffmanTree[pa].parent;
      }
      huffmanCode[i] = String.valueOf(temp, start + 1, charNum - start);
    }
  }

  // 返回給定字符串的哈夫曼代碼，對于本樹中無記錄的字符則直接插入到原對應(yīng)位置
  String toCodes(String in) {
    StringBuffer out = new StringBuffer();
    char c;
    int j;
    for (int i = 0; i < in.length(); i++) {
      c = in.charAt(i);
      j = 1;
      while (huffmanTree[j].chara != c && j <= charNum) {
        j++;
      }
      if (j <= charNum) {
        out.append(huffmanCode[j]);
      }
      else {
        out.append(c);
      }
    }
    return out.toString();
  }

  // 對給定哈夫曼碼譯碼，對于非 1、0 的字符直接插入到原對應(yīng)位置
  String toChars(String in) {
    StringBuffer out = new StringBuffer();
    // 指向樹根
    int point = charNum * 2 - 1;
    char c;
    for (int i = 0; i < in.length(); i++) {
      c = in.charAt(i);
      if (c == '0') {
        point = huffmanTree[point].lchild;
      }
      else if (c == '1') {
        point = huffmanTree[point].rchild;
      }
      else {
        out.append(c);
        continue;
      }
      // 為葉子
      if (point <= charNum) {
        out.append(huffmanTree[point].chara);
        point = charNum * 2 - 1;
      }
    }
    return out.toString();
  }

  // 打印哈夫曼樹
  public String printTree() {
    StringBuffer out = new StringBuffer();
    out.append("No.\t" + "Char\t" + "Weight\t" + "Parent\t" + "Lchild\t" +
               "Rchild" + "\r\n\r\n");
    for (int i = 1; i < charNum * 2; i++) {
      out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" +
                 huffmanTree[i].weight + "\t" +
                 huffmanTree[i].parent + "\t" + huffmanTree[i].lchild + "\t" +
                 huffmanTree[i].rchild + "\r\n");
    }
    return out.toString();
  }

  // 打印出所有編碼
  public String printCodes() {
    StringBuffer out = new StringBuffer();
    int value = 0;
    out.append("No.\t" + "Char\t" + "Code" + "\r\n\r\n");
    for (int i = 1; i < charNum + 1; i++) {
      out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" + huffmanCode[i] +
                 "\r\n");
      value += huffmanCode[i].length() * huffmanTree[i].weight;
    }
    out.append("\r\n總帶權(quán)路徑長度為：\t" + value + "\r\n");
    return out.toString();
  }

  public static void main(String[] args) {
    // test：

    // 詞頻表
    char[] in = {
        ' ', 186, 'a', 64, 'b', 13, 'c', 22, 'd', 32, 'e', 103, 'f', 21, 'g',
        15, 'h', 47, 'i', 57, 'j', 1, 'k', 5, 'l', 32, 'm', 20, 'n', 57, 'o',
        63, 'p', 15, 'q', 1, 'r', 48, 's', 51, 't', 80, 'u', 23, 'v', 8, 'w',
        18, 'x', 1, 'y', 16, 'z', 1};

    Huffman huffman = new Huffman(in);
    huffman.printTree();
    huffman.printCodes();

    // 編碼：
    // 輸出：0010111010101101000010101110001000101111100011000111000010101101
    //      000001110010100000001111011000110100100110010100010100
    String code = huffman.toCodes("this program is my favorite");

    // 譯碼：
    // 輸出：this program is my favorite
    huffman.toChars(code);
  }
}