using System;
using System.Collections.Generic;
using System.Text;

namespace Cluster
{
    public class KmeansClassifier
    {
        int N;    //數據個數
        int K;    //集合個數
        int[] CenterIndex; //初始化質心數組的索引
        float[] Center;  //質心集合
        float[] CenterCopy; //質心集合副本
        float[] AllData; //數據集合
        float[][] Cluster; //簇的集合
        int[] Top;   //集合中元素的個數，也會用作棧處理

        //隨機生成k個數x(0<=x<=n-1)作為起始的質心集合中元素的ID
        void CreateRandomArray(int n, int k, int[] center)
        {
            int i = 0, j;
            bool flag;

            Random random = new Random();

            while (i < k)      //隨機生成k個數
            {
                int randK = random.Next(n);
                flag = false;

                for (j = 0; j < i; j++)   //判重
                {
                    if (center[j] == randK) //重復
                    {
                        flag = true;
                        break;
                    }
                }

                if (flag == false)   //如果不重復，加入
                {
                    center[i] = randK;
                    i++;
                }
                else      //如果重復，本次重新隨機生成
                {
                }
            }
        }

        //返回距離最小的質心的序號
        int GetIndex(float value, float[] center)
        {
            int i;
            int index = 0;      //最小的質心序號
            double min = Math.Abs(value - center[0]); //距質心最小距離

            for (i = 0; i < K; i++)
            {
                if (Math.Abs(value - center[i]) < min) //如果比當前距離還小，更新最小的質心序號和距離值
                {
                    index = i;
                    min = Math.Abs(value - center[i]);
                }
            }

            return index;
        }

        //拷貝質心數組到副本
        void CopyCenter()
        {
            int i;

            for (i = 0; i < K; i++)
            {
                CenterCopy[i] = Center[i];
            }
        }

        //初始化質心，隨機生成法
        void InitCenter()
        {
            int i = 0;
            CreateRandomArray(N, K, CenterIndex);   //產生隨機的K個<N的不同的序列

            for (i = 0; i < K; i++)
            {
                Center[i] = AllData[CenterIndex[i]];//將對應數據賦值給質心數組
            }

            // CopyCenter();          //拷貝到質心副本
        }

        //加入一個數據到一個Cluster[index]集合
        void AddToCluster(int index, float value)
        {
            Cluster[index][Top[index]++] = value; //這里同進棧操作
        }

        //重新計算簇集合
        void UpdateCluster()
        {
            int i = 0;
            int tempIndex;

            //將所有的集合清空，即將TOP置0
            for (i = 0; i < K; i++)
            {
                Top[i] = 0;
            }

            for (i = 0; i < N; i++)
            {
                tempIndex = GetIndex(AllData[i], Center); //得到與當前數據最小的質心索引
                AddToCluster(tempIndex, AllData[i]);      //加入到相應的集合中 
            }
        }

        //重新計算質心集合，對每一簇集合中的元素加總求平均即可
        void UpdateCenter()
        {
            int i, j;
            double sum;

            for (i = 0; i < K; i++)
            {
                sum = 0;
                //計算簇i的元素和
                for (j = 0; j < Top[i]; j++)
                {
                    sum += Cluster[i][j];
                }
                if (Top[i] > 0)//如果該簇元素不為空
                {
                    Center[i] = (float)sum / Top[i];//求其平均值
                }
            }
        }

        //判斷2數組元素是否相等
        bool IsEqual(float[] center1, float[] center2)
        {
            int i;

            for (i = 0; i < K; i++)
            {
                if (Math.Abs(center1[i] != center2[i]))
                {
                    return false;
                }
            }

            return true;
        }

        //打印聚合結果
        void Print()
        {
            int i, j;
            printf("-------------------------------------- ");
            for (i = 0; i < K; i++)
            {
                printf("\n第%d個聚類: 質心(%f)", i, Center[i]);
                for (j = 0; j < Top[i]; j++)
                {
                    printf("%f ", Cluster[i][j]);
                }
            }
        }

        /// <summary>
        /// 初始化聚類的各種數據
        /// </summary>
        /// <param name="N">數據個數</param>
        /// <param name="K"><簇個數/param>
        void InitData(float[] data, int k)
        {
            AllData = data;
            N = data.Length;
            K = k;

            if (K > N)
            {
                throw new Exception("N less than K");
            }

            //為質心集合申請空間
            Center = new float[K];
            //為質心集合索引申請空間
            CenterIndex = new int[K];
            //為質心集合副本申請空間
            CenterCopy = new float[K];
            Top = new int[K];

            //Cluster = (float**)malloc(sizeof(float*) * K);
            //為簇集合申請空間
            Cluster = new float[K][];

            //初始化K個簇集合
            for (i = 0; i < K; i++)
            {
                //Cluster[i] = (float*)malloc(sizeof(float) * N);
                Cluster[i] = new float[N];
                Top[i] = 0;
            }

            InitCenter();//初始化質心集合      
            UpdateCluster();//初始化K個簇集合
        }

        /*********************************************************
        算法描述:
         K均值聚類算法:
            給定類的個數K，將N個對象分到K個類中去，
            使得類內對象之間的相似性最大，而類之間的相似性最小。
        **********************************************************/
        //main()
        //{
        //    int Flag=1;//迭代標志，若為false,則迭代結束
        //    int i=0;
        // InitData();//初始化數據      
        // while (Flag)//開始迭代
        // {
        //  UpdateCluster();//更新各個聚類
        //  UpdateCenter();//更新質心數組
        //  if (IsEqual(Center, CenterCopy))//如果本次迭代與前次的質心聚合相等，即已收斂，結束退出
        //  {
        //   Flag = 0;
        //  }
        //  else//否則將質心副本置為本次迭代得到的的質心集合
        //  {
        //   CopyCenter();//將質心副本置為本次迭代得到的的質心集合
        //  }
        // }

        // Print();//輸出結果
        // getchar();
        // getchar();

        //}
    }
}