//------------------------------------------------------------------------------
// C# ConsoleView Control
// Copyright (C) 2011 Cores Co., Ltd. Japan
//------------------------------------------------------------------------------
// $Id: RingBuffer.cs 88 2011-04-05 11:03:57Z nagasima $
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleView
{
	class RingBuffer<T> : IList<T>
	{
		private T[] m_Buffer;
		private int m_First;
		private int m_Last;

		/// <summary>
		/// コンストラクタ
		/// </summary>
		/// <param name="capacity">リングバッファの容量、最大要素数</param>
		public RingBuffer(int capacity)
		{
			m_Buffer = new T[capacity + 1];
			m_First = -1;
			m_Last = -1;
		}

		/// <summary>リングバッファの容量</summary>
		public int Capacity
		{
			get { return m_Buffer.Length; }
		}

		/// <summary>最初の位置</summary>
		public int First
		{
			get { return m_First; }
		}

		/// <summary>最後の位置</summary>
		public int Last
		{
			get { return m_Last; }
		}

		/// <summary>
		/// 次の位置を取得
		/// </summary>
		/// <param name="position">指定位置</param>
		/// <returns>指定位置の次の位置</returns>
		int GetNext(int position)
		{
			int result;

			if (position == (m_Buffer.Length - 1))
				result = 0;
			else
				result = position + 1;

			if (result == m_First)
				return -1;

			return result;
		}

		/// <summary>
		/// 前の位置を取得
		/// </summary>
		/// <param name="position">指定位置</param>
		/// <returns>指定位置の前の位置</returns>
		int GetPrev(int position)
		{
			int result;

			if (position == 0)
				result = (m_Buffer.Length - 1);
			else
				result = position - 1;

			if (result == m_Last)
				return -1;

			return result;
		}

		/// <summary>
		/// 連続なバッファを取得する
		/// </summary>
		/// <param name="index">取得するバッファ位置</param>
		/// <param name="size">連続なバッファのサイズ</param>
		/// <returns>バッファ位置</returns>
		int GetBuffer(int index, out int size)
		{
			int result;

			if (m_First == -1)
			{
				size = 0;
				result = -1;
			}
			else if (m_First <= m_Last)
			{
				size = m_Last - m_First + 1;

				if (index < size)
				{
					result = m_First;
					result += index;
					size -= index;
				}
				else
				{
					size = 0;
					result = -1;
				}
			}
			else
			{
				size = (m_Buffer.Length - 1) - m_First + 1;

				if (index < size)
				{
					result = m_First;
					result += index;
					size -= index;
				}
				else
				{
					index -= size;
					size = m_Last + 1;

					if (index < size)
					{
						result = 0;
						result += index;
						size -= index;
					}
					else
					{
						size = 0;
						result = -1;
					}
				}
			}

			return result;
		}

		#region IList<T> メンバ

		public int IndexOf(T item)
		{
			int result = 0;
			foreach (T item2 in this)
			{
				if (item2.Equals(item))
					return result;
				result++;
			}
			return -1;
		}

		public void Insert(int index, T item)
		{
			int size, rest = Count - index;
			int pos = GetBuffer(index, out size);
			int dst = -1;
			T Temp = default(T);

			while (rest > 0)
			{
				if (dst >= 0)
					m_Buffer[dst] = Temp;

				Temp = m_Buffer[pos + size - 1];

				if (size > 1)
					Buffer.BlockCopy(m_Buffer, pos + 1, m_Buffer, pos, size - 1);

				dst = pos;
				rest -= size;
			}

			m_Last = GetNext(m_Last);
		}

		public void RemoveAt(int index)
		{
			int size, rest = Count - index;
			int pos = GetBuffer(index, out size);
			int dst = -1;

			while (rest > 0)
			{
				if (dst >= 0)
					m_Buffer[dst] = m_Buffer[pos];

				if (size > 1)
					Buffer.BlockCopy(m_Buffer, pos, m_Buffer, pos + 1, size - 1);

				dst = pos + size - 1;
				rest -= size;
			}

			m_Last = GetPrev(m_Last);
		}

		public T this[int index]
		{
			get
			{
				int size;
				int pos = GetBuffer(index, out size);
				return m_Buffer[pos];
			}
			set
			{
				int size;
				int pos = GetBuffer(index, out size);
				m_Buffer[pos] = value;
			}
		}

		#endregion

		#region ICollection<T> メンバ

		/// <summary>
		/// 要素を新しく追加し、領域が一杯の時は最も古い要素を削除する
		/// </summary>
		/// <param name="item">新しい要素</returns>
		public void Add(T item)
		{
			// まだひとつも使っていない場合
			if (m_Last == -1)
			{
				m_First = 0;
				m_Last = 0;
			}
			else
			{
				// 最後の割り当て領域の次の領域を計算
				if (m_Last == (m_Buffer.Length - 1))
					m_Last = 0;
				else
					m_Last = m_Last + 1;

				// 先頭に追いついたら
				if (m_First == m_Last)
				{
					// 先頭を進める
					if (m_First == (m_Buffer.Length - 1))
						m_First = 0;
					else
						m_First = m_First + 1;
				}
			}

			m_Buffer[m_Last] = item;
		}

		/// <summary>
		/// リングバッファをクリアする
		/// </summary>
		public void Clear()
		{
			m_First = -1;
			m_Last = -1;
		}

		public bool Contains(T item)
		{
			foreach (T item2 in this)
			{
				if (item2.Equals(item))
					return true;
			}
			return false;
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			int i = arrayIndex;
			foreach (T item in this)
			{
				array[i++] = item;
				if (i == array.Length)
					return;
			}
		}

		/// <summary>
		/// リングバッファにある要素数を返す
		/// </summary>
		public int Count
		{
			get
			{
				int Result;

				if (m_First == -1)
				{
					Result = 0;
				}
				else if (m_First <= m_Last)
				{
					Result = 1 + (m_Last - m_First);
				}
				else
				{
					Result = 1 + ((m_Buffer.Length - 1) - m_First + m_Last);
				}

				return Result;
			}
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		public bool Remove(T item)
		{
			int pos = IndexOf(item);
			if (pos < 0)
				return false;

			RemoveAt(pos);

			return true;
		}

		#endregion

		#region IEnumerable<T> メンバ

		public IEnumerator<T> GetEnumerator()
		{
			int pos = m_First;
			while ((pos = GetNext(pos)) > 0)
			{
				yield return m_Buffer[pos];
			}
		}

		#endregion

		#region IEnumerable メンバ

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			int pos = m_First;
			while ((pos = GetNext(pos)) > 0)
			{
				yield return m_Buffer[pos];
			}
		}

		#endregion
	}
}
