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.Sets is
25
26   pragma Preelaborate;
27
28   --  A set denotes a collection of items, drawn from some
29   --  well-defined universe. A set may not contain duplicate items.
30
31   --  The parameter Item denotes the universe from which the set
32   --  draws its items. Items may be a primitive type or user-defined.
33
34   type Abstract_Set is abstract new Container with private;
35
36   function Are_Equal (L, R : Abstract_Set'Class) return Boolean;
37   --  Return True if and only if both sets have the same number of
38   --  distinct items, and the same items themselves; return False
39   --  otherwise.  Can't call this "=" because of the standard one for
40   --  Set.
41
42   procedure Clear (S : in out Abstract_Set) is abstract;
43   --  Empty the set of all items.
44
45   procedure Add (S : in out Abstract_Set;
46                  I : Item;
47                  Added : out Boolean) is abstract;
48   --  Add the item to the set. If the item is not already a distinct
49   --  member of the set, copy the item and add it to the set and set
50   --  Added to True. If the item already exists, then set Added to
51   --  False.
52
53   procedure Add (S : in out Abstract_Set; I : Item) is abstract;
54   --  Add the item to the set. If the item is not already a distinct
55   --  member of the set, copy the item and add it to the set.
56
57   procedure Remove (S : in out Abstract_Set; I : Item) is abstract;
58   --  If the item is not a member of the set, raise
59   --  BC.Not_Found. Otherwise, remove the item from the set.
60
61   procedure Union (S : in out Abstract_Set'Class; O : Abstract_Set'Class);
62   --  Perform a logical set union; at the completion of this
63   --  operation, the set S contains the items found in its original
64   --  state combined with the set O (but without duplication). For
65   --  each item in the set O, if the item is not already a distinct
66   --  member of the set S, copy the item and add it to the set S. If
67   --  the item already is a member, do nothing.
68
69   procedure Intersection (S : in out Abstract_Set'Class;
70                           O : Abstract_Set'Class);
71   --  Perform a logical set intersection; at the completion of this
72   --  operation, the set S contains the items found both in its
73   --  original state and in the set O. For each item in the set O, if
74   --  the item is not already a distinct member of the set S, do
75   --  nothing. If the item already is a member of S, do
76   --  nothing. Items in the set S but not in the set O are also
77   --  removed.
78
79   procedure Difference (S : in out Abstract_Set'Class;
80                         O : Abstract_Set'Class);
81   --  Perform a logical set difference; at the completion of this
82   --  operation, the set S contains the items found in its original
83   --  state, less those found in the set O. For each item in the set
84   --  O, if the item is not already a distinct member of the set S,
85   --  do nothing. If the item is a member, remove the item from the
86   --  set S.
87
88   function Available (S : Abstract_Set) return Natural;
89   --  Return the number of unused slots in the set.
90
91   function Extent (S : Abstract_Set) return Natural is abstract;
92   --  Return the number of distinct items in the set.
93
94   function Is_Empty (S : Abstract_Set) return Boolean is abstract;
95   --  Return True if and only if there are no items in the set.
96
97   function Is_Member (S : Abstract_Set; I : Item) return Boolean is abstract;
98   --  Return True if and only if the item exists in the set.
99
100   function Is_Subset (S : Abstract_Set'Class;
101                       O : Abstract_Set'Class) return Boolean;
102   --  Return True if and only if all the items in the set S are also
103   --  in the set O.
104
105   function Is_Proper_Subset (S : Abstract_Set'Class;
106                              O : Abstract_Set'Class) return Boolean;
107   --  Return True if and only if all the items in the set S are also
108   --  in the set O, and there is at least one item in O that is not
109   --  in S.
110
111private
112
113   type Abstract_Set is abstract new Container with null record;
114
115   type Set_Iterator is abstract new Iterator with record
116      Bucket_Index : Natural := 0;
117      Index : Natural := 0;
118   end record;
119
120end BC.Containers.Sets;
121