To still receiving newsletters from us please subscribe to our Newsletters:
http://tech.groups.yahoo.com/group/developers-Heaven/
// dijkstra_shortest_path_via_min_heap.cpp // // 2018-11-21 //
// This example uses a MIN HEAP as a MIN PRIORITY QUEUE //
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <limits> // for numeric_limits
#include <algorithm> // re. make_heap(...), pop_heap(...), // renove(...) //
using std::vector;
using std::list;
// utility forward declaration /////////////////////////////////////
template< typename T >
T takeIn( const std::string& msg, const T& min, const T& max );
////////////////////////////////////////////////////////////////////
const double INF = std::numeric_limits< double >::infinity();
struct Edge
{
size_t target;
double distance;
Edge( size_t t, double d ) : target(t), distance(d) {}
};
typedef vector< vector< Edge > > adj_vec_t;
typedef std::pair< size_t, double > pair_t;
typedef vector< std::string > place_vec_t;
struct MyMinCmp
{
bool operator () ( const pair_t& a, const pair_t& b )
{
return b.second < a.second ;
}
} ;
void dijkstraPaths( int source,
const adj_vec_t& adj_vec,
vector< double >& min_distance,
vector< int >& previous )
{
size_t n = adj_vec.size();
min_distance.clear();
min_distance.resize( n, INF );
min_distance[source] = 0;
previous.clear();
previous.resize( n, -1 );
vector< pair_t > vertex_queue;
vertex_queue.push_back( pair_t( source, min_distance[source] ) );
while( !vertex_queue.empty() )
{
size_t u = vertex_queue.front().first;
double dist_first = vertex_queue.front().second;
pop_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );
vertex_queue.pop_back();
// Visit each edge adjacent to u //
const vector< Edge > &edges = adj_vec[u];
vector< Edge >::const_iterator it = edges.begin();
for ( ; it != edges.end(); ++ it )
{
double through_u = dist_first + it->distance;
size_t v = it->target;
if( through_u < min_distance[v] )
{
pair_t pr = pair_t( v, min_distance[v] );
// THIS BLOCK OF code may be faster RUNNING than 'remove' below ?? //
vector< pair_t >::iterator itt = std::find(
vertex_queue.begin(), vertex_queue.end(), pr );
if (itt != vertex_queue.end() )
{
// swap the one to be removed with the last element
// and remove the item at the end of the container
// to prevent moving all items after '5' by one
std::swap( *itt, vertex_queue.back() );
vertex_queue.pop_back();
}
//std::remove( vertex_queue.begin(), vertex_queue.end(), pr );
////////////////////////////////////////////////////
min_distance[v] = through_u;
previous[v] = u;
vertex_queue.push_back( pair_t( v, min_distance[v] ) );
make_heap( vertex_queue.begin(), vertex_queue.end(), MyMinCmp() );
}
}
}
}
list<int> getShortestPath( int vertex, const vector< int >& previous )
{
list< int > path;
for ( ; vertex != -1; vertex = previous[vertex])
path.push_front(vertex);
return path;
}
void loadAdjList( adj_vec_t& adjacency_list )
{
// NOTE! insert edges both ways for undirected graphs //
adjacency_list[0].push_back(Edge(1, 7));
adjacency_list[1].push_back(Edge(0, 7));
adjacency_list[0].push_back(Edge(2, 9));
adjacency_list[2].push_back(Edge(0, 9));
adjacency_list[0].push_back(Edge(5, 12));
adjacency_list[5].push_back(Edge(0, 12));
adjacency_list[1].push_back(Edge(2, 10));
adjacency_list[2].push_back(Edge(1, 10));
adjacency_list[1].push_back(Edge(3, 13));
adjacency_list[3].push_back(Edge(1, 13));
adjacency_list[2].push_back(Edge(3, 11));
adjacency_list[3].push_back(Edge(2, 11));
adjacency_list[2].push_back(Edge(5, 2));
adjacency_list[5].push_back(Edge(2, 2));
adjacency_list[3].push_back(Edge(4, 6));
adjacency_list[4].push_back(Edge(3, 6));
adjacency_list[4].push_back(Edge(5, 9));
adjacency_list[5].push_back(Edge(4, 9));
}
void showPlaces( const place_vec_t& places )
{
for( size_t i = 0; i < places.size(); ++ i )
std::cout << i << "->" << places[i] << '\n';
}
int main()
{
place_vec_t places;
for( size_t i = 0; i < 6; ++ i )
{
std::ostringstream oss;
oss << i;
places.push_back( "Town_" + oss.str() );
}
adj_vec_t adjacency_list(6);
loadAdjList( adjacency_list );
size_t n = adjacency_list.size();
std::stringstream ss;
ss << n-1;
std::string topStr = ss.str();
// these get initialed inside function dijkstraPaths called below
vector< double > min_distance;
vector< int > previous;
////////////////////////////////////////////////////////////////
while( true )
{
showPlaces( places );
size_t start = takeIn< int>( "Enter place to start (0.." +
topStr + "): ", 0, n-1 );
size_t stop = takeIn< int>( "Enter place to stop (0.." +
topStr + "): ", 0, n-1 );
dijkstraPaths( start, adjacency_list, min_distance, previous );
std::cout << "Distance from " << start << " to " << stop << ": "
<< min_distance[stop] << std::endl;
list< int > path = getShortestPath( stop, previous );
std::cout << "Path : ";
list< int >::const_iterator it = path.begin();
for( ; it != path.end(); ++ it )
std::cout << *it << "->" << places[*it] << " ";
std::cout << std::endl;
std::cout << "More (y/n) ? ";
std::string reply;
getline( std::cin, reply );
if( reply.size() && (reply[0] == 'n' || reply[0] == 'N') )
break;
}
std::cout << "Ok ... exiting ... \nPress 'Enter' to continue/exit ... ";
std::cin.get();
return 0;
}
////////////////////////////////////////////////////////////////////
// definition utility //////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
template< typename T >
T takeIn( const std::string& msg, const T& min, const T& max )
{
while( true )
{
std::cout << msg;
std::string s, tmp;
getline( std::cin, s );
std::istringstream iss( s );
T val;
if( iss >> val && !(iss >> tmp) && val >= min && val <= max )
return val;
// else if reach here ... nOT in valid range //
std::cout << "Only single values in range "
<< min << ".." << max << " are valid here.\n";
}
}
// several 'definitions' follow ... //
template< typename T >
void print( const T ary[], size_t size )
{
for( size_t i = 0; i < size; ++i ) cout << setw(8) << ary[i];
if( size ) std::cout << std::endl;
}
template< typename T >
void print( const vector < T >& v )
{
for( size_t i = 0; i < v.size(); ++i ) cout << setw(8) << v[i];
if( v.size() ) cout << endl;
}
template< typename T >
bool isSorted( const T* ary, size_t size, bool a )
{
if( a ) // ascending
{
for( int i = size-1; i > 0; --i )
{
if( ary[i-1] > ary[i] )
{
#if myDebug
cout << ary[i-1] << ", " << ary[i] << endl;
pause();
#endif
return false;
}
}
}
else // descending //
{
for( int i = size-1; i > 0; --i )
{
if( ary[i-1] < ary[i] )
{
#if myDebug
cout << ary[i-1] << ", " << ary[i] << endl;
pause();
#endif
return false;
}
}
}
// else ...
return true;
}
template< typename T >
bool isSorted( const vector< T >& ary, bool a )
{
if( a )
{
for( int i = ary.size()-1 ; i > 0 ; --i )
{
if( ary[i-1] > ary[i] )
{
#if myDebug
cout << ary[i-1] << ", " << ary[i] << endl;
pause();
#endif
return false;
}
}
}
else
{
for( int i = ary.size()-1 ; i > 0 ; --i )
{
if( ary[i-1] < ary[i] )
{
#if myDebug
cout << ary[i-1] << ", " << ary[i] << endl;
pause();
#endif
return false;
}
}
}
// else ...
return true;
}
bool isSortedCstrs( char** ary, size_t size, bool a )
{
if( a ) // ascending
{
for( int i = size-1; i > 0; --i )
{
if( strcmp( ary[i-1], ary[i] ) > 0 )
{
#if myDebug
cout << "'" << ary[i-1] << "', '" << ary[i] << "'\n";
pause();
#endif
return false;
}
}
}
else // descending //
{
for( int i = size-1; i > 0; --i )
{
if( strcmp( ary[i-1], ary[i] ) < 0 )
{
#if myDebug
cout << "'" << ary[i-1] << "', '" << ary[i] << "'\n";
pause();
#endif
return false;
}
}
}
// else ...
return true;
}
bool fillFromFile( const char* fname, Words& wds, std::map< string, int >& myPairs )
{
ifstream fin( fname );
if( fin.is_open() )
{
string line, word;
while( getline( fin, line ) )
{
istringstream iss(line);
while( iss >> word )
{
if( word[0] == '[' ) continue;
toAllCaps( word );
unsigned i = 0, len = word.size();
while( i < len && ('A' <= word[i] && word[i] <= 'Z') )
++i ;
if( i < len )
word.erase(i);
if( !word.size() ) continue;
if( myPairs.count( word ) ) ++ myPairs[word] ;
else myPairs[word] = 1;
wds.push_back( word );
}
}
fin.close();
return true;
}
// else
std::cout << "\nThere was a problem opening file "
<< fname << "\n\n";
return false;
}
void toAllCaps( string& str )
{
unsigned i = 0, len = str.size();
while( i < len ) {
str[i] = toupper(str[i]);
++ i;
}
}
void pause( const string& msg )
{
cout << msg << flush;
string dummyLine;
getline( cin, dummyLine );
}
// typical output to first part ... //
/*
There were 300160 words read from file: 'Psalms119times128.txt'
495 of which were unique ...
Re. the vector 'myWords' and the array 'ary' ...
Time to msort vector was 0.499 seconds.
Time to msort vector (passing in functor) was 0.499 seconds.
Time to msort vector (down, passing in functor) was 0.374 seconds.
Time to msort array was 0.515 seconds.
Time to msort array (passing in functor) was 0.523 seconds.
Time to msort array (down, passing in functor) was 0.43 seconds.
Time to qSort2 vector was 0.327 seconds.
Time to qSort2 vector (passing in functor) was 0.358 seconds.
Time to qSort2 vector (down, passing in functor) was 0.297 seconds.
Time to qSort2 array was 0.296 seconds.
Time to qSort2 array (passing in functor) was 0.327 seconds.
Time to qSort2 array (down, passing in functor) was 0.281 seconds.
Time to qSort vector was 0.265 seconds.
Time to qSort vector (passing in functor) was 0.265 seconds.
Time to qSort vector (down, passing in functor) was 0.218 seconds.
Time to qsort array of string was 0.124 seconds.
Time to qsort array of string (down) was 0.094 seconds.
Time to qsort ragged array was 0.093 seconds.
Time to qsort ragged array (down) was 0.031 seconds.
Time to C++ library sort vector was 0.156 seconds.
Time to C++ library sort vector (passing in compare function) was 0.171 seconds.
Time to C++ library sort vector (down, passing in compare function) was 0.125 se
conds.
Time to shellsort vector was 0.608 seconds.
Time to shellsort vector (passing in functor) was 0.558 seconds.
Time to shellsort vector (down, passing in functor) was 0.421 seconds.
Press 'Enter' to continue and see the (word, count) pairs ...
The word: 'A' occured 1536 times =? 1536 times.
The word: 'ABHOR' occured 128 times =? 128 times.
The word: 'ABIDETH' occured 128 times =? 128 times.
The word: 'ABOVE' occured 256 times =? 256 times.
The word: 'ACCEPT' occured 128 times =? 128 times.
The word: 'ACCORDING' occured 2304 times =? 2304 times.
The word: 'AFFLICTED' occured 512 times =? 512 times.
The word: 'AFFLICTION' occured 384 times =? 384 times.
The word: 'AFRAID' occured 128 times =? 128 times.
The word: 'AFTER' occured 512 times =? 512 times.
The word: 'AGAINST' occured 384 times =? 384 times.
The word: 'AIN' occured 128 times =? 128 times.
The word: 'ALEPH' occured 128 times =? 128 times.
The word: 'ALL' occured 2304 times =? 2304 times.
The word: 'ALMOST' occured 128 times =? 128 times.
The word: 'ALSO' occured 768 times =? 768 times.
The word: 'ALWAY' occured 128 times =? 128 times.
The word: 'AM' occured 384 times =? 384 times.
The word: 'AN' occured 384 times =? 384 times.
The word: 'ANCIENTS' occured 128 times =? 128 times.
Press 'Enter' to continue ...
The word: 'AND' occured 8064 times =? 8064 times.
The word: 'ANGUISH' occured 128 times =? 128 times.
The word: 'ANSWER' occured 128 times =? 128 times.
The word: 'ANY' occured 128 times =? 128 times.
The word: 'ARE' occured 384 times =? 384 times.
The word: 'ART' occured 128 times =? 128 times.
The word: 'AS' occured 896 times =? 896 times.
The word: 'ASHAMED' occured 640 times =? 640 times.
The word: 'ASTRAY' occured 256 times =? 256 times.
The word: 'AT' occured 512 times =? 512 times.
The word: 'AWAY' occured 384 times =? 384 times.
The word: 'AWE' occured 128 times =? 128 times.
The word: 'BANDS' occured 128 times =? 128 times.
The word: 'BE' occured 1664 times =? 1664 times.
The word: 'BECAUSE' occured 1152 times =? 1152 times.
The word: 'BECOME' occured 128 times =? 128 times.
The word: 'BEEN' occured 384 times =? 384 times.
The word: 'BEFORE' occured 640 times =? 640 times.
The word: 'BEGINNING' occured 128 times =? 128 times.
The word: 'BEHELD' occured 128 times =? 128 times.
Press 'Enter' to continue ...
*/
// test_msort_vs_qsort_etc.etc.cpp // // 2018-10-10 //
/*
Merge-Sort times compared to various quick sort times and shell sort time //
*/
// sorts and counts word duplicates ...
// comparing TWO different methods
// 1. using a map to hold in insert sorted order, the (key.value) pairs -> (word, count)
// 2. using a vector to hold all the words, then after sorting it, count any duplicates. //
#define myDebug 1 // set to 0 to turn off, to 1 to turn on //
#include "msort.h" // NOTE!!! ALSO has: typedef unsigned int uns; //
#include "qSort2.H" // a NON 'record order preserving' qsort //
#include "qsort_isort_vector.h" // an 'record order preserving' qsort //
#include <iostream>
#include <fstream> // re. ifstream
#include <iomanip> // re. std::setw(..)
#include <sstream> // re. std::istringstream
#include <string>
#include <cctype> // re. isalpha, toupper
#include <vector>
#include <map>
#include <ctime> // re. running timimg via clock()
#include <cstdlib> // re. qsort //
#include <cstring> // re. strcmp //
#include <algorithm> // re. vector sorts using STL library sort //
using std::cin;
using std::cout;
using std::endl;
using std::flush;
using std::ifstream;
using std::setw;
using std::istringstream;
using std::string;
using std::vector;
using std::map;
const char* IN_FNAME = "Psalms119times128.txt";
template< typename T >
void print( const T ary[], size_t );
template< typename T >
void print( const vector < T >& );
template< typename T >
bool isSorted( const T* ary, size_t, bool a = true );
bool isSortedCstrs( char** ary, size_t, bool a = true );
template< typename T >
bool isSorted( const vector< T >&, bool a = true );
typedef std::vector< string > Words; // this is used in next function qnd following ... //
bool fillFromFile( const char* fname, Words& wds, std::map< string, int >& myPairs );
void toAllCaps( string& str );
void pause( const string& msg = "Press 'Enter' to continue ... " );
char** toCstrings( const string* ary, size_t size )
{
char** pp = (char**)malloc( size*sizeof(char*) );
if( pp )
{
for( size_t i = 0; i < size; ++ i )
{
pp[i] = (char*)malloc( sizeof(char)*(ary[i].size() + 1) );
if(pp[i])
{
size_t j = 0;
for( ; j < ary[i].size(); ++ j ) pp[i][j] = ary[i][j];
pp[i][j] = 0;
}
// else print error and exit //
}
}
// else print srror and exit //
return pp;
}
struct MyCmp // re. demo sorting strings... using functors ... //
{
int operator () ( const string& a, const string& b )
{
if( a < b ) return -1;
if( a > b ) return 1;
return 0;
}
} ;
bool myStrCmp( const string& a, const string& b )
{
return a < b;
}
struct MyCmpRev // re. demo sorting strings... using functors ... //
{
int operator () ( const string& a, const string& b )
{
if( b < a ) return -1;
if( b > a ) return 1;
return 0;
}
} ;
int myCmpCstr( const void* a, const void* b )
{
//return strcmp( *(char* const*)a, *(char* const*)b ); // or //
return strcmp( *(const char**)a, *(const char**)b );
}
bool myStrCmpRev( const string& a, const string& b )
{
return b < a;
}
int myCmpCstrRev( const void* a, const void* b )
{
//return strcmp( *(char* const*)b, *(char* const*)a ); // or //
return strcmp( *(const char**)b, *(const char**)a );
}
int myqStrCmp( const void* a, const void* b )
{
return ( (*(string*)a) ).compare( *(string*)b );
}
int myqStrCmpRev( const void* a, const void* b )
{
return ( (*(string*)b) ).compare( *(string*)a );
}
int main() /////////// MAIN BEGINS /////////////////////////
{
vector< string > myWords;
map < string, int > myPairs; // to hold sorted (word, count) pairs //
if( fillFromFile( IN_FNAME, myWords, myPairs ) )
{
// NOW ... GET/HOLD a copy of the 'unsorted'
// vector in a 'new array' ...
string* ary = new string[myWords.size()];
string* aryCpy = new string[myWords.size()];
for( unsigned i = 0; i < myWords.size(); ++ i )
aryCpy[i] = ary[i] = myWords[i];
double t1 = clock();
msort( myWords, 0, myWords.size()-1 );
double t2 = clock();
cout << "There were " << myWords.size()
<< " words read from file: '" << IN_FNAME << "'\n"
<< myPairs.size()
<< " of which were unique ... \n\n"
<<"Re. the vector 'myWords' and the array 'ary' ...\n "
<< "\nTime to msort vector was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted ... report only if NOT //
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
MyCmp ascending;
msort( myWords, 0, myWords.size()-1, ascending );
t2 = clock();
cout << "Time to msort vector (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
t1 = clock();
MyCmpRev descending;
msort( myWords, 0, myWords.size()-1, descending );
t2 = clock();
cout << "Time to msort vector (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords, false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
t1 = clock();
msort( ary, 0, myWords.size()-1 );
t2 = clock();
cout << "\nTime to msort array was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size() ); // test if sorted //
// re-inital ary... //
for( unsigned i = 0; i < myWords.size(); ++ i )
ary[i] = aryCpy[i];
t1 = clock();
msort( ary, 0, myWords.size()-1, ascending );
t2 = clock();
cout << "Time to msort array (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size() ); // test if sorted //
t1 = clock();
msort( ary, 0, myWords.size()-1, descending );
t2 = clock();
cout << "Time to msort array (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size(), false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
// re-inital ary... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
qSort2( myWords, 0, myWords.size()-1 );
t2 = clock();
cout << "\nTime to qSort2 vector was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
qSort2( myWords, 0, myWords.size()-1, ascending );
t2 = clock();
cout << "Time to qSort2 vector (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
t1 = clock();
qSort2( myWords, 0, myWords.size()-1, descending );
t2 = clock();
cout << "Time to qSort2 vector (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords, false ); // test if sorted //
////////////////////////////////////////////////////////////
// re-inital ary ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
ary[i] = aryCpy[i];
t1 = clock();
qSort2( ary, 0, myWords.size()-1 );
t2 = clock();
cout << "\nTime to qSort2 array was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size() ); // test if sorted //
// re-inital ary ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
ary[i] = aryCpy[i];
t1 = clock();
qSort2( ary, 0, myWords.size()-1, ascending );
t2 = clock();
cout << "Time to qSort2 array (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size() ); // test if sorted //
t1 = clock();
qSort2( ary, 0, myWords.size()-1, descending );
t2 = clock();
cout << "Time to qSort2 array (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size(), false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
// re-inital vector... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
qSort( myWords, 0, myWords.size()-1 );
t2 = clock();
cout << "\nTime to qSort vector was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
qSort( myWords, 0, myWords.size()-1, ascending );
t2 = clock();
cout << "Time to qSort vector (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
t1 = clock();
qSort( myWords, 0, myWords.size()-1, descending );
t2 = clock();
cout << "Time to qSort vector (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords, false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
// re-inital ary... //
for( unsigned i = 0; i < myWords.size(); ++ i )
ary[i] = aryCpy[i];
t1 = clock();
qsort( ary, myWords.size(), sizeof(string), myqStrCmp );
t2 = clock();
cout << "\nTime to qsort array of string was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size() ); // test if sorted //
t1 = clock();
qsort( ary, myWords.size(), sizeof(string), myqStrCmpRev );
t2 = clock();
cout << "Time to qsort array of string (down) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( ary, myWords.size(), false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
// get ragged ary of C strings ... //
char** rAryStrs = toCstrings( aryCpy, myWords.size() );
// debugging ...
// for( size_t k = 0; k < 10; ++ k ) cout << rAryStrs[k] << '\n';
t1 = clock();
qsort( rAryStrs, myWords.size(), sizeof(char*), myCmpCstr );
t2 = clock();
cout << "\nTime to qsort ragged array was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSortedCstrs( rAryStrs, myWords.size() ); // test if sorted //
t1 = clock();
qsort( rAryStrs, myWords.size(), sizeof(char*), myCmpCstrRev );
t2 = clock();
cout << "Time to qsort ragged array (down) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSortedCstrs( rAryStrs, myWords.size(), false ); // test if rev. sorted //
////////////////////////////////////////////////////////////
// re-inital ary... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
sort( myWords.begin(), myWords.end() );
t2 = clock();
cout << "\nTime to C++ library sort vector was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
sort( myWords.begin(), myWords.end(), myStrCmp );
t2 = clock();
cout << "Time to C++ library sort vector (passing in compare function) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
t1 = clock();
sort( myWords.begin(), myWords.end(), myStrCmpRev );
t2 = clock();
cout << "Time to C++ library sort vector (down, passing in compare function) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords, false ); // test if sorted //
////////////////////////////////////////////////////////////
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
shellsort( myWords );
t2 = clock();
cout << "\nTime to shellsort vector was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
// re-inital vector ... //
for( unsigned i = 0; i < myWords.size(); ++ i )
myWords[i] = aryCpy[i];
t1 = clock();
shellsort( myWords, ascending );
t2 = clock();
cout << "Time to shellsort vector (passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords ); // test if sorted //
t1 = clock();
shellsort( myWords, descending );
t2 = clock();
cout << "Time to shellsort vector (down, passing in functor) was "
<< (t2-t1)/CLOCKS_PER_SEC << " seconds.\n";
isSorted( myWords, false ); // test if sorted //
qSort( myWords, 0, myWords.size()-1, ascending ); // resort up to get ready for next part //
pause("Press 'Enter' to continue and see the (word, count) pairs ... " );
// Ok ... show the words and count, 20 at a time ... //
unsigned i = 0, count = 0, stop = 0;
map< string, int >::const_iterator it; // to traverse the map ... //
for( it = myPairs.begin(); it != myPairs.end(); ++ it )
{
++stop; // pause every 20 words //
while( (i < myWords.size()) && (myWords[i] == it->first) )
{
++count;
++i;
}
cout << "The word: '" << it->first << "' occured "
<< it->second << " times =? " << count << " times.\n";
if( stop % 20 == 0 )
pause();
count = 0; // get ready to count the next duplicate words in the vector //
}
cout << "All done? Now i = " << i
<< " and words in myWords = " << myWords.size() << endl;
delete [] aryCpy;
delete [] ary;
// can you code up a clear function for the ragges array? //
}
pause( "\nPress 'Enter' to continue/exit ..." );
} //////////////////// MAIN ENDS ///////////////////////////