SSet.h

#ifndef UTIL_S_SET_H
#define UTIL_S_SET_H

/*
* Util Package - C++ Utilities for Scientific Computation
*
* Copyright 2010 - 2017, The Regents of the University of Minnesota
* Distributed under the terms of the GNU General Public License.
*/

#include <util/containers/PArrayIterator.h>
#include <util/containers/ConstPArrayIterator.h>
#include <util/global.h>

namespace Util
{

   template <typename Data, int Capacity>
   class SSet 
   {

   public:

      SSet();

      SSet(const SSet<Data, Capacity>& other);

      SSet<Data, Capacity>& operator=(const SSet<Data, Capacity>& other);

      ~SSet();

      void append(Data &data);

      void remove(const Data& data);

      void clear();

      int capacity() const;

      int size() const;

      bool isElement(const Data& data) const;

      int index(const Data& data) const;

      void begin(PArrayIterator<Data> &iterator);

      void begin(ConstPArrayIterator<Data> &iterator) const;

      Data& operator[] (int i);

      const Data& operator[] (int i) const;

   protected:

      Data* ptrs_[Capacity];

      int  size_;

   };
      
   // Method definitions

   /*
   * Constructor.
   */
   template <typename Data, int Capacity>
   inline SSet<Data, Capacity>::SSet()
    : size_(0)
   {}

   /*
   * Copy constructor, copy all pointers.
   */
   template<typename Data, int Capacity>
   SSet<Data, Capacity>::SSet(const SSet<Data, Capacity>& other) 
   {

      // Copy pointer values
      int i;
      for (i = 0; i < other.size_; ++i) {
         ptrs_[i] = other.ptrs_[i];
      }
      size_ = other.size_;

      // Nullify any unused elements
      if (Capacity > size_) {
         for (i = size_; i < Capacity; ++i) {
            ptrs_[i] = 0;
         }
      }

   }

   /*
   * Assignment, element by element.
   */
   template <typename Data, int Capacity>
   SSet<Data, Capacity>& 
   SSet<Data, Capacity>::operator=(const SSet<Data, Capacity>& other) 
   {

      // Check for self assignment
      if (this == &other) return *this;

      // Precondition
      if (Capacity < other.size_) {
         UTIL_THROW("LHS SSet is too small");
      }

      // Copy pointers
      for (int i = 0; i < other.size_; ++i) {
         ptrs_[i] = other[i];
      }
      size_ = other.size_;

      // Nullify any unused elements
      if (Capacity > size_) {
         for (int i = size_; i < Capacity; ++i) {
            ptrs_[i] = 0;
         }
      }

      return *this;
   }
 
   /*
   * Destructor.
   */
   template <typename Data, int Capacity>
   SSet<Data, Capacity>::~SSet()
   {}

   /*
   * Return physical capacity of array.
   */
   template <typename Data, int Capacity>
   inline int SSet<Data, Capacity>::capacity() const
   { return Capacity; }

   /*
   * Return logical size of this array.
   */
   template <typename Data, int Capacity>
   inline int SSet<Data, Capacity>::size() const
   { return size_; }

   /*
   * Set a PArrayIterator to the beginning of this Array.
   *
   * \param iterator PArrayIterator, initialized on output. 
   */
   template <typename Data, int Capacity>
   inline void SSet<Data, Capacity>::begin(PArrayIterator<Data> &iterator)
   {
      iterator.setCurrent(const_cast<Data**>(ptrs_));
      iterator.setEnd(const_cast<Data**>(ptrs_ + size_));
   }

   /*
   * Set a PArrayIterator to the beginning of this Array.
   */
   template <typename Data, int Capacity>
   inline void SSet<Data, Capacity>::begin(ConstPArrayIterator<Data> &iterator) const
   {
      iterator.setCurrent(const_cast<Data**>(ptrs_));
      iterator.setEnd(const_cast<Data**>(ptrs_ + size_));
   }

   /*
   * Mimic C array subscripting.
   */
   template <typename Data, int Capacity>
   inline Data& SSet<Data, Capacity>::operator[] (int i)
   {
      assert(i < size_);
      assert(i >= 0);
      return *ptrs_[i];
   }

   /*
   * Mimic C array subscripting.
   */
   template <typename Data, int Capacity>
   inline const Data& SSet<Data, Capacity>::operator[] (int i) const
   {
      assert(i < size_);
      assert(i >= 0 );
      return *ptrs_[i];
   }

   /*
   * Append data to the end of the array.
   *
   * \param data Data to add to end of array.
   */
   template <typename Data, int Capacity>
   inline void SSet<Data, Capacity>::append(Data &data) 
   {
      if (size_ == Capacity) {
         UTIL_THROW("Attempt to add to full SSet");
      }
      ptrs_[size_] = &data;
      ++size_;
   }

   /*
   * Clear out the container.
   */
   template <typename Data, int Capacity>
   inline void SSet<Data, Capacity>::clear() 
   { 
      size_ = 0; 
      for (int i=0; i < Capacity; ++i) {
         ptrs_[i] = 0;
      }
   }
 
   /*
   * Remove an element from the set.
   */
   template <typename Data, int Capacity>
   void SSet<Data, Capacity>::remove(const Data& data)
   {
      const Data* const ptr = &data;
      int   i;
      bool  found;

      // Search for object
      found = false;
      for (i = 0; i < size_; ++i) {
         if (ptr == ptrs_[i]) {
            found = true;
            break;
         }
      }

      if (!found) {
         UTIL_THROW("Element is not in set");
      }

      // Remove element
      if (i != size_ - 1) {
         ptrs_[i] = ptrs_[size_-1];
      }
      ptrs_[size_ - 1] = 0;
      --size_;

   }

   /*
   * Return true if an object is in the set, false otherwise.
   */
   template <typename Data, int Capacity>
   bool SSet<Data, Capacity>::isElement(const Data& data) const
   {
      const Data* const ptr = &data;
      bool  found;

      // Search for element in set
      found = false;
      for (int i = 0; i < size_; ++i) {
         if (ptr == ptrs_[i]) {
            found = true;
            break;
         }
      }
      return found;
   }

   template <typename Data, int Capacity>
   int SSet<Data, Capacity>::index(const Data& data) const
   {
      const Data* const ptr = &data;
      int   i;
      bool  found;

      // Search for element in set
      found = false;
      for (i = 0; i < size_; ++i) {
         if (ptr == ptrs_[i]) {
            found = true;
            break;
         }
      }
      if (found) {
         return i;
      } else {
         return -1;
      }
   }

} 
#endif