Справочник по Ada 2005

A.18.3 Пакет Containers.Doubly_Linked_Lists

Определённый языком обобщённый пакет Containers.Doubly_Linked_Lists предоставляет закрытые типы List и Cursor, а также набор операций для каждого типа. Контейнер списка оптимизирован для вставки и удаления в любой позиции.

Объект контейнера двусвязного списка управляет связанным списком внутренних узлов, каждый из которых содержит элемент и указатели на следующий (преемник) и предыдущий (предшественник) внутренние узлы. Курсор обозначает конкретный узел в списке (и, по расширению, элемент, содержащийся в этом узле). Курсор продолжает указывать на тот же узел (и тот же элемент), пока узел является частью контейнера, даже если узел перемещается в контейнере.

Длина списка — это количество элементов, которые он содержит.

Статическая семантика

Обобщённый пакет библиотек Containers.Doubly_Linked_Lists имеет следующее объявление:

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

type List is tagged private;
pragma Preelaborable_Initialization(List);

type Cursor is private;
pragma Preelaborable_Initialization(Cursor);

Empty_List : constant List;

No_Element : constant Cursor;

function "=" (Left, Right : List) return Boolean;

function Length (Container : List) return Count_Type;

function Is_Empty (Container : List) return Boolean;

procedure Clear (Container : in out List);

function Element (Position : Cursor)
return Element_Type;

procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);

procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));

procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));

procedure Move (Target : in out List;
Source : in out List);

procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);

procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);

procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);

procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);

procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);

procedure Reverse_Elements (Container : in out List);

procedure Swap (Container : in out List;
I, J : in Cursor);

procedure Swap_Links (Container : in out List;
I, J : in Cursor);

procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);

procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);

procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);

function First (Container : List) return Cursor;

function First_Element (Container : List)
return Element_Type;

function Last (Container : List) return Cursor;

function Last_Element (Container : List)
return Element_Type;

function Next (Position : Cursor) return Cursor;

function Previous (Position : Cursor) return Cursor;

procedure Next (Position : in out Cursor);

procedure Previous (Position : in out Cursor);

function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;

function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;

function Contains (Container : List;
Item : Element_Type) return Boolean;

function Has_Element (Position : Cursor) return Boolean;

procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));

procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));

generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting is

function Is_Sorted (Container : List) return Boolean;

procedure Sort (Container : in out List);

procedure Merge (Target : in out List;
Source : in out List);

end Generic_Sorting;

private

... -- не задано языком

end Ada.Containers.Doubly_Linked_Lists;

Ожидается, что фактическая функция обобщённого формального параметра "=" для значений Element_Type определит рефлексивное и симметричное отношение и вернёт то же значение результата каждый раз, когда она вызывается с определённой парой значений. Если она работает каким-либо другим образом, функции Find, Reverse_Find и "=" для значений списка возвращают неопределённое значение. Точные аргументы и количество вызовов этой обобщённой формальной функции функциями Find, Reverse_Find и "=" для значений списка не определены.

Тип List используется для представления списков. Тип List требует финализации (см. 7.6).

Empty_List представляет собой пустой объект List. Его длина равна 0. Если объект типа List не инициализируется иначе, он инициализируется тем же значением, что и Empty_List.

No_Element представляет собой курсор, который не обозначает ни одного элемента. Если объект типа Cursor не инициализируется иначе, он инициализируется тем же значением, что и No_Element.

Предопределённый оператор "=" для типа Cursor возвращает True, если оба курсора являются No_Element или обозначают тот же элемент в том же контейнере.

Выполнение стандартной реализации атрибутов Input, Output, Read или Write для типа Cursor вызывает исключение Program_Error.

Некоторые операции этого обобщённого пакета имеют параметры доступа к подпрограммам. Для обеспечения корректной работы таких операций они предотвращают определённые действия назначенной подпрограммой. В частности, некоторые операции проверяют «вмешательство в курсоры» контейнера, поскольку они зависят от того, что набор элементов контейнера остаётся постоянным, а другие проверяют «вмешательство в элементы» контейнера, поскольку они зависят от того, что элементы контейнера не заменяются.

Подпрограмма считается вмешивающейся в курсоры объекта списка L, если:

она вставляет или удаляет элементы из L, то есть она вызывает процедуры Insert, Clear, Delete или Delete_Last с L в качестве параметра; или

она переупорядочивает элементы L, то есть она вызывает процедуры Splice, Swap_Links или Reverse_Elements, или процедуры Sort или Merge экземпляра Generic_Sorting с L в качестве параметра; или

она завершает L; или

она вызывает процедуру Move с L в качестве параметра.

Подпрограмма считается вмешивающейся в элементы объекта списка L, если:

она вмешивается в курсоры L; или

она заменяет один или несколько элементов L, то есть она вызывает процедуры Replace_Element или Swap с L в качестве параметра.

function "=" (Left, Right : List) return Boolean;

Если Left и Right обозначают один и тот же объект списка, функция возвращает True. Если у Left и Right разная длина, функция возвращает False. В противном случае она сравнивает каждый элемент в Left с соответствующим элементом в Right с использованием обобщённого формального оператора равенства. Если любое такое сравнение возвращает False, функция возвращает False; в противном случае она возвращает True. Любое исключение, возникающее во время вычисления равенства элементов, передаётся.

function Length (Container : List) return Count_Type;

Возвращает количество элементов в Container.

function Is_Empty (Container : List) return Boolean;

Равно длине (Контейнер) = 0.

процедура Clear (Контейнер : in out Список);

Удаляет все элементы из Контейнера.

функция Element (Позиция : Курсор) возвращает Тип_Элемента;

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error. В противном случае Element возвращает элемент, обозначенный Позицией.

процедура Replace_Element (Контейнер : in out Список;
Позиция : in Курсор;
Новый_Элемент : in Тип_Элемента);

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error; если Позиция не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Replace_Element присваивает значение Новый_Элемент элементу, обозначенному Позицией.

процедура Query_Element
(Позиция : in Курсор;
Обработка : not null access procedure (Элемент : in Тип_Элемента));

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error. В противном случае Query_Element вызывает Process.all с элементом, обозначенным Позицией, в качестве аргумента. Program_Error генерируется, если Process.all изменяет элементы Контейнера. Любое исключение, сгенерированное Process.all, передается дальше.

процедура Update_Element
(Контейнер : in out Список;
Позиция : in Курсор;
Обработка : not null access procedure (Элемент : in out Тип_Элемента));

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error; если Позиция не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Update_Element вызывает Process.all с элементом, обозначенным Позицией, в качестве аргумента. Program_Error генерируется, если Process.all изменяет элементы Контейнера. Любое исключение, сгенерированное Process.all, передается дальше.

Если Тип_Элемента является не ограниченным и определённым, то фактический параметр Элемент Process.all должен быть не ограниченным.

процедура Move (Целевой : in out Список;
Источник : in out Список);

Если Целевой обозначает тот же объект, что и Источник, то Move не имеет эффекта. В противном случае Move сначала вызывает Clear (Целевой). Затем узлы из Источника перемещаются в Целевой (в первоначальном порядке). Длина Целевого устанавливается равной длине Источника, а длина Источника устанавливается в 0.

процедура Insert (Контейнер : in out Список;
Перед : in Курсор;
Новый_Элемент : in Тип_Элемента;
Количество : in Тип_Счёта := 1);

Если Перед не равно Нет_Элемента и не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Insert вставляет Количество копий Новый_Элемента перед элементом, обозначенным Перед. Если Перед равно Нет_Элемента, новые элементы вставляются после последнего узла (если таковой имеется). Любое исключение, возникающее при выделении внутренней памяти, передаётся, и Контейнер не изменяется.

процедура Insert (Контейнер : in out Список;
Перед : in Курсор;
Новый_Элемент : in Тип_Элемента;
Позиция : out Курсор;
Количество : in Тип_Счёта := 1);

Если Перед не равно Нет_Элемента и не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Insert выделяет Количество копий Новый_Элемента и вставляет их перед элементом, обозначенным Перед. Если Перед равно Нет_Элемента, новые элементы вставляются после последнего элемента (если таковой имеется). Позиция указывает на первый вставленный элемент. Любое исключение, возникающее при выделении внутренней памяти, передаётся, и Контейнер не изменяется.

процедура Insert (Контейнер : in out Список;
Перед : in Курсор;
Позиция : out Курсор;
Количество : in Тип_Счёта := 1);

Если Перед не равно Нет_Элемента и не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Insert вставляет Количество новых элементов перед элементом, обозначенным Перед. Если Перед равно Нет_Элемента, новые элементы вставляются после последнего узла (если таковой имеется). Новые элементы инициализируются по умолчанию (см. 3.3.1). Любое исключение, возникающее при выделении внутренней памяти, передаётся, и Контейнер не изменяется.

процедура Prepend (Контейнер : in out Список;
Новый_Элемент : in Тип_Элемента;
Количество : in Тип_Счёта := 1);

Эквивалентно Insert (Контейнер, First (Контейнер), Новый_Элемент, Количество).

процедура Append (Контейнер : in out Список;
Новый_Элемент : in Тип_Элемента;
Количество : in Тип_Счёта := 1);

Эквивалентно Insert (Контейнер, Нет_Элемента, Новый_Элемент, Количество).

процедура Delete (Контейнер : in out Список;
Позиция : in out Курсор;
Количество : in Тип_Счёта := 1);

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error. Если Позиция не указывает на элемент в Контейнере, то генерируется Program_Error. В противном случае Delete удаляет (из Контейнера) Количество элементов, начиная с элемента, обозначенного Позицией (или все элементы, начиная с Позиции, если элементов меньше, чем Количество). Наконец, Позиция устанавливается в Нет_Элемента.

процедура Delete_First (Контейнер : in out Список;
Количество : in Тип_Счёта := 1);

Эквивалентно Delete (Контейнер, First (Контейнер), Количество).

процедура Delete_Last (Контейнер : in out Список;
Количество : in Тип_Счёта := 1);

Если Длина (Контейнер) <= Количество, то Delete_Last эквивалентно Clear (Контейнер). В противном случае удаляет последние Количество узлов из Контейнера.

процедура Reverse_Elements (Контейнер : in out Список);

Изменяет порядок элементов Контейнера на обратный.

процедура Swap (Контейнер : in out Список;
I, J : in Курсор);

Если I или J равны Нет_Элемента, то генерируется Constraint_Error. Если I или J не указывают на элемент в Контейнере, то генерируется Program_Error. В противном случае Swap меняет значения элементов, обозначенных I и J.

процедура Swap_Links (Контейнер : in out Список;
I, J : in Курсор);

Если I или J равны Нет_Элемента, то генерируется Constraint_Error. Если I или J не указывают на элемент в Контейнере, то генерируется Program_Error. В противном случае Swap_Links меняет местами узлы, обозначенные I и J.

процедура Splice (Целевой : in out Список;
Перед : in Курсор;
Источник : in out Список);

Если Перед не равно Нет_Элемента и не указывает на элемент в Целевом, то генерируется Program_Error. В противном случае, если Источник обозначает тот же объект, что и Целевой, операция не имеет эффекта. В противном случае Splice переупорядочивает элементы таким образом, что они удаляются из Источника и перемещаются в Целевой, непосредственно перед Перед. Если Перед равно Нет_Элемента, узлы Источника вставляются после последнего узла Целевого. Длина Целевого увеличивается на количество узлов в Источнике, а длина Источника устанавливается в 0.

процедура Splice (Целевой : in out Список;
Перед : in Курсор;
Источник : in out Список;
Позиция : in out Курсор);

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error. Если Перед не равно Нет_Элемента и не указывает на элемент в Целевом, то генерируется Program_Error. Если Позиция не равна Нет_Элемента и не указывает на узел в Источнике, то генерируется Program_Error. Если Источник обозначает тот же объект, что и Целевой, то нет эффекта, если Позиция равна Перед, иначе элемент, обозначенный Позицией, перемещается непосредственно перед Перед, или, если Перед равно Нет_Элемента, после последнего элемента. В обоих случаях Позиция и длина Целевого не изменяются. В противном случае элемент, обозначенный Позицией, удаляется из Источника и перемещается в Целевой, непосредственно перед Перед, или, если Перед равно Нет_Элемента, после последнего элемента Целевого. Длина Целевого увеличивается, длина Источника уменьшается, а Позиция обновляется для обозначения элемента в Целевом.

процедура Splice (Контейнер: in out Список;
Перед : in Курсор;
Позиция : in Курсор);

Если Позиция равна Нет_Элемента, то генерируется Constraint_Error. Если Перед не равно Нет_Элемента и не указывает на элемент в Контейнере, то генерируется Program_Error. Если Позиция не равна Нет_Элемента и не указывает на узел в Контейнере, то генерируется Program_Error. Если Позиция равна Перед, то нет эффекта. В противном случае элемент, обозначенный Позицией, перемещается непосредственно перед Перед, или, если Перед равно Нет_Элемента, после последнего элемента. Длина Контейнера не изменяется.

функция First (Контейнер : Список) возвращает Курсор;

Если Контейнер пуст, First возвращает значение Нет_Элемента. В противном случае возвращает курсор, который обозначает первый узел в Контейнере.

функция First_Element (Контейнер : Список) возвращает Тип_Элемента;

Эквивалентно Element (First (Контейнер)).

функция Last (Контейнер : Список) возвращает Курсор;

Если Контейнер пуст, Last возвращает значение Нет_Элемента. В противном случае возвращает курсор, который обозначает последний узел в Контейнере.

функция Last_Element (Контейнер : Список) возвращает Тип_Элемента;

Эквивалентно Element (Last (Контейнер)).

функция Next (Позиция : Курсор) возвращает Курсор;

Если Позиция равна Нет_Элемента или обозначает последний элемент контейнера, то Next возвращает значение Нет_Элемента. В противном случае возвращает курсор, который обозначает преемника элемента, обозначенного Позицией.

функция Previous (Позиция : Курсор) возвращает Курсор;

Если Position равно No_Element или обозначает первый элемент контейнера, то Previous возвращает значение No_Element. В противном случае, он возвращает курсор, обозначающий предшественника элемента, обозначенного Position.

процедура Next (Position : вход/выход Cursor);

Эквивалентно Position := Next (Position).

процедура Previous (Position : вход/выход Cursor);

Эквивалентно Position := Previous (Position).

функция Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
возвращает Cursor;

Если Position не равно No_Element и не обозначает элемент в Container, то генерируется Program_Error. Find ищет элементы в Container, равные Item (используя обобщенный формальный оператор равенства). Поиск начинается с элемента, обозначенного Position, или с первого элемента, если Position равно No_Element. Он продолжается в направлении Last (Container). Если элемент не найден, то Find возвращает No_Element. В противном случае, он возвращает курсор, обозначающий первый найденный равный элемент.

функция Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
возвращает Cursor;

Если Position не равно No_Element и не обозначает элемент в Container, то генерируется Program_Error. Find ищет элементы в Container, равные Item (используя обобщенный формальный оператор равенства). Поиск начинается с элемента, обозначенного Position, или с последнего элемента, если Position равно No_Element. Он продолжается в направлении First (Container). Если элемент не найден, то Reverse_Find возвращает No_Element. В противном случае, он возвращает курсор, обозначающий первый найденный равный элемент.

функция Contains (Container : List;
Item : Element_Type) возвращает Boolean;

Эквивалентно Find (Container, Item) /= No_Element.

функция Has_Element (Position : Cursor) возвращает Boolean;

Возвращает True, если Position обозначает элемент, и False в противном случае.

процедура Iterate
(Container : вход List;
Process : не null доступная процедура (Position : вход Cursor));

Iterate вызывает Process.all с курсором, обозначающим каждый узел в Container, начиная с первого узла и перемещая курсор согласно функции Next. Program_Error генерируется, если Process.all изменяет курсоры Container. Любое исключение, поднятое Process.all, передается дальше.

процедура Reverse_Iterate
(Container : вход List;
Process : не null доступная процедура (Position : вход Cursor));

Итерирует по узлам в Container, как и Iterate, за исключением того, что элементы просматриваются в обратном порядке, начиная с последнего узла и перемещая курсор согласно функции Previous.

Фактическая функция для обобщенного формального оператора "<" в Generic_Sorting должна возвращать одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элемента. Она должна определять строгую упорядоченность, то есть быть нерефлексивной, несимметричной и транзитивной; она не должна изменять Container. Если фактическое поведение "<" отличается, поведение подпрограмм Generic_Sorting не определено. Сколько раз подпрограммы Generic_Sorting вызывают "<" не определено.

функция Is_Sorted (Container : List) возвращает Boolean;

Возвращает True, если элементы отсортированы в порядке возрастания, как определено обобщенным формальным оператором "<"; в противном случае Is_Sorted возвращает False. Любое исключение, поднятое при вычислении "<", передается дальше.

процедура Sort (Container : вход/выход List);

Переупорядочивает узлы Container таким образом, что элементы отсортированы в порядке возрастания, как определено обобщенным формальным оператором "<". Сортировка стабильна. Любое исключение, поднятое при вычислении "<", передается дальше.

процедура Merge (Target : вход/выход List;
Source : вход/выход List);

Merge удаляет элементы из Source и вставляет их в Target; после этого Target содержит объединение элементов, которые изначально были в Source и Target; Source остается пустым. Если Target и Source изначально отсортированы в порядке возрастания, то Target упорядочен в порядке возрастания, как определено обобщенным формальным оператором "<"; в противном случае порядок элементов в Target не определен. Любое исключение, поднятое при вычислении "<", передается дальше.

Ограниченные (временно́й) ошибки

Вызов Merge в экземпляре Generic_Sorting с Source или Target, не отсортированными в порядке возрастания с использованием предоставленного обобщенного формального оператора "<", является ограниченной ошибкой. Либо Program_Error генерируется после обновления Target, как описано для Merge, либо операция выполняется как определено.

Ошибочное выполнение

Значение Cursor является недействительным, если произошло любое из следующего с момента его создания:

Список, содержащий элемент, который он обозначает, был завершен;

Список, содержащий элемент, который он обозначает, был использован в качестве Source или Target при вызове Move; или

Элемент, который он обозначает, был удален.

Результат операторов "=" или Has_Element не определен, если он вызывается с недействительным параметром курсора. Выполнение является ошибочным, если любая другая подпрограмма, объявленная в Containers.Doubly_Linked_Lists, вызывается с недействительным параметром курсора.

Требования к реализации

Память, связанная с объектом списка Doubly_Linked_List, не должна теряться при присваивании или выходе из области видимости.

Выполнение оператора присваивания для списка должно иметь эффект копирования элементов из исходного списка в целевой список.

A.18.3 Пакет Containers.Doubly_Linked_Lists

Статическая семантика

Ограниченные (временно́й) ошибки

Ошибочное выполнение

Требования к реализации

Рекомендации по реализации