using System;
using System.Diagnostics;
using System.Linq;

namespace FloodFill
{
    internal class Program
    {
        private const int MAP_SIZE = 4096; // only powers of two are supported

        private static void Main()
        {
            var map = new byte[MAP_SIZE * MAP_SIZE];
            for (int i = 0; i < MAP_SIZE; i++)
            {
                map[0 * MAP_SIZE + i] = 1;
                map[(MAP_SIZE - 1) * MAP_SIZE + i] = 1;

                map[i * MAP_SIZE + 0] = 1;
                map[i * MAP_SIZE + MAP_SIZE - 1] = 1;
            }

            var stopwatch = Stopwatch.StartNew();
            {
                FloodFill(map, startX: 123, startY: 123, fromValue: 0, toValue: 1);
            }
            stopwatch.Stop();

            Console.WriteLine(stopwatch.ElapsedMilliseconds);

            // Test results
            if (map.Any(item => item == 0))
            {
                Console.WriteLine("Error");
            }
            else
            {
                Console.WriteLine("Ok");
            }

            Console.ReadLine();
        }

        private static unsafe void FloodFill(byte[] map, int startX, int startY, byte fromValue, byte toValue)
        {
            int shift = (int)Math.Round(Math.Log(map.Length, 4)); // if the array's length is (2^x * 2^x), then shift = x
            int startIndex = startX + (startY << shift);

            if (map[startIndex] != fromValue)
            {
                return;
            }

            // initialize flood fill
            int size = 1 << shift;
            int xMask = size - 1;

            // initialize queue
            int capacity = size * 2;
            int mask = capacity - 1;
            uint tail = 0;
            uint head = 0;
            var queue = new int[capacity];

            fixed (byte* m = map)
            fixed (int* q = queue)
            {
                *(m + startIndex) = toValue;
                *(q + (tail++ & mask)) = startIndex;

                while (tail - head > 0)
                {
                    int index = q[head++ & mask];
                    int x = index & xMask;
                    byte* p = m + index;

                    if (*(p - 1) == fromValue)
                    {
                        *(p - 1) = toValue;
                        *(q + (tail++ & mask)) = index - 1;
                    }

                    if (*(p + 1) == fromValue)
                    {
                        *(p + 1) = toValue;
                        *(q + (tail++ & mask)) = index + 1;
                    }

                    if (*(p - size) == fromValue)
                    {
                        *(p - size) = toValue;
                        *(q + (tail++ & mask)) = index - size;
                    }

                    if (*(p + size) == fromValue)
                    {
                        *(p + size) = toValue;
                        *(q + (tail++ & mask)) = index + size;
                    }
                }
            }
        }
    }
}