tpl_memArray.H

# ifndef TPL_MEMARRAY_H
# define TPL_MEMARRAY_H

# include <utility>

# include <stdlib.h>
# include <math.h>
# include <stdexcept>
# include <nana.h>

# include <ahDry.H>

namespace Aleph
{

    template <typename T>
class MemArray
{
protected:

  T *    ptr;
  size_t dim;
  size_t n;
  size_t contract_threshold;

  void allocate()
  {
    ptr = new T [dim];
    contract_threshold = dim / 4; 
  }

  // return true if expansion is done
  bool expand(const size_t first = 0)
  {
    if (n < dim)
      return false;

    const size_t newsz = dim << 1; // 2*dim
    T * new_ptr = new T [newsz];
    for (int i = 0; i < dim; ++i)
      std::swap(ptr[(i + first) % dim ], new_ptr[i]);
    delete [] ptr;
    ptr = new_ptr;
    dim = newsz;
    contract_threshold = dim/4;

    return true;
  }

  // return true if contraction is done
  bool contract(const size_t first = 0)
  {
    if (n > contract_threshold)
      return false;

    const size_t newsz = dim >> 1; // dim/2

    T * new_ptr = new T [newsz];

    for (int i = 0; i < newsz; ++i)
      std::swap(ptr[(first + i) % dim], new_ptr[i]);

    for (int i = newsz; i < dim; ++i)
      ptr[i].~T();

    delete [] ptr;
    ptr = new_ptr;
    dim = newsz;
    contract_threshold = dim/4;

    return true;
  }

  // if dim == 2^k returns dim; else next two power 2^k > dim 
  static size_t init_dim(const size_t dim)
  {
    if (dim == 0 or ((dim > 0) and (dim & (dim - 1)) == 0))
      return dim;

    return 1 << (int) (log2(dim) + 1);
  }

public:

  const size_t & capacity() const { return dim; }

  const size_t & size() const { return n; }

  bool is_empty() const { return n == 0; }

  MemArray(size_t __dim = 8)
    : ptr(NULL), dim(init_dim(__dim)), n(0)
  {
    allocate();
  }

  ~MemArray()
  {
    if (ptr != NULL)
      {
        delete [] ptr;
        ptr = NULL;
      }
  }

  void swap(MemArray & a)
  {
    std::swap(ptr, a.ptr);
    std::swap(dim, a.dim);
    std::swap(n, a.n);
    std::swap(contract_threshold, a.contract_threshold);
  }

  MemArray(const MemArray & a) 
    : ptr(NULL), dim(a.dim), n(a.n)
  {
    allocate();
    for (int i = 0; i < dim; ++i)
      ptr[i] = a.ptr[i];
  }

  MemArray(MemArray && a) 
    : ptr(NULL), dim(0), n(0), contract_threshold(0)
  {
    swap(a);
  }

  MemArray & operator = (const MemArray & a)
  {
    if (this == &a)
      return *this;

    T * newptr = new T [a.n];      // allocate new array
    for (int i = 0; i < a.n; ++i)  // copy items to new array
      newptr[i] = a.ptr[i];

    delete [] ptr;
    ptr = newptr;
    dim = a.dim;
    n = a.n;

    return *this;
  }

  MemArray & operator = (MemArray && a)
  {
    swap(a);
    return *this;
  }

  void empty()
  {
    n = 0;
    if (dim == 1)
      return;

    contract();
  }

  T & put(const T & item)
  {
    expand();

    T & ret = ptr[n++] = item;
    return ret;
  }

  T & put(T && item)
  {
    expand();
    
    T & ret = ptr[n++] = std::move(item);
    return ret;
  }

  T & put(const size_t i, const T & item)
  {
    if (i >= dim)
      throw std::range_error("index out of range");

    return ptr[i] = item;
  }

  T & put(const size_t i, T && item)
  {
    if (i >= dim)
      throw std::range_error("index out of range");

    return ptr[i] = std::move(item);
  }

  void putn(const size_t more)
  {
    n += more;
    expand();
  }
  
  T get(int i = 1) 
  {
    int idx = n - i;
    if (idx < 0)
      throw std::underflow_error("Deleted more entries than capacity");

    n = idx;
    T ret = std::move(ptr[n]);

    contract();

    return ret;
  }

  T & last() { return ptr[n - 1]; }

  T & first() { return ptr[0]; }

  T & access(const size_t i)
  {
    return ptr[i];
  }

  const T & last() const { return ptr[n - 1]; }

  const T & first() const { return ptr[0]; }

  const T & access(const size_t i) const
  {
    return ptr[i];
  }

  T & operator [] (const size_t i) 
  {
    return ptr[i];
  }

  const T & operator [] (const size_t i) const
  {
    if (i >= n)
      throw std::range_error("access out of range");

    return ptr[i];
  }

  T & operator () (const size_t i) 
  {
    I(i < dim);
    return ptr[i];
  }

  const T & operator () (const size_t i) const
  {
    I(i < dim);
    return ptr[i];
  }

  template <class Operation>
  bool traverse(Operation & operation)
  {
    for (int i = 0; i < n; i++)
      if (not operation(ptr[i]))
        return false;

    return true;
  }

  template <class Operation>
  bool traverse(Operation & operation) const
  {
    return const_cast<MemArray*>(this)->traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) const
  {
    return traverse<Operation>(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation())
  {
    return traverse<Operation>(operation);
  }

  Functional_Methods(T);
};


} // end namespace Aleph

# endif // TPL_MEMARRAY_H