// Program: find_array_test.cpp
// test the find function on sample input

#include <iostream>
#include <vector>
#include <set>
#include <string>

typedef std::vector<int>::const_iterator Cit;

namespace ifm {
  // PRE:  [begin, end) is a valid range
  //       Iterator it supports ++it increment
  //       type T can be compared to *it
  // POST: return value is an iterator it in [begin , end) such
  //       that *it == x, or the iterator end if no such 
  //       iterator exists  
  template <typename Iterator, typename T>
  Iterator find (Iterator begin, Iterator end, const T x)
  {
    // insert your code here (and return the solution...)
    return begin;
  }
}  
    
int main() 
{
  const int a[] = {3, 5, 2, 9};
  const int k = 9;
  
  
  // search for k in the in vector:
  std::vector<int> v(a, a+4);
  std::cout << ((ifm::find(v.begin(), v.end(), k) == v.end()) 
               ? "not found\n" 
               : "found\n");  
  
  // check bordercases: empty vector
  std::vector<int> b(a, a);
  std::cout << ((ifm::find(b.begin(), b.end(), k) == b.end()) 
               ? "not found\n" 
               : "found\n");    
  
  // can you also search a vector of doubles?
  std::vector<double> w(a, a+4);
  std::cout << ((ifm::find(w.begin(), w.end(), k) == w.end()) 
               ? "not found\n" 
               : "found\n");   
  
  // your function should also work for simple arrays:
  std::cout << ((ifm::find(a, a+3, k) == a+3) 
               ? "not found\n" 
               : "found\n");   
  
  // and vectors of strings:
  std::vector<std::string> s(4);
  s[0] = "alpha"; s[1] = "beta"; s[2] = "gamma"; s[3] = "delta";
  std::cout << ((ifm::find(s.begin(), s.end(), "gamma") == s.end()) 
               ? "not found\n" 
               : "found\n");     
  
  /*
  // can you also search in sets? test it:
  std::set<int> set(a, a+3);
  std::cout << ((ifm::find(set.begin(), set.end(), k) == set.end()) 
               ? "not found\n" 
               : "found\n"); 
  */
               
  return 0;
}