Merge branch 'release-2.140.101'
[feisty_meow.git] / nucleus / library / structures / set.h
1 #ifndef SET_CLASS
2 #define SET_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : set                                                               *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1996-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include "object_packers.h"
19 #include "string_array.h"
20
21 #include <basis/astring.h>
22 #include <basis/contracts.h>
23 #include <basis/definitions.h>
24 #include <basis/guards.h>
25
26 namespace structures {
27
28 //! Emulates a mathematical set, providing several standard set operations.
29 /*!
30   Note: this is not an efficient object and it should not be used for
31   sets of non-trivial sizes.
32 */
33
34 template <class contents>
35 class set : public basis::array<contents>
36 {
37 public:
38   //! Constructs a set with "num" elements, copying them from "init".
39   /*! Be very careful to ensure that the array "init" has sufficient length
40   for "num" elements to be copied from it. */
41   set(int num = 0, const contents *init = NULL_POINTER,
42       basis::un_short flags = basis::array<contents>::EXPONE)
43   : basis::array<contents>(num, init, flags) {}
44
45   ~set() {}  //!< Destroys any storage held for the set.
46
47   int elements() const { return this->length(); }
48     //!< Returns the number of elements in this set.
49
50   bool empty() const { return elements() == 0; }
51     //!< Returns true if the set has no elements.
52   bool non_empty() const { return elements() != 0; }
53     //!< Returns true if the set has some elements.
54
55   void clear() { this->reset(); }  //!< Empties out this set.
56
57   bool member(const contents &to_test) const;
58     //!< Returns true if the item "to_test" is a member of this set.
59   
60   bool add(const contents &to_add);
61     //!< Adds a new element "to_add" to the set.
62     /*!< This always succeeds, but will return true if the item was not
63     already present. */
64
65   set &operator += (const contents &to_add)
66       { add(to_add); return *this; }
67     //!< An algebraic operator synonym for add() that operates on the contents.
68   set &operator += (const set &to_add)
69       { unionize(to_add); return *this; }
70     //!< An algebraic operator synonym for add() that operates on a set.
71
72   bool remove(const contents &to_remove);
73     //!< Removes the item "to_remove" from the set.
74     /*!< If it was not present, false is returned and the set is unchanged. */
75
76   set &operator -= (const contents &to_zap)
77       { remove(to_zap); return *this; }
78     //!< An algebraic operator synonym for remove that operates on the contents.
79   set &operator -= (const set &to_zap)
80       { differentiate(to_zap); return *this; }
81     //!< An algebraic operator synonym for remove that operates on a set.
82
83   set set_union(const set &union_with) const;
84     //!< Implements the set union of "this" with "union_with".
85     /*!< This returns the set formed from the union of "this" set with the set
86     specified in "union_with".  (unfortunately, the name "set_union" must
87     be used to distinguish from the C keyword "union".) */
88
89   void unionize(const set &union_with);
90     //!< Makes "this" set a union of "this" and "union_with".
91
92   set operator + (const set &uw) const { return set_union(uw); }
93     //!< A synonym for set_union.
94
95   set intersection(const set &intersect_with) const;
96     //!< Returns the intersection of "this" with the set in "intersect_with".
97
98   set operator * (const set &iw) const { return intersection(iw); }
99     //!< A synonym for intersection.
100
101   set difference(const set &differ_with) const;
102     //!< Returns the difference of this with "differ_with".
103     /*!< Difference is defined as the subset of elements in "this" that are not
104     also in "differ_with". */
105
106   void differentiate(const set &differ_with);
107     //!< Makes "this" set equal to the difference of "this" and "differ_with".
108     /*!< That is, after the call, "this" will only contain elements that were
109     not also in "differ_with". */
110
111   set operator - (const set &dw) const { return difference(dw); }
112     //!< A synonym for difference.
113
114   int find(const contents &to_find) const;
115     //!< Returns the integer index of the item "to_find" in this set.
116     /*!< This returns a negative number if the index cannot be found.  Note
117     that this only makes sense within our particular implementation of set as
118     an array. */
119
120   //! Zaps the entry at the specified "index".
121   /*! This also treats the set like an array.  The index must be within the
122   bounds of the existing members. */
123   bool remove_index(int index)
124       { return this->zap(index, index) == basis::common::OKAY; }
125 };
126
127 //////////////
128
129 //! provides a way to pack any set that stores packable objects.
130 template <class contents>
131 void pack(basis::byte_array &packed_form, const set<contents> &to_pack)
132 {
133   obscure_attach(packed_form, to_pack.elements());
134   for (int i = 0; i < to_pack.elements(); i++) to_pack[i].pack(packed_form);
135 }
136
137 //! provides a way to unpack any set that stores packable objects.
138 template <class contents>
139 bool unpack(basis::byte_array &packed_form, set<contents> &to_unpack)
140 {
141   to_unpack.clear();
142   basis::un_int len;
143   if (!obscure_detach(packed_form, len)) return false;
144   contents to_fill;
145   for (int i = 0; i < (int)len; i++) {
146     if (!to_fill.unpack(packed_form)) return false;
147     to_unpack.add(to_fill);
148   }
149   return true;
150 }
151
152 //////////////
153
154 //! A simple object that wraps a templated set of ints.
155 class int_set : public set<int>, public virtual basis::root_object
156 {
157 public:
158   int_set() {}
159     //!< Constructs an empty set of ints.
160   int_set(const set<int> &to_copy) : set<int>(to_copy) {}
161     //!< Constructs a copy of the "to_copy" array.
162
163   DEFINE_CLASS_NAME("int_set");
164 };
165
166 //! A simple object that wraps a templated set of strings.
167 class string_set : public set<basis::astring>, public virtual basis::packable
168 {
169 public:
170   string_set() {}
171     //!< Constructs an empty set of strings.
172   string_set(const set<basis::astring> &to_copy)
173       : set<basis::astring>(to_copy) {}
174     //!< Constructs a copy of the "to_copy" array.
175   string_set(const string_array &to_copy) {
176     for (int i = 0; i < to_copy.length(); i++)
177       add(to_copy[i]);
178   }
179
180   DEFINE_CLASS_NAME("string_set");
181
182   bool operator == (const string_set &compare) const {
183           for (int i = 0; i < elements(); i++)
184             if (get(i) != compare.get(i)) return false;
185     return true;
186   }
187
188   operator string_array() const {
189     string_array to_return;
190     for (int i = 0; i < length(); i++)
191       to_return += get(i);
192     return to_return;
193   }
194
195   virtual void pack(basis::byte_array &packed_form) const
196       { structures::pack(packed_form, *this); }
197   virtual bool unpack(basis::byte_array &packed_form)
198       { return structures::unpack(packed_form, *this); }
199   virtual int packed_size() const {
200     int to_return = sizeof(int) * 2;  // length packed in, using obscure.
201     for (int i = 0; i < length(); i++)
202       to_return += get(i).length() + 1;
203     return to_return;
204   }
205 };
206
207 //! A set of pointers that hides the platform's pointer size.
208 class pointer_set : public set<void *>
209 {
210 public:
211   pointer_set() {}
212     //!< Constructs an empty set of void pointers.
213   pointer_set(const set<void *> &to_copy) : set<void *>(to_copy)
214       {}
215     //!< Constructs a copy of the "to_copy" array.
216 };
217
218 //////////////
219
220 // implementation for longer functions is below...
221
222 template <class contents>
223 bool set<contents>::member(const contents &to_test) const
224 {
225   for (int i = 0; i < elements(); i++)
226     if (to_test == this->get(i))
227       return true;
228   return false;
229 }
230
231 template <class contents>
232 bool set<contents>::add(const contents &to_add)
233 {
234   if (member(to_add)) return false; 
235   this->concatenate(to_add);
236   return true;
237 }
238
239 template <class contents>
240 int set<contents>::find(const contents &to_find) const
241 {
242   for (int i = 0; i < elements(); i++)
243     if (to_find == this->get(i))
244       return i;
245   return basis::common::NOT_FOUND;
246 }
247
248 template <class contents>
249 bool set<contents>::remove(const contents &to_remove)
250 {
251   for (int i = 0; i < elements(); i++)
252     if (to_remove == this->get(i)) {
253       this->zap(i, i);
254       return true;
255     }
256   return false;
257 }
258
259 template <class contents>
260 set<contents> set<contents>::intersection(const set &intersect_with) const
261 {
262   set<contents> created(0, NULL_POINTER, this->flags());
263   const set *smaller = this;
264   const set *larger = &intersect_with;
265   if (elements() > intersect_with.elements()) {
266     // switch the smaller one into place.
267     smaller = &intersect_with;
268     larger = this;
269   }
270   for (int i = 0; i < smaller->length(); i++)
271     if (larger->member(smaller->get(i)))
272       created.concatenate(smaller->get(i));
273   return created;
274 }
275
276 template <class contents>
277 set<contents> set<contents>::set_union(const set &union_with) const
278 {
279   set<contents> created = *this;
280   for (int i = 0; i < union_with.elements(); i++)
281     created.add(union_with.get(i));
282   return created;
283 }
284
285 template <class contents>
286 void set<contents>::unionize(const set &union_with)
287 {
288   for (int i = 0; i < union_with.elements(); i++)
289     add(union_with.get(i));
290 }
291
292 template <class contents>
293 set<contents> set<contents>::difference(const set &differ_with) const
294 {
295   set<contents> created = *this;
296   for (int i = 0; i < differ_with.elements(); i++) {
297     if (created.member(differ_with[i]))
298       created.remove(differ_with[i]);
299   }
300   return created;
301 }
302
303 template <class contents>
304 void set<contents>::differentiate(const set &differ_with)
305 {
306   for (int i = 0; i < differ_with.elements(); i++) {
307     if (member(differ_with[i]))
308       remove(differ_with[i]);
309   }
310 }
311
312 }  // namespace.
313
314 #endif
315