remove_neighbors in STL like fashion

Question

I'm trying to implement, in STL fashion, an algorithm with the following functionallity:

Given a range [first,last), a neighborhood span nSpan and a (binary) predicate Pred, it removes elements from that range, so that Pred is NOT true for any remaining elements distant from each other at most nSpan

Examples :

• nSpan=1 and Pred=Equality => decays to the std::unique algorithm

• nSpan=2 and Pred=PointEquality => sanitize polyline

               + P2
               | 
               v
               ^
  P0           |          P4               P0          P1          P4
  +---->-------+---->------+    becomes    +---->-------+---->------+
             P1  P3
  

• nSpan=2 and Pred=Equality: ['a', 'b', 'a', 'd', 'e', 'd', 'f'] -> ['a', 'd', 'f']

In the last example, it's obvious that (to prevent the algorithm from going ambiguous) we sweep from the first iterator and on, while checking up to nSpan distance to remove elements (otherwise there would be multiple ways to remove elements).

My attempt so far (code listing below) has the following shortcomings:

• After a first sweep the new range may have new elements that are invalid, so a recursive functionality (again scaning from the new start towards the end) is needed to rescan the range (or maybe immitate recursion every time a removal happens)
• It's not implemented as a remove function but as an erase one (I need a remove one and it seems significantly more difficult) and that forces to supply the whole container as an argument instead of a range (ideally the algorithm should be container agnostic)

I'm listing a first attempt

    template<typename Cont, typename It, class Pr>
    void erase_neighbors(Cont &cont, It first, It last, int nSpan, Pr Pred)
    {
        if (0 < nSpan && nSpan < std::distance(first, last)) for (It it2; (it2 = first), first != last; )
        {
            if (nSpan < std::distance(it2, last))
            {
                std::advance(it2, nSpan);
                if (Pred(*first, *it2))
                {
                    first = cont.erase(first, it2);
                    last = cont.end();
                    continue;
                }
            }
            ++first;
        }
    }

Ideal signature

template<typename It, class Pr>
It remove_neighbors(It first, It last, int nSpan, Pr Pred);

Ideal implementation : non c++11 and without boost (even though if there is a related boost algorithm I would appreciate knowing about it)

Answer 1

To the extent I understand the problem statement, this seems to do what you want. See it in action:

template<typename It, class Pr>
It remove_neighbors(It first, It last, int nSpan, Pr Pred) {
  if (first == last || nSpan <= 0) return last;

  It lastGood = first;
  It cur = first;
  ++cur;
  for (; cur != last; ++cur) {
    bool found = false;
    It back = lastGood;
    for (int i = nSpan; i > 0; --i, --back) {
      if (Pred(*back, *cur)) {
        found = true;
        lastGood = back;
        break;
      }
      if (back == first) break;
    }

    if (!found) {
      ++lastGood;
      *lastGood = std::move(*cur);
    }
  }
  ++lastGood;
  return lastGood;
}

This makes no more than N moves/copies, and no more than N * nSpan invocations of Pred.

Answer 2

You can avoid both the problems you listed, by maintaining a table of next element. So each position will point to the next valid position that qualifies as the good neighbour without violating the predicate, like so:

map<unsigned, unsigned> neigh_table;
while(it != end){
    neigh = startneigh = it + 1;
    do{
        if(pred(it, neigh)) //if predicate fails, restart with a new neighbour
            neigh = startneigh = neigh + 1;
        else
            ++neigh;
    }while(neigh - startneigh < range && neigh != end);

    neigh_table[it-start] = startneigh - start;
    it = neigh;
}

At the end of the operation, you can either:

1. Return the lookup table of neighbours for the user to process or
2. Return a list of the iterators, separate from the container, like a vector/list of iterators that are neighbours, by walking the map yourself inside the function.

In either case you won't be able to modify the container, without passing in the actual container to the function. This is why functions such as stl::remove don't modify the length of the container. See remove-erase idiom, for examples of how to actually modify the container, using stl::remove.