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