namespace AlgorithmTest06_List
{
    interface IListDS<T>
    {
        int GetLength();//求长度

        void Chear();//清空

        bool IsEmpty();//判断线性表是否为空

        T Add(T item);//添加

        void Insert(int index, T item);//插入

        T Delete(int i);//删除

        T this[int i] { get; }//定义索引器 获取元素

        T GetElem(int i);//取表元

        T Set(int i, T item);//修改

        int IndexOf(T value);//按值查找

        void Remove(T value);//根据值删除
    }
}

/// <summary>
/// 实现顺序表
/// </summary>
/// <typeparam name="T"></typeparam>
class SeqList<T> : IListDS<T>
{
    //新建类,继承IListDs<T>并且实现接口
    private T[] data;//存储数据的数组
    private int count = 0;
    /// <summary>
    /// size:设定成员个数,默认构造函数容量为10
    /// </summary>
    /// <param name="size"></param>
    public SeqList(int size)
    {//size是最大容量
        data = new T[size];
        count = 0;
    }
    public SeqList() : this(10) { }
    /// <summary>
    /// index的位置插入item值
    /// </summary>
    /// <param name="index"></param>
    /// <param name="item"></param>
    public void Insert(int index, T item)
    {//插入
        if (index < 0 || index > count)
        {
            throw new ArgumentException("数组索引越界");
        }
        if (count == data.Length)
        {
            //throw new ArgumentException("数组已满");
            ResetCapacity(2 * data.Length);//数组扩容加原来两倍
        }
        for (int i = count - 1; i >= index; i--)
        {
            data[i + 1] = data[i];
        }
        data[index] = item;
        count++;
    }
    /// <summary>
    /// 末尾添加
    /// </summary>
    /// <param name="item"></param>
    public T Add(T item)
    {
        Insert(count, item);
        return item;
    }
    /// <summary>
    /// 删除index位置的值
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T Delete(int index)
    {
        if (count == data.Length / 4)//不足四分之一时,空间减少
        {
            ResetCapacity(data.Length / 2);
        }
        if (index < 0 || index >= count)
        {
            throw new ArgumentException("索引超出数组界限");
        }
        T temp = data[index];
        for (int i = index + 1; i < count; i++)
        {
            data[i - 1] = data[i];//左移
        }
        count--;
        data[count] = default(T);
        return temp;
    }
    public void Chear()
    {
        count = 0;
    }
    /// <summary>
    /// 通过i查找对应内容
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        if (i >= 0 && i < count)//索引存在
        {
            return data[i];
        }
        else
        {
            return default(T);
            throw new ArgumentException("索引不存在");
        }
    }
    public T this[int i]
    {
        get { return GetElem(i); }
    }
    /// <summary>
    /// 索引i,替换内容为item
    /// </summary>
    /// <param name="i"></param>
    /// <param name="item"></param>
    /// <returns></returns>
    public T Set(int i, T item)
    {
        if (i >= 0 && i < count)//索引存在
            return data[i] = item;
        else
            throw new ArgumentException("索引越界");
    }
    /// <summary>
    /// 获取数组长度
    /// </summary>
    /// <returns></returns>
    public int GetCount()
    {
        return count;//非空数量
    }
    public int GetLength()
    {
        return data.Length;//总元素

    }
    /// <summary>
    /// 是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return count == 0;
    }
    /// <summary>
    /// 根据值找索引
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public int IndexOf(T value)
    {
        for (int i = 0; i < count; i++)
        {
            if (data[i].Equals(value))//不能用==,因为都是值类型,不合法
            {//确定指定的对象是否等于当前对象。
                return i;
            }
        }
        return -1;//值不存在
    }
    /// <summary>
    /// 根据值删除对象
    /// </summary>
    /// <param name="value"></param>
    public void Remove(T value)
    {
        int index = IndexOf(value);
        if (index != -1)//不能是搜寻不到的数
        {
            Delete(index);//删除
        }
    }
    /// <summary>
    /// 打印
    /// </summary>
    /// <returns></returns>
    public override string ToString()
    {
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < count - 1; i++)
        {
            res.Append(data[i]);
            // if (i != count - 1)
            //如果不是最后一个元素
            //{
            res.Append(",");
            //}
        }
        res.Append(data[count - 1]);
        return res.ToString();
    }
    /// <summary>
    /// 扩容数组,私有
    /// </summary>
    /// <param name="newCapacity"></param>
    private void ResetCapacity(int newCapacity)
    {
        T[] newData = new T[newCapacity];//newCapacity:扩容多少
        for (int i = 0; i < count; i++)
        {
            newData[i] = data[i];//赋值
        }
        data = newData;//再赋值,为了让他外部可用
    }
}

class Program
{
            static void Main(string[] argss)
    {
        #region 添加和删除
        //使用自己封装的顺序表
        SeqList<int> seqlist = new SeqList<int>(20);
        Console.WriteLine("元素个数:" + seqlist.GetCount());
        for (int i = 0; i < 10; i++)
        {
            seqlist.Add(i);
        }
        Console.WriteLine("已添加元素个数:" + seqlist.GetCount());
        Console.WriteLine("----------------");

        Console.WriteLine("索引3添加数字100");
        seqlist.Insert(3, 100);//索引3添加数字100
        //for (int i = 0; i < seqlist.GetLength(); i++)
        //{
        //    Console.Write(seqlist.GetElem(i) + ";");
        //}
        Console.WriteLine(seqlist);

        Console.WriteLine("个数:" + seqlist.GetCount());

        seqlist.Chear();

        Console.WriteLine("清空后个数:" + seqlist.GetCount());

        Console.WriteLine("是否为空" + seqlist.IsEmpty());

        Console.WriteLine("----------------");

        for (int i = 4; i > 0; i--)
        {
            seqlist.Add(i);
        }
        //for (int i = 0; i < seqlist.GetLength(); i++)
        //{
        //    Console.Write(seqlist[i] + ";");
        //}
        Console.WriteLine("重新添加4~1");
        Console.WriteLine(seqlist);

        Console.WriteLine("\n----------------");


        Console.WriteLine("删除:" + seqlist.Delete(2));
        //for (int i = 0; i < seqlist.GetLength(); i++)
        //{
        //    Console.Write(seqlist[i] + ";");
        //}
        Console.WriteLine("打印" + seqlist);

        Console.WriteLine("\n----------------");
        #endregion

        #region 查找
        Console.WriteLine("输入值找索引(-1为找不到):");
        int value = int.Parse(Console.ReadLine());
        Console.WriteLine("索引:" + seqlist.IndexOf(value));
        Console.WriteLine("当前值:" + seqlist);
        Console.WriteLine("找到后删除对象");
        seqlist.Remove(value);
        Console.WriteLine("----------------");
        Console.WriteLine("当前值:" + seqlist);
        Console.WriteLine("索引0替换为100");
        seqlist.Set(0, 100);
        Console.WriteLine(seqlist);
        #endregion

        #region 扩容数组(动态数组)
        Console.WriteLine("----------------");
        Console.WriteLine("扩容数组");
        SeqList<int> seq = new SeqList<int>(10);
        for (int i = 0; i < 10; i++)
        {
            seq.Add(i);
        }
        Console.WriteLine("数组元素展示:" + seq);
        Console.WriteLine("容量:" + seq.GetLength());
        Console.WriteLine("数组元素数量:" + seq.GetCount());
        Console.WriteLine("添加元素:" + seq.Add(1000));
        Console.WriteLine("数组元素展示:" + seq);
        Console.WriteLine("容量" + seq.GetLength());
        Console.WriteLine("数组元素数量:" + seq.GetCount());
        #endregion



        Console.ReadKey();
    }
}

public override string ToString()
       {
           StringBuilder res = new StringBuilder();

           for (int i = 0; i < count; i++)
           {
               res.Append(data[i]);
               if (i != count - 1)
               //如果不是最后一个元素
               {
                   res.Append(", ");
               }
           }
           return res.ToString();
       }

public override string ToString()
        {
            StringBuilder res = new StringBuilder();

            for (int i = 0; i < count - 1; i++)
            {
                res.Append(data[i]);
                // if (i != count - 1)
                //如果不是最后一个元素
                //{
                res.Append(",");
                //}
            }
            res.Append(data[count - 1]);
            return res.ToString();
        }