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.Dynamic; 24with BC.Support.Hash_Tables; 25with System.Storage_Pools; 26 27generic 28 with function Hash (V : Item) return Natural is <>; 29 Buckets : Positive; 30 Storage : in out System.Storage_Pools.Root_Storage_Pool'Class; 31 Initial_Size : Positive := 10; 32package BC.Containers.Sets.Dynamic is 33 34 pragma Preelaborate; 35 36 -- A set denotes a collection of items, drawn from some 37 -- well-defined universe. A set may not contain duplicate items. 38 39 -- The hash function (the generic parameter Hash) determines the 40 -- allocation of items to hash buckets. The value returned must 41 -- not change during the lifetime of a given Item. The range of 42 -- hash values need not be constrained to the number of buckets in 43 -- the set. 44 45 -- The hash function must satisfy the condition that, for objects 46 -- A and B, if A = B, then Hash (A) must equal Hash (B). The hash 47 -- function should attempt to spread the set of possible items 48 -- uniformly across the number of buckets. The quality of the hash 49 -- function has a significant impact upon performance. 50 51 type Set is new Abstract_Set with private; 52 53 function Null_Container return Set; 54 55 function Create (Size : Positive) return Set; 56 -- Creates a new Dynamic Set each of whose buckets is preallocated 57 -- for 'Size' elements 58 59 procedure Clear (S : in out Set); 60 -- Empty the set of all items. 61 62 procedure Add (S : in out 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 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 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 Extent (S : Set) return Natural; 77 -- Return the number of items in the set. 78 79 function Is_Empty (S : Set) return Boolean; 80 -- Return True if and only if there are no items in the set. 81 82 function Is_Member (S : Set; I : Item) return Boolean; 83 -- Return True if and only if the item exists in the set. 84 85 procedure Preallocate (S : in out Set; Size : Positive); 86 -- Allocates 'Size' additional storage elements for each bucket of 87 -- the Set. 88 89 procedure Set_Chunk_Size (S : in out Set; Size : Positive); 90 -- Establishes the Size each bucket of the Set will grow if the 91 -- Set exhausts its current size. 92 93 function Chunk_Size (S : Set) return Positive; 94 -- Returns the Chunk_Size. 95 96 function New_Iterator (For_The_Set : Set) return Iterator'Class; 97 -- Return a reset Iterator bound to the specific Set. 98 99private 100 101 package IC is new BC.Support.Dynamic (Item => Item, 102 Item_Ptr => Item_Ptr, 103 Storage => Storage, 104 Initial_Size => Initial_Size); 105 package Items is new BC.Support.Hash_Tables.Item_Signature 106 (Item => Item, 107 Item_Ptr => Item_Ptr, 108 Eq => Containers."=", 109 Hash => Hash, 110 Item_Container => IC.Dyn_Node, 111 Clear => IC.Clear, 112 Insert => IC.Insert, 113 Append => IC.Append, 114 Remove => IC.Remove, 115 Replace => IC.Replace, 116 Length => IC.Length, 117 Item_At => IC.Item_At, 118 Access_Item_At => IC.Item_At, 119 Location => IC.Location); 120 121 -- We need a dummy type for the Value component of the hash table. 122 type Dummy is null record; 123 type Dummy_Ptr is access all Dummy; 124 package VC is new BC.Support.Dynamic (Item => Dummy, 125 Item_Ptr => Dummy_Ptr, 126 Storage => Storage, 127 Initial_Size => Initial_Size); 128 package Values is new BC.Support.Hash_Tables.Value_Signature 129 (Value => Dummy, 130 Value_Ptr => Dummy_Ptr, 131 Eq => "=", 132 Value_Container => VC.Dyn_Node, 133 Clear => VC.Clear, 134 Insert => VC.Insert, 135 Append => VC.Append, 136 Remove => VC.Remove, 137 Replace => VC.Replace, 138 Length => VC.Length, 139 Item_At => VC.Item_At, 140 Access_Item_At => VC.Item_At, 141 Location => VC.Location); 142 143 package Tables is new BC.Support.Hash_Tables.Tables 144 (Items => Items, 145 Values => Values); 146 147 type Set is new Abstract_Set with record 148 Rep : Tables.Table (Number_Of_Buckets => Buckets); 149 end record; 150 151 -- Iterators 152 153 type Dynamic_Set_Iterator is new Set_Iterator with null record; 154 155 procedure Reset (It : in out Dynamic_Set_Iterator); 156 157 procedure Next (It : in out Dynamic_Set_Iterator); 158 159 function Is_Done (It : Dynamic_Set_Iterator) return Boolean; 160 161 function Current_Item (It : Dynamic_Set_Iterator) return Item; 162 163 function Current_Item_Ptr (It : Dynamic_Set_Iterator) return Item_Ptr; 164 165 procedure Delete_Item_At (It : in out Dynamic_Set_Iterator); 166 167end BC.Containers.Sets.Dynamic; 168