#include <iostream>
#include <algorithm>
#include <cstdlib>

namespace std {

using namespace std;

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

   array_map_node(const Key & k, const Data & d) {
      key = k;
      data = d;
   }

   array_map_node() {
   }

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

template< class Key, class Data >
class array_map_comp {
public:
   bool operator()(const array_map_node< Key, Data > * arg1,
                   const array_map_node< Key, Data > * arg2) const {
      bool ret = false;
      ret = arg1->key < arg2->key;
      return ret;
   }
};

template< class Key, class Data >
class array_map;

template< class Key, class Data >
class array_map_iterator {
public:
   typedef int size_type;
   typedef array_map_node< Key, Data > ** array_type;

private:
   friend class array_map< Key, Data >;
   size_type index;
   array_type ptr;

public:
   array_map_iterator(array_type ptr, const size_type index) {
      this->index = index;
      this->ptr = ptr;
   }

   array_map_iterator(const array_map_iterator< Key, Data > & cp) {
      index = cp.index;
      ptr = cp.ptr;
   }

   array_map_iterator() {
      index = 0; 
      ptr = 0;
   }

   ~array_map_iterator() {
   }

   size_type get_index() const { 
      return index; 
   }

   size_type get_index() { 
      return index; 
   }

   array_map_iterator< Key, Data > & operator++() {
      index++;
      return *this;
   }

   array_map_iterator< Key, Data > & operator--() {
      index--;
      return *this;
   }

   array_map_node< Key, Data > * operator*() {
      return ptr[index];
   }

   bool operator==(const array_map_iterator< Key, Data > & right) {
      bool ret = right.index == index;
      return ret;
   }

   bool operator!=(const array_map_iterator< Key, Data > & right) {
      bool ret = right.index != index;
      return ret;
   }

   array_map_iterator< Key, Data > & operator=(const array_map_iterator< Key, Data > & arg) {
      ptr = arg.ptr;
      index = arg.index;
      return *this;
   }

   array_map_node< Key, Data > * operator->() {
      return ptr[index];
   }
};

template< class Key, class Data >
class array_map {
public:
   typedef array_map_iterator< Key, Data > iterator;
   typedef int size_type;

private:
   array_map_node< Key, Data > ** array;
   size_type array_size;
   Data nil;

public:
   array_map() { 
      array = 0;
      array_size = 0;
   }

   virtual ~array_map() { 
      clear();
   }

   void clear() { 
      for(size_type i = 0; i < array_size; i++) {
         delete array[i];
      } 
      delete [] array;
      array = 0;
      array_size = 0;
   }

   iterator end() {
      return array_map_iterator< Key, Data >(array, array_size);
   }

   iterator begin() {
      return array_map_iterator< Key, Data >(array, 0);
   }

   size_type size() { return this->array_size; }

   iterator binarySearch(size_type left, 
                         size_type right, 
                         const Key & key) {
      if(left > right) {
         return end();
      }

      int middle = (left + right) / 2;

      if(array[middle]->key == key) {
         return iterator(array, middle);
      }
      else if(array[middle]->key > key) {
         return binarySearch(left, middle - 1, key);
      }
      else {
         return binarySearch(middle + 1, right, key);
      }

      return iterator(array,array_size);
   }

   Data & operator[](const Key & key) {
      array_map_node< Key, Data > * ptr;
      if(array_size == 0) {
         array_size = 1;
         array = new array_map_node< Key, Data > * [array_size];
         array[0] = new array_map_node< Key, Data >(key, nil);
         ptr = array[0];
      }
      else {
         iterator p = binarySearch(0, array_size-1, key);
         if(p == end()) {
            array_size++;
            array_map_node< Key, Data > ** temp = new array_map_node< Key, Data > * [array_size];
            for(size_type i = 0; i < array_size-1; i++) {
               temp[i] = array[i];
            } 
            temp[array_size-1] = new array_map_node< Key, Data >(key,nil);
            delete [] array;
            array = temp;
            ptr = array[array_size-1];
            array_map_comp< Key, Data > comp;
            sort(array, array+array_size, comp);
         }
         else {
            ptr = (*p);
         }
      }
      return ptr->data;
   }

   iterator find(const Key & key) {
      return binarySearch(0, array_size-1, key);
   }

   array_map< Key, Data > & operator=(const array_map< Key, Data > & right) {
      clear();
      array = new array_map_node< Key, Data > * [right.array_size];
      array_size = right.array_size;
      for(size_t i = 0; i < right.array_size; i++) {
         array[i] = new array_map_node< Key, Data >(right.array[i]->key, right.array[i]->data);
      }
      return *this;
   }

   void erase(iterator ptr) {
      size_type j = 0;
      for(size_type i = 0; i < array_size; i++) {
         if(ptr.index == i) {
            delete array[i];
            array[i] = 0;
            j++;
         }
         array[i] = array[i+j];
      }
      array_size--;
   }
};

}


