--  Copyright (2008-2013) Cédric Coussinet (cedric.coussinet@nomoseed.net)
--
--  This program is free software: you can redistribute it and/or modify
--  it under the terms of the GNU Affero General Public License as published
--  by the Free Software Foundation, either version 3 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 Affero General Public License for more details.

--  You should have received a copy of the GNU Affero General Public License
--  along with this program. If not, see <http://www.gnu.org/licenses/>
--
--  Le principe de l'algorithme mis en exemple avec le cas où
--  trois prémises P peuvent se combinées avec quatre E événements :
--
--        * Calculer des distances possibles :
--                   [P1, P2, P3]t * [ E1, E2, E3, E4 ] =
--
--                             E1  E2  E3  E4
--                         P1  28  14  02  O5
--                         P2  01  02  07  06
--                         P3  11  17  09  15
--
--        * Mise en forme de listes triées des résultats comme suit :
--                    P1 => (02,E3), (05,E4), (14,E2), (28,E1)
--                    P2 => (01,E1), (02,E2), (O6,E4), (07,E3)
--                    P3 => (09,E3), (11,E1), (15,E4), (17,E2)
--
--        * Calculer les différences entre les premiers et les seconds minima
--                    Delta_P1 => (02,E3) - (05,E4) = 3
--                    Delta_P2 => (01,E1) - (02,E2) = 1
--                    Delta_P3 => (09,E3) - (11,E1) = 2
--
--        * Le couple prémise/événement conservé correspond au différentielle
--          minimu : (P2, E1). L'événement E1 est ensuite supprimé des autres
--          listes.
--                    P1 => (02,E3), (05,E4), (14,E2)
--                    P3 => (09,E3), (15,E4), (17,E2)
--
--        * Calcule les différences entre les premiers et les seconds minima
--                    Delta_P1 => (02,E3) - (05,E4) = 3
--                    Delta_P3 => (09,E3) - (15,E4) = 6
--
--        * Le couple prémise/événement conservé correspond au différentielle
--          minimu : (P1, E3). L'événement E3 est ensuite supprimé des autres
--          listes soit :
--                    P3 => (15,E4), (17,E2)
--
--        * Le dernier couple est donc (P3,E4) soit un total minimum égal à 18
--          (total qui n'est calculé par un "Matchmaker" il ne donne que les
--          meilleures couples).

package body Nomo.Interpreter.Internal_Events_Index.Matchmakers is

   procedure Get_Optimum_Pair (This     : in out Matchmaker;
                               Event    : out Internal_Event_Index;
                               Premise  : out Premise_Index;
                               Distance : out Positive_Real) is
      Last_Table         : Premise_Index renames This.Last_Table;
      Form               : Results_Registers renames This.Form;
      Distance_Delta     : Real;
      Min_Distance_Delta : Real := Positive_Real'Last;
      Cursor             : Premise_Index := 1;
      Table_Buffer       : Premise_Index;
      Result_Buffer      : Natural;
   begin
      if Last_Table > 1 then
         for I in 1 .. Last_Table loop
            Distance_Delta := Form (I).Table (2).Distance - Form (I).Table (1).Distance;
            if Min_Distance_Delta > Distance_Delta then
               Min_Distance_Delta := Distance_Delta;
               Cursor := I;
            end if;
         end loop;
         Event := Form (Cursor).Table (1).Event;
         Distance := Form (Cursor).Table (1).Distance;
         Premise :=  Form (Cursor).Reference;
         Table_Buffer := Last_Table - 1;
         Form (Cursor .. Table_Buffer) := Form (Cursor + 1 .. Last_Table);
         Last_Table := Table_Buffer;
         for I in 1 .. Last_Table loop
            Result_Buffer := Form (I).Last_Result;
            for J in 1 .. Result_Buffer loop
               if Form (I).Table (J).Event = Event then
                  Result_Buffer := Result_Buffer - 1;
                  Form (I).Table (J .. Result_Buffer) := Form (I).Table (J + 1 .. Form (I).Last_Result);
                  Form (I).Last_Result := Result_Buffer;
                  exit;
               end if;
            end loop;
         end loop;
      else
         pragma Assert (Last_Table = 1);
         Event := Form (1).Table (1).Event;
         Premise :=  Form (1).Reference;
         Distance := Form (1).Table (1).Distance;
         Last_Table := 0;
      end if;
   end Get_Optimum_Pair;

   procedure Insertion_Sort (T    : in out Results;
                             Last : in Positive);
   --  Le trie par insertion a été choisi car le nombre
   --  d'événements devrait être généralement inférieur à 20.

   procedure Insertion_Sort (T    : in out Results;
                             Last : in Positive) is
      J      : Natural;
      Buffer : Result;
   begin
      for I in  2 .. Last loop
         Buffer := T (I);
         J := Natural'Pred (I);
         while (J >= 1) and then (T (J).Distance > Buffer.Distance) loop
            T (Natural'Succ (J)) := T (J);
            J := Natural'Pred (J);
         end loop;
         T (Natural'Succ (J)) := Buffer;
      end loop;
   end Insertion_Sort;

   function Last_Table_Have_Minimum (This : in Matchmaker) return Boolean is
   begin
      for I in 1 .. This.Form (This.Last_Table).Last_Result loop
         if This.Form (This.Last_Table).Table (I).Distance /= Positive_Real'Last then
            return True;
         end if;
      end loop;
      return False;
   end Last_Table_Have_Minimum;

   function Last_Table_Have_Zero (This : in Matchmaker) return Boolean is
   begin
      for I in 1 .. This.Form (This.Last_Table).Last_Result loop
         if This.Form (This.Last_Table).Table (I).Distance = 0.0 then
            return True;
         end if;
      end loop;
      return False;
   end Last_Table_Have_Zero;

   procedure Match (This : in out Matchmaker)  is
      Form : Results_Registers renames This.Form;
   begin
      for I in Form'First .. This.Last_Table loop
         Insertion_Sort (Form (I).Table, Form (I).Last_Result);
      end loop;
   end Match;

   procedure New_Table (This    : in out Matchmaker;
                        Premise : in Premise_Index) is
      Last_Table : constant Premise_Index := This.Last_Table + 1;
      Register   : Results_Register renames This.Form (Last_Table);
   begin
      This.Last_Table := Last_Table;
      Register.Reference := Premise;
      Register.Last_Result := 0;
   end New_Table;

   procedure Put_Pair (This     : in out Matchmaker;
                       Event    : in Internal_Event_Index;
                       Distance : in Positive_Real) is
      Register    : Results_Register renames This.Form (This.Last_Table);
      Last_Result : constant Natural := Register.Last_Result + 1;
   begin
      Register.Last_Result := Last_Result;
      Register.Table (Last_Result) := (Event, Distance);
   end Put_Pair;

   procedure Reset (This : out Matchmaker) is
   begin
      This.Last_Table := 0;
   end Reset;

end Nomo.Interpreter.Internal_Events_Index.Matchmakers;
