-- set_of_natural_pkg.ads
with Interfaces;                 use Interfaces;
with Ada.Finalization;
with Ada.Unchecked_Deallocation;
with Ada.Iterator_Interfaces;

package set_of_natural_pkg is

   -- --------------------------------------------------------------------------
   -- Определиние типов элементов множества
   subtype element_value_ext is Integer range -1 .. 4096*4096 - 1;
   subtype element_value is element_value_ext range 0 .. element_value_ext'Last;
   no_element_value : constant element_value_ext := -1;
   -- --------------------------------------------------------------------------

   -- --------------------------------------------------------------------------
   -- публичное определение типа множества "BS_Set"
   type BS_Set is tagged private
     with
       Constant_Indexing => BS_Element,
       Default_Iterator  => BS_Iterate,
       Iterator_Element  => element_value;
   type BS_Access is access all BS_Set;
   -- --------------------------------------------------------------------------

   -- --------------------------------------------------------------------------
   -- Определения для "Ada.Iterator_Interfaces" (перечисление элементов множества)
   type BS_Cursor is private;
   no_element : constant BS_Cursor;
   function BS_Has_Element (Position : BS_Cursor) return Boolean;
   package BS_Iterator_Interface is new Ada.Iterator_Interfaces( BS_Cursor, BS_Has_Element );
   function BS_Element(Set : aliased BS_Set; Position : BS_Cursor) return element_value_ext;
   function To_Cursor (Set : aliased BS_Set; Value : element_value_ext) return BS_Cursor;
   function BS_Iterate(Set : BS_Set) return BS_Iterator_Interface.Reversible_Iterator'Class;
   function BS_Iterate(Set : BS_Set; Start : BS_Cursor) return BS_Iterator_Interface.Reversible_Iterator'Class;
   function BS_Find(Set : BS_Set; cs_element : element_value) return BS_Cursor;
   -- --------------------------------------------------------------------------

   -- получение мощности множества (количества элементов в множестве)
   function get_power(set_object : BS_set) return Natural;

   procedure Deallocate(ptr : in out BS_Access);
   -- --------------------------------------------------------------------------
   -- Добавление нового элемента в множество.
   --    Если параметр element = no_element_value то значение добавляемого элемента устанавливается на единицу
   --    большим максимального элемента присутствующего в множестве (если множество было пустым то значение
   --    элемента устанавливается равным нулю). В любом случае, выходной параметр element_pos получает значение
   --    добавляемого элемента.
   procedure Append (
                     set_object : in out BS_Set;
                     element : in element_value_ext;
                     element_pos : out element_value_ext
                    );
   -- --------------------------------------------------------------------------
   -- Удаление элемента из множества
   procedure Remove (
                     set_object : in out BS_Set;
                     element : in element_value
                    );
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “or” – объединение множеств.
   function "or" (Left, Right : BS_Set) return BS_Set;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “and” – пересечение множеств.
   function "and" (Left, Right : BS_Set) return BS_Set;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “xor” – антипересечение множеств.
   function "xor" (Left, Right : BS_Set) return BS_Set;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “-” – вычитание множеств.
   function "-" (Left, Right : BS_Set) return BS_Set;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “not” – инверсия множества.
   function "not" (set_object : BS_Set) return BS_Set;
   -- --------------------------------------------------------------------------
   procedure minmax_recalculation( set_object : in out BS_Set);
   -- --------------------------------------------------------------------------
   -- Очистка множества.
   procedure Clear( set_object : in out BS_Set);
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “=” – предикат равенства множеств.
   function "=" (Left, Right : BS_Set) return Boolean;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “>” – предикат полного включения.
   --    Множество «Right» полностью содержится в множестве «Left».
   function ">" (Left, Right : BS_Set) return Boolean;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Переопределённая операция “>=” – предикат неполного включения.
   --    Множество «Right» содержится в множестве или равно множеству «Left».
   function ">=" (Left, Right : BS_Set) return Boolean;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Предикат пустоты множества.
   function IsEmpty(set_object : BS_Set) return Boolean with Inline => True;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Предикат полного заполнения множества.
   function IsFullFilled(set_object : BS_Set) return Boolean;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Предикат присутствия элемента в множестве.
   function Find(set_object : BS_Set; element : element_value) return Boolean;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Получение первого элемента множества.
   function GetFirst(set_object : BS_Set) return element_value_ext;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Получение последнего элемента множества.
   function GetLast(set_object : BS_Set) return element_value_ext;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Получение следующего элемента множества.
   function GetNext(set_object : BS_Set; element : element_value_ext) return element_value_ext;
   -- --------------------------------------------------------------------------
   -- --------------------------------------------------------------------------
   -- Получение предыдущего элемента множества.
   function GetPrev(set_object : BS_Set; element : element_value_ext) return element_value_ext;
   -- --------------------------------------------------------------------------

private
   type bit_set is array (0 .. 63) of Unsigned_64;
   type bit_set_access is access all bit_set;
   type bit_set_array is array (0 .. 4095) of bit_set_access;
   type bit_mask_array is array (0 .. 63) of Unsigned_64;
   type BS_Set is new Ada.Finalization.Controlled with record
      min_element, max_element : element_value_ext := -1;
      not_empty_bitset, full_bitsets : bit_set := (others => 0);
      bit_sets : bit_set_array := (others => null);
   end record;
   overriding procedure Initialize (set_object : in out BS_Set);
   overriding procedure Adjust     (set_object : in out BS_Set);
   overriding procedure Finalize   (set_object : in out BS_Set);
   procedure Free is
     new Ada.Unchecked_Deallocation (bit_set, bit_set_access);
   procedure Free is
     new Ada.Unchecked_Deallocation (BS_Set, BS_Access);
   type BS_Cursor is
      record
         BS_Set_Ref : BS_Access;
         Value  : element_value_ext := no_element_value;
      end record;
   no_element : constant BS_Cursor := BS_Cursor'(null, no_element_value);
end set_of_natural_pkg;