1  // This sample code tests the performance of sorting provided by
 2  // "szsort.h". Strings in files specified by command line arguments are
 3  // sorted by StringSort::Sort() and std::sort().
 4  #include "szsort.h"
 5  
 6  #include <cassert>
 7  #include <ctime>
 8  
 9  #include <fstream>
10  #include <string>
11  #include <vector>
12  
13  using namespace std;
14  
15  
16  namespace {
17  
18  // Timer.
19  void Timer(const char *message) {
20    static clock_t cl;
21    if (message == NULL)
22      cl = clock();
23    else
24      printf("%s%.3f sec\n", message, 1.0 * (clock() - cl) / CLOCKS_PER_SEC);
25  }
26  
27  // Function object to get a letter from a key.
28  struct GetLetter {
29    unsigned char operator()(string *key, size_t depth) {
30      return (unsigned char)(*key)[depth];
31    }
32  };
33  
34  // Function object to compare strings.
35  struct CompareStrings {
36    bool operator()(string *lhs, string *rhs) {
37      return *lhs < *rhs;
38    }
39  };
40  
41  // Confirm that an array is sorted.
42  template <typename RandomAccessIterator>
43  void IsSorted(RandomAccessIterator l, RandomAccessIterator r) {
44    while (++l < r)
45      assert(**(l - 1) <= **l);
46  }
47  
48  // Test using files.
49  void TestForFiles(char **files, int num_files) {
50    vector<string *> keys;
51    for (int i = 0; i < num_files; ++i) {
52      ifstream input(files[i]);
53      string line;
54      while (getline(input, line))
55        keys.push_back(new string(line));
56    }
57  
58    // Multikey quicksort.
59    vector<string *> tmp(keys);
60    Timer(NULL);
61    StringSort::Sort(tmp.begin(), tmp.end(), 0, GetLetter());
62    Timer("StringSort::Sort(): ");
63    IsSorted(tmp.begin(), tmp.end());
64  
65    // Standard sorting algorithm.
66    Timer(NULL);
67    sort(keys.begin(), keys.end(), CompareStrings());
68    Timer("std::sort(): ");
69    IsSorted(keys.begin(), keys.end());
70  
71    for (vector<string *>::iterator it = keys.begin(); it != keys.end(); ++it)
72      delete *it;
73  }
74  
75  }  // namespace.
76  
77  
78  int main(int argc, char *argv[]) {
79    assert(argc > 1);
80    TestForFiles(argv + 1, argc - 1);
81    return 0;
82  }