using UnityEngine;
using System.Collections.Generic;


namespace kun.Maze
{
    public abstract class Cell
    {
        public int x;
        public int y;
        public bool[] walls;


        public Cell(int x , int y)
        {
            this.x = x;
            this.y = y;
        }


        public int GetRandomNeighbor( System.Random random, out int nx, out int ny )
        {
            int index = random.Next(edgeCount);
            GetNeighbor(index, out nx, out ny);
            return index;
        }


        public int GetBeyondEdgeIndex(int edgeIndex)
        {
            return ( edgeIndex + ( edgeCount >> 1 ) ) % edgeCount;
        }
        
        public abstract int edgeCount { get; }
        public abstract void GetNeighbor( int index, out int x, out int y );
    }


    public class RectCell : Cell
    {
        public override int edgeCount { get { return 4; } }


        public RectCell(int x , int y)
            :base(x,y)
		{
			walls = new bool[edgeCount];
            for ( int i = 0; i < edgeCount; ++i )
            {
                walls[i] = true;
            }
        }


        /**
         *    1
         *  0 - 2
         *    3
         */
        public override void GetNeighbor(int index, out int nx, out int ny)
        {
            nx = x;
            ny = y;
            switch(index)
            {
            default:
            case 0: nx -= 1; break;
            case 1: ny -= 1; break;
            case 2: nx += 1; break;
            case 3: ny += 1; break;
            }
        }
    }


    public class MazeMap
    {
        public float length;
        public Cell[,] cells;


        public void Init( int columCount, int rowCount)
        {
            cells = new Cell[columCount, rowCount];
            for ( int y = 0; y < rowCount; ++y )
            {
                for ( int x = 0; x < columCount; ++x )
                {
                    cells[x, y] = new RectCell(x, y);
                }
            }


            MazeGenerator gen = new MazeGenerator(columCount, rowCount, cells);
            cells[0, 0].walls[0] = false;
            cells[columCount - 1, rowCount - 1].walls[2] = false;
        }
    }


    public class MazeGenerator : DisjointSets
    {
        private System.Random random = new System.Random((int)Time.realtimeSinceStartup);


        public MazeGenerator(int columCount, int rowCount, Cell[,] cells)
            :base (columCount * rowCount)
        {
            while(!_IsFinished())
            {
                int x = random.Next(columCount);
                int y = random.Next(rowCount);
                Cell cell = cells[x, y];
                int nx,ny;
                int nbIndex = cell.GetRandomNeighbor(random, out nx, out ny);
                if ( !( 0 <= nx && nx < columCount && 0 <= ny && ny < rowCount ) )
                {
                    nbIndex = cell.GetBeyondEdgeIndex(nbIndex);
                    cell.GetNeighbor(nbIndex, out nx, out ny);
                }


                Cell nbCell = cells[nx, ny];
				if(find(y * columCount + x) != find(ny * columCount + nx))
				{
					//Debug.Log(string.Format("union:({0},{1})", y * columCount + x, ny * columCount + nx));
                    union(find(y * columCount + x), find(ny * columCount + nx));
                    cell.walls[nbIndex] = false;
                    nbCell.walls[nbCell.GetBeyondEdgeIndex(nbIndex)] = false;
				}
            }
        }


        bool _IsFinished()
        {
            for ( int i = 0; i < _sets.Length; ++i )
            {
                if( find(0) != find(i))
                {
                    return false;
                }
            }
            return true;
        }
    }


    public class DisjointSets
    {
        protected int[] _sets;


        public DisjointSets( int count)
        {
            _sets = new int[count];
            for(int i =0 ; i < count; ++i)
            {
                _sets[i] = -1;
            }
        }


        public void union(int root1, int root2)
        {
            if ( _sets[root2] < _sets[root1] )
            {
                _sets[root1] = root2;
            }
            else
            {
                if(_sets[root1] == _sets[root2])
                {
                    _sets[root1]--;
                }
                _sets[root2] = root1;
            }
        }


        public int find(int index)
        {
            if ( _sets[index] < 0 )
            {
                return index;
            }
            else
            {
                int root = find(_sets[index]);
                _sets[index] = root;
                return root;
            }
        }
    }
}