package body generic_bounded_search_trie is

   type trie_node is 
      record 
         key_object     : key_components;  
         in_use         : boolean        := false;  
         data           : data_type;  
         next_component : next_array;  
      end record; 

   type stack_node is 
      record 
         key      : key_type (1 .. maximum_key_length);  
         length   : positive;  
         nxt_node : next;  
         stack    : trie_stack;  
      end record; 

   procedure copy (
         from_trie : in     trie; 
         to_trie   :    out trie  ) is 
      -- Makes an exact copy of a specified trie.
      -- Exception OVERFLOW raised if no space to complete the copy
      temp_from,  
      temp_to   : trie;  
      key       : key_type (1 .. maximum_key_length);  
      length    : positive;  
      data      : data_type;  
   begin
      temp_from := from_trie;
      temp_from.next_in := null;
      for index in 1..temp_from.count loop
         next_inorder (key, length, data, temp_from);
         insert (key(1..length), data, temp_to);
      end loop;
      to_trie := temp_to;
   exception
      when overflow =>
         raise overflow;
   end copy;

   procedure clear (
         this_trie : in out trie ) is 
      -- Returns a trie with a root node that has only null pointers
   begin
      for index in key_components loop
         this_trie.next_component(index) := null;
      end loop;
      this_trie.count   := 0;
      this_trie.next_in := null;
   end clear;

   procedure insert (
         key     : in     key_type;  
         data    : in     data_type; 
         in_trie : in out trie       ) is 
      -- Inserts a given key-data pair into the Trie IN_TRIE.  Nodes are created
      -- as required.  Insertion causes the traversal to reset
      -- Exception KEY_IS_IN_TRIE raised if KEY already in trie.
      -- Exception OVERFLOW raised if no space to add KEY
      -- Exception KEY_INDEX_ERROR raised if KEY indices do not conform.
      temp   : next     := in_trie.next_component (key (key'first));
         
      length : positive := key'last;  
   begin
      if key'first /= 1 or else length > maximum_key_length then
         raise key_index_error;
      elsif
         temp = null then
         -- No KEY with component KEY(1) in Trie
         in_trie.next_component(key(1)) := new trie_node;
         in_trie.next_component(key(1)).key_object := key(1);
         temp := in_trie.next_component(key(1));
      end if;
      for index in positive range 2..length loop
         -- Go through the Trie KEY_ component by KEY component
         if temp.next_component(key(index)) = null then
            -- New node needed
            temp.next_component(key(index)) := new trie_node;
            temp.next_component(key(index)).key_object := key(index
               );
         end if;
         temp := temp.next_component(key(index));
      end loop;
      -- TEMP references the TRIE_NODE where KEY should be.
      if temp.in_use then
         raise key_is_in_trie;
      else
         temp.in_use := true;
         temp.data := data;
         in_trie.count := in_trie.count + 1;
         in_trie.next_in := null;
      end if;
   exception
      when storage_error =>
         raise overflow;
   end insert;

   procedure delete (
         key       : in     key_type; 
         from_trie : in out trie      ) is 
      -- Changes the IN_USE boolean field of the specified KEY to false.
      -- Traversal reset to beginning.
      -- Exception KEY_NOT_IN_TRIE raised if specified KEY not in T
      -- Exception KEY_INDEX_ERROR raised if KEY indices do not conform.
      length : positive := key'last;  
      flag   : boolean  := false;  

      procedure delete (
            key       : in     key_type; 
            next_node : in     next;     
            flag      : in out boolean   ) is 
      begin
         if key'length = 1 then
            -- Check to see if IN_USE = true
            if next_node.next_component(key(key'first)) = null then
               raise key_not_in_trie;
            else
               if next_node.next_component(key(key'first)).in_use =
                     true then
                  next_node.next_component(key(key'first)).in_use :=
                     false;
               else
                  raise key_not_in_trie;
               end if;
               -- Check to see if and subtries exist, set FLAG accordingly
               flag := false;
               for index in key_components loop
                  if next_node.next_component(index) /= null then
                     return;
                  end if;
               end loop;
               flag := true;
            end if;
         elsif
            next_node.next_component(key(key'first)) = null then
            raise key_not_in_trie;
         else
            delete (key(key'first+1..key'last),
               next_node.next_component(key(key'first)), flag);
            if flag then
               -- FLAG = true implies subtrie might be empty
               for index in key_components loop
                  if next_node.next_component(index) /= null then
                     flag := false;
                     return;
                  end if;
               end loop;
               if next_node.next_component(key(key'first)).in_use =
                     false then
                  -- no subtries and IN_USE = false
                  next_node.next_component(key(key'first)) := null
                     ;
               end if;
            end if;
         end if;
      end delete;

   begin
      if key'first /= 1 or length > maximum_key_length then
         raise key_index_error;
      else
         if from_trie.next_component(key(key'first)) = null then
            raise key_not_in_trie;
         elsif
            key'length = 1 then
            if from_trie.next_component(key(key'first)).in_use = true
                  then
               from_trie.next_component(key(key'first)).in_use := false
                  ;
            else
               raise key_not_in_trie;
            end if;
         else
            delete (key(key'first+1..key'last),
               from_trie.next_component(key(key'first)), flag);
            if flag then
               -- FLAG Signals that the subtrie is empty
               from_trie.next_component(key(key'first)) := null;
            end if;
         end if;
         from_trie.count := from_trie.count - 1;
         from_trie.next_in := null;
      end if;
   end delete;

   procedure update (
         key     : in     key_type;  
         data    : in     data_type; 
         in_trie : in out trie       ) is 
      -- Searches for a node with a specified KEY and checks to see if the
      -- the nodes IN_USE = true.  If it is true, the data field is replaced.
      -- Exception KEY_INDEX_ERROR raised if KEY indices do not conform.
      -- Exception KEY_NOT_IN_TRIE raised if specified KEY not in T
      length : positive := key'last;  
      temp   : next;  
   begin
      if key'first /= 1 or length > maximum_key_length then
         raise key_index_error;
      elsif
         in_trie.count = 0 then
         raise key_not_in_trie;
      else
         temp := in_trie.next_component(key(1));
         for index in 2.. length loop
            if temp = null then
               raise key_not_in_trie;
            end if;
            temp := temp.next_component(key(index));
         end loop;
         if temp = null or else not temp.in_use then
            raise key_not_in_trie;
         else
            temp.data := data;
         end if;
      end if;
   end update;

   procedure fix_trie_stack (
         t : in out trie ) is 
      -- Fixes traversal stack so next node to process has
      -- its IN_USE=true.  This also leaves a valid key in the Key component of
      -- the top stack node.  This must terminate because every
      -- leaf of a trie is IN_USE;  If this procedure is called, the
      -- stack is not empty.
      temp_node : next;  
      index     : positive;  
      key_temp  : key_type (1 .. maximum_key_length);  
   begin
      -- Current key in top STACK_NODE is of specified length.  There must
      -- be a key with longer length or this STACK_NODE would not be on the
      -- stack
      index := t.next_in.length;
      -- Get the TRIE_NODE associated with top STACK_NODE
      temp_node := t.next_in.nxt_node;
      --TEMP_NODE.IN_USE = false, not a valid key here, search further
      key_temp(1..index) := t.next_in.key (1..index);
      --Pop stack.  This stack node contains no more information of interest
      t.next_in := t.next_in.stack;
      index := index + 1;
      if index > maximum_key_length then
         -- Leaf must not be a valid key
         raise overflow;
      end if;
      for i in reverse key_components loop
         -- Stack reverses order processed, so put on in reverse order
         if temp_node.next_component(i) /= null then
            -- Must be a valid key-data pair further along, push it on the stack
            key_temp(index) := i;
            t.next_in := new stack_node' (key_temp, index,
               temp_node.next_component(i), t.next_in);
         end if;
      end loop;
      -- Node referenced must contain valid key, if not, go to next level
      if not t.next_in.nxt_node.in_use then
         fix_trie_stack (t);
      end if;
   end fix_trie_stack;

   procedure next_inorder (
         key        :    out key_type;  
         length_key :    out positive;  
         data       :    out data_type; 
         in_trie    : in out trie       ) is 
      -- Returns the next key-data pair of the next node with IN_USE=true
      -- based on a traversal in ascending lexiographic order of KEY
      -- components.  When the traversal is finished, it will repeat
      -- starting at the beginning.  Any insertion or deletion resets the
      -- traversal.
      -- Exception OVERFLOW raised if not enough space for the stack
      -- Exception TREE_IS_EMPTY raised if no key-data pairs to return
      temp_stack : trie_stack;  
      index      : positive;  
      temp_node  : next;  
      key_temp   : key_type (1 .. maximum_key_length);  

   begin -- NEXT_INORDER
      if in_trie.count = 0 then
         raise trie_is_empty;
      elsif
         in_trie.next_in = null then
         -- Check to see if stack has been initialized.
         set_inorder(in_trie);
      end if;
      -- By convention, the STACK_NODE on top contains the a valid key and a
      -- reference to the TRIENODE where the associated data is located.  Get
      -- key-data pair and pop the stack.
      key := in_trie.next_in.key;
      length_key := in_trie.next_in.length;
      data := in_trie.next_in.nxt_node.data;
      -- Update stack so top points to next valid key-data pair.
      -- The node just processed can have subtries or it was a leaf.
      temp_stack := in_trie.next_in;
      in_trie.next_in := in_trie.next_in.stack;
      if in_trie.next_in = null then
         set_inorder (in_trie);
      else
         -- TEMP_STACK references the STACK_NODE just processed.  If the TRIE_NODE
         -- it referenced has any children, they must be placed on the stack.
         if temp_stack.length < maximum_key_length then
            temp_node := temp_stack.nxt_node;
            -- The length of any keys in children will be one more their parent's
            index := temp_stack.length + 1;
            key_temp := temp_stack.key;
            -- Check for all possible children
            for i in reverse key_components loop
               if temp_node.next_component(i) /= null then
                  -- There is a child, put it on the stack
                  key_temp(index) := i;
                  in_trie.next_in := new stack_node' (key_temp, index
                     ,
                     temp_node.next_component(i), in_trie.next_in)
                     ;
               end if;
            end loop;
         end if;
         if not in_trie.next_in.nxt_node.in_use then
            --By convention the top of the stack must reference a valid key-data
            fix_trie_stack(in_trie);
         end if;
      end if;
   exception
      when storage_error =>
         raise overflow;
   end next_inorder;

   procedure set_inorder (
         in_trie : in out trie ) is 
      -- Sets the traversal sequence to list the first valid key-data pair
      -- By convention, the top of the stack will reference a valid
      -- key-data pair
      -- Exception OVERFLOW raised if not enough space for the stack
      -- Exception TREE_IS_EMPTY raised if no key-data pairs to return
      key_temp : key_type (1 .. maximum_key_length);  
   begin
      if in_trie.count = 0 then
         raise trie_is_empty;
      else
         in_trie.next_in := null;
         for index in reverse key_components loop
            if in_trie.next_component(index) /= null then
               -- Subtrie found with valid data, put it on the trie
               key_temp(1) := index;
               in_trie.next_in := new stack_node' (key_temp, 1,
                  in_trie.next_component(index), in_trie.next_in);
            end if;
         end loop;
         if not in_trie.next_in.nxt_node.in_use then
            --By convention the top of the stack must reference a valid key-data
            fix_trie_stack(in_trie);
         end if;
      end if;
   exception
      when storage_error =>
         raise overflow;
   end set_inorder;

   function empty (
         this_trie : trie ) 
     return boolean is 
      -- Returns true if the trie has no key-data pairs.
   begin
      return this_trie.count = 0;
   end empty;

   function full (
         this_trie : trie ) 
     return boolean is 
      -- Returns true if there is no space to add a TRIE_NODE
      temp : next;  
   begin
      temp := new trie_node;
      return false;
   exception
      when storage_error =>
         return true;
   end full;

   function count (
         this_trie : trie ) 
     return natural is 
      -- Returns the number of key-data pairs in T.
   begin
      return this_trie.count;
   end count;

   function equal (
         left,        
         right : trie ) 
     return boolean is 
      -- Returns true if both tries contain the same key-data pairs.
      temp_right   : trie                               := right;
         
      temp_left    : trie                               := left; 
        
      left_key,  
      right_key    : key_type (1 .. maximum_key_length);  
      length_left,  
      length_right : positive;  
      left_data,  
      right_data   : data_type;  
   begin
      if left.count = 0 then
         return right.count = 0;
      elsif
         left.count /= right.count then
         return false;
      else
         temp_left.next_in := null;
         temp_right.next_in := null;
         for index in 1..temp_left.count loop
            next_inorder (left_key, length_left, left_data, temp_left
               );
            next_inorder (right_key, length_right, right_data, temp_right
               );
            if length_left /= length_right or else
                  left_key(1..length_left) /= right_key(1..length_right
                  ) or else
                  left_data /= right_data then
               return false;
            end if;
         end loop;
         return true;
      end if;
   end equal;

   function key_in_trie (
         key     : key_type; 
         in_trie : trie      ) 
     return boolean is 
      -- Returns true if a key-data pair with specified key is in IN_TRIE.
      -- Exception KEY_INDEX_ERROR raised if KEY indices do not conform.
      temp   : next;  
      length : positive := key'last;  
   begin
      if key'first /= 1 or else length > maximum_key_length then
         raise key_index_error;
      else
         -- traverse through Trie, set TEMP to proper subtrie
         temp := in_trie.next_component(key(1));
         for index in 2..length loop
            if temp = null then
               -- Subtrie empty, key is not there
               return false;
            end if;
            temp := temp.next_component(key(index));
         end loop;
         -- Temp should reference the proper TREE_NODE
         if temp = null then
            return false;
         else
            return temp.in_use;
         end if;
      end if;
   end key_in_trie;

   function get_data_for_trie (
         key     : key_type; 
         in_trie : trie      ) 
     return data_type is 
      -- Returns the data field of a specified key-data pair for a given
      -- key in T.
      -- Exception KEY_INDEX_ERROR raised if KEY indices do not conform.
      -- Exception KEY_NOT_IN_TRIE raised if specified KEY not in T
      ans    : data_type;  
      length : positive  := key'last;  
      index  : positive  := 2;  
      temp   : next;  
   begin
      if key'first /= 1 or length > maximum_key_length then
         raise key_index_error;
      else
         temp := in_trie.next_component(key(1));
         for index in 2..length loop
            if temp = null then
               -- Subtrie empty, key is not there
               raise key_not_in_trie;
            end if;
            temp := temp.next_component(key(index));
         end loop;
         -- Temp should reference the proper TREE_NODE
         if temp = null or else not temp.in_use then
            raise key_not_in_trie;
         else
            return temp.data;
         end if;
      end if;
   end get_data_for_trie;

end generic_bounded_search_trie;