path: root/utils/indices_after.h

#ifndef INDICES_AFTER_REMOVING_H
#define INDICES_AFTER_REMOVING_H

//TODO: instead of making REMOVED a constant, make it class state (defaults to -1 as before, of course).

#include <assert.h>
#include <boost/config.hpp> // STATIC_CONSTANT
#include <algorithm> //swap
#include <iterator>

// iterator wrapper.  inverts boolean value.
template <class AB>
struct keep_not_marked
{
    typedef keep_not_marked<AB> self_type;
    AB i;
    bool operator *() const
    {
        return !*i;
    }
    void operator++()
    {
        ++i;
    }
    bool operator ==(self_type const& o)
    {
        return i==o.i;
    }
};

// outputs sequence to out iterator, of new indices for each element i, corresponding to deleting element i from an array when remove[i] is true (-1 if it was deleted, new index otherwise), returning one-past-end of out (the return value = # of elements left after deletion)
template <class KEEP,class KEEPe,class O>
unsigned new_indices_keep(KEEP i, KEEPe end,O out) {
    unsigned f=0;
    while (i!=end)
      *out++ = *i++ ? f++ : (unsigned)-1;
    return f;
};

template <class It,class KeepIf,class O>
unsigned new_indices_keep_if_n(unsigned n,It i,KeepIf const& r,O out)
{
    unsigned f=0;
    while(n--)
      *out++ = r(*i++) ? f++ : (unsigned)-1;
    return f;
}

template <class KEEP,class O>
unsigned new_indices_keep(KEEP keep,O out) {
  return new_indices_keep(keep.begin(),keep.end(),out);
}

template <class V,class Out,class Permi>
void copy_perm_to(Out o,V const& from,Permi i,Permi e) {
  for (;i!=e;++i)
    *o++=from[*i];
}

//to cannot be same as from, for most permutations.  for to==from, use indices_after::init_inverse_order instead.
template <class Vto,class Vfrom,class Perm>
void remap_perm_to(Vto &to,Vfrom const& from,Perm const& p) {
  to.resize(p.size());
  copy_perm_to(to.begin(),from,p.begin(),p.end());
}

// given a vector and a parallel sequence of bools where true means keep, keep only the marked elements while maintaining order.
// this is done with a parallel sequence to the input, marked with positions the kept items would map into in a destination array, with removed items marked with the index -1.  the reverse would be more compact (parallel to destination array, index of input item that goes into it) but would require the input sequence be random access.
struct indices_after
{
  BOOST_STATIC_CONSTANT(unsigned,REMOVED=(unsigned)-1);
  unsigned *map; // map[i] == REMOVED if i is deleted
  unsigned n_kept; // important to init this.
  unsigned n_mapped;
  template <class AB,class ABe>
  indices_after(AB i, ABe end) {
    init(i,end);
  }

  template <class Order>
  void init_inverse_order(unsigned from_sz,Order const& order) {
    init_inverse_order(from_sz,order.begin(),order.end());
  }
  template <class OrderI>
  void init_inverse_order(unsigned from_sz,OrderI i,OrderI end) {
    init_alloc(from_sz);
    unsigned d=0;
    n_kept=0;
    for(;i!=end;++i) {
      assert(d<from_sz);
      map[d++]=*i;
      ++n_kept;
    }
    for(;d<from_sz;++d)
      map[d]=REMOVED;
  }

  template <class Vec,class R>
  void init_keep_if(Vec v,R const& r)
  {
    n_mapped=v.size();
    if ( !n_mapped ) return;
    map=(unsigned *)::operator new(sizeof(unsigned)*n_mapped);
    n_kept=new_indices_keep_if_n(n_mapped,r,map);
  }
  // contents uninit.
  void init_alloc(unsigned n) {
    free();
    n_mapped=n;
    map=n_mapped>0 ?
      (unsigned *)::operator new(sizeof(unsigned)*n_mapped)
      : 0;
  }
  void init_const(unsigned n,unsigned map_all_to) {
    init_alloc(n);
    for (unsigned i=0;i<n;++i)
      map[i]=map_all_to;
    n_kept=(map_all_to==REMOVED)?0:n;
  }

  void init_keep_none(unsigned n) {
    init_const(n,REMOVED);
    n_kept=0;
  }

  template <class AB,class ABe>
  void init(AB i, ABe end) {
    n_mapped=end-i;
    if (n_mapped>0) {
      map=(unsigned *)::operator new(sizeof(unsigned)*n_mapped);
      n_kept=new_indices_keep(i,end,map);
    } else {
      n_kept=0;
      map=NULL;
    }
  }
  template <class A>
  void init(A const& a)
  {
    init(a.begin(),a.end());
  }

  template <class A>
  explicit indices_after(A const& a)
  {
    init(a.begin(),a.end());
  }
  indices_after() : n_mapped(0) {}
  ~indices_after()
  {
    free();
  }
  void free() {
    if (n_mapped)
      ::operator delete((void*)map);
    n_mapped=0;
  }

  bool removing(unsigned i) const
  {
    return map[i] == REMOVED;
  }
  bool keeping(unsigned i) const
  {
    return map[i] != REMOVED;
  }

  unsigned operator[](unsigned i) const
  {
    return map[i];
  }

  template <class Vec>
  void do_moves(Vec &v) const
  {
    assert(v.size()==n_mapped);
    unsigned i=0;
    for (;i<n_mapped&&keeping(i);++i) ;
    for(;i<n_mapped;++i)
      if (keeping(i))
        v[map[i]]=v[i];
    v.resize(n_kept);
  }

  template <class Vec>
  void do_moves_swap(Vec &v) const
  {
    using std::swap;
    assert(v.size()==n_mapped);
    unsigned i=0;
    for (;i<n_mapped&&keeping(i);++i) ;
    for(;i<n_mapped;++i)
      if (keeping(i))
        std::swap(v[map[i]],v[i]);
    v.resize(n_kept);
  }

  template <class Vecto,class Vecfrom>
  void copy_to(Vecto &to,Vecfrom const& v) const {
    to.resize(n_kept);
    for (unsigned i=0;i<n_mapped;++i)
      if (keeping(i))
        to[map[i]]=v[i];
  }

  //transform collection of indices into what we're remapping.  (input/output iterators)
  template <class IndexI,class IndexO>
  void reindex(IndexI i,IndexI const end,IndexO o) const {
    for(;i<end;++i) {
      unsigned m=map[*i];
      if (m!=REMOVED)
        *o++=m;
    }
  }

  template <class VecI,class VecO>
  void reindex_push_back(VecI const& i,VecO &o) const {
    reindex(i.begin(),i.end(),std::back_inserter(o));
  }

private:
  indices_after(indices_after const&)
  {
    map=NULL;
  }
};

#endif