Indefinite containers

Rationale for Ada 2005: 6a Containers

ENG

5. Indefinite containers

@ There are versions of the six container packages we have just been discussing for indefinite types.

@ As mentioned in Section 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.

@ The specification of the indefinite container for lists starts

  1        generic
  2                type Element_Type (<>) is private;
  3                with function "=" (Left, Right : Element_Type) return Boolean is <>;
  4        package Ada.Containers.Indefinite_Doubly_Linked_Lists is
  5                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); In the case of ordered maps we have

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

@ showing that both Element_Type and Key_Type can be indefinite.

@ There are two other differences from the definite versions which should be noted.

@ 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

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

@ where the function To_Lower is from the package Ada.Characters.Handling.

@ We can suppose that the positions of the words are described by a type Place thus

  1        type Place is
  2                record
  3                        Page : Text_IO.Positive_Count;
  4                        Line : Text_IO.Positive_Count;
  5                        Col  : Text_IO.Positive_Count;
  6                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); We then create an indefinite map container from the type String to the type List thus

  1        package Indexes is new Indefinite_Hashed_Maps (
  2                Key_Type        => String;
  3                Element_Type    => Places.List;
  4                Hash            => Ada.Strings.Hash;
  5                Equivalent_Keys => Same_Strings;
  6                "="             => Places."=");

@ The index is then declared by writing

  1        The_Index : Indexes.Map;

@ Note that this example illustrates the use of nested containers since the elements in the map are themselves containers (lists).

@ 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)

  1        type Text_Map is new Indexes.Map with
  2                record
  3                        File_Ref : Text_IO.File_Access;
  4                end record;

@ and now we can more usefully declare

  1        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

  1        procedure Add_Entry (Index : in out Text_Map; Word : String; P : Place) is
  2                M_Cursor : Indexes.Cursor;
  3                A_LIst : Places.List; -- empty list of places
  4        begin
  5                M_Cursor := Index.Find (Word);
  6                if M_Cursor = Indexes.No_Element then
  7                        -- it's a new word
  8                        A_LIst.Append (P);
  9                        Index.Insert (Word, A_List);
 10                else
 11                        -- it's an old word
 12                        A_LIst := Element (M_Cursor); -- get old list
 13                        A_List.Append (P); -- add to it
 14                        Index.Replace_Element (M_Cursor, A_LIst);
 15                end if;
 16        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

  1        procedure Add_Entry (Index : in out Text_Map; Word : String; P : Place) is
  2                M_Cursor : Indexes.Cursor;
  3                A_LIst : Places.List; -- empty list of places
  4        begin
  5                M_Cursor := Index.Find (Word);
  6                if M_Cursor = Indexes.No_Element then
  7                        -- it's a new word
  8                        A_LIst.Append (P);
  9                        Index.Insert (Word, A_List);
 10                else
 11                        -- it's an old word
 12                        declare
 13                                -- this procedure adds to the list in situ
 14                                procedure Add_It (The_Key : in String; The_List : in out Places.List) is
 15                                begin
 16                                        The_List.Append (P);
 17                                end Add_It;
 18                        begin
 19                                -- and here we call it via Update_Element
 20                                Index.Update_Element (M_Cursor, Add_It'Access);
 21                        end;
 22                end if;
 23        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

  1        procedure Add_Entry (Index : in out Text_Map; Word : String; P : Place) is
  2                M_Cursor : Indexes.Cursor := Index.Find (Word);
  3                OK : Boolean;
  4        begin
  5                if M_Cursor = Indexes.No_Element then
  6                        -- it's a new word
  7                        Index.Insert (Word, Places.Empty_List, M_Cursor, OK);
  8                        -- M_Cursor now refers to new position
  9                        -- and OK will be True
 10                end if;
 11                declare
 12                        -- this procedure adds to the list in situ
 13                        procedure Add_It (The_Key : in String; The_List : in out Places.List) is
 14                        begin
 15                                The_List.Append (P);
 16                        end Add_It;
 17                begin
 18                        -- and here we call it via Update_Element
 19                        Index.Update_Element (M_Cursor, Add_It'Access);
 20                end;
 21        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.

  1        procedure Add_Entry (Index : in out Text_Map; Word : String; P : Place) is
  2                M_Cursor : Indexes.Cursor;
  3                Inserted : Boolean;
  4        begin
  5                Index.Insert (Word, M_Cursor, Inserted);
  6                -- M_Cursor now refers to position of node
  7                -- and Inserted indicates whether it was added
  8                declare
  9                        -- this procedure adds to the list in situ
 10                        procedure Add_It (The_Key : in String; The_List : in out Places.List) is
 11                        begin
 12                                The_List.Append (P);
 13                        end Add_It;
 14                begin
 15                        -- and here we call it via Update_Element
 16                        Index.Update_Element (M_Cursor, Add_It'Access);
 17                end;
 18        end Add_Entry;

@ Curiously enough we do not need to use the value of Inserted. We leave the reader to decide which of the various approaches is best.

@ 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

  1        function Four_Letters (Index : Text_Map) return Integer is
  2                Count : Integer := 0;
  3                C : Indexes.Cursor := Index.First;
  4        begin
  5                loop
  6                        if Key (C)'Length = 4 then
  7                                Count := Count + 1;
  8                        end if;
  9                        Indexes.Next (C);
 10                        exit when C = Indexes.No_Element;
 11                end loop;
 12                return Count;
 13        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

  1        function Four_Letters_On_Page (Index : Text_Map;
  2                Page : Text_IO.Positive_Count) return Integer
  3        is
  4                Count : Integer := 0;
  5                procedure Do_It_Map (C : Indexes.Cursor) is
  6                        procedure Do_It_List (C : Places.Cursor) is
  7                        begin
  8                                if Element (C).Page = Page then
  9                                        Count := Count + 1;
 10                                end if;
 11                        end Do_It_LIst;
 12                        procedure Action (K : String; E : Places.List) is
 13                        begin
 14                                if K'Length = 4 then
 15                                        -- now scan list for instances of Page
 16                                        E.Iterate (Do_It_List'Access);
 17                                end if;
 18                        end Action;
 19                begin
 20                        Indexes.Query_Element (C, Action'Access);
 21                end Do_It_Map;
 22        begin
 23                Index.Iterate (Do_It_Map'Access);
 24                return Count;
 25        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: 6a Containers

ENGRUSTOPBACKNEXT

5. Неопределённые Контейнеры

@ Для шести контейнерных пакетов, которые мы только что обсуждали имеются версии и для неопределенных типов.

@ Как было упомянуто в Разделе 1, неопределенный тип (подтип) это тот для которого мы не можем объявить объект не задав какого-нибудь ограничения (или явно или через задание начального значения). Кроме того, у нас не может быть массивов из элементов неопределенного подтипа. Тип String тому хороший пример. Т.е., мы не можем объявить массив элементов типа String, потому что строки могут быть разных размеров и индексация в этом случае весьма проблематична. Класс широких типов также является неопределённым.

@ Спецификация неопределенного контейнера для списков начинается так:

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

@ где мы видим, что формальный тип Element_Type имеет неизвестные дискриминанты и, таким образом, это разрешает фактическому типу быть любым неопределенным типом (и действительно определенным типом также). Так, если мы хотим управлять списками строк, где индивидуальные строки могут иметь разную длину тогда, мы объявляем package String_Lists is new Ada.Containers.Indefinite_Doubly_Linked_Lists (String); В случае упорядоченных карт мы имеем:

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

@ показывая что и Element_Type и Key_Type могут быть неопределенными.

@ Есть два других отличия от ранее определенных версий, которые стоит упомянуть.

@ Первое - это исключение процедур Insert для Векторов, Списков и Карт, которые вставляет элемент с его значением по умолчанию (потому что нет никакого способа создать значение по умолчанию для объекта неопределенного типа так или иначе).

@ Второе это то, что параметр Element в ссылке на процедуру Process в процедуре Update_Element (или её многословный вариант Update_Element_Preserving_Key в случае наборов) может быть сдержан, даже если тип Element_Type беспрепятственный.

@ Как пример использования неопределенного контейнера рассмотрим проблему создания индекса. Для каждого слова в текстовом файле мы можем пожелать иметь список вхождений. Индивидуальные слова могут быть представлены только как объекты типа String. Возможно удобно полагать, что значение строки не чувствительно к регистру символов, и таким образом, мы определяем:

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

@ где функция To_Lower из пакета Ada.Characters.Handling.

@ Мы можем предположить, что позиции слов описаны типом Place таким образом:

  1        type Place is
  2                record
  3                        Page : Text_IO.Positive_Count;
  4                        Line : Text_IO.Positive_Count;
  5                        Col  : Text_IO.Positive_Count;
  6                end record;

@ Индекс - это по существу карта от типа String к списку значений типа Place. Мы сначала создаем определенный списковый контейнер для обработки списков: package Places is new Doubly_Linked_Lists (Place); Затем мы создаем неопределенный контейнер карты от типа String типу List:

  1        package Indexes is new Indefinite_Hashed_Maps
  2        (       Key_Type        => String;
  3                Element_Type    => Places.List;
  4                Hash            => Ada.Strings.Hash;
  5                Equivalent_Keys => Same_Strings;
  6                "="             => Places."=");

@ Индекс тогда объявляем следующим образом:

  1        The_Index : Indexes.Map;

@ Отметим, что этот пример иллюстрирует использование вложенных контейнеров, так как элементы в карте - сами по себе являются контейнерами (списками).

@ Было бы полезно для индекса содержать информацию, говорящую, к какому файлу он обращается. Мы можем расширить тип Map таким образом (напомним, что контейнерные типы являются тэговыми).

  1        type Text_Map
  2                is new Indexes.Map
  3                        with record
  4                                File_Ref : Text_IO.File_Access;
  5                        end record;

@ и теперь мы можем более естественно объявить

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

@ Теперь мы можем объявить различные подпрограммы для управления нашей картой. Например, чтобы добавить новый элемент мы должны сначала убедиться, является ли уже такое слово в индексе - если это не так тогда, мы добавляем новое слово к карте и устанавливаем ее список в единственный элемент, если же такое слово уже находится в индексе тогда, мы добавляем новую точку входа в соответствующий список таким образом:

  1        procedure Add_Entry
  2        (       Index : in out Text_Map;
  3                Word  : String;
  4                P     : Place)
  5        is
  6                M_Cursor : Indexes.Cursor;
  7                A_LIst   : Places.List; -- empty list of places
  8        begin
  9                M_Cursor := Index.Find (Word);
 10                if M_Cursor = Indexes.No_Element then
 11                        -- it's a new word
 12                        A_LIst.Append (P);
 13                        Index.Insert (Word, A_List);
 14                else
 15                        -- it's an old word
 16                        A_LIst := Element (M_Cursor); -- get old list
 17                        A_List.Append (P); -- add to it
 18                        Index.Replace_Element (M_Cursor, A_LIst);
 19                end if;
 20        end Add_Entry;

@ Обратим внимание на некоторые моменты. Так тип Text_Map, получаемый из Indexes.Map наследует все операции карты и, таким образом, мы можем написать Index.Find (Word) c использованием префиксной нотации (или мы можем написать Index.Find (Index, Word)). С другой стороны, вспомогательные объекты, такие как тип Cursor и константа No_Element находятся непосредственно в пакете Indexes и должны упоминаться как Indexes.Cursor и так далее.

@ Используя процедуры Element и Replace_Element, а не процедуру Update_Element фактически мы сначала копируем весь существующий список, добавляем новый элемент, а затем копируем весь его обратно. Рассмотрим альтернативный вариант:

  1        procedure Add_Entry
  2        (       Index : in out Text_Map;
  3                Word  : String;
  4                P     : Place)
  5        is
  6                M_Cursor : Indexes.Cursor;
  7                A_LIst   : Places.List; -- empty list of places
  8        begin
  9                M_Cursor := Index.Find (Word);
 10                if M_Cursor = Indexes.No_Element then
 11                        -- it's a new word
 12                        A_LIst.Append (P);
 13                        Index.Insert (Word, A_List);
 14                else
 15                        -- it's an old word
 16                        declare
 17                                -- this procedure adds to the list in situ
 18                                procedure Add_It
 19                                (       The_Key  : in String;
 20                                        The_List : in out Places.List) is
 21                                begin
 22                                        The_List.Append (P);
 23                                end Add_It;
 24                        begin
 25                                -- and here we call it via Update_Element
 26                                Index.Update_Element (M_Cursor, Add_It'Access);
 27                        end;
 28                end if;
 29        end Add_Entry;

@ Это всё ещё несколько неопрятно. В случае нового слова мы могли бы также сделать новый вход карты с пустым списком а затем обновить его используя вызовы Append:

  1        procedure Add_Entry
  2        (       Index : in out Text_Map;
  3                Word  : String;
  4                P     : Place)
  5        is
  6                M_Cursor : Indexes.Cursor := Index.Find (Word);
  7                Ok       : Boolean;
  8        begin
  9                if M_Cursor = Indexes.No_Element then
 10                        -- it's a new word
 11                        Index.Insert (Word, Places.Empty_List, M_Cursor, Ok);
 12                        -- M_Cursor now refers to new position
 13                        -- and OK will be True
 14                end if;
 15                declare
 16                        -- this procedure adds to the list in situ
 17                        procedure Add_It
 18                        (       The_Key : in String;
 19                                The_List : in out Places.List) is
 20                        begin
 21                                The_List.Append (P);
 22                        end Add_It;
 23                begin
 24                        -- and here we call it via Update_Element
 25                        Index.Update_Element (M_Cursor, Add_It'Access);
 26                end;
 27        end Add_Entry;

@ Здесь будет выбрана одна из нескольких возможных версий процедуры Insert. Мы использовали ту, которая имеет два параметра, первый из которых указывает позицию, где узел был вставлен, а второй типа Boolean, указывающий, был ли новый узел вставлен или нет. В этом случае мы знаем, что элемент будет вставлен и, таким образом, последний параметр будет неприятностью (печально, но мы не можем использовать значение по умолчанию для параметров типа out). Отметим также, что мы не должны задавать параметр Places.Empty_List, потому что другая версия процедуры Insert сделает это автоматически, так как это - значение по умолчанию списка так или иначе.

@ Еще один подход, мы можем не использовать процедуру Find. Вместо неё мы можем использовать не всегда выполняющую свои обязательства версию процедуры Insert - если слово присутствует тогда, узел не меняется, а параметр позиции указывает, где он находится, если слово не присутствует тогда, создаётся новый узел с пустым списком, и снова параметр позиции указывает, где это произошло.

  1        procedure Add_Entry
  2        (       Index : in out Text_Map;
  3                Word  : String;
  4                P     : Place)
  5        is
  6                M_Cursor : Indexes.Cursor;
  7                Inserted : Boolean;
  8        begin
  9                Index.Insert (Word, M_Cursor, Inserted);
 10                -- M_Cursor now refers to position of node
 11                -- and Inserted indicates whether it was added
 12                declare
 13                        -- this procedure adds to the list in situ
 14                        procedure Add_It
 15                        (       The_Key  : in String;
 16                                The_List : in out Places.List) is
 17                        begin
 18                                The_List.Append (P);
 19                        end Add_It;
 20                begin
 21                        -- and here we call it via Update_Element
 22                        Index.Update_Element (M_Cursor, Add_It'Access);
 23                end;
 24        end Add_Entry;

@ Весьма любопытно, мы не должны использовать значение Inserted. Мы оставляем читателя, чтобы решить, какой из различных подходов лучше.

@ Теперь мы можем сделать несколько запросов к индексу. Например, мы могли бы хотеть знать сколько различных непристойных слов находятся в тексте. Мы можем или использовать процедуру Iterate или сделать это непосредственно используя процедуру Next следующим образом:

  1        function Four_Letters (Index : Text_Map) return Integer is
  2                Count : Integer := 0;
  3                C : Indexes.Cursor := Index.First;
  4        begin
  5                loop
  6                        if Key (C)'Length = 4 then
  7                                Count := Count + 1;
  8                        end if;
  9                        Indexes.Next (C);
 10                        exit when C = Indexes.No_Element;
 11                end loop;
 12                return Count;
 13        end Four_Letters;

@ Мы могли бы наконец пожелать узнать сколько непристойных слов находятся на определённой странице. (Это - только для иллюстрации - ясно что искать это в оригинальном тексте горахдо проще!) Мы используем Iterate на сей раз чтобы просмотреть карту для слов а затем просмотреть каждый список для номера страницы.

  1        function Four_Letters_On_Page
  2        (       Index : Text_Map;
  3                Page  : Text_IO.Positive_Count) return Integer
  4        is
  5                Count : Integer := 0;
  6                procedure Do_It_Map (C : Indexes.Cursor) is
  7                        procedure Do_It_List (C : Places.Cursor) is
  8                        begin
  9                                if Element (C).Page = Page then
 10                                        Count := Count + 1;
 11                                end if;
 12                        end Do_It_LIst;
 13                        procedure Action (K : String; E : Places.List) is
 14                        begin
 15                                if K'Length = 4 then
 16                                        -- now scan list for instances of Page
 17                                        E.Iterate (Do_It_List'Access);
 18                                end if;
 19                        end Action;
 20                begin
 21                        Indexes.Query_Element (C, Action'Access);
 22                end Do_It_Map;
 23        begin
 24                Index.Iterate (Do_It_Map'Access);
 25                return Count;
 26        end Four_Letters_On_Page;

@ Мы, конечно, могли использовать процедуры First и Next для поиска в списке. Но в любом случае важный момент состоит в том, что при использовании Query_Element мы не копируем список, чтобы просмотреть его.

ENG RUS

TOP BACK NEXT

2010-10-24 00:26:58

. .