Справочное руководство по Ada 2012

A.18.10 Общий пакет Containers.Multiway_Trees

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

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

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

Узел, у которого нет дочерних узлов, называется листовым узлом. Предки узла — это сам узел, его родительский узел, родитель родительского узла и так далее до узла без родителя. Аналогично, потомки узла — это сам узел, его дочерние узлы, дочерние узлы каждого дочернего узла и так далее.

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

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

Общий библиотечный пакет Containers.Multiway_Trees имеет следующую декларацию:

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

type Tree is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Tree);

type Cursor is private;
pragma Preelaborable_Initialization(Cursor);

Empty_Tree : constant Tree;

No_Element : constant Cursor;

function Has_Element (Position : Cursor) return Boolean;

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

function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) return Boolean;

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

function Is_Empty (Container : Tree) return Boolean;

function Node_Count (Container : Tree) return Count_Type;

function Subtree_Node_Count (Position : Cursor) return Count_Type;

function Depth (Position : Cursor) return Count_Type;

function Is_Root (Position : Cursor) return Boolean;

function Is_Leaf (Position : Cursor) return Boolean;

function Root (Container : Tree) return Cursor;

procedure Clear (Container : in out Tree);

function Element (Position : Cursor) return Element_Type;

procedure Replace_Element (Container : in out Tree;
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 Tree;
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;

type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;

function Constant_Reference (Container : aliased in Tree;
Position : in Cursor)
return Constant_Reference_Type;

function Reference (Container : aliased in out Tree;
Position : in Cursor)
return Reference_Type;

procedure Assign (Target : in out Tree; Source : in Tree);

function Copy (Source : Tree) return Tree;

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

procedure Delete_Leaf (Container : in out Tree;
Position : in out Cursor);

procedure Delete_Subtree (Container : in out Tree;
Position : in out Cursor);

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

function Find (Container : Tree;
Item : Element_Type)
return Cursor;

function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor;

function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor;

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

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

procedure Iterate_Subtree
(Position : in Cursor;
Process : not null access procedure (Position : in Cursor));

function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;

function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;

function Child_Count (Parent : Cursor) return Count_Type;

function Child_Depth (Parent, Child : Cursor) return Count_Type;

procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);

procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);

procedure Prepend_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Append_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

procedure Delete_Children (Container : in out Tree;
Parent : in Cursor);

procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor);

procedure Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor);

procedure Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor);

procedure Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor);

procedure Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor);

function Parent (Position : Cursor) return Cursor;

function First_Child (Parent : Cursor) return Cursor;

function First_Child_Element (Parent : Cursor) return Element_Type;

function Last_Child (Parent : Cursor) return Cursor;

function Last_Child_Element (Parent : Cursor) return Element_Type;

function Next_Sibling (Position : Cursor) return Cursor;

function Previous_Sibling (Position : Cursor) return Cursor;

procedure Next_Sibling (Position : in out Cursor);

procedure Previous_Sibling (Position : in out Cursor);

procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));

procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));

function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;

END_OF_DOCUMENT_MARKER

private
... -- не определено языком
end Ada.Containers.Multiway_Trees;

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

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

Empty_Tree представляет пустой объект Tree. Он содержит только узел корня (Node_Count (Empty_Tree) возвращает 1). Если объект типа Tree не инициализирован иначе, он инициализируется тем же значением, что и Empty_Tree.

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

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

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

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

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

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

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

она вставляет или удаляет элементы T, то есть она вызывает процедуры Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree или Copy_Subtree с T в качестве параметра; или

она переупорядочивает элементы T, то есть она вызывает процедуры Splice_Subtree или Splice_Children с T в качестве параметра; или

она завершает работу T; или

она вызывает Assign с T в качестве параметра Target; или

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

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

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

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

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

function Has_Element (Position : Cursor) return Boolean;

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

function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) return Boolean;

Если Left_Position или Right_Position равны No_Element, генерируется Constraint_Error. Если количество дочерних узлов элемента, обозначенного Left_Position, отличается от количества дочерних узлов элемента, обозначенного Right_Position, функция возвращает False. Если Left_Position обозначает корневой узел, а Right_Position — нет, функция возвращает False. Если Right_Position обозначает корневой узел, а Left_Position — нет, функция возвращает False. Если оба курсора не обозначают корневой узел, элементы сравниваются с использованием обобщенного формального оператора равенства. Если результат сравнения элементов равен False, функция возвращает False. В противном случае она вызывает Equal_Subtree для курсора, обозначающего каждый дочерний элемент элемента, обозначенного Left_Position, и курсора, обозначающего соответствующий дочерний элемент элемента, обозначенного Right_Position. Если какой-либо такой вызов возвращает False, функция возвращает False; в противном случае она возвращает True. Любое исключение, возникшее во время вычисления равенства элементов, передается.

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

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

function Node_Count (Container : Tree) return Count_Type;

Node_Count возвращает количество узлов в Container.

function Subtree_Node_Count (Position : Cursor) return Count_Type;

Если Position равно No_Element, Subtree_Node_Count возвращает 0; в противном случае Subtree_Node_Count возвращает количество узлов в поддереве, укорененном в Position.

function Is_Empty (Container : Tree) return Boolean;

Эквивалентно Node_Count (Container) = 1.

function Depth (Position : Cursor) return Count_Type;

Если Position равно No_Element, Depth возвращает 0; в противном случае Depth возвращает количество предковых узлов узла, обозначенного Position (включая сам узел).

function Is_Root (Position : Cursor) return Boolean;

Is_Root возвращает True, если Position обозначает корневой узел некоторого дерева; и False в противном случае.

function Is_Leaf (Position : Cursor) return Boolean;

Is_Leaf возвращает True, если Position обозначает узел, у которого нет дочерних узлов; и False в противном случае.

function Root (Container : Tree) return Cursor;

Root возвращает курсор, обозначающий корневой узел Container.

procedure Clear (Container : in out Tree);

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

function Element (Position : Cursor) return Element_Type;

Если Position равно No_Element, то генерируется Constraint_Error; если Position обозначает корневой узел дерева, то генерируется Program_Error. В противном случае Element возвращает элемент, обозначенный Position.

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

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

Если Position равно No_Element, то генерируется Constraint_Error; если Position обозначает корневой узел дерева, то генерируется Program_Error. В противном случае Query_Element вызывает Process.all с элементом, обозначенным Position, в качестве аргумента. Вмешательство в элементы дерева, содержащего элемент, обозначенный Position, запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, передается.

procedure Update_Element
(Container : in out Tree;
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;

type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;

Типы Constant_Reference_Type и Reference_Type требуют финализации.

Стандартная инициализация объекта типа Constant_Reference_Type или Reference_Type порождает Program_Error.

function Constant_Reference (Container : aliased in Tree;
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, существует и не завершен.

функция Reference (Container : с ссылкой на выход Tree;
Position : вход Cursor)
возвращает Reference_Type;

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

Если Position равно No_Element, то генерируется ошибка Constraint_Error; если Position не указывает на элемент в Container, то генерируется ошибка Program_Error. В противном случае Reference возвращает объект, дискриминант которого представляет собой значение доступа, указывающее на элемент, на который указывает Position. Изменение элементов Container запрещено, пока объект, возвращаемый Reference, существует и не завершен.

процедура Assign (Target : с ссылкой на выход Tree; Source : вход Tree);

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

функция Copy (Source : Tree) возвращает Tree;

Возвращает дерево с такой же структурой, что и Source, элементы которого инициализируются из соответствующих элементов Source.

процедура Move (Target : с ссылкой на выход Tree;
Source : с ссылкой на выход Tree);

Если Target обозначает тот же объект, что и Source, операция не выполняется. В противном случае Move сначала вызывает Clear (Target). Затем узлы, отличные от корневого узла в Source, перемещаются в Target (в тех же позициях). После завершения Move, Node_Count (Target) равен количеству узлов в исходном Source, а Node_Count (Source) равно 1.

процедура Delete_Leaf (Container : с ссылкой на выход Tree;
Position : с ссылкой на выход Cursor);

Если Position равно No_Element, то генерируется ошибка Constraint_Error; если Position не указывает на элемент в Container (включая корневой узел), то генерируется ошибка Program_Error. Если у элемента, на который указывает Position, есть дочерние элементы, то генерируется ошибка Constraint_Error. В противном случае Delete_Leaf удаляет (из Container) элемент, на который указывает Position. Наконец, Position устанавливается в No_Element.

процедура Delete_Subtree (Container : с ссылкой на выход Tree;
Position : с ссылкой на выход Cursor);

Если Position равно No_Element, то генерируется ошибка Constraint_Error. Если Position не указывает на элемент в Container (включая корневой узел), то генерируется ошибка Program_Error. В противном случае Delete_Subtree удаляет (из Container) поддерево, указанное Position (то есть все потомки узла, указанного Position, включая сам узел), и Position устанавливается в No_Element.

процедура Swap (Container : с ссылкой на выход Tree;
I, J : вход Cursor);

Если I или J равны No_Element, то генерируется ошибка Constraint_Error. Если I или J не указывают на элемент в Container (включая корневой узел), то генерируется ошибка Program_Error. В противном случае Swap меняет значения элементов, на которые указывают I и J.

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

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

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

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

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

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

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

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

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

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

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

Если Position равно No_Element, то генерируется ошибка Constraint_Error. В противном случае Iterate_Subtree вызывает Process.all с курсором, указывающим на каждый элемент в поддереве, укоренённом в узле, указанном Position, начиная с узла, указанного Position, и проходя в глубину. Изменение курсоров дерева, содержащего элемент, указанный Position, запрещено во время выполнения вызова Process.all. Любая исключительная ситуация, поднятая Process.all, распространяется.

функция Iterate (Container : вход Tree)
возвращает Tree_Iterator_Interfaces.Forward_Iterator'Class;

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

функция Iterate_Subtree (Position : вход Cursor)
возвращает Tree_Iterator_Interfaces.Forward_Iterator'Class;

Если Position равно No_Element, то генерируется ошибка Constraint_Error. В противном случае Iterate_Subtree возвращает объект итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающее каждый элемент в поддереве, укоренённом в узле, указанном Position, начиная с узла, указанного Position, и проходя в глубину. Если Position равно No_Element, то генерируется ошибка Constraint_Error. Изменение курсоров контейнера, содержащего узел, указанный Position, запрещено, пока существует объект итератора (в частности, в sequence_of_statements оператора loop_statement, чья iterator_specification обозначает этот объект). Объект итератора требует завершения.

функция Child_Count (Parent : Cursor) возвращает Count_Type;

Child_Count возвращает количество дочерних узлов узла, указанного Parent.

функция Child_Depth (Parent, Child : Cursor) возвращает Count_Type;

Если Child или Parent равны No_Element, то генерируется ошибка Constraint_Error. В противном случае Child_Depth возвращает количество предковых узлов Child (включая сам Child), но не включая Parent; ошибка Program_Error генерируется, если Parent не является предком Child.

процедура Insert_Child (Container : с ссылкой на выход Tree;
Parent : вход Cursor;
Before : вход Cursor;
New_Item : вход Element_Type;
Count : вход Count_Type := 1);

Если Parent равно No_Element, то генерируется ошибка Constraint_Error. Если Parent не указывает на узел в Container, то генерируется ошибка Program_Error. Если Before не равно No_Element и не указывает на узел в Container, то генерируется ошибка Program_Error. Если Before не равно No_Element и Parent не указывает на родительский узел узла, указанного Before, то генерируется ошибка Constraint_Error. В противном случае Insert_Child выделяет Count узлов, содержащих копии New_Item, и вставляет их как дочерние узлы Parent. Если у Parent уже есть дочерние узлы, новые узлы вставляются перед узлом, указанным Before, или, если Before равно No_Element, новые узлы вставляются после последнего существующего дочернего узла Parent. Любая исключительная ситуация, возникшая во время выделения внутренней памяти, распространяется, и Container не изменяется.

процедура Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);

Если Parent равно No_Element, то ошибка Constraint_Error распространяется. Если Parent не обозначает узел в Container, то распространяется ошибка Program_Error. Если Before не равно No_Element и не обозначает узел в Container, то распространяется ошибка Program_Error. Если Before не равно No_Element и Parent не обозначает родительский узел узла, обозначенного Before, то распространяется ошибка Constraint_Error. В противном случае Insert_Child выделяет Count узлов, содержащих копии New_Item, и вставляет их как дочерние узлы Parent. Если Parent уже имеет дочерние узлы, то новые узлы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, новые узлы вставляются после последнего существующего дочернего узла Parent. Position обозначает первый вставленный узел, или если Count равно 0, то Position присваивается значение Before. Любая исключительная ситуация, возникшая во время выделения внутренней памяти, распространяется, и Container не изменяется.

процедура Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);

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

процедура Prepend_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

Эквивалентно Insert_Child (Container, Parent, First_Child (Container, Parent), New_Item, Count).

процедура Append_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);

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

процедура Delete_Children (Container : in out Tree;
Parent : in Cursor);

Если Parent равно No_Element, то распространяется ошибка Constraint_Error. Если Parent не обозначает узел в Container, то распространяется ошибка Program_Error. В противном случае Delete_Children удаляет из Container всех потомков Parent, кроме самого Parent.

процедура Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor);

Если Parent равно No_Element, то распространяется ошибка Constraint_Error. Если Parent не обозначает узел в Target, то распространяется ошибка Program_Error. Если Before не равно No_Element и не обозначает узел в Target, то распространяется ошибка Program_Error. Если Before не равно No_Element и Parent не обозначает родительский узел узла, обозначенного Before, то распространяется ошибка Constraint_Error. Если Source обозначает корневой узел, то распространяется ошибка Constraint_Error. Если Source равно No_Element, то операция не имеет эффекта. В противном случае поддерево, укоренённое в Source (которое может быть из любого дерева; оно не обязательно должно быть поддеревом Target), копируется (новые узлы выделяются для создания нового поддерева с такой же структурой, как поддерево Source, причём каждый элемент инициализируется соответствующим элементом поддерева Source) и вставляется в Target как дочерний узел Parent. Если Parent уже имеет дочерние узлы, то новые узлы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, новые узлы вставляются после последнего существующего дочернего узла Parent. Родитель созданного поддерева устанавливается в Parent, а общее количество элементов в Target увеличивается на Subtree_Node_Count (Source). Любая исключительная ситуация, возникшая во время выделения внутренней памяти, распространяется, и Container не изменяется.

процедура Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor);

Если Parent равно No_Element, то Constraint_Error распространяется. Если Parent не обозначает узел в Target, то распространяется Program_Error. Если Before не равно No_Element и не обозначает узел в Target, то распространяется Program_Error. Если Before не равно No_Element и Parent не обозначает родительский узел узла, обозначенного Before, то распространяется Constraint_Error. Если Position равно No_Element, то распространяется Constraint_Error. Если Position не обозначает узел в Source или обозначает корневой узел, то распространяется Program_Error. Если Source обозначает тот же объект, что и Target, то: если Position равно Before, то никакого действия не происходит; если Position обозначает предка Parent (включая сам Parent), то распространяется Constraint_Error; в противном случае поддерево, укоренённое элементом, обозначенным Position, перемещается, чтобы стать дочерним элементом Parent. Если Parent уже имеет дочерние узлы, то перемещённые узлы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, перемещённые узлы вставляются после последнего существующего дочернего узла Parent. В каждом из этих случаев Position и счёт Target остаются неизменными, а родитель элемента, обозначенного Position, устанавливается в Parent.

В противном случае (если Source не обозначает тот же объект, что и Target), поддерево, обозначенное Position, удаляется из Source и перемещается в Target. Поддерево вставляется как дочерний элемент Parent. Если Parent уже имеет дочерние узлы, то перемещённые узлы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, перемещённые узлы вставляются после последнего существующего дочернего узла Parent. В каждом из этих случаев счёт Target увеличивается на Subtree_Node_Count (Position), а счёт Source уменьшается на Subtree_Node_Count (Position), Position обновляется для обозначения элемента в Target.

процедура Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor);

Если Parent равно No_Element, то Constraint_Error распространяется. Если Parent не обозначает узел в Container, то распространяется Program_Error. Если Before не равно No_Element и не обозначает узел в Container, то распространяется Program_Error. Если Before не равно No_Element и Parent не обозначает родительский узел узла, обозначенного Before, то распространяется Constraint_Error. Если Position равно No_Element, то распространяется Constraint_Error. Если Position не обозначает узел в Container или обозначает корневой узел, то распространяется Program_Error. Если Position равно Before, то никакого действия не происходит. Если Position обозначает предка Parent (включая сам Parent), то распространяется Constraint_Error. В противном случае поддерево, укоренённое элементом, обозначенным Position, перемещается, чтобы стать дочерним элементом Parent. Если Parent уже имеет дочерние узлы, то перемещённые узлы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, перемещённые узлы вставляются после последнего существующего дочернего узла Parent. Родитель элемента, обозначенного Position, устанавливается в Parent.

процедура Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor);

Если Target_Parent равно No_Element, то Constraint_Error распространяется. Если Target_Parent не обозначает узел в Target, то распространяется Program_Error. Если Before не равно No_Element и не обозначает элемент в Target, то распространяется Program_Error. Если Source_Parent равно No_Element, то распространяется Constraint_Error. Если Source_Parent не обозначает узел в Source, то распространяется Program_Error. Если Before не равно No_Element и Target_Parent не обозначает родительский узел узла, обозначенного Before, то распространяется Constraint_Error.

Если Source обозначает тот же объект, что и Target, то:

если Target_Parent равно Source_Parent, то никакого действия не происходит; иначе

если Source_Parent является предком Target_Parent, отличным от Target_Parent, то распространяется Constraint_Error; иначе

дочерние элементы (и дальнейшие потомки) Source_Parent перемещаются, чтобы стать дочерними элементами Target_Parent. Если Target_Parent уже имеет дочерние элементы, то перемещённые элементы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, перемещённые элементы вставляются после последнего существующего дочернего элемента Target_Parent. Родитель каждого перемещённого дочернего элемента устанавливается в Target_Parent.

В противном случае (если Source не обозначает тот же объект, что и Target), дочерние элементы (и дальнейшие потомки) Source_Parent удаляются из Source и перемещаются в Target. Дочерние элементы вставляются как дочерние элементы Target_Parent. Если Target_Parent уже имеет дочерние элементы, то перемещённые элементы вставляются перед узлом, обозначенным Before, или, если Before равно No_Element, перемещённые элементы вставляются после последнего существующего дочернего элемента Target_Parent. В каждом из этих случаев общий счёт Target увеличивается на Subtree_Node_Count (Source_Parent)-1, а общий счёт Source уменьшается на Subtree_Node_Count (Source_Parent)-1.

процедура Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor);

Если Target_Parent равно No_Element, то генерируется Constraint_Error. Если Target_Parent не указывает на узел в Container, то генерируется Program_Error. Если Before не равно No_Element и не указывает на элемент в Container, то генерируется Program_Error. Если Source_Parent равно No_Element, то генерируется Constraint_Error. Если Source_Parent не указывает на узел в Container, то генерируется Program_Error. Если Before не равно No_Element и Target_Parent не указывает на родительский узел узла, указанного Before, то генерируется Constraint_Error. Если Target_Parent равно Source_Parent, то никаких действий не выполняется. Если Source_Parent является предком Target_Parent, отличным от самого Target_Parent, то генерируется Constraint_Error. В противном случае дочерние элементы (и их потомки) Source_Parent перемещаются и становятся дочерними элементами Target_Parent. Если Target_Parent уже имеет дочерние элементы, то перемещенные элементы вставляются перед узлом, указанным Before, или, если Before равно No_Element, после последнего существующего дочернего узла Target_Parent. Родитель каждого перемещенного дочернего элемента устанавливается в Target_Parent.

function Parent (Position : Cursor) return Cursor;

Если Position равно No_Element или указывает на корневой узел, возвращается No_Element. В противном случае возвращается указатель на родительский узел узла, указанного Position.

function First_Child (Parent : Cursor) return Cursor;

Если Parent равно No_Element, то генерируется Constraint_Error. В противном случае First_Child возвращает указатель на первый дочерний узел узла, указанного Parent; если такого узла нет, возвращается No_Element.

function First_Child_Element (Parent : Cursor) return Element_Type;

Эквивалентно Element (First_Child (Parent)).

function Last_Child (Parent : Cursor) return Cursor;

Если Parent равно No_Element, то генерируется Constraint_Error. В противном случае Last_Child возвращает указатель на последний дочерний узел узла, указанного Parent; если такого узла нет, возвращается No_Element.

function Last_Child_Element (Parent : Cursor) return Element_Type;

Эквивалентно Element (Last_Child (Parent)).

function Next_Sibling (Position : Cursor) return Cursor;

Если Position равно No_Element или указывает на последний дочерний узел своего родителя, то Next_Sibling возвращает No_Element. В противном случае возвращает указатель на последующий (с тем же родителем) узел, указанный Position.

function Previous_Sibling (Position : Cursor) return Cursor;

Если Position равно No_Element или указывает на первый дочерний узел своего родителя, то Previous_Sibling возвращает No_Element. В противном случае возвращает указатель на предыдущий (с тем же родителем) узел, указанный Position.

procedure Next_Sibling (Position : in out Cursor);

Эквивалентно Position := Next_Sibling (Position);

procedure Previous_Sibling (Position : in out Cursor);

Эквивалентно Position := Previous_Sibling (Position);

procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));

Если Parent равно No_Element, то генерируется Constraint_Error.

Iterate_Children вызывает Process.all с указателем, указывающим на каждый дочерний узел Parent, начиная с первого дочернего узла и перемещая указатель в соответствии с функцией Next_Sibling.

Запрещается изменять указатели дерева, содержащего Parent, во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, передается дальше.

procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));

Если Parent равно No_Element, то генерируется Constraint_Error.

Reverse_Iterate_Children вызывает Process.all с указателем, указывающим на каждый дочерний узел Parent, начиная с последнего дочернего узла и перемещая указатель в соответствии с функцией Previous_Sibling.

function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;

Iterate_Children возвращает объект обратимого итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающее каждый дочерний узел Parent. Если Parent равно No_Element, то генерируется Constraint_Error. Если Parent не указывает на узел в Container, то генерируется Program_Error. В противном случае, при использовании в качестве прямого итератора, узлы обозначаются, начиная с первого дочернего узла и перемещая указатель по функции Next_Sibling; при использовании в качестве обратного итератора, узлы обозначаются, начиная с последнего дочернего узла и перемещая указатель по функции Previous_Sibling. Запрещается изменять указатели Container, пока существует объект итератора (в частности, в sequence_of_statements инструкции loop_statement, чья iterator_specification обозначает этот объект). Объект итератора требует завершения.

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

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

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

Ошибка выполнения

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

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

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

Дерево, содержащее элемент, указанный им, было использовано в качестве Target в вызове Assign или объектом-мишенью инструкции assignment_statement;

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

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

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

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

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

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

A.18.10 Общий пакет Containers.Multiway_Trees

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

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

Ошибка выполнения

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

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