using FigureCollections;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace SparseMatrix
{//основна программа
    class ClassName
    {
        static void Main(string[] args)
        {
            Rectangle rect = new Rectangle(5, 4);
            Square square = new Square(5);
            Circle circle = new Circle(5);
 
            Console.WriteLine("\nArrayList");
            ArrayList al = new ArrayList();
            al.Add(circle); al.Add(rect); al.Add(square);
 
            foreach (var x in al) Console.WriteLine(x);
 
            Console.WriteLine("\nArrayList - сортировка"); al.Sort();
            foreach (var x in al) Console.WriteLine(x);
 
            Console.WriteLine("\nList<Figure>");
            List<Figure> fl = new List<Figure>();
            fl.Add(circle);
            fl.Add(rect); fl.Add(square);
 
            foreach (var x in fl) Console.WriteLine(x);
 
            Console.WriteLine("\nList<Figure> - сортировка");
            fl.Sort();
            foreach (var x in fl) Console.WriteLine(x);
 
            Console.WriteLine("\nМатрица");
            Matrix3D<Figure> cube = new Matrix3D<Figure>(3, 3, 3, null);
            cube[0, 0, 0] = rect; cube[1, 1, 1] = square;
            cube[2, 2, 2] = circle;
            Console.WriteLine(cube.ToString());
 
            Console.WriteLine("\nСписок");
            SimpleList<Figure> list = new SimpleList<Figure>();
            list.Add(square); list.Add(rect);
            list.Add(circle);
 
            foreach (var x in list) Console.WriteLine(x);
 
            list.Sort();
            Console.WriteLine("\nСортировка списка");
            foreach (var x in list) Console.WriteLine(x);
 
            Console.WriteLine("\nСтек");
            SimpleStack<Figure> stack = new SimpleStack<Figure>();
            stack.Push(rect); stack.Push(square); stack.Push(circle);
 
            while (stack.Count > 0)
            {
                Figure f = stack.Pop();
                Console.WriteLine(f);
            }
 
            Console.ReadLine();
        }
 
    }
 
 
    //матриця
    namespace SparseMatrix
    {
        public class Matrix<T>
        {
        
            Dictionary<string, T> _matrix = new Dictionary<string, T>();   
            int maxX;
 
                 
            int maxY;
 
            T nullElement;
 
            public Matrix(int px, int py, T nullElementParam)
            {
                this.maxX = px; this.maxY = py;
                this.nullElement = nullElementParam;
            }
 
    
            public T this[int x, int y]
            {
                get
                {
                    CheckBounds(x, y); string key = DictKey(x, y); if (this._matrix.ContainsKey(key))
                    {
                        return this._matrix[key];
                    }
                    else
                    {
                        return this.nullElement;
                    }
                }
                set
                {
                    CheckBounds(x, y); string key = DictKey(x, y); this._matrix.Add(key, value);
                }
            }
    
            void CheckBounds(int x, int y)
            {
                if (x < 0 || x >= this.maxX) throw new Exception("x=" + x + " выходит за границы");
                if (y < 0 || y >= this.maxY) throw new Exception("y=" + y + " выходит за границы");
 
            }
 
            string DictKey(int x, int y)
            {
                return x.ToString() + "_" + y.ToString();
            }
 
    
            public override string ToString()
            {StringBuilder b = new StringBuilder();
 
                for (int j = 0; j < this.maxY; j++)
                {
                    b.Append("[");
                    for (int i = 0; i < this.maxX; i++)
                    {
                        if (i > 0) b.Append("\t");
                        b.Append(this[i, j].ToString());
                    }
                    b.Append("]\n");
                }
 
                return b.ToString();
            }
 
        }
    }
    //однозв'язний список
    namespace FigureCollections
    {
                public class SimpleListItem<T>
        {
                    public T data { get; set; }
            
            public SimpleListItem<T> next { get; set; }
                                    public SimpleListItem(T param)
            {
                this.data = param;
            }
        }
 
    
        public class SimpleList<T> : IEnumerable<T> where T : IComparable
        {
            
            protected SimpleListItem<T> first = null;
 
                    protected SimpleListItem<T> last = null;
 
            
            public int Count
            {
                get { return _count; }
                protected set { _count = value; }
            }
            int _count;       
            public void Add(T element)
            {
                SimpleListItem<T> newItem = new SimpleListItem<T>(element);
                this.Count++;
 
 
                if (last == null)
                {
 
                    this.first = newItem; this.last = newItem;
                }
 
                else
                {
                    this.last.next = newItem;
 
                    this.last = newItem;
                }
            }
 
            
            public SimpleListItem<T> GetItem(int number)
            {
                if ((number < 0) || (number >= this.Count))
                {
 
                    throw new Exception("Выход за границу индекса");
                }
 
                SimpleListItem<T> current = this.first; int i = 0;
 
 
                while (i < number)
                {
 
                    current = current.next;
                    i++;
                }
 
                return current;
            }
 
              
            public T Get(int number)
            {
                return GetItem(number).data;
            }
 
            public IEnumerator<T> GetEnumerator()
            {
                SimpleListItem<T> current = this.first;
 
                while (current != null)
                {
 
                    yield return current.data;
                    current = current.next;
                }
            }
            
            System.Collections.IEnumerator
            System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }
  
            public void Sort()
            {
                Sort(0, this.Count - 1);
            }
            private void Sort(int low, int high)
            {
                int i = low; int j = high;
                T x = Get((low + high) / 2); do
                {
                    while (Get(i).CompareTo(x) < 0) ++i;
                    while (Get(j).CompareTo(x) > 0) --j;
                    if (i <= j)
                    {
                        Swap(i, j); i++; j--;
                    }
                } while (i <= j);
 
                if (low < j) Sort(low, j); if (i < high) Sort(i, high);
            }
            private void Swap(int i, int j)
            {
                SimpleListItem<T> ci = GetItem(i);
                SimpleListItem<T> cj = GetItem(j);
                T temp = ci.data;
                ci.data = cj.data; cj.data = temp;
            }
        }
    }
}