ifndef SASS_ORDERED_MAP_H define SASS_ORDERED_MAP_H

namespace Sass {

// ##########################################################################
// Very simple and limited container for insert ordered hash map.
// Piggy-back implementation on std::unordered_map and sass::vector
// ##########################################################################
template<
  class Key,
  class T,
  class Hash = std::hash<Key>,
  class KeyEqual = std::equal_to<Key>,
  class Allocator = std::allocator<std::pair<const Key, T>>
>
class ordered_map {

private:

  using map_type = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>;
  using map_iterator = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>::iterator;
  using map_const_iterator = typename std::unordered_map< Key, T, Hash, KeyEqual, Allocator>::const_iterator;

  // The main unordered map
  map_type _map;

  // Keep insertion order
  sass::vector<Key> _keys;
  sass::vector<T> _values;

  const KeyEqual _keyEqual;

public:

  ordered_map() :
    _keyEqual(KeyEqual())
  {
  }

  ordered_map& operator= (const ordered_map& other) {
    _map = other._map;
    _keys = other._keys;
    _values = other._values;
    return *this;
  }

  std::pair<Key, T> front() {
    return std::make_pair(
      _keys.front(),
      _values.front()
    );
  }

  bool empty() const {
    return _keys.empty();
  }

  void insert(const Key& key, const T& val) {
    if (!hasKey(key)) {
      _values.push_back(val);
      _keys.push_back(key);
    }
    _map[key] = val;
  }

  bool hasKey(const Key& key) const {
    return _map.find(key) != _map.end();
  }

  bool erase(const Key& key) {
    _map.erase(key);
    // find the position in the array
    for (size_t i = 0; i < _keys.size(); i += 1) {
      if (_keyEqual(key, _keys[i])) {
        _keys.erase(_keys.begin() + i);
        _values.erase(_values.begin() + i);
        return true;
      }
    }
    return false;
  }

  const sass::vector<Key>& keys() const { return _keys; }
  const sass::vector<T>& values() const { return _values; }

  const T& get(const Key& key) {
    if (hasKey(key)) {
      return _map[key];
    }
    throw std::runtime_error("Key does not exist");
  }

  using iterator = typename sass::vector<Key>::iterator;
  using const_iterator = typename sass::vector<Key>::const_iterator;
  using reverse_iterator = typename sass::vector<Key>::reverse_iterator;
  using const_reverse_iterator = typename sass::vector<Key>::const_reverse_iterator;

  typename sass::vector<Key>::iterator end() { return _keys.end(); }
  typename sass::vector<Key>::iterator begin() { return _keys.begin(); }
  typename sass::vector<Key>::reverse_iterator rend() { return _keys.rend(); }
  typename sass::vector<Key>::reverse_iterator rbegin() { return _keys.rbegin(); }
  typename sass::vector<Key>::const_iterator end() const { return _keys.end(); }
  typename sass::vector<Key>::const_iterator begin() const { return _keys.begin(); }
  typename sass::vector<Key>::const_reverse_iterator rend() const { return _keys.rend(); }
  typename sass::vector<Key>::const_reverse_iterator rbegin() const { return _keys.rbegin(); }

};

}

endif