bucket.h

Go to the documentation of this file.

#ifndef BUCKET_H
#define BUCKET_H

#include <cassert>
using namespace std;


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


/*
\brief Implement generic bucket sort for attempted O(n) sorting.  
Worst Case is O(n^2). The bucket allows for duplicate data.

The bucket size is passed through the function and must
 be >= datasz.


\verbatim
Interface for template HFN parameter

class HFN
{
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);
};
\endverbatim

\par Example
\verbatim
  vector<double> v(n);
  fill(&v[0],n);
  
  unitdouble f1(2*n);
  bucket<double,unitdouble> b(&v[0],n,f1);
  b.eval();
\endverbatim

Issues: I chose not to use STL for I may need perhaps hundreds 
 of thousands of lists and I do not know how lightweight STL is.
 Equal elements are unfortunately inserted last.
*/
template< typename T, typename HFN >
class bucket
{
protected: 
  T * data;
  uintc datasz;
  HFN fn;  
  bucketlink<T> * * vb;   
  bucketlink<T> * link;
  uint linki;  
public:

  bucket
  (
    T * data_, 
    uintc datasz_,
    HFN fn_
  );
  ~bucket();

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

};


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


template< typename T, typename HFN >
void bucket<T,HFN>::copy(T * data2) const
{
  assert(data2!=data);

  bucketlink<T> * cp;
  
  for (uint i=0; i<fn.bucketsize; ++i)
  {
    cp = vb[i];
    if (cp==0)
      continue;

    for (;cp!=0;)
    {
      *data2++ = *(cp->data);
      cp = cp->next;
    }
  }

}

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

    k = fn.index(*b->data); 
    assert(k<fn.bucketsize);
    k = k % fn.bucketsize;

    cp = vb[k];
    if (cp==0)
    {
      vb[k] = b; 
      continue;
    }

    if ( fn(*(b->data),*(cp->data)) )
    {
      b->next = cp;
      vb[k] = b;
    }
    else
      cp->insertafterself(b,fn);
  }
}




template< typename T, typename HFN >
bucket<T,HFN>::bucket
(
  T *data_, 
  uintc datasz_,
  HFN fn_
) :
  data(data_),
  datasz(datasz_),
  fn(fn_)
{
  assert(fn.bucketsize >= datasz);

  link = new bucketlink<T>[datasz];

  vb = new bucketlink<T> * [fn.bucketsize];
  for (uint i=0; i<fn.bucketsize; ++i)
    vb[i] = 0;
}

template< typename T, typename HFN >
bucket<T,HFN>::~bucket()
{
  delete[] link;
  delete[] vb;

  link = 0;
  vb = 0;
}





#endif