#ifndef BUCKETLINK_H
#define BUCKETLINK_H

#include <cassert>
using namespace std;

#include <typedefs.h>


//#define DEBUG_BUCKETLINK

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


/*!
\brief:  Used by class bucket.  This is a linked list class.
*/
template< typename T>
class bucketlink
{
public:

  /** Hold the data. */
  T * data;

  /** The next link in the chain. */
  bucketlink * next;

  /** Construct an empty link. */
  bucketlink()
    : data(0), next(0) 
    {}
  /** Construct with data. */
  bucketlink(T * data_)
    : data(data_), next(0)
    {}

  /** Set to zero before inserting, then you can compare
     after insertion to see the chain length. */
  static uint insertafterselfcounter;

  /** Insert the link in the list in order.
      This routine can only insert after itself 
      and not before. */
  template< typename I2 >
  void insertafterself(bucketlink<T>* b, I2 & fn);

};

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

template< typename T>
uint bucketlink<T>::insertafterselfcounter = 0;

template< typename T>
template< typename I2 >
void bucketlink<T>::insertafterself(bucketlink<T>* b, I2 & fn)
{
  assert(b!=0);
  assert( fn(*(b->data),*(this->data))==false );

insertafterselfcounter=0;

  bucketlink<T>* cp = next;
  bucketlink<T>* cp0 = this;
  for ( ;cp!=0; )
  {

    ++insertafterselfcounter;
#ifdef DEBUG_BUCKETLINK
cout << SHOW(insertafterselfcounter) << endl;
#endif

    if (fn(*(b->data),*(cp->data)))
    {
      b->next = cp;
      cp0->next = b;
      return;
    }

    cp0 = cp;
    cp = cp->next;
  }

  // Insert at the end of the list.
  cp0->next = b;
  b->next=0;
}

#endif