using System;
using System.Collections.Generic;

namespace yield
{

	public static class MovingMaxTask
	{
		public class QueueItem<T>
		{
			public T Value { get; set; }
			public QueueItem<T> Next { get; set; }
		}

		public class Queues<T>
		{
			public QueueItem<T> head { get;  set; }
			QueueItem<T> tail;

			public bool IsEmpty { get { return head == null; } }

			public void Enqueue(T value)
			{
				if (IsEmpty)
					tail = head = new QueueItem<T> { Value = value, Next = null };
				else
				{
					var item = new QueueItem<T> { Value = value, Next = null };
					tail.Next = item;
					tail = item;
				}
			}

			public T Dequeue()
			{
				if (head == null) throw new InvalidOperationException();
				var result = head.Value;
				head = head.Next;
				if (head == null)
					tail = null;
				return result;
			}
		}

		public static void Search(Queues<DataPoint> maxes, DataPoint element)
		{
			var current = maxes.head;
			if (current.Value == element)
			{
				if (current.Next!= null) maxes.head = current.Next;
				else current.Value = null;
				return;
			}

			while (current.Next != null)
			{
				if (current.Next.Value == element)
				{
					if (current.Next.Next != null) current.Next= current.Next.Next;

					else current.Next.Value = null;

					break;
				}
				current = current.Next;
			}
		}

		public static void Checker(Queues<DataPoint> maxes, DataPoint next)
		{
			var current = maxes.head;

			while (true)
			{
				if (next.OriginalY >= current.Value.OriginalY)
				{
					current.Value = next;
					current.Next = null;
					break;
				}

				else
				{
					if (current.Next == null)
					{
						current.Next = new QueueItem<DataPoint> { Value = next, Next = null };
						break;
					}
					else current = current.Next;
				}
			}
		}


		public static IEnumerable<DataPoint> MovingMax(this IEnumerable<DataPoint> data, int windowWidth)
		{

			var maxes = new Queues<DataPoint>();
			var queue = new Queues<DataPoint>();
			int queueCount = 0;

			foreach(var next in data)
			{
				queue.Enqueue(next);
				queueCount += 1;
				if (maxes.head == null)
					maxes.Enqueue(next);

				if (queueCount > windowWidth)
				{
					Search(maxes, queue.Dequeue());
					Checker(maxes, next);
				}

				else
					Checker(maxes, next);

				next.MaxY = maxes.head.Value.OriginalY;
				yield return next;

			}
			yield break;
		}
	}
}