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