1  // This sample code tests the performance of sorting provided by
  2  // "szsort.h". Random 7-letters strings are sorted by
  3  // StringSort::Sort() and std::sort().
  4  #include "szsort.h"
  5  
  6  #include <cassert>
  7  #include <ctime>
  8  
  9  #include <vector>
 10  
 11  using namespace std;
 12  
 13  
 14  namespace {
 15  
 16  using std::size_t;
 17  
 18  // Buffer size (how many keys are sorted in this test).
 19  const size_t N = 1 << 20;
 20  
 21  // Structure for random 7-letters keys.
 22  typedef struct Key {
 23    char s[8];
 24  } Key;
 25  
 26  // Buffer to be sorted.
 27  Key Buf[N];
 28  
 29  // Timer.
 30  void Timer(const char *message) {
 31    static clock_t cl;
 32    if (message == NULL)
 33      cl = clock();
 34    else
 35      printf("%s%.3f sec\n", message, 1.0 * (clock() - cl) / CLOCKS_PER_SEC);
 36  }
 37  
 38  // Randomize Keys in buffer.
 39  template <typename RandomAccessIterator>
 40  void RandomizeBuffer(RandomAccessIterator l, RandomAccessIterator r) {
 41    while (l < r) {
 42      for (size_t i = 0; i < sizeof(l->s) - 1; ++i)
 43        l->s[i] = '0' + rand() % 10;
 44      l->s[sizeof(l->s) - 1] = '\0';
 45      ++l;
 46    }
 47  }
 48  
 49  // Confirm that an array is sorted.
 50  template <typename RandomAccessIterator>
 51  void IsSorted(RandomAccessIterator l, RandomAccessIterator r) {
 52    while (++l != r)
 53      assert(strcmp((l - 1)->s, l->s) <= 0);
 54  }
 55  
 56  // Function object to handle same keys.
 57  struct HandleSameKeys {
 58    template <typename RandomAccessIterator>
 59    bool operator()(RandomAccessIterator l, RandomAccessIterator r) {
 60      printf("HandleSameKeys: stop sorting because of same keys\n");
 61      return false;
 62    }
 63  };
 64  
 65  // Function object to get a letter from a key.
 66  struct GetLetter {
 67    unsigned operator()(const Key &key, size_t depth) {
 68      return (unsigned char)key.s[depth];
 69    }
 70  };
 71  
 72  // Function object to compare a pair of keys (for std::sort()).
 73  struct LessThan {
 74    bool operator()(const Key &lhs, const Key &rhs) {
 75      return strcmp(lhs.s, rhs.s) < 0;
 76    }
 77  };
 78  
 79  }  // namespace.
 80  
 81  
 82  int main() {
 83    srand((unsigned)time(NULL));
 84  
 85    // Sorting for an array.
 86    RandomizeBuffer(Buf, Buf + N);
 87    Timer(NULL);
 88    StringSort::Sort(Buf, Buf + N, 0, GetLetter());
 89    Timer("StringSort::Sort() for array: ");
 90    IsSorted(Buf, Buf + N);
 91  
 92    // Sorting will stop if same keys are in the buffer.
 93    RandomizeBuffer(Buf, Buf + N);
 94    Timer(NULL);
 95    bool sorted = StringSort::Sort(Buf, Buf + N, 0,
 96                                   GetLetter(), HandleSameKeys());
 97    Timer("StringSort::Sort() for array with HandleSameKeys(): ");
 98    if (sorted)
 99      IsSorted(Buf, Buf + N);
100  
101    // Sorting for a vector.
102    vector<Key> vec(N);
103    RandomizeBuffer(vec.begin(), vec.end());
104    Timer(NULL);
105    StringSort::Sort(vec.begin(), vec.end(), 0, GetLetter());
106    Timer("StringSort::Sort() for vector: ");
107    IsSorted(vec.begin(), vec.end());
108  
109    // Sorting will stop if same keys are in the buffer.
110    RandomizeBuffer(vec.begin(), vec.end());
111    Timer(NULL);
112    sorted = StringSort::Sort(vec.begin(), vec.end(), 0,
113                              GetLetter(), HandleSameKeys());
114    Timer("StringSort::Sort() for vector with HandleSameKeys(): ");
115    if (sorted)
116      IsSorted(Buf, Buf + N);
117  
118    // Standard sorting algorithm.
119    RandomizeBuffer(vec.begin(), vec.end());
120    Timer(NULL);
121    sort(vec.begin(), vec.end(), LessThan());
122    Timer("std::sort() for vector: ");
123    IsSorted(vec.begin(), vec.end());
124  
125    return 0;
126  }