#ifndef __JLANG__JALLOCATOR__
#define __JLANG__JALLOCATOR__

#include <vector>
#include <limits>

#include "JLang/JException.hh"


/**
 * \file
 * Auxiliary class to speed up new/delete operations of any class.
 * \author mdejong
 */
namespace JLANG {}
namespace JPP { using namespace JLANG; }

namespace JLANG {

  /**
   * Low-level memory management.
   *
   * Source code is taken from reference:
   * A. Alexandrescu, Modern C++ Design, Addison Wesley.
   */
  struct JAllocatorBuffer {

    typedef unsigned short           JBlock_t;


    /**
     * Constructor.
     *
     * \param  block_size          number of bytes
     * \param  number_of_blocks    number of blocks
     */
    JAllocatorBuffer(const std::size_t block_size,
		     const JBlock_t    number_of_blocks)
    {
      buffer = new unsigned char[block_size * number_of_blocks];

      if (buffer == NULL) {
	THROW(JException, "JAllocatorBuffer::init(): not enough space in memory.");
      }

      // initialise memory as linked list

      unsigned char* p = buffer;

      for (JBlock_t i = 0; i != number_of_blocks; p += block_size) {
	((JBlock_t&) *p) = ++i;
      }

      firstAvailableBlock = 0;
      numberOfFreeBlocks  = number_of_blocks;
    }


    /**
     * Allocate memory.
     *
     * \param  block_size          number of bytes
     * \return                     pointer to available memory
     */
    inline void* allocate(const std::size_t block_size)
    {
      unsigned char* p = buffer + firstAvailableBlock * block_size;

      firstAvailableBlock = ((JBlock_t&) *p);

      --numberOfFreeBlocks;

      return p;
    }
 

    /**
     * Deallocate memory.
     *
     * \param  p                   pointer to memory to be freed
     * \param  block_size          number of bytes
     */
    void free(void* p, const std::size_t block_size)
    {
      unsigned char* q = static_cast<unsigned char*>(p);

      if (p < buffer || (q - buffer) % block_size != 0) {
	THROW(JException, "JAllocatorBuffer::free(): inconsistent pointer.");
      }

      ((JBlock_t&) *q) = firstAvailableBlock;

      firstAvailableBlock = static_cast<JBlock_t>((q - buffer) / block_size);

      if (firstAvailableBlock != (q - buffer) / block_size) {
	THROW(JException, "JAllocatorBuffer::free(): failed truncation check.");
      }

      ++numberOfFreeBlocks;
    }


    unsigned char* buffer;
    JBlock_t       firstAvailableBlock;
    JBlock_t       numberOfFreeBlocks;
  };


  /**
   * Memory management for small objects.
   * This object allocator consitutes a comprimise between speed and memory overhead.
   *
   * Source code is taken from reference:
   * A. Alexandrescu, Modern C++ Design, Addison Wesley.
   */
  class JAllocator :
    public std::vector<JAllocatorBuffer>
  {
  private:

    typedef JAllocatorBuffer::JBlock_t        JBlock_t;

    std::size_t          BLOCK_SIZE;
    JBlock_t             numberOfBlocks;

    JAllocatorBuffer*    pAlloc;
    JAllocatorBuffer*    pDealloc;

  public:
    /**
     * Constructor.
     *
     * \param  block_size          number of bytes
     * \param  number_of_blocks    number of blocks
     */
    JAllocator(const std::size_t   block_size,
	       const JBlock_t      number_of_blocks = std::numeric_limits<JBlock_t>::max()) :
      std::vector<JAllocatorBuffer>(),
      BLOCK_SIZE    (block_size),
      numberOfBlocks(number_of_blocks),
      pAlloc  (NULL),
      pDealloc(NULL)
    {}


    /**
     * Get total used RAM.
     *
     * \return                     number of bytes
     */
    long long int getTotalRAM()
    {
      return this->size() * BLOCK_SIZE * numberOfBlocks;
    }


    /**
     * Get total free RAM.
     *
     * \return                     number of bytes
     */
    long long int getFreeRAM()
    {
      long long int n = 0;

      for (const_iterator i = this->begin(); i != this->end(); ++i) {
	n += i->numberOfFreeBlocks;
      }

      return n * BLOCK_SIZE;
    }


    /**
     * Allocate memory.
     *
     * \return                     pointer to avaible memory
     */
    void* allocate()
    {
      if (pAlloc == NULL || pAlloc->numberOfFreeBlocks == 0) {

	for (iterator i = this->begin(); ; ++i) {

	  if (i == this->end()) {

	    this->push_back(JAllocatorBuffer(BLOCK_SIZE, numberOfBlocks));

	    pAlloc   = &this->back();
	    pDealloc = pAlloc;
	    break;
	  }

	  if (i->numberOfFreeBlocks != 0) {

	    pAlloc   = &(*i);
	    break;
	  }
	}

	if (pAlloc == NULL) {
	  THROW(JException, "JAllocator::allocate() no buffer available.");
	}

	if (pAlloc->numberOfFreeBlocks == 0) {
	  THROW(JException, "JAllocator::allocate() no buffer available.");
	}
      }

      return pAlloc->allocate(BLOCK_SIZE);
    }


    /**
     * Deallocate memory.
     *
     * \param  p                   pointer to memory to be freed
     */
    void free(void* p)
    {
      if (this->size() != 1) {

	if (p <  pDealloc->buffer ||
	    p >= pDealloc->buffer + numberOfBlocks * BLOCK_SIZE) {
	  
	  for (std::vector<JAllocatorBuffer>::iterator i = this->begin(); i != this->end(); ++i) {
	    
	    if (p >= i->buffer && 
		p <  i->buffer + numberOfBlocks * BLOCK_SIZE) {
	      pDealloc = &(*i);
	      break;
	    }
	  }
	}
      }


      pDealloc->free(p, BLOCK_SIZE);


      if (this->size() != 1 && pDealloc->numberOfFreeBlocks == numberOfBlocks) {

	std::vector<JAllocatorBuffer>::reverse_iterator i = this->rbegin();

	for ( ; &(*i) != pDealloc && i->numberOfFreeBlocks == numberOfBlocks; ++i) {}

	if (&(*i) != pDealloc) {

	  std::swap(*pDealloc, *i);

	  if (i != this->rend()) {

	    delete [] this->rbegin()->buffer;
	    
	    this->pop_back();
	  }
	}
      }

      pAlloc = pDealloc;
    }
  };
}

#endif