------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- Cheddar is a GNU GPL real-time scheduling analysis tool.
-- This program provides services to automatically check schedulability and
-- other performance criteria of real-time architecture models.
--
-- Copyright (C) 2002-2020, Frank Singhoff, Alain Plantec, Jerome Legrand, 
--                          Hai Nam Tran, Stephane Rubini
--
-- The Cheddar project was started in 2002 by 
-- Frank Singhoff, Lab-STICC UMR CNRS 6285, Universite de Bretagne Occidentale
-- 
-- Cheddar has been published in the "Agence de Protection des Programmes/France" in 2008. 
-- Since 2008, Ellidiss technologies also contributes to the development of 
-- Cheddar and provides industrial support.
--
-- The full list of contributors and sponsors can be found in AUTHORS.txt and SPONSORS.txt
--
-- 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
--
--
-- Contact : cheddar@listes.univ-brest.fr
--           
------------------------------------------------------------------------------
-- Last update : 
--    $Rev$
--    $Date$
--    $Author: singhoff $
------------------------------------------------------------------------------
------------------------------------------------------------------------------

with Text_IO;             	use Text_IO;
with Ada.Strings.Unbounded;	use Ada.Strings.Unbounded;
with Ada.Strings.Bounded; 	use Ada.Strings.Bounded;
with Scheduling_Analysis;	use Scheduling_Analysis;
with Scheduling_Analysis;	use Scheduling_Analysis.Task_Release_Records_Table_Package;
with Tables;
with Task_Set; 			use Task_Set;
with Tasks; 			use Tasks;
with natural_util; 		use natural_util;
with Tasks.Extended; 		use Tasks.Extended;
with Integer_Arrays; 		use Integer_Arrays;
with Framework_Config; use Framework_Config;
with Caches; use Caches;
with Caches; use Caches.Cache_Blocks_Table_Package;

package body Priority_Assignment.Utility is

   procedure Put(obj : in Task_Release_Records_Table_Ptr)
   is
   begin
      for i in 0..obj.Nb_Entries-1 loop
         Put_Line(To_String(obj.Entries(i).task_name));
      end loop;
   end Put;

   procedure warshall_algorithm
     (warshall_array :in out Boolean_Arr_2D_Ptr;
      size : in Integer)
   is
   begin
      for k in 0..size-1 loop
         for i in 0..size-1 loop
            if(warshall_array(i,k)) then
               for j in 0..size-1 loop
                  warshall_array(i,j) := warshall_array(i,j) OR (warshall_array(i,k) AND warshall_array(k,j));
               end loop;
            end if;
         end loop;
      end loop;
   end warshall_algorithm;

   function Calculate_Pi
     (priority_level : in Integer;
      my_tasks : in Tasks_Set)
      return Integer
   is
      Pi : Integer := 1;
      my_iterator : Tasks_Iterator;
      i_task : Generic_Task_Ptr;
   begin
      reset_iterator (my_tasks, my_iterator);
      loop
         current_element (my_tasks, i_task, my_iterator);
         Pi := Lcm(Pi, Periodic_Task_Ptr(i_task).period);
         exit when is_last_element (my_tasks, my_iterator);
         next_element (my_tasks, my_iterator);
      end loop;
      return Pi;
   end Calculate_Pi;

   function Calculate_H
     (my_tasks : in Tasks_Set)
      return Integer
   is
      H : Integer := 1;
      my_iterator : Tasks_Iterator;
      i_task : Generic_Task_Ptr;
   begin
      reset_iterator (my_tasks, my_iterator);
      loop
         current_element (my_tasks, i_task, my_iterator);

         H := Lcm(H, Periodic_Task_Ptr(i_task).period);
         exit when is_last_element (my_tasks, my_iterator);
         next_element (my_tasks, my_iterator);
      end loop;
      return H;
   end Calculate_H;

   procedure Refine_Offset
     (a_task : in Generic_Task_Ptr;
      my_tasks : in Tasks_Set;
      refined_tasks : out Tasks_Set)
   is
      my_iterator : Tasks_Iterator;
      j_task      : Generic_Task_Ptr;


      --Oi : Float := Float(a_task.offsets.Entries(0).offset_value);
      Oi : Float := Float(a_task.start_time);
      Oj : Float;
      Tj : Float;
      lj : Float;

   begin
      duplicate(my_tasks,refined_tasks);
      -- if(a_task.offsets.Entries(0).offset_value = 0) then
      if(a_task.start_time = 0) then
         return;
      end if;

      reset_iterator (refined_tasks, my_iterator);

      loop
         current_element (refined_tasks, j_task, my_iterator);
         Oj := Float(j_task.start_time);
         Tj := Float(Periodic_Task_Ptr(j_task).period);

         if (j_task.name = a_task.name) then
            j_task.start_time := 0;
         else
            if(Oi > Oj) then
               lj := Float'Ceiling((Oi-Oj) / Tj);
               j_task.start_time := Natural(lj * Tj + Oj) - Natural(Oi);
            else
               j_task.start_time := j_task.start_time - Natural(Oi);
            end if;
         end if;

         exit when is_last_element (refined_tasks, my_iterator);

         next_element (refined_tasks, my_iterator);

      end loop;


   end Refine_Offset;

   procedure Calculate_Task_Release_Records_Table
     (t_start : in Integer;
      t_end : in Integer;
      a_task : in out Generic_Task_Ptr;
      my_tasks : in out Tasks_Set;
      a_task_release_records_table : out Task_Release_Records_Table)
   is
      my_iterator : Tasks_Iterator;
      i_task : Generic_Task_Ptr;

      track_time : Integer := t_start;

      finished : boolean;
      temp : Task_Release_Record_Ptr;

      a_task_release_record : Task_Release_Record_Ptr;
   begin
      --CALCULATE
      reset_iterator (my_tasks, my_iterator);
      loop
         current_element (my_tasks, i_task, my_iterator);
         track_time:= t_start;
         if(i_task.name /= a_task.name AND i_task.priority > a_task.priority) then

            -- track_time:= Periodic_Task_Ptr(i_task).period * (t_start/Periodic_Task_Ptr(i_task).period) + i_task.offsets.Entries(0).offset_value;
            track_time:= Periodic_Task_Ptr(i_task).period * (t_start/Periodic_Task_Ptr(i_task).period) + i_task.start_time;
            while(track_time < t_start) loop
               track_time := track_time + Periodic_Task_Ptr(i_task).period;
            end loop;

            while(track_time < t_end) loop

               a_task_release_record := new Task_Release_Record;
               a_task_release_record.task_name := i_task.name;
               a_task_release_record.capacity := i_task.capacity;
               a_task_release_record.release_time := track_time;
               a_task_release_record.finish_time := track_time + i_task.capacity;
               a_task_release_record.deadline := track_time + i_task.deadline;
               Add(a_task_release_records_table, a_task_release_record);

               track_time := track_time + Periodic_Task_Ptr(i_task).period;
            end loop;
         end if;
         exit when is_last_element (my_tasks, my_iterator);
         next_element (my_tasks, my_iterator);
      end loop;

      --SORT
      loop
         finished := true;
         for j in 0 .. a_task_release_records_table.Nb_Entries-2 loop
            if(a_task_release_records_table.Entries(j+1).release_time < a_task_release_records_table.Entries(j).release_time) then
               finished := false;
               temp := a_task_release_records_table.Entries(j+1);
               a_task_release_records_table.Entries(j+1) := a_task_release_records_table.Entries(j);
               a_task_release_records_table.Entries(j) := temp;
            end if;
         end loop;

         exit when finished;
      end loop;
   end Calculate_Task_Release_Records_Table;

   procedure Calculate_Task_Release_Records_Table
     (t_start  : in Integer;
      t_end    : in Integer;
      a_task   : in Generic_Task_Ptr;
      my_tasks : in out Tasks_Set;
      a_tuea   : in Task_UCB_ECB_Array_Ptr;
      a_trrt   : out Task_Release_Records_Table_Ptr)
   is
      my_iterator 	: Tasks_Iterator;
      i_task 		: Generic_Task_Ptr;
      track_time 	: Integer := t_start;
      finished 		: boolean;
      temp  		: Task_Release_Record_Ptr;
      a_trr 		: Task_Release_Record_Ptr;
      a_trr_ext		: Task_Release_Record_Ext_Ptr;
   begin
      a_trrt := new Task_Release_Records_Table;

      --COMPUTE
      reset_iterator (my_tasks, my_iterator);
      loop
         current_element (my_tasks, i_task, my_iterator);
         track_time:= t_start;
         if(i_task.name /= a_task.name AND i_task.priority > a_task.priority) then

            --track_time:= Periodic_Task_Ptr(i_task).period * (t_start/Periodic_Task_Ptr(i_task).period) + i_task.offsets.Entries(0).offset_value;
            track_time:= Periodic_Task_Ptr(i_task).period * (t_start/Periodic_Task_Ptr(i_task).period) + i_task.start_time;
            while(track_time < t_start) loop
               track_time := track_time + Periodic_Task_Ptr(i_task).period;
            end loop;

            while(track_time < t_end) loop
               a_trr_ext			:= new Task_Release_Record_Ext;
               a_trr_ext.task_name 		:= i_task.name;
               a_trr_ext.capacity 		:= i_task.capacity;
               a_trr_ext.release_time 		:= track_time;
               a_trr_ext.finish_time 		:= track_time + i_task.capacity;
               a_trr_ext.deadline 		:= track_time + i_task.deadline;
               a_trr_ext.completed 		:= False;
               for i in 0..a_tuea'Length-1 loop
                  if(a_tuea(i).Task_Name = i_task.name) then
                     a_trr_ext.UCBs 		:= a_tuea(i).UCBs;
                     a_trr_ext.ECBs 		:= a_tuea(i).ECBs;
                     a_trr_ext.task_index 	:= a_tuea(i).Task_Index;
                  end if;
               end loop;
               Fill_Tasks_UCBs_In_Cache(a_trr_ext);

               a_trr := Task_Release_Record_Ptr(a_trr_ext);
               Add(a_trrt.all, a_trr);
               track_time := track_time + Periodic_Task_Ptr(i_task).period;
            end loop;
         end if;
         exit when is_last_element (my_tasks, my_iterator);
         next_element (my_tasks, my_iterator);
      end loop;


      --SORT
      loop
         finished := true;
         for j in 0 .. a_trrt.Nb_Entries-2 loop
            if(a_trrt.Entries(j+1).release_time < a_trrt.Entries(j).release_time) then
               finished := false;
               temp := a_trrt.Entries(j+1);
               a_trrt.Entries(j+1) := a_trrt.Entries(j);
               a_trrt.Entries(j) := temp;
            end if;
         end loop;

         exit when finished;
      end loop;

   end Calculate_Task_Release_Records_Table;

   procedure Check_CCB
     (a_task_ucb_ecb_array : in Task_UCB_ECB_Array_Ptr;
      preempting_task : in Unbounded_String;
      preempted_task : in Unbounded_String;
      n_ccb : out Natural)
   is
      m,n : Integer;
   begin
      n_ccb := 0;
      for i in 0..a_task_ucb_ecb_array'Length-1 loop
         if (a_task_ucb_ecb_array(i).Task_Name = preempting_task) then
            m := i;
         end if;
         if (a_task_ucb_ecb_array(i).Task_Name = preempted_task) then
            n := i;
         end if;
      end loop;

      Intersect(arr_a => a_task_ucb_ecb_array(m).ECBs,
                arr_b => a_task_ucb_ecb_array(n).UCBs,
                n     => n_ccb);
   end Check_CCB;

   procedure Get_EUCBs
     (a_task_ucb_ecb_array : in Task_UCB_ECB_Array_Ptr;
      preempting_task : in Unbounded_String;
      preempted_task : in Unbounded_String;
      arr_eucbs : out Integer_Array)
   is
      m,n : Integer;
      n_ccb : Integer;
   begin
      n_ccb := 0;
      for i in 0..a_task_ucb_ecb_array'Length-1 loop
         if (a_task_ucb_ecb_array(i).Task_Name = preempting_task) then
            m := i;
         end if;
         if (a_task_ucb_ecb_array(i).Task_Name = preempted_task) then
            n := i;
         end if;
      end loop;

      Intersect(arr_a => a_task_ucb_ecb_array(m).ECBs,
                arr_b => a_task_ucb_ecb_array(n).UCBs,
                arr_c => arr_eucbs,
                n     => n_ccb);
   end Get_EUCBs;


   function Get_CRPD_by_NCB (n_ucb_ecb : in Integer) return Integer is
   begin
      return n_ucb_ecb;
   end Get_CRPD_By_NCB;

   -----------------------------------------------------------------------------
   function Compute_CRPD_Potential_Preempted
     (sets : in IAs_Ptr;
      k : in Integer;
      n : in Integer)
      return Integer
   is
      generic
         type Integers is range <>;
      package Combinations is
         type Combination is array (Natural range <>) of Integers;
         procedure First (X : in out Combination);
         procedure Next (X : in out Combination);
      end Combinations;

      package body Combinations is
         procedure First (X : in out Combination) is
         begin
            X (0) := Integers'First;
            for I in 1..X'Last loop
               X (I) := X (I - 1) + 1;
            end loop;
         end First;
         procedure Next (X : in out Combination) is
         begin
            for I in reverse X'Range loop
               if X (I) < Integers'Val (Integers'Pos (Integers'Last) - X'Last + I) then
                  X (I) := X (I) + 1;
                  for J in I + 1..X'Last loop
                     X (J) := X (J - 1) + 1;
                  end loop;
                  return;
               end if;
            end loop;
            raise Constraint_Error;
         end Next;
      end Combinations;

      subtype Five is Integer range 0..n-1;
      package Fives is new Combinations (Five);
      use Fives;

      X : Combination (0..k-1);
      --------------------------------------------------------------------------
      n_eucb : Integer := 0;
      arr_result : Integer_Array;
   begin
      First (X);
      Initialize(arr_result);
      for I in X'Range loop
         Union(arr_a => arr_result,
               arr_b => sets(X(I)));
      end loop;
      n_eucb := arr_result.Size;

      loop
         Next (X);
         Initialize(arr_result);
         for I in X'Range loop
            Union(arr_a => arr_result,
                  arr_b => sets(X(I)));
         end loop;
         if(n_eucb < arr_result.Size) then
            n_eucb := arr_result.Size;
         end if;
      end loop;
   exception
      when Constraint_Error =>
         --Put_Line(n_eucb'Img);
         Free(arr_result);
         return n_eucb;
   end Compute_CRPD_Potential_Preempted;
   -----------------------------------------------------------------------------

   procedure Initialize (a_ias : in out IAs_Ptr) is
   begin
      a_ias := new IAs(0..0);
   end Initialize;

   procedure Add(a_ias: in out IAs_Ptr;
                 a_ia : in Integer_Array)
   is
      temp_ias : IAs_Ptr;
   begin
      temp_ias := new IAs(0..a_ias'Length);
      for i in 0..a_ias'Length-1 loop
         temp_ias(i) := a_ias(i);
      end loop;
      temp_ias(a_ias'Length) := a_ia;
      Free(a_ias);
      a_ias := temp_ias;
   end Add;

   procedure Fill_Tasks_UCBs_In_Cache(a_trr : in out Task_Release_Record_Ext_Ptr)
   is
   begin
      Free(a_trr.UCBs_In_Cache.Elements);
      Initialize(a_trr.UCBs_In_Cache);

      for i in 0..a_trr.UCBs.Size-1 loop
         Add(a_trr.UCBs_In_Cache, a_trr.UCBs.Elements(i));
      end loop;
   end Fill_Tasks_UCBs_In_Cache;


   procedure Initialize
     (My_Task_UCB_ECB 	: in out Task_UCB_ECB;
      Task_Name         : in Unbounded_String;
      Task_Index	: in Integer := 0;
      UCBs      	: in Integer_Array;
      CRPD_UCB		: in Integer := 0;
      ECBs		: in Integer_Array;
      CRPD_ECB		: in Integer := 0)
   is
   begin
      My_Task_UCB_ECB.Task_Name := Task_Name;
      My_Task_UCB_ECB.Task_Index := Task_Index;
      My_Task_UCB_ECB.UCBs := UCBs;
      My_Task_UCB_ECB.ECBs := ECBs;
      My_Task_UCB_ECB.CRPD_UCB := CRPD_UCB;
      My_Task_UCB_ECB.CRPD_ECB := CRPD_ECB;
   end Initialize;

   function Get_Task_CRPD_ECB
     (A_Task_UCB_ECB_Array_Ptr : in Task_UCB_ECB_Array_Ptr;
      Task_Name : in Unbounded_String)
      return Integer
   is
   begin
      for i in 0..A_Task_UCB_ECB_Array_Ptr'Length-1 loop
         if (A_Task_UCB_ECB_Array_Ptr(i).Task_Name = Task_Name) then
            return A_Task_UCB_ECB_Array_Ptr(i).CRPD_ECB;
         end if;
      end loop;
      return 0;
   end Get_Task_CRPD_ECB;

   function Get_Task_CRPD_UCB
     (A_Task_UCB_ECB_Array_Ptr : in Task_UCB_ECB_Array_Ptr;
      Task_Name : in Unbounded_String)
      return Integer
   is
   begin
      for i in 0..A_Task_UCB_ECB_Array_Ptr'Length-1 loop
         if (A_Task_UCB_ECB_Array_Ptr(i).Task_Name = Task_Name) then
            return A_Task_UCB_ECB_Array_Ptr(i).CRPD_UCB;
         end if;
      end loop;
      return 0;
   end Get_Task_CRPD_UCB;

   procedure CAP_to_TUEA
     (my_tasks		       : in Tasks_Set;
      my_cache_access_profiles : in Cache_Access_Profiles_Set;
      a_task_ucb_ecb_array     : in out Task_UCB_ECB_Array_Ptr)
   is
      a_task      : Generic_Task_Ptr;
      my_iterator : Tasks_Iterator;

      a_cache_access_profile : Cache_Access_Profile_Ptr;

      ucb_array : Integer_Array;
      ecb_array : Integer_Array;

      N : Integer;
      index : Integer := 0;
   begin
      N := Integer(get_number_of_elements(my_set => my_tasks));
      a_task_ucb_ecb_array := new Task_UCB_ECB_Array (0..N-1);

      reset_iterator(my_set      => my_tasks,
                     my_iterator => my_iterator);
      loop
         current_element (my_tasks, a_task, my_iterator);

         a_cache_access_profile := Search_Cache_Access_Profile(my_cache_access_profiles => my_cache_access_profiles,
                                                               name                     => a_task.cache_access_profile_name);

         Initialize(ecb_array);
         Initialize(ucb_array);

         for i in 0..a_cache_access_profile.ECBs.Nb_Entries-1 loop
            Add(ecb_array,a_cache_access_profile.ECBs.Entries(i).cache_block_number);
         end loop;
         for i in 0..a_cache_access_profile.UCBs.Nb_Entries-1 loop
            Add(ucb_array,a_cache_access_profile.UCBs.Entries(i).cache_block_number);
         end loop;

         a_task_ucb_ecb_array(index).Task_Name := a_task.name;
         a_task_ucb_ecb_array(index).Task_Index := index;
         a_task_ucb_ecb_array(index).UCBs := ucb_array;
         a_task_ucb_ecb_array(index).ECBs := ecb_array;
         a_task_ucb_ecb_array(index).CRPD_ECB := Get_CRPD_by_NCB(ecb_array.Size);
         a_task_ucb_ecb_array(index).CRPD_UCB := Get_CRPD_by_NCB(ucb_array.Size);

         index := index + 1;

         exit when is_last_element (my_tasks, my_iterator);
         next_element (my_tasks, my_iterator);
      end loop;
      Put_Line("");
   end CAP_to_TUEA;
end Priority_Assignment.Utility;