package huffmancode;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class HuffManCode 
{

 public static void main(String[] args) 
 {
  String srcFile="d://mydata.txt";//要壓縮的文件
  String dstFile="d://mydata.zip";//壓縮后的文件
  zipFile(srcFile, dstFile);//壓縮文件
  System.out.println("壓縮成功！");
  
  unZipFile(dstFile,"d://unzip.txt");//對(duì)剛才的文件進(jìn)行解壓，解壓后的文件名稱叫做unzip.txt
  System.out.println("解壓文件成功！");  
 }
 
 public static void unZipFile(String zipFile,String dstFile)
 {
  InputStream inputStream=null;
  ObjectInputStream objectInputStream=null;
  OutputStream outputStream=null;
  try 
  {
   inputStream=new FileInputStream(zipFile);
   objectInputStream=new ObjectInputStream(inputStream);
   byte [] array= (byte [])objectInputStream.readObject();
   Map<Byte,String> map=(Map<Byte,String>)objectInputStream.readObject();
   byte[] decode = decode(map, array);
   outputStream=new FileOutputStream(dstFile);
   outputStream.write(decode);
  } catch (Exception e) 
  {
   System.out.println(e);
  }finally
  {
   try {
    outputStream.close();
    objectInputStream.close();
    inputStream.close();
    
   } catch (Exception e2) {
    System.out.println(e2);
   }
   
  }
  
  
 }
 
 public static void zipFile(String srcFile,String dstFile)
 {
  FileInputStream inputStream=null;
  OutputStream outputStream=null;
  ObjectOutputStream objectOutputStream=null;
  
  try 
  {
   inputStream=new FileInputStream(srcFile);
   byte [] b=new byte[inputStream.available()];
   inputStream.read(b);
   byte[] huffmanZip = huffmanZip(b);
   outputStream=new FileOutputStream(dstFile);
   objectOutputStream=new ObjectOutputStream(outputStream);
   objectOutputStream.writeObject(huffmanZip);
   objectOutputStream.writeObject(map);
  } catch (Exception e)
  {
   System.out.println(e);
  }
  finally 
  {
   if(inputStream!=null)
   {
    try 
    {
     objectOutputStream.close();
     outputStream.close();
     inputStream.close();//釋放資源
    
    } catch (Exception e2) 
    {
     System.out.println(e2);
    }
    
   }  
  }
 }
 
 private static byte[] decode(Map<Byte, String> map,byte [] array)
 {
  StringBuilder stringBuilder = new StringBuilder();
  for(int i=0;i<array.length;i++)
  {
   boolean flag=(i==array.length-1);
   stringBuilder.append(byteToBitString(!flag, array[i]));
  }
  
  Map<String, Byte> map2=new HashMap<String, Byte>();//反向編碼表
  Set<Byte> keySet = map.keySet();
  for(Byte b:keySet)
  {
   String value=map.get(b);
   map2.put(value, b);
  }
  List<Byte> list=new ArrayList<Byte>();
  for (int i = 0; i < stringBuilder.length();) 
  {
   int count=1;
   boolean flag=true;
   Byte byte1=null;
   while (flag) 
   {
    String substring = stringBuilder.substring(i, i+count);
    byte1 = map2.get(substring);
    if(byte1==null)
    {
     count++;
    }
    else 
    {
     flag=false;
    }
    
   }
   list.add(byte1);
   i+=count;  
  }
  
  byte [] by=new byte[list.size()];
  for(int i=0;i<by.length;i++)
  {
   by[i]=list.get(i);
  }
  return by;
 }
 
 private static String byteToBitString(boolean flag, byte b)
 {
  int temp=b;
  if(flag)
  {
   temp|=256;
  }
  
  String binaryString = Integer.toBinaryString(temp);
  if(flag)
  {
   return binaryString.substring(binaryString.length()-8);
  }
  else
  {
   return binaryString;
  }
  
 }
 
 private static byte[] huffmanZip(byte [] array)
 {
  List<Node> nodes = getNodes(array);
  Node createHuffManTree = createHuffManTree(nodes);
  Map<Byte, String> m=getCodes(createHuffManTree);
  byte[] zip = zip(array, m);
  return zip; 
 }
 
 //
 private static byte[] zip(byte [] array,Map<Byte,String> map)
 {
  StringBuilder sBuilder=new StringBuilder();
  for(byte item:array)
  {
   String value=map.get(item);
   sBuilder.append(value);
  }
  //System.out.println(sBuilder);
  int len;
  if(sBuilder.toString().length()%8==0)//如果可以整除
  {
   len=sBuilder.toString().length()/8;
  }
  else //如果不能整除
  {
   len=sBuilder.toString().length()/8+1;
  }
  
  byte [] by=new byte[len];
  int index=0;
  for(int i=0;i<sBuilder.length();i+=8)
  {
   String string;
   if((i+8)>sBuilder.length())
   {
    string=sBuilder.substring(i);
   }
   else 
   {
    string=sBuilder.substring(i, i+8);
   }
      
   by[index]=(byte)Integer.parseInt(string,2);
   index++;
  }
  
  return by;
   
 }
 
 
 //重載
 private static Map<Byte, String> getCodes(Node root)
 {
  if(root==null)
  {
   return null;
  }
  getCodes(root.leftNode,"0",sBuilder);
  getCodes(root.rightNode,"1",sBuilder);
  return map;
 }
 
 
 
 //獲取哈夫曼編碼
  static Map<Byte, String> map=new HashMap<>();
  static StringBuilder sBuilder=new StringBuilder();
  public static void getCodes(Node node,String code,StringBuilder stringBuilder)
  {
   StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
   stringBuilder2.append(code);
   if(node!=null)
   {
    if(node.data==null)//非葉子結(jié)點(diǎn)
    {
     //向左遞歸
     getCodes(node.leftNode,"0",stringBuilder2);
     //向右遞歸
     getCodes(node.rightNode,"1",stringBuilder2);
    }
    else //如果是葉子結(jié)點(diǎn)
    {
     map.put(node.data,stringBuilder2.toString());
    }
   }
  }
 
 
 
 public static List<Node> getNodes(byte [] array)
 {
  List<Node> list=new ArrayList<Node>();
  Map<Byte, Integer> map=new HashMap<Byte, Integer>();
  for(Byte data:array)
  {
   Integer count=map.get(data);//通過(guò)鍵獲取值
   if(count==null)//說(shuō)明此時(shí)map集合中還沒(méi)有改字符
   {
    map.put(data, 1);
   }
   else 
   {
    map.put(data,count+1);
   }
  }
  //遍歷map集合
  Set<Byte> set=map.keySet();
  for(Byte key:set)
  {
   int value=map.get(key);
   Node node=new Node(key, value);
   list.add(node);
  }
  return list;
 }
 
 private static Node createHuffManTree(List<Node> list)
 {
  while(list.size()>1)
  {
   Collections.sort(list);//先對(duì)集合進(jìn)行排序
   Node leftNode=list.get(0);
   Node rightNode=list.get(1);
   
   Node parentNode=new Node(null, leftNode.weight+rightNode.weight);
   parentNode.leftNode=leftNode;
   parentNode.rightNode=rightNode;
   
   list.remove(leftNode);
   list.remove(rightNode);
   
   list.add(parentNode);
  }
  return list.get(0);
  
 }

}

class Node implements Comparable<Node>
{
 Byte data;//字符
 int weight;//字符出現(xiàn)的次數(shù)
 Node leftNode;
 Node rightNode;
 
 public Node(Byte data,int weight)//構(gòu)造器
 {
  this.data=data;
  this.weight=weight;
 }

 @Override
 public int compareTo(Node o) 
 {
  return this.weight-o.weight;
 }

 @Override
 public String toString() 
 {
  return "Node [data=" + data + ", weight=" + weight + "]";
 }
 
 //前序遍歷
 public void preOrder()
 {
  System.out.println(this);
  if(this.leftNode!=null)
  {
   this.leftNode.preOrder();
  }
  if(this.rightNode!=null)
  {
   this.rightNode.preOrder();
  }
 }
 
 
}