1-- Copyright 1994 Grady Booch 2-- Copyright 1998-2014 Simon Wright <simon@pushface.org> 3 4-- This package is free software; you can redistribute it and/or 5-- modify it under terms of the GNU General Public License as 6-- published by the Free Software Foundation; either version 2, or 7-- (at your option) any later version. This package is distributed in 8-- the hope that it will be useful, but WITHOUT ANY WARRANTY; without 9-- even the implied warranty of MERCHANTABILITY or FITNESS FOR A 10-- PARTICULAR PURPOSE. See the GNU General Public License for more 11-- details. You should have received a copy of the GNU General Public 12-- License distributed with this package; see file COPYING. If not, 13-- write to the Free Software Foundation, 59 Temple Place - Suite 14-- 330, Boston, MA 02111-1307, USA. 15 16-- As a special exception, if other files instantiate generics from 17-- this unit, or you link this unit with other files to produce an 18-- executable, this unit does not by itself cause the resulting 19-- executable to be covered by the GNU General Public License. This 20-- exception does not however invalidate any other reasons why the 21-- executable file might be covered by the GNU Public License. 22 23with BC.Support.Bounded_Hash_Tables; 24 25generic 26 with function Hash (V : Item) return Natural is <>; 27 Buckets : Positive; 28 Maximum_Size : Positive; 29package BC.Containers.Sets.Bounded is 30 31 pragma Preelaborate; 32 33 -- A set denotes a collection of items, drawn from some 34 -- well-defined universe. A set may not contain duplicate items. 35 36 -- The hash function (the generic parameter Hash) determines the 37 -- allocation of items to hash buckets. The value returned must 38 -- not change during the lifetime of a given Item. The range of 39 -- hash values need not be constrained to the number of buckets in 40 -- the set. 41 42 -- The hash function must satisfy the condition that, for objects 43 -- A and B, if A = B, then Hash (A) must equal Hash (B). The hash 44 -- function should attempt to spread the set of possible items 45 -- uniformly across the number of buckets. The quality of the hash 46 -- function has a significant impact upon performance. 47 48 type Unconstrained_Set 49 (Number_Of_Buckets : Positive; 50 Maximum_Size : Positive) is new Abstract_Set with private; 51 52 subtype Set is Unconstrained_Set (Number_Of_Buckets => Buckets, 53 Maximum_Size => Maximum_Size); 54 55 function Null_Container return Unconstrained_Set; 56 -- Note, this function has to be provided but the object returned 57 -- is in fact a Set (ie, it is constrained). 58 59 procedure Clear (S : in out Unconstrained_Set); 60 -- Empty the set of all items. 61 62 procedure Add (S : in out Unconstrained_Set; I : Item; Added : out Boolean); 63 -- Add the item to the set. If the item is not already a distinct 64 -- member of the set, copy the item and add it to the set and set 65 -- Added to True. If the item already exists, then set Added to 66 -- False. 67 68 procedure Add (S : in out Unconstrained_Set; I : Item); 69 -- Add the item to the set. If the item is not already a distinct 70 -- member of the set, copy the item and add it to the set. 71 72 procedure Remove (S : in out Unconstrained_Set; I : Item); 73 -- If the item is not a member of the set, raise 74 -- BC.Not_Found. Otherwise, remove the item from the set. 75 76 function Available (S : Unconstrained_Set) return Natural; 77 -- Return the number of unused slots in the set. 78 79 function Extent (S : Unconstrained_Set) return Natural; 80 -- Return the number of distinct items in the set. 81 82 function Is_Empty (S : Unconstrained_Set) return Boolean; 83 -- Return True if and only if there are no items in the set. 84 85 function Is_Member (S : Unconstrained_Set; I : Item) return Boolean; 86 -- Return True if and only if the item exists in the set. 87 88 function New_Iterator 89 (For_The_Set : Unconstrained_Set) return Iterator'Class; 90 -- Return a reset Iterator bound to the specific Set. 91 92private 93 94 package Items is new BC.Support.Bounded_Hash_Tables.Item_Signature 95 (Item => Item, 96 Item_Ptr => Item_Ptr, 97 Eq => Containers."=", 98 Hash => Hash); 99 100 -- We need a dummy type for the Value component of the hash table. 101 type Dummy is null record; 102 type Dummy_Ptr is access all Dummy; 103 package Values is new BC.Support.Bounded_Hash_Tables.Value_Signature 104 (Value => Dummy, 105 Value_Ptr => Dummy_Ptr, 106 Eq => "="); 107 108 package Tables is new BC.Support.Bounded_Hash_Tables.Tables 109 (Items => Items, 110 Values => Values); 111 112 type Unconstrained_Set 113 (Number_Of_Buckets : Positive; 114 Maximum_Size : Positive) 115 is new Abstract_Set with record 116 Rep : Tables.Table (Number_Of_Buckets => Buckets, 117 Maximum_Size => Maximum_Size); 118 end record; 119 120 type Bounded_Set_Iterator is new Set_Iterator with null record; 121 122 procedure Reset (It : in out Bounded_Set_Iterator); 123 124 procedure Next (It : in out Bounded_Set_Iterator); 125 126 function Is_Done (It : Bounded_Set_Iterator) return Boolean; 127 128 function Current_Item (It : Bounded_Set_Iterator) return Item; 129 130 function Current_Item_Ptr (It : Bounded_Set_Iterator) return Item_Ptr; 131 132 procedure Delete_Item_At (It : in out Bounded_Set_Iterator); 133 134end BC.Containers.Sets.Bounded; 135