6
\$\begingroup\$

The point of this algorithm is to see if an element exists in a NxN matrix that has its rows and columns sorted.

What would you change? What did I do well? Both perspectives help so I am not left guessing.

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
/* Author: Matthew Everett Hoggan                                           */
/* Date: August 8, 2011                                                     */
/* Problem Statement:                                                       */
/* Given an matrix such that every row is sorted and every column is sorted */
/* write a function "find_kth_element_and_return_rowXcol" that returns a    */
/* a pair<int,int> where the element was found. If it is not found return   */
/* <N,N> to indicate to user that their value was not found                 */

namespace Matrix 
{
    /* This class is designed to solve the problem at hand                  */
    /* The method definitions are described where they are defined          */
    /* Note this matrix is a N x N square matrix                            */
    class RandomOrderedMatrix 
    {
        public:
            RandomOrderedMatrix( int N );
            ~RandomOrderedMatrix( );
            void find_element( int element );
            void print_matrix( );
            std::pair<int,int>& get_coord( ) { return this->data; }
        private:
            void build_matrix( );
            int **matrix;
            std::pair<int,int> data;
            int N;
            friend std::ostream& operator<< ( std::ostream &out, Matrix::RandomOrderedMatrix &rom )
            {
                std::pair<int,int> d = rom.data;
                return out << "<" << d.first << ", " << d.second << ">" << std::endl;
            }
    };

    /* ctor                                                                 */
    RandomOrderedMatrix::RandomOrderedMatrix( int N )
    {
        this->N = N;
        this->matrix = new int*[N];
        for( int r=0;r<N;r++ ) matrix[r] = new int[N];
        this->build_matrix( );
    } 

    /* dtor                                                                  */
    RandomOrderedMatrix::~RandomOrderedMatrix( )
    {
        if( matrix ) 
        {
            for( int r=0;r<N;r++ ) delete [ ] matrix[r];
            delete [ ] matrix;
        }
    }

    /* This is the n lg(n) algorithm required to find the coord of an elem.  */
    /* Assuming that the rows and columns are all sorted we find the row     */
    /* with the right range matrix[row][0] <= element <= matrix[row][N]      */
    /* Once it finds the right row if it existis it performs binary search   */
    /* which is lg(n) to see if element exists on that row. If the element   */
    /* is found it prints sets the coordinate pair member variable to the    */
    /* row and column where it found it. If it did not find the elment it    */
    /* sets the member variable coordinate pair to N                         */
    void RandomOrderedMatrix::find_element( int element ) 
    {
        int left_index = 0;
        int right_index = N-1;
        /* Scan the rows */
        for( int r = 0; r < N; r++ ) 
        {
            /* Check the range for that row */
            if( element >= matrix[r][0] && element <= matrix[r][N-1] )
            {
               /* Binary search */
               while( right_index>left_index ) {
                    int middle = (right_index+left_index)/2;
                    if( element == matrix[r][middle] )
                    {
                        data.first = r;
                        data.second = middle;
                        return;
                    }
                    else if( element > matrix[r][middle] )
                    {
                        left_index = middle + 1;
                    }
                    else if( element < matrix[r][middle] )
                    {
                        right_index = middle - 1;
                    }
                }
            }
            /* These last two cases are used when there are only two items   */
            /* left in the binary partition                                  */
            if( element == matrix[r][left_index] ) 
            {
                data.first = r;
                data.second = left_index;
                return;
            }
            if( element == matrix[r][right_index] )
            {
                data.first = r;
                data.second = right_index;
                return;
            }
        }
        /* If function above did not find the elements then set them to N to */
        /* notify the client that their pair could not be found              */
        data.first = N;
        data.second = N;
    }

    /* Pretty Formating Print functino =)                                    */
    void RandomOrderedMatrix::print_matrix( ) 
    {
        std::cout << "Your Matrix is" << std::endl;
        std::cout << std::setw( 6 ) << " ";
        std::cout << std::setw( 6 ) << " ";
        for( int c=0;c<N;c++ )
        {
            std::cout << std::setw( 6 ) << c;
        }
        std::cout << std::endl;
        for( int r=0;r<N;r++ )
        {
            std::cout << std::setw( 6 ) << r;
            std::cout << std::setw( 6 ) << "|";
            for( int c=0;c<N;c++ )
            {
                std::cout << std::setw( 6 ) << matrix[r][c];
            }
            std::cout << std::setw( 6 ) << "|";
            std::cout << std::endl;
        }
    }

    /* Build a matrix such that the rows are sorted and the columns are      */
    /* sorted.                                                               */
    void RandomOrderedMatrix::build_matrix( ) 
    {
        matrix[0][0] = rand( )%50;   
        for( int c=1; c<N; c++ ) matrix[0][c] = matrix[0][c-1] + rand( )%50;
        for( int r=1; r<N; r++ )
        {
            for( int c=0; c<N; c++ ) 
            {
                if( c == 0 ) 
                {
                    matrix[r][c] = matrix[r-1][N-1]+rand( )%50;
                }
                else
                {
                    matrix[r][c] = matrix[r][c-1]+rand( )%50;
                } 
            }
        }
    }
}

/* Driver function, normally found in another file, but to facilitate        */
/* reading I have included it here                                           */
/* I also included some unit testing code which automates the testing        */
/* If you want you can uncomment it to make your testing easier              */
int main( int argc, char *argv[ ] ) 
{
    Matrix::RandomOrderedMatrix rom( 10 );
    rom.print_matrix( );
    srand((unsigned)time(NULL));
    int element;
    std::cout << "Please input a number to find in your matrix>>> ";
    while( std::cin >> element ) 
    {
        rom.find_element( element );
        std::pair<int,int> &results = rom.get_coord( );
        if( results.first != 10 && results.second != 10 ) 
        {
            std::cout << "Results success, found " << element << " @ coord " << rom;
        }
        else 
        {
            std::cout << "Results failed could not find " << element << " in matrix " << std::endl;
        }
        std::cout << "Please input a number to find in your matrix>>> ";
    }
    /* Slight Unit Testing
    for( int x = 0; x < 20; x++ ) 
    {  
        std::cout << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%" << std::endl;
        int element = rand( )%10000;
        rom.find_element( element );
        std::pair<int,int> &results = rom.get_coord( );
        if( results.first != 10 && results.second != 10 ) 
        {
            std::cout << "Results success, found " << element << " @ coord " << rom;
        }
        else 
        {
            std::cout << "Results failed could not find " << element << " in matrix " << std::endl;
        }
        std::cout << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%" << std::endl;
    }
    //*/
}
\$\endgroup\$
5
\$\begingroup\$

I would replace:

        int **matrix;

with:

        std::vector<std::vector<int> >  matrix; /* or Boost::Matrix */

Then your constructor/destructor become:

RandomOrderedMatrix::RandomOrderedMatrix( int N )
    : matrix(N, std::vector<int>(N))

    // , N(N)   Don't need this anymore size is part of the vector
{
    build_matrix( );
} 

/* dtor                                                                  */
// Don't need the de-structor

This also solves the problem of not obeying the "rule of three".

Move this:

srand((unsigned)time(NULL));

To the first line of main() (note your build matrix uses rand() which is happening before the call to srand() thus you are not getting random numbers).

\$\endgroup\$
  • \$\begingroup\$ I just finished reading C++ Programming Language (Special Edition) but don't recall seeing anything about the "rule of three" . Wikipedia (en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)) was helpful, and I can recall context where such things were discussed. Where does this exact phrase come from? \$\endgroup\$ – Matthew Hoggan Aug 10 '11 at 8:44
  • \$\begingroup\$ I have a suspicion it's from Herb Sutter GoTW series, but I can't find a link right now. \$\endgroup\$ – Flexo Aug 10 '11 at 12:40
  • \$\begingroup\$ It comes from. If you need to write a special version of any destructor/assignment operator/copy constructor then you will probably need to write all three. Personally I think it is a silly name I prefer the rule of four (though nobody else uses it) because the compiler generates four methods automatically for you and if you have a RAW owned pointer in your class you will need to override all four (though I believe there are more now in C++0x with move). So we may be seeing a re-name soon. \$\endgroup\$ – Martin York Aug 10 '11 at 15:13
  • \$\begingroup\$ The "Rule of Three++0x" ?... \$\endgroup\$ – paercebal Aug 13 '11 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.