---

PG_heap.hpp

#ifndef _PG_HEAP_HPP_
#define _PG_HEAP_HPP_

#include <vector>

namespace ParGraph
{

namespace heap
{
const size_t rowsize = 256;

template< class TYPE >
class row
{
    TYPE * data;
    size_t first_empty_entry;
    size_t empty_entries_count;
public:
    row() : data(0), empty_entries_count(rowsize) {}
    size_t insert( const TYPE & element );
    size_t insert();
    bool erase( size_t );
    TYPE & operator[] ( size_t pos ) { return data[ pos ]; }
    const TYPE & operator[] ( size_t pos ) const { return data[ pos ]; }
    bool is_full() const { return empty_entries_count == 0; }
    void delete_row() 
        {
            assert( empty_entries_count == rowsize );
            free( data ); data = 0;
        }
    void destrukt();
};

template< class TYPE >
size_t
row<TYPE>::insert( const TYPE & element )
{
  if( data == 0 )
  {
    data = (TYPE*) malloc( rowsize * sizeof(TYPE) * 2 );
    assert( data != 0 );
    for( size_t i = 0 ; i < rowsize ; i++ )
    {
      size_t * p = reinterpret_cast<size_t *>( & data[ i ] );
      *p = i + 1;
    }
    first_empty_entry = 0;
  }
  assert( first_empty_entry < rowsize && empty_entries_count > 0 );

  size_t tmp = first_empty_entry;
  size_t * p = reinterpret_cast<size_t *>( & data[ first_empty_entry ] );
  first_empty_entry = *p;
  new( static_cast< void* >( & data[ tmp ] ) ) TYPE( element );
  empty_entries_count--;
  return tmp;
}

template< class TYPE >
size_t
row<TYPE>::insert()
{
  if( data == 0 )
  {
    data = (TYPE*) malloc( rowsize * sizeof(TYPE) * 2 );
    assert( data != 0 );
    for( size_t i = 0 ; i < rowsize ; i++ )
    {
      size_t * p = reinterpret_cast<size_t *>( & data[ i ] );
      *p = i + 1;
    }
    first_empty_entry = 0;
  }
  assert( first_empty_entry < rowsize && empty_entries_count > 0 );

  size_t tmp = first_empty_entry;
  size_t * p = reinterpret_cast<size_t *>( & data[ first_empty_entry ] );
  first_empty_entry = *p;
  new( static_cast< void* >( & data[ tmp ] ) ) TYPE();
  empty_entries_count--;
  return tmp;
}

template< class TYPE >
bool
row<TYPE>::erase( size_t pos )
{
  data[ pos ].~TYPE();
  size_t * p = reinterpret_cast<size_t *>( & data[ pos ] );
  *p = first_empty_entry;
  first_empty_entry = pos;
  empty_entries_count++;
  return empty_entries_count == rowsize;
}

template< class TYPE >
void
row<TYPE>::destrukt()
{
  if( data == 0 ) return;
  std::vector<bool> tmp( rowsize, true );
  size_t i = first_empty_entry;
  while( i != rowsize )
  {
    tmp[i] = false;
    size_t * p = reinterpret_cast<size_t *>( & data[ i ] );
    i = *p;
  }
  for( i = 0 ; i < rowsize ; i++ )
  {
    if( tmp[i] )  data[ i ].~TYPE();
  }
  free( data );
}

} // namespace heap


template< class TYPE >
class PG_heap
{
    std::vector< heap::row<TYPE> > datarows;

    size_t first_non_full_row;
    bool one_non_deleted_row_exists;
    size_t non_deleted_row;
    size_t _size;
public:
    PG_heap();
    ~PG_heap();

    size_t insert( const TYPE & );
    size_t insert();
    void erase( size_t );
    TYPE & operator[] ( size_t );
    const TYPE & operator[] ( size_t ) const;
    size_t size() const { return _size; }
};

template< class TYPE >
PG_heap<TYPE>::PG_heap() : datarows(), first_non_full_row(0), 
                           one_non_deleted_row_exists(false),
                           non_deleted_row(0), _size(0)
{ }

template< class TYPE >
PG_heap<TYPE>::~PG_heap()
{
  typename std::vector< heap::row<TYPE> >::iterator it = datarows.begin();
  for(; it != datarows.end() ; it++ )
  {
    (*it).destrukt();
  }
}

template< class TYPE >
size_t
PG_heap<TYPE>::insert( const TYPE & element )
{
  _size++;
  if( first_non_full_row == datarows.size() )
  {
    datarows.push_back( heap::row<TYPE>() );
  }

  size_t pos = datarows[ first_non_full_row ].insert( element );
  pos += first_non_full_row * heap::rowsize;

  if( one_non_deleted_row_exists && non_deleted_row == pos )
      one_non_deleted_row_exists = false;

  while( first_non_full_row < datarows.size() && datarows[ first_non_full_row ].is_full() )
  {
    first_non_full_row++;
  }
  return pos;
}

template< class TYPE >
size_t
PG_heap<TYPE>::insert()
{
  _size++;
  if( first_non_full_row == datarows.size() )
  {
    datarows.push_back( heap::row<TYPE>() );
  }

  size_t pos = datarows[ first_non_full_row ].insert();
  pos += first_non_full_row * heap::rowsize;

  if( one_non_deleted_row_exists && non_deleted_row == pos )
      one_non_deleted_row_exists = false;

  while( first_non_full_row < datarows.size() && datarows[ first_non_full_row ].is_full() )
  {
    first_non_full_row++;
  }
  return pos;
}

template< class TYPE >
void
PG_heap<TYPE>::erase( size_t pos )
{
  _size--;
  if( datarows[ pos / heap::rowsize ].erase( pos % heap::rowsize ) )
  {
    if( one_non_deleted_row_exists )
    {
      if( pos / heap::rowsize < non_deleted_row )
      {
        datarows[ non_deleted_row ].delete_row();
        non_deleted_row = pos / heap::rowsize;
      }
      else
      {
        datarows[ pos / heap::rowsize ].delete_row();
      }
    }
    else
    {
      one_non_deleted_row_exists = true;
      non_deleted_row = pos / heap::rowsize;
    }
  }
  if( pos / heap::rowsize < first_non_full_row )
  first_non_full_row = pos / heap::rowsize;
}

template< class TYPE >
TYPE &
PG_heap<TYPE>::operator[] ( size_t pos )
{
  return datarows[ pos / heap::rowsize ][ pos % heap::rowsize ];
}

template< class TYPE >
const TYPE &
PG_heap<TYPE>::operator[] ( size_t pos ) const
{
  return datarows[ pos / heap::rowsize ][ pos % heap::rowsize ];
}

} // namespace ParGraph
#endif // _PG_HEAP_HPP_

---