using Nemerle.Collections;

namespace NSokoban
{
    public module TreeSearch
    {
  public BFS (map : SMap) : bool * option [SMap]
  {
      mutable found = false;
      mutable result = None ();
      
      def visited = Hashtable (4000000);
      mutable queue = Queue(4000000);

      mutable depth = 0;
      queue.Enqueue (map);

      def start = System.DateTime.Now;

      while(!found && !(queue.Count == 0))
      {        
    def m = queue.Dequeue();        

    when(depth < m.moves_so_far.Length)
    {
        ++depth;
        System.Console.WriteLine(depth);
        //System.Console.WriteLine(m);
    }

    when(!visited.ContainsKey(m.Id))
    if(m.GoalTest())
    {
        found = true;
        result = Some(m);
    }
    else
    {
        visited.Add(m.Id,"");
        List.Iter(m.NextStates(),fun(x){queue.Enqueue(x);})    
    }
      }
      when(found)
    System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());  
      
      (found,result)
  }

  public BlindIDFS (map : SMap) : bool * option [SMap]
  {
      mutable i = 1;
      mutable found = false;
      mutable mp = null;

      def start = System.DateTime.Now;
  
      while(!found)
      {
    def (f,m) = BlindDFS(map,i);
    mp = m;
    found = f;
    ++i;
      }
      when(found)
    System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());  
      (found,mp)
  }

  public BlindDFS (map : SMap, limit : int) : bool * option [SMap]
  {
      mutable found = false;      
      mutable result = None ();

      mutable stack = Stack(1000000);
      
      mutable i = 0;      
      stack.Push (map);

      while(!found && !(stack.Count == 0))
      {    
    ++i;
    def m = stack.Pop();
    if(m.GoalTest())
    {
        found = true;
        result = Some(m);
    }
    else    
        when(m.moves_so_far.Length <= limit)
      List.Iter(m.NextStates(),fun(x){stack.Push(x);})
    
      }      
      
      (found,result)
  }

  public IDFS (map : SMap) : bool * option [SMap]
  {
      mutable i = 1;
      mutable found = false;
      mutable mp = null;

      def start = System.DateTime.Now;
  
      while(!found)
      {
    def (f,m) = DFS(map,i);
    mp = m;
    found = f;
    ++i;
    System.Console.WriteLine(i);
      }
      when(found)
    System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());  
      (found,mp)
  }

  public DFS (map : SMap, limit : int) : bool * option [SMap]
  {
      mutable found = false;      
      mutable result = None ();
      
      def visited = Hashtable.[string,SMap] (20000);
      
      mutable stack = Stack(1000000);
      
      stack.Push (map);

      while(!found && !(stack.Count == 0))
      {        
    def m = stack.Pop();    
    
    if(visited.ContainsKey(m.Id))     
        when(visited[m.Id].moves_so_far.Length > m.moves_so_far.Length)
        {
      visited[m.Id] = m;
      List.Iter(m.NextStates(),fun(x){stack.Push(x);})
        }
    else
    if(m.GoalTest())
    {
        found = true;
        result = Some(m);
    }
    else    
        when(m.moves_so_far.Length <= limit)
        {
            visited.Add(m.Id,m);
            List.Iter(m.NextStates(),fun(x){stack.Push(x);})
        }    
      }      
      
      (found,result)
  }    

  public A_Star (map : SMap) : bool * option[SMap]
  {
      mutable found = false;      
      mutable result = None ();

      def visited = Hashtable.[string,SMap] (20000);
      mutable contour = SplayHeap.Empty ();
      
      def start = System.DateTime.Now;
      
      mutable len = 0;
      
      contour = contour.Insert(map);
            
      while(!found && !contour.IsEmpty())
      {
    def (m,c) = contour.DeleteMin ();    

    contour = c;

    when (m.H < 50000)
    {

        when(len < m.moves_so_far.Length)
        {
      len=m.moves_so_far.Length;
      System.Console.WriteLine(len);
      //System.Console.WriteLine(m);
      //System.Console.WriteLine(m.F);
        }
    
        if(visited.ContainsKey(m.Id)) 
      when(visited[m.Id].moves_so_far.Length > m.moves_so_far.Length)
      {
          visited[m.Id] = m;
          List.Iter(m.NextStates(),fun(x){contour = contour.Insert(x);})
      }
        else
        if (m.GoalTest ())
        {   
      found = true;
      result = Some(m);        
        }
        else
        {
      //System.Console.WriteLine(m);
      //System.Console.WriteLine(m.H);
      visited.Add(m.Id,m);        
      List.Iter(m.NextStates(),fun(x){contour = contour.Insert(x);})   
        }
    }
      }      
      when(found)
    System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());
  
      (found,result)
  }

  public IDA (map : SMap) : bool * option [SMap]
  {
      mutable limit = map.F;
      mutable r = None ();
      
      def start = System.DateTime.Now;
      
      while(!Option.IsSome (r))
      {
    def visited = Hashtable (200000);
    def (res , l ,_) = dfs_FL (map,limit,visited);
    r = res;
    limit = l;
    System.Console.WriteLine(limit);
      }

      System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());

      (true,r)
  }

  private dfs_FL (map : SMap,limit : int,visited : Hashtable [string, SMap]) : option [SMap] * int * Hashtable [string, SMap]
  {
      mutable vis = visited;
      
      if(map.F > limit)
    (None () , map.F,vis)
      else
      {
    if(map.GoalTest ())    
        (Some (map),-1,vis)    
    else
    {
        mutable min = 100000;
        def succ = map.NextStates ();

        def loop (lst : list [SMap])
        {
      | [] => (None (),min,vis)
      | head :: tail =>
          if(vis.ContainsKey(head.Id))          
        if(visited[head.Id].moves_so_far.Length > head.moves_so_far.Length)
        {   
            visited[head.Id] = head;
            loop(head.NextStates () + tail);
        }
        else
            loop(tail)          
          else
          {
        vis.Add(head.Id,head);
        def (new_m, new_l ,v) = dfs_FL (head,limit,vis);
        
        vis = v;

        if(Option.IsSome (new_m))
            (new_m,-1,vis)
        else
        {
            min = System.Math.Min (min,new_l);
            loop(tail);
        }
          }
        }
        
        loop(succ);
    }
      }
  }

  public RBFS (map : SMap) : bool * option [SMap]
  {
      def start = System.DateTime.Now;      
      def (m,_) = rbfs (map,100000,0);      
      match(m)
      {
    | None => 
        System.Console.WriteLine("Not found after "+(start - System.DateTime.Now).ToString ());
        (false,None ())
    | Some (x) => 
        System.Console.WriteLine("Found after "+(start - System.DateTime.Now).ToString ());
        (true, Some (x))
      }
  }

  private rbfs (map : SMap, limit : int,depth : int) : option [SMap] * int
  {
      mutable set = SplayHeap.Empty ();
      
      if (map.GoalTest ())
    (Some(map),map.moves_so_far.Length)
      else
      {
    mutable ret = false;
    mutable result = 0;
    mutable r_map = None ();

    def succ = map.NextStates ();
    
    match(succ)
    {
        | [] => (None (),100000)
        | _ =>    
      foreach(map : SMap in succ)
      {
          def m = map;
          m.F = System.Math.Max (map.G + map.H,map.F);          
          set = set.Insert(m);
      }
    
      while(!ret)
      {          
          def (best,s) = set.DeleteMin ();
          
          if (best.F > limit)
          {        
        ret = true;
        result = best.F;        
          }
          else
          {
        if(!s.IsEmpty ())
        {
            def alternative = s.FindMin ();
        
            def (r , f_best) = rbfs(best,System.Math.Min(limit, alternative.F),depth+1);
            best.F = f_best;

            set = s.Insert (best);

            when(Option.IsSome(r))
            {
          ret = true;          
          r_map = r;
            }
        }
        else
        {
            def (r , f_best) = rbfs(best,limit,depth+1);
            ret = true;
            r_map = r;
            result = f_best;
        }
          }
          
      }

      (r_map,result)
    }    
      }
  }
    }
}