Справочник Ada 2012

A.18.7 Множества

Определяемые языком обобщенные пакеты Containers.Hashed_Sets и Containers.Ordered_Sets предоставляют приватные типы Set и Cursor, а также набор операций для каждого типа. Контейнер множества позволяет хранить элементы произвольного типа без дублирования. Хэшированное множество использует хеш-функцию для организации элементов, а упорядоченное множество упорядочивает свои элементы по заданному отношению.

Этот подпункт описывает объявления, общие для обоих типов множеств. Смотрите A.18.8 для описания семантики, специфичной для Containers.Hashed_Sets, и A.18.9 для описания семантики, специфичной для Containers.Ordered_Sets.

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

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

Тип Set используется для представления множеств. Тип Set требует завершения (см. 7.6).

Множество содержит элементы. Курсоры множества обозначают элементы. Существует отношение эквивалентности на элементах, определение которого отличается для хэшированных и упорядоченных множеств. Множество никогда не содержит два или более эквивалентных элемента. Длина множества — это количество элементов, которые оно содержит.

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

Некоторые операции этих обобщенных пакетов имеют параметры доступа к подпрограммам. Чтобы гарантировать корректность таких операций, они предохраняют от определенных действий со стороны указанной подпрограммы. В частности, некоторые операции проверяют «вмешательство с курсорами» контейнера, поскольку они зависят от того, чтобы набор элементов контейнера оставался постоянным, а другие проверяют «вмешательство с элементами» контейнера, поскольку они зависят от того, чтобы элементы контейнера не заменялись.

Подпрограмма называется вмешивающейся с курсорами объекта множества S, если:

она вставляет или удаляет элементы S, то есть, она вызывает процедуры Insert, Include, Clear, Delete, Exclude или Replace_Element с S в качестве параметра;

она завершает S;

она вызывает процедуру Assign с S в качестве параметра Target;

она вызывает процедуру Move с S в качестве параметра;

она вызывает одну из операций, определенных как вмешивающаяся с курсорами S.

Подпрограмма называется вмешивающейся с элементами объекта множества S, если:

она вмешивается с курсорами S.

Когда вмешательство с курсорами запрещено для определенного объекта множества S, Program_Error передается при вызове любой определяемой языком подпрограммы, которая определена как вмешивающаяся с курсорами S, оставляя S неизменным. Аналогично, когда вмешательство с элементами запрещено для определенного объекта множества S, Program_Error передается при вызове любой определяемой языком подпрограммы, которая определена как вмешивающаяся с элементами S (или вмешивающаяся с курсорами S), оставляя S неизменным. Эти проверки выполняются до любого другого определенного поведения тела определяемой языком подпрограммы.

Empty_Set представляет пустой объект Set. Его длина равна 0. Если объект типа Set не инициирован другим способом, он инициализируется тем же значением, что и Empty_Set.

No_Element представляет курсор, который не обозначает ни одного элемента. Если объект типа Cursor не инициализирован иначе, он инициализируется тем же значением, что и No_Element.

Предопределенный оператор «=» для типа Cursor возвращает True, если оба курсора равны No_Element или обозначают тот же элемент в том же контейнере.

Выполнение стандартной реализации атрибутов Input, Output, Read или Write типа Cursor вызывает Program_Error.

Set'Write для объекта множества S записывает Length(S) элементов множества в поток. Он также может записать дополнительную информацию о множестве.

Set'Read считывает представление множества из потока и присваивает Item множество с той же длиной и теми же элементами, что и записано с помощью Set'Write.

function Has_Element (Position : Cursor) return Boolean;

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

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

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

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

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

function To_Set (New_Item : Element_Type) return Set;

Возвращает множество, содержащее единственный элемент New_Item.

function Length (Container : Set) return Count_Type;

Возвращает количество элементов в Container.

function Is_Empty (Container : Set) return Boolean;

Эквивалентно Length (Container) = 0.

procedure Clear (Container : in out Set);

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

function Element (Position : Cursor) return Element_Type;

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

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

Если Position равно No_Element, то передается Constraint_Error; если Position не обозначает элемент в Container, то передается Program_Error. Если элемент, эквивалентный New_Item, уже присутствует в Container в позиции, отличной от Position, передается Program_Error. В противном случае Replace_Element присваивает New_Item элементу, обозначенному Position. Любое исключение, поднятое при присваивании, передается.

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

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

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

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

Стандартная инициализация объекта типа Constant_Reference_Type передает Program_Error.

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

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

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

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

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

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

Если Target обозначает тот же объект, что и Source, то операция не имеет эффекта. В противном случае операция эквивалентна Assign (Target, Source) за которой следует Clear (Source).

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

Проверка вставки, если элемент, эквивалентный New_Item, уже присутствует в Container. Если совпадение найдено, Inserted устанавливается в False, а Position обозначает соответствующий элемент. В противном случае Insert добавляет New_Item в Container; Inserted устанавливается в True, а Position обозначает вновь вставленный элемент. Любое исключение, возникшее во время выделения памяти, передаётся дальше, и Container не изменяется.

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

Insert вставляет New_Item в Container, как в случае с четырёхпараметрическим Insert, с той разницей, что если элемент, эквивалентный New_Item, уже находится в множестве, то возникает исключение Constraint_Error.

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

Include вставляет New_Item в Container, как в четырёхпараметрическом Insert, с той разницей, что если элемент, эквивалентный New_Item, уже есть в множестве, то он заменяется. Любое исключение, возникшее во время присваивания, передаётся дальше.

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

Replace проверяет, есть ли в множестве элемент, эквивалентный New_Item. Если совпадение найдено, этот элемент заменяется на New_Item; в противном случае возникает исключение Constraint_Error.

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

Exclude проверяет, присутствует ли в Container элемент, эквивалентный Item. Если совпадение найдено, Exclude удаляет элемент из множества.

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

Delete проверяет, присутствует ли в Container элемент, эквивалентный Item. Если совпадение найдено, Delete удаляет элемент из множества; в противном случае возникает исключение Constraint_Error.

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

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

процедура Union (Target : in out Set;
Source : in Set);

Union вставляет в Target элементы Source, которые не эквивалентны элементам, уже присутствующим в Target.

функция Union (Left, Right : Set) return Set;

Возвращает множество, содержащее все элементы Left и элементы Right, не эквивалентные элементам Left.

процедура Intersection (Target : in out Set;
Source : in Set);

Intersection удаляет из Target элементы, не эквивалентные элементам Source.

функция Intersection (Left, Right : Set) return Set;

Возвращает множество, содержащее все элементы Left, эквивалентные элементам Right.

процедура Difference (Target : in out Set;
Source : in Set);

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

функция Difference (Left, Right : Set) return Set;

Возвращает множество, содержащее элементы Left, не эквивалентные элементам Right.

процедура Symmetric_Difference (Target : in out Set;
Source : in Set);

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

функция Symmetric_Difference (Left, Right : Set) return Set;

Возвращает множество, содержащее элементы Left, не эквивалентные элементам Right, и элементы Right, не эквивалентные элементам Left.

функция Overlap (Left, Right : Set) return Boolean;

Если элемент Left эквивалентен элементу Right, то Overlap возвращает True. В противном случае возвращает False.

функция Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;

Если элемент Subset не эквивалентен элементу Of_Set, то Is_Subset возвращает False. В противном случае возвращает True.

функция First (Container : Set) return Cursor;

Если Length (Container) = 0, то First возвращает No_Element. В противном случае First возвращает курсор, указывающий на первый элемент в Container.

функция Next (Position : Cursor) return Cursor;

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

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

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

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

функция Find (Container : Set;
Item : Element_Type) return Cursor;

Если Length (Container) равно 0, то Find возвращает No_Element. В противном случае Find проверяет, присутствует ли элемент, эквивалентный Item, в Container. Если совпадение найдено, возвращается курсор, указывающий на соответствующий элемент; в противном случае возвращается No_Element.

функция Contains (Container : Set;
Item : Element_Type) return Boolean;

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

Абзацы 83 и 84 были перемещены выше.

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

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

Как Containers.Hashed_Set, так и Containers.Ordered_Set объявляют вложенный обобщённый пакет Generic_Keys, который предоставляет операции по манипулированию множествами с точки зрения ключа (обычно, части элемента), а не всего элемента. Формальная функция Key из Generic_Keys извлекает значение ключа из элемента. Ожидается, что она будет возвращать одно и то же значение каждый раз, когда вызывается с конкретным элементом. Поведение Generic_Keys не определено, если Key ведёт себя каким-либо другим образом.

Ожидается, что ключ однозначно определяет единый класс эквивалентности для элементов. Поведение Generic_Keys не определено, если формальные параметры этого пакета ведут себя каким-либо другим образом.

функция Key (Position : Cursor) return Key_Type;

Эквивалентно Key (Element (Position)).

Подпрограммы в пакете Generic_Keys с именами Contains, Find, Element, Delete и Exclude эквивалентны соответствующим подпрограммам в родительском пакете с той разницей, что используется параметр Key для поиска элемента в множестве.

процедура Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);

Эквивалентно Replace_Element (Container, Find (Container, Key), New_Item).

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

Если Position равно No_Element, то возникает исключение Constraint_Error; если Position не указывает на элемент в Container, то возникает исключение Program_Error. В противном случае Update_Element_Preserving_Key использует Key для сохранения значения ключа K элемента, обозначенного Position. Затем Update_Element_Preserving_Key вызывает Process.all с этим элементом в качестве аргумента. Изменение элементов Container запрещено во время выполнения вызова Process.all. Любое исключение, вызванное Process.all, передаётся дальше. После возвращения Process.all, Update_Element_Preserving_Key проверяет, определяет ли K тот же класс эквивалентности, что и для нового элемента; если нет, элемент удаляется из множества, и возникает исключение Program_Error.

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

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

Тип Reference_Type требует финализации.

По умолчанию инициализация объекта типа Reference_Type вызывает исключение Program_Error.

функция Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;

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

Если Position равно No_Element, то Constraint_Error распространяется; если Position не обозначает элемент в Container, то распространяется Program_Error. В противном случае, Reference_Preserving_Key использует Key для сохранения значения ключа K; затем возвращает объект, дискриминант которого является значением доступа, обозначающим элемент, обозначенный Position. Вмешательство в элементы Container запрещено, пока существует возвращаемый объектом Reference_Preserving_Key и он не завершен. Когда возвращаемый объектом Reference_Preserving_Key объект завершен, проверяется, определяет ли K тот же класс эквивалентности, что и для нового элемента; если нет, элемент удаляется из множества, и распространяется Program_Error.

функция Constant_Reference (Container : алиас в Set;
Key : в Key_Type)
возвращает Constant_Reference_Type;

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

Эквивалентно Constant_Reference (Container, Find (Container, Key)).

функция Reference_Preserving_Key (Container : алиас во вход Set;
Key : в Key_Type)
возвращает Reference_Type;

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

Эквивалентно Reference_Preserving_Key (Container, Find (Container, Key)).

Ограниченные (времени выполнения) ошибки

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

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

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

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

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

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

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

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

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

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

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

Никакой памяти, связанной с объектом Set, не должна теряться при присваивании или выходе из области видимости.

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

A.18.7 Множества

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

Ограниченные (времени выполнения) ошибки

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

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

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