set.h

Go to the documentation of this file.

#ifndef SET_CLASS
#define SET_CLASS
 
/*****************************************************************************\
*                                                                             *
*  Name   : set                                                               *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1996-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/
 
#include "object_packers.h"
#include "string_array.h"
 
#include <basis/astring.h>
#include <basis/contracts.h>
#include <basis/definitions.h>
#include <basis/guards.h>
 
namespace structures {
 
 
template <class contents>
class set : public basis::array<contents>
{
public:
 
  set(int num = 0, const contents *init = NULL_POINTER,
      basis::un_short flags = basis::array<contents>::EXPONE)
  : basis::array<contents>(num, init, flags) {}
 
  ~set() {}  
 
  int elements() const { return this->length(); }
 
  bool empty() const { return elements() == 0; }
  bool non_empty() const { return elements() != 0; }
 
  void clear() { this->reset(); }  
 
  bool member(const contents &to_test) const;
  
  bool add(const contents &to_add);
 
  set &operator += (const contents &to_add)
      { add(to_add); return *this; }
  set &operator += (const set &to_add)
      { unionize(to_add); return *this; }
 
  bool remove(const contents &to_remove);
 
  set &operator -= (const contents &to_zap)
      { remove(to_zap); return *this; }
  set &operator -= (const set &to_zap)
      { differentiate(to_zap); return *this; }
 
  set set_union(const set &union_with) const;
 
  void unionize(const set &union_with);
 
  set operator + (const set &uw) const { return set_union(uw); }
 
  set intersection(const set &intersect_with) const;
 
  set operator * (const set &iw) const { return intersection(iw); }
 
  set difference(const set &differ_with) const;
 
  void differentiate(const set &differ_with);
 
  set operator - (const set &dw) const { return difference(dw); }
 
  int find(const contents &to_find) const;
 
 
  bool remove_index(int index)
      { return this->zap(index, index) == basis::common::OKAY; }
};
 
 
template <class contents>
void pack(basis::byte_array &packed_form, const set<contents> &to_pack)
{
  obscure_attach(packed_form, to_pack.elements());
  for (int i = 0; i < to_pack.elements(); i++) to_pack[i].pack(packed_form);
}
 
template <class contents>
bool unpack(basis::byte_array &packed_form, set<contents> &to_unpack)
{
  to_unpack.clear();
  basis::un_int len;
  if (!obscure_detach(packed_form, len)) return false;
  contents to_fill;
  for (int i = 0; i < (int)len; i++) {
    if (!to_fill.unpack(packed_form)) return false;
    to_unpack.add(to_fill);
  }
  return true;
}
 
 
class int_set : public set<int>, public virtual basis::root_object
{
public:
  int_set() {}
  int_set(const set<int> &to_copy) : set<int>(to_copy) {}
 
  DEFINE_CLASS_NAME("int_set");
};
 
class string_set : public set<basis::astring>, public virtual basis::packable
{
public:
  string_set() {}
  string_set(const set<basis::astring> &to_copy)
      : set<basis::astring>(to_copy) {}
  string_set(const string_array &to_copy) {
    for (int i = 0; i < to_copy.length(); i++)
      add(to_copy[i]);
  }
 
  DEFINE_CLASS_NAME("string_set");
 
  bool operator == (const string_set &compare) const {
    for (int i = 0; i < elements(); i++)
      if (get(i) != compare.get(i)) return false;
    return true;
  }
 
  operator string_array() const {
    string_array to_return;
    for (int i = 0; i < length(); i++)
      to_return += get(i);
    return to_return;
  }
 
  virtual void pack(basis::byte_array &packed_form) const
      { structures::pack(packed_form, *this); }
  virtual bool unpack(basis::byte_array &packed_form)
      { return structures::unpack(packed_form, *this); }
  virtual int packed_size() const {
    int to_return = sizeof(int) * 2;  // length packed in, using obscure.
    for (int i = 0; i < length(); i++)
      to_return += get(i).length() + 1;
    return to_return;
  }
};
 
class pointer_set : public set<void *>
{
public:
  pointer_set() {}
  pointer_set(const set<void *> &to_copy) : set<void *>(to_copy)
      {}
};
 
 
// implementation for longer functions is below...
 
template <class contents>
bool set<contents>::member(const contents &to_test) const
{
  for (int i = 0; i < elements(); i++)
    if (to_test == this->get(i))
      return true;
  return false;
}
 
template <class contents>
bool set<contents>::add(const contents &to_add)
{
  if (member(to_add)) return false; 
  this->concatenate(to_add);
  return true;
}
 
template <class contents>
int set<contents>::find(const contents &to_find) const
{
  for (int i = 0; i < elements(); i++)
    if (to_find == this->get(i))
      return i;
  return basis::common::NOT_FOUND;
}
 
template <class contents>
bool set<contents>::remove(const contents &to_remove)
{
  for (int i = 0; i < elements(); i++)
    if (to_remove == this->get(i)) {
      this->zap(i, i);
      return true;
    }
  return false;
}
 
template <class contents>
set<contents> set<contents>::intersection(const set &intersect_with) const
{
  set<contents> created(0, NULL_POINTER, this->flags());
  const set *smaller = this;
  const set *larger = &intersect_with;
  if (elements() > intersect_with.elements()) {
    // switch the smaller one into place.
    smaller = &intersect_with;
    larger = this;
  }
  for (int i = 0; i < smaller->length(); i++)
    if (larger->member(smaller->get(i)))
      created.concatenate(smaller->get(i));
  return created;
}
 
template <class contents>
set<contents> set<contents>::set_union(const set &union_with) const
{
  set<contents> created = *this;
  for (int i = 0; i < union_with.elements(); i++)
    created.add(union_with.get(i));
  return created;
}
 
template <class contents>
void set<contents>::unionize(const set &union_with)
{
  for (int i = 0; i < union_with.elements(); i++)
    add(union_with.get(i));
}
 
template <class contents>
set<contents> set<contents>::difference(const set &differ_with) const
{
  set<contents> created = *this;
  for (int i = 0; i < differ_with.elements(); i++) {
    if (created.member(differ_with[i]))
      created.remove(differ_with[i]);
  }
  return created;
}
 
template <class contents>
void set<contents>::differentiate(const set &differ_with)
{
  for (int i = 0; i < differ_with.elements(); i++) {
    if (member(differ_with[i]))
      remove(differ_with[i]);
  }
}
 
}  // namespace.
 
#endif