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

A.18.9 Общий пакет Containers.Ordered_Sets

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

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

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

function Equivalent_Elements (Left, Right : Element_Type) return Boolean;

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

type Cursor is private;
pragma Preelaborable_Initialization(Cursor);

Empty_Set : constant Set;

No_Element : constant Cursor;

function Has_Element (Position : Cursor) return Boolean;

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

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

function Equivalent_Sets (Left, Right : Set) return Boolean;

function To_Set (New_Item : Element_Type) return Set;

function Length (Container : Set) return Count_Type;

function Is_Empty (Container : Set) return Boolean;

procedure Clear (Container : in out Set);

function Element (Position : Cursor) return Element_Type;

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

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

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

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

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

function Copy (Source : Set) return Set;

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

procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);

procedure Insert (Container : in out Set;
New_Item : in Element_Type);

procedure Include (Container : in out Set;
New_Item : in Element_Type);

procedure Replace (Container : in out Set;
New_Item : in Element_Type);

procedure Exclude (Container : in out Set;
Item : in Element_Type);

procedure Delete (Container : in out Set;
Item : in Element_Type);

procedure Delete (Container : in out Set;
Position : in out Cursor);

procedure Delete_First (Container : in out Set);

procedure Delete_Last (Container : in out Set);

procedure Union (Target : in out Set;
Source : in Set);

function Union (Left, Right : Set) return Set;

function "or" (Left, Right : Set) return Set renames Union;

procedure Intersection (Target : in out Set;
Source : in Set);

function Intersection (Left, Right : Set) return Set;

function "and" (Left, Right : Set) return Set renames Intersection;

procedure Difference (Target : in out Set;
Source : in Set);

function Difference (Left, Right : Set) return Set;

function "-" (Left, Right : Set) return Set renames Difference;

procedure Symmetric_Difference (Target : in out Set;
Source : in Set);

function Symmetric_Difference (Left, Right : Set) return Set;

function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;

function Overlap (Left, Right : Set) return Boolean;

function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;

function First (Container : Set) return Cursor;

function First_Element (Container : Set) return Element_Type;

function Last (Container : Set) return Cursor;

function Last_Element (Container : Set) return Element_Type;

function Next (Position : Cursor) return Cursor;

procedure Next (Position : in out Cursor);

function Previous (Position : Cursor) return Cursor;

procedure Previous (Position : in out Cursor);

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

function Floor (Container : Set;
Item : Element_Type)
return Cursor;

function Ceiling (Container : Set;
Item : Element_Type)
return Cursor;

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

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

function "<" (Left, Right : Cursor) return Boolean;

function ">" (Left, Right : Cursor) return Boolean;

function "<" (Left : Cursor; Right : Element_Type)
return Boolean;

function ">" (Left : Cursor; Right : Element_Type)
return Boolean;

function "<" (Left : Element_Type; Right : Cursor)
return Boolean;

function ">" (Left : Element_Type; Right : Cursor)
return Boolean;

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

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

function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Reversible_Iterator'Class;

function Iterate (Container : in Set; Start : in Cursor)
return Set_Iterator_Interfaces.Reversible_Iterator'Class;

generic
type Key_Type (<>) is private;
with function Key (Element : Element_Type) return Key_Type;
with function "<" (Left, Right : Key_Type)
return Boolean is <>;
package Generic_Keys is

function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;

function Key (Position : Cursor) return Key_Type;

function Element (Container : Set;
Key : Key_Type)
return Element_Type;

procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);

procedure Exclude (Container : in out Set;
Key : in Key_Type);

procedure Delete (Container : in out Set;
Key : in Key_Type);

function Find (Container : Set;
Key : Key_Type)
return Cursor;

function Floor (Container : Set;
Key : Key_Type)
return Cursor;

function Ceiling (Container : Set;
Key : Key_Type)
return Cursor;

function Contains (Container : Set;
Key : Key_Type) return Boolean;

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

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

function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;

function Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
return Constant_Reference_Type;

function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;

end Generic_Keys;

private

... -- не определено языком

end Ada.Containers.Ordered_Sets;

Два элемента E1 и E2 считаются эквивалентными, если оба E1 < E2 и E2 < E1 возвращают False, используя общий формальный оператор «<» для элементов. Функция Equivalent_Elements возвращает True, если Left и Right эквивалентны, и False в противном случае.

END_OF_DOCUMENT_MARKER

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

Если фактическая функция для универсальной формальной функции «=» возвращает True для любой пары неэквивалентных элементов, то поведение функции контейнера «=» не определено.

Если значение элемента, хранящегося в множестве, изменяется иначе, чем операцией в этом пакете, так, что по крайней мере одно из «<» или «=» дает разные результаты, поведение этого пакета не определено.

Первый элемент непустого множества — это элемент, который меньше всех других элементов в множестве. Последний элемент непустого множества — это элемент, который больше всех других элементов в множестве. Преемник элемента — это наименьший элемент, который больше данного элемента. Предшественник элемента — это наибольший элемент, который меньше данного элемента. Все сравнения выполняются с использованием универсального формального оператора «<» для элементов.

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

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

процедура Delete_First (Container : in out Set);

Если Container пуст, Delete_First не оказывает никакого влияния. В противном случае, элемент, обозначенный First (Container), удаляется из Container. Delete_First изменяет курсоры Container.

процедура Delete_Last (Container : in out Set);

Если Container пуст, Delete_Last не оказывает никакого влияния. В противном случае, элемент, обозначенный Last (Container), удаляется из Container. Delete_Last изменяет курсоры Container.

функция First_Element (Container : Set) возвращает Element_Type;

Эквивалентно Element (First (Container)).

функция Last (Container : Set) возвращает Cursor;

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

функция Last_Element (Container : Set) возвращает Element_Type;

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

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

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

процедура Previous (Position : in out Cursor);

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

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

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

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

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

функция «<» (Left, Right : Cursor) возвращает Boolean;

Эквивалентно Element (Left) < Element (Right).

функция «>» (Left, Right : Cursor) возвращает Boolean;

Эквивалентно Element (Right) < Element (Left).

функция «<» (Left : Cursor; Right : Element_Type) возвращает Boolean;

Эквивалентно Element (Left) < Right.

функция «>» (Left : Cursor; Right : Element_Type) возвращает Boolean;

Эквивалентно Right < Element (Left).

функция «<» (Left : Element_Type; Right : Cursor) возвращает Boolean;

Эквивалентно Left < Element (Right).

функция «>» (Left : Element_Type; Right : Cursor) возвращает Boolean;

Эквивалентно Element (Right) < Left.

процедура Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));

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

функция Iterate (Container : in Set)
возвращает Set_Iterator_Interfaces.Reversible_Iterator'Class;

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

функция Iterate (Container : in Set; Start : in Cursor)
возвращает Set_Iterator_Interfaces.Reversible_Iterator'Class;

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

Для любых двух элементов E1 и E2 ожидается, что булевы значения (E1 < E2) и (Key(E1) < Key(E2)) будут равны. Если фактические значения для Key или Generic_Keys."<" ведут себя иначе, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Key и Generic_Keys."<", и сколько раз функции вызываются, не определено.

В дополнение к семантике, описанной в A.18.7, подпрограммы в пакете Generic_Keys с именами Floor и Ceiling эквивалентны соответствующим подпрограммам в родительском пакете, за исключением того, что параметр подпрограммы Key сравнивается с элементами в контейнере с использованием универсальных формальных функций Key и «<». Функция с именем Equivalent_Keys в пакете Generic_Keys возвращает True, если оба Left < Right и Right < Left возвращают False с использованием универсального формального оператора «<», и возвращает True в противном случае.

A.18.9 Общий пакет Containers.Ordered_Sets

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

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