/*
 * A simplified version of std_lib_facilities.h from the book
 * "Programming: Principles and Practice using C++" by Bjarne
 * Stroustrup. Many of the features in std_lib_facilities.h have been
 * removed or simplified. For instance, range-checked vectors have
 * been simplified and renamed to "check_vector", so that "vector" is
 * the regular standard library vector class. One notable addition is
 * the inclusion of cassert.
 *
 */

// By defining std_lib_cmpt125, we avoid problems caused by including
// this file more than once: if std_lib_cmpt125 is already defined,
// then the code is *not* included.
#ifndef std_lib_cmpt125
#define std_lib_cmpt125 201004L

const int std_lib_cmpt125_version = 3;

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>


// C++'s standard functions are all in a namespace called std. This
// line lets us use all those functions without needing to write
// "std::" in front of them.
using namespace std;

// runtime_error is a pre-defined C++ object meant to be "thrown"
// when an error occurs while a program is running. When it is thrown,
// the program will end and print the given error message. It is
// possible to "catch" runtime_error objects to prevent the program
// from crashing, but you should probably never do that for an error
// function like this.
inline void error(const string& s)
{
	throw runtime_error(s);
}
 
inline void error(const string& s, int i)
{
	ostringstream os;
	os << s <<": " << i;
	error(os.str());
}

inline void error(const string& s, const string& t)
{
	ostringstream os;
	os << s <<": " << t;
	error(os.str());
}

//
// check_pre is a macro (not a function!) throws a runtime_error if b is
// false. It does nothing if b is true.
//
// check_pre is meant to be used for testing function pre-conditions. For
// example:
//
//      double my_div(double a, double b) {
//        check_pre(b != 0);
//        return a / b;
//      }
//
// In this example, if b is 0 then check_pre purposely crashes the program
// with an error message saying a pre-condition has failed.
//
// This is implemented as a macro instead of a function to get the  correct
// line number. Macros are essentially a simple textual replacement technique,
// i.e. when the compiler sees (say) check_pre(n > 0) it gets textually
// replaced by this:
//
//    if (!(n > 0)) error("pre-condition failed on line " + to_string(__LINE__) + 
//                        " in file \"" + to_string(__FILE__) + "\"";
//
// Macros don't work like regular functions, and so you need to learn a number
// of special rules to use and debug them effectively. Generally, they are
// more trouble than they are worth, and most of the benefits of macros can
// be gotten in other ways using regular C++ functions.
#define check_pre(b) if (!(b)) error("Pre-condition failed on line " + to_string(__LINE__) + " in file \"" + to_string(__FILE__) + "\"");

//
// The checked_vector class is a very simple extension of the vector
// class that does range-checking whenever you access its elements. It
// works just like vector, but catches index out-of-range errors.
//
// For example, a regular vector does no range-checking:
//
//   vector v(4);
//
//   v[-1] = 6;  // wrong, but no error generated!
// 
// This code compiles and runs, but it is wrong.
//
// If you instead used a checked_vector, the program crashes with an 
// error message:
//
//   checked_vector v(4);
//
//   v[-1] = 6;  // runtime error: v[-1] does not exist!
//
// This code compiles, but at run-time you will get an error indicating
// that -1 is out of range for the vector. This is a very useful way to
// catch errors, and 
//
template<typename T>  
class checked_vector : public vector<T> {
 public:
  //
  // constructors
  //

  // create an empty vector
  checked_vector() : vector<T>() { }
  
  // create a vector of size n
  checked_vector(int n) : vector<T>(n) { }

  //
  // range-checked square-bracket operators
  //

  // Note that the variable "this" is a special pointer that points
  // the checked_vector object itself.

  T& operator[](unsigned int i) {
    if (i >= this->size()) error("index out of range", i);
    return vector<T>::operator[](i);
  }
  
  const T& operator[](unsigned int i) const {
    if (i >= this->size()) error("index out of range", int(i));
    return vector<T>::operator[](i);
  }
}; // class checked_vector
 

// Allows printing of a vector with the << operator.
template<class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  if (v.empty()) return out << "{}";                   // empty vector
  if (v.size() == 1) return out << "{" << v[0] << "}"; // singleton vector

  // v has at least 2 elements
  out << "{" << v[0];
  for(int i = 1; i < v.size(); ++i) { // i starts at 1
    out << ", " << v[i];
  }

  return out << "}";
}


// Returns a new vector of the form {0, 1, 2, ..., n - 1}.
vector<int> range(int n) {
  vector<int> result(n);
  for(int i = 0; i < n; ++i) {
    result[i] = i;
  }
  return result;
}


// On some systems (we're looking at you, Visual C++) the window
// closes after a program ends. This function can be used to keep the
// window open.
inline void keep_window_open() {
  cin.clear();
  cout << "Please enter a character to exit\n";
  char ch;
  cin >> ch;
  return;
}


// Initialize the random number generator with a random seed based on
// the current time.
inline void randomize() {
  srand(time(NULL));
}


// Returns a random int n such that 0 <= n < max.
// It's important to note that the returned number will never be equal
// to max. For example, the biggest value randint(6) will return is 5
// (not 6).
inline int randint(int max) { 
  return rand() % max; 
}


// Returns a random int n such that min <= n < max
// It's important to note that the returned number might be equal to
// min, but will never be equal to max. For example, randint(1, 10)
// might return 5, but it would never return 10 (the biggest value it
// might return is 9).
inline int randint(int min, int max) { 
  return randint(max - min) + min; 
}


// to match C++0x
inline double sqrt(int x) { 
  return sqrt(double(x)); 
}	


// Convert t to a string, e.g.
//    Trace trace("sum(" + to_string(n) + ")");
template<class T> string to_string(const T& t) {
  ostringstream os;
  os << t;
  return os.str();
}


//////////////////////////////////////////////////////////////////////////

// Trace is used to write simple debugging messages when a function is
// called and when it ends. Indentation is used to align a function's
// entering/exiting 
//
// To use it, put it as the first statement
// of a function. For example:
//
//  int sum(int n) {
//    Trace trace("sum(" + to_string(n) + ")");
//    if (n <= 0) 
//      return 0;
//    else
//      return n + sum(n - 1);
//  }
//
// When sum(5) is called, this output is printed:
//
//  sum(5) entered ...
//    sum(4) entered ...
//      sum(3) entered ...
//        sum(2) entered ...
//          sum(1) entered ...
//            sum(0) entered ...
//            ... sum(0) exited
//          ... sum(1) exited
//        ... sum(2) exited
//      ... sum(3) exited
//    ... sum(4) exited
//  ... sum(5) exited
//  
class Trace {
  string msg;
  string spaces;
  static int indent;
  const static int indent_increase;

 public:
  Trace(const string& prompt) : msg(prompt), spaces(indent, ' ') {
    cout << spaces << msg << " entered ..." << endl;
    indent += indent_increase;
  }

  ~Trace() {
    cout << spaces << "... " << msg << " exited" << endl;
    indent -= indent_increase;
  }
}; // class Trace


// The variables indent and indent_increase are static, meaning there
// is only one copy of each that is shared by all Trace objects. 
int Trace::indent = 0;
const int Trace::indent_increase = 2;

//////////////////////////////////////////////////////////////////////////

// A simple class to help write testing messages. For example:
//
//   void is_digit_test() {
//     Test test("is_digit");
//     for(char c = '0'; c <= '9'; ++c)
//       assert(is_digit(c));
//   
//     assert(!is_digit('a'));
//     assert(!is_digit('-'));
//     assert(!is_digit(' '));
//   }
//
class Test {
  string msg;

 public:

 Test(const string& prompt) : msg(prompt) {  // constructor
    cout << "Testing " << msg << " ...\n";
  }

 ~Test() {
   cout << "... all " << msg << " tests passed!\n";
 }

}; // class Test

#endif