fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. template<typename It, class Pr>
  7. It remove_neighbors(It first, It last, int nSpan, Pr Pred) {
  8.   if (first == last || nSpan <= 0) return last;
  9.  
  10.   It lastGood = first;
  11.   It cur = first;
  12.   ++cur;
  13.   for (; cur != last; ++cur) {
  14.     bool found = false;
  15.     It back = lastGood;
  16.     for (int i = nSpan; i > 0; --i, --back) {
  17.       if (Pred(*back, *cur)) {
  18.         found = true;
  19.         lastGood = back;
  20.         break;
  21.       }
  22.       if (back == first) break;
  23.     }
  24.  
  25.     if (!found) {
  26.       ++lastGood;
  27.       *lastGood = std::move(*cur);
  28.     }
  29.   }
  30.   ++lastGood;
  31.   return lastGood;
  32. }
  33.  
  34. void test_remove_neighbors(const string& in, int nSpan) {
  35.   vector<char> v(in.begin(), in.end());
  36.   vector<char>::iterator trash =
  37.       remove_neighbors(v.begin(), v.end(), nSpan, equal_to<char>());
  38.   string out(v.begin(), trash);
  39.   cout << "In: " << in << " span: " << nSpan << " out: " << out << endl;
  40. }
  41.  
  42. int main(int argc, char *argv[])
  43. {
  44.   // No ops:
  45.   test_remove_neighbors("abab", 1);
  46.   test_remove_neighbors("abcabc", 2);
  47.   // unique
  48.   test_remove_neighbors("aabbaaabbb", 1);
  49.   // simple
  50.   test_remove_neighbors("abadedf", 2);
  51.   // backtracking
  52.   test_remove_neighbors("abcba", 2);
  53.   return 0;
  54. }
  55.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
In: abab span: 1 out: abab
In: abcabc span: 2 out: abcabc
In: aabbaaabbb span: 1 out: abab
In: abadedf span: 2 out: adf
In: abcba span: 2 out: a
https://ideone.com/ryTLcs
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!