#ifndef BUCKETHYBRID_H
#define BUCKETHYBRID_H

#include <cassert>
using namespace std;

#include <bucket.h>
#include <bucketlink.h>
#include <typedefs.h>

//#define DEBUG_BUCKETHYBRID 

#ifdef DEBUG_BUCKETHYBRID
#include <iostream>
#include <print.h>
#endif

/*!
\brief Hybrid bucket sort which in worst case sorts with 
       the default sorter.
When the chain reaches a maximum length all elements on 
 the chain are inserted into the second default sorting container C.
 I expect the client to supply a O(logn) default sorter.

Warning: It is important that I and C template parameters have 
 the same sorting operator.
     

\verbatim
Interface for template HFN parameter

class I
{
  public:

  // Configures the number of buckets.
  uint bucketsize; 
  // Decide which bucket the data belongs.
  uintc index(T const &) const;  
  // Comparision for sorting
  bool const operator()(T const & a, T const & b);
};

Interface for template C parameter
 
C is assumed to be a STL container as C has the following references.

C::const_iterator i
*i to get the data
defaultsorter.begin();
defaultsorter.end()
defaultsorter.insert(x)
defaultsorter.empty()
\endverbatim

\par Example
\verbatim
  vector<double> v(n);
  ... fill v.
  unitdouble f1(n*2);
  typedef buckethybrid<double,unitdouble, multiset<double> > bhd;
  bhd b(chainmax,&v[0],n,f1);
  b.eval();

  vector<double> v2(n);
  b.copy(&v2[0]);
\endverbatim
*/
template< typename T, typename HFN, typename C >
class buckethybrid : public bucket<T,HFN>
{
public:

  /** STL's multiset<T> has log(n) insertion and can handle multiple
      data entry. */
  C defaultsorter;
  /** The maximum number of elements inserted into a chain/list.
      Keep small. */
  uintc maxchainlength;

  /** Pre allocates memory. Pass in the data, data size, hash function
      and the maximum chain length before the data is inserted to the
      default container. */
  buckethybrid
  (
    T * data_, 
    uintc datasz_,
    HFN fn_,
    uintc maxchainlength_
  ) : bucket<T,HFN>(data_,datasz_,fn_), maxchainlength(maxchainlength_)
    {}

  /** Sort the data. */
  void eval();
  /** Extract the result by copying to another vector.
      Merges the two data structures. */
  void copy(T * data2) const;

protected:

  /** Copies the default sorter to data2 upto x in value. */
  void mergeuptoelement
  (
    T * & data2, 
    typename C::const_iterator & i, 
    T const & x
  ) const;

  /** Move the bucket into the defaultsorter. */
  void move(bucketlink<T> * b);
};


//---------------------------------------------------------
// Implementation

template< typename T, typename HFN, typename C >
void buckethybrid<T,HFN,C>::move(bucketlink<T> * b)
{
  for ( ; b!=0; )
  {
    assert(b!=0);
    defaultsorter.insert( * (b->data) );
    b = b->next;
  }
//cout << SHOW(defaultsorter.size()) << endl;
}


template< typename T, typename HFN, typename C >
void buckethybrid<T,HFN,C>::mergeuptoelement
(
  T * & data2, 
  typename C::const_iterator & i, 
  T const & x
) const 
{
  for ( ;i!=defaultsorter.end() ; )
  {
    if (fn(*i,x))
    {
      *data2++ = *i;
      ++i;
    }
    else
      return;
  }
}

template< typename T, typename HFN, typename C >
void buckethybrid<T,HFN,C>::copy(T * data2) const
{
  if (defaultsorter.empty())
  {
    bucket<T,HFN>::copy(data2);
    return;
  }

  typename C::const_iterator pos = defaultsorter.begin();
  bucketlink<T> * cp;

#ifdef DEBUG_BUCKETHYBRID
  // Test code
  cout << "Printing the bucket first" << endl;
  for (uint i=0; i < bucket<T,HFN>::fn.bucketsize; ++i)
  {
    cp = bucket<T,HFN>::vb[i];
    if (cp==0)
      continue;

    for (;cp!=0;)
    {
      cout << *(cp->data) <<  " ";
      cp = cp->next;
    }
    cout << endl;
  }

  cout << "Printing the default sorter" << endl;
  for ( ; pos!=defaultsorter.end(); ++pos )
    cout <<  *pos << " ";
  cout << endl;
  pos = defaultsorter.begin();
#endif

  for (uint i=0; i < bucket<T,HFN>::fn.bucketsize; ++i)
  {
    cp = bucket<T,HFN>::vb[i];
    if (cp==0)
      continue;

    for (;cp!=0;)
    {
      mergeuptoelement(data2,pos,*(cp->data));

      *data2++ = *(cp->data);
      cp = cp->next;
    }
  }

  for ( ; pos!=defaultsorter.end(); ++pos )
    *data2++ = *pos;
}


template< typename T, typename HFN, typename C >
void buckethybrid<T,HFN,C>::eval()
{
  bucketlink<T> * cp;
  bucketlink<T> * b;
  uint k;
  // Insert data into the structure.
  for (uint i=0; i< bucket<T,HFN>::datasz; ++i )
  {
    b = & bucket<T,HFN>::link[i];
    b->data = & bucket<T,HFN>::data[i];

    k = bucket<T,HFN>::fn.index(*b->data); 
    assert( (k < bucket<T,HFN>::fn.bucketsize) );
    k = k % bucket<T,HFN>::fn.bucketsize;

//cout << SHOW(i) << endl;

    cp = bucket<T,HFN>::vb[k];
    if (cp==0)
    {
      bucket<T,HFN>::vb[k] = b; 
      continue;
    }

    // If the insert is contant do it.
    if ( bucket<T,HFN>::fn(*(b->data),*(cp->data)) )
    {
      b->next = cp;
      bucket<T,HFN>::vb[k] = b;
    }
    else
    {
      //bucketlink<T>::insertafterselfcounter = 0;
      cp->insertafterself(b,bucket<T,HFN>::fn);
      if (bucketlink<T>::insertafterselfcounter > maxchainlength)
      {
        move(cp);
        bucket<T,HFN>::vb[k] = 0;
      }
    }
  }
}





#endif