#ifndef memory_allocator_h
#define memory_allocator_h

//#include <segment.h>
//#include <traits.h>

enum Memory_Allocation_Algorithms{FIRST_FIT};
enum Heap_Type {STATIC,SEGMENT};


template<unsigned int size, Heap_Type ht> class Heap {
};

template<unsigned int size> class Heap<size, STATIC> {
public:
  void * heap() { return reinterpret_cast<void *> (__heap); }
private:
  unsigned char __heap[size];
};

/*template<unsigned int size>
class Heap<size, SEGMENT> {
public:
  Heap() : _segment(size) {
    Address_Space *as  =  AddressSpace::getCurrent();
    _heap = reinterpret_cast<void *> (as.attach(_segment,0));
  }

  ~Heap() {
    Address_Space *as = AddressSpace::getCurrent();
    as->detach(segment);    		
  }  

  void * heap() { return reinterpret_cast<void >( __heap); }
  void resize(int s) { _segment->resize(s); }
private:
  //unsigned int _log_addr;
  void* __heap;
  Segment  _segment;
};
*/
template<unsigned int memory_size, Memory_Allocation_Algorithms type, Heap_Type t>
class Memory_Allocator {};

template<unsigned int memory_size, Heap_Type t> class Memory_Allocator<memory_size, FIRST_FIT,t> {
  public:
    struct Header{
      unsigned int size;
      unsigned char status;
      void *data;
      void *next;
      void *previous;
    };
  public:
    Memory_Allocator() {
        void *init_heap = ____heap.heap();
        first = reinterpret_cast<Header *> (init_heap);
//        first->size = sizeof(heap) - sizeof(Header);
        first->size = memory_size - sizeof(Header);
        first->status = 0;
//        first->data = &heap[sizeof(Header);
        first->data = reinterpret_cast <void*>(reinterpret_cast<int>(init_heap) + sizeof(Header));
        first->next = 0;
        first->previous = 0;
    }
    ~Memory_Allocator(){}
     void * alloc(unsigned int size) {
        Header *p = first;

        bool found = false;

        while(p!=0 && !found) {
          if(p->status==0 && p->size > size)
            found = true;
          else
            p = reinterpret_cast<Header *> ((p->next));
        }

        if(p==0) {
          return 0;
        }

        Header *next;
        int temp = p->size;

        p->status = 1;
  //p->next = reinterpret_cast<void*>(reinterpret_cast<int>(p->data)+p->size);

        int restOfMemory = (temp - size - sizeof(Header));
        if(p->next==0) {
          if(restOfMemory > 0) {
            p->size = size;
            p->next = reinterpret_cast<void*>(reinterpret_cast<int>(p->data)+p->size);
            next = reinterpret_cast<Header *>((p->next));
            next->size = restOfMemory;
            next->status = 0;
            next->data = reinterpret_cast<void *>(reinterpret_cast<int>(next)+sizeof(Header));
            next->next = 0;
            next->previous = reinterpret_cast<void *>(p);
          }
        } else {
            restOfMemory = p->size - size - sizeof(Header);
            if(restOfMemory > 0) {
              next = reinterpret_cast<Header *>(reinterpret_cast<int>(p->data) + size);
              next->next = p->next;
              //next->previous = reinterpret_cast<void *>(p);
              next->previous = (void *)p;
              next->status = 0;
              next->data = reinterpret_cast<void *>(reinterpret_cast<int>(next)+sizeof(Header));
              next->size = restOfMemory;
              p->size = size;
              p->next = reinterpret_cast<void*>(reinterpret_cast<int>(p->data)+p->size);
            }
        }
        return p->data;
    }
    
    void free(void *obj) {
        Header *p;
        p = reinterpret_cast<Header *>(reinterpret_cast<int>(obj) - sizeof(Header));
        p->status = 0;

        Header *next, *previous;
        next = reinterpret_cast<Header *>(p->next);
        previous = reinterpret_cast<Header *>(p->previous);

        if(next!=0 && next->status==0) {
          p->size = p->size + next->size + sizeof(Header);
          p->next = 0;
          if(next->next!=0) {
            p->next = next->next;
            (reinterpret_cast<Header *>(next->next))->previous = p;
          }
        }                                                  

        if(previous!=0 && previous->status==0) {
          previous->size = p->size + previous->size + sizeof(Header);
          previous->next = 0;
          if(p->next!=0) {
            previous->next = p->next;
            (reinterpret_cast<Header *>(p->next))->previous = previous;
          }
        }
    }

    Header *first;
    Heap<memory_size,t>  ____heap;
};

//Memory_Allocator<Traits<System>::HEAP_SIZE,Traits<System>::ALGORITHM,Traits<System>::HEAP_TYPE> ____ma;
Memory_Allocator<4096,FIRST_FIT,STATIC> ____ma;

void * operator new(unsigned int s) {return ____ma.alloc(s);}
void * operator new[](unsigned int s) {return ____ma.alloc(s);}
void operator delete(void *obj) { ____ma.free(obj);}
void operator delete[](void *obj) {____ma.free(obj);}

#endif