DynamicArray of T

DynamicArrayOfT.cs

IEnumerable< T > 인터페이스를 상속받는 동적배열 generic 클래스입니다.

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

namespace Collections
{
    internal class DynamicArray<T> : IEnumerable<T>
        where T : IComparable<T>
    {
        private static int DEFAULT_SIZE = 1;
        
        public int Count => _count;
        public int Capacity => _items.Length;

        public T this[int index] // 인덱스 프로퍼티
        {
            get
            {
                if ((uint)index >= _count)
                {
                    throw new IndexOutOfRangeException();
                }

                return _items[index];
            }
            set
            {
                if ((uint)index >= _count)
                {
                    throw new IndexOutOfRangeException();
                }

                _items[index] = value;
            }
        }

        private T[] _items = new T[DEFAULT_SIZE];
        private int _count;

        // 삽입 알고리즘
        // 일반적인 경우에는 O(1), 공간이 모자란 경우에는 O(N) 
        public void Add(T item)
        {
            if (_count == _items.Length)
            {
                T[] tmpItems = new T[_count * 2];
                Array.Copy(_items, 0, tmpItems, 0, _count);
                _items = tmpItems;
            }

            _items[_count++] = item;
        }

        // 탐색 알고리즘
        // 최악의 경우 O(N)
        public T Find(Predicate<T> match)
        {
            for (int i = 0; i < _count; i++)
            {
                if (match.Invoke(_items[i]))
                {
                    return _items[i];
                }
            }

            return default(T);
        }
        
        // 탐색 알고리즘
        // 최악의 경우 O(N)
        // 공간 복잡도도 최악의 경우 O(N)
        public MyDynamicArray<T> FindAll(Predicate<T> match)
        {
            MyDynamicArray<T> result = new MyDynamicArray<T>();
            
            for (int i = 0; i < _count; i++)
            {
                if (match.Invoke(_items[i]))
                {
                    result.Add(_items[i]);
                }
            }

            return result;
        }
        
        // 탐색 알고리즘
        // 최악의 경우 O(N)
        public int IndexOf(T item)
        {
            for (int i = 0; i < _count; i++)
            {
                if (Comparer<T>.Default.Compare(_items[i], item) == 0)
                {
                    return i;
                }
            }

            return -1;
        }

        // 삭제 알고리즘
        public bool Remove(T item)
        {
            int index = IndexOf(item);

            if (index < 0)
            {
                return false;
            }

            for (int i = index; i < _count; i++)
            {
                _items[i] = _items[i + 1];
            }

            _count--;
            return true;
        }
        
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < _count; i++)
            {
                yield return _items[i];
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        public struct Enumerator : IEnumerator<T>
        {
            public bool MoveNext()
            {
                _index++;
                return _index < _data._count;
            }

            public void Reset()
            {
                _index = -1;
            }

            public T Current => _data._items[_index];

            object IEnumerator.Current => _data._items[_index];

            private MyDynamicArray<T> _data;
            private int _index;
            public Enumerator(MyDynamicArray<T> data)
            {
                _data = data;
                _index = -1; // MoveNext()를 먼저 호출하기 때문에 -1로 초기화;
            }

            public void Dispose() // 관리되지 않는 힙 영역(Unmanagerd Heap Memory) 에 올라간 데이터는 직접 해제를 해줘야 한다.
                                  // 관리되는 힙 영역(Managed Heap Memory)에 올라간 데이터는 GC가 관리해준다.
            {
                throw new NotImplementedException();
            }
        }
    }
}