Indefinite containers

As mentioned in Section 8.1, an indefinite (sub)type is one for which we cannot declare an object without giving a constraint (either explicitly or though an initial value). Moreover we cannot have an array of an indefinite subtype. The type String is a good example. Thus we cannot declare an array of the type String because the components might not all be the same size and indexing would be a pain. Class wide types are also indefinite.

generic
   type Element_Type(<>) is private;
   with function "=" (Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Indefinite_Doubly_Linked_Lists is
   pragma Preelaborate(Indefinite_Doubly_Linked_Lists);

where we see that the formal type Element_Type has unknown discriminants and so permits the actual type to be any indefinite type (and indeed a definite type as well). So if we want to manipulate lists of strings where the individual strings can be of any length then we declare

package String_Lists is new Ada.Containers.Indefinite_Doubly_Linked_Lists(String);

generic
   type Key_Type(<>) is private;
   type Element_Type(<>)  is private;
   with function "<" (Left, Right: Key_Type) return Boolean is <>;
   with function "=" (Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Indefinite_Ordered_Maps is
   pragma Preelaborate(Indefinite_Ordered_Maps);

One is that the Insert procedures for Vectors, Lists and Maps which insert an element with its default value are omitted (because there is no way to create a default initialized object of an indefinite type anyway).

The other is that the parameter Element of the access procedure Process of Update_Element (or the garrulous Update_Element_Preserving_Key in the case of sets) can be constrained even if the type Element_Type is unconstrained.

As an example of the use of an indefinite container consider the problem of creating an index. For each word in a text file we need a list of its occurrences. The individual words can be represented as just objects of the type String. It is perhaps convenient to consider strings to be the same irrespective of the case of characters and so we define

function Same_Strings(S, T: String) return Boolean is
begin
return To_Lower(S) = To_Lower(T);
end Same_Strings;

type Place is
   record
      Page: Text_IO.Positive_Count;
      Line: Text_IO.Positive_Count;
      Col: Text_IO.Positive_Count;
   end record;

The index is essentially a map from the type String to a list of values of type Place. We first create a definite list container for handling the lists thus

package Places is new Doubly_Linked_Lists(Place);

package Indexes is new Indefinite_Hashed_Maps(
        Key_Type => String;
        Element_Type => Places.List;
        Hash => Ada.Strings.Hash;
        Equivalent_Keys => Same_Strings;
        "=" => Places."=");

The_Index: Indexes.Map;

It might be helpful for the index to contain information saying which file it refers to. We can extend the type Map thus (remember that container types are tagged)

type Text_Map is new Indexes.Map with
   record
      File_Ref: Text_IO.File_Access;
   end record;

My_Index: Text_Map := (Indexes.Empty_Map with My_File'Access);

We can now declare various subprograms to manipulate our map. For example to add a new item we have first to see whether the word is already in the index – if it is not then we add the new word to the map and set its list to a single element whereas if it is already in the index then we add the new place entry to the corresponding list. Thus

procedure Add_Entry(Index: in out Text_Map; Word: String; P: Place) is
   M_Cursor: Indexes.Cursor;
   A_List: Places.List;    -- empty list of places
begin
   M_Cursor := Index.Find(Word);
   if M_Cursor = Indexes.No_Element then
      -- it's a new word
      A_List.Append(P);
      Index.Insert(Word, A_List);
   else
      -- it's an old word
      A_List := Element(M_Cursor);    -- get old list
      A_List.Append(P);    -- add to it
      Index.Replace_Element(M_Cursor, A_List);
   end if;
end Add_Entry;

A number of points should be observed. The type Text_Map being derived from Indexes.Map inherits all the map operations and so we can write Index.Find(Word) which uses the prefixed notation (or we can write Indexes.Find(Index, Word)). On the other hand auxiliary entities such as the type Cursor and the constant No_Element are of course in the package Indexes and have to be referred to as Indexes.Cursor and so on.

A big problem with the procedure as written however is that it uses Element and Replace_Element rather than Update_Element. This means that it copies the whole of the existing list, adds the new item to it, and then copies it back. Here is an alternative version

procedure Add_Entry(Index: in out Text_Map; Word: String; P: Place) is
   M_Cursor: Indexes.Cursor;
   A_List: Places.List;    -- empty list of places
begin
   M_Cursor := Index.Find(Word);
   if M_Cursor = Indexes.No_Element then
      -- it's a new word
      A_List.Append(P);
      Index.Insert(Word, A_List);
   else
      -- it's an old word
      declare
         -- this procedure adds to the list in situ
         procedure Add_It(The_Key: in String; The_List: in out Places.List) is
         begin
            The_List.Append(P);
         end Add_It;
      begin
         -- and here we call it via Update_Element
         Index.Update_Element(M_Cursor, Add_It'Access);
      end;
   end if;
end Add_Entry;

This is still somewhat untidy. In the case of a new word we might as well make the new map entry with an empty list and then update it thereby sharing the calls of Append. We get

procedure Add_Entry(Index: in out Text_Map; Word: String; P: Place) is
   M_Cursor: Indexes.Cursor := Index.Find(Word);
   OK: Boolean;
begin
   if M_Cursor = Indexes.No_Element then
      -- it's a new word
      Index.Insert(Word, Places.Empty_List, M_Cursor, OK);
      -- M_Cursor now refers to new position
      -- and OK will be True
   end if;
   declare
     -- this procedure adds to the list in situ
      procedure Add_It(The_Key: in String; The_List: in out Places.List) is
      begin
         The_List.Append(P);
      end Add_It;
   begin
      -- and here we call it via Update_Element
      Index.Update_Element(M_Cursor, Add_It'Access);
   end;
end Add_Entry;

It will be recalled that there are various versions of Insert. We have used that which has two out parameters being the position where the node was inserted and a Boolean parameter indicating whether a new node was inserted or not. In this case we know that it will be inserted and so the final parameter is a nuisance (but sadly we cannot default out parameters). Note also that we need not give the parameter Places.Empty_List because another version of Insert will do that automatically since that is the default value of a list anyway.

Yet another approach is not to use Find but just call Insert. We can even use the defaulted version – if the word is present then the node is not changed and the position parameter indicates where it is, if the word is not present then a new node is made with an empty list and again the position parameter indicates where it is.

procedure Add_Entry(Index: in out Text_Map; Word: String; P: Place) is
   M_Cursor: Indexes.Cursor;
   Inserted: Boolean;
begin
   Index.Insert(Word, M_Cursor, Inserted);
   -- M_Cursor now refers to position of node
   -- and Inserted indicates whether it was added
   declare
     -- this procedure adds to the list in situ
      procedure Add_It(The_Key: in String; The_List: in out Places.List) is
      begin
         The_List.Append(P);
      end Add_It;
   begin
      -- and here we call it via Update_Element
      Index.Update_Element(M_Cursor, Add_It'Access);
   end;
end Add_Entry;

We can now do some queries on the index. For example we might want to know how many different four-lettered words there are in the text. We can either use Iterate or do it ourselves with Next as follows

function Four_Letters(Index: Text_Map) return Integer is
   Count: Integer := 0;
   C: Indexes.Cursor := Index.First;
begin
   loop
      if Key(C)'Length = 4 then
         Count := Count + 1;
      end if;
      Indexes.Next(C);
      exit when C = Indexes.No_Element;
   end loop;
   return Count;
end Four_Letters;

We might finally wish to know how many four-lettered words there are on a particular page. (This is just an exercise – it would clearly be simplest to search the original text!) We use Iterate this time both to scan the map for the words and then to scan each list for the page number

function Four_Letters_On_Page(
         Index: Text_Map;
         Page: Text_IO.Positive_Count) return Integer is
   Count: Integer := 0;

procedure Do_It_Map(C: Indexes.Cursor) is

      procedure Do_It_List(C: Places.Cursor) is
      begin
         if Element(C).Page = Page then
            Count := Count + 1;
         end if;
      end Do_It_LIst;

      procedure Action(K: String; E: Places.List) is
      begin
         if K'Length = 4 then
            -- now scan list for instances of Page
            E.Iterate(Do_It_List'Access);
         end if;
      end Action;

   begin
      Indexes.Query_Element(C, Action'Access);
   end Do_It_Map;

begin
Index.Iterate(Do_It_Map'Access);
return Count;
end Four_Letters_On_Page;

We could of course have used First and Next to search the list. But in any event the important point is that by using Query_Element we do not have to copy the list in order to scan it.

Rationale for Ada 2005

8.5 Indefinite containers