#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 {

//! Emulates a mathematical set, providing several standard set operations.
/*!
  Note: this is not an efficient object and it should not be used for
  sets of non-trivial sizes.
*/

template <class contents>
class set : public basis::array<contents>
{
public:
  //! Constructs a set with "num" elements, copying them from "init".
  /*! Be very careful to ensure that the array "init" has sufficient length
  for "num" elements to be copied from it. */
  set(int num = 0, const contents *init = NULL_POINTER,
      basis::un_short flags = basis::array<contents>::EXPONE)
  : basis::array<contents>(num, init, flags) {}

  ~set() {}  //!< Destroys any storage held for the set.

  int elements() const { return this->length(); }
    //!< Returns the number of elements in this set.

  bool empty() const { return elements() == 0; }
    //!< Returns true if the set has no elements.
  bool non_empty() const { return elements() != 0; }
    //!< Returns true if the set has some elements.

  void clear() { this->reset(); }  //!< Empties out this set.

  bool member(const contents &to_test) const;
    //!< Returns true if the item "to_test" is a member of this set.
  
  bool add(const contents &to_add);
    //!< Adds a new element "to_add" to the set.
    /*!< This always succeeds, but will return true if the item was not
    already present. */

  set &operator += (const contents &to_add)
      { add(to_add); return *this; }
    //!< An algebraic operator synonym for add() that operates on the contents.
  set &operator += (const set &to_add)
      { unionize(to_add); return *this; }
    //!< An algebraic operator synonym for add() that operates on a set.

  bool remove(const contents &to_remove);
    //!< Removes the item "to_remove" from the set.
    /*!< If it was not present, false is returned and the set is unchanged. */

  set &operator -= (const contents &to_zap)
      { remove(to_zap); return *this; }
    //!< An algebraic operator synonym for remove that operates on the contents.
  set &operator -= (const set &to_zap)
      { differentiate(to_zap); return *this; }
    //!< An algebraic operator synonym for remove that operates on a set.

  set set_union(const set &union_with) const;
    //!< Implements the set union of "this" with "union_with".
    /*!< This returns the set formed from the union of "this" set with the set
    specified in "union_with".  (unfortunately, the name "set_union" must
    be used to distinguish from the C keyword "union".) */

  void unionize(const set &union_with);
    //!< Makes "this" set a union of "this" and "union_with".

  set operator + (const set &uw) const { return set_union(uw); }
    //!< A synonym for set_union.

  set intersection(const set &intersect_with) const;
    //!< Returns the intersection of "this" with the set in "intersect_with".

  set operator * (const set &iw) const { return intersection(iw); }
    //!< A synonym for intersection.

  set difference(const set &differ_with) const;
    //!< Returns the difference of this with "differ_with".
    /*!< Difference is defined as the subset of elements in "this" that are not
    also in "differ_with". */

  void differentiate(const set &differ_with);
    //!< Makes "this" set equal to the difference of "this" and "differ_with".
    /*!< That is, after the call, "this" will only contain elements that were
    not also in "differ_with". */

  set operator - (const set &dw) const { return difference(dw); }
    //!< A synonym for difference.

  int find(const contents &to_find) const;
    //!< Returns the integer index of the item "to_find" in this set.
    /*!< This returns a negative number if the index cannot be found.  Note
    that this only makes sense within our particular implementation of set as
    an array. */

  //! Zaps the entry at the specified "index".
  /*! This also treats the set like an array.  The index must be within the
  bounds of the existing members. */
  bool remove_index(int index)
      { return this->zap(index, index) == basis::common::OKAY; }
};

//////////////

//! provides a way to pack any set that stores packable objects.
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);
}

//! provides a way to unpack any set that stores packable objects.
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;
}

//////////////

//! A simple object that wraps a templated set of ints.
class int_set : public set<int>, public virtual basis::root_object
{
public:
  int_set() {}
    //!< Constructs an empty set of ints.
  int_set(const set<int> &to_copy) : set<int>(to_copy) {}
    //!< Constructs a copy of the "to_copy" array.

  DEFINE_CLASS_NAME("int_set");
};

//! A simple object that wraps a templated set of strings.
class string_set : public set<basis::astring>, public virtual basis::packable
{
public:
  string_set() {}
    //!< Constructs an empty set of strings.
  string_set(const set<basis::astring> &to_copy)
      : set<basis::astring>(to_copy) {}
    //!< Constructs a copy of the "to_copy" array.
  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;
  }
};

//! A set of pointers that hides the platform's pointer size.
class pointer_set : public set<void *>
{
public:
  pointer_set() {}
    //!< Constructs an empty set of void pointers.
  pointer_set(const set<void *> &to_copy) : set<void *>(to_copy)
      {}
    //!< Constructs a copy of the "to_copy" array.
};

//////////////

// 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