C++

profilesilviya23
project4files.zip
Home>Computer Science homework help>C++

ASTree.cpp

ASTree.cpp

/*
 *  ASTree.cpp
 *  Abstract Syntax Tree
 *
 *  Created by Jonathan Maletic on 11/8/11.
 *  Copyright 2013 Kent State University. All rights reserved.
 *
 *  Modified by:
 *
 */

#include   "ASTree.hpp"


/////////////////////////////////////////////////////////////////////
// Copy constructor for srcML
//
srcML :: srcML ( const  srcML &  actual )   {
  tree  =   new   ASTree ( * ( actual . tree ));
}

/////////////////////////////////////////////////////////////////////
// Constant time swap for srcML
//
void  srcML :: swap ( srcML &  b )   {
  std :: string t_header  =  header ;
  header  =  b . header ;
  b . header  =  t_header ;
    
   ASTree   * temp  =  tree ;
  tree  =  b . tree ;
  b . tree  =  temp ;
}

/////////////////////////////////////////////////////////////////////
// Assignment for srcML
//
srcML &  srcML :: operator = ( srcML rhs )   {
  swap ( rhs );
   return   * this ;
}

/////////////////////////////////////////////////////////////////////
// Reads in and constructs a srcML object.
//
std :: istream &   operator >> ( std :: istream &  in ,  srcML &  src ){
   char  ch ;
   if   ( ! in . eof ())  in  >>  ch ;
  src . header  =  readUntil ( in ,   '>' );
   if   ( ! in . eof ())  in  >>  ch ;
   if   ( src . tree )   delete  src . tree ;
  src . tree  =   new   ASTree ( category ,  readUntil ( in ,   '>' ));
  src . tree -> read ( in );
   return  in ;
}


/////////////////////////////////////////////////////////////////////
// Prints out a srcML object
//
std :: ostream &   operator << ( std :: ostream &  out ,   const  srcML &  src ){
   if   ( TAGS )  out  <<   "<"   <<  src . header  <<   ">"   <<  std :: endl ;
  src . tree -> print ( out ,   0 );
   return  out ;
}




/////////////////////////////////////////////////////////////////////
//  Adds in the includes and profile variables
//
void  srcML :: mainHeader ( std :: vector < std :: string >&  profileNames )   {
  tree -> mainHeader ( profileNames );
}

/////////////////////////////////////////////////////////////////////
//  Adds in the includes and profile variables
//
void  srcML :: fileHeader ( std :: vector < std :: string >&  profileNames )   {
  tree -> fileHeader ( profileNames );
}


/////////////////////////////////////////////////////////////////////
// Adds in the report to the main.
//
void  srcML :: mainReport ( std :: vector < std :: string >&  profileNames )   {
  tree -> mainReport ( profileNames );
}

/////////////////////////////////////////////////////////////////////
//  Inserts a function.count() into each function body.
//
void  srcML :: funcCount ()   {
  tree -> funcCount ();
}

/////////////////////////////////////////////////////////////////////
// Inserts a filename.count() for each statement.
//
void  srcML :: lineCount ( const  std :: string &  profilename )   {
  tree -> lineCount ( profilename );
}

    


/////////////////////////////////////////////////////////////////////
// Constructs a category, token, or whitespace node for the tree.
//
ASTree :: ASTree ( nodes t ,   const  std :: string &  s )   {
  nodeType  =  t ;
   switch   ( nodeType )   {
   case  category :
    tag  =  s ;
     break ;
   case  token :
    text  =  unEscape ( s );
     break ;
   case  whitespace :
    text  =  s ;
     break ;
   }
}



///
///  NOTE: Can implement destructor implemented in .h file or here.
///




/////////////////////////////////////////////////////////////////////
// Copy Constructor for ASTree
//
ASTree :: ASTree ( const   ASTree &  actual )   {
   //NEED TO IMPLEMENT
}


/////////////////////////////////////////////////////////////////////
// Constant time swap for ASTree
//
void   ASTree :: swap ( ASTree &  b )   {
   //NEED TO IMPLEMENT
}

/////////////////////////////////////////////////////////////////////
// Assignment for ASTree
//
ASTree &   ASTree :: operator = ( ASTree  rhs )   {
  swap ( rhs );
   return   * this ;
}




/////////////////////////////////////////////////////////////////////
// Returns an this->child[i] where (this->child[i]->tag == tagName)
//
ASTree *   ASTree :: getChild ( std :: string tagName )   {
  std :: list < ASTree *>:: iterator ptr  =  child . begin ();
   while   ((( * ptr ) -> tag  !=  tagName )   &&   ( ptr  !=  child . end ()))   {
     ++ ptr ;
   }
   return   * ptr ;
}



/////////////////////////////////////////////////////////////////////
// Returns the full name of a <name> node.
//
std :: string  ASTree :: getName ()   const   {
  std :: string result ;
   if   ( child . front () -> tag  !=   "name" )   {
    result  =  child . front () -> text ;     //A simple name (e.g., main)
   }   else   {                                //A complex name (e.g., stack::push).
    result  =  child . front () -> child . front () -> text ;
    result  +=   "::" ;
    result  +=  child . back () -> child . front () -> text ;
   }
   return  result ;
}




/////////////////////////////////////////////////////////////////////
//  Adds in the includes and profile variables in a main file.
//
void   ASTree :: mainHeader ( std :: vector < std :: string >&  profileNames )   {

   //NEED TO IMPLEMENT
   //Skip down a couple lines.
   //For each file profile name, add a new node with a profile 
   // declaration.
   //Also, add in the profile declaration for functions and the
   //include for profile.hpp
}


/////////////////////////////////////////////////////////////////////
//  Adds in the includes and profile variables for non-main files
//
void   ASTree :: fileHeader ( std :: vector < std :: string >&  profileNames )   {

   //NEED TO IMPLEMENT
   //Skip down a couple lines.
   //For each file profile name, add a new node with a profile 
   // extern declaration.
   //Also, add in the extern declaration for functions and the
   //include for profile.hpp
    

}


/////////////////////////////////////////////////////////////////////
// Adds in the report to the main.
// Assumes only one return at end of main body.
//
void   ASTree :: mainReport ( std :: vector < std :: string >&  profileNames )   {
    
   //NEED TO IMPLEMENT
    
   //Find the function with name main and then start from the end.
   //Find the main - function with name of "main"
   //Then start from the end() of this function and iterate
   // backwards until you find a return stmt.   You'll want
   // to insert the report statements before this return.
    
    
}


/////////////////////////////////////////////////////////////////////
// Adds in a line to count the number of times each function is executed.
//  Assumes no nested functions.
//
void   ASTree :: funcCount ()   {
    
   //NEED TO IMPLEMENT
    
   // Check for function, constructor, destructor.
   // Find the function name and insert the count.

}

/////////////////////////////////////////////////////////////////////
// Adds in a line to count the number of times each statement is executed.
//   No breaks, returns, throw etc.
//   Assumes all construts (for, while, if) have { }.
//
void   ASTree :: lineCount ( const  std :: string &  profileNames )   {
    
   //NEED TO IMPLEMENT
    
   // Check for expr_stmt and call
    
    
}


/////////////////////////////////////////////////////////////////////
// Read in and construct ASTree
// REQUIRES: '>' was pre            temp = readUntil(in, '>');
if   ( temp [ 0 ]   ==   '/' )   {
  closeTag  =  temp ;
   break ;                                         //Found close tag, stop recursion
  }
subtree  =   new   ASTree ( category ,  temp );              //New subtree
subtree -> read ( in );                                 //Read it in
in . get ( ch );
child . push_back ( subtree );                          //Add it to child
}   else   {                                               //Found a token
    temp  =  std :: string ( 1 ,  ch )   +  readUntil ( in ,   '<' );    //Read it in.
    std :: vector < std :: string >  tokenList  =  tokeniree );
}
ch  =   '<' ;
}
}
return  in ;
}


/////////////////////////////////////////////////////////////////////
// Print an ASTree 
// REQUIRES: indent >= 0
//
std :: ostream &   ASTree :: print ( std :: ostream &  out ,   int  indent )   const   {
   if   ( TAGS )  out  <<  std :: setw ( indent )   <<   " " ;
   if   ( TAGS )  out  <<   "<"   <<  tag  <<   ">"   <<  std :: endl ;  
   for   ( std :: list < ASTree *>:: const_iterator i  =  child . begin ();  i  !=  child . end ();   ++ i )   {
     switch   (( * i ) -> nodeType )   {
       ///////////////////
       // Utilities
       //

       bool  isStopTag ( std :: string tag )   {
     if   ( tag  ==   "decl_stmt" )   return   true ;
     if   ( tag  ==   "argument_list" )   return   true ;
     if   ( tag  ==   "init" )   return   true ;
     if   ( tag  ==   "condition" )   return   true ;
     if   ( tag  ==   "cpp:include" )   return   true ;
     if   ( tag  ==   "comment type\"block\"" )   return   true ;
     if   ( tag  ==   "comment type\"line\"" )   return   true ;
     if   ( tag  ==   "macro" )   return   true ;
        
     return   false ;
       }

       /////////////////////////////////////////////////////////////////////
       // Reads until a key is encountered.  Does not inclutVal == "<"
       //
      std :: string unEscape ( std :: string s )   {
    std :: size_t pos  =   0 ;
     while   (( pos  =  s . find ( "&gt;" ))    !=  s . npos )   {  s . replace ( pos ,   4 ,   ">" );}
     while   (( pos  =  s . find ( "&lt;" ))    !=  s . npos )   {  s . replace ( pos ,   4 ,   "<" );}
     while   (( pos  =  s . find ( "&amp;" ))   !=  s . npos )   {  s . replace ( pos ,   5 ,   "&" );}
     return  s ;
       }


       /////////////////////////////////////////////////////////////////////
       // Given: s == "   a + c  "
       // RetVal == {"   ", "a", " ", "+", "c", " "}  
       //
      std :: vector < std :: string >  tokenize ( const  std :: string &  s )   {
    std :: vector < std :: string >  result ;
    std :: string temp  =   "" ;
     unsigned  i  =   0 ;
     while   ( i  <  s . length ())   {
       while   ( isspace ( s [ i ])   &&   ( i  <  s .        temp  =   "" ;
                    }
          }
       return  result ;
     }
    

ASTree.hpp

/* * ASTree.hpp * Abstract Syntax Tree * * Created by Jonathan Maletic on 11/8/11. * Copyright 2013 Kent State University. All rights reserved. * * Modified by: * */ #ifndef INCLUDES_ASTree_H_ #define INCLUDES_ASTree_H_ #include <list> #include <vector> #include <iostream> #include <iomanip> #include <cassert> #include <algorithm> #include <string> class ASTree; enum nodes {category, token, whitespace}; const bool TAGS = false; bool isStopTag (std::string); std::string readUntil (std::istream&, char); std::string unEscape (std::string); std::vector<std::string> tokenize (const std::string& s); //////////////////////////////////////////////////////////////////////// // An ASTree is either a: // -Syntactic category node // -Token node // -Whitespace node // // CLASS INV: if (nodeType == category) than (child != 0) && (text == "") // if ((nodeType == token) || (nodeType == whitespace)) then (child == 0) && (text != "") // class ASTree { public: ASTree () {}; ASTree (nodes t) : nodeType(t) {}; ASTree (nodes t, const std::string&); ~ASTree () {}; //NEED TO IMPLEMENT ASTree (const ASTree&); void swap (ASTree&); ASTree& operator= (ASTree); ASTree* copyASTree(); ASTree* getChild (std::string); std::string getName () const; void mainHeader(std::vector<std::string>&); void fileHeader(std::vector<std::string>&); void mainReport(std::vector<std::string>&); void funcCount (); void lineCount (const std::string&); std::ostream& print (std::ostream&, int) const; std::istream& read (std::istream&); private: nodes nodeType; //Category, Token, or Whitespace std::string tag, //Category: the tag name and closeTag; // closing tag. std::list<ASTree*> child; //Category: A list of subtrees. std::string text; //Token/Whitespace: the text. }; //////////////////////////////////////////////////////////////////////// // srcML is an internal data structure for a srcML input file. // CLASS INV: Assigned(tree) // class srcML { public: srcML () : tree(0) {}; ~srcML () {delete tree;} srcML (const srcML&); void swap (srcML&); srcML& operator= (srcML); void mainHeader(std::vector<std::string>&); void fileHeader(std::vector<std::string>&); void mainReport(std::vector<std::string>&); void funcCount (); void lineCount (const std::string&); friend std::istream& operator>>(std::istream&, srcML&); friend std::ostream& operator<<(std::ostream&, const srcML&); private: std::string header; ASTree* tree; }; #endif

main.cpp

main.cpp

/*
 *  main.cpp
 *  Profiler
 *
 *  Created by Jonathan Maletic on 11/8/11.
 *  Copyright 2013 Kent State University. All rights reserved.
 *
 *  Requires main.cpp first, followed by other files.
 *
 *  Modified by:
 *
 */

#include   < iostream >
#include   < fstream >
#include   < vector >
#include   < string >
#include   < algorithm >

#include   "ASTree.hpp"
#include   "profile.hpp"


//
// Reads a srcML file into an internal data structure.
// Then prints out the data structure.

int  main ( int  argc ,   char   * argv [])   {
   if   ( argc  <   2 )   {
    std :: cerr  <<   "Error: One or more input files are required."   <<  std :: endl ;
    std :: cerr  <<   "       The main must be the first argument followed by any other .cpp files.  For example:"   <<  std :: endl ;
    std :: cerr  <<   "profiler main.cpp.xml file1.cpp.xml file2.cpp.xml"   <<  std :: endl  <<  std :: endl ;
     return ( 1 );
   }
    
  srcML                     code ;                //The source code to be profiled.
  std :: vector < std :: string >   files ;               //The list of file names (without .xml)
  std :: vector < std :: string >   profileNames ;        //The list of profile names to be used.
    
   for   ( int  i  =   1 ;  i  <  argc ;   ++ i )   {
    std :: string filename  =  argv [ i ];
    files . push_back ( filename );
    filename  =  filename . substr ( 0 ,  filename . find ( ".xml" ));        //Remove .xml
    std :: replace ( filename . begin (),  filename . end (),   '.' ,   '_' );    // Change . to _
    profileNames . push_back ( filename );
   }
    
  std :: ifstream inFile ( files [ 0 ]. c_str ());      //Read in the main.
  inFile  >>  code ;
  inFile . close ();
    
  code . mainHeader ( profileNames );               //Add in main header info
  code . mainReport ( profileNames );               //Add in the report
  code . funcCount ();                            //Count funciton invocations
  code . lineCount ( profileNames [ 0 ]);             //Count line invocations
    
  std :: string outFileName  =   "p-"   +  files [ 0 ];
  outFileName  =  outFileName . substr ( 0 ,  outFileName . find ( ".xml" ));    //Remove .xml
  std :: ofstream outFile ( outFileName . c_str ());
  outFile  <<  code  <<  std :: endl ;
  outFile . close ();

   for   ( unsigned  i  =   1 ;  i  <  files . size ();   ++ i )   {    //Read in the rest of the files.
    inFile . open ( files [ i ]. c_str ());
    inFile  >>  code ;
    inFile . close ();
        
    code . fileHeader ( profileNames );               //Add in file header info
    code . funcCount ();                            //Count funciton invocations
    code . lineCount ( profileNames [ i ]);             //Count line invocations
        
    outFileName  =   "p-"   +  files [ i ];
    outFileName  =  outFileName . substr ( 0 ,  outFileName . find ( ".xml" ));    //Remove .xml
    outFile . open ( outFileName . c_str ());
    outFile  <<  code  <<  std :: endl ;
    outFile . close ();
   }
    
   return   0 ;
}


Makefile

#============================================================================ # Make file for Profiler # # CS II Kent State University # # J. Maletic 2015 ############################################################### # Variables CPP = clang++ CPP_OPTS = -g -Wall -W -Wunused -Wuninitialized -Wshadow -std=c++11 ############################################################### # The first rule is run if only make is typed msg: @echo 'Targets are:' @echo ' profiler:' @echo ' sort:' @echo ' p-sort:' @echo ' clean:' ############################################################### profiler : main.o ASTree.o $(CPP) $(CPP_OPTS) -o profiler main.o ASTree.o main.o : main.cpp ASTree.hpp $(CPP) $(CPP_OPTS) -c main.cpp ASTree.o : ASTree.hpp ASTree.cpp $(CPP) $(CPP_OPTS) -c ASTree.cpp #============================================================== # sort sort : sort.o sort_lib.o $(CPP) $(CPP_OPTS) -o sort sort.o sort_lib.o sort.o: sort_lib.h sort.cpp $(CPP) $(CPP_OPTS) -c sort.cpp sort_lib.o: sort_lib.h sort_lib.cpp $(CPP) $(CPP_OPTS) -c sort_lib.cpp #============================================================== # p-sort # p-sort.cpp # p-sort_lib.cpp p-sort : profile.o p-sort.o p-sort_lib.o $(CPP) $(CPP_OPTS) -o p-sort profile.o p-sort.o p-sort_lib.o p-sort.o: profile.hpp sort_lib.h p-sort.cpp $(CPP) $(CPP_OPTS) -c p-sort.cpp p-sort_lib.o: profile.hpp sort_lib.h p-sort_lib.cpp $(CPP) $(CPP_OPTS) -c p-sort_lib.cpp profile.o: profile.hpp profile.cpp $(CPP) $(CPP_OPTS) -c profile.cpp ############################################################### #This will clean up everything via "make clean" clean: rm -f profiler rm -f sort rm -f *.o rm -f p-*

profile.cpp

profile.cpp

/*
 *  profile.cpp
 *
 *  Created by Jonathan Maletic on 3/29/2012.
 *  Copyright 2012 Kent State University. All rights reserved.
 *
 *  Modified by:
 *
 */

#include   "profile.hpp"

////////////////////////////////////////////////////////////////////////
// Prints out the profile.
//
// TODO: Very simple output, need to make it into columns with nice headings.
// 
std :: ostream &   operator <<   ( std :: ostream &  out ,   const  profile &  p )   {
    
   for ( std :: map < std :: string ,   int >:: const_iterator i  =  p . item . begin ();  i  !=  p . item . end ();   ++ i )   {
    out  <<  i -> first  <<   " "   <<  i -> second  <<  std :: endl ;         
   }
    
   return  out ;
}



////////////////////////////////////////////////////////// 
// PRE:  n >= 0
// POST: Returns a text version of a positive integer long
std :: string intToString ( int  n )   {
  assert ( n  >=   0 );
  std :: string result ;
    
   if   ( n  ==   0 )   return   "0" ;
   while   ( n  >   0 )   {
    result  =   char ( int ( '0' )   +   ( n  %   10 ))   +  result ;
    n  =  n  /   10 ;
   }   
   return  result ;
}

profile.hpp

/* * profile.hpp * * Created by Jonathan Maletic on 3/29/2012. * Copyright 2012 Kent State University. All rights reserved. * * Modified by: * */ #ifndef INCLUDES_PROFILE_H_ #define INCLUDES_PROFILE_H_ #include <iostream> #include <cassert> #include <string> #include <map> #include <algorithm> std::string intToString(int); //////////////////////////////////////////////////////////////////////// // A map of line numbers or line number function names and the number // of times each was called. // // class profile { public: profile () {}; void count (const int line, const std::string& fname) { item[intToString(line) + " " + fname] += 1; } void count (const int line) { item[intToString(line)] += 1; } friend std::ostream& operator<< (std::ostream&, const profile&); private: std::map<std::string, int> item; //Map of items and their counts }; #endif

simple.cpp

simple.cpp

////////////////////////////////////////////////////////////////////
// File:         simple.cpp
// Creation:     4/2013
// Programmer:   Dr. J. Maletic
//
// Description:  Simple program for testing profiler
//
//
#include   < iostream >

int  search ( int  tbl [],   int  n ,   int  key )   {
   int  result  =   - 1 ;
   for   ( int  i  =   0 ;  i  <  n ;   ++ i )   {
     if   ( key  ==  tbl [ i ])   {
      result  =  i ;
     }
   }
   return  result ;
}



int  main ()   {

   int  lst [ 5 ]   =   { 2 ,   4 ,   6 ,   8 ,   10 };
  std :: cout  <<  search ( lst ,   5 ,   6 );
  std :: cout  <<  std :: endl ;
    
  std :: cout  <<   "Done" ;
  std :: cout  <<  std :: endl ;
   return   0 ;
}

simple.cpp.xml

//////////////////////////////////////////////////////////////////// // File: simple.cpp // Creation: 4/2013 // Programmer: Dr. J. Maletic // // Description: Simple program for testing profiler // // # include <iostream> int search ( int tbl [], int n, int key) { int result = -1; for ( int i = 0; i < n; ++ i) { if ( key == tbl [ i]) { result = i; } } return result; } int main () { int lst [ 5] = { 2, 4, 6, 8, 10}; std:: cout << search ( lst, 5, 6); std:: cout << std:: endl; std:: cout << "Done"; std:: cout << std:: endl; return 0; }

sort.cpp

sort.cpp

/**
 *  @brief   Application to run sorting algorithms on random int data
 *
 *  @author  Dale Haverstock
 *  @date    2012-04-19
 */

//==============================================================================
#include   "sort_lib.h"
#include   < iostream >
#include   < iomanip >
#include   < vector >
#include   < cstdlib >

//==============================================================================
// Using declarations
using  std :: string ;
using  std :: vector ;
using  std :: cout ;
using  std :: cerr ;

//==============================================================================
// Function declarations
void  process_command_line ( Options &  opts ,   int  argc ,   char *  argv []);
void  generate_random_data ( vector < int >&  data ,   int  size ,   int  seed ,   int  mod );
void  output_data ( const  vector < int >& );
void  output_usage_and_exit ( const  string &  cmd );
void  output_error_and_exit ( const  string &  msg );

//==============================================================================
int  main ( int  argc ,   char *  argv [])
{
   // Options container
   Options  opts ;

   // Get values from the command line, opts may be changed
  process_command_line ( opts ,  argc ,  argv );

   // Generate data
  vector < int >  data ;
  generate_random_data ( data ,  opts . _data_size ,  opts . _seed ,  opts . _mod );

   // Output data before sorting
   if ( opts . _output_data )
     {  cout  <<   "\nData Before: " ;  output_data ( data );   }  

   // Sort, if a sort was specified, there is no default
   if   ( opts . _quick_sort )       {  quick_sort ( data );        }
   if   ( opts . _selection_sort )   {  selection_sort ( data );    }
   if   ( opts . _bubble_sort )      {  bubble_sort ( data );       }
   if   (   ! opts . _quick_sort       &&
          ! opts . _selection_sort   &&
        ! opts . _bubble_sort   )
     {  output_error_and_exit ( "No sort specified." );   }

   // Output data after sorting
   if ( opts . _output_sorted_data )
     {  cout  <<   "\nData After: " ;  output_data ( data );   }  

   return   0 ;
}

//==============================================================================
void  generate_random_data ( vector < int >&  vec ,   int  size ,   int  seed ,   int  mod )
{
   // Resize vector
  vec . resize ( size );

   // Set random number generator seed
  srandom ( static_cast < unsigned   int > ( seed ));

   // Put random values in vector
   for   ( vector < int >:: size_type idx  =   0 ;  idx  <  vec . size ();   ++ idx )
     {
       if ( mod )   {  vec [ idx ]   =  random ()   %  mod ;   }
       else      {  vec [ idx ]   =  random ();         }
     }
}

//==============================================================================
void  output_data ( const  vector < int >&  vec )
{
   // Number of columns, column width
   const   int  cols   =    7 ;
   const   int  width  =   10 ;

   // Output vector elements
   for   ( vector < int >:: size_type idx  =   0 ;  idx  <  vec . size ();   ++ idx )
     {
       // Output newline to end row
       if   (   !   ( idx  %  cols )   )
     {  cout   <<   "\n" ;   }

      cout  <<  std :: setw ( width )   <<  vec [ idx ]   <<   " " ;
     }

  cout  <<   '\n' ;
}

//==============================================================================
// Note:
//   * No check for C-string to int conversion success
//
void  process_command_line ( Options &  opts ,   int  argc ,   char *  argv [])
{
   // Useage message if no command line args
   if   ( argc  ==   1 )
     {  output_usage_and_exit ( argv [ 0 ]);   }

   // Go through the argumets
   for   ( int  idx  =   1 ;  idx  <  argc ;   ++ idx )
     {
       // Standard library string from C-string
      string opt ( argv [ idx ]);

       // Process the option
       if   ( opt  ==   "-h" )     {  output_usage_and_exit ( argv [ 0 ]);   }
       if   ( opt  ==   "-qs" )    {  opts . _quick_sort          =   true ;    }
       if   ( opt  ==   "-ss" )    {  opts . _selection_sort      =   true ;    }
       if   ( opt  ==   "-bs" )    {  opts . _bubble_sort         =   true ;    }
       if   ( opt  ==   "-od" )    {  opts . _output_data         =   true ;    }
       if   ( opt  ==   "-osd" )   {  opts . _output_sorted_data  =   true ;    }
       if   ( opt  ==   "-sz" )
         {
       if   ( idx  +   1   <  argc )   {   ++ idx ;  opts . _data_size  =  atoi ( argv [ idx ]);   }
       else                  {  output_error_and_exit ( "Value for -sz option is missing." );   }
         }
       if   ( opt  ==   "-rs" )
         {
       if   ( idx  +   1   <  argc )   {   ++ idx ;  opts . _seed  =  atoi ( argv [ idx ]);   }
       else                  {  output_error_and_exit ( "Value for -rs option is missing." );   }
         }
       if   ( opt  ==   "-mod" )
         {
       if   ( idx  +   1   <  argc )   {   ++ idx ;  opts . _mod  =  atoi ( argv [ idx ]);   }
       else                  {  output_error_and_exit ( "Value for -mod option is missing." );   }
         }
       if   (   ( opt  !=   "-h" )     &&
        ( opt  !=   "-qs" )    &&
        ( opt  !=   "-ss" )    &&
        ( opt  !=   "-bs" )    &&
        ( opt  !=   "-od" )    &&
        ( opt  !=   "-osd" )   &&
        ( opt  !=   "-sz" )    &&
        ( opt  !=   "-rs" )    &&
        ( opt  !=   "-mod" )   )
         {
      output_error_and_exit ( string ( "Error: Bad option: " )   +  opt );
         }
     }
}

//==============================================================================
void  output_usage_and_exit ( const  string &  cmd )
{
  cout  <<  
     "Usage: "   <<  cmd  <<   " [options]\n"
        "  Options:\n"
        "     -sz  int  The number of data items\n"
        "     -rs  int  The random number generator seed\n"
        "     -mod int  The mod value for random numbers\n"
        "     -od       Output data to be sorted\n"
        "     -osd      Output sorted data\n"
        "     -qs       Use quick sort\n"
        "     -ss       Use selection sort\n"
        "     -bs       Use bubble sort\n"
        "     -h        This message\n"
        "\n"
        "  A sort must be specified, there is no default sort.\n"
        "  If more than 1 sort is specified then the first sort\n"
        "  specified from the following order will be done.\n"
        "     1. quick\n"
        "     2. selection\n"
     "     3. bubble\n" ;

  exit ( 0 );
}

//==============================================================================
void  output_error_and_exit ( const  string &  msg )
{
  cerr  <<   "Error: "   <<  msg  <<   "\n" ;

  exit ( 1 );
}

sort.cpp.xml

/** * @brief Application to run sorting algorithms on random int data * * @author Dale Haverstock * @date 2012-04-19 */ //============================================================================== # include "sort_lib.h" # include <iostream> # include <iomanip> # include <vector> # include <cstdlib> //============================================================================== // Using declarations using std:: string; using std:: vector; using std:: cout; using std:: cerr; //============================================================================== // Function declarations void process_command_line ( Options& opts, int argc, char* argv []); void generate_random_data ( vector < int>& data, int size, int seed, int mod); void output_data ( const vector < int>&); void output_usage_and_exit ( const string& cmd); void output_error_and_exit ( const string& msg); //============================================================================== int main ( int argc, char* argv []) { // Options container Options opts; // Get values from the command line, opts may be changed process_command_line ( opts, argc, argv); // Generate data vector < int> data; generate_random_data ( data, opts. _data_size, opts. _seed, opts. _mod); // Output data before sorting if ( opts. _output_data) { cout << "\nData Before: "; output_data ( data); } // Sort, if a sort was specified, there is no default if ( opts. _quick_sort) { quick_sort ( data); } if ( opts. _selection_sort) { selection_sort ( data); } if ( opts. _bubble_sort) { bubble_sort ( data); } if ( ! opts. _quick_sort && ! opts. _selection_sort && ! opts. _bubble_sort ) { output_error_and_exit ( "No sort specified."); } // Output data after sorting if ( opts. _output_sorted_data) { cout << "\nData After: "; output_data ( data); } return 0; } //============================================================================== void generate_random_data ( vector < int>& vec, int size, int seed, int mod) { // Resize vector vec. resize ( size); // Set random number generator seed srandom ( static_cast<unsigned int>(seed)) ; // Put random values in vector for ( vector < int>:: size_type idx = 0; idx < vec. size (); ++ idx) { if ( mod) { vec [ idx] = random () % mod; } else { vec [ idx] = random (); } } } //============================================================================== void output_data ( const vector < int>& vec) { // Number of columns, column width const int cols = 7; const int width = 10; // Output vector elements for ( vector < int>:: size_type idx = 0; idx < vec. size (); ++ idx) { // Output newline to end row if ( ! ( idx % cols) ) { cout << "\n"; } cout << std:: setw ( width) << vec [ idx] << " "; } cout << '\n'; } //============================================================================== // Note: // * No check for C-string to int conversion success // void process_command_line ( Options& opts, int argc

sort_lib.cpp

sort_lib.cpp

/**
 *  @brief   Application to run sorting algorithms on random int data
 *
 *  @author  Dale Haverstock
 *  @date    2012-04-19
 */

// sort library
//

//==============================================================================
#include   "sort_lib.h"
#include   < vector >

//==============================================================================
// Make shorter type names
typedef  std :: vector < int >:: size_type  Vec_Idx ;

//==============================================================================
// Function declarations, uppercase so those stand out
void  quick_sort ( std :: vector < int >&  data ,   int  left ,   int  right );
void  SWAP ( int &  n1 ,   int &  n2 );
bool  LESS_THAN ( int  n1 ,   int  n2 );
bool  GREATER_THAN ( int  n1 ,   int  n2 );

//==============================================================================
void  quick_sort ( std :: vector < int >&  data )
{
   // Do nothing if empty vector
   if   ( data . size ()   ==   0 )
     {   return ;   }

   // Do the sort
  quick_sort ( data ,   0 ,  data . size ()   -   1 );
}

//==============================================================================
// The unsigned ints cause problems here, jdx may go to -1.
// Subscripts are cast so there are no warnings.
void  quick_sort ( std :: vector < int >&  data ,   int  left ,   int  right )
{
   // Calculate the pivot
   int  pivot  =  data [ Vec_Idx (( left  +  right )   /   2 )];

   // Partition
   int  idx  =  left ,  jdx  =  right ;
   while   ( idx  <=  jdx )   {
     while   ( LESS_THAN ( data [ Vec_Idx ( idx )],  pivot ))
      idx ++ ;

     while   ( GREATER_THAN ( data [ Vec_Idx ( jdx )],  pivot ))
      jdx -- ;

     if   ( idx  <=  jdx )
       {
    SWAP ( data [ Vec_Idx ( idx )],  data [ Vec_Idx ( jdx )]);
    idx ++ ;
    jdx -- ;
       }
   }

   // Recurse
   if   ( left  <  jdx )
     {  quick_sort ( data ,  left ,  jdx );   }

   if   ( idx  <  right )
     {  quick_sort ( data ,  idx ,  right );   }
}

//==============================================================================
void  selection_sort ( std :: vector < int >&  data )
{
   // Do nothing if empty vector (note unsigned 0 - 1 is a big number)
   if   ( data . size ()   ==   0 )
     {   return ;   }

   // Index of last element in vector, also last in unsorted part
   Vec_Idx  last  =  data . size ()   -   1 ;

   // Do the sort
   while   ( last  >   0 )
     {
       // Find greatest in unsorted part
       Vec_Idx  idx_of_greatest  =   0 ;
       for   ( Vec_Idx  idx  =   0 ;  idx  <=  last ;   ++ idx )
         {
       if   (  LESS_THAN ( data [ idx_of_greatest ],  data [ idx ])   )
             {
           // Remember as new greatest so far
          idx_of_greatest  =  idx ;
             }
         }

       // Swap last in unsorted with greatest in unsorted part
      SWAP ( data [ last ],  data [ idx_of_greatest ]);

       // Increase sorted part
       -- last ;
     }
}

//==============================================================================
void  bubble_sort ( std :: vector < int >&  data )
{
   // Go through vector repeatedly
   for ( Vec_Idx  limit  =  data . size ();  limit  >   0 ;  limit -- )
     {
       // Go through vector once, swap element and next element if out of order
       for ( Vec_Idx  idx  =   0 ;  idx  <  limit  -   1 ;  idx ++ )
         {
       if (  LESS_THAN ( data [ idx  +   1 ],  data [ idx ])   )
             {
          SWAP ( data [ idx ], data [ idx  +   1 ]);
             }
         }
     }
}

//==============================================================================
// This is here so the number of calls can be counted.
void  SWAP ( int &  n1 ,   int &  n2 )
{
  std :: swap ( n1 ,  n2 );
}

//==============================================================================
// This is here so the number of calls can be counted.
bool  LESS_THAN ( int  n1 ,   int  n2 )
{
   return  n1  <  n2 ;
}

//==============================================================================
// This is here so the number of calls can be counted.
bool  GREATER_THAN ( int  n1 ,   int  n2 )
{
   return  n1  >  n2 ;
}

sort_lib.cpp.xml

/** * @brief Application to run sorting algorithms on random int data * * @author Dale Haverstock * @date 2012-04-19 */ // sort library // //============================================================================== # include "sort_lib.h" # include <vector> //============================================================================== // Make shorter type names typedef std:: vector < int>:: size_type Vec_Idx; //============================================================================== // Function declarations, uppercase so those stand out void quick_sort ( std:: vector < int>& data, int left, int right); void SWAP ( int& n1, int& n2); bool LESS_THAN ( int n1, int n2); bool GREATER_THAN ( int n1, int n2); //============================================================================== void quick_sort ( std:: vector < int>& data) { // Do nothing if empty vector if ( data. size () == 0) { return; } // Do the sort quick_sort ( data, 0, data. size () - 1); } //============================================================================== // The unsigned ints cause problems here, jdx may go to -1. // Subscripts are cast so there are no warnings. void quick_sort ( std:: vector < int>& data, int left, int right) { // Calculate the pivot int pivot = data [ Vec_Idx ( ( left + right) / 2)]; // Partition int idx = left, jdx = right; while ( idx <= jdx) { while ( LESS_THAN ( data [ Vec_Idx ( idx)], pivot)) idx++; while ( GREATER_THAN ( data [ Vec_Idx ( jdx)], pivot)) jdx--; if ( idx <= jdx) { SWAP ( data [ Vec_Idx ( idx)], data [ Vec_Idx ( jdx)]); idx++; jdx--; } } // Recurse if ( left < jdx) { quick_sort ( data, left, jdx); } if ( idx < right) { quick_sort ( data, idx, right); } } //============================================================================== void selection_sort ( std:: vector < int>& data) { // Do nothing if empty vector (note unsigned 0 - 1 is a big number) if ( data. size () == 0) { return; } // Index of last element in vector, also last in unsorted part Vec_Idx last = data. size () - 1; // Do the sort while ( last > 0) { // Find greatest in unsorted part Vec_Idx idx_of_greatest = 0; for ( Vec_Idx idx = 0; idx <= last; ++ idx) { if ( LESS_THAN ( data [ idx_of_greatest], data [ idx]) ) { // Remember as new greatest so far idx_of_greatest = idx; } } // Swap last in unsorted with greatest in unsorted part SWAP ( data [ last], data [ idx_of_greatest]); // Increase sorted part -- last; } } //============================================================================== void bubble_sort ( std:: vector < int>& data) { // Go through vector repeatedly for( Vec_Idx limit = data. size (); limit > 0; limit--) data [ idx + 1]

sort_lib.h

/** * @brief Application to run sorting algorithms on random int data * * @author Dale Haverstock * @date 2012-04-19 */ #ifndef SORT_LIB_H #define SORT_LIB_H //============================================================================== #include <vector> //============================================================================== struct Options { // Option values int _seed; int _data_size; int _mod; bool _output_data; bool _output_sorted_data; bool _bubble_sort; bool _selection_sort; bool _quick_sort; // Defaults Options() : _seed(0), _data_size(0), _mod(0), _output_data(false), _output_sorted_data(false), _bubble_sort(false), _selection_sort(false), _quick_sort(false) { } }; //============================================================================== void selection_sort(std::vector<int>&); void quick_sort(std::vector<int>&); void bubble_sort(std::vector<int>&); #endif