using System;
using System.Collections.Generic;
using System.Linq;

namespace iWareModel
{
    public class Huffman
    {
        /// <summary>
        /// 原始的编码字符的集合
        /// </summary>
        private char[] mDict;

        /// <summary>
        /// 原始编码字符中实际使用到的字符集（用于需要编码的字符串中的字符小于所定义的字符集）
        /// </summary>
        private char[] mCntDict;

        /// <summary>
        /// 无参构造函数
        /// </summary>
        public Huffman()
        {
            this.mDict = new char[0];
            mCntDict = mDict;
        }

        /// <summary>
        /// 构造函数，给定Haffman字符的字段集合
        /// </summary>
        /// <param name="dict"></param>
        public Huffman(char[] dict)
        {
            this.mDict = dict.Distinct().ToArray();
            mCntDict = mDict;
        }

        /// <summary>
        /// 构造函数，给定Haffman字符的字段集合
        /// </summary>
        public Huffman(string dict)
        {
            this.mDict = dict.ToCharArray().Distinct().ToArray();
            mCntDict = mDict;
        }

        /// <summary>
        /// 将字符串转Huffman码，并且生成字符转换的关键字典集
        /// </summary>
        /// <param name="key">导出的关键字字典</param>
        /// <param name="str">需要编码的huffman集合</param>
        /// <returns></returns>
        public string StringToHuffmanCode(out Dictionary<char, string> key, string str)
        {
            var tmps = GetWeightArray(str);
            var tree = CreateHuffmanTree(tmps);
            key = CreateHuffmanCode("", tree);
            return ToHuffmanCode(str, key);
        }

        /// <summary>
        /// 关键关键字典将编码还原
        /// </summary>
        /// <param name="code"></param>
        /// <param name="key"></param>
        /// <returns></returns>
        public string ToText(string code, Dictionary<char, string> key)
        {
            string result = "";

            for (int i = 0; i < code.Length; )
            {
                foreach (var item in key)
                {
                    if (code[i] == item.Value[0] && item.Value.Length + i <= code.Length)
                    {
                        char[] tmpArr = new char[item.Value.Length];
                        Array.Copy(code.ToCharArray(), i, tmpArr, 0, tmpArr.Length);
                        if (new string(tmpArr) == item.Value)
                        {
                            result += item.Key;
                            i += item.Value.Length;
                            break;
                        }
                    }
                }
            }
            return result;
        }


        /// <summary>
        /// 计算每个字符串的权重
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private Node[] GetWeightArray(string str)
        {
            var nodes = new List<Node>();
            var charArr = str.ToCharArray();
            if (charArr.Length < mDict.Length)
            {
                mCntDict = new char[charArr.Length];
                Array.Copy(mDict, 0, mCntDict, 0, charArr.Length);
            }
            while (charArr.Length > 0)
            {
                var tmp = charArr.Where(m => m == charArr[0]).ToArray();
                nodes.Add(new Node(tmp.Length, tmp.First()));
                charArr = charArr.Where(m => m != tmp.First()).ToArray();
            }
            return nodes.ToArray();
        }

        /// <summary>
        /// 生成Haffman树的算法
        /// </summary>
        /// <param name="nodes">原始的节点集合</param>
        /// <returns>生成好的Haffman树</returns>
        private Node CreateHuffmanTree(Node[] nodes)
        {
            if (nodes.Length <= mCntDict.Length)
            {
                var node = new Node(0, '\0');
                node.Children = nodes;
                foreach (var n in nodes) { node.Weight += n.Weight; }
                return node;
            }
            Array.Sort(nodes);
            var newNode = new Node(0, '\0');
            newNode.Children = new Node[mCntDict.Length];

            for (int i = nodes.Length - 1, j = 0; i >= 0; i--, j++)
            {
                if (j >= mCntDict.Length) { break;}
                newNode.Weight += nodes[i].Weight;
                newNode.Children[j] = nodes[i];
            }

            var newNodes = new Node[nodes.Length - mCntDict.Length + 1];
            Array.Copy(nodes, 0, newNodes, 0, newNodes.Length - 1);
            newNodes[newNodes.Length - 1] = newNode;
            return CreateHuffmanTree(newNodes);
        }

        /// <summary>
        /// 生成关键字典集
        /// </summary>
        /// <param name="code">默认填充字符</param>
        /// <param name="hTree"></param>
        /// <returns></returns>
        private Dictionary<char, string> CreateHuffmanCode(string code, Node hTree)
        {
            var key = new Dictionary<char, string>();
            if (hTree.Children == null)
            {
                key.Add(hTree.Key, code);
            }
            else
            {
                for (int i = 0; i < hTree.Children.Length; i++)
                {
                    var tmpDict = CreateHuffmanCode(code + mCntDict[i], hTree.Children[i]);

                    foreach (var item in tmpDict)
                    {
                        key.Add(item.Key, item.Value);
                    }
                }
            }
            return key;
        }
        
        /// <summary>
        /// 关键生成的数将字符转出Haffman码
        /// </summary>
        /// <param name="source"></param>
        /// <param name="key"></param>
        /// <returns></returns>
        private string ToHuffmanCode(string source, Dictionary<char, string> key)
        {
            string result = "";

            for (int i = 0; i < source.Length; i++)
            {
                result += key.First(m => m.Key == source[i]).Value;
            }
            return result;
        }
    }

    public class Node : IComparable
    {
        public Node[] Children { get; set; }
        public int Weight { get; set; }
        public char Key { get; set; }
        public Node() { }
        public Node(int weight, char value)
        {
            this.Weight = weight;
            this.Key = value;
        }

        /// <summary>
        /// 关键权重降序排序
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public int CompareTo(object obj)
        {
            var tmp = obj as Node;
            if (tmp.Weight > this.Weight) { return 1; }
            if (tmp.Weight < this.Weight) { return -1; }
            return 0;
        }
    }
}