#ifndef ADS_SET_H
#define ADS_SET_H

#include <functional>
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <cmath>
#include <stdexcept>
#include <vector>

template <typename Key, size_t N = 7>
class ADS_set {
public:
  class Iterator;
  using value_type = Key;
  using key_type = Key;
  using reference = key_type &;
  using const_reference = const key_type &;
  using size_type = size_t;
  using difference_type = std::ptrdiff_t;
  using iterator = Iterator;
  using const_iterator = Iterator;
  using key_compare = std::less<key_type>;   // B+-Tree
  using key_equal = std::equal_to<key_type>; // Hashing
  using hasher = std::hash<key_type>;        // Hashing

private:
  enum class Mode {free, used, freeagain, end};
  struct element {
    key_type key;
    Mode mode {Mode::free};
    element *next {nullptr};
  };
  element *table {nullptr};
  element *last_ptr {nullptr};
  element *keller{nullptr};
  size_type table_size {0}, curr_size {0};
  float max_lf {0.5};
  size_type hash_idx(const key_type &key) const { return hasher{}(key) % static_cast<size_t>(ceil(table_size*max_lf)); }
  void reserve(size_type n);
  void rehash(size_type n);
  element *insert_(const key_type &key);
  element *find_(const key_type &key) const;
public:
  ADS_set() { rehash(N); }
  ADS_set(std::initializer_list<key_type> ilist): ADS_set{} { insert(ilist); }
  template<typename InputIt> ADS_set(InputIt first, InputIt last): ADS_set{} { insert(first,last); }
   ADS_set(const ADS_set &other): ADS_set{} {
    reserve(other.curr_size);
    for (const auto &k: other) {
      insert_(k);
    }
  }

  ~ADS_set() { delete[] table; }


 ADS_set &operator=(const ADS_set &other) {
    if (this == &other) return *this;
    ADS_set tmp{other};
    swap(tmp);
    return *this;
  }
  ADS_set &operator=(std::initializer_list<key_type> ilist) {
    ADS_set tmp{ilist};
    swap(tmp);
    return *this;
  }

  size_type size() const { return curr_size; }
  bool empty() const { return curr_size == 0; }

  size_type count(const key_type &key) const { return !!find_(key); }
  iterator find(const key_type &key) const {
	if (auto p {find_(key)}) return iterator{p};
    return end();
  }

  void clear() {
    ADS_set tmp;
    swap(tmp);
  }
  void swap(ADS_set &other) {
    using std::swap;
    swap(table, other.table);
    swap(curr_size, other.curr_size);
    swap(table_size, other.table_size);
	swap(last_ptr, other.last_ptr);
	swap(keller, other.keller);
    swap(max_lf, other.max_lf);
  }

  void insert(std::initializer_list<key_type> ilist) { insert(std::begin(ilist), std::end(ilist)); }
  std::pair<iterator,bool> insert(const key_type &key) {
    if (auto p {find_(key)}) return {iterator{p},false};
    reserve(curr_size+1);
    return {iterator{insert_(key)},true};
  }

  template<typename InputIt> void insert(InputIt first, InputIt last);


  size_type erase(const key_type &key){
	if(find_(key) == nullptr){
		return 0;
	}

	element* current = table + hash_idx(key);
	element* follow {nullptr};
	element* previous{nullptr};

	//if(current->mode != Mode::used) return 0;

	if(key_equal{}(current->key, key)){
		if(current->next == nullptr) current->mode = Mode::freeagain;
		else{
			follow = current->next;
			current->key = follow->key;
			current->next = follow->next;
			follow->mode = Mode::freeagain;

			if(follow > last_ptr) last_ptr = follow;
		}
		--curr_size;
	}else{
		previous = current;
		current = previous->next;
		follow = current->next;

		while(current != nullptr) {

			if(key_equal{}(current->key, key)) {
				follow = current->next;
				previous->next = follow;
				current->mode = Mode::freeagain;
				break;}

			previous = current;
			current = previous->next;

		}

		if(current > last_ptr) last_ptr = current;
		--curr_size;
	}

	return 1;
}

 const_iterator begin() const { return const_iterator{table}; }
  const_iterator end() const { return const_iterator{table+table_size}; }

  void dump(std::ostream &o = std::cerr) const;

  friend bool operator==(const ADS_set &lhs, const ADS_set &rhs) {
    if (lhs.curr_size != rhs.curr_size) return false;
    for (const auto &k: rhs) if (!lhs.count(k)) return false;
    return true;
  }
  friend bool operator!=(const ADS_set &lhs, const ADS_set &rhs) { return !(lhs == rhs); }


};

template <typename Key, size_t N>
typename ADS_set<Key,N>::element *ADS_set<Key,N>::insert_(const key_type &key) {
	reserve(curr_size + 1);
  size_type idx {hash_idx(key)};

  if(table[idx].mode != Mode::used){
    table[idx].key = key;
    table[idx].mode = Mode::used;
    ++curr_size;

	return table+idx;
  }else {
    element *help = table + idx;
    while(help->next != nullptr) help = help->next;
    help->next = last_ptr;
    last_ptr->key = key;
    last_ptr->mode = Mode::used;
    last_ptr->next = nullptr;
	  help = last_ptr;

	while(last_ptr->mode ==  Mode::used && last_ptr !=  keller) { --last_ptr; }

    ++curr_size;

    return help;
  }
}

template <typename Key, size_t N>
typename ADS_set<Key,N>::element *ADS_set<Key,N>::find_(const key_type &key) const {
		element * help = table + hash_idx(key);

		if(help->mode == Mode::used){
			if(key_equal{}(help->key, key)) return help;

			else{
				while(help != nullptr) {
					if(key_equal{}(help->key, key)) {return help;}
					else help = help->next;
				}
			}
		}
		return nullptr;
}

template <typename Key, size_t N>
template<typename InputIt> void ADS_set<Key,N>::insert(InputIt first, InputIt last) {
  for (auto it {first}; it != last; ++it) {
    if (!count(*it)) {
      reserve(curr_size + 1);
      insert_(*it);
    }
  }
}


template <typename Key, size_t N>
void ADS_set<Key,N>::reserve(size_type n) {
  if(n > table_size * max_lf || last_ptr == keller) {
    size_type new_table_size { table_size};
    do{
      new_table_size = new_table_size * 2 + 1;
    } while(n > new_table_size * max_lf);
    rehash(new_table_size);
  }
}

template <typename Key, size_t N>
void ADS_set<Key,N>::rehash(size_type n) {
  size_type new_table_size {std::max(N, std::max(n,size_type(curr_size / max_lf)))};
  element *new_table {new element[new_table_size+1]};
  new_table[new_table_size].mode = Mode::end;
  size_type old_table_size {table_size};
  element *old_table {table};
  curr_size = 0;
  table = new_table;
  table_size = new_table_size;
  keller = table + static_cast<size_type>(floor(table_size*max_lf));
  last_ptr = table + table_size - 1;
  for (size_type idx{0}; idx < old_table_size; ++idx) {
    if (old_table[idx].mode == Mode::used) insert_(old_table[idx].key);
  }
  delete[] old_table;
}

template <typename Key, size_t N>
void ADS_set<Key,N>::dump(std::ostream &o) const {
  o << "curr_size = " <<  curr_size << " table_size = " << table_size << "\n";
  for(size_type idx{0}; idx < table_size + 1; ++idx) {
    o << idx << " : ";
    switch (table[idx].mode) {
      case Mode::free:
        o << "..free";
        break;
      case Mode::used:
        o << table[idx].key;
        break;
      case Mode::freeagain:
        o << "..freeagain";
        break;
	case Mode::end:
        o << "..END";
        break;

    }
    o << "\n";
  }
}


template <typename Key, size_t N>
class ADS_set<Key,N>::Iterator {
public:
  using value_type = Key;
  using difference_type = std::ptrdiff_t;
  using reference = const value_type &;
  using pointer = const value_type *;
  using iterator_category = std::forward_iterator_tag;

private:
  element *pos;
  void skip() { while (pos->mode != Mode::used && pos->mode != Mode::end) ++pos; }

public:
  explicit Iterator(element *pos = nullptr): pos{pos} { if (pos) skip(); }
  reference operator*() const { return pos->key; }
  pointer operator->() const { return &pos->key; }
  Iterator &operator++() { ++pos; skip(); return *this; }
  Iterator operator++(int) { auto rc {*this}; ++*this; return rc; }
  friend bool operator==(const Iterator &lhs, const Iterator &rhs) { return lhs.pos == rhs.pos; }
  friend bool operator!=(const Iterator &lhs, const Iterator &rhs) { return !(lhs == rhs); }
};

template <typename Key, size_t N> void swap(ADS_set<Key,N> &lhs, ADS_set<Key,N> &rhs) { lhs.swap(rhs); }

#endif // ADS_SET_H