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(SSet<Data, Capacity> const & other);
 
      SSet<Data, Capacity>& operator=(SSet<Data, Capacity> const & other);
 
      ~SSet();
 
      void append(Data &data);
 
      void remove(Data const & data);
 
      void clear();
 
      int capacity() const;
 
      int size() const;
 
      bool isElement(Data const & data) const;
 
      int index(Data const & data) const;
 
      void begin(PArrayIterator<Data> &iterator);
 
      void begin(ConstPArrayIterator<Data> &iterator) const;
 
      Data& operator[] (int i);
 
      Data const & 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(SSet<Data, Capacity> const & 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=(SSet<Data, Capacity> const & 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 Data const & 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(Data const & data)
   {
      Data const * 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(Data const & data) const
   {
      Data const * 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(Data const & data) const
   {
      Data const * 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