Skip to main content
deleted 2 characters in body
Source Link
UmNyobe
  • 219
  • 2
  • 11
  • AAs you said there are std::min(m,n)/2; rings.
  • the ring R(r, p) has 2*(r+p-2) elements.
  • the top left of the ring has always coordinates (x,x). This is visible in your code :) j = ring_i; v_ring.push_back(mat[ring_i][j]);
  • Your code is using a relatively efficient amount of memory for the in-place transformation, and running in O(m*n) time, which is the best possible.
  • A performance improvement will be to use a single vector for the data in the matrix such that m(x,y) = m.data[x * cols + y]
std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
     // remember ring_i is now
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
     return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}

Now you can rotate the matrix using the view. To be able to rotate in both directions (negative rotationpositive for clockwise, negative counter-clockwise) we use

  • A you said there are std::min(m,n)/2; rings.
  • the ring R(r, p) has 2*(r+p-2) elements.
  • the top left of the ring has always coordinates (x,x). This is visible in your code :) j = ring_i; v_ring.push_back(mat[ring_i][j]);
  • Your code is using a relatively efficient amount of memory for the in-place transformation, and running in O(m*n) time, which is the best possible.
  • A performance improvement will be to use a single vector for the data in the matrix such that m(x,y) = m.data[x * cols + y]
std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
     // remember ring_i is now
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
     return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}

Now you can rotate the matrix using the view. To be able to rotate in both directions (negative rotation) we use

  • As you said there are std::min(m,n)/2; rings.
  • the ring R(r, p) has 2*(r+p-2) elements.
  • the top left of the ring has always coordinates (x,x). This is visible in your code :) j = ring_i; v_ring.push_back(mat[ring_i][j]);
  • Your code is using a relatively efficient amount of memory for the in-place transformation, and running in O(m*n) time, which is the best possible.
  • A performance improvement will be to use a single vector for the data in the matrix such that m(x,y) = m.data[x * cols + y]
std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
     return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}

Now you can rotate the matrix using the view. To be able to rotate in both directions (positive for clockwise, negative counter-clockwise) we use

allow negative rotation
Source Link
UmNyobe
  • 219
  • 2
  • 11

Now you can rotate the matrix using the view. To be able to rotate in both directions (negative rotation) we use

r' = (r % view.size() + view.size()) % view.size();

void rotate_mat (Matrix &mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = (r % view.size() + view.size()) % view.size();
        auto next_location = view.begin();
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}

Now you can rotate the matrix using the view

void rotate_mat (Matrix &mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = r % view.size();
        auto next_location = view.begin();
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}

Now you can rotate the matrix using the view. To be able to rotate in both directions (negative rotation) we use

r' = (r % view.size() + view.size()) % view.size();

void rotate_mat (Matrix &mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = (r % view.size() + view.size()) % view.size();
        auto next_location = view.begin();
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}
added 2026 characters in body
Source Link
UmNyobe
  • 219
  • 2
  • 11
std::pair<int, int> 
rotated_local_next(int i, int j, int hw, int wh)
{
   if(j == 0) //top , special case top-right
   {
        return i == w-1 ? {std::make_pair(i, ++j}) : {std::make_pair(++i, j});  
   }
   if(i == w-1) //right, special case bottom-right
   {
        return j == h-1 ? {std::make_pair(--i, j}) : {std::make_pair(i, ++j});  
   }
   if(j == h-1) //bottom, special case bottom-left
   {
        return i == 0 ? {std::make_pair(i, --j}) : {std::make_pair(--i, j});  
   }
   if(i == 0) //left, special case top-left
   {
        return j == 0 ? {std::make_pair(++i, j} ): {std::make_pair(i, --j});  
   } 

   // unreachable  cannot happen
   throw std::exception{};
}
std::pair<int, int> 
rotated_matrix_next(int x, int y, int ring_i, int nheight, int mwidth )
{
     // remember ring_i is now 
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, nwidth-2*(ring_i+1ring_i), mheight-2*(ring_i+1ring_i));
     return {std::make_pair(local_point.first + ring_i, local_point.second + ring_i});
}

All you need to do now is to implement iterators satisfying MoveAssignable and MoveConstructible. The followingbeginning of your ring is just pseudocodethe element at positing ring, ring, which is also the end of the ring.

struct RingView
{
   class ring_iterator//ring start at 0
   RingView(std::vector<std::vector<int>>& {mat, int ringnumber)
   : matrix(mat)
   , publicrows(mat.size())
   , cols(mat[0].size())
   , ring(ringnumber)
   {}

   std::vector<std::vector<int>>& matrix;
   int rows;
   int cols;
   int ring;

    ptr_matrixclass p;ring_iterator : public std::iterator<std::forward_iterator_tag, int>
    {
    public:

    int x   ring_iterator(RingView* v = nullptr, int yxpos = 0, int ring;ypos = 0)
        : view(v)
        , x(xpos)
        , y(ypos)
   // Forward    {}

        ring_iterator(const ring_iterator& other) = default;
        ring_iterator(ring_iterator&& operator++other) = default;
        ring_iterator& operator =(ring_iterator const&) {= default;
        ring_iterator& operator=(ring_iterator&&) = default;
        virtual ~ring_iterator() = default;

        RingView* view;
        int x;
        int y;

        // Forward
        ring_iterator& operator++() {
            auto posnext = rotated_matrix_next(x, y, ringview->ring, pview->size()>cols, (*p)[0].size()view->rows); 

            x = posnext.first;
   ring_iterator next_iter        y = posnext.second;
            return *this;
        }

        ring_iterator next_iter.operator++(int) {
            auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
            ring_iterator next_iter = posnext.first;*this;
            next_iter.x = posnext.first;
            next_iter.y = posnext.second;
            return next_iter;
        } 

        bool operator==(const ring_iterator& other) const {
            if(view == nullptr ){
            // Swappable
   return other.view == nullptr;
         void swap(ring_iterator& other) {}
            return view->ring == other.view->ring && int&x mine== =other.x (*p)[x][y];
&& y == other.y;
        }

      int& theirs bool operator!=(const ring_iterator& other.(*p)[x][y]; const {
            return !(*this == other);
   int tmp = mine;  }

        // usually required
       mine =int& theirs;operator*() {
            return view->matrix[x][y];
    theirs = tmp;
  }
        int* operator->() }{
            // usuallyreturn required&(view->matrix[x][y]);
        }
    reference};

 operator*   ring_iterator begin()
    {
        return ring_iterator(*pthis, ring, ring)[x][y];;
    } 

    ring_iterator end()
    {
   pointer operator->    return begin();
 { &(  }

    int size(*p)[x][y] const
    {
        return 2*(rows+cols -2); }- 4 * ring;
    }
};

Once begin(), end() is implemented your code will becomeNow you can rotate the matrix using the view

forvoid rotate_mat (autoMatrix ring_i=0;&mat, ring_i<n_rings;int ++ring_ir){
     
   auto n_rings RingWiew= viewstd::min(&m, mmat.size(), m[0]mat[0].size(),)/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = r % view.ringNumberOfElementssize();
     
    auto std::rotate(next_location = view.begin(),;
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(), r_modulo)next_location,v_ringview.end());
    }
}

Full code : https://ideone.com/I3vg5v

std::pair<int, int> 
rotated_local_next(int i, int j, int h, int w)
{
   if(j == 0) //top , special case top-right
   {
        return i == w-1 ? {i, ++j} : {++i, j};  
   }
   if(i == w-1) //right, special case bottom-right
   {
        return j == h-1 ? {--i, j} : {i, ++j};  
   }
   if(j == h-1) //bottom, special case bottom-left
   {
        return i == 0 ? {i, --j} : {--i, j};  
   }
   if(i == 0) //left, special case top-left
   {
        return j == 0 ? {++i, j} : {i, --j};  
   }
   // unreachable       
}
std::pair<int, int> 
rotated_matrix_next(int x, int y, int ring_i, int n, int m)
{
     // remember ring_i is now 
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, n-2*(ring_i+1), m-2*(ring_i+1))
     return {local_point.first + ring_i, local_point.second + ring_i};
}

All you need to do now is to implement iterators satisfying MoveAssignable and MoveConstructible. The following is just pseudocode

    class ring_iterator
    {
        public:
            ptr_matrix p;
            int x, int y, int ring;
            
            // Forward
            ring_iterator operator++() { 
                 posnext = rotated_matrix_next(x, y, ring, p->size(), (*p)[0].size());
                 ring_iterator next_iter = *this;
                 next_iter.x = posnext.first;
                 next_iter.y = posnext.second;
            }
            
            
            // Swappable
            void swap(ring_iterator& other) {
                 int& mine = (*p)[x][y];
                 int& theirs = other.(*p)[x][y];
                 int tmp = mine;
                 mine = theirs;
                 theirs = tmp;
            }
            // usually required
            reference operator*() { return (*p)[x][y]; }
            pointer operator->() { &((*p)[x][y]); }
    };

Once begin(), end() is implemented your code will become

for(auto ring_i=0; ring_i<n_rings; ++ring_i){
     
     RingWiew view(&m, m.size(), m[0].size(), ring_i);
     int r_modulo = r % view.ringNumberOfElements();
     
     std::rotate(view.begin(),std::advance(view.begin(), r_modulo),v_ring.end());
}
std::pair<int, int>
rotated_local_next(int i, int j, int w, int h)
{
   if(j == 0) //top , special case top-right
   {
        return i == w-1 ? std::make_pair(i, ++j) : std::make_pair(++i, j);
   }
   if(i == w-1) //right, special case bottom-right
   {
        return j == h-1 ? std::make_pair(--i, j) : std::make_pair(i, ++j);
   }
   if(j == h-1) //bottom, special case bottom-left
   {
        return i == 0 ? std::make_pair(i, --j) : std::make_pair(--i, j);
   }
   if(i == 0) //left, special case top-left
   {
        return j == 0 ? std::make_pair(++i, j): std::make_pair(i, --j);
   } 

   // cannot happen
   throw std::exception{};
}
std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
     // remember ring_i is now
     auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
     return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}

All you need to do now is to implement iterators satisfying MoveAssignable and MoveConstructible. The beginning of your ring is the element at positing ring, ring, which is also the end of the ring.

struct RingView
{
    //ring start at 0
   RingView(std::vector<std::vector<int>>& mat, int ringnumber)
   : matrix(mat)
   , rows(mat.size())
   , cols(mat[0].size())
   , ring(ringnumber)
   {}

   std::vector<std::vector<int>>& matrix;
   int rows;
   int cols;
   int ring;

    class ring_iterator : public std::iterator<std::forward_iterator_tag, int>
    {
    public:

        ring_iterator(RingView* v = nullptr, int xpos = 0, int ypos = 0)
        : view(v)
        , x(xpos)
        , y(ypos)
        {}

        ring_iterator(const ring_iterator& other) = default;
        ring_iterator(ring_iterator&& other) = default;
        ring_iterator& operator =(ring_iterator const&) = default;
        ring_iterator& operator=(ring_iterator&&) = default;
        virtual ~ring_iterator() = default;

        RingView* view;
        int x;
        int y;

        // Forward
        ring_iterator& operator++() {
            auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows); 

            x = posnext.first;
            y = posnext.second;
            return *this;
        }

        ring_iterator operator++(int) {
            auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
            ring_iterator next_iter = *this;
            next_iter.x = posnext.first;
            next_iter.y = posnext.second;
            return next_iter;
        } 

        bool operator==(const ring_iterator& other) const {
            if(view == nullptr ){
                return other.view == nullptr;
            }
            return view->ring == other.view->ring && x == other.x && y == other.y;
        }

        bool operator!=(const ring_iterator& other) const {
            return !(*this == other);
        }

        // usually required
        int& operator*() {
            return view->matrix[x][y];
        }
        int* operator->() {
            return &(view->matrix[x][y]);
        }
    };

    ring_iterator begin()
    {
        return ring_iterator(this, ring, ring);
    } 

    ring_iterator end()
    {
        return begin();
    }

    int size() const
    {
        return 2*(rows+cols -2) - 4 * ring;
    }
};

Now you can rotate the matrix using the view

void rotate_mat (Matrix &mat, int r){
    auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        RingView view(mat,ring_i);
        int r_modulo = r % view.size();
        auto next_location = view.begin();
        std::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}

Full code : https://ideone.com/I3vg5v

Source Link
UmNyobe
  • 219
  • 2
  • 11
Loading