Справочник Ada 2012
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 is
pragma Preelaborate(Doubly_Linked_Lists);
pragma Remote_Types(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);
pragma Remote_Types(Doubly_Linked_Lists);
type List is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(List);
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(List);
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
pragma Preelaborable_Initialization(Cursor);
Empty_List : constant List;
No_Element : constant Cursor;
function Has_Element (Position : Cursor) return Boolean;
package List_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
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;
return Element_Type;
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
Position : in Cursor;
New_Item : in Element_Type);
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
(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));
(Container : in out List;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
with Implicit_Dereference => Element;
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type;
Position : in Cursor)
return Constant_Reference_Type;
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type;
Position : in Cursor)
return Reference_Type;
procedure Assign (Target : in out List; Source : in List);
function Copy (Source : List) return List;
procedure Move (Target : in out List;
Source : 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);
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);
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);
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);
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);
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);
Position : in out Cursor;
Count : in Count_Type := 1);
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
Count : in Count_Type := 1);
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
Count : in Count_Type := 1);
procedure Reverse_Elements (Container : in out List);
procedure Swap (Container : in out List;
I, J : in Cursor);
I, J : in Cursor);
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
I, J : in Cursor);
procedure Splice (Target : in out List;
Before : in Cursor;
Source : 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);
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
Before : in Cursor;
Position : in Cursor);
function First (Container : List) return Cursor;
function First_Element (Container : List)
return Element_Type;
return Element_Type;
function Last (Container : List) return Cursor;
function Last_Element (Container : List)
return Element_Type;
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;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Contains (Container : List;
Item : Element_Type) return Boolean;
Item : Element_Type) return Boolean;
Этот абзац был удалён.
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
(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));
(Container : in List;
Process : not null access procedure (Position : in Cursor));
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
return List_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
return List_Iterator_Interfaces.Reversible_Iterator'Class;
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting is
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);
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.
List'Write для объекта List L записывает Length(L) элементов списка в поток. Он также может записать дополнительную информацию о списке.
List'Read считывает представление списка из потока и присваивает Item список с той же длиной и элементами, что и был записан List'Write.
Некоторые операции этого универсального пакета имеют доступ к параметрам подпрограммы. Для обеспечения корректности таких операций они предотвращают определенные действия, выполняемые назначенной подпрограммой. В частности, некоторые операции проверяют наличие «вмешательства в курсоры» контейнера, поскольку они зависят от того, чтобы набор элементов контейнера оставался неизменным, а другие проверяют наличие «вмешательства в элементы» контейнера, поскольку они зависят от того, чтобы элементы контейнера не заменялись.
Подпрограмма считается вмешивающейся в курсоры объекта списка L, если:
- она вставляет или удаляет элементы L, то есть вызывает процедуры Insert, Clear, Delete или Delete_Last с L в качестве параметра; или
- она переупорядочивает элементы L, то есть вызывает процедуры Splice, Swap_Links или Reverse_Elements, или процедуры Sort или Merge экземпляра Generic_Sorting с L в качестве параметра; или
- она завершает работу L; или
- она вызывает процедуру Assign с L в качестве целевого параметра; или
- она вызывает процедуру Move с L в качестве параметра.
Подпрограмма считается вмешивающейся в элементы объекта списка L, если:
- она вмешивается в курсоры L; или
- она заменяет один или несколько элементов L, то есть вызывает процедуры Replace_Element или Swap с L в качестве параметра.
Когда вмешательство в курсоры запрещено для конкретного объекта списка L, Program_Error передается при вызове любой подпрограммы, определенной в языке, которая предназначена для вмешательства в курсоры L, оставляя L неизменным. Аналогично, когда вмешательство в элементы запрещено для конкретного объекта списка L, Program_Error передается при вызове любой подпрограммы, определенной в языке, которая предназначена для вмешательства в элементы L (или вмешательство в курсоры L), оставляя L неизменным. Эти проверки выполняются до любого другого определенного поведения тела подпрограммы, определенной в языке.
function Has_Element (Position : Cursor) return Boolean;
Возвращает True, если Position указывает на элемент, и False в противном случае.
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;
Эквивалентно Length (Container) = 0.
procedure Clear (Container : in out List);
Удаляет все элементы из Container.
function Element (Position : Cursor) return Element_Type;
Если Position равно No_Element, то Constraint_Error передаётся. В противном случае Element возвращает элемент, указанный Position.
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
Position : in Cursor;
New_Item : in Element_Type);
Если Position равно No_Element, то Constraint_Error передается; если Position не указывает на элемент в Container, то передается Program_Error. В противном случае Replace_Element присваивает значение New_Item элементу, указанному Position.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
Если Position равно No_Element, то Constraint_Error передаётся. В противном случае Query_Element вызывает Process.all с элементом, указанным Position, в качестве аргумента. Вмешательство в элементы списка, содержащего элемент, указанный Position, запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, передается.
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
Если Position равно No_Element, то Constraint_Error передаётся; если Position не указывает на элемент в Container, то передаётся Program_Error. В противном случае Update_Element вызывает Process.all с элементом, указанным Position, в качестве аргумента. Вмешательство в элементы Container запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, передаётся.
Если Element_Type не ограничено и определено, то фактический параметр Element для Process.all должен быть неограниченным.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
with Implicit_Dereference => Element;
Типы Constant_Reference_Type и Reference_Type требуют завершения работы.
Инициализация по умолчанию объекта типа Constant_Reference_Type или Reference_Type передает Program_Error.
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type;
Position : in Cursor)
return Constant_Reference_Type;
Эта функция (в сочетании с аспектами Constant_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения доступа к отдельному элементу списка, заданному курсором.
Если Position равно No_Element, то Constraint_Error передаётся; если Position не указывает на элемент в Container, то передаётся Program_Error. В противном случае Constant_Reference возвращает объект, дискриминанта которого является значением доступа, указывающим на элемент, указанный Position. Вмешательство в элементы Container запрещено, пока объект, возвращаемый Constant_Reference, существует и не завершен.
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type;
Position : in Cursor)
return Reference_Type;
Эта функция (в сочетании с аспектами Variable_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения и записи доступа к отдельному элементу списка, заданному курсором.
Если Position равно No_Element, то Constraint_Error передаётся; если Position не указывает на элемент в Container, то передаётся Program_Error. В противном случае Reference возвращает объект, дискриминанта которого является значением доступа, указывающим на элемент, указанный Position. Вмешательство в элементы Container запрещено, пока объект, возвращаемый Reference, существует и не завершен.
procedure Assign (Target : in out List; Source : in List);
Если Target обозначает тот же объект, что и Source, операция не имеет эффекта. В противном случае элементы Source копируются в Target, как и в выражение_присваивания , присваивающее Source Target.
function Copy (Source : List) return List;
Возвращает список, элементы которого соответствуют элементам Source.
procedure Move (Target : in out List;
Source : in out List);
Source : in out List);
Если Target обозначает тот же объект, что и Source, операция не имеет эффекта. В противном случае операция эквивалентна Assign (Target, Source), за которым следует Clear (Source).
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
Если Before не равно No_Element и не указывает на элемент в Container, то передаётся Program_Error. В противном случае Insert вставляет Count копий New_Item перед элементом, указанным Before. Если Before равно No_Element, новые элементы вставляются после последнего узла (если таковой имеется). Любое исключение, сгенерированное при выделении внутреннего хранилища, передаётся, и Container не изменяется.
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
Если Before не равно No_Element и не указывает на элемент в Container, то передаётся Program_Error. В противном случае Insert выделяет Count копий New_Item и вставляет их перед элементом, указанным Before. Если Before равно No_Element, новые элементы вставляются после последнего элемента (если таковой имеется). Position указывает на первый вставленный элемент, или если Count равно 0, то Position присваивается значение Before. Любое исключение, сгенерированное при выделении внутреннего хранилища, передаётся, и Container не изменяется.
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
Если Before не равно No_Element и не указывает на элемент в Container, то передаётся Program_Error. В противном случае Insert вставляет Count новых элементов перед элементом, указанным Before. Если Before равно No_Element, новые элементы вставляются после последнего узла (если таковой имеется). Новые элементы инициализируются по умолчанию (см. 3.3.1). Position указывает на первый вставленный элемент, или если Count равно 0, то Position присваивается значение Before. Любое исключение, сгенерированное при выделении внутреннего хранилища, передаётся, и Container не изменяется.
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
New_Item : in Element_Type;
Count : in Count_Type := 1);
Эквивалентно Insert (Container, First (Container), New_Item, Count).
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
New_Item : in Element_Type;
Count : in Count_Type := 1);
Эквивалентно Insert (Container, No_Element, New_Item, Count).
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
Position : in out Cursor;
Count : in Count_Type := 1);
Если Position равно No_Element, то генерируется Constraint_Error. Если Position не указывает на элемент в Container, то генерируется Program_Error. В противном случае Delete удаляет из Container Count элементов, начиная с элемента, указанного Position (или все элементы, начиная с Position, если их меньше, чем Count). В заключение, Position устанавливается в значение No_Element.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
Count : in Count_Type := 1);
Если Length (Container) <= Count, то Delete_First эквивалентен Clear (Container). В противном случае, он удаляет первые Count узлов из Container.
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
Count : in Count_Type := 1);
Если Length (Container) <= Count, то Delete_Last эквивалентен Clear (Container). В противном случае, он удаляет последние Count узлов из Container.
procedure Reverse_Elements (Container : in out List);
Изменяет порядок элементов Container в обратном порядке.
procedure Swap (Container : in out List;
I, J : in Cursor);
I, J : in Cursor);
Если I или J равны No_Element, то генерируется Constraint_Error. Если I или J не указывают на элемент в Container, то генерируется Program_Error. В противном случае Swap меняет значения элементов, указанных I и J.
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
I, J : in Cursor);
Если I или J равны No_Element, то генерируется Constraint_Error. Если I или J не указывают на элемент в Container, то генерируется Program_Error. В противном случае Swap_Links меняет узлы, указанные I и J.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
Before : in Cursor;
Source : in out List);
Если Before не равно No_Element и не указывает на элемент в Target, то генерируется Program_Error. В противном случае, если Source обозначает тот же объект, что и Target, операция не выполняется. В противном случае Splice изменяет порядок элементов, удаляя их из Source и перемещая в Target непосредственно перед Before. Если Before равно No_Element, узлы Source вставляются после последнего узла Target. Длина Target увеличивается на количество узлов в Source, а длина Source устанавливается в 0.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
Если Position равно No_Element, то генерируется Constraint_Error. Если Before не равно No_Element и не указывает на элемент в Target, то генерируется Program_Error. Если Position не равно No_Element и не указывает на узел в Source, то генерируется Program_Error. Если Source обозначает тот же объект, что и Target, то нет никакого эффекта, если Position равно Before, в противном случае элемент, указанный Position, перемещается непосредственно перед Before, или, если Before равно No_Element, после последнего элемента. В обоих случаях Position и длина Target не изменяются. В противном случае, элемент, указанный Position, удаляется из Source и перемещается в Target непосредственно перед Before, или, если Before равно No_Element, после последнего элемента Target. Длина Target увеличивается, длина Source уменьшается, и Position обновляется для обозначения элемента в Target.
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
Before : in Cursor;
Position : in Cursor);
Если Position равно No_Element, то генерируется Constraint_Error. Если Before не равно No_Element и не указывает на элемент в Container, то генерируется Program_Error. Если Position не равно No_Element и не указывает на узел в Container, то генерируется Program_Error. Если Position равно Before, то нет никакого эффекта. В противном случае, элемент, указанный Position, перемещается непосредственно перед Before, или, если Before равно No_Element, после последнего элемента. Длина Container не изменяется.
function First (Container : List) return Cursor;
Если Container пуст, First возвращает значение No_Element. В противном случае, он возвращает курсор, указывающий на первый узел в Container.
function First_Element (Container : List) return Element_Type;
Эквивалентно Element (First (Container)).
function Last (Container : List) return Cursor;
Если Container пуст, Last возвращает значение No_Element. В противном случае, он возвращает курсор, указывающий на последний узел в Container.
function Last_Element (Container : List) return Element_Type;
Эквивалентно Element (Last (Container)).
function Next (Position : Cursor) return Cursor;
Если Position равно No_Element или указывает на последний элемент контейнера, то Next возвращает значение No_Element. В противном случае, он возвращает курсор, указывающий на преемника элемента, указанного Position.
function Previous (Position : Cursor) return Cursor;
Если Position равно No_Element или указывает на первый элемент контейнера, то Previous возвращает значение No_Element. В противном случае, он возвращает курсор, указывающий на предшественника элемента, указанного Position.
procedure Next (Position : in out Cursor);
Эквивалентно Position := Next (Position).
procedure Previous (Position : in out Cursor);
Эквивалентно Position := Previous (Position).
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
Если Position не равно No_Element и не указывает на элемент в Container, то генерируется Program_Error. Find ищет элементы в Container, равные Item (используя универсальный формальный оператор равенства). Поиск начинается с элемента, указанного Position, или с первого элемента, если Position равно No_Element. Он продолжается в направлении Last (Container). Если равный элемент не найден, то Find возвращает No_Element. В противном случае, он возвращает курсор, указывающий на первый найденный равный элемент.
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
Если Position не равно No_Element и не указывает на элемент в Container, то генерируется Program_Error. Find ищет элементы в Container, равные Item (используя универсальный формальный оператор равенства). Поиск начинается с элемента, указанного Position, или с последнего элемента, если Position равно No_Element. Он продолжается в направлении First (Container). Если равный элемент не найден, то Reverse_Find возвращает No_Element. В противном случае, он возвращает курсор, указывающий на первый найденный равный элемент.
function Contains (Container : List;
Item : Element_Type) return Boolean;
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));
(Container : in List;
Process : not null access procedure (Position : in Cursor));
Iterate вызывает Process.all с курсором, который указывает на каждый узел в Container, начиная с первого узла и перемещая курсор в соответствии с функцией Next. Внесение изменений в курсоры Container запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, передается дальше.
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
(Container : in List;
Process : not null access procedure (Position : in Cursor));
Итерирует по узлам в Container, как и процедура Iterate, за исключением того, что элементы перебираются в обратном порядке, начиная с последнего узла и перемещая курсор в соответствии с функцией Previous.
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
return List_Iterator_Interfaces.Reversible_Iterator'Class;
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;
return List_Iterator_Interfaces.Reversible_Iterator'Class;
Если Start не равно No_Element и не обозначает элемент в Container, то генерируется Program_Error. Если Start равно No_Element, то генерируется Constraint_Error. В противном случае 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 функции "<" не определено.
функция Is_Sorted (Container : List) возвращает Boolean;
Возвращает True, если элементы отсортированы в порядке возрастания, как определяется обобщенным формальным оператором "<"; в противном случае Is_Sorted возвращает False. Любое исключение, сгенерированное во время вычисления "<", распространяется.
процедура Sort (Container : вход/выход List);
Переупорядочивает узлы Container таким образом, чтобы элементы были отсортированы в порядке возрастания, как определяется обобщенным формальным оператором "<". Сортировка устойчивая. Любое исключение, сгенерированное во время вычисления "<", распространяется.
процедура Merge (Target : вход/выход List;
Source : вход/выход List);
Source : вход/выход List);
Если Source пуста, Merge ничего не делает. Если Source и Target — один и тот же непустой контейнерный объект, генерируется Program_Error. В противном случае Merge удаляет элементы из Source и вставляет их в Target; после этого Target содержит объединение элементов, которые изначально находились в Source и Target; Source остается пустой. Если Target и Source изначально отсортированы в порядке возрастания, то Target упорядочивается в порядке возрастания, как определяется обобщенным формальным оператором "<"; в противном случае порядок элементов в Target не определен. Любое исключение, сгенерированное во время вычисления "<", распространяется.
Ограниченные (временно́й сложности) ошибки
Вызов Merge в экземпляре Generic_Sorting, где Source или Target не отсортированы в порядке возрастания с использованием предоставленного обобщенного формального оператора "<", является ограниченной ошибкой. Либо Program_Error генерируется после обновления Target, как описано для Merge, либо операция работает согласно определению.
Ошибка ограниченной сложности (временно́й сложности) возникает, если фактическая функция, связанная с обобщенным формальным подпрограммой, при вызове в рамках операции этого пакета, изменяет элементы любого параметра List операции. Либо генерируется Program_Error, либо операция работает согласно определению на значении List, либо до, либо после некоторых или всех изменений в List.
Обращение к любой подпрограмме, объявленной в видимой части Containers.Doubly_Linked_Lists, когда связанный контейнер был финализирован, является ошибкой. Если операция принимает Container в качестве параметра вход/выход, то она генерирует Constraint_Error или Program_Error. В противном случае операция либо выполняется так, как она бы выполнялась для пустого контейнера, либо генерирует Constraint_Error или Program_Error.
Ошибочное выполнение
Значение Cursor считается недействительным, если после его создания произошло хотя бы одно из следующих событий:
- Список, содержащий элемент, обозначенный курсором, был финализирован;
- Список, содержащий элемент, обозначенный курсором, был использован в качестве Target при вызове Assign или в качестве цели оператора присваивания assignment_statement;
- Список, содержащий элемент, обозначенный курсором, был использован в качестве Source или Target при вызове Move; или
- Элемент, обозначенный курсором, был удален из списка, который ранее содержал этот элемент.
Результат "=" или Has_Element не определен, если он вызван с недействительным параметром курсора. Выполнение является ошибочным, если любая другая подпрограмма, объявленная в Containers.Doubly_Linked_Lists, вызывается с недействительным параметром курсора.
Выполнение является ошибочным, если список, связанный с результатом вызова Reference или Constant_Reference, финализирован до финализации объекта-результата, возвращенного вызовом Reference или Constant_Reference.
Требования к реализации
Никакой памяти, связанной с объектом списка типа Doubly-linked List, не должна быть потеряна при присваивании или выходе из области видимости.
Выполнение оператора присваивания assignment_statement для списка должно иметь эффект копирования элементов из исходного списка в целевой список и изменения длины целевого объекта на длину исходного объекта.
Рекомендации по реализации
Containers.Doubly_Linked_Lists должен быть реализован аналогично связанному списку. В частности, если N — длина списка, то наихудшая временная сложность операций Element, Insert с Count=1 и Delete с Count=1 должна составлять O(log N).
Наихудшая временная сложность вызова процедуры Sort экземпляра Containers.Doubly_Linked_Lists.Generic_Sorting должна составлять O(N**2), а средняя временная сложность должна быть лучше, чем O(N**2).
Move не должен копировать элементы и должен минимизировать копирование внутренних структур данных.
Если из операции со списком распространяется исключение, никакая память не должна быть потеряна, и никакие элементы из списка не должны быть удалены, если это не предусмотрено операцией.
ПРИМЕЧАНИЯ
50 Сортировка списка никогда не копирует элементы и является устойчивой сортировкой (равные элементы сохраняют свой исходный порядок). Это отличается от сортировки массива или вектора, которая может потребовать копирования элементов и, вероятно, не является устойчивой сортировкой.
