LazyVector.h

Go to the documentation of this file.

#ifndef LARDATAOBJ_UTILITIES_LAZYVECTOR_H
#define LARDATAOBJ_UTILITIES_LAZYVECTOR_H

// C/C++ standard libraries
#include <algorithm>
#include <cassert>
#include <stdexcept> // std::out_of_range
#include <string>    // std::to_string()
#include <vector>

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(); }

    void data_prepare(size_type startIndex, size_type endIndex);

    void data_prepare(size_type n) { data_prepare(0U, n); }

    void data_init(size_type startIndex, size_type endIndex);

    void data_init(size_type n) { data_init(0U, n); }

    // --- 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>::data_prepare(size_type startIndex, size_type endIndex)
{
  // we do not go beyond the declared size of the vector:
  size_type const e = std::min(endIndex, size());
  if (startIndex >= e) return;

  data_clear(); // remove the old data
  storage().reserve(e - startIndex);
  fFirstIndex = startIndex;

} // util::LazyVector<T,A>::data_prepare(size_type, size_type)

//------------------------------------------------------------------------------
template <typename T, typename A /* = std::vector<T>::allocator_type */>
void util::LazyVector<T, A>::data_init(size_type startIndex, size_type endIndex)
{
  // we do not go beyond the declared size of the vector:
  size_type const e = std::min(endIndex, size());
  if (startIndex >= e) return;

  data_clear(); // remove the old data
  storage().resize(e - startIndex, data_defvalue());
  fFirstIndex = startIndex;

} // util::LazyVector<T,A>::data_init(size_type, size_type)

//------------------------------------------------------------------------------
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