with Ada.Text_Io, Plateau, Configs, TableHach, File,
     Ada.Unchecked_Deallocation ;
use Ada, Ada.Text_Io, Plateau, Configs, TableHach ;

function CheminGagnant return ConfigConnue is

   procedure Deallocate is new Unchecked_Deallocation(ConfigCell,
         ConfigConnue) ;

   -- current Etat/Config
   InitConfig: constant Config := Exporte_Etat ;
   ---- an irrelevant Coup used to instantiate the initial ConfigConnue
   --C: Coup;
   -- pointing to the currently checked Config (head of queue)
   CurrentConf: ConfigConnue ;

   -- Adds all the neigbours of the given Config into the queue.
   procedure AddNeighbours(CurrentConf: in ConfigConnue) is
      -- represent all the moves which can be played one after the other
      -- (and thus the reachable neighbour Configs)
      TempECoup: Enum_Coup ;
      -- the current neighbour's Config
      NeighbourConfig: Config ;
   begin
      -- get the first usable move
      Demarrer(TempECoup) ;

      -- while there is a next possible move, add the related Config
      -- into the queue
      while (not Fin(TempECoup)) loop
         -- get the Config of the current move
         Effectue(Courant(TempECoup)) ;
         NeighbourConfig := Exporte_Etat ;
         -- if this Config is not already in the hash table, add it
         -- (this avoids adding to many elements in the File, but is not
         -- a sufficient condition to filter all the irrelevant ones)
         if (Cherche(NeighbourConfig) = null) then
            File.Inserer(new ConfigCell'
                 (NeighbourConfig, CurrentConf,
                  Courant(TempECoup), null)) ;
         end if ;

         -- set the board to the previous position
         Met_Plateau(CurrentConf.all.Clef) ;
         -- get the next possible move
         Avancer(TempECoup) ;
      end loop ;
   end AddNeighbours ;

begin
   File.Vider ;
   -- insert the initial Etat into the queue as its first element
   CurrentConf := new ConfigCell ;
   CurrentConf.Clef := InitConfig ;
   File.Inserer(CurrentConf) ;

   -- Each iteration is associated with a unique Config (Etat).
   -- The first element of the queue is added into the hash table, and
   -- each one of its neighbours is then added into the Queue unless
   -- they are already existing in the hash table, or unless the current
   -- queue head is a winning Config.
   while (not File.Estvide) loop
      -- get the head of the queue (the currently checked Config)
      File.Extraire(CurrentConf) ;
      if (TableHach.Cherche(CurrentConf.all.Clef) = null) then
         -- set the board to the current Config
         Met_Plateau(CurrentConf.all.Clef) ;
         -- insert the head of the queue into the hash table
         TableHach.Inserer(CurrentConf) ;
         -- check if the added Config is a winning one
         if (Plateau.A_Gagne) then
            -- if it is, set the board back to the initial Config
            Plateau.Met_Plateau(InitConfig) ;
            File.Vider ;
            -- complete the hash table and return the initial Config
            return TableHach.SetWinningConfig(CurrentConf) ;
         end if ;
         -- add the relevant neighbours of the current Config
         AddNeighbours(CurrentConf) ;
      else
         Deallocate(CurrentConf) ;
      end if;
   end loop ;
   -- reaching this code part means no winning Config has been found
   Met_Plateau(InitConfig) ;
   File.Vider ;
   return null ;
end ;