pragma Ada_2022;
with ada.text_io;
use ada.text_io;
procedure main is
  generic
    type Element is private;
    NullElement : Element;
    with FUNCTION "<" (E1, E2: Element) RETURN Boolean IS <>;
  package dst_matrices  is
    type Matrix (<>) is limited private;
    type Indexes is array (Positive range <>) of Positive;
    function MakeMatrix (Dimensions: Indexes) return Matrix;
    procedure Insert (M: in out Matrix; N: Indexes; E: Element);
    procedure Retrieve (M: Matrix; N:Indexes; Value: out Element; Success: out Boolean);
  private
    type Node;
    type Position is access Node;
    type NodeKind is (ElementKind, Dummy, Index);
    type Node (Kind: NodeKind) is record
      Link: Position;
      case Kind is
        when ElementKind|Index =>
          Rank: Positive;
          case Kind is
            when ElementKind => Info: Element;
            when Index => Nextdimension: Position;
            when others => null;
          end case;
        when others => null;
      end case;
    end record;
    type Matrix (First: Position; DimNumber: Positive) is record
      Dimensions: Indexes (1..DimNumber);
    end record;
  end dst_matrices;

  package body dst_matrices is
    function MakeMatrix (Dimensions: Indexes) return Matrix is
        (new Node(Dummy), Dimensions'Length, Dimensions);

    procedure Insert (M: in out Matrix; N: Indexes; E: Element)
    -- with Refined_Pre => N'Length = M.DimNumber and (for all J in N'Range => N(J) <= M.Dimensions(J))
    is
        Current: Position := M.First;
    begin
        for A of N(1..N'Last-1) loop
            while Current.Link /= null and then Current.Link.Rank < A loop
                Current := @.Link;
            end loop;
            if Current.Link = null or else Current.Link.Rank /= A then
                Current.Link := new Node'(Kind => Index, Link => @, Rank => A, NextDimension => new Node(Dummy));
            end if;
            Current := @.Link.NextDimension;
        end loop;
        while Current.Link /= null and then Current.Link.Rank < N(N'Last) loop
            Current := @.Link;
        end loop;
        if Current.Link = null or else Current.Link.Rank /= N(N'Last) then
            Current.Link := new Node'(Kind => ElementKind, Link => @, Rank => N(N'Last), Info => E);
            put_line (Current.Link.all'Image);
        end if;
    end Insert;

    procedure Retrieve (M: Matrix; N:Indexes; Value: out Element; Success: out Boolean)
     -- with Refined_Pre => N'Length = M.DimNumber and (for all J in N'Range => N(J) <= M.Dimensions(J))
     is
        Current: Position := M.First.Link;
    begin
        for A of N(1..N'Last-1) loop
            while Current /= null and then Current.Rank < A loop
                Current := @.Link;
            end loop;
            if Current /= null or else Current.Rank /= A then
                Success := False;
                return;
            else
                Current := @.NextDimension.Link;
            end if;
        end loop;
        while Current /= null and then Current.Rank < N(N'Last) loop
            Current := @.Link;
        end loop;
        if Current.Link = null or else Current.Rank /= N(N'Last) then
            Success := False;
        else
            Value := Current.Info;
        end if;
    end Retrieve;

  end dst_matrices;

    package dmp is new dst_matrices (Natural, 0);
    use dmp;
    M: Matrix := MakeMatrix ([9,2]);
    Value: Positive;
    Success: Boolean;
begin
    Insert (M, [1,2], 82);
    Insert (M, [1,1], 87);
    Insert (M, [3,2], 87);
    Insert (M, [3,1], 87);
    Retrieve (M, [1,1], Value, Success);
    put_line (Value'Image);
end main;