Справочник Ada 2005
A.18.9 Пакет Containers.Ordered_Sets
Статическая семантика
В библиотечном пакете Containers.Ordered_Sets содержится следующее объявление:
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);
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);
function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
type Set is tagged private;
pragma Preelaborable_Initialization(Set);
pragma Preelaborable_Initialization(Set);
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
pragma Preelaborable_Initialization(Cursor);
Empty_Set : constant Set;
No_Element : constant Cursor;
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);
Position : in Cursor;
New_Item : in Element_Type);
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
procedure Move (Target : in out Set;
Source : in out Set);
Source : in out Set);
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Include (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Exclude (Container : in out Set;
Item : in Element_Type);
Item : in Element_Type);
procedure Delete (Container : in out Set;
Item : in Element_Type);
Item : in Element_Type);
procedure Delete (Container : in out Set;
Position : in out Cursor);
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);
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);
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);
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);
Source : in Set);
function Symmetric_Difference (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;
Symmetric_Difference;
function Overlap (Left, Right : Set) return Boolean;
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
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;
Item : Element_Type)
return Cursor;
function Floor (Container : Set;
Item : Element_Type)
return Cursor;
Item : Element_Type)
return Cursor;
function Ceiling (Container : Set;
Item : Element_Type)
return Cursor;
Item : Element_Type)
return Cursor;
function Contains (Container : Set;
Item : Element_Type) return Boolean;
Item : Element_Type) return Boolean;
function Has_Element (Position : Cursor) return Boolean;
function "<" (Left, Right : Cursor) return Boolean;
function ">" (Left, Right : Cursor) return Boolean;
function "<" (Left : Cursor; Right : Element_Type)
return Boolean;
return Boolean;
function ">" (Left : Cursor; Right : Element_Type)
return Boolean;
return Boolean;
function "<" (Left : Element_Type; Right : Cursor)
return Boolean;
return Boolean;
function ">" (Left : Element_Type; Right : Cursor)
return Boolean;
return Boolean;
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
(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));
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
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
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;
return Boolean;
function Key (Position : Cursor) return Key_Type;
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
Key : Key_Type)
return Element_Type;
procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
procedure Exclude (Container : in out Set;
Key : in Key_Type);
Key : in Key_Type);
procedure Delete (Container : in out Set;
Key : in Key_Type);
Key : in Key_Type);
function Find (Container : Set;
Key : Key_Type)
return Cursor;
Key : Key_Type)
return Cursor;
function Floor (Container : Set;
Key : Key_Type)
return Cursor;
Key : Key_Type)
return Cursor;
function Ceiling (Container : Set;
Key : Key_Type)
return Cursor;
Key : Key_Type)
return Cursor;
function Contains (Container : Set;
Key : Key_Type) return Boolean;
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));
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
end Generic_Keys;
private
... -- не определено языком
end Ada.Containers.Ordered_Sets;
Два элемента E1 и E2 являются эквивалентными, если оба выражения E1 < E2 и E2 < E1 возвращают False, используя оператор "<" для элементов. Функция Equivalent_Elements возвращает True, если Left и Right эквивалентны, и False в противном случае.
Ожидается, что фактическая функция для универсального формального оператора "<" над значениями Element_Type возвращает одно и то же значение каждый раз, когда она вызывается с конкретной парой значений ключей. Она должна определять строгое отношение порядка, то есть быть нерефлексивной, несимметричной и транзитивной. Если фактическая реализация "<" ведет себя иначе, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают "<" и сколько раз они это делают, не определено.
Если значение элемента, хранящегося в множестве, изменяется иным способом, чем операцией в этом пакете, так что по крайней мере один из "<" или "=" дает разные результаты, поведение этого пакета не определено.
Первый элемент непустого множества — это тот, который меньше всех других элементов в множестве. Последний элемент непустого множества — это тот, который больше всех других элементов в множестве. Преемник элемента — это наименьший элемент, который больше данного элемента. Предшественник элемента — это наибольший элемент, который меньше данного элемента. Все сравнения выполняются с использованием универсального формального оператора "<" для элементов.
procedure Delete_First (Container : in out Set);
Если Container пуст, Delete_First не имеет эффекта. В противном случае элемент, обозначенный First (Container), удаляется из Container. Delete_First изменяет курсоры Container.
procedure Delete_Last (Container : in out Set);
Если Container пуст, Delete_Last не имеет эффекта. В противном случае элемент, обозначенный Last (Container), удаляется из Container. Delete_Last изменяет курсоры Container.
function First_Element (Container : Set) return 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;
Item : Element_Type) возвращает Cursor;
Floor ищет последний элемент, который не больше Item. Если такой элемент найден, возвращается указатель, обозначающий его. В противном случае возвращается No_Element.
функция Ceiling (Container : Set;
Item : Element_Type) возвращает Cursor;
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 : in Set;
Process : not null access procedure (Position : in Cursor));
Итерирует по элементам в Container в соответствии с Iterate, с той разницей, что элементы просматриваются в порядке предшественников, начиная с последнего элемента.
Для любых двух элементов 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).
