#ifndef _D_LIST_H
#define _D_LIST_H

#include <iostream>
#include <fstream>
#include <sstream>
#include <typeinfo>
#include "bfstream.h"
#include "bsstream.h"
#include "disk_tools.h"
#include "d_alloc.h"
#include "d_db.h"

namespace disk_tools {

using namespace std;
using namespace io_tools;

typedef long offset_type;

template< class T >
class d_list;

template< class T >
bfstream & operator<<(bfstream & bf, const d_list< T > & l);

template< class T >
bfstream & operator>>(bfstream & bf, d_list< T > & l);

template< class T >
bstringstream & operator<<(bstringstream & bf, const d_list< T > & l);

template< class T >
bstringstream & operator>>(bstringstream & bf, d_list< T > & l);

template< class T >
class d_list_node {
public:
   offset_type data;
   offset_type addr;
   offset_type next;
   offset_type prev;

   d_list_node() {
      data = addr = next = prev = -1L;
   }

   d_list_node(const d_list_node< T > & cp) {
      data = cp.data;
      addr = cp.addr;
      next = cp.next;
      prev = cp.prev;
   }

   d_list_node< T > operator=(const d_list_node< T > & right) {
      this->addr = right.addr;
      this->next = right.next;
      this->prev = right.prev;
      this->data = right.data;
      return *this;
   }

   void load(bfstream * fp) {
      (*fp) >> addr >> next >> prev >> data;
   }

   void store(bfstream * fp) {
      (*fp) << addr << next << prev << data;
   }

   size_t get_size() {
      return sizeof(addr) + sizeof(next) + sizeof(prev) + sizeof(data);
   }

   T get_data(bfstream * file) {
      file->seek(data);
      T temp;
      *file >> temp;
      return temp;
   }
};

template< class T >
class d_list;

template< class T >
class dl_assign {
   d_list_node< T > * ptr;
   d_alloc * alloc;
   bfstream * file;
public:
   dl_assign(d_list_node< T > * ptr, d_alloc * alloc, bfstream * file) {
      this->ptr = ptr;
      this->alloc = alloc;
      this->file = file;
   }

   dl_assign() {
      ptr = 0;
      alloc = 0;
      file = 0;
   }

   dl_assign(const dl_assign< T > & cp) {
      ptr = cp.ptr;
      alloc = cp.alloc;
      file = cp.file;
   }

   ~dl_assign() {
   }

   size_t get_size(const T & data) {
      bstringstream ss;
      ss << data;
      return ss.size();
   }

   dl_assign< T > & operator=(const T & data) {
      alloc->dealloc(ptr->data);

      ptr->data = alloc->alloc(get_size(data)); 
 
      file->seek(ptr->data);

      *file << data;      

      file->seek(ptr->addr);

      ptr->store(file);

      return *this;
   }

   bool operator<(const dl_assign< T > & right) {
      return get_data(ptr->data) < get_data(right.ptr->data);
   }

   T get_data(offset_type addr) {
      file->seek(addr);
      T temp; 
      *file >> temp;
      return temp;
   }
  
   operator T() {
      file->seek(ptr->data);
      T temp; 
      *file >> temp;
      return temp;
   }
};

template< class T >
class dl_iterator {
   d_list_node< T > ptr;
   bfstream * file;
   d_alloc * alloc;
   T temp;

public:
   dl_iterator() {
      file = 0;
      alloc = 0;
   }
   dl_iterator(const dl_iterator< T > & cp) {
      ptr = cp.ptr;
      file = cp.file;
      alloc = cp.alloc;
      temp = cp.temp;
   }
   dl_iterator(d_list_node< T > ptr, bfstream * file, d_alloc * alloc) {
      this->ptr = ptr;
      this->file = file;
      this->alloc = alloc;
   }
   dl_iterator & operator=(const dl_iterator & right) {
      ptr = right.ptr;
      file = right.file;
      alloc = right.alloc;
      temp = right.temp;
      return *this;
   }
   bool operator==(const dl_iterator & right) {
      return ptr->addr == right.ptr->addr;
   }
   bool operator<(dl_iterator & right) {
      return get_data(ptr->data) < get_data(right.ptr->data);
   }
   T get_data(offset_type addr) {
      T temp;
      file->seek(addr);
      *file >> temp;
      return temp;
   }
   T * get_data2(offset_type addr) {
      file->seek(addr);
      *file >> temp;
      return &temp;
   }
   T * operator->() {
      return get_data2(ptr.data);
   }
   dl_assign< T > operator*() {
      return dl_assign< T >(&ptr, alloc, file);
   }
   d_list_node< T > * get_node() { return &ptr; }
   dl_iterator & operator++(int) {
      d_list_node< T > n;
      file->seek(ptr.next);
      n.load(file);
      ptr = n;
      return *this;
   }
   dl_iterator & operator++() {
      return *this;
   }
   dl_iterator & operator--(int) {
      d_list_node< T > n;
      file->seek(ptr.prev);
      n.load(file);
      ptr = n;
      return *this;
   }
   dl_iterator & operator--() {
      return *this;
   }
   bool operator!=(const dl_iterator< T > & right) {
      return ptr.addr != right.ptr.addr;
   }
   operator void*() {
      return (void*)ptr.addr;
   }
};

template< class T >
class CompLess {
public:
   bool operator()(const T & a, const T & b) const {
      return a < b;
   }
};

template< class T >
class d_list {
public:
   typedef dl_iterator< T > iterator;

private:
   d_list_node< T > head;
   bfstream * file;
   d_alloc * alloc;
   offset_type addr;
   d_database * db_ptr;
   offset_type the_size;

public:
   d_list(d_env * env = p_d_env) {
      db_ptr = env->get_db();
      alloc = env->get_alloc();
      offset_type temp = create_list(db_ptr);
      db_ptr->grab(temp, *this);
   }
   d_list(const offset_type & address, d_env * env = p_d_env) {
      db_ptr = env->get_db();
      alloc = env->get_alloc();
      db_ptr->grab(address, *this);
   }
   d_list(const string & name, d_env * env = p_d_env) {
      file = 0;
      alloc = 0;
      addr = head.next = head.prev = -1L;
      the_size = 0L;
      db_ptr = env->get_db();
      alloc = env->get_alloc();
      db_ptr->grab(name, *this);
   }
   ~d_list() {
   }
   void load() {
      file->seek(addr);
      offset_type temp;
      *file >> temp;
      file->seek(temp);
      *file >> addr >> the_size;
      file->seek(addr);
      head.load(file); 
   }
   void grab(bfstream * file, offset_type addr, d_alloc * alloc, d_database * db_ptr) {
      this->file = file;
      this->alloc = alloc;
      this->addr = addr;
      this->db_ptr = db_ptr;
      file->seek(this->addr);
      offset_type temp;
      *file >> temp;
      if(temp != -1L) {
         file->seek(temp);
         *file >> this->addr >> the_size;
         file->seek(this->addr);
         head.load(file);
      }
      else {
         head.addr = alloc->allocate(head.get_size() + sizeof(offset_type));
         temp = create_list(db_ptr);
         file->seek(addr);
         *file << temp;
         the_size = 0L;
         file->seek(temp);
         *file << head.addr << the_size;
         head.next = head.addr;
         head.prev = head.addr;
         file->seek(head.addr);
         head.store(file);
      }
   }
   d_list< T > & operator=(const d_list< T > & right) {
      clear();
      the_size = 0;
      for(d_list< T >::iterator ptr = right.begin(); ptr != right.end(); ptr++) {
         push_back(*ptr);
      }
      save_size();
      return *this;
   }
   d_database * get_db() { return db_ptr; }
   offset_type get_head_addr() { return head.addr; }
   void save_size() {
      file->seek(head.addr + head.get_size());
      *file << the_size;
   } 
   offset_type size() const {
      return the_size;
   }
   iterator begin() const { 
      d_list_node< T > node;
      file->seek(head.next);
      node.load(file);
      return dl_iterator< T >(node,file,alloc); 
   }
   iterator begin() { 
      d_list_node< T > node;
      file->seek(head.next);
      node.load(file);
      return dl_iterator< T >(node,file,alloc); 
   }
   iterator end() { 
      return dl_iterator< T >(head,file,alloc);
   }
   iterator end() const { 
      return dl_iterator< T >(head,file,alloc);
   }

   size_t get_size(const T & data) {
      bstringstream ss;
      ss << data;
      return ss.size();
   }

   void push_front(const T & data) { 
      d_list_node< T > node, node2;
      
      offset_type temp = alloc->alloc(get_size(data));
      file->seek(temp);
      *file << data;
      node2.data = temp;
      node2.addr = alloc->alloc(node.get_size());
      node2.next = head.next;
      node2.prev = head.addr;
      file->seek(node2.addr);
      node2.store(file);

      if(head.next != head.addr) {
         file->seek(head.next);
         node.load(file);
         node.prev = node2.addr;
         file->seek(head.next);
         node.store(file); 
      }

      if(head.prev == head.addr) {
         head.prev = node2.addr;
      } 

      head.next = node2.addr;
      file->seek(head.addr);
      head.store(file);

      the_size++;

      save_size();

      file->flush();
   }

   void push_back(const T & data) {
      d_list_node< T > node;
      d_list_node< T > node2;

      offset_type temp = alloc->alloc(get_size(data));
      file->seek(temp);
      *file << data;
      node.data = temp;

      node.addr = alloc->allocate(node.get_size());
      node.next = head.addr;
      node.prev = head.prev;
      file->seek(node.addr);
      node.store(file);

      if(head.prev != head.addr) {
         file->seek(head.prev);
         node2.load(file);
         node2.next = node.addr;
         file->seek(head.prev);
         node2.store(file);
      }
      
      if(head.next == head.addr) {
         head.next = node.addr;
      }

      head.prev = node.addr;
      file->seek(head.addr);
      head.store(file);

      the_size++;
 
      save_size();

      file->flush();
   }

   void insert(iterator n, const T & data) {
      d_list_node< T > node, node2, * ptr = n.get_node();
      offset_type temp = alloc->alloc(get_size(data));
      file->seek(temp);
      *file << data;
      node.data = temp;
      node.addr = alloc->allocate(node.get_size());
      node.next = ptr->addr;
      node.prev = ptr->prev;
      file->seek(node.addr);
      node.store(file);

      file->seek(ptr->prev);
      node2.load(file);
      node2.next = node.addr;
      file->seek(ptr->prev);
      node2.store(file);

      file->seek(ptr->next);
      node2.load(file);
      node2.prev = node.addr;
      file->seek(ptr->next);
      node2.store(file);

      the_size++;
      save_size();
   }

   void pop_front() {
      iterator it = begin();
      erase(it);
   }

   void pop_back() {
      iterator it = end();
      erase(it);
   }

   T get_data(offset_type addr) {
      T temp;
      file->seek(addr);
      *file >> temp;
      return temp;
   }

   T front() { 
      d_list_node< T > node;
      file->seek(head.next);
      node.load(file);
      return get_data(node.data);
   }

   T back() {
      d_list_node< T > node;
      file->seek(head.prev);
      node.load(file);
      return get_data(node.data);
   }

   void clear() {
      d_list_node< T > node;
      file->seek(head.next);
      node.load(file);
      while(node.addr != head.addr) {
         alloc->deallocate(node.data);
         alloc->deallocate(node.addr);
         file->seek(node.next);
         node.load(file);
      }
      head.next = head.addr;
      head.prev = head.addr;
      file->seek(head.addr);
      head.store(file);

      the_size = 0L;
      save_size();
   }

   void erase(iterator & ptr) {

      d_list_node< T > * n = ptr.get_node();
      d_list_node< T > left;
      d_list_node< T > right;

      if(n->addr == head.addr) {
         file->seek(n->next);
         left.load(file);

         file->seek(left.next);
         right.load(file);

         head.next = right.addr;
         file->seek(head.addr);
         head.store(file);

         right.prev = head.addr;
         file->seek(right.addr);
         right.store(file);

         alloc->dealloc(left.data);
         alloc->dealloc(left.addr);

         the_size--;
         save_size();
      }
      else {
         file->seek(n->next);
         right.load(file);

         file->seek(n->prev);
         left.load(file);

         left.next = right.addr;
         right.prev = left.addr;

         file->seek(left.addr);
         left.store(file);

         file->seek(right.addr);
         right.store(file);

         alloc->dealloc(n->data);
         alloc->dealloc(n->addr);

         the_size--;
         save_size();
      }
   }

   void erase(iterator & ptr1, iterator & ptr2) {
      d_list_node< T > * n1 = ptr1.get_node();
      d_list_node< T > * n2 = ptr2.get_node();
      d_list_node< T > node1 = *n1;
      d_list_node< T > node2 = *n2;


      file->seek(n1->prev);
      n1->load(file);
      node1 = *n1;

      if(n1->addr == head.addr && n2->addr == head.addr) {
         clear();
      }
      else { 
         while(node1.addr != node2.addr) {
            file->seek(node1.next);
            node1.load(file);
            if(node1.addr != node2.addr) {
               the_size--;
               alloc->dealloc(node1.data);
               alloc->dealloc(node1.addr);
            }
         }

         n1->next = n2->addr;
         n2->prev = n1->addr;
  
         file->seek(n1->addr);
         n1->store(file);

         file->seek(n2->addr);
         n2->store(file);

         save_size(); 
      }
   }

   void swap(iterator & ptr1, iterator & ptr2) {
      offset_type temp1 = ptr1.get_node()->data;
      offset_type temp2 = ptr2.get_node()->data;

      ptr1.get_node()->data = temp2;
      ptr2.get_node()->data = temp1;

      file->seek(ptr2.get_node()->addr);
      ptr2.get_node()->store(file);

      file->seek(ptr1.get_node()->addr);
      ptr1.get_node()->store(file);
   }

   offset_type get_address() const {
      return addr;
   }

   offset_type get_address() {
      return addr;
   }

   void set_address(const offset_type & off) {
      addr = off;
   }

   void sort() {
      CompLess< T > cmp;
      sort(cmp);
   }

   template< class Comp >
   void sort(Comp comp) {
      for(iterator ptr1 = begin(); ptr1 != end(); ptr1++) {
         for(iterator ptr2 = ptr1; ptr2 != end(); ptr2++) {
            if(ptr1 != ptr2) {
               if(comp(get_data(ptr1.get_node()->data), get_data(ptr2.get_node()->data))) {
                  swap(ptr1, ptr2);
               }
            }
         }
      }
   }

   void set_addr(const offset_type & addr) {
      this->addr = addr;
   }

   void set_size(const offset_type & sz) {
      this->the_size = sz;
   }
};

template< class T >
inline
bfstream & operator<<(bfstream & bf, const d_list< T > & l)
{
    bf << l.get_address() << l.size();
    return bf;
}

template< class T >
inline
bfstream & operator>>(bfstream & bf, d_list< T > & l)
{
    offset_type addr,size;
    bf >> addr >> size;
    l.set_address(addr);
    l.set_size(size);
    l.load();
    return bf;
}

template< class T >
inline
bstringstream & operator<<(bstringstream & bf, const d_list< T > & l)
{
    bf << l.get_address() << l.size();
    return bf;
}

template< class T >
inline
bstringstream & operator>>(bstringstream & bf, d_list< T > & l)
{
    return bf;
}

 
}

#endif /* _D_LIST_H */
