#include "misc.h"

#include <iostream>
#include <algorithm>



using namespace std;

void test01()
{
   // Output the permuations of the set {1,2,3,4,5}

   //
   // Permutation of n elements = n!
   // The current permutation isn't repeated.
   //
   // Use:
   // Ordering is used to keep track of the permutation state.
   // To go through all elements in the set, order in an ascending
   // direction before starting to permutate.
   //
   

   int a[5] = {1,2,3,4,5};
   vector<int> v(a,a+sizeof(a)/sizeof(int));

  

   cout << "Initial permutation" << endl;
   copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
   cout << endl << endl;

   int counter=0;

   while ( next_permutation(v.begin(),v.end()) )
   {
      copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
      cout << endl;
      ++counter;
   }

   cout << "counter=" << counter << endl;


}



bool divby11(const vector<int>& v)
{
   // Test if there is a number
   if (v.empty() )
      return false;

   // Sum of odd digits = sum of even digits for divisablility by 11.
   // eg  121  1 - 2 + 1 == 0  so 121 is divisable by 11. 

   int sum=0;

   bool sgn=false;
   vector<int>::const_iterator i=v.begin();
   vector<int>::const_iterator j=v.end();

   for ( ; i!=j; ++i )
   {
      if (sgn)
      {
         sgn=false;
         sum += *i;
      }
      else
      {
         sgn=true;
         sum -= *i;
      };
   }

   return sum==0;
}
   

// Test bool divby11(const vector<int>& )

void test02()
{
   // 121
   vector<int> v2;
   v2.push_back(1); v2.push_back(2); v2.push_back(1);
   cout << divby11(v2) << endl;

   // 23
   vector<int> v3;
   v3.push_back(2); v3.push_back(3);
   cout << divby11(v3) << endl;
}

void test03()
{
   // Problem : Find permutation of digits 1234 that
   //    are divisible by 11.

   int a[] = {1,2,3,4};
   vector<int> v(a,a+sizeof(a)/sizeof(int));

   do
   {
      if (divby11(v))
      {
         copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
         cout << endl;
      }
   } while ( next_permutation(v.begin(),v.end()) );

}


void test04()
{
   // Problem : Find permutation of digits 12345 that
   //    are divisible by 11.

   int a[] = {1,2,3,4,5};
   vector<int> v(a,a+sizeof(a)/sizeof(int));

   do
   {
      if (divby11(v))
      {
         copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
         cout << endl;
      }
   } while ( next_permutation(v.begin(),v.end()) );

}

#include <iterator>

template< class BidIt >
void print_reverse( BidIt first, BidIt last)
{
   reverse_iterator< BidIt > rfirst(last);
   reverse_iterator< BidIt > rlast(first);

   for (; rfirst!=rlast; ++rfirst)
      cout << *rfirst << " ";
}


//
// Testing iterator conversions
//
   
void test05()
{
   int a[5] = {1,2,3,4,5};
   vector<int> v(a,a+sizeof(a)/sizeof(int));

   print_reverse(v.begin(),v.end());

 //  cout << "Initial permutation" << endl;
 //  copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
 //  cout << endl << endl;


}


//
//<TODO> Implement next_comb
//

// bool next_comb (Iter first, Iter last, unsigned int count)
//{
//...
//}

// Use next_permutation.  If the permutation doesn't change
// in the first count places, repeat.  This generates the next
// combination.

//
// <TODO> equal algorithm - give examples
//

   


int main()
{

   test05();

   return 0;
}