(kind of) rotating and slicing elements of a container in C++

Question

Hi,

I have a std::vector that holds a Point struct (x,y,z and some other non-pointer types).

These points are control points for drawing a bspline curve. I'm not having trouble drawing the curve, but complications arise when I have to close the curve, which involves adding control points (alredy existing inside the container) in certain order.

For example, if I have 5 control points

A B C D E

I would have to get 5 sequences like this:

A B C D  //curve is drawn from B to C
B C D E  //curve is drawn from C to D
C D E A  //curve is drawn from D to E 
D E A B  //curve is drawn from E to A
E A B C  //curve is drawn from A to B

Initially, I went with std::rotate, but then realized it wasn't what I was looking for.

I'm having trouble implementing this. Best I got is a non-working version in C++ (the reason of this failing is not the question, here's a snippet).

static char letters = 'A';
typedef struct Point{
        float x,y,z;
        char name;

        Point(float x,float y,float z=0):name(letters++){}

}Point;
typedef std::vector<Point> lpoints;

void
rotate(lpoints& points)
{
    for (unsigned int i =0;i<5;i++){
                lpoints::iterator beg =   lista.begin() + (i%5);
                lpoints::iterator dernier=lista.begin()+(4+i)%6; 

                lpoints subseq(beg,dernier); //4 points in subseq

                //do stuff with subseq                                                       
    }
}

Is there a way to do this? I know I can implement it with many nested for loops, but i'm trying to avoid that, looking for something more elegant (if the word fits).

Thanks in advance.

Answer 1

What, exactly, is wrong with using std::rotate()? For example,

std::vector<int> v(5);

std::rotate(v.begin(), v.begin() + 1, v.end());
std::vector<int> firstFour(v.begin(), v.begin() + 4);

firstFour then contains the first four elements from the rotated vector. If you use this in a loop and run it v.size() times, you will get the five vectors you have in the question.

Answer 2

If you are willing to use more space, you can first append lpoints to itself and then increment iterators while taking subseq if needed. This also caters to your '5 different vectors or one long one', as you can just work with the iterators of the doubled vector, instead of creating new ones.

Pardon me, I haven't written C++ for a while, so here is C++ like pseudo code

void 
rotate(lpoints& points) 
{ 
    pointsDouble = Append(points,points); // Do your own implementation
                                 // if points is A B C D E
                                 // pointsDouble is A B C D E A B C D E

    pointsDouble::iterator beg =   lista.begin(); 
    pointsDouble::iterator dernier=lista.begin()+4;  

    for (unsigned int i =0;i<5;i++){ 

        lpoints subseq(beg,dernier); //4 points in subseq 

        //do stuff with subseq

       ++beg; ++dernier;

    } 
}

The for loop could perhaps be written better too, in terms of begin and end(or dernier) instead of the loop variable i.

For an append you can probably use std::copy (caveat: I am rusty in C++).

lpoints pointsDouble(points);
std::copy(points.begin(), points.end(), std::back_inserter(pointsDouble));

(back_inserter suggested by Luc)

Answer 3

could you do something like:

// vector = (a,b,c,d,e);

front = vector.front();
vector.pop_front();
vector.push_back(front);
// now you have (b,c,d,e,a);

repeat whatever number of times. might be inefficient in terms of memory shuffles however

Answer 4

Pretty much what James wrote above:

vector <char> newv[5];

for(int i=0; i<5; i++)
{
    newv[i].insert(newv[i].begin(),v.begin(), v.begin()+4);
    std::rotate(v.begin(), v.begin()+1, v.end());
}

Tested and it works.

Answer 5

All the above answers require mutating a container. It is possible to solve this without doing so and still use stl / boost algorithms. Appologies if the below doesn't quite compile as I haven't tested it.

std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);

for(int i = 0; i < 5; i ++)
{
    using boost::join;
    using boost::adaptors::sliced;
    using std::ostream_iterator;
    using std::cout;
    using boost::copy;

    copy
        ( join(v | sliced(i,4), v | sliced(0, (4 + i) % 5))
        , ostream_iterator<int>(cout, " ") 
        )
    }
    cout << std::endl;

}

The doc for boost::sliced is at

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/adaptors/reference/sliced.html#range.reference.adaptors.reference.sliced.sliced_example