LazyVector.h

Go to the documentation of this file.

#ifndef LARDATAOBJ_UTILITIES_LAZYVECTOR_H
#define LARDATAOBJ_UTILITIES_LAZYVECTOR_H

// C/C++ standard libraries
#include <vector>
#include <string> // std::to_string()
#include <stdexcept> // std::out_of_range
#include <type_traits> // std::enable_if_t, std::is_arithmetic_v
#include <cassert>


namespace util {
  
  template <typename T, typename A = typename std::vector<T>::allocator_type>
  class LazyVector {
    
    using Data_t = std::vector<T, A>; 
    
      public:
    
    // --- BEGIN STL vector types ----------------------------------------------
    
    using allocator_type  = typename Data_t::allocator_type;
    using value_type      = typename Data_t::value_type;
    using size_type       = typename Data_t::size_type;
    using difference_type = typename Data_t::difference_type;
    using reference       = typename Data_t::reference;
    using const_reference = typename Data_t::const_reference;
    using pointer         = typename Data_t::pointer;
    using const_pointer   = typename Data_t::const_pointer;
    
    // --- END STL vector types ------------------------------------------------
    
    
    LazyVector() = default;
    
    LazyVector(allocator_type const& a);
   
     
    LazyVector(size_type n);
    
    LazyVector(size_type n, value_type const& defValue);

    
    
    
    
    // --- BEGIN Container information -----------------------------------------
    
    size_type size() const noexcept { return fNominalSize; }
    
    bool empty() const noexcept { return fNominalSize == 0U; }
    
    size_type data_size() const noexcept { return fData.size(); }
    
    bool has_index(size_type pos) const noexcept { return pos < size(); }
    
    bool data_empty() const noexcept { return fData.empty(); }
    
    value_type const& data_defvalue() const { return fDefValue; }
    
    size_type data_begin_index() const { return fFirstIndex; }
    
    size_type data_end_index() const
      { return data_begin_index() + data_size(); }
    
    bool data_has_index(size_type pos) const
      { return (pos >= data_begin_index()) && (pos < data_end_index()); }
    
    const_pointer data_address(size_type pos) const;
    
    // --- END Container information -------------------------------------------
    
    
    
    // --- BEGIN Access to data elements ---------------------------------------
    

    value_type at(size_type pos) const;
    value_type const_at(size_type pos) const { return at(pos); }
    
    reference at(size_type pos);
    

    value_type operator[](size_type pos) const;
    value_type const_get(size_type pos) const { return this->operator[](pos); }
    

    reference operator[](size_type pos);
    reference get(size_type pos) { return this->operator[](pos); }
    
    // --- END Access to data elements -----------------------------------------
    
    
    
    // --- BEGIN Setting data elements -----------------------------------------
    
    
    // --- END Setting data elements -------------------------------------------
    
    
    
    // --- BEGIN Container operations -----------------------------------------
    
    void resize(size_type newSize);
    
    void reserve(size_type n) { storage().reserve(n); }
    
    void clear();
    
    void shrink_to_fit() { storage().shrink_to_fit(); }
    
    // --- END Container operations --------------------------------------------
    
      private:
    Data_t fData; 
    
    size_type fNominalSize = 0U; 
    size_type fFirstIndex = fData.max_size();  
    value_type fDefValue = defaultValueType(); 
    
    static value_type const fDefaultDefaultValue;
    
    Data_t& storage() { return fData; }
    Data_t const& storage() const { return fData; }
    
    size_type index_of(size_type pos) const { return pos - fFirstIndex; }
    
    void expand(size_type pos);
    
    void init(size_type pos, size_type n = 1U);
    
    void expand_front(size_type pos);
    
    void expand_back(size_type pos);
    
    void fix_size();
    
    void data_clear();
    
    void check_range(size_type pos) const;
    
    
    static value_type const& defaultValueType() { return fDefaultDefaultValue; } 
    
    
  }; // LazyVector<>

} // namespace util


//------------------------------------------------------------------------------
//---  template implementation
//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::value_type const
util::LazyVector<T,A>::fDefaultDefaultValue{};


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
util::LazyVector<T,A>::LazyVector(allocator_type const& a)
  : fData(a)
  {}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
util::LazyVector<T,A>::LazyVector(size_type n)
  : LazyVector(n, defaultValueType())
  {}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
util::LazyVector<T,A>::LazyVector(size_type n, value_type const& defValue)
  : fNominalSize(n)
  , fDefValue(defValue)
  {}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::reference util::LazyVector<T,A>::at
  (size_type pos)
{
  /*
   * Behaviour summary:
   * * if `pos` is out of vector range, throw an exception
   * * if element at `pos` has no storage, create storage for it
   * * return a reference to the element at `pos`
   */
  check_range(pos); // verify that `pos` is valid, throw otherwise
  expand(pos);
  return storage()[index_of(pos)]; // we already know it's valid
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::value_type util::LazyVector<T,A>::at
  (size_type pos) const
{
  /*
   * Behaviour summary:
   * * if `pos` is out of vector range, throw an exception
   * * if element at `pos` has no storage, return a copy of the default value
   * * otherwise, return a copy of the element at `pos`
   */
  check_range(pos); // verify that `pos` is valid, throw otherwise
  return data_has_index(pos)? storage()[index_of(pos)]: data_defvalue();
} // util::LazyVector<T,A>::at() const


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::reference util::LazyVector<T,A>::operator[]
  (size_type pos)
{
  /*
   * Behaviour summary:
   * * if `pos` is out of vector range, behaviour is undefined
   * * if element at `pos` has no storage, create storage for it
   * * return a reference to the element at `pos`
   */
  // to have the common case where the requested position has storage be handled
  // the fastest, we "enforce" the order by nesting (optimiser has last word)
  if (!data_has_index(pos)) {
    if (has_index(pos)) expand(pos);
  }
  return storage()[index_of(pos)];
} // util::LazyVector<T,A>::operator[]()


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::value_type util::LazyVector<T,A>::operator[]
  (size_type pos) const
{
  /*
   * Behaviour summary:
   * * if `pos` is out of vector range, behaviour is undefined
   * * if element at `pos` has no storage, return a copy of the default value
   * * otherwise, return a copy of the element at `pos`
   */
  // this implementation will return a default value if `pos` is out of range;
  // this is not a requirement, and may change at any time.
  if (pos < data_begin_index()) return data_defvalue();
  auto const index = index_of(pos);
  return (index < data_size())? storage()[index]: data_defvalue();
} // util::LazyVector<T,A>::operator[] () const


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
typename util::LazyVector<T,A>::const_pointer
util::LazyVector<T,A>::data_address(size_type pos) const
{
  /*
   * Behaviour summary:
   * * if `pos` is out of vector range, behaviour is undefined
   * * if element at `pos` has no storage, return nullptr
   * * otherwise, return the pointer to the specified element
   */
  // this implementation will return nullptr if `pos` is out of range;
  // this is not a requirement, and may change at any time.
  if (pos < data_begin_index()) return nullptr;
  auto const index = index_of(pos);
  return (index < data_size())? storage().data() + index: nullptr;
} // util::LazyVector<T,A>::data_address()


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::resize(size_type newSize) {
  /*
   * Behaviour summary:
   * * when extending, do not change storage
   * * when shrinking, cut the excess storage
   */
  fNominalSize = newSize;
  // delete any excess data
  if (data_end_index() > newSize) {
    if (fNominalSize <= data_begin_index()) data_clear(); // no data is left
    else {
      storage().erase
        (storage().begin() + index_of(fNominalSize), storage().end());
    }
  }
} // util::LazyVector<T,A>::resize()


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::clear() {
  data_clear();
  fNominalSize = 0U;
} // util::LazyVector<T,A>::clear()


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::expand(size_type pos) {
  // this is just a dispatcher
  if      (data_empty())              init(pos);
  else if (pos <  data_begin_index()) expand_front(pos);
  else if (pos >= data_end_index())   expand_back(pos);
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::init(size_type pos, size_type n /* = 1 */) {
  assert(data_empty());
  storage().assign(n, data_defvalue());
  fFirstIndex = pos;
  fix_size();
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::expand_front(size_type pos) {
  assert(pos < data_begin_index());
  storage().insert
    (storage().begin(), data_begin_index() - pos, data_defvalue());
  fFirstIndex = pos;
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::expand_back(size_type pos) {
  assert(pos >= data_end_index());
  storage().resize(pos + 1U - data_begin_index(), data_defvalue());
  fix_size();
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::fix_size(){
  auto const min_size = data_end_index();
  if (fNominalSize < min_size) fNominalSize = min_size;
}


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::data_clear() { 
  storage().clear();
  fFirstIndex = storage().max_size();
} // util::LazyVector<T,A>::data_clear()


//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T,A>::check_range(size_type pos) const {
  if (has_index(pos)) return;
  throw std::out_of_range(
    "Index " + std::to_string(pos) + " is out of LazyVector range (size: "
    + std::to_string(size()) + ")"
    );
} // util::LazyVector<T,A>::check_range()


//------------------------------------------------------------------------------

#endif // LARDATAOBJ_UTILITIES_LAZYVECTOR_H