using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using STVrogue.Utils;
using static STVrogue.Utils.HelperPredicates;

namespace STVrogue.GameLogic
{
    
    /// <summary>
    /// Representing a dungeon. A dungeon consists of rooms, connected to from a graph.
    /// It has one unique starting room and one unique exit room. All rooms should be
    /// reachable from the starting room.
    /// </summary>
    public class Dungeon
    {

        #region Fields and Properties
        
        /// <summary>
        /// All rooms in the dungeon, including the start and exit rooms.
        /// </summary>
        public List<Room> Rooms { get; } = new List<Room>();
        public Room StartRoom { get; set; }
        public Room ExitRoom { get; set; }
        
        // Use this to force deterministic random numbers generation for testing purposes.
        // IRandomGenerator randomGenerator = new STVControlledRandom();
        IRandomGenerator randomGenerator = new RandomGenerator();

        #endregion

        protected Dungeon() { }
        
        /// <summary>
        /// Create a dungeon with the indicated number of rooms and the indicated shape.
        /// A dungeon shape can be "linear" (list-shaped), "tree", or "random".
        /// <list type="bullet">
        /// <item>
        /// A dungeon should have a unique start-room and a unique exit-room. </item>
        /// <item>
        /// All rooms in the dungeon must be reachable from the start-room. </item>
        /// <item>
        /// Each room is set to have a random capacity between 1 and the given maximum-capacity.
        /// Start and exit-rooms should have capacity 0. </item>
        /// </list>
        /// </summary>
        public Dungeon(DungeonShapeType shape, int numberOfRooms, int maximumRoomCapacity) : base()
        {
            switch (shape)
            {
                case DungeonShapeType.LINEARshape:
                    MkLinearDungeon(numberOfRooms, maximumRoomCapacity);
                    break;
                case DungeonShapeType.TREEshape:
                    MkTreeDungeon(numberOfRooms, maximumRoomCapacity);
                    break;
                case DungeonShapeType.RANDOMshape:
                    MkRandomDungeon(numberOfRooms, maximumRoomCapacity);
                    break;
            }
        }
        
        private void MkLinearDungeon(int numberOfRooms, int maximumRoomCapacity)
        {
            Room prev = null;
            Room r = null;
            for (int k = 0 ; k<numberOfRooms; k++)
            {
                int capacity = randomGenerator.NextInt(maximumRoomCapacity) + 1 ; // kutu note
                r = new Room("R" + k, RoomType.ORDINARYroom, capacity); // kutu note
                Rooms.Add(r);
                if (k == 0)
                {
                    StartRoom = r;
                    prev = r;
                }
                else
                {
                    prev.Connect(r);
                    prev = r;
                }
            }
        }

        private void MkTreeDungeon(int numberOfRooms, int maximumRoomCapacity)
        {
            StartRoom = new Room("R" + 0, RoomType.STARTroom, 0);
            MkTreeDungeonWorker(StartRoom, numberOfRooms, maximumRoomCapacity);
        }
        
        private int MkTreeDungeonWorker(Room parent, int numberOfRooms, int maximumRoomCapacity)
        {
            int parentId = int.Parse(parent.Id.Substring(1));
            int freshId = parentId + 1;
            while (numberOfRooms > 0)
            {
                int capacity = randomGenerator.NextInt(maximumRoomCapacity) + 1 ; // kutu note
                Room r = new Room("R" + freshId, RoomType.ORDINARYroom, capacity);
                parent.Connect(r);
                int N = Math.Max(1, numberOfRooms / 3);
                int lastUsedId = MkTreeDungeonWorker(r, N, maximumRoomCapacity);
                freshId = lastUsedId + 1;
                numberOfRooms -= N;
            }
            return freshId; // kutu minor note
        }
        
        void MkRandomDungeon(int numberOfRooms, int maximumRoomCapacity)
        {
            bool isTree = true;
            
            bool[] visited = new bool[numberOfRooms];
            for (int k = 0 ; k<numberOfRooms; k++)
            {
                int capacity; 
                RoomType roomType;
                if (k == 0)
                {
                    capacity = 0;
                    roomType = RoomType.STARTroom;
                }
                else if (k == 1)
                {
                    capacity = 0;
                    roomType = RoomType.EXITroom;
                }
                else
                {
                    capacity = randomGenerator.NextInt(maximumRoomCapacity) + 1 ;
                    roomType = RoomType.ORDINARYroom;
                }
                Room r = new Room("R" + k, roomType, capacity);
                Rooms.Add(r);
                visited[k] = false;
            }

            int i = 0;

            while (!Forall(visited, b => b))
            {
                int j=i;
                while(j==i)
                {
                    j = randomGenerator.NextInt(numberOfRooms - 1);
                }

                if(!Rooms[i].Neighbors.Contains(Rooms[j]))
                    if (visited[j])
                        //this means j has multiple parents
                        isTree = false;
                    Rooms[i].Connect(Rooms[j]);
                visited[j] = true;
                i = j;


            }

            if (isTree)
            {
                //Our graph is not allowed to be a tree. By adding
                //a new edge that did not exist before we can accomplish this
                int j;
                do
                {
                    i = randomGenerator.NextInt(numberOfRooms - 1);
                    j = randomGenerator.NextInt(numberOfRooms - 1);

                } while (Rooms[i].Neighbors.Contains(Rooms[j]));
                Rooms[i].Connect(Rooms[j]);
            }

            //Create dungeons
            //i=0
            //while(not all dungeons have been visited){
            //  do{
            //      j=random()
            //   }while(i==j)
            //   add j as neighbour of i
            //   visited[j] = true
            //}
            
            //throw new NotImplementedException();
        }

        #region additional getters

        /// <summary>
        /// Return all creatures in the Dungeon. The player is excluded.
        /// </summary>
        public List<Creature> Creatures
        {
            get => throw new NotImplementedException();
        }

        /// <summary>
        /// Return all items in this Dungeon. The items in the player's bag
        /// are excluded.
        /// </summary>
        public List<Item> Items
        {
            get => throw new NotImplementedException();
        }
        #endregion

        /// <summary>
        /// Populate the dungeon with the specified number of monsters and items.
        /// They are dropped in random locations. Keep in mind that the number of
        /// monsters in a room should not exceed the room's capacity. There are also
        /// other constraints; see the Project Document.
        /// <para></para>
        /// Note that it is not always possible to populate the dungeon according to
        /// the specified parameters. E.g. in a dungeon with N rooms whose capacity
        /// are between 0 and k, it is definitely not possible to populate it with
        /// (N-2)*k monsters or more.
        /// The method returns true if it manages to populate the dungeon as specified,
        /// else it returns false.
        /// <para></para>
        /// If it fails to populate the dungeon, it returns false.
        /// </summary>
        public bool SeedMonstersAndItems(int numberOfMonster, int numberOfHealingPotion, int numberOfRagePotion)
        {
            throw new NotImplementedException();
        }
    }

    [Serializable()]
    public enum DungeonShapeType
    {
        LINEARshape, 
        TREEshape,
        RANDOMshape
    }
    
    /// <summary>
    /// Representing different types of rooms.
    /// </summary>
    public enum RoomType
    {
        STARTroom,  // the starting room of the player. 
        EXITroom,   // representing the player's final destination.
        ORDINARYroom  // the type of the rest of the rooms. 
    }

    /// <summary>
    /// Representing a room in a dungeon.
    /// </summary>
    public class Room : GameEntity
    {

        #region fields and properties

        /// <summary>
        /// The type of this node: either start-node, exit-node, or common-node.
        /// </summary>
        public RoomType RoomType { get; }

        /// <summary>
        /// The number of monsters in this room cannot exceed this capacity.
        /// </summary>
        public int Capacity { get;  }
        
        /// <summary>
        /// Neighbors are nodes that are considered connected to this node.
        /// The connection is bidirectional. If u is in this.neighbors of this room,
        /// you have to make sure that this room is also in u.neighbors.
        /// </summary>
        public List<Room> Neighbors { get; } = new List<Room>();

        /// <summary>
        /// All creatures, excluding the players, which are currently in this room.
        /// </summary>
        public List<Creature> Creatures { get;  } = new List<Creature>();

        /// <summary>
        /// All items, excluding those in the player's bag, which are currently in this room.
        /// </summary>
        public List<Item> Items { get; } = new List<Item>();
        
        #endregion
        
        
        public Room(string uniqueId, RoomType roomTy, int capacity) : base(uniqueId)
        {
            RoomType = roomTy;
            Capacity = capacity;
        }

        #region additional getters
       
        /// <summary>
        /// The number of monsters in this room. The player does not count as a monster.
        /// </summary>
        public int NumberOfMonsters => Creatures.Count(c => c is Monster);

        #endregion

        /// <summary>
        /// To add the given room as a neighbor of this room.
        /// </summary>
        public void Connect(Room r)
        {
            Neighbors.Add(r); r.Neighbors.Add(this);
        }

        /// <summary>
        /// To disconnect the given room. That is, the room r will no longer be a
        /// neighbor of this room.
        /// </summary>
        public void Disconnect(Room r)
        {
            Neighbors.Remove(r); r.Neighbors.Remove(this);
        }

        /// <summary>
        /// return the set of all rooms which are reachable from this room.
        /// </summary>
        public List<Room> ReachableRooms()
        {
            Room x = this;
            var seen = new List<Room>();
            var todo = new List<Room>();
            todo.Add(x);
            while (todo.Count > 0)
            {
                x = todo[0] ; todo.RemoveAt(0) ;
                seen.Add(x);
                foreach (Room y in x.Neighbors)
                {
                    if (seen.Contains(y) 
                        || todo.Contains(y))
                        continue;
                    todo.Add(y);
                }
            }
            return seen;
        }

        /// <summary>
        /// Check if the given room is reachable from this room.
        /// </summary>
        public bool CanReach(Room r)
        {
            return ReachableRooms().Contains(r); // not the most efficient way of checking it btw
        }
    }



}