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 23generic 24package BC.Containers.Bags is 25 26 pragma Preelaborate; 27 28 -- A bag denotes a collection of items, drawn from some 29 -- well-defined universe. A bag may contain duplicate items. A bag 30 -- actually owns only one copy of each unique item: duplicates are 31 -- counted, but are not stored with the bag. 32 33 -- The parameter Item denotes the universe from which the bag 34 -- draws its items. Items may be a primitive type or user-defined. 35 36 type Abstract_Bag is abstract new Container with private; 37 38 function Are_Equal (L, R : Abstract_Bag'Class) return Boolean; 39 -- Return True if and only if both bags have the same number of 40 -- distinct items, and the same items themselves, each with the 41 -- same count; return False otherwise. 42 -- Can't call this "=" because of the standard one for Bag. 43 44 procedure Clear (B : in out Abstract_Bag) is abstract; 45 -- Empty the bag of all items. 46 47 procedure Add 48 (B : in out Abstract_Bag; I : Item; Added : out Boolean) is abstract; 49 -- Add the item to the bag. If the item is not already a distinct 50 -- member of the bag, copy the item and add it to the bag and set 51 -- Added to True. If the item already exists, then increment the 52 -- number of that item and set Added to False. 53 54 procedure Add (B : in out Abstract_Bag'Class; I : Item); 55 -- Add the item to the bag. If the item is not already a distinct 56 -- member of the bag, copy the item and add it to the bag; if it 57 -- is, increment the number of that item. 58 59 procedure Remove (B : in out Abstract_Bag; I : Item) is abstract; 60 -- If the item is not a member of the bag, raise 61 -- BC.Not_Found. Otherwise, if there is exactly one of the item in 62 -- the bag, remove the item in the bag; if there is more than one 63 -- of the item in the bag, simply decrement its number. 64 65 procedure Union (B : in out Abstract_Bag'Class; O : Abstract_Bag'Class); 66 -- Perform a logical bag union; at the completion of this 67 -- operation, the bag B contains the items and counts found in its 68 -- original state combined with the bag O. For each item in the 69 -- bag O, if the item is not already a distinct member of the bag 70 -- B, copy the item and add it and its count to the bag B. If the 71 -- item already is a member, increment its count in B. 72 73 procedure Intersection (B : in out Abstract_Bag'Class; 74 O : Abstract_Bag'Class); 75 -- Perform a logical bag intersection; at the completion of this 76 -- operation, the bag B contains the items found both in its 77 -- original state and in the bag O. For each item in the bag O, if 78 -- the item is not already a distinct member of the bag B, do 79 -- nothing. If the item already is a member of B, set its count to 80 -- the lower of the two counts. Items in the bag B but not in the 81 -- bag O are also removed. 82 83 procedure Difference (B : in out Abstract_Bag'Class; 84 O : Abstract_Bag'Class); 85 -- Perform a logical bag difference; at the completion of this 86 -- operation, the bag B contains the items found in its original 87 -- state, less those found in the bag O. For each item in the bag 88 -- O, if the item is not already a distinct member of the bag B, 89 -- do nothing. If the item is a member of the bag B with a count 90 -- less than that in the bag O, remove the item from the bag B. If 91 -- the item is a member of the bag B with a count more than that 92 -- in the bag O, decrement the count in the bag B by the count in 93 -- the bag O. 94 95 function Available (B : Abstract_Bag) return Natural; 96 -- Return the number of unused slots in the bag. 97 98 function Extent (B : Abstract_Bag) return Natural is abstract; 99 -- Return the number of distinct items in the bag. 100 101 function Total_Size (B : Abstract_Bag'Class) return Natural; 102 -- Return the total number of items in the bag. 103 104 function Count (B : Abstract_Bag; I : Item) return Natural is abstract; 105 -- Return the number of times the item occurs in the bag. 106 107 function Is_Empty (B : Abstract_Bag) return Boolean is abstract; 108 -- Return True if and only if there are no items in the bag. 109 110 function Is_Member (B : Abstract_Bag; I : Item) return Boolean is abstract; 111 -- Return True if and only if the item exists in the bag. 112 113 function Is_Subset 114 (B : Abstract_Bag'Class; O : Abstract_Bag'Class) return Boolean; 115 -- Return True if and only if the bag B has the same or fewer 116 -- distinct items than in the bag O and equal or less numbers of 117 -- each such item than in the bag O. 118 119 function Is_Proper_Subset 120 (B : Abstract_Bag'Class; O : Abstract_Bag'Class) return Boolean; 121 -- Return True if and only if all the distinct items in the bag B 122 -- are also in the bag O, and either at least one of the items in 123 -- the bag B has a lower number than the number in the bag O, or 124 -- there is at least one distinct item in the bag O that is not in 125 -- the bag B. 126 127private 128 129 type Abstract_Bag is abstract new Container with null record; 130 131 -- These subprograms are used in the implementation of the Bag 132 -- operations above. They would be abstract but that the ALRM 133 -- forbids that for private operations. 134 -- 135 -- These implementatiosm raise Should_Have_Been_Overridden. 136 137 procedure Attach (B : in out Abstract_Bag; I : Item; C : Positive); 138 139 procedure Detach (B : in out Abstract_Bag; I : Item); 140 141 procedure Set_Value (B : in out Abstract_Bag; I : Item; C : Positive); 142 143 type Bag_Iterator is abstract new Iterator with record 144 Bucket_Index : Natural := 0; 145 Index : Natural := 0; 146 end record; 147 148end BC.Containers.Bags; 149