//: C06:SortedSearchTest.cpp
// Z knihy "Myslíme v jazyce C++, část 2" od Bruce Eckela a Chucka Allisona.
// (c) 1995-2004 MindView, Inc. Všechna práva vyhrazena.
// Přečtěte si podmínky používání zdrojových kódů umístěné v souboru 
// 'Licence.txt' dodávaném spolu s balíčkem kódu dostupným na www.MindView.net.
// Test vyhledávání v setříděných rozsazích
// NString
#include <algorithm>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <cstddef>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include "NString.h"
#include "PrintSequence.h"
#include "../require.h"
using namespace std;

int main(int argc, char* argv[]) {
  typedef vector<NString>::iterator sit;
  char* fname = "Test.txt";
  if(argc > 1) fname = argv[1];
  ifstream in(fname);
  assure(in, fname);
  srand(time(0));
  cout.setf(ios::boolalpha);
  vector<NString> original;
  copy(istream_iterator<string>(in),
    istream_iterator<string>(), back_inserter(original));
  require(original.size() >= 4, "Musí mít čtyři prvky");
  vector<NString> v(original.begin(), original.end()),
    w(original.size() / 2);
  sort(v.begin(), v.end());
  print(v.begin(), v.end(), "sort");
  v = original;
  stable_sort(v.begin(), v.end());
  print(v.begin(), v.end(), "stable_sort");
  v = original;
  sit it = v.begin(), it2;
  // Přesunout iterátor do prostředka
  for(size_t i = 0; i < v.size() / 2; i++)
    ++it;
  partial_sort(v.begin(), it, v.end());
  cout << "střed = " << *it << endl;
  print(v.begin(), v.end(), "partial_sort");
  v = original;
  // Přesunout iterátor do čtvrtiny
  it = v.begin();
  for(size_t i = 0; i < v.size() / 4; i++)
    ++it;
  // Do cíle se zkopíruje jen část prvků ze zdroje.
  partial_sort_copy(v.begin(), it, w.begin(), w.end());
  print(w.begin(), w.end(), "partial_sort_copy");
  // Nedostatek místa v cíli
  partial_sort_copy(v.begin(), v.end(), w.begin(),w.end());
  print(w.begin(), w.end(), "w partial_sort_copy");
  // v se během všech operací nemění
  assert(v == original);
  nth_element(v.begin(), it, v.end());
  cout << "n-tý prvek = " << *it << endl;
  print(v.begin(), v.end(), "nth_element");
  string f = original[rand() % original.size()];
  cout << "binární hledání: "
       << binary_search(v.begin(), v.end(), f) << endl;
  sort(v.begin(), v.end());
  it = lower_bound(v.begin(), v.end(), f);
  it2 = upper_bound(v.begin(), v.end(), f);
  print(it, it2, "rozsah nalezen");
  pair<sit, sit> ip = equal_range(v.begin(), v.end(), f);
  print(ip.first, ip.second, "equal_range");
} ///:~
