#nullable disable
using System;
using System.Diagnostics;

/* Timer.runtimeconfig.json
{ "runtimeOptions": { "tfm": "net6.0", "framework": { "name": "Microsoft.NETCore.App", "version": "6.0.0-rc.1.21451.13" }
, "configProperties": { "System.GC.Concurrent": true, "System.GC.Server": true }
}}
*/
public class Node
{
	internal Node next;
	internal long runTime;

	public bool InTimer()
	{
		return next != null;
	}

	public long RunTime()
	{
		return runTime;
	}

	public virtual long OnTimer()
	{
		return 0;
	}
}

class Timer
{
	const int SLOT_SHIFT = 8;
	const int SLOTS_COUNT = 5;
	const int SLOT_MASK = (1 << SLOT_SHIFT) - 1;
	const int SLOT_SIZE = (1 << SLOT_SHIFT) * SLOTS_COUNT;

	readonly Node[] nodeHeads = new Node[SLOT_SIZE + 1];
	long curTime;

	public Timer(long curTime)
	{
		this.curTime = curTime;
	}

	public long CurTime()
	{
		return curTime;
	}

	public void Add(long runTime, Node node)
	{
		if (node.next != null)
			throw new Exception("added already");
		int idx;
		long dt = runTime - curTime;
		if (dt < 1L << SLOT_SHIFT)
		{
			if (dt < 0)
				idx = runTime < curTime ? (int)(runTime = curTime) & SLOT_MASK : SLOT_SIZE;
			else
				idx = (int)runTime & SLOT_MASK;
		}
		else if (dt < 1L << (SLOT_SHIFT * 2))
			idx = (1 << SLOT_SHIFT) + ((int)(runTime >> SLOT_SHIFT) & SLOT_MASK);
		else if (dt < 1L << (SLOT_SHIFT * 3))
			idx = (2 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 2)) & SLOT_MASK);
		else if (dt < 1L << (SLOT_SHIFT * 4))
			idx = (3 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 3)) & SLOT_MASK);
		else if (dt < 1L << (SLOT_SHIFT * 5))
			idx = (4 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 4)) & SLOT_MASK);
		else // SLOTS_COUNT overflow
			idx = SLOT_SIZE;
		Node[] heads = nodeHeads;
		Node head = heads[idx];
		if (head == null)
			node.next = node;
		else
		{
			node.next = head.next;
			head.next = node;
		}
		heads[idx] = node;
		node.runTime = runTime;
	}

	public void Update(long curTime)
	{
		long t = this.curTime;
		if (curTime < t)
			return;
		Node[] heads = nodeHeads;
		for (int idx = (int)t & SLOT_MASK; ;)
		{
			Node head = heads[idx];
			if (head != null)
			{
				this.curTime = t;
				do
				{
					heads[idx] = null;
					for (Node node = head.next; ;)
					{
						Node next = node.next;
						node.next = null;
						long nextTime = node.OnTimer();
						if (nextTime > 0)
							Add(t + nextTime, node);
						if (node == head)
							break;
						node = next;
					}
				}
				while ((head = heads[idx]) != null);
			}
			if (t == curTime)
			{
				this.curTime = t;
				return;
			}
			if ((idx = (int)++t & SLOT_MASK) == 0)
			{
				int i = 1;
				while (((t >> (i * SLOT_SHIFT)) & SLOT_MASK) == 0 && i < SLOTS_COUNT - 1)
					i++;
				for (; i > 0; i--)
				{
					int begin = i << SLOT_SHIFT;
					int shift = i * SLOT_SHIFT;
					int idx1 = begin + ((int)(t >> shift) & SLOT_MASK);
					if ((head = heads[idx1]) != null)
					{
						heads[idx1] = null;
						begin -= 1 << SLOT_SHIFT;
						shift -= SLOT_SHIFT;
						for (Node node = head.next; ;)
						{
							Node next = node.next;
							idx1 = begin + ((int)(node.runTime >> shift) & SLOT_MASK);
							Node head1 = heads[idx1];
							if (head1 == null)
								node.next = node;
							else
							{
								node.next = head1.next;
								head1.next = node;
							}
							heads[idx1] = node;
							if (node == head)
								break;
							node = next;
						}
					}
				}
			}
		}
	}

	struct Random
	{
		long seed;

		public long Rand()
		{
			long r = seed * 6364136223846793005L + 1442695040888963407L;
			seed = r;
			return r;
		}
	}

	sealed class State
	{
		public Random rand = new();
		public readonly Timer timer;
		public long runCount;

		public State()
		{
			timer = new((int)rand.Rand());
		}
	}

	sealed class TestNode : Node
	{
		readonly State state;

		public TestNode(State s)
		{
			state = s;
		}

		public override long OnTimer()
		{
			State s = state;
			long runTime = RunTime();
			long curTime = s.timer.CurTime();
			if (runTime != curTime)
				throw new Exception(string.Format("0x%X != 0x%X", runTime, curTime));
			s.runCount++;
			return s.rand.Rand() & 0x1_ffff;
		}
	}

	static void Main(string[] args)
	{
		Stopwatch sw = Stopwatch.StartNew();
		State state = new();
		Timer timer = state.timer;
		long curTime = timer.CurTime();
		for (int i = 0; i < 100_000; i++)
			timer.Add(curTime + (state.rand.Rand() & 0x1_ffff), new TestNode(state));
		for (int i = 0; i < 86_400_000; i += 33)
			timer.Update(curTime + i);
		sw.Stop();
		Console.WriteLine(state.runCount + ", time: " + sw.Elapsed);
	}
}