#ifndef _MATT_STL_MAP
#define _MATT_STL_MAP

#include <algorithm>
#include <cstring>
#include <assert.h>
#include <cstdio>

extern "C" {
extern int printf(const char * fmt, ...);
extern size_t get_stack();
}

namespace std {

template< class Key, class Data >
class pair {
public:
   Key first;
   Data second;

   pair() { }
   pair(const pair< Key, Data > & cp) { 
      first = cp.first; 
      second = cp.second; 
   }
   pair(const Key & k) { first = k; }
   pair(const Key & k, const Data & d) { first = k; second = d; }
   ~pair() { }

   pair & operator=(const pair & p) {
      first = p.first;
      second = p.second;
      return *this;
   }
};

template< class Key >
class less {
public:
   bool operator()(const Key & a, const Key & b) const {
      bool ret = a < b;
      return ret;
   }
};

template< class Key, class Data >
class map_iterator {
public:
   typedef pair< Key, Data > pair_type;
   //typedef pair< Key, Data > ** pair_vector_type;

private:
   pair< Key, Data > ** p_vec;
   size_t index;
   size_t size;
   pair_type nil;

public:
   map_iterator() { 
      p_vec = 0; 
      index = 0; 
      size = 0;
   }
   map_iterator(const map_iterator & cp) { 
      p_vec = cp.p_vec; 
      index = cp.index; 
      size = cp.size; 
   }
   map_iterator(pair< Key, Data > ** pv, size_t i, size_t sz) {  
      p_vec = pv; 
      index = i; 
      size = sz; 
   }
   ~map_iterator() { }

   map_iterator & operator++(int) {
      index++;
      return *this;
   }

   pair_type & operator*() {
      if(index == size) {
         //return pair_type();
         return nil;
      }
      pair_type * p;
      p = p_vec[index];
      return *p;
   }

   map_iterator & operator++() {
      index++;
      return *this;
   }

   bool operator==(const map_iterator & right) {
      return index == right.index;
   }

   bool operator!=(const map_iterator & right) {
      bool ret;
      if(index != right.index) 
         ret = true;
      else
         ret = false;
      return ret;
   }

   map_iterator & operator=(const map_iterator & r) {
      p_vec = r.p_vec;
      index = r.index;
      size = r.size;
      return *this;
   }

   pair_type * operator->() {
      if(index >= size)
         return 0;
      return p_vec[index];
   }

   size_t get_index() { return index; }

   void set_index(const size_t index) { this->index = index; }
};

template< class Key, class Data, class Compare /*= less< Key >*/ >
class map {
public:
   typedef pair< Key, Data > pair_type;
   //typedef pair< Key, Data > ** pair_vector_type;
   typedef map_iterator< Key, Data > iterator;

private:
   pair< Key, Data > ** array;
   unsigned int the_size;
   Data nil;

public:
   map() {
      the_size = 0;
      array = new pair_type* [ 1 ];
      array[0] = 0;
   }

   map(const map & cp) {
//printf("map::map(cp)\n");
      the_size = cp.the_size;
      array = new pair_type* [the_size];
//printf("array == %d\n");
      for(size_t i = 0; i < the_size; i++) {
         array[i] = new pair_type(*cp.array[i]);
      }
   }

   ~map() {
//printf("map::~map()\n");
      for(size_t i = 0; i < the_size; i++) {
         delete array[i];
      }
      delete [] array;
      the_size = 0;
   }

   iterator begin() {
      iterator ret(array, 0, the_size);
      return ret;
   }

   iterator  end() {
      iterator ret(array, the_size, the_size);
      return ret;
   }

   map & operator=(const map & right) {
      if(array == right.array) {
         return *this;
      }
      size_t i;
      for(i = 0; i < the_size; i++) {
         delete array[i];
      }
      delete [] array;
      the_size = right.the_size;
      array = new pair_type* [the_size];
      for(i = 0; i < the_size; i++) {
         array[i] = new pair_type(*(right.array[i]));
      }
      return *this;
   }

// BUG
   Data & operator[](const Key & key) {
      int found = 0;
      int i;
      Compare comp;
      for(i = 0; i < the_size; i++) {
         if(!comp(key, array[i]->first) && !comp(array[i]->first, key)) {
            found = 1;
            break;
         }
      }
      if(!found) {
         the_size++;
         pair< Key, Data > ** temp;
         temp = array;
         array = new pair< Key, Data> *[the_size];
         for(i = 0; i < the_size-1; i++) {
            array[i] = temp[i];
         }
         delete [] temp;
         Data d = 0;
         array[the_size-1] = new pair< Key, Data >(key, d);
         i = the_size-1;
      }
      return array[i]->second;
   }

   iterator find(const Key & key) {
      Compare comp;
      for(size_t i = 0; i < the_size; i++) {
         if(!comp(key, array[i]->first) && !comp(array[i]->first, key)) {
            iterator it(array, i, the_size);
            return it;
         }
      }
      return end();
   }

   unsigned int size() {
      return the_size;
   }

   void clear() {
      if(the_size) {
         for(unsigned int i = 0; i < the_size; i++)
            delete array[i];
         delete [] array;
         the_size = 0;
         array = new pair_type* [ 1 ];
         array[0] = 0;
      }
   }

   void erase(iterator & it) {
      assert(the_size != 0);
      size_t i;
      delete array[it.get_index()];
      array[it.get_index()] = 0;
      for(i = it.get_index(); i < the_size-1; i++) {
         array[i] =  array[i+1];
      }
      the_size--;
      array[the_size] = 0;
   }
};

}

#endif /* _MATT_STL_MAP */
