FloodFill

using System;
using System.Diagnostics;

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

        private static void Main()
        {
            var map = new byte[MAP_SIZE * MAP_SIZE];

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

            Console.WriteLine(stopwatch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        private static 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;
            }

            int size = 1 << shift;
            int sizeMinusOne = size - 1;
            int xMask = size - 1;
            int minIndexForVerticalCheck = size;
            int maxIndexForVerticalCheck = map.Length - size - 1;

            map[startIndex] = toValue;

            var queue = new FastQueue<int>();
            queue.Enqueue(startIndex);

            while (queue.Count > 0)
            {
                int index = queue.Dequeue();
                int x = index & xMask;

                if (x > 0)
                {
                    if (map[index - 1] == fromValue)
                    {
                        map[index - 1] = toValue;
                        queue.Enqueue(index - 1);
                    }
                }
                if (x < sizeMinusOne)
                {
                    if (map[index + 1] == fromValue)
                    {
                        map[index + 1] = toValue;
                        queue.Enqueue(index + 1);
                    }
                }
                if (index >= minIndexForVerticalCheck)
                {
                    if (map[index - size] == fromValue)
                    {
                        map[index - size] = toValue;
                        queue.Enqueue(index - size);
                    }
                }
                if (index <= maxIndexForVerticalCheck)
                {
                    if (map[index + size] == fromValue)
                    {
                        map[index + size] = toValue;
                        queue.Enqueue(index + size);
                    }
                }
            }
        }
    }

    internal class FastQueue<T> where T : struct
    {
        private const int INITIAL_CAPACITY = 16;

        private T[] items;
        private int size;
        private int mask;
        private int head, tail;

        public FastQueue()
        {
            items = new T[INITIAL_CAPACITY];
            mask = INITIAL_CAPACITY - 1;
            head = tail = 0;
            size = 0;
        }

        public int Count
        {
            get { return size; }
        }

        public void Enqueue(T item)
        {
            if (size == items.Length)
            {
                IncreaseCapacity(items.Length << 1);
            }

            items[head & mask] = item;
            head++;
            size++;
        }

        public T Dequeue()
        {
            var item = items[tail & mask];
            tail++;
            size--;
            return item;
        }

        private void IncreaseCapacity(int capacity)
        {
            Array.Resize(ref items, capacity);
            mask = capacity - 1;
        }
    }
}