#ifndef MAP_H_
#define MAP_H_

#include <iostream>
#include "pair.h"

namespace mtm {

// exception definitions
class MappingDoesntExist : public std::exception {
public:
    virtual const char* what() const throw() {
        return "Mapping for key was not found!\n";
    }
};
class MappingAlreadyExists : public std::exception {
public:
    virtual const char* what() const throw() {
        return "Key already exists";
    }
};


template <class KeyType, class DataType>
class Map {
private:

    //Node
    template <class S, class T>
    class Node {

    public:
        const S key;
        T data;
        Node<S, T>* next;

        //C'tor
        Node(const KeyType& sKey, const DataType& sData) :
            key(sKey), data(sData), next(NULL) {
        }

        //Copy C'tor
        Node(const Node<S, T>& sNode):
            key(sNode.key), data(sNode.data), next(NULL) {
        }

        friend class map;
        friend class iterator;
        friend class const_iterator;
    };
    //End of Node

    //Map structure
    Node<KeyType, DataType>* head;
    Node<KeyType, DataType>* tail;
    int mSize;
    //End of Map stracture

public:

    /*
    Class declarations
    */
    class iterator;
    class const_iterator;


    //Beginning of iterator
    class iterator {
    private:
        Node<KeyType, DataType>* current;
        Map<KeyType, DataType>* map;

    public:

        //C'tor
        iterator() :
            current(NULL), map(NULL) {}

        iterator(Map<KeyType, DataType>* mapPtr, Node<KeyType, DataType>* nodePtr):
            current(nodePtr), map(mapPtr) {}

        iterator(Map<KeyType, DataType>::const_iterator& sIterator):
            current(sIterator.current), map(sIterator.map) {
        }


        iterator& operator=(const iterator& sIterator);
        iterator& operator++();
        iterator operator++(int);
        bool operator==(const iterator& sIterator) const;
        bool operator!=(const iterator& sIterator) const;
        const Pair<KeyType,DataType> operator*() const;
        const KeyType& getKey() const;
        DataType& getData();

        friend class Map;
    };
    //End of iterator


    //Beginning of const_iterator
    class const_iterator {
    private:
        Node<KeyType, DataType>* current;
        const Map<KeyType, DataType>* map;

    public:

        //C'tor
        const_iterator() :
            current(NULL), map(NULL) {}

        const_iterator(const Map<KeyType, DataType>* mapPtr, Node<KeyType, DataType>* nodePtr):
            current(nodePtr), map(mapPtr) {}

        const_iterator(const Map<KeyType, DataType>::const_iterator& sIterator):
            current(sIterator.current), map(sIterator.map) {}

        const_iterator(const Map<KeyType, DataType>::iterator& sIterator):
            current(sIterator.current), map(sIterator.map) {}


        const_iterator& operator=(const const_iterator& sIterator);
        const_iterator& operator++();
        const_iterator operator++(int);
        bool operator==(const const_iterator& sIterator) const;
        bool operator!=(const const_iterator& sIterator) const;
        const Pair<KeyType,DataType> operator*() const;
        const KeyType& getKey() const;
        const DataType& getData() const;


        friend class Map;
    };
    //End of const_iterator


    //C`tor
    Map() : head(NULL), tail(NULL), mSize(0) {}

    //D`tor
    ~Map() {
        while (head != NULL)
        {
            Node<KeyType, DataType>* tempNode = head;
            head = head->next;
            delete(tempNode);
        }
        mSize = 0;
    }

    //Copy C'tor
    Map(const Map<KeyType, DataType>& sMap) : head(NULL), tail(NULL), mSize(0) {
        for(Map::const_iterator it = sMap.begin(); it != sMap.end(); it++ ){
            insert(it.getKey(), it.getData());
        }

    }

    Map::const_iterator begin() const;
    Map::const_iterator end() const;
    Map::iterator begin();
    Map::iterator end();
    void insert(const KeyType& key, const DataType& data);
    bool isIn(const KeyType& key) const;
    void remove(const KeyType key);
    void clear();
    bool isEmpty();
    int size() const;
    const DataType& operator[](const KeyType key) const;
    DataType& operator[](const KeyType key);

};

/*
Map methods and operators
*/
template<class S, class T>
typename Map<S,T>::const_iterator Map<S,T>::begin() const {
    Map::const_iterator iterator;
    iterator.current = head;
    iterator.map = this;
    return iterator;
}

template<class S, class T>
typename Map<S,T>::const_iterator Map<S, T>::end() const {
    return Map<S,T>::const_iterator();
}

template <class S, class T>
typename Map<S,T>::iterator Map<S, T>::begin() {
    Map::iterator iterator;
    iterator.current = head;
    iterator.map = this;
    return iterator;
}

template <class S, class T>
typename Map<S,T>::iterator Map<S, T>::end() {
    return Map<S,T>::iterator();
}

template <class S, class T>
void Map<S,T>::insert(const S& key, const T& data) {
    Node<S,T>* newNode = new Node<S,T>(key, data);
    if (mSize == 0){
        head = newNode;
        tail = newNode;
        mSize++;
        return;
    }

    if (isIn(key)){
        throw MappingAlreadyExists();
        return;
    }

    tail->next = newNode;
    tail = newNode;
    mSize++;
    return;
}

template <class S, class T>
bool Map<S,T>::isIn(const S& key) const {
    Map<S,T>::const_iterator it = begin();
    while (it != end()){
        if (it.current->key == key){
            return true;
        }
        it++;
    }
    return false;
}

template <class S, class T>
void Map<S,T>::remove(const S key) {
    Node<S,T>* nodeToRemove;

    //If the node to be removed is the first one.
    if (head->key == key){
        nodeToRemove = head;
        head = head->next;
        delete(nodeToRemove);
        mSize--;
        return;
    }

    //Find a node and remove it.
    Node<S,T>* currentNode = head;
    Node<S,T>* nextNode;
    while (currentNode != NULL)
    {
        nextNode = currentNode->next;
        if (nextNode != NULL && nextNode->key == key)
        {
            nodeToRemove = nextNode;
            currentNode->next = nodeToRemove->next;
            delete(nodeToRemove);
            mSize--;
            return;
        }

        currentNode = currentNode->next;
    }

    throw MappingDoesntExist();
    return;
}

template <class S, class T>
void Map<S,T>::clear() {
    Node<S,T>* tempNode;
    while(head != NULL){
        tempNode = head;
        head=head->next;
        delete (tempNode);
    }
    mSize = 0;
}

template <class S, class T>
bool Map<S,T>::isEmpty() {
    return (mSize == 0);
}

template <class S, class T>
int Map<S,T>::size() const {
    return mSize;
}

template <class S, class T>
const T& Map<S,T>::operator[](const S key) const {
    for (Map::const_iterator it = begin(); it != end(); ++it){
        if (it.current->key == key){
            return it.current->data;
        }
    }
    throw MappingDoesntExist();
}

template <class S, class T>
T& Map<S,T>::operator[](const S key) {
    for (Map::iterator it = begin(); it != end(); ++it){
        if (it.current->key == key){
            return it.current->data;
        }
    }
    throw MappingDoesntExist();
}
/* End of Map methods and operators */


/* iterator methods and operators */
template <class S, class T>
typename Map<S,T>::iterator& Map<S,T>::iterator::operator=(const Map<S,T>::iterator& sIterator) {
    current = sIterator.current;
    map = sIterator.map;
}

template <class S, class T>
typename Map<S,T>::iterator& Map<S,T>::iterator::operator++() {
    current = current->next;
    return *this;
}

template <class S, class T>
typename Map<S,T>::iterator Map<S,T>::iterator::operator++(int) {
    Map<S,T>::iterator tmpIt(*this);
    current = current->next;
    return tmpIt;
}

template <class S, class T>
bool Map<S,T>::iterator::operator==(const Map<S,T>::iterator& sIterator) const {
    return (current == sIterator.current);
}

template <class S, class T>
bool Map<S,T>::iterator::operator!=(const Map<S,T>::iterator& sIterator) const {
    return !(*this == sIterator);
}

template <class S, class T>
const Pair<S, T> Map<S,T>::iterator::operator*() const {
    return Pair<S,T>(current->key, current->data);
}

template <class S, class T>
const S& Map<S,T>::iterator::getKey() const {
    return current->key;
}

template <class S, class T>
T& Map<S,T>::iterator::getData() {
    return current->data;
}


/* End of iterator methods and operators */


/* iterator methods and operators */
template <class S, class T>
typename Map<S,T>::const_iterator& Map<S,T>::const_iterator::operator=(const Map<S,T>::const_iterator& sIterator) {
    current = sIterator.current;
    map = sIterator.map;
}

template <class S, class T>
typename Map<S,T>::const_iterator& Map<S,T>::const_iterator::operator++() {
    current = current->next;
    return *this;
}

template <class S, class T>
typename Map<S,T>::const_iterator Map<S,T>::const_iterator::operator++(int) {
    Map<S,T>::const_iterator tmpIt(*this);
    current = current->next;
    return tmpIt;
}

template <class S, class T>
bool Map<S,T>::const_iterator::operator==(const Map<S,T>::const_iterator& sIterator) const {
    return (current == sIterator.current);
}

template <class S, class T>
bool Map<S,T>::const_iterator::operator!=(const Map<S,T>::const_iterator& sIterator) const {
    return !(*this == sIterator);
}

template <class S, class T>
const Pair<S, T> Map<S,T>::const_iterator::operator*() const {
    return Pair<S,T>(current->key, current->data);
}

template <class S, class T>
const S& Map<S,T>::const_iterator::getKey() const {
    return current->key;
}

template <class S, class T>
const T& Map<S,T>::const_iterator::getData() const {
    return current->data;
}

/* End of const_iterator methods and operators */


template<class T, class V, class Predicate, class Action>
void MapIf(Map<T,V>& map, Predicate predicate, Action action){
    for (typename Map<T, V>::iterator it = map.begin(); it != map.end(); it++){
        if (predicate(it.getKey())){
            action(it.getData());
        }
    }
}


} /* End of mtm namespace */

#endif /* MAP_H_ */