CepsVector.hpp

Go to the documentation of this file.

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   This file is part of CEPS.
 
   CEPS 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.
 
   CEPS 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 CEPS (see file LICENSE at root of project).
   If not, see <https://www.gnu.org/licenses/>.
 
 
   Copyright 2019-2024 Inria, Universite de Bordeaux
 
   Authors, in alphabetical order:
 
     Pierre-Elliott BECUE, Florian CARO, Yves COUDIERE(*), Andjela DAVIDOVIC, 
     Charlie DOUANLA-LONTSI, Marc FUENTES, Mehdi JUHOOR, Michael LEGUEBE(*), 
     Pauline MIGERDITICHAN, Valentin PANNETIER(*), Nejib ZEMZEMI.
     * : currently active authors
 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#pragma once
 
#include <functional>
#include <numeric>
 
#include "common/core/CepsMemory.hpp"
 
namespace ceps
{
 
  template <class _Type, class _Alloc>
  void
  destroy(CepsVector<_Type,_Alloc>& vec, CepsBool deleteAll = true)
  {
    if (deleteAll)
      for (_Type &v : vec)
        ceps::destroyObject(v);
    return vec.clear();
  }
 
  template <class _Type, class _Alloc>
  CepsBool
  contains(const CepsVector<_Type,_Alloc>& vec, const _Type& item)
  {
    auto it = std::find(vec.begin(), vec.end(), item);
    return it != vec.end();
  }
 
  template <class _Type, class _Alloc>
  CepsBool
  contains(const CepsVector<_Type,_Alloc>& vec, _Type&& item)
  {
    auto it = std::find(vec.begin(), vec.end(),item);
    return it != vec.end();
  }
 
  template <class _Type, class _Alloc, class InputIt>
  void
  pushBack(CepsVector<_Type,_Alloc> &vec, InputIt first, InputIt last)
  {
    vec.reserve (vec.size() + std::distance(first, last));
    for (auto it=first; it!=last; ++it)
      vec.push_back (*it);
    return;
  }
 
  template <class _Type, class _Alloc, class InputIt>
  void
  insertIf(
    CepsVector<_Type,_Alloc>&             vec,
    InputIt                               first,
    InputIt                               last,
    std::function<CepsBool(const _Type&)> func
  )
  {
    vec.reserve (vec.size() + std::distance(first, last));
    for (auto it=first; it!=last; ++it)
    {
      auto item = *it;
      if (func(item))
        vec.push_back(item);
    }
    return;
  }
 
  template <class _Type, class _Alloc>
  void
  insert(CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    vec.push_back(value);
    return;
  }
 
  template <class _Type, class _Alloc, class InputIt>
  void
  insertUnique(CepsVector<_Type,_Alloc>& vec, InputIt first, InputIt last)
  {
    vec.reserve (vec.size () + std::distance (first, last));
    for (auto it = first; it != last; ++it)
    {
      auto item = *it;
      if (not contains (vec, item))
        vec.push_back (item);
    }
    return;
  }
 
  template <class _Type, class _Alloc>
  CepsBool
  insertUnique (CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    CepsBool b = contains(vec, value);
    if (not b)
      vec.push_back(value);
    return not b;
  }
 
  template <class _Type, class _Alloc>
  CepsBool
  insertUnique (CepsVector<_Type,_Alloc>& vec, _Type&& value)
  {
    CepsBool b = contains(vec, value);
    if (not b)
      vec.push_back(value);
    return not b;
  }
 
  template <class _Type, class _Alloc>
  void
  eraseValue(CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    vec.erase(std::remove(vec.begin(),vec.end(),value),vec.end());
    return;
  }
 
  template <class _Type, class _Alloc, class InputIt>
  void
  eraseValues(CepsVector<_Type,_Alloc>& vec, InputIt first, InputIt last)
  {
    for (InputIt it=first; it!=last; ++it)
    {
      auto item = *it;
      eraseValue(vec,item);
    }
    return;
  }
 
  template <class _Type, class _Alloc>
  typename CepsVector<_Type,_Alloc>::iterator
  find(CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    return std::find(vec.begin(),vec.end(),value);
  }
 
  template <class _Type, class _Alloc>
  typename CepsVector<_Type,_Alloc>::const_iterator
  find(const CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    return std::find(vec.begin(),vec.end(),value);
  }
 
  template <class _Type, class _Alloc>
  std::pair<CepsBool, CepsUInt>
  indexOf(const CepsVector<_Type,_Alloc>& vec, const _Type &value)
  {
    auto it = find (vec, value);
    if (it == vec.end ())
      return {false, 0U};
    return {true, std::distance (vec.begin (), it)};
  }
 
  template <class _Type, class _Alloc>
  CepsInt
  argVector(const CepsVector<_Type,_Alloc>& vec, const _Type& value)
  {
    auto it = find(vec, value);
    if (it == vec.end())
      return -1;
    return std::distance(vec.begin(), it);
  }
 
  template <class _Type, class _Alloc>
  CepsUInt
  countWithPredicate(
    const CepsVector<_Type,_Alloc>&         vec,
    std::function<CepsBool(const _Type& x)> predicate
  )
  {
    return std::count_if(vec.begin(),vec.end(),predicate);
  }
 
  template <class _Type, class _Alloc>
  CepsUInt
  countWithPredicate(
    const CepsVector<_Type*,_Alloc>&  vec,
    std::function<CepsBool(_Type* x)> predicate
  )
  {
    return std::count_if(vec.begin(),vec.end(),predicate);
  }
 
  template <class _Type, class _Alloc, typename _Compare>
  void
  sort(CepsVector<_Type,_Alloc>& vec, _Compare compare)
  {
    std::sort(vec.begin(),vec.end(),compare);
    return;
  }
 
  template <class _Type, class _Alloc>
  void
  sort(CepsVector<_Type,_Alloc>& vec)
  {
    return sort(vec,std::less<_Type>());
  }
 
  template <class _Type, class _Alloc, typename _Compare>
  CepsVector<CepsUInt>
  getSortPermutation(const CepsVector<_Type,_Alloc>& vec, _Compare compare)
  {
    CepsVector<CepsUInt> p(vec.size());
    std::iota(p.begin(),p.end(),0);
    std::sort(p.begin(),p.end(),[&] (CepsUInt i, CepsUInt j) {
      return compare (vec[i],vec[j]);
    });
    return p;
  }
 
  template <class _Type, class _Alloc>
  CepsVector<CepsUInt>
  getSortPermutation(CepsVector<_Type,_Alloc> &vec)
  {
    return getSortPermutation(vec, std::less<_Type>());
  }
 
  template <class _Type, class _Alloc>
  void
  applyPermutation(CepsVector<_Type, _Alloc>& vec, const CepsVector<CepsUInt>& p)
  {
    const CepsUInt&      n = vec.size();
    CepsVector<CepsBool> done(n,false);
    for (CepsUInt i=0; i<n; ++i)
    {
      if (done[i])
        continue;
 
      done[i]         = true;
      CepsUInt prev_j = i, j = p[i];
      while (i != j)
      {
        std::swap(vec[prev_j], vec[j]);
        done[j] = true;
        prev_j  = j;
        j       = p[j];
      }
    }
    return;
  }
 
  template <class _Type, class _Alloc>
  CepsVector<CepsUInt>
  getIndicesInVector(const CepsVector<_Type,_Alloc>& origin, const CepsVector<_Type,_Alloc>& target)
  {
    const CepsUInt      &n = target.size();
    const CepsUInt      &m = target.size();
    CepsVector<CepsUInt> p (m, static_cast<CepsUInt>(-1));
 
    using eq_t = std::equal_to<_Type>;
 
    // loop to store target elements indices into origin basis
    for (CepsUInt i=0U; i<n; ++i)
      for (CepsUInt j=0U; j<m; ++j)
        if (eq_t {}(origin[i], target[j]))
          p[j] = i;
 
    // only check if target Union origin == target
    for (CepsUInt j=0U; j<m; ++j)
      CEPS_ABORT_IF (p[j]>n,
        "target union with origin is not target. Index of " << p[j] << " is missing into target vec"
      );
 
    return p;
  }
 
  template <class _Type, class _Alloc>
  void
  rightRotate(CepsVector<_Type,_Alloc>& vec, CepsUInt n = 1)
  {
    std::rotate(vec.rbegin(),vec.rbegin()+n,vec.rend());
    return;
  }
 
  template <class _Type, class _Alloc>
  void
  leftRotate(CepsVector<_Type,_Alloc>& vec, CepsUInt n = 1)
  {
    std::rotate(vec.begin(),vec.begin()+n,vec.end());
    return;
  }
 
  /*
  template <class _Type, class _Alloc>
  void
  roll (CepsVector<_Type, _Alloc> &vec, CepsUInt i = 1)
  {
    return rrotate (vec, i);
  }
  */
 
  template <class _Type, class _Alloc>
  CepsUInt
  argmin(CepsVector<_Type,_Alloc>& vec)
  {
    CEPS_ABORT_IF(vec.empty(),"empty vector");
 
    CepsUInt        i_min = 0;
    _Type           x_min = vec[0];
    const CepsUInt &n     = vec.size();
 
    for (CepsUInt i=1; i<n; ++i)
      if (vec[i] < x_min)
      {
        x_min = vec[i];
        i_min = i;
      }
    return i_min;
  }
 
  template <class _Type, class _Alloc, typename _Res>
  CepsUInt
  argmin(CepsVector<_Type,_Alloc>& vec, std::function<_Res(const _Type&)> func)
  {
    CEPS_ABORT_IF(vec.empty(),"empty vector");
 
    CepsUInt        i_min = 0;
    _Type           x_min = vec[0];
    _Res            f_min = func(x_min);
    _Res            f;
    const CepsUInt& n = vec.size ();
 
    for (CepsUInt i=1; i<n; ++i)
    {
      f = func(vec[i]);
      if (f < f_min)
      {
        x_min = vec[i];
        f_min = f;
        i_min = i;
      }
    }
    return i_min;
  }
 
  template <class _Type, class _Alloc>
  CepsUInt
  argmax(CepsVector<_Type,_Alloc>& vec)
  {
    CEPS_ABORT_IF(vec.empty(),"empty vector");
 
    CepsUInt        i_max = 0;
    _Type           x_max = vec[0];
    const CepsUInt& n     = vec.size();
 
    for (CepsUInt i=1; i<n; ++i)
      if (x_max < vec[i])
      {
        x_max = vec[i];
        i_max = i;
      }
    return i_max;
  }
 
  template <class _Type, class _Alloc, typename _Res>
  CepsUInt
  argmax (CepsVector<_Type,_Alloc>& vec, std::function<_Res(const _Type&)> func)
  {
    CEPS_ABORT_IF(vec.empty(),"empty vector");
 
    CepsUInt        i_max = 0;
    _Type           x_max = vec[0];
    _Res            f_max = func(x_max);
    _Res            f;
    const CepsUInt& n = vec.size();
 
    for (CepsUInt i=1; i<n; ++i)
    {
      f = func (vec[i]);
      if (f_max < f)
      {
        x_max = vec[i];
        f_max = f;
        i_max = i;
      }
    }
    return i_max;
  }
 
  template <class _Type, class _Alloc>
  const _Type&
  min(const CepsVector<_Type,_Alloc>& vec)
  {
    return vec[argmin(vec)];
  }
 
  template <class _Type, class _Alloc>
  _Type &
  min(CepsVector<_Type, _Alloc>& vec)
  {
    return vec[argmin(vec)];
  }
 
  template <class _Type, class _Alloc>
  const _Type&
  max(const CepsVector<_Type,_Alloc>& vec)
  {
    return vec[argmax(vec)];
  }
 
  template <class _Type, class _Alloc>
  _Type&
  max (CepsVector<_Type,_Alloc>& vec)
  {
    return vec[argmax(vec)];
  }
 
  template <class _Type, class _Alloc>
  void
  cumSum(const CepsVector<_Type, _Alloc>& vec, CepsVector<_Type, _Alloc>& vecOut)
  {
    CepsUInt N = vec.size();
    vecOut.resize(N+1, _Type(0x0));
    for (CepsUInt i=1U; i<N+1; ++i)
      vecOut[i] = vecOut[i-1] + vec[i-1];
    return;
  }
 
  template <class _Type, class _Alloc>
  CepsVector<_Type,_Alloc>
  cumSum(const CepsVector<_Type,_Alloc>& vec)
  {
    CepsVector<_Type,_Alloc> out = {};
    cumSum(vec,out);
    return out;
  }
 
  template <typename _Input1, typename _Input2>
  void
  setIntersectionIndices(_Input1               first1,
                         _Input1               last1,
                         _Input2               first2,
                         _Input2               last2,
                         CepsVector<CepsUInt>& indices1,
                         CepsVector<CepsUInt>& indices2)
  {
    CepsSize n1 = std::distance(first1, last1);
    CepsSize n2 = std::distance(first2, last2);
 
    indices1.clear();
    indices2.clear();
    indices1.reserve(n1);
    indices2.reserve(n2);
 
    while (first1 != last1 && first2 != last2)
      if (*first1<*first2)
        ++first1;
      else if (*first2<*first1)
        ++first2;
      else  // are same
      {
        indices1.push_back(n1-std::distance(first1,last1));
        indices2.push_back(n2-std::distance(first2,last2));
        ++first1;
        ++first2;
      }
    return;
  }
 
  template <class _Key, class _Value>
  void
  extractValues(const CepsVector<_Key>&   keys1,
                const CepsVector<_Value>& vals1,
                const CepsVector<_Key>&   keys2,
                CepsVector<_Value>&       vals2,
                _Value                    defaultValue = _Value ())
  {
    // sort keys1
    CepsVector<_Key>     skeys1 = keys1;
    CepsVector<CepsUInt> perm1  = ceps::getSortPermutation(skeys1);
    ceps::applyPermutation  (skeys1, perm1);
 
    // sort keys2
    CepsVector<_Key>     skeys2 = keys2;
    CepsVector<CepsUInt> perm2  = ceps::getSortPermutation(skeys2);
    ceps::applyPermutation  (skeys2, perm2);
 
    CepsVector<CepsUInt> idx1;  // indices of intersection in skeys1
    CepsVector<CepsUInt> idx2;  // indices of intersection in skeys2
 
    setIntersectionIndices(skeys1.begin(), skeys1.end(), skeys2.begin(), skeys2.end(), idx1, idx2);
    vals2.resize (keys2.size(), _Value(defaultValue));
 
    const CepsUInt &n = idx1.size();
    for (CepsUInt i = 0; i < n; ++i)
      vals2[perm2[idx2[i]]] = vals1[perm1[idx1[i]]];
 
    return;
  }
 
 
 
 
  template <typename _Type>
  void
  popFront(CepsVector<_Type>& vec)
  {
    if (vec.empty())
      return;
 
    vec.erase(vec.begin());
    return;
  }
 
  template <class _Type>
  void
  distribute(const CepsVector<_Type>& vec, CepsVector<CepsVector<_Type>>& vecs,
             CepsUInt s, CepsBool eqDistrib = true)
  {
    const CepsUInt &n    = vec.size();
    const CepsSize &rest = n % s;
    const CepsSize &div  = n / s;
 
    if (rest !=0 and eqDistrib)
    {
      CEPS_ABORT("The size " + std::to_string(n) +
                 " is not divisible into groups of size " +
                 std::to_string(s) + ". The last one mays be incomplete.");
      return;
    }
 
    vecs.clear();
    vecs.reserve(div);
 
    for (CepsUInt i = 0; i < n; ++i)
    {
      CepsVector<_Type> subVec = {};
      subVec.reserve(s);
      for (CepsUInt j = 0; j < s and i < n; ++j, ++i)
        subVec.push_back(vec[i]);
      vecs.push_back(subVec);
    }
 
    return;
  }
 
  template <class _Type, class _Res>
  _Res
  applyAlong(const CepsVector<_Type> &vec, std::function<void(const _Type &, _Res &)> f, 
             _Res init = _Res ())
  {
    for (const _Type &v : vec)
      f(v,init);
    return init;
  }
 
}  // namespace ceps
 
template <class _Type1, class _Alloc1, class _Type2, class _Alloc2>
CepsVector<_Type1, _Alloc1>&
operator+=(CepsVector<_Type1, _Alloc1>& vec, const CepsVector<_Type2, _Alloc2>& other)
{
  const size_t& n = vec  .size();
  const size_t& m = other.size();
  CEPS_ABORT_IF(n!=m, "You are trying to sum two vectors with different sizes !");
 
  for (CepsUInt i = 0; i < n; ++i)
    vec[i] += other[i];
  return vec;
}
 
template <
  class _Type1,
  class _Alloc1,
  class _Type2,
  class _Alloc2,
  class _ResultType = decltype (std::declval<_Type1> () + std::declval<_Type2> ())>
CepsVector<_ResultType, _Alloc1>
operator+ (const CepsVector<_Type1, _Alloc1> &a, const CepsVector<_Type2, _Alloc2> &b)
{
  using ResultType = decltype (std::declval<_Type1> () + std::declval<_Type2> ());
 
  const size_t &n = a.size ();
  const size_t &m = b.size ();
  CEPS_ABORT_IF (n != m, "you are trying to sum two vectors with different sizes !");
 
  CepsVector<ResultType, _Alloc1> c = {};
  c.resize (n);
  for (CepsUInt i = 0; i < n; ++i)
    c[i] = a[i] + b[i];
  return c;
}
 
template <class _Type1, class _Alloc1, class _Type2, class _Alloc2>
CepsVector<_Type1, _Alloc1> &
operator-= (CepsVector<_Type1, _Alloc1> &vec, const CepsVector<_Type2, _Alloc2> &other)
{
  const size_t &n = vec.size ();
  const size_t &m = other.size ();
  CEPS_ABORT_IF (n != m, "you are trying to substract two vectors with different sizes !");
 
  for (CepsUInt i = 0; i < n; ++i)
    vec[i] -= other[i];
  return vec;
}
 
template <
  class _Type1,
  class _Alloc1,
  class _Type2,
  class _Alloc2,
  class _ResultType = decltype (std::declval<_Type1> () - std::declval<_Type2> ())>
CepsVector<_ResultType, _Alloc1>
operator- (const CepsVector<_Type1, _Alloc1> &a, const CepsVector<_Type2, _Alloc2> &b)
{
  const size_t &n = a.size ();
  const size_t &m = b.size ();
  CEPS_ABORT_IF (n != m, "you are trying to substract two vectors with different sizes !");
 
  CepsVector<_ResultType, _Alloc1> c = {};
  c.resize (n);
  for (CepsUInt i = 0; i < n; ++i)
    c[i] = a[i] - b[i];
  return c;
}
 
template <class _Type1, class _Alloc1, class _Type2, class _Alloc2>
CepsVector<_Type1, _Alloc1> &
operator*= (CepsVector<_Type1, _Alloc1> &vec, const CepsVector<_Type2, _Alloc2> &other)
{
  const size_t &n = vec.size ();
  const size_t &m = other.size ();
  CEPS_ABORT_IF (n != m, "you are trying to multiply two vectors with different sizes !");
 
  for (CepsUInt i = 0; i < n; ++i)
    vec[i] *= other[i];
  return vec;
}
 
template <
  class _Type1,
  class _Alloc1,
  class _Type2,
  class _Alloc2,
  class _ResultType = decltype (std::declval<_Type1> () * std::declval<_Type2> ())>
CepsVector<_ResultType, _Alloc1>
operator* (const CepsVector<_Type1, _Alloc1> &a, const CepsVector<_Type2, _Alloc2> &b)
{
  const size_t &n = a.size ();
  const size_t &m = b.size ();
  CEPS_ABORT_IF (n != m, "you are trying to multiply two vectors with different sizes !");
 
  CepsVector<_ResultType, _Alloc1> c = {};
  c.resize (n);
  for (CepsUInt i = 0; i < n; ++i)
    c[i] = a[i] * b[i];
  return c;
}
 
template <class _Type1, class _Alloc1, class _Type2, class _Alloc2>
CepsVector<_Type1, _Alloc1> &
operator/= (CepsVector<_Type1, _Alloc1> &vec, const CepsVector<_Type2, _Alloc2> &other)
{
  const size_t &n = vec.size ();
  const size_t &m = other.size ();
  CEPS_ABORT_IF (n != m, "you are trying to divide two vectors with different sizes !");
 
  for (CepsUInt i = 0; i < n; ++i)
    vec[i] /= other[i];
  return vec;
}
 
template <
  class _Type1,
  class _Alloc1,
  class _Type2,
  class _Alloc2,
  class _ResultType = decltype (std::declval<_Type1> () / std::declval<_Type2> ())>
CepsVector<_ResultType, _Alloc1>
operator/ (const CepsVector<_Type1, _Alloc1> &a, const CepsVector<_Type2, _Alloc2> &b)
{
  const size_t &n = a.size ();
  const size_t &m = b.size ();
  CEPS_ABORT_IF (n != m, "you are trying to substract two vectors with different sizes !");
 
  CepsVector<_ResultType, _Alloc1> c = {};
  c.resize (n);
  for (CepsUInt i = 0; i < n; ++i)
    c[i] = a[i] / b[i];
  return c;
}
 
template <class _Type, class _Alloc>
std::ostream &
operator<< (std::ostream &os, const CepsVector<_Type, _Alloc> &v)
{
  os << "[";
  for (const _Type &item : v)
    os << item << " ";
  os << "]" << std::flush;
  return os;
}
 
template <class _Type, class _Compare>
std::ostream &
operator<< (std::ostream &os, const CepsSet<_Type, _Compare> &v)
{
  os << "[";
  for (const _Type &item : v)
    os << item << " ";
  os << "]" << std::flush;
  return os;
}