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

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
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is

type Tree is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Tree,
Stable_Properties => (Node_Count,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Node_Count (Tree) = 1 and then
(not Tampering_With_Cursors_Prohibited (Tree)) and then
(not Tampering_With_Elements_Prohibited (Tree)),
Preelaborable_Initialization;

type Cursor is private
with Preelaborable_Initialization;

Empty_Tree : constant Tree;

No_Element : constant Cursor;

function Equal_Element (Left, Right : Element_Type)
return Boolean renames "=";

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

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

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 Tampering_With_Cursors_Prohibited
(Container : Tree) return Boolean
with Nonblocking, Global => null, Use_Formal => null;

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

function Empty return Tree
is (Empty_Tree)
with Post =>
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Node_Count (Empty'Result) = 1;

function Is_Empty (Container : Tree) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Node_Count (Container) = 1);

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

function Subtree_Node_Count (Position : Cursor) return Count_Type
with Nonblocking, Global => во всех, Use_Formal => null;

function Subtree_Node_Count (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;

function Depth (Position : Cursor) return Count_Type
with Nonblocking, Global => во всех, Use_Formal => null;

function Depth (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;

function Is_Root (Position : Cursor) return Boolean
with Nonblocking, Global => во всех, Use_Formal => null;

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

function Is_Leaf (Position : Cursor) return Boolean
with Nonblocking, Global => во всех, Use_Formal => null;

function Is_Leaf (Container : Tree; Position : Cursor)
return Boolean
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;

function Is_Ancestor_Of (Container : Tree;
Parent : Cursor;
Position : Cursor) return Boolean
with Pre => (Meaningful_For (Container, Position)
or else raise Program_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => null;

function Root (Container : Tree) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => Root'Result /= No_Element and then
not Has_Element (Container, Root'Result);

function Meaningful_For (Container : Tree; Position : Cursor)
return Boolean is
(Position = No_Element or else
Is_Root (Container, Position) or else
Has_Element (Container, Position))
with Nonblocking, Global => null, Use_Formal => null;

procedure Clear (Container : in out Tree)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Node_Count (Container) = 1;

function Element (Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Position) or else raise Program_Error),
Nonblocking, Global => во всех, Use_Formal => Element_Type;

function Element (Container : Tree;
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 Tree;
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) and then
(Has_Element (Position) or else raise Program_Error),
Global => во всех;

procedure Query_Element
(Container : in Tree;
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 Tree;
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);

тип Reference_Type (Элемент : не null доступ Element_Type) является приватным
с Implicit_Dereference => Элемент,
Nonblocking, Global => внутри синхронизированного,
Default_Initial_Condition => (бросить Program_Error);

функция Constant_Reference (Контейнер : алиасированный в Tree;
Позиция : вход Cursor)
возвращает Constant_Reference_Type
с Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Есть_Элемент (Контейнер, Позиция)
иначе бросить Program_Error),
Post => Запрет_Изменения_Указателей (Контейнер),
Nonblocking, Global => null, Use_Formal => null;

функция Reference (Контейнер : алиасированный в выход Tree;
Позиция : вход Cursor)
возвращает Reference_Type
с Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Есть_Элемент (Контейнер, Позиция)
иначе бросить Program_Error),
Post => Запрет_Изменения_Указателей (Контейнер),
Nonblocking, Global => null, Use_Formal => null;

процедура Assign (Целевая : вход выход Tree; Источник : вход Tree)
с Pre => не Запрет_Изменения_Указателей (Целевая)
иначе бросить Program_Error,
Post => Кол-во_Узлов (Источник) = Кол-во_Узлов (Целевая);

функция Copy (Источник : Tree) возвращает Tree
с Post =>
Кол-во_Узлов (Copy'Result) = Кол-во_Узлов (Источник) и затем
не Запрет_Изменения_Элементов (Copy'Result) и затем
не Запрет_Изменения_Указателей (Copy'Result);

процедура Move (Целевая : вход выход Tree;
Источник : вход выход Tree)
с Pre => (не Запрет_Изменения_Указателей (Целевая)
иначе бросить Program_Error) и затем
(не Запрет_Изменения_Указателей (Источник)
иначе бросить Program_Error),
Post => (если не Целевая'Has_Same_Storage (Источник) то
Кол-во_Узлов (Целевая) = Кол-во_Узлов (Источник'Old) и затем
Кол-во_Узлов (Источник) = 1);

процедура Delete_Leaf (Контейнер : вход выход Tree;
Позиция : вход выход Cursor)
с Pre => (не Запрет_Изменения_Указателей (Контейнер)
иначе бросить Program_Error) и затем
(Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Есть_Элемент (Контейнер, Позиция)
иначе бросить Program_Error) и затем
(Лист (Контейнер, Позиция)
иначе бросить Constraint_Error),
Post =>
Кол_во_Узлов (Контейнер)'Old = Кол_во_Узлов (Контейнер)+1 и затем
Позиция = Нет_Элемента;

процедура Delete_Subtree (Контейнер : вход выход Tree;
Позиция : вход выход Cursor)
с Pre => (не Запрет_Изменения_Указателей (Контейнер)
иначе бросить Program_Error) и затем
(Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Есть_Элемент (Контейнер, Позиция)
иначе бросить Program_Error),
Post => Кол_во_Узлов (Контейнер)'Old = Кол_во_Узлов (Контейнер) +
Кол_во_Узлов_Поддерева (Контейнер, Позиция)'Old и затем
Позиция = Нет_Элемента;

процедура Swap (Контейнер : вход выход Tree;
I, J : вход Cursor)
с Pre => (не Запрет_Изменения_Указателей (Контейнер)
иначе бросить Program_Error) и затем
(I /= Нет_Элемента или Constraint_Error) и затем
(J /= Нет_Элемента или Constraint_Error) и затем
(Есть_Элемент (Контейнер, I)
иначе бросить Program_Error) и затем
(Есть_Элемент (Контейнер, J)
иначе бросить Program_Error);

функция Find (Контейнер : Tree;
Элемент : Element_Type)
возвращает Cursor
с Post => (если Find'Result /= Нет_Элемента
то Есть_Элемент (Контейнер, Find'Result));

функция Find_In_Subtree (Позиция : Cursor;
Элемент : Element_Type)
возвращает Cursor
с Pre => Позиция /= Нет_Элемента иначе бросить Constraint_Error,
Post => (если Find_In_Subtree'Result = Нет_Элемента
то Есть_Элемент (Find_In_Subtree'Result)),
Global => во всех;

функция Find_In_Subtree (Контейнер : Tree;
Позиция : Cursor;
Элемент : Element_Type)
возвращает Cursor
с Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Позиция)
иначе бросить Program_Error),
Post => (если Find_In_Subtree'Result /= Нет_Элемента
то Есть_Элемент (Контейнер, Find_In_Subtree'Result));

функция Ancestor_Find (Позиция : Cursor;
Элемент : Element_Type)
возвращает Cursor
с Pre => Позиция /= Нет_Элемента иначе бросить Constraint_Error,
Post => (если Ancestor_Find'Result = Нет_Элемента
то Есть_Элемент (Ancestor_Find'Result)),
Global => во всех;

функция Ancestor_Find (Контейнер : Tree;
Позиция : Cursor;
Элемент : Element_Type)
возвращает Cursor
с Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Позиция)
иначе бросить Program_Error),
Post => (если Ancestor_Find'Result = Нет_Элемента
то Есть_Элемент (Контейнер, Ancestor_Find'Result));

функция Contains (Контейнер : Tree;
Элемент : Element_Type) возвращает Boolean;

процедура Iterate
(Контейнер : вход Tree;
Обработка : не null доступ процедура (Позиция : вход Cursor))
с Allows_Exit;

процедура Iterate_Subtree
(Позиция : вход Cursor;
Обработка : не null доступ процедура (Позиция : вход Cursor))
с Allows_Exit,
Pre => Позиция /= Нет_Элемента иначе бросить Constraint_Error,
Global => во всех;

процедура Iterate_Subtree
(Контейнер : вход Tree;
Позиция : вход Cursor;
Обработка : не null доступ процедура (Позиция : вход Cursor))
с Allows_Exit,
Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Позиция)
иначе бросить Program_Error);

функция Iterate (Контейнер : вход Tree)
возвращает Tree_Iterator_Interfaces.Parallel_Iterator'Class
с Post => Запрет_Изменения_Указателей (Контейнер);

функция Iterate_Subtree (Позиция : вход Cursor)
возвращает Tree_Iterator_Interfaces.Parallel_Iterator'Class
с Pre => Позиция /= Нет_Элемента иначе бросить Constraint_Error,
Global => во всех;

функция Iterate_Subtree (Контейнер : вход Tree; Позиция : вход Cursor)
возвращает Tree_Iterator_Interfaces.Parallel_Iterator'Class
с Pre => (Позиция /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Позиция)
иначе бросить Program_Error),
Post => Запрет_Изменения_Указателей (Контейнер);

функция Child_Count (Родитель : Cursor) возвращает Count_Type
с Post => (если Родитель = Нет_Элемента то Child_Count'Result = 0),
с Nonblocking, Global => во всех, Use_Formal => null;

функция Child_Count (Контейнер : Tree; Родитель : Cursor)
возвращает Count_Type
с Pre => Допустимо_Для (Контейнер, Родитель)
иначе бросить Program_Error,
Post => (если Родитель = Нет_Элемента то Child_Count'Result = 0),
Nonblocking, Global => null, Use_Formal => null;

функция Child_Depth (Родитель, Дитя : Cursor) возвращает Count_Type
с Pre => (Родитель = Нет_Элемента и Дитя = Нет_Элемента)
иначе бросить Constraint_Error,
с Nonblocking, Global => во всех, Use_Formal => null;

функция Child_Depth (Контейнер : Tree; Родитель, Дитя : Cursor)
возвращает Count_Type
с Pre => ((Родитель = Нет_Элемента и Дитя = Нет_Элемента)
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Родитель)
иначе бросить Program_Error) и затем
(Допустимо_Для (Контейнер, Дитя)
иначе бросить Program_Error),
Nonblocking, Global => null, Use_Formal => null;

процедура Insert_Child (Контейнер : вход выход Tree;
Родитель : вход Cursor;
Перед : вход Cursor;
Новый_Элемент : вход Element_Type;
Счет : вход Count_Type := 1)
с Pre => (не Запрет_Изменения_Указателей (Контейнер)
иначе бросить Program_Error) и затем
(Родитель /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Родитель)
иначе бросить Program_Error) и затем
(Допустимо_Для (Контейнер, Перед)
иначе бросить Program_Error) и затем
(Перед = Нет_Элемента или
Контейнер.Родитель (Перед) = Родитель
иначе бросить Constraint_Error),
Post => Кол_во_Узлов (Контейнер) =
Кол_во_Узлов (Контейнер)'Old + Счет;

процедура Insert_Child (Контейнер : вход выход Tree;
Родитель : вход Cursor;
Перед : вход Cursor;
Новый_Элемент : вход Element_Type;
Позиция : выход Cursor;
Счет : вход Count_Type := 1)
с Pre => (не Запрет_Изменения_Указателей (Контейнер)
иначе бросить Program_Error) и затем
(Родитель /= Нет_Элемента
иначе бросить Constraint_Error) и затем
(Допустимо_Для (Контейнер, Родитель)
иначе бросить Program_Error) и затем
(Допустимо_Для (Контейнер, Перед)
иначе бросить Program_Error) и затем
(Перед = Нет_Элемента или
Контейнер.Родитель (Перед) = Родитель
иначе бросить Constraint_Error),
Post => (Кол_во_Узлов (Контейнер) =
Кол_во_Узлов (Контейнер)'Old + Счет) и затем
Есть_Элемент (Контейнер, Позиция);

процедура Insert_Child (Container : in out Tree;
Parent : in Cursor;
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
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count) and then
Has_Element (Container, Position);

процедура Prepend_Child (Container : in out Tree;
Parent : 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
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;

процедура Append_Child (Container : in out Tree;
Parent : 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
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;

процедура Delete_Children (Container : in out Tree;
Parent : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => (Node_Count (Container) = Node_Count (Container)'Old -
Child_Count (Container, Parent)'Old) and then
Child_Count (Container, Parent) = 0;

процедура Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) =
Node_Count (Target)'Old + Subtree_Node_Count (Source),
Global => in all;

процедура Copy_Local_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(Meaningful_For (Target, Source)
or else raise Program_Error) and then
(not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Target, Source);

процедура Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Tree;
Subtree : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(Meaningful_For (Source, Subtree)
or else raise Program_Error) and then
(not Is_Root (Source, Subtree)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Source, Subtree);

процедура Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor)
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) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) /= Parent
or else raise Constraint_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Source, Position)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Position = Before or else
Is_Ancestor_Of (Target, Position, Parent)
or else raise Constraint_Error),
Post => (declare
Org_Sub_Count renames
Subtree_Node_Count (Source, Position)'Old;
Org_Target_Count renames Node_Count (Target)'Old;
begin
(if not Target'Has_Same_Storage (Source) then
Node_Count (Target) = Org_Target_Count +
Org_Sub_Count and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Sub_Count and then
Has_Element (Target, Position)
else
Target.Parent (Position) = Parent and then
Node_Count (Target) = Org_Target_Count));

процедура Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) /= Parent
or else raise Constraint_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error) and then
(Position = Before or else
Is_Ancestor_Of (Container, Position, Parent)
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old and then
Container.Parent (Position) = Parent);

процедура Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor)
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) and then
(Target_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Target_Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Source_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Source, Source_Parent)
or else raise Program_Error) and then
(Before = No_Element or else
Parent (Target, Before) /= Target_Parent
or else raise Constraint_Error) and then
(Target'Has_Same_Storage (Source) or else
Target_Parent = Source_Parent or else
Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => (declare
Org_Child_Count renames
Child_Count (Source, Source_Parent)'Old;
Org_Target_Count renames Node_Count (Target)'Old;
begin
(if not Target'Has_Same_Storage (Source) then
Node_Count (Target) = Org_Target_Count +
Org_Child_Count and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Child_Count
else
Node_Count (Target) = Org_Target_Count));

процедура Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Target_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Target_Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Source_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Source_Parent)
or else raise Program_Error) and then
(Before = No_Element or else
Parent (Container, Before) /= Target_Parent
or else raise Constraint_Error) and then
(Target_Parent = Source_Parent or else
Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => Node_Count (Container) = Node_Count (Container)'Old;

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

function Parent (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element or else
Is_Root (Container, Position)
then Parent'Result = No_Element
else Has_Element (Container, Parent'Result));

function First_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;

function First_Child (Container : Tree;
Parent : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => First_Child'Result = No_Element or else
Has_Element (Container, First_Child'Result);

function First_Child_Element (Parent : Cursor) return Element_Type
with Nonblocking, Global => in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;

function First_Child_Element (Container : Tree;
Parent : Cursor) return Element_Type
with Nonblocking, Global => null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(First_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);

function Last_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;

function Last_Child (Container : Tree;
Parent : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Last_Child'Result = No_Element or else
Has_Element (Container, Last_Child'Result);

function Last_Child_Element (Parent : Cursor) return Element_Type
with Nonblocking, Global => in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;

function Last_Child_Element (Container : Tree;
Parent : Cursor) return Element_Type
with Nonblocking, Global => null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Last_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);

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

function Next_Sibling (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Next_Sibling'Result = No_Element then
Position = No_Element or else
Is_Root (Container, Position) or else
Last_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Next_Sibling'Result));

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

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

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

function Previous_Sibling (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Previous_Sibling'Result = No_Element then
Position = No_Element or else
Is_Root (Container, Position) or else
First_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Previous_Sibling'Result));

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

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

procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element or else raise Constraint_Error,
Global => in all, Use_Formal => null;

procedure Iterate_Children
(Container : in Tree;
Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);

procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element or else raise Constraint_Error,
Global => in all, Use_Formal => null;

procedure Reverse_Iterate_Children
(Container : in Tree;
Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);

function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);

package Stable is

type Tree (Base : not null access Multiway_Trees.Tree) is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Node_Count),
Global => null,
Default_Initial_Condition => Node_Count (Tree) = 1,
Preelaborable_Initialization;

type Cursor is private
with Preelaborable_Initialization;

Empty_Tree : constant Tree;

No_Element : constant Cursor;

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

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

procedure Assign (Target : in out Multiway_Trees.Tree;
Source : in Tree)
with Post => Node_Count (Source) = Node_Count (Target);

function Copy (Source : Multiway_Trees.Tree) return Tree
with Post => Node_Count (Copy'Result) = Node_Count (Source);

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

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

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

private

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

end Stable;

private
... -- не указано языком
end Ada.Containers.Multiway_Trees;

END_OF_DOCUMENT_MARKER

Ожидается, что фактическая функция для универсальной формальной функции «=» для значений типа 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, Program_Error распространяется при финализации T, а также при вызове, передающем T в определённые операции этого пакета, как указано в предусловии такой операции. Аналогично, когда вмешательство с элементами запрещено для T, Program_Error распространяется при вызове, передающем T в определённые другие операции этого пакета, как указано в предусловии такой операции.

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

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

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

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

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

функция Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) возвращает 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. Любое исключение, сгенерированное во время вычисления равенства элементов, распространяется.

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

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

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

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

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

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

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

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

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

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

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

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

функция Subtree_Node_Count (Container : Tree; Position : Cursor)
возвращает Count_Type
с Pre => Meaningful_For (Container, Position)
или же поднимает Program_Error,
Nonblocking, Global => null, Use_Formal => null;

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

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

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

функция Depth (Container : Tree; Position : Cursor)
возвращает Count_Type
с Pre => Meaningful_For (Container, Position)
или же поднимает Program_Error,
Nonblocking, Global => null, Use_Formal => null;

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

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

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

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

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

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

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

функция Is_Leaf (Container : Tree; Position : Cursor)
возвращает Boolean
с Pre => Meaningful_For (Container, Position)
или же поднимает Program_Error,
Nonblocking, Global => null, Use_Formal => null;

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

функция Is_Ancestor_Of (Container : Tree;
Parent : Cursor;
Position : Cursor) возвращает Boolean
с Pre => (Meaningful_For (Container, Position)
или же поднимает Program_Error) и затем
(Meaningful_For (Container, Parent)
или же поднимает Program_Error),
Nonblocking, Global => null, Use_Formal => null;

Is_Ancestor_Of возвращает True, если Parent обозначает предковый узел Position (включая сам Position), и False в противном случае.

функция Root (Container : Tree) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Post => Root'Result /= No_Element и затем
не Has_Element (Container, Root'Result);

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

процедура Clear (Container : вход-выход Tree)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или же поднимает Program_Error,
Post => Node_Count (Container) = 1;

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

функция Element (Position : Курсор) возвращает Element_Type
с Pre => (Position /= Нет_Элемента или
вызвать Constraint_Error) и
(Есть_Элемент (Position) или вызвать Program_Error),
Nonblocking, Global => во всех, Use_Formal => Element_Type;

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

функция Element (Container : Дерево;
Position : Курсор) возвращает Element_Type
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;

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

процедура Replace_Element (Container : вход-выход Дерево;
Position : вход Курсор;
New_item : вход Element_Type)
с Pre => (не Запрещено_Изменять_Элементы (Container)
или вызвать Program_Error) и
(Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error);

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

процедура Query_Element
(Position : вход Курсор;
Process : не null доступная процедура (Element : вход Element_Type))
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Position)
или вызвать Program_Error),
Global => во всех;

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

процедура Query_Element
(Container : вход Дерево;
Position : вход Курсор;
Process : не null доступная процедура (Element : вход Element_Type))
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error);

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

процедура Update_Element
(Container : вход-выход Дерево;
Position : вход Курсор;
Process : не null доступная процедура
(Element : вход-выход Element_Type))
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error);

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

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

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

тип Reference_Type (Element : не null доступный Element_Type) частный
с Implicit_Dereference => Element,
Nonblocking, Global => вход-выход синхронизирован,
Default_Initial_Condition => (вызвать Program_Error);

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

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

функция Constant_Reference (Container : ссылка на Дерево;
Position : вход Курсор)
возвращает Constant_Reference_Type
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error),
Post => Запрещено_Изменять_Курсоры (Container),
Nonblocking, Global => null, Use_Formal => null;

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

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

функция Reference (Container : ссылка на вход-выход Дерево;
Position : вход Курсор)
возвращает Reference_Type
с Pre => (Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error),
Post => Запрещено_Изменять_Курсоры (Container),
Nonblocking, Global => null, Use_Formal => null;

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

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

процедура Assign (Target : вход-выход Дерево; Source : вход Дерево)
с Pre => не Запрещено_Изменять_Курсоры (Target)
или вызвать Program_Error,
Post => Количество_Узлов (Source) = Количество_Узлов (Target);

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

функция Copy (Source : Дерево) возвращает Дерево
с Post =>
Количество_Узлов (Copy'Result) = Количество_Узлов (Source) и
не Запрещено_Изменять_Элементы (Copy'Result) и
не Запрещено_Изменять_Курсоры (Copy'Result);

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

процедура Move (Target : вход-выход Дерево;
Source : вход-выход Дерево)
с Pre => (не Запрещено_Изменять_Курсоры (Target)
или вызвать Program_Error) и
(не Запрещено_Изменять_Курсоры (Source)
или вызвать Program_Error),
Post => (если не Target'Has_Same_Storage (Source) то
Количество_Узлов (Target) = Количество_Узлов (Source'Old) и
Количество_Узлов (Source) = 1);

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

процедура Delete_Leaf (Container : вход-выход Дерево;
Position : вход-выход Курсор)
с Pre => (не Запрещено_Изменять_Курсоры (Container)
или вызвать Program_Error) и
(Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error) и
(Есть_Лист (Container, Position)
или вызвать Constraint_Error),
Post =>
Количество_Узлов (Container)'Old = Количество_Узлов (Container) + 1 и
Position = Нет_Элемента;

Delete_Leaf удаляет (из Container) элемент, обозначенный Position, и Position устанавливается в Нет_Элемента.

процедура Delete_Subtree (Container : вход-выход Дерево;
Position : вход-выход Курсор)
с Pre => (не Запрещено_Изменять_Курсоры (Container)
или вызвать Program_Error) и
(Position /= Нет_Элемента
или вызвать Constraint_Error) и
(Есть_Элемент (Container, Position)
или вызвать Program_Error),
Post => Количество_Узлов (Container)'Old = Количество_Узлов (Container) +
Количество_Узлов_Поддерева (Container, Position)'Old и
Position = Нет_Элемента;

Delete_Subtree удаляет (из Container) поддерево, обозначенное Position (т.е. все потомки узла, обозначенного Position, включая сам узел), и Position устанавливается в Нет_Элемента.

процедура Swap (Container : вход-выход Дерево;
I, J : вход Курсор)
с Pre => (не Запрещено_Изменять_Курсоры (Container)
или вызвать Program_Error) и
(I /= Нет_Элемента или Constraint_Error) и
(J /= Нет_Элемента или Constraint_Error) и
(Есть_Элемент (Container, I)
или вызвать Program_Error) и
(Есть_Элемент (Container, J)
или вызвать Program_Error);

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

функция Find (Container : Дерево;
Item : Element_Type)
возвращает Курсор
с Post => (если Find'Result /= Нет_Элемента
то Есть_Элемент (Container, Find'Result));

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

function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => Position /= No_Element or else raise Constraint_Error,
Post => (if Find_In_Subtree'Result = No_Element
then Has_Element (Find_In_Subtree'Result)),
Global => in all;

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

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

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

function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => Position /= No_Element or else raise Constraint_Error,
Post => (if Ancestor_Find'Result = No_Element
then Has_Element (Container, Ancestor_Find'Result)),
Global => in all;

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

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

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

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

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

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

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

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

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

procedure Iterate_Subtree
(Container : in Tree;
Position : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error);

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

function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);

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

function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;

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

function Iterate_Subtree (Container : in Tree; Position : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);

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

function Child_Count (Parent : Cursor) return Count_Type
with Post => (if Parent = No_Element then Child_Count'Result = 0),
Nonblocking, Global => in all, Use_Formal => null;

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

function Child_Count (Container : Tree; Parent : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Parent)
or else raise Program_Error,
Post => (if Parent = No_Element then Child_Count'Result = 0),
Nonblocking, Global => null, Use_Formal => null;

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

function Child_Depth (Parent, Child : Cursor) return Count_Type
with Pre => (Parent /= No_Element and then Child /= No_Element)
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => null;

Child_Depth возвращает количество узлов-предков Child (включая сам Child), но не включая Parent; Program_Error распространяется, если Parent не является предком Child.

функция Child_Depth (Container : Tree; Parent, Child : Cursor)
возвращает Count_Type
с Pre => ((Parent /= No_Element и Child /= No_Element)
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Container, Child)
или иначе поднять Program_Error),
Nonblocking, Global => null, Use_Formal => null;

Child_Depth возвращает количество предковых узлов Child в Container (включая сам Child), но не включая Parent; Program_Error распространяется, если Parent не является предком Child.

процедура Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Container, Before)
или иначе поднять Program_Error) и
(Before = No_Element или
Container.Parent (Before) = Parent
или иначе поднять Constraint_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;

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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Container, Before)
или иначе поднять Program_Error) и
(Before = No_Element или
Container.Parent (Before) = Parent
или иначе поднять Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count) и
Has_Element (Container, Position);

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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Container, Before)
или иначе поднять Program_Error) и
(Before = No_Element или
Container.Parent (Before) = Parent
или иначе поднять Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count) и
Has_Element (Container, Position);

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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;

Эквивалентно 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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;

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

процедура Delete_Children (Container : in out Tree;
Parent : in Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Container, Parent)
или иначе поднять Program_Error),
Post => (Node_Count (Container) = Node_Count (Container)'Old -
Child_Count (Container, Parent)'Old) и
Child_Count (Container, Parent) = 0;

Delete_Children удаляет из Container всех потомков Parent, кроме самого Parent.

процедура Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Target, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Target, Before)
или иначе поднять Program_Error) и
(Before = No_Element или
Target.Parent (Before) = Parent
или иначе поднять Constraint_Error) и
(не Is_Root (Source)
или иначе поднять Constraint_Error),
Post => Node_Count (Target) =
Node_Count (Target)'Old + Subtree_Node_Count (Source),
Global => in all;

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

процедура Copy_Local_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе поднять Program_Error) и
(Parent /= No_Element
или иначе поднять Constraint_Error) и
(Meaningful_For (Target, Parent)
или иначе поднять Program_Error) и
(Meaningful_For (Target, Before)
или иначе поднять Program_Error) и
(Before = No_Element или
Target.Parent (Before) = Parent
или иначе поднять Constraint_Error) и
(Meaningful_For (Target, Source)
или иначе поднять Program_Error) и
(не Is_Root (Source)
или иначе поднять Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Target, Source);

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

процедура Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Tree;
Subtree : in Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе выбросить Program_Error) и затем
(Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Target, Parent)
или иначе выбросить Program_Error) и затем
(Meaningful_For (Target, Before)
или иначе выбросить Program_Error) и затем
(Before = No_Element или иначе
Target.Parent (Before) = Parent
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Source, Subtree)
или иначе выбросить Program_Error) и затем
(не Is_Root (Source, Subtree)
или иначе выбросить Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Source, Subtree);

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

процедура Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе выбросить Program_Error) и затем
(не Tampering_With_Cursors_Prohibited (Source)
или иначе выбросить Program_Error) и затем
(Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Target, Parent)
или иначе выбросить Program_Error) и затем
(Meaningful_For (Target, Before)
или иначе выбросить Program_Error) и затем
(Before = No_Element или иначе
Target.Parent (Before) /= Parent
или иначе выбросить Constraint_Error) и затем
(Position /= No_Element
или иначе выбросить Constraint_Error) и затем
(Has_Element (Source, Position)
или иначе выбросить Program_Error) и затем
(Target'Has_Same_Storage (Source) или иначе
Position = Before или иначе
Is_Ancestor_Of (Target, Position, Parent)
или иначе выбросить Constraint_Error),
Post => (объявить
Org_Sub_Count переименовать
Subtree_Node_Count (Source, Position)'Old;
Org_Target_Count переименовать Node_Count (Target)'Old;
начало
(если не Target'Has_Same_Storage (Source) то
Node_Count (Target) = Org_Target_Count +
Org_Sub_Count и затем
Node_Count (Source) = Node_Count (Source)'Old -
Org_Sub_Count и затем
Has_Element (Target, Position)
иначе
Target.Parent (Position) = Parent и затем
Node_Count (Target) = Org_Target_Count));

Если Source обозначает тот же объект, что и Target, то: если Position равно Before, то нет эффекта; в противном случае поддерево, укорененное элементом, обозначенным 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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе выбросить Program_Error) и затем
(Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Container, Parent)
или иначе выбросить Program_Error) и затем
(Meaningful_For (Container, Before)
или иначе выбросить Program_Error) и затем
(Before = No_Element или иначе
Container.Parent (Before) /= Parent
или иначе выбросить Constraint_Error) и затем
(Position /= No_Element
или иначе выбросить Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе выбросить Program_Error) и затем
(Position = Before или иначе
Is_Ancestor_Of (Container, Position, Parent)
или иначе выбросить Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old и затем
Container.Parent (Position) = Parent);

Если Position равно Before, то нет эффекта. В противном случае поддерево, укорененное элементом, обозначенным 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)
с Pre => (не Tampering_With_Cursors_Prohibited (Target)
или иначе выбросить Program_Error) и затем
(не Tampering_With_Cursors_Prohibited (Source)
или иначе выбросить Program_Error) и затем
(Target_Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Target, Target_Parent)
или иначе выбросить Program_Error) и затем
(Meaningful_For (Target, Before)
или иначе выбросить Program_Error) и затем
(Source_Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Source, Source_Parent)
или иначе выбросить Program_Error) и затем
(Before = No_Element или иначе
Parent (Target, Before) /= Target_Parent
или иначе выбросить Constraint_Error) и затем
(Target'Has_Same_Storage (Source) или иначе
Target_Parent = Source_Parent или иначе
Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
или иначе выбросить Constraint_Error),
Post => (объявить
Org_Child_Count переименовать
Child_Count (Source, Source_Parent)'Old;
Org_Target_Count переименовать Node_Count (Target)'Old;
начало
(если не Target'Has_Same_Storage (Source) то
Node_Count (Target) = Org_Target_Count +
Org_Child_Count и затем
Node_Count (Source) = Node_Count (Source)'Old -
Org_Child_Count
иначе
Node_Count (Target) = Org_Target_Count));

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

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

если Target_Parent равно Source_Parent, то нет эффекта; иначе

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

дочерние элементы (и последующие потомки) 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)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе выбросить Program_Error) и затем
(Target_Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Container, Target_Parent)
или иначе выбросить Program_Error) и затем
(Meaningful_For (Container, Before)
или иначе выбросить Program_Error) и затем
(Source_Parent /= No_Element
или иначе выбросить Constraint_Error) и затем
(Meaningful_For (Container, Source_Parent)
или иначе выбросить Program_Error) и затем
(Before = No_Element или иначе
Parent (Container, Before) /= Target_Parent
или иначе выбросить Constraint_Error) и затем
(Target_Parent = Source_Parent или иначе
Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
или иначе выбросить Constraint_Error),
Post => Node_Count (Container) = Node_Count (Container)'Old;

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

Возвращает указатель, обозначающий родительский узел узла, обозначенного Position.

Возвращает указатель, обозначающий родительский узел узла, обозначенного Position в Container.

function First_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;

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

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

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

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

function Last_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;

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

Last_Child возвращает указатель, обозначающий последний дочерний узел узла, обозначенного Parent в Container; если такого узла нет, возвращается No_Element.

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

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

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

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

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

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

Previous_Sibling возвращает указатель, обозначающий предшественника (с тем же родителем) узла, обозначенного Position в Container.

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

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

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

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

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

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

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

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

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

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

процедура Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element or else raise Constraint_Error,
Global => in all, Use_Formal => null;

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

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

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

процедура Reverse_Iterate_Children
(Container : in Tree;
Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);

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

функция Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);

Iterate_Children возвращает объект-итератор (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающее каждый дочерний узел Parent. При использовании в качестве итератора вперёд узлы обозначаются, начиная с первого дочернего узла и перемещая курсор по функции Next_Sibling; при использовании в качестве обратного итератора, узлы обозначаются, начиная с последнего дочернего узла и перемещая курсор по функции Previous_Sibling; при использовании как параллельного итератора, обработка всех дочерних узлов выполняется одновременно. Вмешиваться в курсоры Container запрещено, пока существует объект итератора (в частности, в последовательности_команд оператора_цикла, чья спецификация_итератора обозначает этот объект). Объект итератора нуждается в завершении.

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

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

Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited, Assign, Move, Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree, Copy_Subtree, Copy_Local_Subtree, Splice_Subtree, и Splice_Children

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

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

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

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

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

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

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

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

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

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

Дерево, содержащее элемент, обозначенный им, было использовано в качестве Цели вызова Assign или объектом назначения оператора_присваивания;

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

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

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

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

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

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

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

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

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

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

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

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