using System;

using System.Collections.Generic;

namespace Assistance {

	public class KeyHistory<t> where T: IComparable, new() {</t>

		public class Holder: IDisposable {

			public readonly KeyHistory<t> history;</t>

			public readonly long ticks;

			public readonly double timeOffset;

			private readonly long heldTicks;

			private bool disposed = false;

			public Holder(KeyHistory<t> history, long ticks, double timeOffset = 0.0) {</t>

				this.history = history;

				this.ticks = ticks;

				this.timeOffset = timeOffset;

				heldTicks = history.hold(ticks);

			}

			public Holder offset(double timeOffset) {

				return Geometry.isEqual(timeOffset, 0.0)

				     ? this

				     : new Holder(history, ticks, this.timeOffset + timeOffset);

			}

			public KeyState<t>.Holder get(double time) {</t>

				long dticks = (long)Math.Ceiling(Timer.frequency*(time + timeOffset));

				KeyState<t> state = history.get(ticks + dticks);</t>

				return new KeyState<t>.Holder(state, ticks, timeOffset + time);</t>

			}

			public void Dispose() { 

				Dispose(true);

				GC.SuppressFinalize(this);           

			}

			protected virtual void Dispose(bool disposing) {

				if (disposed) return;

				history.release(heldTicks);

				disposed = true;

			}

			~Holder()

				{ Dispose(false); }

		}

		private readonly List<keystate<t>> states = new List<keystate<t>>() { new KeyState<t>() };</t></keystate<t></keystate<t>

		private readonly List<long> locks = new List<long>();</long></long>

		public KeyState<t> current</t>

			{ get { return states[ states.Count - 1 ]; } }

		public KeyState<t> change(bool press, T value, long ticks)	{</t>

			states.Add(current.change(press, value, ticks));

			autoRemove();

			return current;

		}

		public KeyState<t> press(T value, long ticks)</t>

			{ return change(true, value, ticks); }

		public KeyState<t> release(T value, long ticks)</t>

			{ return change(false, value, ticks); }

		private int findLock(long ticks) {

			// locks[a] <= ticks < locks[b]

			if (locks.Count == 0) return -1;

			int a = 0;

			int b = locks.Count - 1;

			if (locks[a] < ticks) return -1;

			if (ticks >= locks[b]) return b;

			while(true) {

				int c = (a + b)/2;

				if (a == c) break;

				if (ticks < locks[c]) b = c; else a = c;

			}

			return a;

		}

		private void autoRemove() {

			long ticks = locks.Count > 0 ? locks[0] : long.MaxValue;

			while(states.Count > 1 && (states[0].ticks < ticks || states[0].isEmpty))

				states.RemoveAt(0);

		}

		private long hold(long ticks) {

			long heldTicks = Math.Max(ticks, states[0].ticks);

			locks.Insert(findLock(heldTicks) + 1, heldTicks);

			return heldTicks;

		}

		private void release(long heldTicks) {

			int i = findLock(heldTicks);

			if (i >= 0 && locks[i] == heldTicks) locks.RemoveAt(i);

			autoRemove();

		}

		private KeyState<t> get(long ticks) {</t>

			// state[a].ticks <= ticks < state[b].ticks 

			int a = 0;

			int b = states.Count - 1;

			if (states[a].ticks < ticks) return new KeyState<t>();</t>

			if (ticks >= states[b].ticks) return states[b];

			while(true) {

				int c = (a + b)/2;

				if (a == c) break;

				if (ticks < states[c].ticks) b = c; else a = c;

			}

			return states[a];

		}

	}

}