#include <iostream>
#include <stdlib.h>
using namespace std;

// if true we use the unordered_map (hash table) for the mapping 
// from Coord to int otherwise use map (binary tree)
#define HASH_TABLE false


// 2 dimensional coordinate
class Coord
{
public:
    int x,y;

    Coord(int x,int y)
        : x(x),y(y)
    {}
};

// Coord stream operator, for printing
std::ostream& operator<< (std::ostream &os, const Coord &c)
{
    os<<"("<<c.x<<","<<c.y<<")";
    return os;
}

// Coord addition operator
Coord operator+ (const Coord& c1, const Coord &c2)
{ return Coord(c1.x+c2.x,c1.y+c2.y); }

// Coord equality operator, needed by CoordMap
bool operator== (const Coord& c1, const Coord &c2)
{ return (c1.x==c2.x && c1.y==c2.y); }


#if HASH_TABLE // use hash table
  
    #include <boost/unordered_map.hpp>
    // Coord hash function, needed by CoordMap
    size_t hash_value(const Coord& c)
    { 
        size_t x=c.x;
        size_t y=c.y;
        y<<=sizeof(size_t)*8/2; // bit shift to left half of the bits of size_t 
        // so that different coords have different hash values
        return x^y; // xor bit operator
    }
    typedef boost::unordered_map<Coord, int> CoordMap; // defines the map type used

#else // use binary tree

    #include <map>
    // Coord less than operator, needed by CoordMap
    bool operator< (const Coord& c1, const Coord &c2)
    { 
        return (c1.y<c2.y || 
                (c1.y==c2.y && c1.x<c2.x) ); 
    }
    typedef map<Coord, int> CoordMap; // defines the map type used

#endif


// CoordMap stream operator, for printing 
std::ostream& operator<< (std::ostream &os, const CoordMap &m)
{
    for (CoordMap::const_iterator it=m.begin();it!=m.end();it++)
        os<<it->first<<"=>"<<it->second<<", ";
    return os;
}

int main() // demonstrates all needed map functionality
{
    CoordMap coordMap; // the map

    cout<<"add some items (a coord that maps to an int):"<<endl;
    for (int y=0;y<3;y++)
    {
        Coord c(0,y);
        for (int x=0;x<3;x++)
        {
            int random=rand()%10;// random number in range 0 through 9
            cout<<"Coord "<<c<<" maps to "<<random<<endl;
            coordMap[c]=random; // add to the map
            c=c+Coord(1,0); // demonstrates use of addition operator
        }
    }

    cout<<"erase Coord(1,1), just as a test"<<endl;
    coordMap.erase(Coord(1,1));

    cout<<"print the map"<<endl;
    cout<<"coordMap: "<<coordMap<<endl;

    cout<<"print the mapping of some coords or 'not found' when the Coord is not known by the map:"<<endl;
    for (int y=0;y<6;y++)
    {
        Coord c(1,y);
        cout<<"search "<<c<<": ";
        CoordMap::iterator find=coordMap.find(c); // search the map for Coord c
        if (find==coordMap.end()) // test if c is found
            cout<<"not found"<<endl;
        else
            cout<<find->second<<endl;
    }
    
    cout<<"loop over all items in the map:"<<endl;
    for (CoordMap::const_iterator it=coordMap.begin();it!=coordMap.end();it++)
    {
        Coord c=it->first;
        int i=it->second;
        cout<<c<<" maps to "<<i<<endl;
    }

}