SetVector.h

Go to the documentation of this file.

/*
Copyright 2007-2025. Algoryx Simulation AB.
 
All AGX source code, intellectual property, documentation, sample code,
tutorials, scene files and technical white papers, are copyrighted, proprietary
and confidential material of Algoryx Simulation AB. You may not download, read,
store, distribute, publish, copy or otherwise disseminate, use or expose this
material unless having a written signed agreement with Algoryx Simulation AB, or having been
advised so by Algoryx Simulation AB for a time limited evaluation, or having purchased a
valid commercial license from Algoryx Simulation AB.
 
Algoryx Simulation AB disclaims all responsibilities for loss or damage caused
from using this software, unless otherwise stated in written agreements with
Algoryx Simulation AB.
*/
 
#pragma once
 
 
#include <agx/Vector.h>
#include <agx/HashTable.h>
 
namespace agx
{
 
  template <typename DataT, typename HashT = HashFn<DataT> >
  class SetVector
  {
  public:
 
    typedef DataT value_type;
    typedef const DataT& const_reference;
    typedef size_t size_type;
    typedef SetVector<DataT, HashT> ContainerType;
    typedef Vector<DataT> VectorType;
    typedef HashTable<DataT, size_t, HashT> HashType;
 
  private:
    VectorType m_vector;
    HashType m_hash;
 
  public:
#ifndef SWIG
    enum ClearPolicy
    {
      SHRINK_BUFFER=VectorType::SHRINK_BUFFER,           // Buffer is deallocated and replaced by an empty buffer
      SHRINK_BUFFER_AVERAGED=VectorType::SHRINK_BUFFER_AVERAGED,  // Buffer is shrunk if a smoothing average (which is updated each clear call) goes below a threshold
      MAINTAIN_BUFFER=VectorType::MAINTAIN_BUFFER          // Buffer is maintained
    };
#endif
 
    typedef typename VectorType::iterator iterator;
    typedef typename VectorType::const_iterator const_iterator;
    typedef typename VectorType::reverse_iterator reverse_iterator;
    typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
 
 
    SetVector()
    {}
 
    SetVector(const ContainerType& other) : m_vector( other.m_vector ), m_hash( other.m_hash )
    {
      this->clear(SHRINK_BUFFER);
      *this = other;
    }
 
    ContainerType& operator= (const ContainerType& other)  // NOLINT clang-tidy-7 doesn't realize that ContainerType is a SetVector.
    {
      if ( this == &other ) {
        return *this;
      }
 
      m_vector = other.m_vector;
      m_hash = other.m_hash;
      return *this;
    }
 
 
    ~SetVector()
    {
      // don't change buffer, will be dealloc'ed soon anyway
      clear(MAINTAIN_BUFFER);
    }
 
    const VectorType& vector() const
    {
      return m_vector;
    }
 
    const HashType& table() const
    {
      return m_hash;
    }
 
    inline size_t size() const
    {
      agxAssert( checkSize() );
 
      return m_vector.size();
    }
 
    inline bool empty() const
    {
      return m_vector.empty();
    }
 
    template< typename T2 >
    inline iterator push_back(const T2& data)
    {
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find(data);
      if (it != m_hash.end())
      {
        // Replace the already existing data value with the new
        m_vector[it->second] = data;
        return &m_vector[it->second];
      }
 
      // Key did not exist, insert at the end of the vector
      m_vector.push_back( data );
 
      // Hash on data, index is data value
      m_hash.insert( data, m_vector.size()-1 );
 
      return end()-1; // Return iterator to the newly inserted element.
    }
 
    template< typename T2 >
    inline iterator insert(const T2& data)
    {
      agxAssert( checkSize() );
 
      return push_back(data);
    }
 
    template< typename OldDataT, typename NewDataT >
    iterator replace( const OldDataT& oldData, const NewDataT& newData )
    {
      agxAssert( checkSize() );
 
      auto oldIt = m_hash.find( oldData );
      if ( oldIt == m_hash.end() )
        return end();
 
      size_t index = oldIt->second;
      m_vector[ index ] = newData;
      m_hash.erase( oldIt );
      m_hash.insert( newData, index );
 
      return begin() + index;
    }
 
    template< typename T2 >
    inline bool contains(const T2& key) const
    {
      agxAssert( checkSize() );
 
      return m_hash.contains( key );
    }
 
    template< typename T2 >
    iterator find(const T2& key)
    {
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find( key );
      if (it == m_hash.end())
        return end();
 
      return &m_vector[it->second];
    }
 
    template< typename T2 >
    const_iterator find(const T2& key) const
    {
      agxAssert( checkSize() );
 
      typename HashType::const_iterator it = m_hash.find( key );
      if (it == m_hash.end())
        return end();
 
      // Return index to the element in the vector
      return &m_vector[it->second];
    }
 
#ifndef SWIG
    inline iterator begin()
    {
      agxAssert( checkSize() );
 
      return m_vector.begin();
    }
 
    inline const_iterator begin() const
    {
      agxAssert( checkSize() );
 
      return m_vector.begin();
    }
 
    inline reverse_iterator rbegin()
    {
      agxAssert( checkSize() );
 
      return m_vector.rbegin();
    }
 
    inline const_reverse_iterator rbegin() const
    {
      agxAssert( checkSize() );
 
      return m_vector.rbegin();
    }
 
    inline iterator end()
    {
      agxAssert( checkSize() );
 
      return m_vector.end();
    }
 
    inline const_iterator end() const
    {
      agxAssert( checkSize() );
      return m_vector.end();
    }
 
    inline reverse_iterator rend()
    {
      agxAssert( checkSize() );
 
      return m_vector.rend(); }
 
    inline const_reverse_iterator rend() const
    {
      agxAssert( checkSize() );
      return m_vector.rend();
    }
#endif
    inline DataT& front()
    {
      agxAssert( checkSize() );
      return m_vector[0];
    }
 
    inline const DataT& front() const
    {
      agxAssert( checkSize() );
      return m_vector[0];
    }
 
    inline DataT& back()
    {
      agxAssert( checkSize() );
      return m_vector[m_vector.size()-1];
    }
 
    inline const DataT& back() const
    {
      agxAssert( checkSize() );
      return m_vector[m_vector.size()-1];
    }
 
 
    template< typename T2 >
    bool erase(const T2& key)
    {
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find( key );
      if (it == m_hash.end())
        return false;
 
      erase( it );
      return true;
    }
 
    bool erase(const iterator& it)
    {
 
      agxAssert( checkSize() );
 
      if (it == end())
        return false;
      agxAssert( it != end() );
 
      DataT& key = *it;
      typename HashType::iterator hashIt = m_hash.find( key );
 
      agxAssert ( hashIt != m_hash.end() );
 
      erase( hashIt );
 
      return true;
    }
 
#ifndef SWIG
    void clear(ClearPolicy policy = SHRINK_BUFFER_AVERAGED)
#else
    void clear()
#endif
    {
 
      agxAssert( checkSize() );
 
      m_hash.clear( (typename HashType::ClearPolicy)policy );
      m_vector.clear( (typename VectorType::ClearPolicy)policy );
    }
 
    inline DataT& operator[](size_t i )
    {
      agxAssert( checkSize() );
 
      agxAssert(i < m_vector.size());
      return m_vector[i];
    }
 
    inline const DataT& operator[](size_t i ) const
    {
      agxAssert( checkSize() );
 
      agxAssert(i < m_vector.size());
      return m_vector[i];
    }
 
 
    inline const DataT& at(size_t index) const
    {
      return m_vector.at(index);
    }
 
 
    inline DataT& at(size_t index)
    {
      return m_vector.at(index);
    }
 
 
    void reserve(size_t size)
    {
      agxAssert( checkSize() );
 
      m_vector.reserve( size );
      m_hash.reserve( size );
    }
 
 
 
    template<typename T>
    size_t purge(T purger)
    {
      if (empty()) // Nothing to do
        return 0;
 
#if 0 // Slower implementation
      typename VectorType savedElements; // Elements to keep
      savedElements.reserve( m_vector.size());
      typename VectorType::const_iterator it = m_vector.begin();
      for(; it != m_vector.end(); ++it)
      {
        // Should we keep it?
        if (!purger(*it))
          savedElements.push_back(*it); // store all elements that should remain
      }
      m_vector.clear(agx::Container::SHRINK_BUFFER_AVERAGED);
      m_hash.clear(agx::Container::SHRINK_BUFFER_AVERAGED);
 
      // Make sure we can fit all the saved elements
      m_vector.reserve( savedElements.size() );
      m_hash.reserve( savedElements.size() );
 
      for(typename VectorType::const_iterator it = savedElements.begin(); it != savedElements.end(); ++it)
      {
        m_vector.push_back( *it );
        // Hash on data, index is data value
        m_hash.insert( *it, m_vector.size()-1 );
      }
#else // Faster implementation
      typename agx::Vector<typename VectorType::value_type *> removeElements; // Safe to use pointers?
      removeElements.reserve( m_vector.size());
      for(typename VectorType::iterator it = m_vector.begin(); it != m_vector.end(); ++it)
      {
        // Should we keep it?
        if (!purger(*it))
          removeElements.push_back(&(*it)); // store all elements that should remain
      }
 
      for(typename agx::Vector<typename VectorType::value_type *>::const_iterator it = removeElements.begin(); it != removeElements.end(); ++it)
      {
        this->erase( **it );
      }
 
      return removeElements.size();
#endif
    }
 
  private:
 
    // Return true if size of vector and hash is equal
    AGX_FORCE_INLINE bool checkSize() const {
      return m_vector.size() == m_hash.size();
    }
 
    void erase( typename HashType::iterator it )
    {
      size_t idx = it->second;
 
      m_hash.erase( it ); // remove from hash
 
      // Remove from vector too:
      if (m_vector.size() > 1 && idx != (m_vector.size()-1))
      {
        // Get the last element
        typename VectorType::value_type lastElement = m_vector.back();
 
        // Put it where we have removed an element
        m_vector[idx] = lastElement;
 
        // remove the last now
        m_vector.pop_back();
 
        // Rehash the moved one with the new index
        m_hash.insert( lastElement, idx );
      }
      else
        // Only one element, OR its the last we are removing: just remove it
        m_vector.pop_back();
 
      agxAssert( checkSize() );
    }
 
 
  };
 
}