| ------------------------------------------------------------------------------ |
| -- -- |
| -- GNAT RUN-TIME COMPONENTS -- |
| -- -- |
| -- G N A T . S E T S -- |
| -- -- |
| -- S p e c -- |
| -- -- |
| -- Copyright (C) 2018-2021, AdaCore -- |
| -- -- |
| -- GNAT is free software; you can redistribute it and/or modify it under -- |
| -- terms of the GNU General Public License as published by the Free Soft- -- |
| -- ware Foundation; either version 3, or (at your option) any later ver- -- |
| -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- |
| -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- |
| -- or FITNESS FOR A PARTICULAR PURPOSE. -- |
| -- -- |
| -- As a special exception under Section 7 of GPL version 3, you are granted -- |
| -- additional permissions described in the GCC Runtime Library Exception, -- |
| -- version 3.1, as published by the Free Software Foundation. -- |
| -- -- |
| -- You should have received a copy of the GNU General Public License and -- |
| -- a copy of the GCC Runtime Library Exception along with this program; -- |
| -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- |
| -- <http://www.gnu.org/licenses/>. -- |
| -- -- |
| -- GNAT was originally developed by the GNAT team at New York University. -- |
| -- Extensive contributions were provided by Ada Core Technologies Inc. -- |
| -- -- |
| ------------------------------------------------------------------------------ |
| |
| pragma Compiler_Unit_Warning; |
| |
| with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; |
| |
| package GNAT.Sets is |
| |
| -------------------- |
| -- Membership_Set -- |
| -------------------- |
| |
| -- The following package offers a membership set abstraction with the |
| -- following characteristics: |
| -- |
| -- * Creation of multiple instances, of different sizes |
| -- * Iterable elements |
| -- |
| -- The following use pattern must be employed with this set: |
| -- |
| -- Set : Membership_Set := Create (<some size>); |
| -- |
| -- <various operations> |
| -- |
| -- Destroy (Set); |
| -- |
| -- The destruction of the set reclaims all storage occupied by it. |
| |
| generic |
| type Element_Type is private; |
| |
| with function "=" |
| (Left : Element_Type; |
| Right : Element_Type) return Boolean; |
| |
| with function Hash (Key : Element_Type) return Bucket_Range_Type; |
| -- Map an arbitrary key into the range of buckets |
| |
| package Membership_Sets is |
| |
| -------------------- |
| -- Set operations -- |
| -------------------- |
| |
| -- The following type denotes a membership set handle. Each instance |
| -- must be created using routine Create. |
| |
| type Membership_Set is private; |
| Nil : constant Membership_Set; |
| |
| function Contains |
| (S : Membership_Set; |
| Elem : Element_Type) return Boolean; |
| -- Determine whether membership set S contains element Elem |
| |
| function Create (Initial_Size : Positive) return Membership_Set; |
| -- Create a new membership set with bucket capacity Initial_Size. This |
| -- routine must be called at the start of the membership set's lifetime. |
| |
| procedure Delete |
| (S : Membership_Set; |
| Elem : Element_Type); |
| -- Delete element Elem from membership set S. The routine has no effect |
| -- if the element is not present in the membership set. This action will |
| -- raise Iterated if the membership set has outstanding iterators. |
| |
| procedure Destroy (S : in out Membership_Set); |
| -- Destroy the contents of membership set S, rendering it unusable. This |
| -- routine must be called at the end of the membership set's lifetime. |
| -- This action will raise Iterated if the hash table has outstanding |
| -- iterators. |
| |
| procedure Insert |
| (S : Membership_Set; |
| Elem : Element_Type); |
| -- Insert element Elem in membership set S. The routine has no effect |
| -- if the element is already present in the membership set. This action |
| -- will raise Iterated if the membership set has outstanding iterators. |
| |
| function Is_Empty (S : Membership_Set) return Boolean; |
| -- Determine whether set S is empty |
| |
| function Present (S : Membership_Set) return Boolean; |
| -- Determine whether set S exists |
| |
| procedure Reset (S : Membership_Set); |
| -- Destroy the contents of membership set S, and reset it to its initial |
| -- created state. This action will raise Iterated if the membership set |
| -- has outstanding iterators. |
| |
| function Size (S : Membership_Set) return Natural; |
| -- Obtain the number of elements in membership set S |
| |
| ------------------------- |
| -- Iterator operations -- |
| ------------------------- |
| |
| -- The following type represents an element iterator. An iterator locks |
| -- all mutation operations, and unlocks them once it is exhausted. The |
| -- iterator must be used with the following pattern: |
| -- |
| -- Iter := Iterate (My_Set); |
| -- while Has_Next (Iter) loop |
| -- Next (Iter, Element); |
| -- end loop; |
| -- |
| -- It is possible to advance the iterator by using Next only, however |
| -- this risks raising Iterator_Exhausted. |
| |
| type Iterator is private; |
| |
| function Iterate (S : Membership_Set) return Iterator; |
| -- Obtain an iterator over the elements of membership set S. This action |
| -- locks all mutation functionality of the associated membership set. |
| |
| function Has_Next (Iter : Iterator) return Boolean; |
| -- Determine whether iterator Iter has more keys to examine. If the |
| -- iterator has been exhausted, restore all mutation functionality of |
| -- the associated membership set. |
| |
| procedure Next (Iter : in out Iterator; Elem : out Element_Type); |
| -- Return the current element referenced by iterator Iter and advance |
| -- to the next available element. If the iterator has been exhausted |
| -- and further attempts are made to advance it, this routine restores |
| -- mutation functionality of the associated membership set, and then |
| -- raises Iterator_Exhausted. |
| |
| private |
| procedure Destroy (B : in out Boolean); |
| -- Destroy boolean B |
| |
| package Hashed_Set is new Dynamic_Hash_Tables |
| (Key_Type => Element_Type, |
| Value_Type => Boolean, |
| No_Value => False, |
| Expansion_Threshold => 1.5, |
| Expansion_Factor => 2, |
| Compression_Threshold => 0.3, |
| Compression_Factor => 2, |
| "=" => "=", |
| Destroy_Value => Destroy, |
| Hash => Hash); |
| |
| type Membership_Set is new Hashed_Set.Dynamic_Hash_Table; |
| Nil : constant Membership_Set := Membership_Set (Hashed_Set.Nil); |
| |
| type Iterator is new Hashed_Set.Iterator; |
| end Membership_Sets; |
| |
| end GNAT.Sets; |
