tpl_memArray.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
# ifndef TPL_MEMARRAY_H
# define TPL_MEMARRAY_H

# include <utility>
# include <cstdlib>
# include <cmath>
# include <stdexcept>

# include <ahUtils.H>
# include <ahDry.H>
# include <ahIterator.H>
# include <array_it.H>
# include <array_utils.H>

using namespace Aleph;

namespace Aleph
{

    template <typename T>
class MemArray
{
public:

  static constexpr size_t Min_Dim = 4;

protected:

  T *    ptr = nullptr;
  size_t dim = Min_Dim;
  size_t n   = 0;

public:
  
  mutable size_t contract_threshold;

public:

  T * get_ptr() const noexcept { return ptr; }

  const size_t & get_dim() const noexcept { return dim; }

protected:

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

  bool expand(const size_t first = 0)
  {
    assert(ptr);
    assert(is_power_of_2(dim));
    if (n < dim)
      return false;

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

    return true;
  }

  bool contract(const size_t first = 0)
  {
    assert(ptr);
    if (n > contract_threshold)
      return false;

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

    if (newsz <= Min_Dim)
      return false;

    T * new_ptr = new T [newsz];

    const size_t mask = dim - 1;
    for (int i = 0; i < newsz; ++i)
      {
        assert(((first + i) & mask) == ((first + i) % dim));
        std::swap(ptr[(first + i) & mask], new_ptr[i]);
      }

    for (int i = newsz; i < dim; ++i) // call destructors 
      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 
  void init_dim(size_t d) noexcept
  {
    if (d == 0)
      d = Min_Dim;

    size_t k = log2(d);
    dim = is_power_of_2(d) ? d : 1 << ++k;

    assert(dim >= d);
    assert(dim == 1 << k);
  }

public:

  using Item_Type = T; 

  size_t capacity() const noexcept { return dim; }

  size_t size() const noexcept { return n; }

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

  MemArray(size_t __dim = Min_Dim) : ptr(nullptr), n(0)
  {
    static_assert(std::is_copy_constructible<T>::value, 
                  "No copy constructor for T");
    static_assert(std::is_move_constructible<T>::value,
                  "No move constructor for T");
    static_assert(std::is_copy_assignable<T>::value,
                  "No copy assign for T");
    static_assert(std::is_move_assignable<T>::value,
                  "No move assign for T");
    init_dim(__dim);
    allocate();
  }

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

  void swap(MemArray & a) noexcept
  {
    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(nullptr), dim(a.dim), n(a.n)
  {
    allocate();
    for (int i = 0; i < dim; ++i)
      ptr[i] = a.ptr[i];
  }
  
  MemArray(MemArray && a) noexcept
    : ptr(nullptr), dim(0), n(0), contract_threshold(0)
  {
    assert(a.ptr);
    swap(a);
  }

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

    assert(a.ptr);

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

    if (ptr != nullptr)
      delete [] ptr;
    ptr = newptr;
    dim = a.dim;
    n = a.n;

    return *this;
  }

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

  void empty() { n = 0; }

  void empty_and_release()
  {
    n = 0;
    if (dim <= Min_Dim)
      return;

    assert(ptr);
    delete [] ptr;
    ptr = nullptr;
    dim = Min_Dim;
    allocate();
  }

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

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

  T & put(T && item)
  {
    assert(ptr);
    expand();

    ptr[n] = std::forward<T>(item);
    T & ret = ptr[n++];
    return ret;
  }

private:

  void open_gap(size_t pos = 0, size_t num_entries = 1)
  {
    putn(num_entries);
    Aleph::open_gap(ptr, n, pos, num_entries);
  }

  void close_gap(size_t pos, size_t num_entries = 1)
  {
    Aleph::close_gap(ptr, n, pos, num_entries);
    get(num_entries);
  }

public:

  T & push(const T & item)
  {
    assert(ptr);
    open_gap();

    ptr[0] = item;
    T & ret = ptr[0];
    return ret;
  }

  T & push(T && item)
  {
    assert(ptr);
    open_gap();

    ptr[0] = std::forward<T>(item);
    T & ret = ptr[0];
    return ret;
  }

  T & top() const
  {
    if (n == 0)
      throw std::underflow_error("top(): MemArray is empty");

    return ptr[0];
  }

  T remove_first()
  {
    if (n == 0)
      throw std::underflow_error("remove_first(): MemArray is empty");
    assert(ptr);
    T ret = move(ptr[0]);
    close_gap(0);
    return ret;
  }

  T pop() { return remove_first(); }
  
  T & append(T & item)
  {
    assert(ptr);
    return put(item);
  }

  T & append(T && item)
  {
    assert(ptr);
    return put(std::forward<T>(item));
  }

  T & insert(T & item)
  {
    assert(ptr);
    return push(item);
  }

  T & insert(T && item)
  {
    assert(ptr);
    return push(std::forward<T>(item));
  }

  void putn(const size_t more)
  {
    assert(ptr);
    size_t new_n = n + more;
    if (new_n <= dim)
      {
        n = new_n;
        return;
      }

    size_t new_dim = dim;
    while (new_dim < new_n)
      new_dim <<= 1; // dim = 2*dim

    T * new_ptr = new T[new_dim];
    for (size_t i = 0; i < n; ++i)
      std::swap(ptr[i], new_ptr[i]);
    
    delete [] ptr;
    ptr = new_ptr;
    dim = new_dim;
    n = new_n;
    contract_threshold = dim/4;
  }

  MemArray & append(const MemArray & a)
  {
    const size_t old_n = n;
    const size_t num_entries = a.size();
    putn(num_entries);
    for (size_t i = 0; i < num_entries; ++i)
      ptr[old_n + i] = a.ptr[i];

    return *this;
  }

  /*
  MemArray & insert(const MemArray & a)
  {
    const size_t old_n = n;
    const size_t & num_entries = a.size();
    Aleph::open_gap(ptr, n);
  }
  */

  void reserve(const size_t cap)
  {
    assert(ptr);
    if (cap < dim)
      return;

    size_t k = log2(cap);
    const size_t new_dim = is_power_of_2(cap) ? cap : 1 << ++k;

    T * new_ptr = new T[new_dim];
    for (size_t i = 0; i < n; ++i)
      std::swap(ptr[i], new_ptr[i]);
    
    delete [] ptr;
    ptr = new_ptr;
    dim = new_dim;
    contract_threshold = dim/4;
  }
  
  T get(size_t i = 1) 
  {
    assert(ptr);
    long idx = n - i;
    if (idx < 0)
      throw std::underflow_error("MemArray::get(): deleted more entries"
                                 " than capacity");

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

    contract();

    return ret;
  }

  T get_ne(size_t i = 1) noexcept
  {
    assert(ptr);
    long idx = n - i;
    n = idx;
    T ret = std::move(ptr[n]);

    contract();

    return ret;
  }

  T remove_last() { return get(); }

  T & last() const
  {
    if (n == 0)
      throw std::underflow_error("MemArray::last(): empty array");
    return ptr[n - 1];
  }

  T & first() const
  {
    if (n == 0)
      throw std::underflow_error("MemArray::first(): empty array");
    return ptr[0];
  }

  T & get_first() const { return first(); }

  T & get_last() const { return last(); }

  MemArray & reverse()
  {
    for (size_t i = 0, j = n - 1; i < j; ++i, --j)
      std::swap(ptr[i], ptr[j]);
    return *this;
  }

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

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

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

  template <class Operation>
  bool traverse(Operation & operation) 
  {
    assert(ptr);
    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) const
  {
    return traverse<Operation>(operation);
  }

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

  bool is_valid() const noexcept { return ptr; }

  struct Iterator : public Array_Iterator<T>
  {
    using Base = Array_Iterator<T>;
    using Base::Base;

    Iterator(const MemArray<T> & a) noexcept
      : Array_Iterator<T>(no_exception_ctor, a.ptr, a.dim, a.n)
    {
      assert(a.ptr != nullptr);
    }
  };
};


} // end namespace Aleph

# endif // TPL_MEMARRAY_H