using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

namespace demo_win_extractColor
{
    /// <summary>
    /// 用于图像分色
    /// </summary>
    public class ExtractImageColor2
    {
        public const int sigbits = 5;
        public const int rshift = 8 - sigbits;
        public const int maxIterations = 1000;
        public const float fractByPopulations = 0.75f;

        public static int getColorIndex(int r, int g, int b)
        {
            return (r << (2 * sigbits)) + (g << sigbits) + b;
        }

        /// <summary>
        /// 得到第一个颜色
        /// </summary>
        /// <param name="sourceImage"></param>
        /// <param name="quality"></param>
        /// <returns></returns>
        public static int?[] getColor(Bitmap sourceImage, int quality = 10)
        {
            var palette = getPalette(sourceImage, 5, quality);
            var dominantColor = palette[0];
            return dominantColor;
        }

        /// <summary>
        /// 得到颜色数组
        /// </summary>
        /// <param name="sourceImage"></param>
        /// <param name="colorCount"></param>
        /// <param name="quality"></param>
        /// <returns></returns>
        public static List<int?[]> getPalette(Bitmap sourceImage, int colorCount = 10, int quality = 10)
        {
            //颜色数量
            if (colorCount < 1) colorCount = 10;

            //多少个像素进行分割
            if (quality < 1) quality = 10;

            var pixels = new List<Color>();
            for (int i = 0; i < sourceImage.Height; i++)
                for (int j = 0; j < sourceImage.Width; j++)
                    pixels.Add(sourceImage.GetPixel(j, i));

            var pixelCount = pixels.Count;

            var pixelArray = new List<Color>();

            //间隔进行像素点采样，每个像素点都包含a r g b 四个值（a为透明度）
            for (int i = 0; i < pixelCount; i = i + quality)
            {
                var color = pixels[i];
                // If pixel is mostly opaque and not white
                if (color.A >= 125)
                {
                    //大于白色都去掉
                    if (!(color.R > 250 && color.G > 250 && color.B > 250))
                    {
                        //加入到对象里面，这里面就是rgb的值
                        pixelArray.Add(color);
                    }
                }
            }

            var cmap = quantize(pixelArray, colorCount);


            List<int?[]> palette = cmap != null ? cmap.palette<int?[]>() : null;

            // Clean up

            return palette;
        }

        /// <summary>
        /// 这段代码？切分矩阵
        /// </summary>
        /// <param name="partialsum"></param>
        /// <param name="lookaheadsum"></param>
        /// <param name="vbox"></param>
        /// <param name="color"></param>
        /// <param name="total"></param>
        /// <returns></returns>
        static VBox[] doCut(Dictionary<int, int?> partialsum,
            Dictionary<int, int?> lookaheadsum,
            VBox vbox, string color, int total)
        {
            int i,
                left, right, d2;
            VBox vbox1, vbox2;

            //从一个维度的最小值到最大值，rgb。
            for (i = vbox[color][0]; i <= vbox[color][1]; i++)
            {
                //代表里面的命中的像素以及大于整体的一半信息。
                if (partialsum[i] > total / 2)
                {
                    vbox1 = vbox.copy();
                    vbox2 = vbox.copy();

                    left = i - vbox[color][0];
                    right = vbox[color][1] - i;

                    if (left <= right)
                        d2 = Math.Min(vbox[color][1] - 1, ~~(i + right / 2));
                    else
                        d2 = Math.Max(vbox[color][0], ~~(i - 1 - left / 2));

                    while (!partialsum[d2].HasValue) d2++;
                    //肯定有内容
                    var count2 = lookaheadsum[d2];
                    while (
                        (!count2.HasValue || count2.Value == 0)
                        && partialsum.ContainsKey(d2 - 1)
                        && partialsum[d2 - 1].HasValue
                        && partialsum[d2 - 1].Value > 0)
                        count2 = lookaheadsum[--d2];

                    // set dimensions
                    vbox1[color] = new int[] { vbox1[color][0], d2 };
                    vbox2[color] = new int[] { d2 + 1, vbox2[color][1] };

                    return new VBox[] { vbox1, vbox2 };
                }
            }

            return null;

        }

        static object[] medianCutApply(int[] histo, VBox vbox)
        {
            if (vbox.count() == 0) return null;

            int rw = vbox.r2 - vbox.r1 + 1,
                gw = vbox.g2 - vbox.g1 + 1,
                bw = vbox.b2 - vbox.b1 + 1,

                //最大颜色，按照最大的变进行切分
                maxw = Math.Max(Math.Max(rw, gw), bw);


            // only one pixel, no split
            if (vbox.count() == 1)
            {
                return new VBox[] { vbox.copy(), null };
            }
            /* Find the partial sum arrays along the selected axis. */
            int total = 0;
            Dictionary<int, int?> partialsum = new Dictionary<int, int?>();
            Dictionary<int, int?> lookaheadsum = new Dictionary<int, int?>();
            int i, j, k, sum, index;

            if (maxw == rw)
            {
                for (i = vbox.r1; i <= vbox.r2; i++)
                {
                    sum = 0;
                    for (j = vbox.g1; j <= vbox.g2; j++)
                    {
                        for (k = vbox.b1; k <= vbox.b2; k++)
                        {
                            index = getColorIndex(i, j, k);
                            sum += index < histo.Length ? histo[index] : 0;
                        }
                    }
                    total += sum;
                    partialsum[i] = total;
                }
            }
            else if (maxw == gw)
            {
                for (i = vbox.g1; i <= vbox.g2; i++)
                {
                    sum = 0;
                    for (j = vbox.r1; j <= vbox.r2; j++)
                    {
                        for (k = vbox.b1; k <= vbox.b2; k++)
                        {
                            index = getColorIndex(j, i, k);
                            sum += index < histo.Length ? histo[index] : 0;
                        }
                    }
                    total += sum;
                    partialsum[i] = total;
                }
            }
            else
            {  /* maxw == bw */
                for (i = vbox.b1; i <= vbox.b2; i++)
                {
                    sum = 0;
                    for (j = vbox.r1; j <= vbox.r2; j++)
                    {
                        for (k = vbox.g1; k <= vbox.g2; k++)
                        {
                            index = getColorIndex(j, k, i);
                            sum += index < histo.Length ? histo[index] : 0;
                        }
                    }
                    total += sum;
                    partialsum[i] = total;
                }
            }
            partialsum.Foreach((o) =>
            {
                //计算剩余的部分
                lookaheadsum[o.Key] = total - o.Value;
            });

            // determine the cut planes
            return
                maxw == rw ? doCut(partialsum, lookaheadsum, vbox, "r", total) :
                maxw == gw ? doCut(partialsum, lookaheadsum, vbox, "g", total) :
                doCut(partialsum, lookaheadsum, vbox, "b", total);
        }


        //<PQueue<T>, Dictionary<int, int>, float> 
        static void iter<T>(PQueue<T> lh, int[] histo, float target)
        {
            var ncolors = 1;
            var niters = 0;
            T vbox;

            while (niters < maxIterations)
            {
                vbox = lh.pop();
                if ((vbox as VBox).count() == 0)
                { /* just put it back */
                    lh.push(vbox);
                    niters++;
                    continue;
                }

                var vboxes = medianCutApply(histo, vbox as VBox);

                T vbox1 = (T)vboxes[0];
                T vbox2 = (T)vboxes[1];

                if (vbox1 == null)
                {
                    //无法切分                    ("vbox1 not defined; shouldn't happen!");
                    return;
                }
                lh.push(vbox1);
                if (vbox2 != null)
                {  /* vbox2 can be null */
                    lh.push(vbox2);
                    ncolors++;
                }

                //找到最集中的点的数量，已经大于我们需要的，就不要在继续切分
                if (ncolors >= target) return;

                //循环的次数如果太多，也不要继续循环。
                if (niters++ > maxIterations)
                {
                    //                    ("infinite loop; perhaps too few pixels!");
                    return;
                }
            }
        }

        /// <summary>
        /// 开始计算
        /// </summary>
        /// <param name="pixels"></param>
        /// <param name="maxcolors"></param>
        /// <returns></returns>
        private static CMap quantize(List<Color> pixels, int maxcolors)
        {

            if (pixels.Count == 0 || maxcolors < 2 || maxcolors > 256)
            {
                return null;
            }

            //得到颜色空间 里面每种颜色的数量集合
            var histo = getHisto(pixels);

            //color总数
            var nColors = 0;

            //代表总共有多少种颜色，通过采样出来的
            histo.Foreach((o) =>
            {
                if (o > 0) nColors++;
            });

            //如果颜色还少于需要计算的颜色，应该不现实？
            if (nColors <= maxcolors)
            {
                // XXX: generate the new colors from the histo and return
            }

            //得到颜色的三维空间中 三个向量的最大值 最小值
            var vbox = vboxFromPixels(pixels, histo);

            var pq = new PQueue<VBox>((a, b) =>
            {
                return naturalOrder(a.count(), b.count());
            });
            pq.push(vbox);

            //按照像素点进行切分
            iter(pq, histo, fractByPopulations * maxcolors);

            //切分完毕的数据，按照重量进行排序
            var pq2 = new PQueue<VBox>(
            (a, b) =>
            {
                return naturalOrder(a.count() * a.volume(), b.count() * b.volume());
            });

            //把切分完毕的，装在进去
            while (pq.size() > 0)
            {
                pq2.push(pq.pop());
            }

            //?继续切分吗？
            iter(pq2, histo, maxcolors - pq2.size());


            // calculate the actual colors
            var cmap = new CMap();
            while (pq2.size() > 0)
            {
                cmap.push(pq2.pop());
            }

            return cmap;
        }

        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static int naturalOrder(int a, int b)
        {
            return a < b ? -1 : (a > b ? 1 : 0);
        }

        /// <summary>
        /// 得到矩阵中的顶点坐标
        /// </summary>
        /// <param name="pixels"></param>
        /// <param name="histo"></param>
        /// <returns></returns>
        static VBox vboxFromPixels(List<Color> pixels, int[] histo)
        {
            int rmin = 1000000, rmax = 0,
                gmin = 1000000, gmax = 0,
                bmin = 1000000, bmax = 0,
                rval, gval, bval;

            // find min/max
            pixels.ForEach((o) =>
            {
                rval = o.R >> rshift;
                gval = o.G >> rshift;
                bval = o.B >> rshift;

                if (rval < rmin) rmin = rval;
                else if (rval > rmax) rmax = rval;
                if (gval < gmin) gmin = gval;
                else if (gval > gmax) gmax = gval;
                if (bval < bmin) bmin = bval;
                else if (bval > bmax) bmax = bval;
            });

            //返回所有像素中，rgb中分别的最大值和最小值
            return new VBox(rmin, rmax, gmin, gmax, bmin, bmax, histo);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="pixels"></param>
        /// <returns></returns>
        static int[] getHisto(List<Color> pixels)
        {
            var histosize = 1 << (3 * sigbits);

            var histo = new int[histosize];// (histosize),
            int index, rval, gval, bval;

            pixels.ForEach((o) =>
            {
                rval = o.R >> rshift;
                gval = o.G >> rshift;
                bval = o.B >> rshift;
                index = getColorIndex(rval, gval, bval);

                histo[index]++;
            });

            return histo;
        }

        internal static int sum(int?[] ints)
        {
            int t = 0;
            foreach (var o in ints)
                t += o.Value;

            return t;
        }
    }

    public class CMap
    {
        public PQueue<CMapObject> vboxes = new PQueue<CMapObject>((a, b) =>
        {
            return ExtractImageColor2.naturalOrder(
                a.vbox.count() * a.vbox.volume(),
                b.vbox.count() * b.vbox.volume()
            );
        });

        /// <summary>
        /// 压入矩阵
        /// </summary>
        /// <param name="vbox"></param>
        public void push(VBox vbox)
        {
            vboxes.push(new CMapObject(vbox, vbox.avg()));
        }


        /// <summary>
        /// 抽取颜色
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <returns></returns>
        public List<T> palette<T>()
        {
            return vboxes.map<T>(
                (o) =>
                {
                    return (T)(((o as CMapObject).color) as object);
                });
        }

        /// <summary>
        /// 有多少矩阵
        /// </summary>
        /// <returns></returns>
        public int size()
        {
            return vboxes.size();
        }

        /// <summary>
        /// 查找对应的颜色
        /// </summary>
        /// <param name="color"></param>
        /// <returns></returns>
        public int?[] map(int[] color)
        {
            var vboxes = this.vboxes;

            for (var i = 0; i < vboxes.size(); i++)
            {
                //发现颜色点落到矩阵内部，就直接用这个颜色
                if (vboxes.peek(i).vbox.contains(color))
                {
                    return vboxes.peek(i).color;
                }
            }

            //否则就找聚合点
            return this.nearest(color);
        }

        /// <summary>
        /// 计算vbox聚合中心点位置
        /// </summary>
        /// <param name="color"></param>
        /// <returns></returns>
        public int?[] nearest(int[] color)
        {
            var vboxes = this.vboxes;

            double d1 = -1, d2;
            int?[] pColor = null;
            for (var i = 0; i < vboxes.size(); i++)
            {
                d2 = Math.Sqrt(
                    Math.Pow((double)color[0] - (double)vboxes.peek(i).color[0], 2.0) +
                    Math.Pow((double)color[1] - (double)vboxes.peek(i).color[1], 2.0) +
                    Math.Pow((double)color[2] - (double)vboxes.peek(i).color[2], 2.0)
                );
                if (d2 < d1 || d1 == -1)
                {
                    d1 = d2;
                    pColor = vboxes.peek(i).color;
                }
            }
            return pColor;
        }
        void forcebw()
        {
            // XXX: won't  work yet
            var vboxes = this.vboxes;
            vboxes.sort((a, b) =>
            {
                return
                    ExtractImageColor2.naturalOrder(
                    ExtractImageColor2.sum(a.color),
                    ExtractImageColor2.sum(b.color));
            });

            // force darkest color to black if everything < 5
            var lowest = vboxes[0].color;
            if (lowest[0] < 5 && lowest[1] < 5 && lowest[2] < 5)
                vboxes[0].color = new int?[] { 0, 0, 0 };

            // force lightest color to white if everything > 251
            var idx = vboxes.size() - 1;
            var highest = vboxes[idx].color;
            if (highest[0] > 251 && highest[1] > 251 && highest[2] > 251)
                vboxes[idx].color = new int?[] { 255, 255, 255 };
        }
    }

    public class PQueue<T>
    {
        List<T> contents = new List<T>();
        bool sorted = false;

        //public delegate int Comparartor(VBox a, VBox b);


        public PQueue(Func<T, T, int> comparator)
        {
            this.comparator = comparator;
        }

        public T this[int index]
        {
            get
            {
                return contents.ElementAt(index);
            }
        }

        public void push(T o)
        {
            contents.Add(o);
            sorted = false;
        }

        void sort()
        {
            contents.Sort(new Comparison<T>(comparator));
            sorted = true;
        }

        public void sort(Func<T, T, int> _comparator)
        {
            contents.Sort(new Comparison<T>(_comparator));
            sorted = true;
        }

        public T peek(int index = -1)
        {
            if (!sorted) sort();
            if (index == -1)
                index = contents.Count() - 1;
            return contents[index];
        }

        public T pop()
        {
            if (!sorted) sort();
            if (contents.Count > 0)
            {
                var obj = contents.ElementAt<T>(0);
                contents.RemoveAt(0);
                return obj;
            }
            return default(T);
        }
        public int size()
        {
            return contents.Count();
        }

        public List<T1> map<T1>(Func<T, T1> f)
        {
            var list = new List<T1>();
            foreach (var o in contents)
            {
                list.Add(f(o));
            }
            return list;
        }


        public Func<T, T, int> comparator { get; set; }
    }

    public class CMapObject
    {
        public VBox vbox;
        public int?[] color;

        public CMapObject(VBox vbox, int?[] color)
        {
            this.vbox = vbox;
            this.color = color;
        }
    }

    public class VBox
    {
        public VBox(int r1, int r2, int g1, int g2, int b1, int b2, int[] histo)
        {
            this.r1 = r1;
            this.r2 = r2;
            this.g1 = g1;
            this.g2 = g2;
            this.b1 = b1;
            this.b2 = b2;

            this.histo = histo;
        }

        /// <summary>
        /// 设置参数或者
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int[] this[string s]
        {
            get
            {
                if (s == "r") return new int[] { r1, r2 };
                if (s == "g") return new int[] { g1, g2 };
                if (s == "b") return new int[] { b1, b2 };

                //不会发生
                return null;
            }
            set
            {
                if (s == "r")
                {
                    r1 = value[0];
                    r2 = value[1];
                }
                if (s == "g")
                {
                    g1 = value[0];
                    g2 = value[1];
                }
                if (s == "b")
                {
                    b1 = value[0];
                    b2 = value[1];
                }

            }
        }

        private int? _volume;
        /// <summary>
        /// 得到颜色空间的体积
        /// </summary>
        /// <param name="force"></param>
        /// <returns></returns>
        public int volume(bool force = false)
        {
            if (!this._volume.HasValue || force)
                this._volume = (r1 - r2 + 1) * (g1 - g2 + 1) * (b1 - b2 + 1);
            return this._volume.Value;
        }

        bool _count_set = false;
        int _count = 0;
        /// <summary>
        /// 得到空间的点政数量
        /// </summary>
        /// <param name="force"></param>
        /// <returns></returns>
        public int count(bool force = false)
        {
            if (!_count_set || force)
            {
                int npix = 0,
                    i, j, k;
                for (i = r1; i <= r2; i++)
                {
                    for (j = g1; j <= g2; j++)
                    {
                        for (k = b1; k <= b2; k++)
                        {
                            var index = ExtractImageColor2.getColorIndex(i, j, k);
                            npix += index < histo.Length ? histo[index] : 0;
                        }
                    }
                }
                _count = npix;
                _count_set = true;
            }
            return _count;
        }

        /// <summary>
        /// 对象复制
        /// </summary>
        /// <returns></returns>
        public VBox copy()
        {
            //返回新的VBOX
            return new VBox(r1, r2, g1, g2, b1, b2, histo);
        }

        public int?[] _avg;
        public int?[] avg(bool force = false)
        {
            var vbox = this;
            var histo = vbox.histo;
            if (vbox._avg == null || force)
            {
                int ntot = 0,
                    mult = 1 << (8 - ExtractImageColor2.sigbits);

                float rsum = 0,
                   gsum = 0,
                   bsum = 0;
                int hval,
                  i, j, k, histoindex;
                for (i = vbox.r1; i <= vbox.r2; i++)
                {
                    for (j = vbox.g1; j <= vbox.g2; j++)
                    {
                        for (k = vbox.b1; k <= vbox.b2; k++)
                        {
                            histoindex =
                                ExtractImageColor2.getColorIndex(i, j, k);
                            hval = histoindex < histo.Length ? histo[histoindex] : 0;
                            ntot += hval;
                            rsum += (hval * (i + 0.5f) * mult);
                            gsum += (hval * (j + 0.5f) * mult);
                            bsum += (hval * (k + 0.5f) * mult);
                        }
                    }
                }
                if (ntot > 0)
                {
                    vbox._avg = new int?[] { 
                        ~~(int)(rsum / ntot),
                        ~~(int)(gsum / ntot), 
                        ~~(int)(bsum / ntot) 
                    };
                }
                else
                {
                    vbox._avg = new int?[]{
                        ~~(mult * (vbox.r1 + vbox.r2 + 1) / 2),
                        ~~(mult * (vbox.g1 + vbox.g2 + 1) / 2),
                        ~~(mult * (vbox.b1 + vbox.b2 + 1) / 2)
                    };
                }
            }
            return vbox._avg;
        }

        /// <summary>
        /// 判断像素是否在矩阵范围内
        /// </summary>
        /// <param name="pixel"></param>
        /// <returns></returns>
        public bool contains(int[] pixel)
        {
            var vbox = this;
            int rval = pixel[0] >> ExtractImageColor2.rshift;
            int gval = pixel[1] >> ExtractImageColor2.rshift;
            int bval = pixel[2] >> ExtractImageColor2.rshift;
            return (rval >= vbox.r1 && rval <= vbox.r2 &&
                    gval >= vbox.g1 && gval <= vbox.g2 &&
                    bval >= vbox.b1 && bval <= vbox.b2);
        }



        public int b2 { get; set; }
        public int b1 { get; set; }

        public int g2 { get; set; }
        public int g1 { get; set; }

        public int r2 { get; set; }
        public int r1 { get; set; }
        public int[] histo { get; set; }
    }
}