-- Less_Trivial_Trie - Provide a less trivial trie type that allows for reclaiming the trie storage.
-- Copyright (C) 2022,2024 Prince Trippy <programmer@verisimilitudes.net>.

-- This program is free software: you can redistribute it and/or modify it under the terms of the
-- GNU Affero General Public License version 3 as published by the Free Software Foundation.

-- 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/>.

-- Unlike Trivial_Trie, this library requires Ada 1995 support entirely due to the controlled types.

with Ada.Finalization;

generic
   type  Index_Type is (<>);
   type Domain_Type is (<>);
   type  Input_Type is array (Index_Type range <>) of Domain_Type;
   type Stored_Type is private;
package Less_Trivial_Trie is
   type Trie is limited private;
   procedure Take (Path : in Input_Type; Tree : in out Trie);
   procedure Give (Path : in Input_Type; Tree : in out Trie; What : in  Stored_Type);
   procedure Find (Path : in Input_Type; Tree : in     Trie; Seen : out Boolean;
                                                             Unto : out Stored_Type);
private
   type Node;
   type Link is access Node;
   type Step is array (Domain_Type) of Link;
   type Node is new Ada.Finalization.Controlled with record -- What's the worst that'll happen here?
      Back : Link;
      Just : Boolean := False;
      Here : Stored_Type;
      Past : Step := (others => null);
   end record;

   type Both(Seen : Boolean) is record -- This type exists for function paramater mode restrictions.
      case Seen is
         when True => What : Stored_Type;
         when False => null;
      end case;
   end record;

   type Root is new Ada.Finalization.Controlled with record
      Tree : Link;
   end record;

   protected type Trie is
      procedure Take (Path : in Input_Type);
      procedure Give (Path : in Input_Type; What : in Stored_Type);
      function  Find (Path : in Input_Type) return Both;
      function  Sift (Path : in Input_Type) return Link;
   private
      Tree : Root;
   end Trie;

   procedure Finalize (Object : in out Node);

   procedure Initialize (Object : in out Root);
   procedure   Finalize (Object : in out Root);
end Less_Trivial_Trie;
.