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

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; или

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

она вызывает одну из операций, определённых для вмешательства с курсорами 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.

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, в качестве аргумента. Program_Error передаётся дальше, если Process.all вмешивается с элементами Container. Любое исключение, возникающее в Process.all, передаётся дальше.

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

Если Target обозначает тот же объект, что и Source, то Move не имеет эффекта. В противном случае Move сначала очищает Target. Затем каждый элемент из Source удаляется из Source и вставляется в Target. Длина Source равна 0 после успешного вызова Move.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

END_OF_DOCUMENT_MARKER

Функция Union (Left, Right : Set) возвращает Set;

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

Процедура Intersection (Target : вход/выход Set;
Source : вход Set);

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

Функция Intersection (Left, Right : Set) возвращает Set;

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

Процедура Difference (Target : вход/выход Set;
Source : вход Set);

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

Функция Difference (Left, Right : Set) возвращает Set;

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

Процедура Symmetric_Difference (Target : вход/выход Set;
Source : вход Set);

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

Функция Symmetric_Difference (Left, Right : Set) возвращает Set;

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

Функция Overlap (Left, Right : Set) возвращает Boolean;

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

Функция Is_Subset (Subset : Set;
Of_Set : Set) возвращает Boolean;

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

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

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

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

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

Процедура Next (Position : вход/выход Cursor);

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

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

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

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

Функция Contains (Container : Set;
Item : Element_Type) возвращает Boolean;

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

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

Процедура Iterate
(Container : вход Set;
Process : не null доступная процедура (Position : вход Cursor));

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

Both Containers.Hashed_Set and Containers.Ordered_Set declare a nested generic package Generic_Keys, which provides operations that allow set manipulation in terms of a key (typically, a portion of an element) instead of a complete element. The formal function Key of Generic_Keys extracts a key value from an element. It is expected to return the same value each time it is called with a particular element. The behavior of Generic_Keys is unspecified if Key behaves in some other manner.

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

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

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

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

Процедура Replace (Container : вход/выход Set;
Key : вход Key_Type;
New_Item : вход Element_Type);

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

Процедура Update_Element_Preserving_Key
(Container : вход/выход Set;
Position : вход Cursor;
Process : не null доступная процедура
(Element : вход/выход Element_Type));

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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