Руководство по Ada (Ada 2022)
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
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
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
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
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,
Iterator_View => Stable.Set,
Aggregate => (Empty => Empty,
Add_Unnamed => Include),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited),
Default_Initial_Condition =>
Length (Set) = 0 and then
(not Tampering_With_Cursors_Prohibited (Set)),
Preelaborable_Initialization;
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Set,
Aggregate => (Empty => Empty,
Add_Unnamed => Include),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited),
Default_Initial_Condition =>
Length (Set) = 0 and then
(not Tampering_With_Cursors_Prohibited (Set)),
Preelaborable_Initialization;
type Cursor is private
with Preelaborable_Initialization;
with Preelaborable_Initialization;
Empty_Set : constant Set;
No_Element : constant Cursor;
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
with Nonblocking, Global => in all, Use_Formal => null;
function Has_Element (Container : Set; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
package Set_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Set) return Boolean;
function Equivalent_Sets (Left, Right : Set) return Boolean;
function Tampering_With_Cursors_Prohibited
(Container : Set) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
(Container : Set) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
function Empty return Set
is (Empty_Set)
with Post =>
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
is (Empty_Set)
with Post =>
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
function To_Set (New_Item : Element_Type) return Set
with Post => Length (To_Set'Result) = 1 and then
not Tampering_with_Cursors_Prohibited (To_Set'Result);
with Post => Length (To_Set'Result) = 1 and then
not Tampering_with_Cursors_Prohibited (To_Set'Result);
function Length (Container : Set) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
with Nonblocking, Global => null, Use_Formal => null;
function Is_Empty (Container : Set) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
procedure Clear (Container : in out Set)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
function Element (Container : Set;
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;
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 Set;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Cursors_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);
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global => in all;
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global => in all;
procedure Query_Element
(Container : in Set;
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);
(Container : in Set;
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);
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);
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
procedure Assign (Target : in out Set; Source : in Set)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
function Copy (Source : Set) return Set
with Post => Length (Copy'Result) = Length (Source) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
with Post => Length (Copy'Result) = Length (Source) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
procedure Move (Target : in out Set;
Source : in out Set)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);
Source : in out Set)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position) and then
(if Inserted then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position) and then
(if Inserted then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
procedure Insert (Container : in out Set;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container) = Length (Container)'Old + 1;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container) = Length (Container)'Old + 1;
procedure Include (Container : in out Set;
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length | Original_Length + 1);
New_Item : in Element_Type)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length | Original_Length + 1);
procedure Replace (Container : in out Set;
New_Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old;
New_Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old;
procedure Exclude (Container : in out Set;
Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length - 1 | Original_Length);
Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length - 1 | Original_Length);
procedure Delete (Container : in out Set;
Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
procedure Delete (Container : in out Set;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_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),
Post => Length (Container) = Length (Container)'Old - 1 and then
Position = No_Element;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_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),
Post => Length (Container) = Length (Container)'Old - 1 and then
Position = No_Element;
procedure Delete_First (Container : in out Set)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
(if Original_Length = 0 then Length (Container) = 0
else Length (Container) = Original_Length - 1));
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
(if Original_Length = 0 then Length (Container) = 0
else Length (Container) = Original_Length - 1));
procedure Delete_Last (Container : in out Set)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
(if Original_Length = 0 then Length (Container) = 0
else Length (Container) = Original_Length - 1));
END_OF_DOCUMENT_MARKER with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
(if Original_Length = 0 then Length (Container) = 0
else Length (Container) = Original_Length - 1));
процедура Union (Target : in out Set;
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
функция Union (Left, Right : Set) возвращает Set
с Post => Length (Union'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Union'Result);
с Post => Length (Union'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Union'Result);
функция "или" (Left, Right : Set) возвращает Set переименовывает Union;
процедура Intersection (Target : in out Set;
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
функция Intersection (Left, Right : Set) возвращает Set
с Post =>
Length (Intersection'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Intersection'Result);
с Post =>
Length (Intersection'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Intersection'Result);
функция "и" (Left, Right : Set) возвращает Set переименовывает Intersection;
процедура Difference (Target : in out Set;
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
функция Difference (Left, Right : Set) возвращает Set
с Post =>
Length (Difference'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Difference'Result);
с Post =>
Length (Difference'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (Difference'Result);
функция "-" (Left, Right : Set) возвращает Set переименовывает Difference;
процедура Symmetric_Difference (Target : in out Set;
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
Source : in Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе выдать Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
функция Symmetric_Difference (Left, Right : Set) возвращает Set
с Post =>
Length (Symmetric_Difference'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (
Symmetric_Difference'Result);
с Post =>
Length (Symmetric_Difference'Result) <=
Length (Left) + Length (Right) и затем
не Tampering_With_Cursors_Prohibited (
Symmetric_Difference'Result);
функция "xor" (Left, Right : Set) возвращает Set переименовывает
Symmetric_Difference;
Symmetric_Difference;
функция Overlap (Left, Right : Set) возвращает Boolean;
функция Is_Subset (Subset : Set;
Of_Set : Set) возвращает Boolean;
Of_Set : Set) возвращает Boolean;
функция First (Container : Set) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container)
то Has_Element (Container, First'Result)
иначе First'Result = No_Element);
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container)
то Has_Element (Container, First'Result)
иначе First'Result = No_Element);
функция First_Element (Container : Set)
возвращает Element_Type
с Pre => (не Is_Empty (Container)
или иначе выдать Constraint_Error);
возвращает Element_Type
с Pre => (не Is_Empty (Container)
или иначе выдать Constraint_Error);
функция Last (Container : Set) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container) то
Has_Element (Container, Last'Result)
иначе Last'Result = No_Element);
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container) то
Has_Element (Container, Last'Result)
иначе Last'Result = No_Element);
функция Last_Element (Container : Set)
возвращает Element_Type
с Pre => (не Is_Empty (Container)
или иначе выдать Constraint_Error);
возвращает Element_Type
с Pre => (не Is_Empty (Container)
или иначе выдать Constraint_Error);
функция Next (Position : Cursor) возвращает Cursor
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то Next'Result = No_Element);
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то Next'Result = No_Element);
функция Next (Container : Set;
Position : Cursor) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position = No_Element то Next'Result = No_Element
в противном случае Next'Result = No_Element то
Position = Last (Container)
иначе Has_Element (Container, Next'Result));
Position : Cursor) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position = No_Element то Next'Result = No_Element
в противном случае Next'Result = No_Element то
Position = Last (Container)
иначе Has_Element (Container, Next'Result));
процедура Next (Position : in out Cursor)
с Nonblocking, Global => in all, Use_Formal => null;
с Nonblocking, Global => in all, Use_Formal => null;
процедура Next (Container : in Set;
Position : in out Cursor)
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position <> No_Element
то Has_Element (Container, Position));
Position : in out Cursor)
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position <> No_Element
то Has_Element (Container, Position));
функция Previous (Position : Cursor) возвращает Cursor
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то
Previous'Result = No_Element);
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то
Previous'Result = No_Element);
функция Previous (Container : Set;
Position : Cursor) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position = No_Element то
Previous'Result = No_Element
в противном случае Previous'Result = No_Element то
Position = First (Container)
иначе Has_Element (Container, Previous'Result));
Position : Cursor) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position = No_Element то
Previous'Result = No_Element
в противном случае Previous'Result = No_Element то
Position = First (Container)
иначе Has_Element (Container, Previous'Result));
процедура Previous (Position : in out Cursor)
с Nonblocking, Global => in all,
Use_Formal => null;
с Nonblocking, Global => in all,
Use_Formal => null;
процедура Previous (Container : in Set;
Position : in out Cursor)
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position <> No_Element
то Has_Element (Container, Position));
Position : in out Cursor)
с Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element или иначе
Has_Element (Container, Position)
или иначе выдать Program_Error,
Post => (если Position <> No_Element
то Has_Element (Container, Position));
функция Find (Container : Set;
Item : Element_Type) возвращает Cursor
с Post => (если Find'Result <> No_Element
то Has_Element (Container, Find'Result));
Item : Element_Type) возвращает Cursor
с Post => (если Find'Result <> No_Element
то Has_Element (Container, Find'Result));
функция Floor (Container : Set;
Item : Element_Type) возвращает Cursor
с Post => (если Floor'Result <> No_Element
то Has_Element (Container, Floor'Result));
Item : Element_Type) возвращает Cursor
с Post => (если Floor'Result <> No_Element
то Has_Element (Container, Floor'Result));
функция Ceiling (Container : Set;
Item : Element_Type) возвращает Cursor
с Post => (если Ceiling'Result <> No_Element
то Has_Element (Container, Ceiling'Result));
Item : Element_Type) возвращает Cursor
с Post => (если Ceiling'Result <> No_Element
то Has_Element (Container, Ceiling'Result));
функция Contains (Container : Set;
Item : Element_Type) возвращает Boolean;
Item : Element_Type) возвращает Boolean;
Этот абзац был удален.
функция "<" (Left, Right : Cursor) возвращает Boolean
с Pre => (Left <> No_Element и затем Right <> No_Element)
или иначе выдать Constraint_Error,
Global => in all;
с Pre => (Left <> No_Element и затем Right <> No_Element)
или иначе выдать Constraint_Error,
Global => in all;
функция ">" (Left, Right : Cursor) возвращает Boolean
с Pre => (Left <> No_Element и затем Right <> No_Element)
или иначе выдать Constraint_Error,
Global => in all;
с Pre => (Left <> No_Element и затем Right <> No_Element)
или иначе выдать Constraint_Error,
Global => in all;
функция "<" (Left : Cursor; Right : Element_Type) возвращает Boolean
с Pre => Left <> No_Element или иначе выдать Constraint_Error,
Global => in all;
с Pre => Left <> No_Element или иначе выдать Constraint_Error,
Global => in all;
функция ">" (Left : Cursor; Right : Element_Type) возвращает Boolean
с Pre => Left <> No_Element или иначе выдать Constraint_Error,
Global => in all;
с Pre => Left <> No_Element или иначе выдать Constraint_Error,
Global => in all;
функция "<" (Left : Element_Type; Right : Cursor) возвращает Boolean
с Pre => Right <> No_Element или иначе выдать Constraint_Error,
Global => in all;
с Pre => Right <> No_Element или иначе выдать Constraint_Error,
Global => in all;
функция ">" (Left : Element_Type; Right : Cursor) возвращает Boolean
с Pre => Right <> No_Element или иначе выдать Constraint_Error,
Global => in all;
с Pre => Right <> No_Element или иначе выдать Constraint_Error,
Global => in all;
процедура Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
с Allows_Exit;
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
с Allows_Exit;
процедура Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
с Allows_Exit;
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
с Allows_Exit;
функция Iterate (Container : in Set)
возвращает Set_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
возвращает Set_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
функция Iterate (Container : in Set; Start : in Cursor)
возвращает Set_Iterator_Interfaces.Reversible_Iterator'Class
с Pre => (Start <> No_Element
или иначе выдать Constraint_Error) и затем
(Has_Element (Container, Start)
или иначе выдать Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
возвращает Set_Iterator_Interfaces.Reversible_Iterator'Class
с Pre => (Start <> No_Element
или иначе выдать Constraint_Error) и затем
(Has_Element (Container, Start)
или иначе выдать Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
обобщенное
тип Key_Type (<>) частный;
с функцией Key (Element : Element_Type) возвращает Key_Type;
с функцией "<" (Left, Right : Key_Type)
возвращает Boolean есть <>;
пакет Generic_Keys
с Nonblocking, Global => null есть
тип Key_Type (<>) частный;
с функцией Key (Element : Element_Type) возвращает Key_Type;
с функцией "<" (Left, Right : Key_Type)
возвращает Boolean есть <>;
пакет Generic_Keys
с Nonblocking, Global => null есть
функция Equivalent_Keys (Left, Right : Key_Type)
возвращает Boolean;
возвращает Boolean;
функция Key (Position : Cursor) возвращает Key_Type
с Pre => Position <> No_Element или иначе выдать Constraint_Error,
Global => in all;
с Pre => Position <> No_Element или иначе выдать Constraint_Error,
Global => in all;
функция Key (Container : Set;
Position : Cursor) возвращает Key_Type
с Pre => (Position <> No_Element
или иначе выдать Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе выдать Program_Error);
Position : Cursor) возвращает Key_Type
с Pre => (Position <> No_Element
или иначе выдать Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе выдать Program_Error);
функция Element (Container : Set;
Key : Key_Type)
возвращает Element_Type;
Key : Key_Type)
возвращает Element_Type;
процедура Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => Length (Container) = Length (Container)'Old;
Key : in Key_Type;
New_Item : in Element_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => Length (Container) = Length (Container)'Old;
процедура Exclude (Container : in out Set;
Key : in Key_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
Length (Container) в
Original_Length - 1 | Original_Length);
Key : in Key_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
Length (Container) в
Original_Length - 1 | Original_Length);
процедура Delete (Container : in out Set;
Key : in Key_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
Key : in Key_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
функция Find (Container : Set;
Key : Key_Type) возвращает Cursor
с Post => (если Find'Result /= No_Element
то Has_Element (Container, Find'Result));
Key : Key_Type) возвращает Cursor
с Post => (если Find'Result /= No_Element
то Has_Element (Container, Find'Result));
функция Floor (Container : Set;
Key : Key_Type) возвращает Cursor
с Post => (если Floor'Result /= No_Element
то Has_Element (Container, Floor'Result));
Key : Key_Type) возвращает Cursor
с Post => (если Floor'Result /= No_Element
то Has_Element (Container, Floor'Result));
функция Ceiling (Container : Set;
Key : Key_Type) возвращает Cursor
с Post => (если Ceiling'Result /= No_Element
то Has_Element (Container, Ceiling'Result));
Key : Key_Type) возвращает Cursor
с Post => (если Ceiling'Result /= No_Element
то Has_Element (Container, Ceiling'Result));
функция Contains (Container : Set;
Key : Key_Type) возвращает Boolean;
Key : Key_Type) возвращает Boolean;
процедура Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
с Pre => (Position /= No_Element
иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
иначе поднять Program_Error);
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
с Pre => (Position /= No_Element
иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
иначе поднять Program_Error);
тип Reference_Type
(Element : not null access Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (поднять Program_Error);
(Element : not null access Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (поднять Program_Error);
функция Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
возвращает Reference_Type
с Pre => (Position /= No_Element
иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
иначе поднять Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);;
Position : in Cursor)
возвращает Reference_Type
с Pre => (Position /= No_Element
иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
иначе поднять Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);;
функция Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
возвращает Constant_Reference_Type
с Pre => Find (Container, Key) /= No_Element
иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);;
Key : in Key_Type)
возвращает Constant_Reference_Type
с Pre => Find (Container, Key) /= No_Element
иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);;
функция Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
возвращает Reference_Type
с Pre => Find (Container, Key) /= No_Element
иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);;
Key : in Key_Type)
возвращает Reference_Type
с Pre => Find (Container, Key) /= No_Element
иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);;
конец Generic_Keys;
пакет Stable is
тип Set (Base : not null access Ordered_Sets.Set) is
tagged limited private
с Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global => null,
Default_Initial_Condition => Length (Set) = 0,
Preelaborable_Initialization;
tagged limited private
с Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global => null,
Default_Initial_Condition => Length (Set) = 0,
Preelaborable_Initialization;
тип Cursor is private
с Preelaborable_Initialization;
с Preelaborable_Initialization;
Empty_Set : константа Set;
No_Element : константа Cursor;
функция Has_Element (Position : Cursor) возвращает Boolean
с Nonblocking, Global => in all, Use_Formal => null;
с Nonblocking, Global => in all, Use_Formal => null;
пакет Set_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
процедура Assign (Target : in out Ordered_Sets.Set;
Source : in Set)
с Post => Length (Source) = Length (Target);
Source : in Set)
с Post => Length (Source) = Length (Target);
функция Copy (Source : Ordered_Sets.Set) возвращает Set
с Post => Length (Copy'Result) = Length (Source);
с Post => Length (Copy'Result) = Length (Source);
тип Constant_Reference_Type
(Element : not null access constant Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);
(Element : not null access constant Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);
-- Дополнительные подпрограммы, как описано в тексте
-- объявляются здесь.
-- объявляются здесь.
private
... -- не указано языком
конец Stable;
private
... -- не указано языком
конец Ada.Containers.Ordered_Sets;
Два элемента E1 и E2 являются эквивалентными, если оба E1 < E2 и E2 < E1 возвращают False, используя обобщённый формальный оператор "<" для элементов. Функция Equivalent_Elements возвращает True, если Left и Right эквивалентны, и False в противном случае.
Фактическая функция для обобщённого формального оператора "<" на значениях Element_Type должна возвращать одно и то же значение каждый раз, когда она вызывается с конкретной парой значений ключей. Она должна определять строго слабое отношение упорядочения (см. A.18). Если фактическая функция для "<" ведёт себя по-другому, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают "<" и сколько раз они её вызывают, не определено.
Если фактическая функция для обобщённого формального оператора "=" возвращает True для любой пары неэквивалентных элементов, поведение функции контейнера "=" не определено.
Если значение элемента, хранящегося в наборе, изменяется иначе, чем операцией в этом пакете, таким образом, что по меньшей мере один из операторов "<" или "=" даёт разные результаты, поведение этого пакета не определено.
Первый элемент непустого набора — это элемент, который меньше всех других элементов в наборе. Последний элемент непустого набора — это элемент, который больше всех других элементов в наборе. Последователь элемента — это наименьший элемент, который больше данного элемента. Предшественник элемента — это наибольший элемент, который меньше данного элемента. Все сравнения выполняются с помощью обобщённого формального оператора "<" для элементов.
функция Copy (Source : Set) возвращает Set
с Post => Length (Copy'Result) = Length (Source) и затем
не Tampering_With_Cursors_Prohibited (Copy'Result);
с Post => Length (Copy'Result) = Length (Source) и затем
не Tampering_With_Cursors_Prohibited (Copy'Result);
Возвращает набор, элементы которого инициализированы из соответствующих элементов Source.
процедура Delete_First (Container : in out Set)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
(если Original_Length = 0 то Length (Container) = 0
иначе Length (Container) = Original_Length - 1));
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
(если Original_Length = 0 то Length (Container) = 0
иначе Length (Container) = Original_Length - 1));
Если Container пуст, Delete_First не имеет эффекта. В противном случае, элемент, обозначенный First (Container), удаляется из Container. Delete_First изменяет курсоры Container.
процедура Delete_Last (Container : in out Set)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
(если Original_Length = 0 то Length (Container) = 0
иначе Length (Container) = Original_Length - 1));
с Pre => не Tampering_With_Cursors_Prohibited (Container)
иначе поднять Program_Error,
Post => (объявить
Original_Length : константа Count_Type :=
Length (Container)'Old;
начало
(если Original_Length = 0 то Length (Container) = 0
иначе Length (Container) = Original_Length - 1));
Если Container пуст, Delete_Last не имеет эффекта. В противном случае, элемент, обозначенный Last (Container), удаляется из Container. Delete_Last изменяет курсоры Container.
функция First_Element (Container : Set) возвращает Element_Type
с Pre => (не Is_Empty (Container)
иначе поднять Constraint_Error);
с Pre => (не Is_Empty (Container)
иначе поднять Constraint_Error);
Эквивалентно Element (First (Container)).
функция Last (Container : Set) возвращает Cursor
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container) то
Has_Element (Container, Last'Result)
иначе Last'Result = No_Element);
с Nonblocking, Global => null, Use_Formal => null,
Post => (если не Is_Empty (Container) то
Has_Element (Container, Last'Result)
иначе Last'Result = No_Element);
Возвращает курсор, который обозначает последний элемент в Container. Если Container пуст, возвращает No_Element.
функция Last_Element (Container : Set) возвращает Element_Type
с Pre => (не Is_Empty (Container)
иначе поднять Constraint_Error);
с Pre => (не Is_Empty (Container)
иначе поднять Constraint_Error);
Эквивалентно Element (Last (Container)).
функция Previous (Position : Cursor) возвращает Cursor
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то
Previous'Result = No_Element);
с Nonblocking, Global => in all, Use_Formal => null,
Post => (если Position = No_Element то
Previous'Result = No_Element);
Если Position равно No_Element, то Previous возвращает No_Element. В противном случае, Previous возвращает курсор, обозначающий предшествующий элемент, обозначенный Position. Если Position обозначает первый элемент, то Previous возвращает No_Element.
END_OF_DOCUMENT_MARKER
function Previous (Container : Set;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));
Возвращает указатель на предшествующий узел, обозначенный Position в Container, если такой узел существует.
procedure Previous (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
with Nonblocking, Global => in all, Use_Formal => null;
Эквивалентно Position := Previous (Position).
procedure Previous (Container : in Set;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Эквивалентно Position := Previous (Container, Position).
function Floor (Container : Set;
Item : Element_Type) return Cursor
with Post => (if Floor'Result /= No_Element
then Has_Element (Container, Floor'Result));
Item : Element_Type) return Cursor
with Post => (if Floor'Result /= No_Element
then Has_Element (Container, Floor'Result));
Floor ищет последний элемент, не больший, чем Item. Если такой элемент найден, возвращается указатель на него. В противном случае возвращается No_Element.
function Ceiling (Container : Set;
Item : Element_Type) return Cursor
with Post => (if Ceiling'Result /= No_Element
then Has_Element (Container, Ceiling'Result));
Item : Element_Type) return Cursor
with Post => (if Ceiling'Result /= No_Element
then Has_Element (Container, Ceiling'Result));
Ceiling ищет первый элемент, не меньший, чем Item. Если такой элемент найден, возвращается указатель на него. В противном случае возвращается No_Element.
function "<" (Left, Right : Cursor) return Boolean
with Pre => (Left /= No_Element and then Right /= No_Element)
or else raise Constraint_Error,
Global => in all;
with Pre => (Left /= No_Element and then Right /= No_Element)
or else raise Constraint_Error,
Global => in all;
Эквивалентно Element (Left) < Element (Right).
function ">" (Left, Right : Cursor) return Boolean
with Pre => (Left /= No_Element and then Right /= No_Element)
or else raise Constraint_Error,
Global => in all;
with Pre => (Left /= No_Element and then Right /= No_Element)
or else raise Constraint_Error,
Global => in all;
Эквивалентно Element (Right) < Element (Left).
function "<" (Left : Cursor; Right : Element_Type) return Boolean
with Pre => Left /= No_Element or else raise Constraint_Error,
Global => in all;
with Pre => Left /= No_Element or else raise Constraint_Error,
Global => in all;
Эквивалентно Element (Left) < Right.
function ">" (Left : Cursor; Right : Element_Type) return Boolean
with Pre => Left /= No_Element or else raise Constraint_Error,
Global => in all;
with Pre => Left /= No_Element or else raise Constraint_Error,
Global => in all;
Эквивалентно Right < Element (Left).
function "<" (Left : Element_Type; Right : Cursor) return Boolean
with Pre => Right /= No_Element or else raise Constraint_Error,
Global => in all;
with Pre => Right /= No_Element or else raise Constraint_Error,
Global => in all;
Эквивалентно Left < Element (Right).
function ">" (Left : Element_Type; Right : Cursor) return Boolean
with Pre => Right /= No_Element or else raise Constraint_Error,
Global => in all;
with Pre => Right /= No_Element or else raise Constraint_Error,
Global => in all;
Эквивалентно Element (Right) < Left.
procedure Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
(Container : in Set;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
Итерируется по элементам в Container так же, как и процедура Iterate, но элементы обрабатываются в обратном порядке, начиная с последнего элемента.
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
return Set_Iterator_Interfaces.Parallel_Reversible_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 (Container : in Set; Start : in Cursor)
return Set_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
return Set_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Iterate возвращает объект обратимого итератора (см. 5.5.1), который будет генерировать значения для параметра цикла (см. 5.5.2), обозначающие каждый элемент в Container, начиная с элемента, обозначенного Start, и перемещая курсор в соответствии с отношением преемника при использовании как прямого итератора или перемещая курсор в соответствии с отношением предшественника при использовании как обратного итератора. Изменение курсоров 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 в противном случае.
Рекомендации по реализации
Если N — длина набора, то временная сложность операций Insert, Include, Replace, Delete, Exclude и Find, принимающих параметр элемента, должна составлять O((log N)**2) или лучше. Временная сложность подпрограмм, принимающих параметр курсора, должна составлять O(1).
