Руководство по Ada (Ada 2022)
A.18.8 Общий пакет Containers.Hashed_Sets
Статическая семантика
Общий пакет библиотек Containers.Hashed_Sets имеет следующее объявление:
with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function Hash (Element : Element_Type) return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
generic
type Element_Type is private;
with function Hash (Element : Element_Type) return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets
with Preelaborate, Remote_Types,
Nonblocking, Global => in out synchronized is
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 (Capacity : Count_Type := определяемое реализацией)
return Set
with Post =>
Capacity (Empty'Result) >= Capacity and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
return Set
with Post =>
Capacity (Empty'Result) >= Capacity and then
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 Capacity (Container : Set) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
with Nonblocking, Global => null, Use_Formal => null;
procedure Reserve_Capacity (Container : in out Set;
Capacity : in Count_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
Capacity : in Count_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
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 => Capacity (Container) = Capacity (Container)'Old and then
Length (Container) = 0;
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old and then
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) and then
Capacity (Target) >= Length (Source);
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target) and then
Capacity (Target) >= Length (Source);
function Copy (Source : Set; Capacity : Count_Type := 0)
return Set
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Cursors_Prohibited (Copy'Result) and then
Copy'Result.Capacity = (if Capacity = 0 then
Length (Source) else Capacity);
return Set
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Cursors_Prohibited (Copy'Result) and then
Copy'Result.Capacity = (if Capacity = 0 then
Length (Source) else Capacity);
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)) and then
Capacity (Container) >= Length (Container);
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)) and then
Capacity (Container) >= Length (Container);
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 and then
Capacity (Container) >= Length (Container);
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 and then
Capacity (Container) >= Length (Container);
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) and then
Capacity (Container) >= Length (Container);
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) and then
Capacity (Container) >= Length (Container);
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;
END_OF_DOCUMENT_MARKER Item : in Element_Type)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
процедура Delete (Container : in out Set;
Position : in out Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и затем
(Position /= No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе поднять Program_Error),
Post => Length (Container) = Length (Container)'Old - 1 и затем
Position = No_Element;
Position : in out Cursor)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и затем
(Position /= No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе поднять Program_Error),
Post => Length (Container) = Length (Container)'Old - 1 и затем
Position = No_Element;
процедура 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) return 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) return 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) return 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) return 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) return 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) return 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) return 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);
функция "исключ. или" (Left, Right : Set) return Set
переименовывает Symmetric_Difference;
переименовывает Symmetric_Difference;
функция Overlap (Left, Right : Set) return Boolean;
функция Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
Of_Set : Set) return Boolean;
функция First (Container : Set) return 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);
функция Next (Position : Cursor) return Cursor
с Nonblocking, Global => во всех, Use_Formal => null,
Post => (если Position = No_Element то Next'Result = No_Element);
с Nonblocking, Global => во всех, Use_Formal => null,
Post => (если Position = No_Element то Next'Result = No_Element);
функция Next (Container : Set;
Position : Cursor) return 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) return 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 => во всех, Use_Formal => null;
с Nonblocking, Global => во всех, 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));
функция Find (Container : Set;
Item : Element_Type)
return Cursor
с Post => (если Find'Result /= No_Element
то Has_Element (Container, Find'Result));
Item : Element_Type)
return Cursor
с Post => (если Find'Result /= No_Element
то Has_Element (Container, Find'Result));
функция Contains (Container : Set;
Item : Element_Type) return Boolean;
Item : Element_Type) return Boolean;
Этот абзац был удален.
функция Equivalent_Elements (Left, Right : Cursor)
return Boolean
с Pre => (Left /= No_Element и затем Right /= No_Element)
или иначе поднять Constraint_Error,
Global => во всех;
return Boolean
с Pre => (Left /= No_Element и затем Right /= No_Element)
или иначе поднять Constraint_Error,
Global => во всех;
функция Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean
с Pre => Left /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Right : Element_Type)
return Boolean
с Pre => Left /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
функция Equivalent_Elements (Left : Element_Type;
Right : Cursor)
return Boolean
с Pre => Right /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Right : Cursor)
return Boolean
с Pre => Right /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
процедура Iterate
(Container : in Set;
Process : не null доступ к процедуре (Position : in Cursor))
с Allows_Exit;
(Container : in Set;
Process : не null доступ к процедуре (Position : in Cursor))
с Allows_Exit;
функция Iterate (Container : in Set)
return Set_Iterator_Interfaces.Parallel_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
return Set_Iterator_Interfaces.Parallel_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
generic
тип Key_Type (<>) is private;
с функцией Key (Element : Element_Type) return Key_Type;
с функцией Hash (Key : Key_Type) return Hash_Type;
с функцией Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
пакет Generic_Keys
с Nonblocking, Global => null is
тип Key_Type (<>) is private;
с функцией Key (Element : Element_Type) return Key_Type;
с функцией Hash (Key : Key_Type) return Hash_Type;
с функцией Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
пакет Generic_Keys
с Nonblocking, Global => null is
функция Key (Position : Cursor) return Key_Type
с Pre => Position /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
с Pre => Position /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
функция Key (Container : Set;
Position : Cursor) return Key_Type
с Pre => (Position = No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе поднять Program_Error);
Position : Cursor) return Key_Type
с Pre => (Position = No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе поднять Program_Error);
функция Element (Container : Set;
Key : Key_Type)
return Element_Type;
Key : Key_Type)
return 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 => (declare
Original_Length : const Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length - 1 | Original_Length);
Key : in Key_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => (declare
Original_Length : const Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in 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)
return Cursor
с Post => (если Find'Result = No_Element
то Has_Element (Container, Find'Result));
Key : Key_Type)
return Cursor
с Post => (если Find'Result = No_Element
то Has_Element (Container, Find'Result));
функция Contains (Container : Set;
Key : Key_Type)
return Boolean;
Key : Key_Type)
return Boolean;
процедура Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : не null доступ к процедуре
(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 : не null доступ к процедуре
(Element : in out Element_Type))
с Pre => (Position /= No_Element или иначе
поднять Constraint_Error) и затем
(Has_Element (Container, Position) или иначе
поднять Program_Error);
тип Reference_Type
(Element : не null доступ к Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => in out синхронизировано,
Default_Initial_Condition => (поднять Program_Error);
(Element : не null доступ к Element_Type) is private
с Implicit_Dereference => Element,
Nonblocking, Global => in out синхронизировано,
Default_Initial_Condition => (поднять Program_Error);
функция Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type
с Pre => (Position /= No_Element
или иначе поднять Constraint_Error) и затем
(Has_Element (Container, Position)
или иначе поднять Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Position : in Cursor)
return 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)
return Constant_Reference_Type
с Pre => Find (Container, Key) /= No_Element
или иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);
Key : in Key_Type)
return 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)
return Reference_Type
с Pre => Find (Container, Key) /= No_Element
или иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);
Key : in Key_Type)
return Reference_Type
с Pre => Find (Container, Key) /= No_Element
или иначе поднять Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container);
end Generic_Keys;
пакет Stable is
END_OF_DOCUMENT_MARKER тип Set (Базовый : не null доступ Hashed_Sets.Set) является
меченый ограниченный приватный
с Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Длина),
Global => null,
Default_Initial_Condition => Длина (Set) = 0,
Preelaborable_Initialization;
меченый ограниченный приватный
с Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Длина),
Global => null,
Default_Initial_Condition => Длина (Set) = 0,
Preelaborable_Initialization;
тип Cursor является приватным
с Preelaborable_Initialization;
с Preelaborable_Initialization;
Empty_Set : константа Set;
No_Element : константа Cursor;
функция Has_Element (Position : Cursor) возвращает Boolean
с Nonblocking, Global => во всех, Use_Formal => null;
с Nonblocking, Global => во всех, Use_Formal => null;
пакет Set_Iterator_Interfaces новый
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
процедура Assign (Target : вход/выход Hashed_Sets.Set;
Source : вход Set)
с Post => Длина (Source) = Длина (Target);
Source : вход Set)
с Post => Длина (Source) = Длина (Target);
функция Copy (Source : Hashed_Sets.Set) возвращает Set
с Post => Длина (Copy'Result) = Длина (Source);
с Post => Длина (Copy'Result) = Длина (Source);
тип Constant_Reference_Type
(Element : не null доступ к константе Element_Type) является приватным
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);
(Element : не null доступ к константе Element_Type) является приватным
с Implicit_Dereference => Element,
Nonblocking, Global => null, Use_Formal => null,
Default_Initial_Condition => (поднять Program_Error);
-- Дополнительные подпрограммы, как описано в тексте
-- объявляются здесь.
-- объявляются здесь.
приватный
... -- не указано языком
конец Stable;
приватный
... -- не указано языком
конец Ada.Containers.Hashed_Sets;
Объект типа Set содержит расширяемую хеш-таблицу, которая используется для обеспечения прямого доступа к элементам. Ёмкость объекта типа Set — это максимальное количество элементов, которые могут быть вставлены в хеш-таблицу до её автоматического расширения.
Два элемента E1 и E2 определяются как эквивалентные, если Equivalent_Elements (E1, E2) возвращает True.
Фактическая функция для обобщенного формального параметра Hash должна возвращать одно и то же значение каждый раз, когда она вызывается с конкретным значением элемента. Для любых двух эквивалентных элементов фактическая функция Hash должна возвращать одно и то же значение. Если фактическая функция Hash ведет себя по-другому, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Hash и сколько раз они его вызывают, не определено.
Фактическая функция для обобщенного формального параметра Equivalent_Elements должна возвращать одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элемента. Она должна определять отношение эквивалентности, то есть быть рефлексивной, симметричной и транзитивной. Если фактическая функция Equivalent_Elements ведет себя по-другому, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Equivalent_Elements и сколько раз они её вызывают, не определено.
Если фактическая функция для обобщенного формального параметра «=» возвращает True для любой пары неэквивалентных элементов, поведение контейнерной функции «=» не определено.
Если значение элемента, хранящегося в наборе, изменяется иначе, чем операцией в этом пакете, так что по крайней мере одно из Hash или Equivalent_Elements дает разные результаты, поведение этого пакета не определено.
Какие элементы являются первым и последним элементом набора, и какой элемент является преемником данного элемента, не определено, за исключением общей семантики, описанной в A.18.7.
функция Empty (Capacity : Count_Type := определяемое реализацией)
возвращает Set
с Post =>
Capacity (Empty'Result) >= Capacity и затем
не Tampering_With_Cursors_Prohibited (Empty'Result) и затем
Длина (Empty'Result) = 0;
возвращает Set
с Post =>
Capacity (Empty'Result) >= Capacity и затем
не Tampering_With_Cursors_Prohibited (Empty'Result) и затем
Длина (Empty'Result) = 0;
Возвращает пустой набор.
функция Capacity (Container : Set) возвращает Count_Type
с Nonblocking, Global => null, Use_Formal => null;
с Nonblocking, Global => null, Use_Formal => null;
Возвращает емкость Container.
процедура Reserve_Capacity (Container : вход/выход Set;
Capacity : вход Count_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => Container.Capacity >= Capacity;
Capacity : вход Count_Type)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => Container.Capacity >= Capacity;
Reserve_Capacity выделяет новую хеш-таблицу таким образом, что длина результирующего набора может стать по крайней мере значение Capacity без необходимости дополнительного вызова Reserve_Capacity и достаточно велика, чтобы вместить текущую длину Container. Reserve_Capacity затем перехеширует элементы в Container в новую хеш-таблицу. Она заменяет старую хеш-таблицу новой и затем освобождает старую хеш-таблицу. Любое исключение, возникшее во время выделения, передается, и Container не изменяется.
Этот абзац был удален.
процедура Clear (Container : вход/выход Set)
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old и затем
Длина (Container) = 0;
с Pre => не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old и затем
Длина (Container) = 0;
В дополнение к семантике, описанной в A.18.7, Clear не влияет на емкость Container.
процедура Assign (Target : вход/выход Set; Source : вход Set)
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе поднять Program_Error,
Post => Длина (Source) = Длина (Target) и затем
Capacity (Target) >= Длина (Source);
с Pre => не Tampering_With_Cursors_Prohibited (Target)
или иначе поднять Program_Error,
Post => Длина (Source) = Длина (Target) и затем
Capacity (Target) >= Длина (Source);
В дополнение к семантике, описанной в A.18.7, если длина Source больше емкости Target, Reserve_Capacity (Target, Длина (Source)) вызывается перед присвоением каких-либо элементов.
функция Copy (Source : Set; Capacity : Count_Type := 0)
возвращает Set
с Pre => Capacity = 0 или иначе Capacity >= Длина (Source)
или иначе поднять Capacity_Error,
Post =>
Длина (Copy'Result) = Длина (Source) и затем
не Tampering_With_Cursors_Prohibited (Copy'Result) и затем
Copy'Result.Capacity = (если Capacity = 0 то
Длина (Source) иначе Capacity);
возвращает Set
с Pre => Capacity = 0 или иначе Capacity >= Длина (Source)
или иначе поднять Capacity_Error,
Post =>
Длина (Copy'Result) = Длина (Source) и затем
не Tampering_With_Cursors_Prohibited (Copy'Result) и затем
Copy'Result.Capacity = (если Capacity = 0 то
Длина (Source) иначе Capacity);
Возвращает набор, элементы которого инициализированы из элементов Source.
процедура Insert (Container : вход/выход Set;
New_Item : вход Element_Type;
Position : выход Cursor;
Inserted : выход Boolean)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и затем
(Длина (Container) <= Count_Type'Last - 1
или иначе поднять Constraint_Error),
Post => (объявить
Original_Length : константа Count_Type :=
Длина (Container)'Old;
начало
Has_Element (Container, Position) и затем
(если Inserted то
Длина (Container) = Original_Length + 1
иначе
Длина (Container) = Original_Length)) и затем
Capacity (Container) >= Длина (Container);
New_Item : вход Element_Type;
Position : выход Cursor;
Inserted : выход Boolean)
с Pre => (не Tampering_With_Cursors_Prohibited (Container)
или иначе поднять Program_Error) и затем
(Длина (Container) <= Count_Type'Last - 1
или иначе поднять Constraint_Error),
Post => (объявить
Original_Length : константа Count_Type :=
Длина (Container)'Old;
начало
Has_Element (Container, Position) и затем
(если Inserted то
Длина (Container) = Original_Length + 1
иначе
Длина (Container) = Original_Length)) и затем
Capacity (Container) >= Длина (Container);
В дополнение к семантике, описанной в A.18.7, если Длина (Container) равна Capacity (Container), то Insert сначала вызывает Reserve_Capacity, чтобы увеличить емкость Container до некоторого большего значения.
функция First (Container : Set) возвращает Cursor;
Если Длина (Container) = 0, то First возвращает No_Element. Иначе First возвращает указатель, который обозначает первый хешированный элемент в Container.
функция Equivalent_Elements (Left, Right : Cursor)
возвращает Boolean
с Pre => (Left /= No_Element и затем Right /= No_Element)
или иначе поднять Constraint_Error,
Global => во всех;
возвращает Boolean
с Pre => (Left /= No_Element и затем Right /= No_Element)
или иначе поднять Constraint_Error,
Global => во всех;
Эквивалентно Equivalent_Elements (Element (Left), Element (Right)).
функция Equivalent_Elements (Left : Cursor;
Right : Element_Type) возвращает Boolean
с Pre => Left /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Right : Element_Type) возвращает Boolean
с Pre => Left /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Эквивалентно Equivalent_Elements (Element (Left), Right).
функция Equivalent_Elements (Left : Element_Type;
Right : Cursor) возвращает Boolean
с Pre => Right /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Right : Cursor) возвращает Boolean
с Pre => Right /= No_Element или иначе поднять Constraint_Error,
Global => во всех;
Эквивалентно Equivalent_Elements (Left, Element (Right)).
функция Iterate (Container : вход Set)
возвращает Set_Iterator_Interfaces.Parallel_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
возвращает Set_Iterator_Interfaces.Parallel_Iterator'Class
с Post => Tampering_With_Cursors_Prohibited (Container);
Iterate возвращает объект итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающего каждый элемент в Container, начиная с первого элемента и перемещая указатель в соответствии с отношением преемника при использовании в качестве итератора вперёд, и обрабатывая все узлы параллельно при использовании в качестве параллельного итератора. Вмешательство в указатели Container запрещено во время существования объекта итератора (в частности, в sequence_of_statements оператора цикла loop_statement, чьё iterator_specification обозначает этот объект). Объект итератора нуждается в финализации.
Для любого элемента E, фактическая функция для обобщённой формальной функции Generic_Keys.Hash должна быть такой, что Hash (E) = Generic_Keys.Hash (Key (E)). Если фактические значения для Key или Generic_Keys.Hash ведут себя каким-либо иным образом, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Generic_Keys.Hash и сколько раз они это делают, не определено.
Для любых двух элементов E1 и E2, значения булевых переменных Equivalent_Elements (E1, E2) и Equivalent_Keys (Key (E1), Key (E2)) должны быть равны. Если фактические значения для Key или Equivalent_Keys ведут себя каким-либо иным образом, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Equivalent_Keys и сколько раз они это делают, не определено.
Рекомендации по реализации
Если N — длина множества, средняя временная сложность подпрограмм Insert, Include, Replace, Delete, Exclude и Find, которые принимают параметр элемента, должна составлять O(log N). Средняя временная сложность подпрограмм, которые принимают параметр курсора, должна составлять O(1). Средняя временная сложность Reserve_Capacity должна составлять O(N).
