buckethybrid.h

Go to the documentation of this file.

#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

template< typename T, typename HFN, typename C >
class buckethybrid : public bucket<T,HFN>
{
public:

  C defaultsorter;
  uintc maxchainlength;

  buckethybrid
  (
    T * data_, 
    uintc datasz_,
    HFN fn_,
    uintc maxchainlength_
  ) : bucket<T,HFN>(data_,datasz_,fn_), maxchainlength(maxchainlength_)
    {}

  void eval();
  void copy(T * data2) const;

protected:

  void mergeuptoelement
  (
    T * & data2, 
    typename C::const_iterator & i, 
    T const & x
  ) const;

  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