using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EvoBoat.EvoAlg.Perm
{
    /// <summary>
    /// A permutation of {0,1,...,n-1}
    /// </summary>
    public class PermVector : IVector<int>, ICloneable<PermVector>
    {
        protected int n;
        public int Length
        {
            get { return n; }
        }

        internal int[] values;
        public int this[int index]
        {
            get { return values[index]; }
            set { values[index] = value; }
        }

        PermVector() { }

        public PermVector(int n, bool bInit = true)
        {
            this.n = n;
            values = new int[n];
            if (bInit)
                for (int i = 0; i < n; i++)
                    values[i] = i;
        }

        public PermVector(int[] array)
        {
            this.n = array.Length;
            this.values = array.ToArray();
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder("{");
            for (int i = 0; i < values.Length; i++)
            {
                sb.Append(values[i]);
                sb.Append(',');
            }
            if (sb.Length > 1)
                sb[sb.Length - 1] = '}';
            else
                sb.Append('}');
            return sb.ToString();
        }

        public override bool Equals(object obj)
        {
            PermVector v = obj as PermVector;
            return (!object.ReferenceEquals(v, null) && this == v);
        }

        public override int GetHashCode()
        {
            return values.GetHashCode();
        }

        public IEnumerator<int> GetEnumerator()
        {
            for (int i = 0; i < values.Length; i++)
                yield return values[i];
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public PermVector Clone()
        {
            PermVector p = new PermVector(n, false);
            values.CopyTo(p.values, 0);
            return p;
        }

        public int IndexOf(int v)
        {
            for (int i = 0; i < values.Length; i++)
                if (values[i] == v)
                    return i;
            return -1;
        }

        public void Swap(int i, int j)
        {
            int temp = values[i];
            values[i] = values[j];
            values[j] = temp;
        }

        public void Reverse(int i, int j)
        {
            for (int k = i; k <= (i + j) / 2; k++)
                Swap(k, (i + j) - k);
        }

        /// <summary>
        /// 将解向量中第i个元素的位置移动到第j个位置之前
        /// </summary>
        public void Move(int i, int j)
        {
            int tmp = values[i];
            if (j > i)
            {
                for (int k = i; k < j; k++)
                    values[k] = values[k + 1];
            }
            else if (j < i)
            {
                for (int k = i; k > j; k--)
                    values[k] = values[k - 1];
            }
            values[j] = tmp;
        }
        
        public static bool operator ==(PermVector p1, PermVector p2)
        {
            if (p1.n != p2.n)
                return false;
            for (int i = 0; i < p1.n; i++)
                if (p1.values[i] != p2.values[i])
                    return false;
            return true;
        }

        public static bool operator !=(PermVector p1, PermVector p2)
        {
            return !(p1 == p2);
        }

        public static bool IsPerm(int[] x)
        {
            int n = x.Length, k;
            List<int> list = new List<int>(x);
            while(list.Count > 0)
            {
                k = list.IndexOf(--n);
                if (k < 0) return false;
                list.RemoveAt(k);
            }
            return true;
        }

        public static PermVector CreateRandom(Random rand, int n)
        {
            PermVector p = new PermVector(n, false);
            List<int> list = new List<int>(n);
            int i, j;
            for (i = 0; i < n; i++)
                list.Add(i);
            i = 0;
            while(list.Count > 0)
            {
                j = rand.Next(0, list.Count);
                p.values[i++] = list[j];
                list.RemoveAt(j);
            }
            return p;
        }
    }
}
