Руководство по Ada (Ada 2022)

A.18.3 Общий пакет Containers.Doubly_Linked_Lists

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

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

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

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

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

with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is

type List is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.List,
Aggregate => (Empty => Empty,
Add_Unnamed => Append),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Length (List) = 0 and then
(not Tampering_With_Cursors_Prohibited (List)) and then
(not Tampering_With_Elements_Prohibited (List)),
Preelaborable_Initialization;

type Cursor is private
with Preelaborable_Initialization;

Empty_List : constant List;

No_Element : constant Cursor;

function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;

function Has_Element (Container : List; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;

package List_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);

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

function Tampering_With_Cursors_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;

function Tampering_With_Elements_Prohibited
(Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null;

function Empty return List
is (Empty_List)
with Post =>
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;

function Length (Container : List) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;

function Is_Empty (Container : List) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);

procedure Clear (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;

function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;

function Element (Container : List;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;

procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);

procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;

procedure Query_Element
(Container : in List;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);

procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);

type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);

type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);

function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;

function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Container, Position) or else
raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;

procedure Assign (Target : in out List; Source : in List)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);

function Copy (Source : List)
return List
with Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);

procedure Move (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);

procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container);

procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);

procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Before = No_Element or else
Has_Element (Container, Before)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - Count
or else raise Constraint_Error),
Post => Length (Container)'Old + Count = Length (Container)
and then Has_Element (Container, Position);

процедура Prepend (Container : in out Список;
New_Item : in Тип_Элемента;
Count : in Тип_Счета := 1)
с Pre => (не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы) и затем
(Длина (Container) <= Тип_Счета'Last - Count
иначе возбудить Ошибка_Ограничения),
Post => Длина (Container)'Old + Count = Длина (Container);

процедура Append (Container : in out Список;
New_Item : in Тип_Элемента;
Count : in Тип_Счета)
с Pre => (не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы) и затем
(Длина (Container) <= Тип_Счета'Last - Count
иначе возбудить Ошибка_Ограничения),
Post => Длина (Container)'Old + Count = Длина (Container);

процедура Append (Container : in out Список;
New_Item : in Тип_Элемента)
с Pre => (не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы) и затем
(Длина (Container) <= Тип_Счета'Last - 1
иначе возбудить Ошибка_Ограничения),
Post => Длина (Container)'Old + 1 = Длина (Container);

процедура Delete (Container : in out Список;
Position : in out Курсор;
Count : in Тип_Счета := 1)
с Pre => (не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы) и затем
(Position /= Нет_Элемента
иначе возбудить Ошибка_Ограничения) и затем
(Есть_Элемент (Container, Position)
иначе возбудить Ошибка_Программы),
Post => Длина (Container)'Old - Count <= Длина (Container)
и затем Position = Нет_Элемента;

процедура Delete_First (Container : in out Список;
Count : in Тип_Счета := 1)
с Pre => не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы,
Post => Длина (Container)'Old - Count <= Длина (Container);

процедура Delete_Last (Container : in out Список;
Count : in Тип_Счета := 1)
с Pre => не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы,
Post => Длина (Container)'Old - Count <= Длина (Container);

процедура Reverse_Elements (Container : in out Список)
с Pre => не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы;

процедура Swap (Container : in out Список;
I, J : in Курсор)
с Pre => (не Запрет_На_Изменение_Элементов (Container)
иначе возбудить Ошибка_Программы) и затем
(I /= Нет_Элемента или Ошибка_Ограничения) и затем
(J /= Нет_Элемента или Ошибка_Ограничения) и затем
(Есть_Элемент (Container, I)
иначе возбудить Ошибка_Программы) и затем
(Есть_Элемент (Container, J)
иначе возбудить Ошибка_Программы);

процедура Swap_Links (Container : in out Список;
I, J : in Курсор)
с Pre => (не Запрет_На_Изменение_Элементов (Container)
иначе возбудить Ошибка_Программы) и затем
(I /= Нет_Элемента или Ошибка_Ограничения) и затем
(J /= Нет_Элемента или Ошибка_Ограничения) и затем
(Есть_Элемент (Container, I)
иначе возбудить Ошибка_Программы) и затем
(Есть_Элемент (Container, J)
иначе возбудить Ошибка_Программы);

процедура Splice (Target : in out Список;
Before : in Курсор;
Source : in out Список)
с Pre => (не Запрет_На_Изменение_Курсоров (Target)
иначе возбудить Ошибка_Программы) и затем
(не Запрет_На_Изменение_Курсоров (Source)
иначе возбудить Ошибка_Программы) и затем
(Before = Нет_Элемента или
Есть_Элемент (Target, Before)
иначе возбудить Ошибка_Программы) и затем
(Target'Has_Same_Storage (Source) или
Длина (Target) <= Тип_Счета'Last - Длина (Source)
иначе возбудить Ошибка_Ограничения),
Post => (если не Target'Has_Same_Storage (Source) то
(объявить
Result_Length : константа Тип_Счета :=
Длина (Source)'Old + Длина (Target)'Old;
начать
Длина (Source) = 0 и затем
Длина (Target) = Result_Length));

процедура Splice (Target : in out Список;
Before : in Курсор;
Source : in out Список;
Position : in out Курсор)
с Pre => (не Запрет_На_Изменение_Курсоров (Target)
иначе возбудить Ошибка_Программы) и затем
(не Запрет_На_Изменение_Курсоров (Source)
иначе возбудить Ошибка_Программы) и затем
(Position /= Нет_Элемента
иначе возбудить Ошибка_Ограничения) и затем
(Есть_Элемент (Source, Position)
иначе возбудить Ошибка_Программы) и затем
(Before = Нет_Элемента или
Есть_Элемент (Target, Before)
иначе возбудить Ошибка_Программы) и затем
(Target'Has_Same_Storage (Source) или
Длина (Target) <= Тип_Счета'Last - 1
иначе возбудить Ошибка_Ограничения),
Post => (объявить
Org_Target_Length : константа Тип_Счета :=
Длина (Target)'Old;
Org_Source_Length : константа Тип_Счета :=
Длина (Source)'Old;
начать
(если Target'Has_Same_Storage (Source) то
Position = Position'Old
иначе
Длина (Source) = Org_Source_Length - 1 и затем
Длина (Target) = Org_Target_Length + 1 и затем
Есть_Элемент (Target, Position)));

процедура Splice (Container: in out Список;
Before : in Курсор;
Position : in Курсор)
с Pre => (не Запрет_На_Изменение_Курсоров (Container)
иначе возбудить Ошибка_Программы) и затем
(Position /= Нет_Элемента
иначе возбудить Ошибка_Ограничения) и затем
(Есть_Элемент (Container, Position)
иначе возбудить Ошибка_Программы) и затем
(Before = Нет_Элемента или
Есть_Элемент (Container, Before)
иначе возбудить Ошибка_Программы),
Post => Длина (Container) = Длина (Container)'Old;

функция First (Container : Список) возвращает Курсор
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container)
то Есть_Элемент (Container, First'Result)
иначе First'Result = Нет_Элемента);

функция First_Element (Container : Список)
возвращает Тип_Элемента
с Pre => (не Is_Empty (Container)
иначе возбудить Ошибка_Ограничения);

function Last (Container : List) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);

function Last_Element (Container : List)
return Element_Type
with Pre => (not Is_Empty (Container)
or else raise Constraint_Error);

function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);

function Next (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Next'Result = No_Element then
Position = Last (Container)
else Has_Element (Container, Next'Result));

function Previous (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then
Previous'Result = No_Element);

function Previous (Container : List;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));

procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;

procedure Next (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));

procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;

procedure Previous (Container : in List;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element then
Has_Element (Container, Position));

function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));

function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor
with Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Reverse_Find'Result /= No_Element
then Has_Element (Container, Reverse_Find'Result));

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

Этот абзац был удален.

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

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

функция Iterate (Container : входной List)
возвращает List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);

функция Iterate (Container : входной List; Start : входной Cursor)
возвращает List_Iterator_Interfaces.Reversible_Iterator'Class
с Pre => (Start /= No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Start)
или иначе поднять Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);

обобщенный
с функцией "<" (Left, Right : Element_Type)
возвращает Boolean is <>;
пакет Generic_Sorting
с Nonblocking, Global => null является

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

процедура Sort (Container : входной-выходной List)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error;

процедура Merge (Target : входной-выходной List;
Source : входной-выходной List)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе поднять Program_Error) и затем
(не Tampering_With_Elements_Prohibited (Source)
или иначе поднять Program_Error) и затем
(Length (Target) <= Count_Type'Last - Length (Source)
или иначе поднять Constraint_Error) и затем
((Length (Source) = 0 или иначе
не Target'Has_Same_Storage (Source))
или иначе поднять Constraint_Error),
Post => (объявить
Result_Length : постоянная Count_Type :=
Length (Source)'Old + Length (Target)'Old;
начать
(Length (Source) = 0 и затем
Length (Target) = Result_Length));

конец Generic_Sorting;

пакет Stable является

тип List (Base : не null доступ Doubly_Linked_Lists.List) является
меченый ограниченный частный
с Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global => null,
Default_Initial_Condition => Length (List) = 0,
Preelaborable_Initialization;

тип Cursor является частным
с Preelaborable_Initialization;

Empty_List : постоянная List;

No_Element : постоянная Cursor;

функция Has_Element (Position : Cursor) возвращает Boolean
с Nonblocking, Global => во всех, Use_Formal => null;

пакет List_Iterator_Interfaces является новым
Ada.Iterator_Interfaces (Cursor, Has_Element);

процедура Assign (Target : входной-выходной Doubly_Linked_Lists.List;
Source : входной List)
с Post => Length (Source) = Length (Target);

функция Copy (Source : Doubly_Linked_Lists.List) возвращает List
с Post => Length (Copy'Result) = Length (Source);

тип Constant_Reference_Type
(Element : не null доступ к константе Element_Type) является частным
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);

тип Reference_Type
(Element : не null доступ Element_Type) является частным
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);

-- Дополнительные подпрограммы, как описано в тексте
-- объявляются здесь.

частный

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

конец Stable;

частный

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

конец 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.

List'Write для объекта List L записывает Length(L) элементов списка в поток. Он также может записать дополнительную информацию о списке.

List'Read считывает представление списка из потока и присваивает Item список с той же длиной и элементами, что и записанный List'Write.

Некоторые операции проверяют «вмешательство в указатели» контейнера, так как они зависят от того, чтобы набор элементов контейнера оставался постоянным, а другие проверяют «вмешательство в элементы» контейнера, так как они зависят от того, чтобы элементы контейнера не заменялись. Когда вмешательство в указатели запрещено для конкретного объекта списка L, Program_Error передается при финализации L, а также при вызове, который передает L в определенные операции этого пакета, как указано в предусловии такой операции. Аналогично, когда вмешательство в элементы запрещено для L, Program_Error передается при вызове, который передает L в некоторые другие операции этого пакета, как указано в предусловии такой операции.

Абзацы с 62 по 69 удалены, так как теперь эти правила описаны в предусловиях.

функция Has_Element (Position : Cursor) возвращает Boolean
с Nonblocking, Global => во всех, Use_Formal => null;

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

функция Has_Element (Container : List; Position : Cursor)
возвращает Boolean
с Nonblocking, Global => null, Use_Formal => null;

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

функция "=" (Left, Right : List) возвращает Boolean;

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

функция Tampering_With_Cursors_Prohibited
(Container : List) возвращает Boolean
с Nonblocking, Global => null, Use_Formal => null;

Возвращает True, если вмешательство в указатели или вмешательство в элементы в настоящее время запрещено для Container, и False в противном случае.

функция Tampering_With_Elements_Prohibited
(Container : List) возвращает Boolean
с Nonblocking, Global => null, Use_Formal => null;

Всегда возвращает False, независимо от того, запрещено ли вмешательство в элементы.

функция Length (Container : List) возвращает Count_Type
с Nonblocking, Global => null, Use_Formal => null;

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

функция Is_Empty (Container : List) возвращает Boolean
с Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);

Возвращает True, если Container пустой.

процедура Clear (Container : входной-выходной List)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => Length (Container) = 0;

Удаляет все элементы из Container.

функция Element (Position : Cursor) возвращает Element_Type
с Pre => Position /= No_Element или иначе поднять Constraint_Error,
Nonblocking, Global => во всех, Use_Formal => Element_Type;

Element возвращает элемент, обозначенный Position.

END_OF_DOCUMENT_MARKER

Element возвращает элемент, обозначенный Position в Container.

Replace_Element присваивает значение New_Item элементу, обозначенному Position. Для определения перекрытия параметров в вызове Replace_Element, параметр Container не считается перекрывающимся ни с каким объектом (включая себя).

Query_Element вызывает Process.all со значением элемента, обозначенного Position, как аргумент. Изменение элементов списка, содержащего элемент, обозначенный Position, запрещено во время выполнения вызова Process.all. Любое исключение, поднятое Process.all, распространяется.

Query_Element вызывает Process.all со значением элемента, обозначенного Position, как аргумент. Изменение элементов Container запрещено во время выполнения вызова Process.all. Любое исключение, поднятое Process.all, распространяется.

Update_Element вызывает Process.all со значением элемента, обозначенного Position, как аргумент. Изменение элементов Container запрещено во время выполнения вызова Process.all. Любое исключение, поднятое Process.all, распространяется.

Если Element_Type не ограничен и определен, то фактический параметр Element процесса Process.all должен быть не ограничен.

Типы Constant_Reference_Type и Reference_Type нуждаются в завершении.

Этот абзац был удалён.

Эта функция (в совокупности с аспектами Constant_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения доступа к отдельному элементу списка, используя указатель.

Constant_Reference возвращает объект, дискриминант которого — это доступное значение, которое указывает на элемент, обозначенный Position. Изменение элементов Container запрещено, пока существует объект, возвращённый Constant_Reference, и он не был завершён.

Эта функция (в совокупности с аспектами Variable_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения и записи доступа к отдельному элементу списка, используя указатель.

Reference возвращает объект, дискриминант которого — это доступное значение, которое указывает на элемент, обозначенный Position. Изменение элементов Container запрещено, пока существует объект, возвращённый Reference, и он не был завершён.

Если Target обозначает тот же объект, что и Source, операция не имеет эффекта. В противном случае элементы Source копируются в Target, как при операторе присваивания Source Target.

Возвращает список, элементы которого соответствуют элементам Source.

Если Target обозначает тот же объект, что и Source, операция не имеет эффекта. В противном случае операция эквивалентна Assign (Target, Source) с последующим Clear (Source).

Insert вставляет Count копий New_Item перед элементом, обозначенным Before. Если Before равно No_Element, новые элементы вставляются после последнего узла (если таковой есть). Любое исключение, поднятое при выделении внутренней памяти, распространяется, и Container не изменяется.

Insert выделяет Count копий New_Item и вставляет их перед элементом, обозначенным Before. Если Before равно No_Element, новые элементы вставляются после последнего элемента (если таковой есть). Position обозначает первый вставленный элемент, или если Count равно 0, то Position присваивается значение Before. Любое исключение, поднятое при выделении внутренней памяти, распространяется, и Container не изменяется.

Insert вставляет Count новых элементов перед элементом, обозначенным Before. Если Before равно No_Element, новые элементы вставляются после последнего узла (если таковой есть). Новые элементы инициализируются по умолчанию (см. 3.3.1). Position обозначает первый вставленный элемент, или если Count равно 0, то Position присваивается значение Before. Любое исключение, поднятое при выделении внутренней памяти, распространяется, и Container не изменяется.

процедура Prepend (Container : in out Список;
New_Item : in Тип_Элемента;
Count : in Тип_Счётчика := 1)
with Pre => (not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы) and then
(Длина (Container) <= Тип_Счётчика'Last - Count
or else raise Ошибка_Ограничения),
Post => Длина (Container)'Old + Count = Длина (Container);

Эквивалентно Insert (Container, First (Container), New_Item, Count).

процедура Append (Container : in out Список;
New_Item : in Тип_Элемента;
Count : in Тип_Счётчика)
with Pre => (not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы) and then
(Длина (Container) <= Тип_Счётчика'Last - Count
or else raise Ошибка_Ограничения),
Post => Длина (Container)'Old + Count = Длина (Container);

Эквивалентно Insert (Container, No_Element, New_Item, Count).

процедура Append (Container : in out Список;
New_Item : in Тип_Элемента)
with Pre => (not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы) and then
(Длина (Container) <= Тип_Счётчика'Last - 1
or else raise Ошибка_Ограничения),
Post => Длина (Container)'Old + 1 = Длина (Container);

Эквивалентно Insert (Container, No_Element, New_Item, 1).

процедура Delete (Container : in out Список;
Position : in out Курсор;
Count : in Тип_Счётчика := 1)
with Pre => (not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы) and then
(Position /= No_Element
or else raise Ошибка_Ограничения) and then
(Содержит_Элемент (Container, Position)
or else raise Ошибка_Программы),
Post => Длина (Container)'Old - Count <= Длина (Container)
and then Position = No_Element;

Delete удаляет (из Container) Count элементов, начиная с элемента, обозначенного Position (или все элементы, начиная с Position, если элементов меньше, чем Count). В конце Position устанавливается в No_Element.

процедура Delete_First (Container : in out Список;
Count : in Тип_Счётчика := 1)
with Pre => not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы,
Post => Длина (Container)'Old - Count <= Длина (Container);

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

процедура Delete_Last (Container : in out Список;
Count : in Тип_Счётчика := 1)
with Pre => not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы,
Post => Длина (Container)'Old - Count <= Длина (Container);

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

процедура Reverse_Elements (Container : in out Список)
with Pre => not Запрет_На_Изменение_Курсоров (Container)
or else raise Ошибка_Программы;

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

процедура Swap (Container : in out Список;
I, J : in Курсор)
with Pre => (not Запрет_На_Изменение_Элементов (Container)
or else raise Ошибка_Программы) and then
(I /= No_Element or else Ошибка_Ограничения) and then
(J /= No_Element or else Ошибка_Ограничения) and then
(Содержит_Элемент (Container, I)
or else raise Ошибка_Программы) and then
(Содержит_Элемент (Container, J)
or else raise Ошибка_Программы);

Меняет местами значения элементов, обозначенные I и J.

процедура Swap_Links (Container : in out Список;
I, J : in Курсор)
with Pre => (not Запрет_На_Изменение_Элементов (Container)
or else raise Ошибка_Программы) and then
(I /= No_Element or else Ошибка_Ограничения) and then
(J /= No_Element or else Ошибка_Ограничения) and then
(Содержит_Элемент (Container, I)
or else raise Ошибка_Программы) and then
(Содержит_Элемент (Container, J)
or else raise Ошибка_Программы);

Swap_Links меняет узлы, обозначенные I и J.

процедура Splice (Target : вход-выход Список;
Before : вход Курсор;
Source : вход-выход Список)
с Пре => (не Запрещено_изменение_курсоров (Target)
или иначе поднять Ошибка_программы) и затем
(не Запрещено_изменение_курсоров (Source)
или иначе поднять Ошибка_программы) и затем
(Before = Нет_элемента или иначе
Есть_элемент (Target, Before)
или иначе поднять Ошибка_программы) и затем
(Target'Имеет_тот_же_хранилище (Source) или иначе
Длина (Target) <= Последний_значение_типа_счета - Длина (Source)
или иначе поднять Ошибка_ограничения),
Post => (если не Target'Имеет_тот_же_хранилище (Source) то
(объявить
Result_Length : константа Тип_счёта :=
Длина (Source)'Старое + Длина (Target)'Старое;
начало
Длина (Source) = 0 и затем
Длина (Target) = Result_Length));

Если Source обозначает тот же объект, что и Target, операция не оказывает никакого влияния. В противном случае Splice упорядочивает элементы таким образом, чтобы они были удалены из Source и перемещены в Target, непосредственно перед Before. Если Before равно Нет_элемента, узлы Source вставляются после последнего узла Target.

процедура Splice (Target : вход-выход Список;
Before : вход Курсор;
Source : вход-выход Список;
Position : вход-выход Курсор)
с Пре => (не Запрещено_изменение_курсоров (Target)
или иначе поднять Ошибка_программы) и затем
(не Запрещено_изменение_курсоров (Source)
или иначе поднять Ошибка_программы) и затем
(Position /= Нет_элемента
или иначе поднять Ошибка_ограничения) и затем
(Есть_элемент (Source, Position)
или иначе поднять Ошибка_программы) и затем
(Before = Нет_элемента или иначе
Есть_элемент (Target, Before)
или иначе поднять Ошибка_программы) и затем
(Target'Имеет_тот_же_хранилище (Source) или иначе
Длина (Target) <= Последнее_значение_типа_счёта - 1
или иначе поднять Ошибка_ограничения),
Post => (объявить
Org_Target_Length : константа Тип_счёта :=
Длина (Target)'Старое;
Org_Source_Length : константа Тип_счёта :=
Длина (Source)'Старое;
начало
(если Target'Имеет_тот_же_хранилище (Source) то
Position = Position'Старое
иначе Длина (Source) = Org_Source_Length - 1 и затем
Длина (Target) = Org_Target_Length + 1 и затем
Есть_элемент (Target, Position)));

Если Source обозначает тот же объект, что и Target, то нет эффекта, если Position равно Before, иначе элемент, обозначенный Position, перемещается непосредственно перед Before, или, если Before равно Нет_элемента, после последнего элемента. В противном случае элемент, обозначенный Position, удаляется из Source и перемещается в Target, непосредственно перед Before, или, если Before равно Нет_элемента, после последнего элемента Target. Position обновляется, чтобы обозначить элемент в Target.

процедура Splice (Container: вход-выход Список;
Before : вход Курсор;
Position : вход Курсор)
с Пре => (не Запрещено_изменение_курсоров (Container)
или иначе поднять Ошибка_программы) и затем
(Position /= Нет_элемента
или иначе поднять Ошибка_ограничения) и затем
(Есть_элемент (Container, Position)
или иначе поднять Ошибка_программы) и затем
(Before = Нет_элемента или иначе
Есть_элемент (Container, Before)
или иначе поднять Ошибка_программы),
Post => Длина (Container) = Длина (Container)'Старое;

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

функция First (Container : Список) возвращает Курсор
с Неблокируемый, Глобально => null, Использовать_формальный => null,
Post => (если не Есть_пустой (Container)
то Есть_элемент (Container, First'Результат)
иначе First'Результат = Нет_элемента);

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

функция Первый_элемент (Container : Список)
возвращает Тип_элемента
с Пре => (не Есть_пустой (Container)
или иначе поднять Ошибка_ограничения);

Эквивалентно Элементу (Container, Первый_индекс (Container)).

функция Last (Container : Список) возвращает Курсор
с Неблокируемый, Глобально => null, Использовать_формальный => null,
Post => (если не Есть_пустой (Container)
то Есть_элемент (Container, Last'Результат)
иначе Last'Результат = Нет_элемента);

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

функция Последний_элемент (Container : Список)
возвращает Тип_элемента
с Пре => (не Есть_пустой (Container)
или иначе поднять Ошибка_ограничения);

Эквивалентно Элементу (Last (Container)).

функция Next (Position : Курсор) возвращает Курсор
с Неблокируемый, Глобально => во всех, Использовать_формальный => null,
Post => (если Position = Нет_элемента то Next'Результат = Нет_элемента);

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

Возвращает курсор, указывающий на элемент, следующий за элементом, указанным в Position в Container.

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

Возвращает курсор, указывающий на предшествующий элемент, указанный в Position в Container, если таковой имеется.

procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;

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

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

procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;

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

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

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

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

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

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

Абзацы 139 и 140 были перемещены выше.

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

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

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

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

function Iterate (Container : in List)
return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);

Iterate возвращает объект-итератор (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2) , обозначающее каждый узел в Container, начиная с первого узла и перемещая курсор в соответствии с функцией Next при использовании как прямом итераторе, и начиная с последнего узла и перемещая курсор в соответствии с функцией Previous при использовании обратного итератора, и обрабатывая все узлы параллельно, когда используется параллельный итератор. Изменение курсоров Container запрещено, пока существует объект итератора (в частности, в sequence_of_statements loop_statement, у которого iterator_specification обозначает этот объект). Объекту итератора необходимо завершение.

function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);

Iterate возвращает объект обратимого итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2) , обозначающее каждый узел в Container, начиная с узла, указанного Start, и перемещая курсор в соответствии с функцией Next при использовании как прямом итераторе или перемещая курсор в соответствии с функцией Previous при использовании обратного итератора. Изменение курсоров Container запрещено, пока существует объект итератора (в частности, в sequence_of_statements loop_statement, у которого iterator_specification обозначает этот объект). Объекту итератора необходимо завершение.

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

function Is_Sorted (Container : List) return Boolean;

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

procedure Sort (Container : in out List)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error;

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

procedure Merge (Target : in out List;
Source : in out List)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Elements_Prohibited (Source)
or else raise Program_Error) and then
(Length (Target) <= Count_Type'Last - Length (Source)
or else raise Constraint_Error) and then
((Length (Source) = 0 or else
not Target'Has_Same_Storage (Source))
or else raise Constraint_Error),
Post => (declare
Result_Length : constant Count_Type :=
Length (Source)'Old + Length (Target)'Old;
begin
(Length (Source) = 0 and then
Length (Target) = Result_Length));

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

Вложенный пакет Doubly_Linked_Lists.Stable предоставляет тип Stable.List, представляющий собой стабильный список, который не может увеличиваться и уменьшаться. Такой список можно создать, вызвав функцию Copy или установив стабилизированный вид обычного списка.

Подпрограммы пакета Containers.Doubly_Linked_Lists, имеющие параметр или результат типа List, включаются во вложенный пакет Stable с той же спецификацией, за исключением следующих пунктов:

Запрещено_изменение_курсоров, Запрещено_изменение_элементов, Присвоить, Переместить, Вставить, Добавить, Добавить_в_начало, Очистить, Удалить, Удалить_первый, Удалить_последний, Разрезать, Поменять_ссылки, и Перевернуть_элементы

Операции этого пакета эквивалентны операциям для обычных списков, за исключением того, что вызовы Tampering_With_Cursors_Prohibited и Tampering_With_Elements_Prohibited, которые встречаются в предусловиях, заменяются на False, а любые, которые встречаются в постусловиях, заменяются на True.

Если стабильный список объявлен с дискриминантом Base, обозначающим существующий обычный список, то стабильный список представляет стабилизированный вид базового обычного списка, и любая операция со стабильным списком отражается на базовом обычном списке. Пока существует стабилизированный вид, любая операция, изменяющая элементы, выполняемая на базовом списке, запрещена. Закрытие стабильного списка, предоставляющего такой вид, снимает это ограничение на базовый обычный список (хотя может существовать другое ограничение из-за других одновременных итераций или стабилизированных видов).

Если стабильный список объявляется без указания Base, то объект обязательно инициализируется. Инициализирующее выражение стабильного списка, обычно вызов Copy, определяет Длину списка. Длина стабильного списка никогда не меняется после инициализации.

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

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

Ошибка в том, что фактическая функция, связанная с обобщенной подпрограммой, при вызове в качестве части операции этого пакета, изменяет элементы любого параметра List операции. Либо возникает Program_Error, либо операция работает как определено на значении List до, или после, некоторых или всех модификаций List.

Вызов любой подпрограммы, объявленной в видимой части Containers.Doubly_Linked_Lists, когда связанный контейнер завершен, является ограниченной ошибкой. Если операция принимает Container в качестве параметра in out, то она вызывает Constraint_Error или Program_Error. В противном случае операция либо выполняется так, как это делается для пустого контейнера, либо вызывает Constraint_Error или Program_Error.

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

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

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

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

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

Элемент, который он обозначает, был удален из списка, который ранее содержал этот элемент.

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

Выполнение является ошибочным, если список, связанный с результатом вызова Reference или Constant_Reference, завершен до завершения объекта-результата, возвращенного вызовом Reference или Constant_Reference.

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

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

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

A.18.3 Общий пакет Containers.Doubly_Linked_Lists

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

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

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

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

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