#include "misc.h"

// Toggle debug
#define DEBUG_CONT

#include <set>


//Vector of containers where elements can be inserted into 
//     the container elements.  "cont" is a development class,
//     and really is two different classes doing the same job,
//     written to compare with each other - messy.  Sort of
//     an extension of partition to multiple partitions<



//
// <TODO> Document this class, which is playing the role of 3 classes!
// <TODO> General cont - with variable container
// <TODO> Update documentation
// create Partition, and containers to store them
// 1st April 2002
//


// 
// Binds a condition C to functional objects
// of type T
//
template<class T, class C>
class contcondition
{
   C c;
public:

   // Initialize the condition
   contcondition(C c_=C()) : c(c_) {}

   // Compare
   bool operator ()(T a, T b) const { return c(a(),b()); }
};


//
// container
//
template<class T>
class cont
{
   cont() {};
   T u;
public:

   vector<T> v;

   cont(T upper) : u(upper) {}

   const T operator()() const { return u; }

   bool operator < (T x);

   // Problems with const, if its this hard to implement....
   ostream& print(ostream& os) const
   {
      T temp( (*this)() );
      os << "#" << temp << ":";
      //os << "#" << this->operator() << ":";

      os << printvec<T>(fconst(v)) << "@" << endl;
  
      return os;
   }

   // Add the element, linear time
   // Assumes container c is ordered, min to max 
   static bool add(vector< cont<T> >& c, const T& elem);

   template<class C>
   static bool add2
   ( 
      set< cont<T>, contcondition< cont<T>, C> >& s, 
      const T e
   )
   {

#ifdef DEBUG_CONT
//cout << SHOW(e) << endl;
#endif

      // x is used in search to find point to insert e
      static cont<T> x;
      x.u = e;

      set< cont<T>, contcondition< cont<T>, C> >::const_iterator
         i = s.upper_bound(x);

cout << SHOW( (*i).u ) << endl;
      
#ifdef DEBUG_CONT
   assert( i!=s.end() );
#endif

      if (i==s.end())
         return false;

      //(*i).v.push_back(e);

#ifdef DEBUG_CONT
//cout << SHOW(e);
#endif

      vector<int>& v2( const_cast<vector<int>& >( (*i).v ) ); 
      v2.push_back(e);

      return true;
   }
};


template<class T>
bool cont<T>::operator < (T x)
{
   return u < x;
}

template<class T>
bool cont<T>::add(vector< cont<T> >& c, const T& elem) 
{
   vector< cont<T> >::reverse_iterator j=c.rend();
   vector< cont<T> >::reverse_iterator i=c.rbegin();
   for (; i!=j; ++i)
   {
      if ( (*i)<elem == true )
      {

#ifdef DEBUG_CONT 

cout << SHOW(elem) << endl;
cout << SHOW( (*i)() ) << endl;

   // the element is greater than the container
   assert( i!=c.rbegin() );
#endif

         --i;
         break;
      }
   }
   
   // Insert
   (*i).v.push_back(elem);
}


void print(ostream& os, vector< cont<int> >& c)
{
   for (vector< cont<int> >::iterator i=c.begin();
      i!=c.end(); ++i)
   {
      copy( (*i).v.begin(),(*i).v.end(), ostream_iterator<int>(os," ") );
      os << endl;
   }
}




void test01()
{
   vector< cont<int> > c;
   c.push_back( cont<int>(5) );
   c.push_back( cont<int>(15) );
   c.push_back( cont<int>(35) );
   c.push_back( cont<int>(45) );

   // c is an ordered container

   cont<int>::add(c,25);
   cont<int>::add(c,18);
   cont<int>::add(c,39);
   cont<int>::add(c,30);
   cont<int>::add(c,20);
   cont<int>::add(c,12);
   cont<int>::add(c,7);
   cont<int>::add(c,32);
   cont<int>::add(c,18);
   cont<int>::add(c,20);

   print(cout,c);

   //cont<int> temp(20);
   //cout << temp << endl;
   
   cout << endl << endl;


   cout << printvec< cont<int> >(c);
   

}


class hat
{
public:

   hat() { cout << 0; }

   hat(int k) { cout << k; }
};

template<class T>
class cat : public hat
{
public:

   T x;
   void print() { cout << x; }

   cat() {}

   cat(char ch) : hat(9) { cout << ch; }
   cat(string s)  { cout << s; }
};


//
// Checking that my understanding of temporary objects is clear
//
void test02()
{
   vector<hat> v;
   v.push_back( hat(3) );
   v.push_back( hat() );

   vector<cat<double> > v2;
   v2.push_back( cat<double>() );
   v2.push_back( cat<double>('#') );
   v2.push_back( cat<double>("fku") );
}


void test03()
{
   set< cont<int>, contcondition< cont<int>, less<int> > > s;

   s.insert( cont<int>(35) );
   s.insert( cont<int>(45) );
   s.insert( cont<int>(15) );
   s.insert( cont<int>(5)  );

   // as s is a set, the container is ordered.

   // Use the same data type, a container to find where to insert
   // the element and insert it.  This is the least messy way, without
   // resorting to a pattern or pointers when two different data types
   // are used.  I considered inheritance : one branch represented
   // contiainer, another the items to insert, but indirection and use
   // of pointers made it messy and inefficient.

   cont<int>::add2(s,25);
   cont<int>::add2(s,18);
   cont<int>::add2(s,39);
   cont<int>::add2(s,30);
   cont<int>::add2(s,20);
   cont<int>::add2(s,12);
   cont<int>::add2(s,7);
   cont<int>::add2(s,32);

   vector< cont<int> > c;
   //copy(s.begin(),s.end(),c,back_inserter(c));
   for ( set< cont<int>, contcondition< cont<int>, less<int> > >::const_iterator
      i=s.begin(); i!=s.end(); ++i)
   {

#ifdef DEBUG_CONT
cout << "#" << (*i)() << ":";
cout << printvec<int>(fconst((*i).v)) << "@";
#endif

      c.push_back( *i );
   }

   print(cout,c);
}
   

int main()
{
   test03();


   return 0;
}