//: C02:BuggedSearch.cpp {-xo}
// 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.
//{L} ../TestSuite/Test
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <fstream>
#include "../TestSuite/Test.h"
using namespace std;

// Tato funkce je jediná, ve které jsou chyby
int* binarniHledani(int* odkud, int* konec, int cosi) {
  while(konec - odkud != 1) {
    if(*odkud == cosi) return odkud;
    int stred = (konec - odkud) / 2;
    if(cosi <= odkud[stred]) konec = odkud + stred;
    else odkud = odkud + stred;
  }
  return 0;
}

class TestBinarnihoHledani : public TestSuite::Test {
  enum { SZ = 10 };
  int* data;
  int max; // Uchovává největší číslo
  int aktualni; // Aktuální neobsažené číslo
               // použito v neniObsazeno()
  // najít další číslo, které není v poli obsaženo 
  int neniObsazeno() {
    while(data[aktualni] + 1 == data[aktualni + 1])
      ++aktualni;
    if(aktualni >= SZ) return max + 1;
    int vysledek = data[aktualni++] + 1;
    return vysledek;
  }
  void setData() {
    data = new int[SZ];
    assert(!max);
    // Po jedné vložit hodnoty. Nechte nějaké 
		//hodnoty jak na sudých, tak na lichých indexech.
    for(int i = 0; i < SZ;
        rand() % 2 == 0 ? max += 1 : max += 2)
      data[i++] = max;
  }
  void testVRozsahu() {
    // Otestovat jak sudé tak liché pozice
    // jestli obsahují nebo neobsahují
    for(int i = SZ; --i >=0;)
      test_(binarniHledani(data, data + SZ, data[i]));
    for(int i = neniObsazeno(); i < max;
        i = neniObsazeno())
      test_(!binarniHledani(data, data + SZ, i));
  }
  void testMimoRozsah() {
    // Otestovat nižší hodnoty
    for(int i = data[0]; --i > data[0] - 100;)
      test_(!binarniHledani(data, data + SZ, i));
    // Otestovat vyšší hodnoty
    for(int i = data[SZ - 1];
        ++i < data[SZ -1] + 100;)
      test_(!binarniHledani(data, data + SZ, i));
  }
public:
  TestBinarnihoHledani() { max = aktualni = 0; }
  void run() {
    setData();
    testVRozsahu();
    testMimoRozsah();
    delete [] data;
  }
};

int main() {
  srand(time(0));
  TestBinarnihoHledani t;
  t.run();
  return t.report();
} ///:~
