/*

BINARY FILE SEARCH TREE...

Author: Matthew W. Coan
Date: Thu Jun 22 15:33:34 EDT 2017

*/

#ifndef _D_MAP_H
#define _D_MAP_H

#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
#include "disk_tools.h"
#include "bfstream.h"
#include "bsstream.h"


namespace disk_tools {

using namespace std;

enum { TREE_ORDER = 64 };

template< class Key, class Data >
class d_pair {
public:
   Key key;
   Data data;

   bool operator<(const d_pair< Key, Data > & val) const {
      return key < val.key;
   }

   d_pair< Key, Data > & operator=(const d_pair< Key, Data> & right) {
      key = right.key;
      data = right.data;
      return *this;
   }
};



template< class Key, class Data >
class d_map_node {
public:
   typedef list< d_map_node< Key, Data > * > node_list_type;
   typedef d_pair< Key, Data > pair_type;
   pair_type data[TREE_ORDER];
   offset_type address;
   offset_type left;
   offset_type right;
   offset_type parent;
   offset_type next;
   offset_type size;
   d_map_node< Key, Data > * left0;
   d_map_node< Key, Data > * right0;
   d_map_node< Key, Data > * parent0;
   d_map_node< Key, Data > * next0;
   node_list_type * node_list;
   enum { NODE_SIZE = (sizeof(offset_type) * 6) + ((sizeof(Key) + sizeof(Data)) * TREE_ORDER), };

   d_map_node(node_list_type * nl = 0) {
      left = right = address = parent = next = -1L;
      size = 0U;
      left0 = 0;
      right0 = 0;
      next0 = 0;
      node_list = nl;
   }

   d_map_node(const d_map_node & node) {
      address = node.address;
      left = node.left;
      right = node.right;
      parent = node.parent;
      next = node.next;
      size = node.size;
      left0 = 0;
      right0 = 0;
      next0 = 0;
      node_list = node.node_list;
      for(size_t i = 0; i < TREE_ORDER; i++)
         data[i] = node.data[i];
   }

   ~d_map_node() {
      //if(left0) delete left0;
      //if(right0) delete right0;
   }

   d_map_node & operator=(const d_map_node & right) {
      address = right.address;
      left = right.left;
      this->right = right.right;
      parent = right.parent;
      next = right.next;
      size = right.size;
      for(size_t i = 0; i < TREE_ORDER; i++) 
         data[i] = right.data[i];
      node_list = right.node_list;
      left0 = 0;
      right0 = 0;
      parent0 = 0;
      next0 = 0;
      return *this;
   }

   d_map_node * get_parent(bfstream & in) {
      if(parent == -1L) {
         return 0;
      }
      if(parent0) {
         return parent0;
      }
      d_map_node * ret = new d_map_node(node_list);
      ret->address = parent;
      ret->load(in);
      parent0 = ret;
      return ret;
   }

   d_map_node * get_left(bfstream & in) {
      if(left == -1L) {
         return 0;
      }
      if(left0) {
         return left0;
      }
      d_map_node * ret = new d_map_node(node_list);
      ret->address = left;
      ret->load(in);
      left0 = ret;
      return ret; 
   }

   d_map_node * get_right(bfstream & in) {
      if(right == -1L) {
         return 0;
      }
      if(right0) {
         return right0;
      }
      d_map_node * ret = new d_map_node(node_list);
      ret->address = right;
      ret->load(in);
      right0 = ret;
      return ret;
   }

   d_map_node * get_next(bfstream & in) {
      if(next == -1L) {
         return 0;
      }
      if(next0) {
         return next0;
      }
      d_map_node * p_next = new d_map_node(node_list);
      p_next->address = next;
      p_next->load(in);
      next0 = p_next;
      return p_next;
   }

   int get_left_count(bfstream & file) {
      int ret = 1;
      d_map_node< Key, Data > n;
      n.address = address;
      n.load(file);
      while(n.left != -1L) {
         ret++;
         n.address = n.left;
         n.load(file);
      }
      return ret;
   }

   int get_right_count(bfstream & file) {
      int ret = 1;
      d_map_node< Key, Data > n;
      n.address = address;
      n.load(file);
      while(n.right != -1L) {
         ret++;
         n.address = n.right;
         n.load(file);
      }
      return ret;
   }

   void set_far_left(d_map_node * n, bfstream * file) {
       d_map_node * nn = this;
       while(nn->left != -1L) {
          nn = nn->get_left(*file);
       }
       nn->left = n->address;
       n->parent = nn->address;
       nn->store(*file);
       n->store(*file);
       store(*file);
   }
 
    void set_far_right(d_map_node * n, bfstream * file) {
       d_map_node * nn = this;
       while(nn->right != -1L) {
          nn = nn->get_right(*file);
       }
       nn->right = n->address;
       n->parent = nn->address;
       nn->store(*file);
       n->store(*file);
       store(*file);
   }

   void clear() {
      parent0 = left0 = right0;
   }

   void shift_right4(bfstream & file, d_map_node< Key, Data > & root) {
      d_map_node< Key, Data > *n1,*n2,*n3,*n4,*n5,*n6/*,temp1,temp2,temp3*/;

      n1 = this;

      n2 = n1->get_right(file);

      n3 = n2->get_right(file);

      n4 = n3->get_right(file);

      if(n1->parent != -1L) {
         n6 = n1->get_parent(file);
         n6->load(file);
	 if(n6->right == n1->address)
            n6->right = n3->address;
         else
            n6->left = n3->address;
         n6->store(file);
         if(n6->address == root.address)
            root.load(file);
      }

      offset_type temp1, temp2;

      temp1 = n3->left;
      n3->left = n2->address;
      n3->parent = n1->parent;

      temp2 = n2->left;
      n2->right = temp1;
      n2->left = n1->address;
      n2->parent = n3->address;

      n1->right = temp2;
      n1->parent = n2->address;

      n1->store(file);
      n2->store(file);
      n3->store(file);

      if(address == root.address) {
         root.address = n3->address;
         root.load(file);
      }
      address = n3->address;
      load(file);
   }

   void shift_left4(bfstream & file, d_map_node< Key, Data > & root) {
      d_map_node< Key, Data > *n1,*n2,*n3,*n4,*n5,*n6/*,temp1,temp2,temp3*/;

      n1 = this;

      n2 = n1->get_left(file);
 
      n3 = n2->get_left(file);

      n4 = n3->get_left(file);

      if(n1->parent != -1L) {
         n6 = n1->get_parent(file);
         //n6->load(file);
         if(n6->left == n1->address)
            n6->left = n3->address;
         else 
            n6->right = n3->address;
         n6->store(file);
         if(n6->address == root.address)
            root.load(file);
      }

      offset_type temp1, temp2;

      temp1 = n3->right;
      n3->right = n2->address;
      n3->parent = n1->parent;

      temp2 = n2->right;
      n2->left = temp1;
      n2->right = n1->address;
      n2->parent = n3->address;

      n1->left = temp2;
      n1->parent = n2->address;

      n1->store(file);
      n2->store(file);
      n3->store(file);

      if(address == root.address) {
         root.address = n3->address;
         root.load(file);
      }

      address = n3->address;
      load(file);
   }

   void shift_left(bfstream & file, d_map_node< Key, Data > & root) {
      d_map_node< Key, Data> *n1,*n2,*n3,*n4;

/*
      n1.address = address;
      n1.load(file);

      n2.address = left;
      n2.load(file);

      n3.address = n2.left;
      n3.load(file);
*/

      n1 = this;

      n2 = n1->get_left(file);

      n3 = n2->get_left(file);

      if(n1->parent != -1L) {
         n4 = n1->get_parent(file);
         //n4->load(file);
         if(n4->right == n1->address)
            n4->right = n2->address;
         else
            n4->left = n2->address;
         n4->store(file);
         if(n4->address == root.address)
            root.load(file);
      }

      offset_type temp = n1->parent;
      n1->parent = n2->address;
      n3->parent = n2->address;
      //n2->parent = parent;
      n2->parent = temp;

      n1->left = n2->right;

      n2->left = n3->address;
      n2->right = n1->address;

      n1->store(file);
      n2->store(file);
      n3->store(file);

      if(address == root.address) {
         root.address = n2->address;
         root.load(file);
      }

      address = n2->address;
      load(file);
   }

   void shift_right(bfstream & file, d_map_node< Key, Data > & root) {
      d_map_node< Key, Data > *n1,*n2,*n3,*n4;

      n1 = this;

      n2 = n1->get_right(file);
 
      n3 = n2->get_right(file);

      if(n1->parent != -1L) {
         n4 = n1->get_parent(file);
         //n4->load(file);
         if(n4->right == n1->address)
            n4->right = n2->address;
         else
            n4->left = n2->address;
         n4->store(file);
         if(n4->address == root.address) 
            root.load(file);
      }

      n2->parent = parent;
      n1->parent = n2->address;
      n3->parent = n2->address;

      n1->right = n2->left;

      n2->left = n1->address;
      n2->right = n3->address;
 
      n1->store(file);
      n2->store(file);
      n3->store(file);

      if(address == root.address) {
         root.address = n2->address;
         root.load(file);
      }

      address = n2->address;
      load(file);
   } 
   
   void load(bfstream & in) {
/*
      if(address != -1L) {
         bstringstream binbuf;
         in.seek(address);
         binbuf.load(in, NODE_SIZE);
         binbuf >> left >> right >> parent >> size >> address >> next;
         for(size_t i = 0; i < size; i++) {
            binbuf >> data[i].key;
            binbuf >> data[i].data;
         }
      }
*/
      left0 = 0;
      right0 = 0;
      parent0 = 0;
      next0 = 0;
      if(address != -1L) {
         in.seek(address);
         in >> left;
         in >> right;
         in >> parent;
         in >> size;
         in >> address;
         in >> next;
         for(size_t i = 0; i < size; i++) {
            in >> data[i].key;
            in >> data[i].data;
         }
      }
   }

   void store(bfstream & out) {
      if(address != -1L) {
         bstringstream binbuf;
         binbuf << left << right << parent << size << address << next;
         for(size_t i = 0; i < TREE_ORDER; i++) {
            binbuf << data[i].key;
            binbuf << data[i].data;
         }
         out.seek(address);
         binbuf.write(out);
         out.flush(); 
/*
         out.seek(address);
         out << (size_t)NODE_SIZE;
         out << left;
         out << right;
         out << parent;
         out << size;
         out << address;
         out << next;
         for(size_t i = 0; i < TREE_ORDER; i++) {
            out << data[i].key;
            out << data[i].data;
         }
         out.flush();
*/
      }
   }

   void sort() {
      std::sort(data, data+size);
   }

   Key get_right_most_value(bfstream & file) {
      Key key;
      if(right != -1L) {
         d_map_node< Key, Data > n;
//cout << "LOAD A: " << right << endl;
         n.address = right;
         n.load(file);
         while(n.left != -1L) {
            n.address = n.left;
            n.load(file);
         } 
         key = n.data[0].key;
      }
      return key;
   }

   Key get_left_most_value(bfstream & file) {
      Key key;
      if(left != -1L) {
         d_map_node< Key, Data > n;
//cout << "LOAD B: " << left << endl;
         n.address = left;
         n.load(file);
         while(n.right != -1L) {
            n.address = n.right;
            n.load(file);
         }
         key = n.data[n.size-1].key;
      }
      return key;
   }
};

template< class Key, class Data, class T >
class d_map_assign {
   offset_type address;
   size_t index;
   bfstream * file;

public:
   d_map_assign(offset_type off, size_t ind, bfstream * f) {
      address = off;
      index = ind;
      file = f;
   }

   d_map_assign(const d_map_assign< Key, Data, T > & assign) {
      address = assign.address;
      index = assign.index;
      file = assign.file;
   }

   d_map_assign() {
      address = -1L;
      file = 0;
      index = 0;
   }

   d_map_assign< Key, Data, T > & operator=(const Data & data) {
      d_map_node< Key, Data > node;
      node.address = address;
      node.load(*file);
      node.data[index].data = data;
      node.store(*file);
      return *this;
   }

   d_map_assign< Key, Data, T > & operator=(const d_map_assign< Key, Data, T > & data) {
      address = data.address;
      index = data.index;
      file = data.file;
      return *this;
   }

   Data get_data() {
      d_map_node< Key, Data > node;
      node.address = address;
      node.load(*file);
      return node.data[index].data;
   }

   operator T() {
      d_map_node< Key, Data > node;
      node.address = address;
      node.load(*file);
      return (T)(node.data[index].data);
   }
};

template< class Key, class Data, class T >
class d_map_iterator {
   d_map_node< Key, Data > * p_node;
   bfstream * file;
   size_t index;
   pair< Key, Data > the_pair;

public:
   d_map_iterator(d_map_node< Key, Data > * ptr, bfstream * f) {
      p_node = ptr;
      file = f;
      index = 0;
   }

   d_map_iterator(const d_map_iterator & cp) {
      p_node = cp.p_node;
      file = cp.file;
      index = cp.index;
   }

   d_map_iterator() {
      p_node = 0;
      index = 0;
      file = 0;
   }

   d_map_iterator< Key, Data, T > & operator=(const d_map_iterator< Key, Data, T > & right) {
      p_node = right.p_node;
      file = right.file;
      index = right.index;
      return *this;
   }
   
   d_map_iterator< Key, Data, T > & operator++() {
      index++;
      if(index >= p_node->size) {
         index = 0;
         p_node = p_node->get_next(*file);
      }
      return *this;
   }

   d_map_iterator< Key, Data, T > & operator++(int) {
      index++;
      if(index >= p_node->size) {
         index = 0;
         p_node = p_node->get_next(*file);
      }
      return *this;
   }

   bool operator==(const d_map_iterator< Key, Data, T > & right) {
      bool ret = false;
      if(p_node == 0 && right.p_node == 0) {
         ret = true;
      }
      else if(p_node && right.p_node) {
         if(p_node->data[index].key == right.p_node->data[index].key) { 
            ret = true;
         }
      }
      return ret;
   }

   bool operator!=(const d_map_iterator< Key, Data, T > & right) {
      bool ret = true;
      if(p_node == 0 && right.p_node == 0) {
         ret = false;
      }
      else if(p_node && right.p_node) {
         if(p_node->address == right.p_node->address) {
            if(index == right.index) { 
               ret = false;
            }
         }
      }
      return ret;
   }

   pair< Key, Data > * operator->() {
      the_pair.first = p_node->data[index].key;
      the_pair.second = p_node->data[index].data;
      return &the_pair;
   }

   d_map_assign< Key, Data, T > operator*() {
      return d_map_assign< Key, Data, T >(p_node->address, index, file);
   }
};

template< class Key, class Data, class T = Data >
class d_map {
public:
   typedef d_map_node< Key, Data > node_type;
   typedef d_map_iterator< Key, Data, T > iterator;
   typedef list< d_map_node< Key, Data > * > node_list_type;

private:
   node_type root;
   node_type temp;
   d_alloc * alloc;
   offset_type addr;
   d_database * db_ptr;
   offset_type the_size;
   bfstream * file;
   int full_count;
   node_list_type node_list;
   size_t cash_size;
   offset_type last_address;
   offset_type last_index;
   offset_type head;
   enum { NODE_SIZE = (sizeof(offset_type) * 6) + ((sizeof(Key) + sizeof(Data)) * TREE_ORDER), };

public:
   d_map(const string & name, d_env * env = p_d_env) {
      file = 0;
      alloc = 0;
      addr = -1L;
      the_size = 0L;
      db_ptr = env->get_db();
      alloc = env->get_alloc();
      head = -1L;
      db_ptr->grab(name, *this);
      full_count = 0;
      cash_size = 1024;
      last_address = -1L;
      last_index = -1L;
   }

   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(addr);
      *file >> the_size;
      if(the_size == -1L) {
         the_size = 0L;
         file->seek(addr);
         *file << the_size;
         root.address = alloc->allocate(NODE_SIZE);
         head = root.address;
         root.next = -1L;
         *file << root.address;
         *file << head;
         root.store(*file);
      }
      else {
         *file >> root.address;
         *file >> head;
         root.load(*file);
      }
   }

   ~d_map() {
      file->seek(addr + sizeof(offset_type) + sizeof(offset_type));
      *file << head;
   }

   void clear_node_list() {
      //if(node_list.size() >= cash_size) {
         for(typename node_list_type::iterator ptr = node_list.begin(); ptr != node_list.end(); ptr++) {
            //if((*ptr)->left0) delete (*ptr)->left0;
            //if((*ptr)->right0) delete (*ptr)->right0;
            delete *ptr;
         }
         node_list.clear();
         root.parent0 = root.next0 = root.left0 = root.right0 = 0;
      //}
   }

   void make_even() {
      node_type * n1, * n2, *  n3;
      bool done = false;
      while(!done) {
         done = true;
         stack< node_type * > stk;
         stk.push(&root);
         while(stk.size()) {
            n1 = stk.top();
            stk.pop();
            if(n1 == 0) 
               continue;
            stk.push(n1->get_left(*file));
            stk.push(n1->get_right(*file));
            if(n1->left == -1L && n1->right != -1L) {
               n2 = n1->get_right(*file);
               if(n2->left != -1L && n2->right == -1L) {
                  n3 = n2->get_left(*file);
                  node_type * t1 = n1->get_right(*file);
                  node_type * t2 = n2->get_left(*file);
                  n1->right = -1L;
                  n2->left = -1L;
                  n1->set_far_right(n3, file);
                  n1->set_far_right(n2, file);
                  n1->set_far_right(t1, file);
                  n1->set_far_right(t2, file);
                  n1->store(*file);
                  n2->store(*file);
                  n3->store(*file);
                  t1->store(*file);
                  t2->store(*file);
                  done = false;
                  break;
               }
            }
            else if(n1->left != -1L && n1->right == -1L) {
               n2 = n1->get_left(*file);
               if(n2->left == -1L && n2->right != -1L) {
                  n3 = n2->get_right(*file);
                  node_type * t1 = n1->get_left(*file);
                  node_type * t2 = n2->get_right(*file);
                  n1->left = -1L;
                  n2->right = -1L;
                  n1->set_far_left(n3, file);
                  n1->set_far_left(n2, file);
                  n1->set_far_left(t1, file);
                  n1->set_far_left(t2, file);
                  n1->store(*file);
                  n2->store(*file);
                  n3->store(*file);
                  t1->store(*file);
                  t2->store(*file);
                  done = false;
                  break;
               }
            }         
         }
      }
   }

   void balance() {
      bool do_it = true;
      while(do_it) {
      stack< offset_type > stk;
      map< offset_type, bool > visit;
      node_type n;
      //bool do_it = true;
      int l,r;
      bool first = true;
      //clear_node_list();
      //while(do_it) {
         do_it = false;
         stk = stack< offset_type >();
         stk.push(root.address); 
         visit.clear();
         while(stk.size()) {
            n.address = stk.top();
            stk.pop();
            //if(n.adress == -1L)
               //continue;
            n.load(*file);
/*
            if(visit.find(n.address) != visit.end()) {
               if(n.right != -1L && visit.find(n.right) == visit.end())
                  stk.push(n.right);
               if(n.left != -1L && visit.find(n.left) == visit.end())
                  stk.push(n.left);
               continue;
            }
            visit[n.address] = true;
*/
            //if(n.address == root.address) {
               //root.parent0 = root.left0 = root.right0 = 0;
            ///}
            //n.parent0 = n.left0 = n.right0 = 0;
            if((l = n.get_left_count(*file)) > (r = n.get_right_count(*file))) {
            	while((l - r) >= 3) {
                  //n.parent0 = n.left0 = n.right0 = 0;
                  n.shift_left4(*file, root);
                  //n.parent0 = n.left0 = n.right0 = 0;
                  l = n.get_left_count(*file);
                  r = n.get_right_count(*file);
                  do_it = true;
               }
               //if(do_it) break;

               while((l - r) >= 2) {
                  //n.parent0 = n.left0 = n.right0 = 0;
                  n.shift_left(*file, root);
                  //n.parent0 = n.left0 = n.right0 = 0;
                  l = n.get_left_count(*file);
                  r = n.get_right_count(*file);
                  do_it = true;
               }

               //if(do_it) break;
               //if(do_it) stk = stack< offset_type >();
            }
            else if(r > l/*(r = n.get_right_count(*file)) > (l = n.get_left_count(*file))*/) {
               while((r - l) >= 3) {
                  //n.parent0 = n.left0 = n.right0 = 0;
                  n.shift_right4(*file, root);
                  //n.parent0 = n.left0 = n.right0 = 0;
                  l = n.get_left_count(*file);
                  r = n.get_right_count(*file);
                  do_it = true;
               }

               //if(do_it) break;

               while((r - l) >= 2) {
                  //n.parent0 = n.left0 = n.right0 = 0;
                  n.shift_right(*file, root);
                  //n.parent0 = n.left0 = n.right0 = 0;
                  l = n.get_left_count(*file);
                  r = n.get_right_count(*file);
                  do_it = true;
               }

               //if(do_it) break;
               //if(do_it) stk = stack< offset_type >();
            }
            //n.parent0 = n.left0 = n.right0 = 0;
            if(n.left != -1L /*&& visit.find(n.left) == visit.end()*/)
               stk.push(n.left);
            if(n.right != -1L /*&& visit.find(n.right) == visit.end()*/)
               stk.push(n.right);
         }
      }
   }

   bool insert(const Key & key, const Data & data) {
      bool ret = false;
      node_type * n = &root, * temp;
      bool full = false;
      Key temp_key;
      //full_count = 0;
      while(n) {
         if(n->size < TREE_ORDER && key > n->data[0].key && n->right == -1L) {
            the_size++;
            file->seek(addr);
            *file << the_size;
            n->size++; 
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            if(n->size == TREE_ORDER) {
               full_count++;
               full = true;
            }
            ret = true;
            break;
         }
         else if(n->size < TREE_ORDER && key < n->data[n->size-1].key && n->left == -1L) {
            the_size++;
            file->seek(addr);
            *file << the_size;
            n->size++;
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            if(n->size == TREE_ORDER) {
               full_count++;
               full = true;
            }
            ret = true;
            break;
         }
         else if(n->size < TREE_ORDER && key > n->data[0].key && key < n->data[n->size-1].key) {
            the_size++;
            file->seek(addr);
            *file << the_size;
            n->size++;
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            if(n->size == TREE_ORDER) {
               full_count++;
               full = true;
            }
            ret = true;
            break;
         }
         else if(n->size < TREE_ORDER 
                 && n->left != -1L 
                 && key > n->get_left_most_value(*file) 
                 && key < n->data[n->size-1].key) {
            the_size++;
            file->seek(addr);
            *file << the_size;
            n->size++;
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            if(n->size == TREE_ORDER) {
               full_count++;
               full = true;
            }
            ret = true;
            break;
         }
         else if(n->size < TREE_ORDER 
                 && n->right != -1L 
                 && key > n->data[0].key 
                 && key < n->get_right_most_value(*file)) {
            the_size++;
            file->seek(addr);
            *file << the_size;
            n->size++;
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            if(n->size == TREE_ORDER) {
               full_count++;
               full = true;
            }
            ret = true;
            break;
         }
         else if(n->size == TREE_ORDER && key > n->data[0].key && key < n->data[n->size-1].key) {
            ret = true;
            Key temp_key = n->data[0].key;
            Data temp_data = n->data[0].data;
            for(int i = 0; i < n->size-1; i++) {
               n->data[i] = n->data[i+1];
            }
            n->data[n->size-1].key = key;
            n->data[n->size-1].data = data;
            n->sort();
            n->store(*file);
            insert(temp_key, temp_data);
            break;
         }
         else {
            if(key < n->data[0].key && n->size == TREE_ORDER) {
               temp = n->get_left(*file);
               if(temp) {
                  n = temp;
               }
               else {
                  offset_type tt = n->left;
                  the_size++;
                  file->seek(addr);
                  *file << the_size;
                  n->left = alloc->allocate(NODE_SIZE);
                  n->left0 = 0;
                  n->store(*file);
                  node_type t;
                  t.address = n->left;
                  t.parent = n->address;
                  t.data[0].key = key;
                  t.data[0].data = data;
                  t.next = head;
                  head = t.address;
                  t.size = 1;
                  t.left = tt;
                  t.store(*file);
                  ret = true;
                  break;
               }
            }
            else if(key > n->data[n->size-1].key && n->size == TREE_ORDER) {
               temp = n->get_right(*file);
               if(temp) {
                  n = temp;
               }
               else {
                  offset_type tt = n->right;
                  n->right = alloc->allocate(NODE_SIZE);
                  n->right0 = 0;
                  n->store(*file);
                  the_size++;
                  file->seek(addr);
                  node_type t;
                  *file << the_size;
                  t.address = n->right;
                  t.parent = n->address;
                  t.data[0].key = key;
                  t.data[0].data = data;
                  t.next = head;
                  head = t.address; 
                  t.size = 1;
                  t.right = tt;
                  t.store(*file);
                  ret = true;
                  break;
               }
            }
            else if(n->size < TREE_ORDER && key > n->data[n->size-1].key) {
               temp = n->get_right(*file);
               if(temp) {
                  n = temp;
               }
               else {
                  the_size++;
                  file->seek(addr);
                  *file << the_size;
                  n->size++;
                  n->right0 = 0;
                  n->data[n->size-1].key = key;
                  n->data[n->size-1].data = data;
                  n->sort();
                  n->store(*file);
                  ret = true;
                  break;
               }
            }
            else if(n->size < TREE_ORDER && key < n->data[0].key) {
               temp = n->get_left(*file);
               if(temp) {
               	  n = temp;
               }
               else {
                  the_size++;
                  file->seek(addr);
                  *file << the_size;
                  n->size++;
                  n->left0 = 0;
                  n->data[n->size-1].key = key;
                  n->data[n->size-1].data = data;
                  n->sort();
                  n->store(*file);
                  ret = true;
                  break;
               }
               
            }
            else {
            }
         }
      }

      //make_even();

      if(full_count == 2) {
      	 full_count = 0;
         balance();
         clear_node_list();
      }

      return ret;
   }

   bool update(const Key & key, const Data & data) {
      bool ret = false;
      node_type * n = &root, * temp;
      n->load(*file);
      d_pair< Key, Data > val;
      int index;
      while(n) {
         if(n->size == 0) {
            break;
         }
         else {
            if(key < n->data[0].key) {
               temp = n;
               n = n->get_left(*file);
            }
            else if(key > n->data[n->size-1].key) {
               temp = n;
               n = n->get_right(*file);
            }
            else {
               if((index = bin_search(n, key)) >= 0) {
                  ret = true;
                  n->data[index].data = data;
                  n->store(*file);
               }
               break;
            }
         }
      }

      return ret;
   }

   bool put(const Key & key, const Data & data) {
      bool ret = false;
      if(the_size == 0L) {
         root.address = alloc->allocate(NODE_SIZE);
         root.next = head;
         head = root.address;
         last_address = root.address;
         root.data[0].key = key;
         root.data[0].data = data;
         root.size++;
         root.store(*file);
         the_size++;
         file->seek(addr);
         *file << the_size << root.address << head;
         ret = true;
      }
      else if(!update(key, data)) {
         insert(key, data);
         ret = true;
      }
      return ret;
   }

   bool is_odd(int mid) {
      float temp = (float)(mid);
      temp = temp / 2;
      if((temp - (int)temp) > 0)
         return true;
      return false;
   }

   int bin_search(node_type * n, const Key & key) {
      int l = 0;
      int r = n->size-1;
      int m;
      int ret = -1;
      while(l <= r) {
         m = l + (r-l)/2;
         if(n->data[m].key == key) {
            ret = m;  
            break;
         }
         if(n->data[m].key < key) 
            l = m + 1; 
         else
            r = m - 1; 
      }
      return ret; 
/*
      int ret = -1; 
      for(int i = 0; i < n->size; i++) {
         if(key == n->data[i].key) {
            ret = i;
            break;
         }
      }
      return ret;
*/
   }

   bool get(const Key & key, Data & data) {
      bool ret = false;
      node_type * n = &root, * temp;
      int index;
      while(n) {
         if(n->size == 0) 
            break;
         if(key < n->data[0].key) {
            temp = n;
            n = n->get_left(*file);
         }
         else if(key > n->data[n->size-1].key) {
            temp = n;
            n = n->get_right(*file);
         }
         else {
            if((index = bin_search(n, key)) != -1) {
               last_address = n->address;
               last_index = index;
               data = n->data[index].data;
               ret = true;
            }
            break;
         }
      }

      return ret;
   }

   void print_indent(ostream & out, int indent) {
      for(size_t i = 0; i < indent; i++)
         out << "   " << flush;
   }

   void print_tree_node(d_map_node< Key, Data > * n, ostream & out, int indent = 0) {
      print_indent(out, indent);
      out << n->data[0].key << endl;
      if(n->left != -1L) {
         node_type nn;
         nn.address = n->left;
         nn.load(*file);
         print_tree_node(&nn, out, indent+1);
      }
      if(n->right != -1L) {
         node_type nn;
         nn.address = n->right;
         nn.load(*file);
         print_tree_node(&nn, out, indent+1);
      }
   }

   void print_tree(ostream & out) {
      d_map_node< Key, Data > temp;
      temp.address = root.address;
      temp.load(*file);
      print_tree_node(&temp, out);
   }


   d_map_assign< Key, Data, T > operator[](const Key & key) {
      Data data;
      d_map_assign< Key, Data, T > ret(-1L, -1L, 0);
      if(get(key, data)) {
         d_map_node< Key, Data > node;
         node.load(*file);
         ret = d_map_assign< Key, Data, T >(last_address, last_index, file);
      }
      else {
         put(key, data);
         if(get(key, data)) {
            ret = d_map_assign< Key, Data, T >(last_address, last_index, file);
         }
         else {
            ret = d_map_assign< Key, Data, T >(-1L, -1L, 0);
         }
      }
      return ret;
   }

   d_map_iterator< Key, Data, T > begin() {
      temp.address = head;
      temp.load(*file);
      return d_map_iterator< Key, Data, T >(&temp, file);
   }

   d_map_iterator< Key, Data, T > end() {
      return d_map_iterator< Key, Data, T >(0, file);
   }
};

}

#endif
