HashVector.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.
*/
 
#ifndef AGX_HASHVECTOR_H
#define AGX_HASHVECTOR_H
 
 
#include <agx/Vector.h>
#include <agx/HashTable.h>
 
namespace agx
{
 
  template <typename KeyT, typename DataT=KeyT, typename HashT = agx::HashFn<KeyT> >
  class HashVector
  {
  public:
 
    typedef DataT value_type;
    typedef HashVector<KeyT, DataT, HashT> ContainerType;
 
    typedef Vector<std::pair<KeyT, DataT> > VectorType;
    typedef HashTable<KeyT, size_t, HashT> HashType;
 
  private:
 
    VectorType m_vector;
    HashType m_hash;
 
  public:
 
    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
    };
 
    typedef typename VectorType::iterator iterator;
    typedef typename VectorType::const_iterator const_iterator;
 
 
    HashVector()
    {}
 
    HashVector(const ContainerType& other) : m_vector( other.m_vector ), m_hash( other.m_hash )
    {
      this->clear(SHRINK_BUFFER);
      *this = other;
    }
 
    HashVector<KeyT, DataT, HashT>& operator= (const ContainerType& other)
    {
      if ( this == &other ) {
        return *this;
      }
 
      m_vector = other.m_vector;
      m_hash = other.m_hash;
      return *this;
    }
 
 
    ~HashVector()
    {
      // 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;
    }
 
    size_t size() const
    {
      agxAssert( checkSize() );
 
      return m_vector.size();
    }
 
    bool empty() const
    {
      return m_vector.empty();
    }
 
    template<typename T>
    iterator push_back(const KeyT& key, T&& data)
    {
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find(key);
      if (it != m_hash.end())
      {
        // Replace the already existing data value with the new
        m_vector[it->second].second = std::forward<T>(data);
        return &m_vector[it->second];
      }
 
      // Key did not exist, insert at the end of the vector
      m_vector.push_back(std::make_pair(key, std::forward<T>(data)));
 
      // Hash on data, index is data value
      m_hash.insert(key, m_vector.size()-1);
 
      return end()-1; // Return iterator to the newly inserted element.
    }
 
    template<typename T>
    iterator insert(const KeyT& key, T&& data)
    {
      agxAssert( checkSize() );
 
      return push_back(key, std::forward<T>(data));
    }
 
    iterator replace( const KeyT& oldKey, const KeyT& newKey, const DataT& data )
    {
      agxAssert( checkSize() );
      auto oldIt = m_hash.find( oldKey );
      if ( oldIt == m_hash.end() )
        return end();
 
      size_t index = oldIt->second;
      m_vector[ index ] = std::make_pair( newKey, data );
      m_hash.erase( oldIt );
      m_hash.insert( newKey, index );
 
      return begin() + index;
    }
 
    bool contains(const KeyT& key) const
    {
      agxAssert( checkSize() );
 
      return m_hash.contains( key );
    }
 
    iterator find(const KeyT& key)
    {
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find( key );
      if (it == m_hash.end())
        return end();
 
      return &m_vector[it->second];
    }
 
    const_iterator find(const KeyT& 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];
 
    }
 
 
    iterator begin()
    {
      agxAssert( checkSize() );
 
 
      return m_vector.begin(); }
 
    const_iterator begin() const
    {
      agxAssert( checkSize() );
      return m_vector.begin();
    }
 
 
    iterator end()
    {
      agxAssert( checkSize() );
      return m_vector.end();
    }
 
    const_iterator end() const
    {
      agxAssert( checkSize() );
      return m_vector.end();
    }
 
    DataT& front()
    {
      agxAssert( checkSize() );
      return m_vector[0].second;
    }
 
    const DataT& front() const
    {
      agxAssert( checkSize() );
      return m_vector[0].second;
    }
 
    DataT& back()
    {
      agxAssert( checkSize() );
      return m_vector[m_vector.size()-1].second;
    }
 
    const DataT& back() const
    {
      agxAssert( checkSize() );
      return m_vector[m_vector.size()-1].second;
    }
 
 
 
    bool erase(const KeyT& key)
    {
 
      agxAssert( checkSize() );
 
      typename HashType::iterator it = m_hash.find( key );
      if (it == m_hash.end())
        return false;
 
      erase( it );
      return true;
    }
 
    iterator erase(const iterator& it)
    {
      agxAssert( checkSize() );
 
      if (it == end())
        return it;
 
      KeyT& key = it->first;
      typename HashType::iterator hashIt = m_hash.find( key );
 
      agxAssert ( hashIt != m_hash.end() );
 
      hashIt = erase( hashIt );
 
      if ( hashIt == m_hash.end() )
        return end();
 
      return &m_vector[ hashIt->second ];
    }
 
    void clear(ClearPolicy policy = SHRINK_BUFFER_AVERAGED)
    {
      agxAssert( checkSize() );
 
      m_hash.clear( (typename HashType::ClearPolicy)policy );
      m_vector.clear( (typename VectorType::ClearPolicy)policy );
    }
 
    DataT& operator[](size_t i )
    {
      agxAssert( checkSize() );
 
      agxAssert(i < m_vector.size());
      return m_vector[i].second;
    }
 
    const DataT& operator[](size_t i ) const
    {
      agxAssert( checkSize() );
 
      agxAssert(i < m_vector.size());
      return m_vector[i].second;
    }
 
    void reserve(size_t size)
    {
      agxAssert( checkSize() );
 
      m_vector.reserve( size );
      m_hash.reserve( size );
    }
 
    DataT& getOrCreate( const KeyT& key )
    {
      iterator it = find( key );
      if ( it == end() )
        it = insert( key, value_type() );
      return it->second;
    }
 
    template<typename T>
    size_t purge(T purger)
    {
      if (empty()) // Nothing to do
        return 0;
 
#if 0 // Slow version
      VectorType savedElements; // Elements to keep
      savedElements.reserve( m_vector.size());
      VectorType::const_iterator it = m_vector.begin();
      for(; it != m_vector.end(); ++it)
      {
        // Should we keep it?
        if (!purger(it->first, it->second))
          savedElements.push_back( std::make_pair(it->first, it->second)); // 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(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->first, m_vector.size()-1 );
      }
#else // Faster version (2x)
      typename agx::Vector<typename VectorType::value_type *> removeElements; //PointerVector ; // 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).first, (*it).second ))
          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).first );
      }
 
      return removeElements.size();
#endif
    }
 
  private:
 
    // Return true if size of vector and hash is equal
    bool checkSize() const {
      return m_vector.size() == m_hash.size();
    }
 
    typename HashType::iterator erase( typename HashType::iterator it )
    {
      size_t idx = it->second;
 
      typename HashType::iterator retIt = 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
        retIt = m_hash.insert( lastElement.first, idx );
      }
      else
        // Only one element, OR its the last we are removing: just remove it
        m_vector.pop_back();
 
      agxAssert( checkSize() );
 
      return retIt;
    }
 
 
  };
 
}
 
 
#endif /* AGX_HASHVECTOR_H */