Splice elements from list that meets a certain criteria

[V1sk3y]

Here's what I want to do:
Two consecutive integers in a list (or perhaps vector) should meet a criteria given by a function. If (CriteriaFunction(int1,int2) returns true)
I want to check this criteria for all consecutive pairs of integers.
All the integers that meet the criteria should be inserted into a new list.
I then want to remove all these integers except the first and the last one meeting the criteria and instead insert a new integer in between.

Say I have List1 = 1,2,3,4,5,6,7,8,9,10
Lets say 8,9 and 9,10 and also 10,1 returns true when inserted into the criteriafunction.
(The last and the first integers should be regarded as consecutive to eachother)
I now want to create List2 = 8,9,10,1
After that I want to remove 9,10 from List1 and replace them with integer x so I get: List1 = 1,2,3,4,5,6,7,8,x

I haven't used list much and I really have no idea how to write the code. I looked around for a solution but since I had a hard time phrasing my problem it was hard to google for it. I found out that the splice-function could be useful but I can't understand how to use with the criteria. I presumed that a list would be best since I want to remove elements from anywhere in it.

Thankful for any help even though it can be hard to understand my explanation of the problem

[hamsterman]

Well, the biggest problem here is the cyclic property of your list.

If that didn't exist, it would be fairly simple. The idea is to get the iterators to first and last element in the range that meets the criteria. Once you have that, you can easily copy, erase and replace what you want.
Should I explain how exactly that would work?

The problem with a cycle is that if (in your example list) 1, 2 and 2, 3 and 10, 1 meet the requirement, a naive method will remove 2, while it should really be removing 1, 2. The only solution I can offer is to start from pair 10, 1 and (if it meets the condition) go backwards until some pair doesn't. Then start checking normally from the pair 1, 2 forward. That is, the range that includes pair 10, 1 has to be treated as a special case.

[Evolve]

I would suggest you use something that you are more comfortable with(such as vectors or even arrays) , and when you have functional code, re-write it to use lists. Furthermore you could have a look at the algorithms from standard template library to make your life a little easier (http://www.cplusplus.com/reference/algorithm).

More specific to your problem you might want to have a look at "replace_if" from the STL Algorithms to help you. If your approach is right you only need one list , vector or array.

[V1sk3y]

That would be really helpful hamsterman. Perhaps this should have been in the beginners forum instead. A bit of example code would make my day because I really can't figure out how to write it.

Thanks for your answers though, it feels like I've gotten closer to the solution at least.

Btw can't the cyclic property be solved by using the modulus operator: (i+1)%List1.size()
or something like that?

[hamsterman]

#include <iostream>
#include <list>
#include <algorithm>

bool condition( int a, int b ){
   return a+1 == b;
}

int arr[] = {19, 1, 2, 3, 4, 19, 1, 2, 3, 19, 1, 2 };

int main() {
   std::list<int> l(sizeof(arr)/sizeof(int));
   std::copy( arr, arr+sizeof(arr)/sizeof(int), l.begin() );

   std::list<int>::iterator first = l.begin(), second = l.begin()++, begin, end;
   bool begin_found = false;

   for( ; second != l.end(); first=second, second++ ) {
      if( condition( *first, *second ) ){
         if( !begin_found ){
            begin = first;
            begin_found = true;
         }
      }else{
         if( begin_found ){
            end = second;
            l.insert( l.erase( ++begin, --end ), 2520 );
            begin_found = false;
         }
      }
   }

   for( first = l.begin(); first != l.end(); first++ ) std::cout << *first << '\n';

   std::cin.get();
   return 0;
}

Here is a code which deals with the problem without a cycle. I tried to keep it clean, but I appear to have failed. Does that give you a better idea about how this works? I guess you could append the cyclic part to this. Though now that I think about it, it may be better if you first iterate through list without erasing anything, find the beginning and end of each range, store them in another container, then deal with every one of those ranges except the first and the last. You need to check the first and last elements of the list to decide what to do with them.

Btw can't the cyclic property be solved by using the modulus operator: (i+1)%List1.size()
or something like that?

Well, firstly, lists can't be accessed with an index. Similar thing can be written for iterators though. It is possible to use this, I'm not sure if this will make things easier, but do give it a try.Instead of %, use if( it == my_list.end() ) it = my_list.begin();. So that you don't loop infinitely, you'll need to count how many elements you've processed. You'll have to erase elements one by one, as the erase function which takes two iterators would not wrap. You'll have to start looking for ranges to replace from the first pair which does not meet the condition. Can't think of anything else.

[Duthomhas]

The circular property isn't really an issue so long as you can afford some extra memory usage and a little pre-processing and post-processing on the list. For a single element overlap on your predicate, the following makes it simple enough:

given list 1 2 3 4 5:
preprocess: append copy of first element to end of list: 1 2 3 4 5 1
your function: do your transformation on the list...: 1 2 3 4 x 1
postprocess: delete last element of list: 1 2 3 4 x

Hope this helps.

[V1sk3y]

I can't believe how fast you answer! :D

I see there were a lot of things that I forgot to mention that I think makes things a lot easier:
*There will never be more than one range that satisfies the condition (so when you've found one range you don't have to look anymore)
*Even if no integers will be removed I still need to input an integer in between the others.
*It doesn't have to be a list, I just thought that would be easier but I think I managed to do it with a vector.
*And most importantly what I based my whole solution to the cyclic problem on, it doesn't really matter where the vector starts so you can rearrange it anyway you like as long as the integers are in the same order as before.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool condition(int a, int b){
      return a+1 == b;
}
int arr[]= {14, 15,16, 2, 19, 17, 11, 13 };

int main() {
   int first = -1, last = -1;
   vector<int> v(sizeof(arr)/sizeof(int));
   copy( arr, arr+sizeof(arr)/sizeof(int), v.begin() );

   if ( condition(v.back(),v.front()) ){
      //Do complicated cyclic procedure
      int range=0;
      vector<int> vcopy = v;
      v.clear();
      for (int i = vcopy.size()-1; i!=0; i--){
         if ( condition(vcopy[i-1],vcopy[i]) ){
            if (-1==first){
               first=i-1;
               
            }
         }
         else if ( -1!=first && condition(vcopy[i-1],vcopy[i])==false ){
               break;
         }
         else{
            first=vcopy.size()-1;
            break;
         }
      }
      v.insert(v.begin(),vcopy.begin()+first,vcopy.end());
      for (int i = 0; i <vcopy.size(); i++){
         if ( condition(vcopy[i],vcopy[(i+1)%vcopy.size()])==false){
            last=i+1;
            break;
         }
      }
      v.insert(v.end(),vcopy.begin(),vcopy.begin()+last);
      range=v.size();
      v.insert(v.end(),vcopy.begin()+last,vcopy.begin()+first);
      first=1;
      last=range-1;
   }
   else{
      //Do uncomplicated non-cyclic procedure
      for (int i = 0; i<v.size(); i++){
         if ( condition(v[i],v[(i+1)%v.size()]) ){
            if (-1 == first) first=i+1;
         }
         else if(-1 != first && -1 == last){
            last = i;
            break;
         }
      }
   }
   v.erase(v.begin()+first,v.begin()+last);
   v.insert(v.begin()+first, 2520);

   vector<int>::iterator it;
   for (it = v.begin(); it<v.end(); it++)
      cout << " "<< *it;
   cin.get();
   return 0;
}

Now the copying to a new vector part shouldn't be that hard either. There is one thing I wonder though about the part with:

std::list<int> l(sizeof(arr)/sizeof(int));
std::copy( arr, arr+sizeof(arr)/sizeof(int), l.begin() );

I just copied that straight off but didn't understand what it does. Tried to google it and it seems it has something to do with the datasize? I guess I haven't reached that level of programming.

So grateful for all your help, if you have any comments or criticism on my code just hit me.

Cheers

[hamsterman]

If it works, then it's fine. Except for that redundant call to condition() on line 28..

I just copied that straight off but didn't understand what it does.

sizeof returns the number of bytes something takes. An array of N integers will take N times more bytes than a single integer, so if I have the size of the whole array and divide it by the size of a single element of that array, I get the number of elements in it.
std::copy is a function defined in <algorithm>. See reference for details.
The argument of a list constructor is the number of elements you want it to have. You need this since copy won't push the elements for you.

Also, here's another simple way to do it.

#include <iostream>
#include <vector>
#include <algorithm>

bool condition( int a, int b ){
   return a+1 == b;
}

int arr[] = { 3, 4, 19, 1, 2 };

int main() {
   std::vector<int> v(sizeof(arr)/sizeof(int));
   std::copy( arr, arr+sizeof(arr)/sizeof(int), v.begin() );

   int first, last;
   bool prev = condition( v.back(), v.front() ), current;

   for( unsigned i = 0; i < v.size()+1; i++ ) {

      int a = i >= v.size() ? i-v.size() : i;
      int b = i+1 >= v.size() ? i+1-v.size() : i+1;

      if( current = condition( v[a], v[b] ) ){
         if( prev == false ) first = a;
      }else if( prev == true ) last = b;
      prev = current;

   }

   if( first < last ) {
      v.insert( v.erase( v.begin()+first+1, v.begin()+last-1 ), 2520 );
   }else{
      v.erase( v.begin()+first+1, v.end() );
      v.erase( v.begin(), v.begin()+last-1 );
      v.insert( v.end(), 2520 );
   }

   for( std::vector<int>::iterator it = v.begin(); it != v.end(); it++ ) std::cout << *it << '\n';

   std::cin.get();
   return 0;
}

The idea is that what you need to find are points where the range ends and where it begins. There are points where the value returned by condition() changes. If you keep the previous value, you can find that change. If it goes from 0 to 1, the range just started. If it goes from 1 to 0, it has ended.
When you find the two points, you can do whatever you like.

[V1sk3y]

When I tried both my code and yours with a large number of executions they seemed to take equally long to execute. Your code feels more logical though and looks more elegant in my opinion. Had to add one line though because it didn't work when last number in the vector was also the last one that fulfilled the condition.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool condition( int a, int b ){
   return a+1 == b;
}

int arr[] = {19, 1, 2, 3};
//int arr[] = {19, 19, 19};
//int arr[] = {3, 4, 19, 1, 2};
//int arr[] = {1, 2, 3, 19, 19};

int main() {
   vector<int> v(sizeof(arr)/sizeof(int));
   vector<int> nv; // The other vector to which the range will be copied
   copy( arr, arr+sizeof(arr)/sizeof(int), v.begin() );

   int first=-1, last=-1;
   bool prev = condition( v.back(), v.front() ), current;

   for( unsigned i = 0; i < v.size()+1; i++ ) {

      int a = i >= v.size() ? i-v.size() : i;
      int b = i+1 >= v.size() ? i+1-v.size() : i+1;

      if( current = condition( v[a], v[b] ) ){
         if( prev == false ) first = a;
      }else if( prev == true ) last = b;
      prev = current;
   }
   if (last==0 && !condition(v.back(),v.front())) last=v.size(); // Added this line

   if( first < last ) {
      nv.insert(nv.begin(), v.begin()+first, v.begin()+last);
      v.insert( v.erase( v.begin()+first+1, v.begin()+last-1 ), 2520 );
   }else if(first > last){
      nv.insert(nv.begin(),v.begin()+first,v.end());
      nv.insert(nv.end(),v.begin(),v.begin()+last);
      v.erase( v.begin()+first+1, v.end() );
      v.erase( v.begin(), v.begin()+last-1 );
      v.insert( v.end(), 2520 );
   }


   for( vector<int>::iterator it = v.begin(); it != v.end(); it++ ) cout << *it << ' ';
   cout << '\n';
   for( vector<int>::iterator it = nv.begin(); it!= nv.end(); it++) cout << *it << ' ';

   cin.get();
   return 0;
}

Cheers, think it works with all possible vectors it will recieve now =)