#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>

using namespace std;

class StrCompare {
public:
   bool operator()(const char * a1,
                   const char * a2) const {
      return strcmp(a1, a2) < 0;
   }
};

class Person {
   const char * name;
   int age;
public:

   Person() {
      name = "";
      age = 0;
   }

   Person(const Person & p) {
      name = p.name;
      age = p.age;
   }
 
   Person(const char * name,
          const int age) {
      this->name = name;
      this->age = age;
   }

   Person & operator=(const Person & p) {
      name = p.name;
      age = p.age;
      return *this;
   }

   ~Person() {
   }

   const int get_age() const { return age; }
   const char * get_name() const { return name; }
   void set_name(const char * name) {
      this->name = name;
   }

   void print() {
      cout << "name: " << name << endl;
      cout << "age: " << age << endl;
   }

   bool operator<(const Person & right) const {
      return strcmp(name, right.name) < 0;
   }
};

class PersonCompare {
public:
   bool operator()(const Person & a1, const Person & a2) const {
      return strcmp(a1.get_name(), a2.get_name()) < 0;
   }
};

template< class ForwardIterator, class T, class Compare >
bool binary_search2(ForwardIterator first, ForwardIterator last, const T & val, T ** out, Compare comp)
{
   bool ret = false;
   first = std::lower_bound(first,last,val,comp);
   if(first!=last && !comp(val, *first)) {
      ret = true;
      *out = first;
   }
   return ret;
}

int
main()
{
   long array[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
   less< long > cmp;
   sort(array, array + 10, cmp);
   cout << "---" << endl;
   for(int i = 0; i < 10; i++) {
      cout << "array[" << i << "] == " << array[i] << endl;
   }

   cout << "---" << endl;
   long key = 3;
   long * r;
   if(binary_search2(array, array+10, key, &r, cmp)) {
      cout << "key=" << key << endl;
      cout << "r=" << *r << endl;
   }

   cout << "---" << endl;
   const char * array2[] = { "one", "two", "three", "four", "five" };
   StrCompare scmp;
   sort(array2, array2 + 5, scmp);
   for(int i = 0; i < 5; i++) {
      cout << "array2[" << i << "] == " << array2[i] << endl;
   }

   cout << "---" << endl;
   const char * skey = "four";
   const char ** sr = 0;
   if(binary_search2(array2, array2+5, skey, &sr, scmp)) {
      cout << "sr=" << *sr << endl;
   }

   cout << "---" << endl;
   Person array3[] = { 
      Person("Matthew W. Coan", 42),
      Person("Phoebe", 71),
      Person("John Smith", 33),
      Person("John Boy", 32),
      Person("Elisibeth Corn", 40),
   };
   PersonCompare pcmp;
   sort(array3, array3+5, pcmp);
   for(int i = 0; i < 5; i++) {
      array3[i].print();
      cout << "-----------------" << endl;
   }

   cout << "---" << endl;
   Person pkey;
   pkey.set_name("Matthew W. Coan");
   Person * pr;
   if(binary_search2(array3, array3+5, pkey, &pr, pcmp)) {
      pr->print();
   }
   cout << "---" << endl;
   return 0;
}
