buckethybrid< T, HFN, C > Class Template Reference

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. More...

#include <buckethybrid.h>

Inheritance diagram for buckethybrid< T, HFN, C >:

Collaboration diagram for buckethybrid< T, HFN, C >:

List of all members.

Public Member Functions
	buckethybrid (T *data_, uintc datasz_, HFN fn_, uintc maxchainlength_)
	Pre allocates memory.
void	eval ()
	Sort the data.
void	copy (T *data2) const
	Extract the result by copying to another vector.
Public Attributes
C	defaultsorter
	STL's multiset<T> has log(n) insertion and can handle multiple data entry.
uintc	maxchainlength
	The maximum number of elements inserted into a chain/list.
Protected Member Functions
void	mergeuptoelement (T *&data2, typename C::const_iterator &i, T const &x) const
	Copies the default sorter to data2 upto x in value.
void	move (bucketlink< T > *b)
	Move the bucket into the defaultsorter.

---

Detailed Description

template<typename T, typename HFN, typename C>
class buckethybrid< T, HFN, C >

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.

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()

Example

  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]);

Definition at line 70 of file buckethybrid.h.

---

Constructor & Destructor Documentation

template<typename T , typename HFN , typename C >

buckethybrid< T, HFN, C >::buckethybrid	(	T *	data_,
		uintc	datasz_,
		HFN	fn_,
		uintc	maxchainlength_
	)			[inline]

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.

Definition at line 85 of file buckethybrid.h.

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

---

Member Function Documentation

template<typename T , typename HFN , typename C >

void buckethybrid< T, HFN, C >::copy

(

T *

data2

)

const [inline]

Extract the result by copying to another vector.

Merges the two data structures.

Reimplemented from bucket< T, HFN >.

Definition at line 151 of file buckethybrid.h.

References bucketlink< T >::data, buckethybrid< T, HFN, C >::defaultsorter, buckethybrid< T, HFN, C >::mergeuptoelement(), and bucketlink< T >::next.

{
  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

(

)

[inline]

Sort the data.

Reimplemented from bucket< T, HFN >.

Definition at line 207 of file buckethybrid.h.

References bucketlink< T >::data, bucketlink< T >::insertafterself(), buckethybrid< T, HFN, C >::maxchainlength, buckethybrid< T, HFN, C >::move(), and bucketlink< T >::next.

{
  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;
      }
    }
  }
}

template<typename T , typename HFN , typename C >

void buckethybrid< T, HFN, C >::mergeuptoelement	(	T *&	data2,
		typename C::const_iterator &	i,
		T const &	x
	)			const [inline, protected]

Copies the default sorter to data2 upto x in value.

Definition at line 132 of file buckethybrid.h.

Referenced by buckethybrid< T, HFN, C >::copy().

{
  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 >::move

(

bucketlink< T > *

b

)

[inline, protected]

Move the bucket into the defaultsorter.

Definition at line 118 of file buckethybrid.h.

References bucketlink< T >::data, buckethybrid< T, HFN, C >::defaultsorter, and bucketlink< T >::next.

Referenced by buckethybrid< T, HFN, C >::eval().

{
  for ( ; b!=0; )
  {
    assert(b!=0);
    defaultsorter.insert( * (b->data) );
    b = b->next;
  }
//cout << SHOW(defaultsorter.size()) << endl;
}

---

Member Data Documentation

template<typename T , typename HFN , typename C >

C buckethybrid< T, HFN, C >::defaultsorter

STL's multiset<T> has log(n) insertion and can handle multiple data entry.

Definition at line 76 of file buckethybrid.h.

Referenced by buckethybrid< T, HFN, C >::copy(), and buckethybrid< T, HFN, C >::move().

template<typename T , typename HFN , typename C >

uintc buckethybrid< T, HFN, C >::maxchainlength

The maximum number of elements inserted into a chain/list.

Keep small.

Definition at line 79 of file buckethybrid.h.

Referenced by buckethybrid< T, HFN, C >::eval().

---

The documentation for this class was generated from the following file:

• bucket/buckethybrid.h