-- This program is the last attempt of artificial intelligency with Ada.
-- Elhoim is Copyright (C) 2023 Manuel ; 
--
--   This program is free software; you can redistribute it and/or modify
--   it under the terms of the GNU General Public License as published by
--   the Free Software Foundation; either version 2 of the License, or
--   (at your option) any later version.
--
--   This program is distributed in the hope that it will be useful,
--   but WITHOUT ANY WARRANTY; without even the implied warranty of
--   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
--   GNU General Public License for more details.
--
--   You should have received a copy of the GNU General Public License
--   along with this program; if not, write to the Free Software
--   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
--
-- Date := "2023-05-01 20:03:01"
-- Version := "1.0.0a"

--  // A* Search Algorithm
--  1.  Initialize the open list
--  2.  Initialize the closed list
--      put the starting node on the open 
--      list (you can leave its f at zero)

--  3.  while the open list is not empty
--      a) find the node with the least f on 
--         the open list, call it "q"

--      b) pop q off the open list
  
--      c) generate q's 8 successors and set their 
--         parents to q
   
--      d) for each successor
--          i) if successor is the goal, stop search
        
--          ii) else, compute both g and h for successor
--            successor.g = q.g + distance between 
--                                successor and q
--            successor.h = distance from goal to 
--            successor (This can be done using many 
--            ways, we will discuss three heuristics- 
--            Manhattan, Diagonal and Euclidean 
--            Heuristics)
          
--            successor.f = successor.g + successor.h

--          iii) if a node with the same position as 
--              successor is in the OPEN list which has a 
--             lower f than successor, skip this successor

--          iV) if a node with the same position as 
--              successor  is in the CLOSED list which has
--              a lower f than successor, skip this successor
--              otherwise, add  the node to the open list
--       end (for loop)
  
--      e) push q on the closed list
--      end (while loop)


with Ada.Containers.Doubly_Linked_Lists;
use Ada.Containers;
package Lib.Search is
   
   
      generic
      type Element is private;
      with function Heuristic (E : Element) return Float;
      with function Uniform (E : Element) return Float;
      with function equal (Left, Right : Element) return Boolean;
      with function "<" (Left, Right : Element) return Boolean;      
      type El_Array is array (Positive range <>) of Element;
      with function Successors (E : Element) return El_Array;
   package Path_Finding is
      
      type Node_Record is private;
      
      
      
      package Element_Lists is new Ada.Containers.Doubly_Linked_Lists(Element, "=");
      
      package Elements_Sorting is new Element_Lists.Generic_Sorting ("<");
      
      use Element_Lists;
      
      subtype Element_List is Element_Lists.List;
      
      procedure Astar (Open : in Element_List;
		       Close  : out Element_List);
      
      task Astar_Task is
      	 entry Init (Open : in Element_List);	 
      	 entry Close_Set (Closed_Out : out Element_List; End_Of_Task : out Boolean);
      	 entry Halt;
      end Astar_Task;
      
      
      
      
   private
      

      
      type Node_Access is access Node_Record;
      
      type Node_Record is tagged
	 record
	    E : Element;
	    Ucost : Float := 0.0;
	    Hcost  : Float := 0.0;
	 end record;      
      
      function Init return Node_Access;
      
      function Element_Of (Node : in Node_Record) return Element;
      
      
      procedure Adjust(N : in out Node_Record; E : in Element);
      
      
      
      
      
   end Path_Finding;
   

end Lib.Search ;