1------------------------------------------------------------------------------ 2-- -- 3-- GNAT RUN-TIME COMPONENTS -- 4-- -- 5-- G N A T . S E T S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2018-2019, AdaCore -- 10-- -- 11-- GNAT is free software; you can redistribute it and/or modify it under -- 12-- terms of the GNU General Public License as published by the Free Soft- -- 13-- ware Foundation; either version 3, or (at your option) any later ver- -- 14-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 15-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 16-- or FITNESS FOR A PARTICULAR PURPOSE. -- 17-- -- 18-- As a special exception under Section 7 of GPL version 3, you are granted -- 19-- additional permissions described in the GCC Runtime Library Exception, -- 20-- version 3.1, as published by the Free Software Foundation. -- 21-- -- 22-- You should have received a copy of the GNU General Public License and -- 23-- a copy of the GCC Runtime Library Exception along with this program; -- 24-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- 25-- <http://www.gnu.org/licenses/>. -- 26-- -- 27-- GNAT was originally developed by the GNAT team at New York University. -- 28-- Extensive contributions were provided by Ada Core Technologies Inc. -- 29-- -- 30------------------------------------------------------------------------------ 31 32pragma Compiler_Unit_Warning; 33 34with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; 35 36package GNAT.Sets is 37 38 -------------------- 39 -- Membership_Set -- 40 -------------------- 41 42 -- The following package offers a membership set abstraction with the 43 -- following characteristics: 44 -- 45 -- * Creation of multiple instances, of different sizes. 46 -- * Iterable elements. 47 -- 48 -- The following use pattern must be employed with this set: 49 -- 50 -- Set : Instance := Create (<some size>); 51 -- 52 -- <various operations> 53 -- 54 -- Destroy (Set); 55 -- 56 -- The destruction of the set reclaims all storage occupied by it. 57 58 generic 59 type Element_Type is private; 60 61 with function "=" 62 (Left : Element_Type; 63 Right : Element_Type) return Boolean; 64 65 with function Hash (Key : Element_Type) return Bucket_Range_Type; 66 -- Map an arbitrary key into the range of buckets 67 68 package Membership_Set is 69 70 -------------------- 71 -- Set operations -- 72 -------------------- 73 74 -- The following type denotes a membership set handle. Each instance 75 -- must be created using routine Create. 76 77 type Instance is private; 78 Nil : constant Instance; 79 80 function Contains (S : Instance; Elem : Element_Type) return Boolean; 81 -- Determine whether membership set S contains element Elem 82 83 function Create (Initial_Size : Positive) return Instance; 84 -- Create a new membership set with bucket capacity Initial_Size. This 85 -- routine must be called at the start of the membership set's lifetime. 86 87 procedure Delete (S : Instance; Elem : Element_Type); 88 -- Delete element Elem from membership set S. The routine has no effect 89 -- if the element is not present in the membership set. This action will 90 -- raise Iterated if the membership set has outstanding iterators. 91 92 procedure Destroy (S : in out Instance); 93 -- Destroy the contents of membership set S, rendering it unusable. This 94 -- routine must be called at the end of the membership set's lifetime. 95 -- This action will raise Iterated if the hash table has outstanding 96 -- iterators. 97 98 procedure Insert (S : Instance; Elem : Element_Type); 99 -- Insert element Elem in membership set S. The routine has no effect 100 -- if the element is already present in the membership set. This action 101 -- will raise Iterated if the membership set has outstanding iterators. 102 103 function Is_Empty (S : Instance) return Boolean; 104 -- Determine whether set S is empty 105 106 function Size (S : Instance) return Natural; 107 -- Obtain the number of elements in membership set S 108 109 ------------------------- 110 -- Iterator operations -- 111 ------------------------- 112 113 -- The following type represents an element iterator. An iterator locks 114 -- all mutation operations, and unlocks them once it is exhausted. The 115 -- iterator must be used with the following pattern: 116 -- 117 -- Iter := Iterate (My_Set); 118 -- while Has_Next (Iter) loop 119 -- Next (Iter, Element); 120 -- end loop; 121 -- 122 -- It is possible to advance the iterator by using Next only, however 123 -- this risks raising Iterator_Exhausted. 124 125 type Iterator is private; 126 127 function Iterate (S : Instance) return Iterator; 128 -- Obtain an iterator over the elements of membership set S. This action 129 -- locks all mutation functionality of the associated membership set. 130 131 function Has_Next (Iter : Iterator) return Boolean; 132 -- Determine whether iterator Iter has more keys to examine. If the 133 -- iterator has been exhausted, restore all mutation functionality of 134 -- the associated membership set. 135 136 procedure Next (Iter : in out Iterator; Elem : out Element_Type); 137 -- Return the current element referenced by iterator Iter and advance 138 -- to the next available element. If the iterator has been exhausted 139 -- and further attempts are made to advance it, this routine restores 140 -- mutation functionality of the associated membership set, and then 141 -- raises Iterator_Exhausted. 142 143 private 144 package Hashed_Set is new Dynamic_HTable 145 (Key_Type => Element_Type, 146 Value_Type => Boolean, 147 No_Value => False, 148 Expansion_Threshold => 1.5, 149 Expansion_Factor => 2, 150 Compression_Threshold => 0.3, 151 Compression_Factor => 2, 152 "=" => "=", 153 Hash => Hash); 154 155 type Instance is new Hashed_Set.Instance; 156 Nil : constant Instance := Instance (Hashed_Set.Nil); 157 158 type Iterator is new Hashed_Set.Iterator; 159 end Membership_Set; 160 161end GNAT.Sets; 162