using System;
using System.Collections.Generic;
using System.Text;
namespace Chorice_List
{
/// <summary>
/// Iterating을 하면서 수정/삭제가 가능한 List가 필요해 만들어진 List입니다.
/// Doubly Linked List로 구현되어 있으며
/// foreach를 통한 Iteration 또한 가능합니다.
/// (단 foreach 중에는 Collction을 수정할 수 없습니다.)
/// </summary>
/// <typeparam name="T"></typeparam>
class ChoriceList<T> : IList<T>
{
/* Nested Classes */
/* List 내부에서 쓰이는 노드입니다. */
class Node
{
public T Data;
public Node Prev, Next;
public Node()
{
Data = null;
Prev = Next = null;
}
public Node(T Data)
{
Node();
this.Data = Data;
}
public Node(Node Prev, T Data)
{
Node(Data);
this.Prev = Prev;
Prev.Next = this;
}
public Node(Node Prev, Node Next, T Data)
{
Node(Prev, Data);
this.Next = Next;
Next.Prev = this;
}
public T Remove()
{
if (this.Prev != null) this.Prev.Next = this.Next;
if (this.Next != null) this.Next.Prev = this.Prev;
return this.Data;
}
}
/* Foreach를 위한 Enumerator입니다. */
class Enumerator<T2> : IEnumerator<T2>
{
private Node current; /* 현재 Enumerator가 가리키는 노드 */
private Node dummy; /* 가장 처음 노드의 앞 노드입니다. */
public T2 Current
{
get
{
if (current == null || current == dummy)
{
throw new InvalidOperationException();
}
return current.Data;
}
}
/* MoveNext()와 Reset()은 List가 수정되면 Exception을 내야 한다.
* 하지만 어떻게 수정을 감지하는지 모른다.
*/
/* 한칸 전진시킨다. current가 적당한 값이 아니면 false 리턴 */
public bool MoveNext()
{
if (current!= null)
current = current.Next;
if (current == null || current == dummy)
return false;
return true;
}
/* 현재 Enumerator가 가리키는 것을 가장 처음으로 되돌린다. */
public void Reset()
{
current = dummy;
}
/* 현재 Enumerator를 메모리 공간에서 삭제한다. */
public void Dispose()
{
//뭘 넣어야 되는거지? -_-
}
/* 생성자들 */
public Enumerator()
{
current = dummy = null;
}
public Enumerator(Node BeforeFirst)
{
Enumerator();
dummy = BeforeFirst;
current = dummy;
}
public Enumerator(Node BeforeFirst, Node Current)
{
Enumerator(BeforeFirst);
current = Current;
}
}
/* Properties */
private Node dummy; //List를 만들면 자동으로 만들어지는 더미노드
private Node current; //Enumerator를 통하지 않고 Iterating을 지원하기 위함.
private int count;
private bool isReadOnly;
public int Count { get { return count; } }
public bool IsReadOnly { get { return isReadOnly; } }
/* Methods */
/// <summary>
/// ChoriceList를 반복하는 열거자를 반환합니다.
/// </summary>
/// <returns></returns>
public IEnumerator<T> GetEnumerator()
{
return new Enumerator<T>(dummy);
}
/* For Implementing IList */
/* []을 이용한 Indexing. o(n) time complexity. n = index or the size of this list. */
public T this[int index]
{
get
{
Node n = dummy;
int i = 0;
while (i <= index && (n = n.Next) != null)
i++;
if (n != dummy && n != null)
return n;
throw new ArgumentOutOfRangeException();
}
set
{
Node n = dummy;
int i = 0;
if (0 <= index && index < count)
{
for (i; i <= index; i++)
n = n.Next;
n.Data = value;
}
else if (index == count)
{
while (n.Next != null)
n = n.Next;
Node(n, value);
count++;
}
else
{
throw new ArgumentOutOfRangeException();
}
}
}
/// <summary>
/// 이 ChoriceList에서 해당 Item의 Index를 반환합니다.
/// 만약 해당 Item이 여러개 있다면 가장 앞에 있는 것의 Index를 반환합니다.
/// 해당 Item이 List에 존재 하지 않으면 -1을 반환합니다.
/// </summary>
public int IndexOf(T Item)
{
Node n = dummy;
int i = 0;
while ((n = n.Next) != null)
{
if (n.Data.Equals(Item))
return i;
i++;
}
return -1;
}
/// <summary>
/// 해당 Index에 Item을 추가합니다. Linear Search이며
/// Time Complexity는 o(n) 입니다.
/// </summary>
/// <param name="Index"></param>
/// <param name="Item"></param>
public void Insert(int Index, T Item)
{
if (isReadOnly) throw new NotSupportedException();
Node n = dummy;
int i = 0;
if (0 <= index && index < count)
{
for (i; i < index; i++)
n = n.Next;
Node(n, n.Next, Item);
count++;
}
else if (index == count)
{
while (n.Next != null)
n = n.Next;
Node(n, value);
count++;
}
else
{
throw new ArgumentOutOfRangeException();
}
}
/// <summary>
/// 해당 Index의 Item을 삭제합니다.
/// Time Complexity는 o(n) 입니다.
/// </summary>
/// <param name="Index"></param>
public void RemoveAt(int Index)
{
if (isReadOnly) throw new NotSupportedException();
Node n = dummy;
int i = 0;
if (0 <= index && index < count)
{
for (i; i <= index; i++)
n = n.Next;
n.Remove();
count--;
}
else
{
throw new ArgumentOutOfRangeException();
}
}
/* For Implementing ICollection */
/// <summary>
/// 해당 Item을 이 ChoriceList에 더합니다. List의 가장 마지막 부분에 더하게 됩니다.
/// </summary>
public void Add(T Item)
{
if (isReadOnly) throw new NotSupportedException();
Insert(count, Item);
}
/// <summary>
/// 이 ChoriceList를 비웁니다.
/// </summary>
public void Clear()
{
if (isReadOnly) throw new NotSupportedException();
dummy.Next = null;
count = 0;
}
/// <summary>
/// 이 ChoriceList에 해당 Item이 저장되어 있는지 확인합니다.
/// Comparer가 아닌 Equals를 이용하여 구현합니다.
/// </summary>
/// <param name="Item"></param>
/// <returns></returns>
public bool Contains(T Item)
{
Node n = dummy;
int i = 0;
for (i; i <= count; i++)
{
n = n.Next;
if (n.Data.Equals(Item))
return true;
}
return false;
}
/// <summary>
/// 이 ChoriceList를 해당 Array의 해당 ArrayIndex로 복사합니다.
/// </summary>
/// <param name="Array"></param>
/// <param name="ArrayIndex"></param>
public void CopyTo(T[] Array, int ArrayIndex)
{
//Check Exceptions
if (Array = null)
throw new ArgumentNullException();
if (ArrayIndex < 0)
throw new ArgumentOutOfRangeException();
if (Array.Rank != 1 || ArrayIndex >= Array.Length
|| count > Array.Length - ArrayIndex || !Array.GetType().IsAssignableFrom(T))
throw new ArithmeticException();
Node n = dummy;
int i = ArrayIndex;
while ((n = n.Next) != null)
Array[i++] = n;
}
/// <summary>
/// 이 ChoriceList에 들어있는 Item 중 가장 먼저 보이는 것을 삭제합니다.
/// </summary>
/// <param name="Item"></param>
/// <returns></returns>
public bool Remove(T Item)
{
if (isReadOnly) throw new NotSupportedException();
Node n = dummy;
int i = 0;
while ((n = n.Next) != null)
{
if (n.Data.Equals(Item))
{
n.Remove();
count--;
return true;
}
}
return false;
}
/* .Net FrameWork의 기본 Generic List에 나오는 구현들 */
/* 자체 Iteration을 위한 구현들 */
/* 생성자들 */
public ChoriceList()
{
dummy = new Node();
count = 0;
isReadOnly = false;
}
public ChoriceList(T Item)
{
ChoriceList();
Node(dummy, Item);
count++;
}
}
}