/***************************************************************
Steven Gallagher
BasicSymbolTable.hpp
Program 2
Provides implementation for SymbolTable.hpp.
***************************************************************/

#ifndef BASIC_SYMBOL_TABLE_H
#define BASIC_SYMBOL_TABLE_H

#include <algorithm>
#include <deque>
#include <iostream>
#include "SymbolTable.hpp"

template <typename Key, typename Value>
class BasicSymbolTable : public SymbolTable<Key, Value>
{
  protected:

    struct NodePair
    {
        Key _key;
        Value _value;

        NodePair(const Key& key = Key{}, const Value& value = Value{}) : _key{ key }, _value{ value } {}
    };

    // The container of the <key, value> pairs
    std::deque<NodePair> _pairs;

    // Key value comparison (less than)
    bool keyLessThan(const NodePair& lhs, const NodePair& rhs) const { return lhs._key < rhs._key; }
    bool keyLessThan(const Key& lhs, const Key& rhs) const { return lhs < rhs; }

    // Equality of key values
    bool keyEquals(const NodePair& lhs, const NodePair& rhs) const { return lhs._key == rhs._key; }
    bool keyEquals(const Key& lhs, const Key& rhs) const { return lhs == rhs; }

    // Equality of key values
    bool keyLessThanOrEquals(const NodePair& lhs, const NodePair& rhs) const
    {
        return keyEquals(lhs, rhs) || keyLessThan(lhs, rhs);
    }
    bool keyLessThanOrEquals(const Key& lhs, const Key& rhs) const
    {
        return keyEquals(lhs, rhs) || keyLessThan(lhs, rhs);
    }

  public:

	BasicSymbolTable() {};
	virtual ~BasicSymbolTable() { clear(); };

	//insert a key,value NodePair into the Symbol Table
	 void put(const Key& key, const Value& val = Value{}) {
        NodePair pairToPut(key, val);
        if(!empty() && key <= _pairs.back()._key) {
            for(auto itr = _pairs.begin(); itr != _pairs.end(); ++itr) {
                if(keyLessThanOrEquals(key,itr -> _key)) {
                    //overwrite value if key exsist
                    if(keyEquals(key,itr->_key)) itr->_value = val;
                    else _pairs.insert(itr,pairToPut);
                    break;

                }
            }
        }
        else _pairs.push_back(pairToPut);
    }



    // acquire the value paired with key
    bool get(const Key& key, Value& val = Value{}) const {
		if (empty()) return false;
        for(NodePair pair : _pairs) {
			if (keyLessThan(key, pair._key)) break;
            if(keyEquals(pair._key,key)) {
                val = pair._value;
                return true;
            }
        }
		return false;
    }

    // Number of key-value pairs.
    int size() const { return _pairs.size(); }

    // Is the table empty?
    bool empty() const { return size()==0; }

    // Removes all elements from the table
    void clear() { _pairs.clear(); }

    // remove key (and its value) from table
    void remove(const Key& key) {
		if (!empty()) {
			for (auto itr = _pairs.begin(); itr != _pairs.end(); ++itr) {
				if (keyLessThan(key, itr->_key)) break;
				if (keyEquals(itr->_key, key)) {
					_pairs.erase(itr);
					break;
				}
			}
		}
    }

    // Is there a value paired with key?
    bool contains(const Key& key) const {
        if(empty()) return false;
		for (NodePair pair : _pairs) {
			if (keyLessThan(key, pair._key)) break;
			if (keyEquals(pair._key, key)) return true;
		}
		return false;
    }

	//return smallest key
    bool min(Key& key = Key{}) const {
        if(empty()) return false;
        key = _pairs.front()._key;
        return true;
    }

	//return largest key
    bool max(Key& key = Key{}) const {
        if(empty()) return false;
        key = _pairs.back()._key;
        return true;
    }

    // Largest key less than or equal to key
    bool floor(const Key& key, Key& floorKey) const {
        if(empty()) return false;
		for (auto itr = _pairs.end()-1; itr != _pairs.begin(); --itr) {
			if (keyLessThanOrEquals(itr->_key, key)) {
				floorKey = itr -> _key;
				return true;
			}
		}
		//compare key against first NodePair in _pairs
		if (keyLessThanOrEquals(_pairs.front()._key, key)) {
			floorKey = _pairs.front()._key;
			return true;
		}
		//if there is no key less than or equal to the key
		return false;
    }

    // Smallest key greater than or equal to key
    bool ceiling(const Key& key, Key& ceilingKey) const {
		if (empty()) return false;
		for (NodePair pair : _pairs) {
			if (keyLessThanOrEquals(key,pair._key)) {
				ceilingKey = pair._key;
				return true;
			}
		}
		//if there is no key greater than or equal to the key
		return false;
    }

    // Number of keys less than key
    int rank(const Key& key) const {
        int count = 0;
		for (NodePair pair : _pairs) {
			if (keyLessThan(pair._key, key)) count++;
			else break;
		}
        return count;
    }

    // Delete the smallest key
    bool deleteMin() {
        if(empty()) return false;
        remove(_pairs.front()._key);
        return true;
    }

    // Delete the largest key
    bool deleteMax() {
        if(empty()) return false;
        remove(_pairs.back()._key);
        return true;
    }

    // all keys in the table, in sorted order
    std::vector<Key> keys() const {
        std::vector<Key> result;
        for(NodePair pair : _pairs)
            result.push_back(pair._key);
        return result;
    }

    // number of keys in [low, high] (including low, high)
    int size(const Key& low, const Key& high) const {
		int count = 0;
		for (NodePair pair : _pairs) {
			if (keyLessThanOrEquals(pair._key, high) && keyLessThanOrEquals(low, pair._key))
				count++;
			else if (keyLessThan(high, pair._key)) break;
		}
		return count;
    }

    //keys in [low, high] (including low, high), in sorted order
    std::vector<Key> keys(const Key& low, const Key& high) const {
		std::vector<Key> result;
		for (NodePair pair : _pairs) {
			if (keyLessThanOrEquals(pair._key, high) && keyLessThanOrEquals(low, pair._key))
				result.push_back(pair._key);
			else if (keyLessThan(high, pair._key)) break;
		}
		return result;
    }

	//key of rank k
    bool select(int k = 0, Key& key = Key{}) const {
        if(empty()) return false;
        key = _pairs.at(k)._key;
        return true;
    }

    //
    ///////////////////////////////////////////////////////////////////////////////
    // Check integrity of the vector data structure.
    ///////////////////////////////////////////////////////////////////////////////
    //
    bool check() const
    {
        bool ordered = isOrdered();
        bool rankConsistent = isRankConsistent();

        if (!ordered)        std::cout << "Not in symmetric order" << std::endl;
        if (!rankConsistent) std::cout << "Ranks inconsistent" << std::endl;

        return ordered && rankConsistent;
    }

  private:
    //
    // does this container satisfy symmetric order?
    //
    bool isOrdered() const
    {
        if (size() <= 1) return true;

        for (unsigned index = 0; index < _pairs.size() - 1; index++)
        {
            if (keyLessThan(_pairs[index + 1], _pairs[index])) return false;
        }
        return true;
    }

    // check that ranks are consistent
    bool isRankConsistent() const
    {
        // The i th node should be rank i
        for (int i = 0; i < size(); i++)
        {
            Key key;
            select(i, key);
            if (i != rank(key)) return false;
        }
        // All keys must equate to the key acquired at its rank
        for (Key key : keys())
        {
            Key acquired;
            select(rank(key), acquired);

            if (!keyEquals(key, acquired)) return false;
        }

        return true;

    }

};

#endif