using System.Xml;
using Nemerle.Collections;
using Nemerle.Utility;
using NSokoban.Macros;

namespace NSokoban
{
    public struct MapCollection
    {
  private mutable maps : list[SMap]; 
  private doc : XmlDocument;
  
  public this (file_name : string)
  {
      maps = [];
      doc = XmlDocument ();
      def reader = XmlTextReader (file_name);
      doc.Load (reader);
      translate_xml ();
  }  

  private translate_xml () : void
  {
      def nodes = doc.SelectNodes("SokobanLevels/LevelCollection/Level");
      System.Console.WriteLine(nodes.Count);
      for(mutable i=0 ; i<nodes.Count ; i+=1)
      {
    def lines = nodes[i].SelectNodes("L");

    def width = System.Int32.Parse(nodes[i].Attributes["Width"].Value);
    def height = System.Int32.Parse(nodes[i].Attributes["Height"].Value);

    mutable er = 0;

    mutable xpos = None ();
    mutable ypos = None ();

    mutable packs = [];
    mutable free_places = [];
    mutable places = [];

    def sarray = array(height);
    
    def s (i)
    {
        mutable str = "";
        for(mutable j = 0 ; j < i ; j+=1)
      str+=" ";
        str
    }
    
    for (mutable j=0; j<lines.Count ; j+=1 )
    {
        sarray[j] = lines[j].InnerText + s(width - lines[j].InnerText.Length);
        for(mutable k=0; k < width ; k+=1 )
      match(lines[j].InnerText[k])
      {
          | '@' => 
        xpos = Some(k);
        ypos = Some(j);
        def chars = sarray[j].ToCharArray();
        chars[k] = ' ';
        sarray[j] = System.String(chars);
          | '%' => 
        xpos = Some(k);
        ypos = Some(j);
        def chars = sarray[j].ToCharArray();
        chars[k] = '.';
        sarray[j] = System.String(chars);
          | '$' => 
        ++er;
        packs = (k,j) :: packs
          | '.' => 
        free_places = (k,j) :: free_places;
        places = (k,j) :: places
          | '*' => 
        places = (k,j) :: places
          | _ => ()        
      }
    }    
    def map = SMap(width,height,Option.UnSome(xpos),Option.UnSome(ypos),sarray,"",er,null,free_places,packs,null,null);
      
    map.compute_heuristic (places,width,height);
    map.compute_macros ();
    
    maps = map :: maps;
      }
      maps = List.Rev(maps);
  }

  public override ToString () : string
  {
      def buffer = System.Text.StringBuilder ("");
      List.Iter(List.Rev(maps),fun(map : SMap){ ignore (buffer.Append(map.ToString() + "\n\n"))  });

      buffer.ToString ();
  }

  public Nth (n : int) : SMap
  {
      List.Nth(maps,n)    
  }

    }

    public class SMap
    {
  public mutable static Visited : Hashtable [string, SMap];
  
  private xsize : int;      // width of the map
  private ysize : int;      // height of the map

  public mutable xpos : int;  // x position of worker
  public mutable ypos : int;  // y position of worker
  
  private mutable packs : list[int * int] = [];
  private mutable free_places : list[int * int] = [];
  
  private mutable h : option [int] = None ();
  private mutable f : option [int] = None ();
  
  private mutable heuristic : array [2,list [int * int * int]];
  
  private mutable allowed : array [2,bool];
  
  private mutable macros : array [2,char * char];
  
  private mutable error : int;
  
  private mutable map : array [string];  
  
  public mutable moves_so_far : string;  // moves made so far

  public this(xsize : int , ysize : int,xpos : int,ypos : int, map : array[string],moves : string,
        error : int,heuristic : array [2, list[ int * int * int]],
        free_places : list [int * int],packs : list [int * int],allowed : array[2,bool],macros : array[2,char * char])
  {
      this.xsize = xsize;
      this.ysize = ysize;
      this.map = (map.Clone() :> array[string]);                  
      this.xpos = xpos;
      this.ypos  = ypos;
      this.moves_so_far = moves;
      this.error = error;
      this.heuristic = heuristic;  
      this.free_places = free_places;
      this.packs = packs;
      this.allowed = allowed;
      this.macros = macros;
  }

  internal compute_macros () : void
  {
      def is_not_wall (i,j)
      {
    map[i][j] != '#' 
      }
      
      def is_wall (i,j)
      {
    map[i][j] == '#' 
      }
      
      def is_start_of_tunnel (i,j,dir)
      {
    if(i>0 && j>0 && j<(xsize - 1) && i<(ysize-1))
    {
    if(dir == 'D')
        if(map[i+1][j+1] == '#' && is_not_wall(i+1,j) && map[i+1][j-1] == '#')
      true
        else
      false
    else 
    if(dir == 'U')
        if(map[i-1][j+1] == '#' && is_not_wall(i-1,j) && map[i-1][j-1] == '#')
      true
        else
      false
    else
    if(dir == 'R')
        if(map[i+1][j+1] == '#' && is_not_wall(i,j+1) && map[i-1][j+1] == '#')
      true
        else
      false
    else
        if(map[i+1][j-1] == '#' && is_not_wall(i,j-1) && map[i-1][j-1] == '#')
      true
        else
      false
    }
    else
        false
      }
      
      def is_in_a_tunnel (i,j,dir)
      {
    if(i>0 && j>0 && j<(xsize - 1) && i<(ysize-1))
    if(dir == 'U')    
        if(map[i][j+1] == '#' && is_not_wall(i,j) && map[i][j-1] == '#')
      (is_in_a_tunnel(i+1,j,'U') || is_start_of_tunnel(i+1,j,'U'))
        else
      false
    else 
    if(dir == 'D')
        if(map[i][j+1] == '#' && is_not_wall(i,j) && map[i][j-1] == '#')
      (is_in_a_tunnel(i-1,j,'D') || is_start_of_tunnel(i-1,j,'D') )
        else 
      false
    else
    if(dir == 'R')
        if(map[i+1][j] == '#' && is_not_wall(i,j) && map[i-1][j] == '#')
      (is_in_a_tunnel(i,j+1,'R') || is_start_of_tunnel(i,j+1,'L'))
        else
      false
    else
        if(map[i+1][j] == '#' && is_not_wall(i,j) && map[i-1][j] == '#')
      (is_in_a_tunnel(i,j-1,'L') || is_start_of_tunnel(i,j-1,'R') )
        else false
    else
        false
      }
      
      def is_corner_tunnel (i,j,dir)
      {
    if(i>0 && j>0 && j<(xsize - 1) && i<(ysize-1))
    if(dir == "RD")
        is_not_wall(i,j) && is_not_wall(i+1,j) && is_not_wall(i,j+1)
        && is_wall (i+1,j+1) && is_wall (i-1,j) && is_wall (i,j-1)
    else
    if(dir == "LD")
        is_not_wall(i,j) && is_not_wall(i+1,j) && is_not_wall(i,j-1)
        && is_wall (i+1,j-1) && is_wall (i-1,j) && is_wall (i,j+1)
    else
    if(dir == "LU")
        is_not_wall(i,j) && is_not_wall(i-1,j) && is_not_wall(i,j-1)
        && is_wall (i-1,j-1) && is_wall (i+1,j) && is_wall (i,j+1)
    else
        is_not_wall(i,j) && is_not_wall(i-1,j) && is_not_wall(i,j+1)
        && is_wall (i-1,j+1) && is_wall (i+1,j) && is_wall (i,j-1)
    else
        false
      }
      
      macros = array(ysize,xsize);

      for(mutable i = 1; i < ysize - 1 ; i+= 1)
      {
    for(mutable j = 1; j < xsize - 1 ; j+= 1)
    {
        mutable v = ' ';
        mutable h = ' ';

        when(is_in_a_tunnel(i,j,'U') && is_in_a_tunnel(i,j,'D'))        
      h = 'B';
        
        when(is_in_a_tunnel(i,j,'L') && is_in_a_tunnel(i,j,'R'))
      v = 'B';

        when(v == ' ' && h == ' ')
        {
      if(is_corner_tunnel(i,j,"RD"))
      {
          v = 'R';
          h = 'D';
      }
      else
      if(is_corner_tunnel(i,j,"LD"))
      {
          v = 'L';
          h = 'D';
      }
      else
      if(is_corner_tunnel(i,j,"RU"))
      {
          v = 'R';
          h = 'U';
      }
      else
      when(is_corner_tunnel(i,j,"LU"))
      {
          v = 'L';
          h = 'U';
      }
        }
        macros [i,j] = (h,v);
    }
      }
  }

  /**
   *  computes heuristic function for all fields on the map
   *  constructs array containing information about allowed and disallowed fields
   */
  internal compute_heuristic (places : list [int * int],xsize : int,ysize : int) : void
  {            
      def is_corner (i,j) 
      {
    if(map[i][j] == ' ' && i>0 && j>0 && i<(ysize-1) && j<(xsize-1))
        if(map[i+1][j] == '#'  && map[i][j+1] == '#')
      true
        else if(map[i+1][j] == '#' && map[i][j-1] == '#')
      true
        else if(map[i-1][j] == '#' && map[i][j+1] == '#')
      true
        else if(map[i-1][j] == '#' && map[i][j-1] == '#')
      true
      else
          false
    else
        false
      }

      def is_unavailable (i,j,c)
      {    
    if(map[i][j] == ' ' && i>0 && j>0 && i<(ysize-1) && j<(xsize-1))
        if(is_corner(i,j))
      true
        else
      if(map[i+1][j+1] == '#' && map[i][j+1] == '#' && map[i-1][j+1] == '#')
          if(c == 'R')
        is_unavailable(i+1,j,'R')        
          else if(c == 'L' && is_unavailable(i-1,j,c))
        true
          else
        false
        
      else if(map[i+1][j-1] == '#' && map[i][j-1] == '#' && map[i-1][j-1] == '#')
        if(c == 'R' && is_unavailable(i+1,j,c))
            true
        else if(c == 'L' && is_unavailable(i-1,j,c))
            true
        else
            false
      else if(map[i+1][j+1] == '#' && map[i+1][j] == '#' && map[i+1][j-1] == '#')
        if(c == 'R' && is_unavailable(i,j+1,c))
            true
        else if(c == 'L' && is_unavailable(i,j-1,c))
            true
        else
            false

      else if(map[i-1][j+1] == '#' && map[i-1][j] == '#' && map[i-1][j-1] == '#')
        if(c == 'R' && is_unavailable(i,j+1,c))
            true
        else if(c == 'L' && is_unavailable(i,j-1,c))
            true
        else
            false
          else
        false
    else
        false
      }
      
      heuristic = array(ysize,xsize);
      allowed = array(ysize,xsize);
      
      for(mutable i = 1; i < ysize - 1 ; i+= 1)
      {
    for(mutable j = 1; j < xsize - 1 ; j+= 1)
    {
        def f (x,y)
        {
      (y,x,length ((x,y),(j,i)))
        }
        
        def g (x,y)
        {
      (y,x,100000)  
        }
        
        def cmp (t1 : int * int * int,t2)
        {
      def (_,_,l1) = t1;
      def (_,_,l2) = t2;
      if(l1 == l2)
          0
      else
          if(l1 < l2)
        -1
          else
        1
        }                
        
        if(is_unavailable(i,j,'R') && is_unavailable(i,j,'L'))
        {      
      heuristic [i,j] = List.Map (places,g);
      allowed [i,j] = false;
        }
        else
        {      
      def l = List.Sort(List.Map (places , f),cmp);
      heuristic [i,j] = l;
      allowed [i,j] = true;
        }
    }
      }
    
  }

  private length (p1 : int * int,p2 : int * int) : int
  {
      def (x1,y1) = p1;
      def (x2,y2) = p2;
      System.Math.Abs (x1 - x2) + System.Math.Abs (y1 - y2)
  }  

  public static Leq(x : SMap, y : SMap) : bool
  {
      x.F <= y.F      
  }

  /**
   *  h(n) in A*, IDA*, RBFS algorithms
   *  sum of distances between every pack on the map and the nearest free place(goal)
   *  plus distance from worker to the nearest pack
   */
  public H : int
  {
      get
      {
    match(h)
    {
        | None =>
      mutable sum = 0;

      foreach ((x,y) : int * int in packs)
      {
          mutable i = 0;
          mutable found = false;
          def n = List.Length (heuristic[y,x]);
          while(!found && i < n)
          {
        def (j,k,l) = List.Nth (heuristic[y,x],i);
        when(List.Member (free_places ,(j,k)))
        {
            found = true;
            sum += l;
        }
            
        ++i;
          }
      }

      def distance =
      if(List.Length(packs)== 0)
          0
      else
      {
          mutable  min = 100000;        
          
          foreach(pack : int * int in packs)
          {
        def (x,y) = pack;        
        def len = length ((x,y),(xpos,ypos));
        when (len < min)
        min = len;    
          }
          min 
      }
      sum += distance;
      h = Some(sum);
      sum;

        | Some (h_) => h_
    }
      }
  }

  /**
   *  f(n) in A*, IDA*, RBFS algorithms
   */
  public F : int
  {
      get
      {
    match(f)
    {
        | None =>
      def f_temp = H + G;
      f = Some(f_temp);
      f_temp
        | Some (f_) => f_
    }
      
      }
      set
      {
    f = Some(value);
      }
  }

  /**
   *  h(n) in A*, IDA*, RBFS algorithms
   */
  public G : int
  {
      get
      {
    moves_so_far.Length  
      }
  }

  public AddMove (move : string) : void
  {
      moves_so_far = moves_so_far + move;    
  }

  public override ToString () : string
  {
      def buffer = System.Text.StringBuilder ("");
      for (mutable i = 0 ; i < ysize ; i+=1)
      {
    for(mutable k=0;k < map[i].Length;k+=1)  
        if(k == xpos && i == ypos)
      ignore(buffer.Append("@"));  
        else
      ignore(buffer.Append(map[i][k]));
    ignore(buffer.Append("|\n"));
      }      

      buffer.ToString () + " " + moves_so_far.Length.ToString () + " " + moves_so_far 
  }

  /**
   *   property used as a key in visited hashtable 
   */
  public Id : string
  {
      get
      {
    def buffer = System.Text.StringBuilder ("");
    for (mutable i = 0 ; i < ysize ; i+=1)      
        for(mutable k=0;k < map[i].Length;k+=1)  
      if(k == xpos && i == ypos)
          ignore(buffer.Append("@"));  
      else
          ignore(buffer.Append(map[i][k]));            

    buffer.ToString ();    
      }
  }

  public GoalTest () : bool
  {
      error == 0
  }

  /**
   *  method tries to move to all directions
   */
  public NextStates (long_moves : bool) : list[SMap] 
  {
      def moves = array["U","D","L","R"];
      mutable result = [];
      
      foreach(move : string in moves)
      {
    result = next_move(move,long_moves) + result  
      }

      result
  }
  
  public NextStates () : list [SMap]
  {
      NextStates (false);
  }
  
  private next_move (move : string) : list[SMap]
  {
      next_move(move,false);
  }
  
  /**
   *  method tries to move to one specified direction
   */  
  private next_move (move : string,long_moves : bool) : list[SMap]
  {
      def (nx,ny) = NextMove(xpos,ypos,move);
    
      match(map[ny][nx])
      {
    | '.' =>       
        def new_map = SMap(xsize,ysize,nx,ny,this.map,moves_so_far + move,error,heuristic,free_places,packs,allowed,macros);
        
        if(long_moves)
      if(Visited.ContainsKey(new_map.Id))
      {
          []
      }
      else
      {
          Visited.Add(new_map.Id,new_map);
          new_map.NextStates ();
      }
        else
      UseTunnelMacro (ny,nx,macros,new_map,move)
        
        
    | ' '  => 
        def new_map = SMap(xsize,ysize,nx,ny,this.map,moves_so_far + move,error,heuristic,free_places,packs,allowed,macros);

        if(long_moves)
      if(Visited.ContainsKey(new_map.Id))
      {
          []
      }
      else
      {
          Visited.Add(new_map.Id,new_map);
          new_map.NextStates ();
      }
        else
      UseTunnelMacro (ny,nx,macros,new_map,move)

    | '$' =>
        def (nnx,nny) = NextMove(nx,ny,move);            
      
        if(allowed[nny,nnx])
        {            
      def new_map = SMap(xsize,ysize,nx,ny,this.map,moves_so_far + move,error,heuristic,free_places,packs,allowed,macros);

      def chars = new_map.map[ny].ToCharArray();
      chars[nx] = ' ';
      new_map.map[ny] = System.String(chars);
      
      match(map[nny][nnx])
      {
          | '.' =>           
        def chars = new_map.map[nny].ToCharArray();
        chars[nnx] = '*';
        new_map.map[nny] = System.String(chars);
        
        new_map.free_places = List.Remove (new_map.free_places , (nnx,nny));
        new_map.packs = List.Remove (new_map.packs , (nx,ny));
        
        new_map.error -= 1;

        UseTunnelMacro2 (ny,nx,nny,nnx,macros,new_map,move)
    
          | ' ' =>
        def chars = new_map.map[nny].ToCharArray();
        chars[nnx] = '$';
        new_map.map[nny] = System.String(chars);

        new_map.packs = List.Remove (new_map.packs , (nx,ny));
        new_map.packs = (nnx,nny) :: new_map.packs; 

        UseTunnelMacro2 (ny,nx,nny,nnx,macros,new_map,move)
    
          | _ => []
      }
        
        }
        else []
    | '*' =>
        def (nnx,nny) = NextMove(nx,ny,move);
      
        if(allowed[nny,nnx])
        {            
      def new_map = SMap(xsize,ysize,nx,ny,this.map,moves_so_far + move,error,heuristic,free_places,packs,allowed,macros);
      
      def chars = new_map.map[ny].ToCharArray();
      chars[nx] = '.';
      new_map.map[ny] = System.String(chars);

      match(map[nny][nnx])
      {
          | '.' =>           
        def chars = new_map.map[nny].ToCharArray();
        chars[nnx] = '*';
        new_map.map[nny] = System.String(chars);

        new_map.free_places = List.Remove (new_map.free_places,(nnx,nny));
        new_map.free_places = (nx,ny) :: new_map.free_places;
        
        UseTunnelMacro2 (ny,nx,nny,nnx,macros,new_map,move)
    
          | ' ' =>
        def chars = new_map.map[nny].ToCharArray();
        chars[nnx] = '$';
        new_map.map[nny] = System.String(chars);
        new_map.error += 1;

        new_map.free_places = (nx,ny) :: new_map.free_places;
        new_map.packs = (nnx,nny) :: new_map.packs; 
        
        UseTunnelMacro2 (ny,nx,nny,nnx,macros,new_map,move)
    
          | _ => []
      }

        }
        else []
    | _ => []
      }      
  } /* end of next_move method */   

    } /* end of SMap class */
    
} /* end of NSokoban namespace */