/*
	This file is part of Fennix Kernel.

	Fennix Kernel is free software: you can redistribute it and/or
	modify it under the terms of the GNU General Public License as
	published by the Free Software Foundation, either version 3 of
	the License, or (at your option) any later version.

	Fennix Kernel is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Fennix Kernel. If not, see <https://www.gnu.org/licenses/>.
*/

#pragma once

#include <initializer_list>
#include <algorithm>
#include <assert.h>
#include <lock.hpp>
#include <iterator>
#include <utility>
#include <memory>

namespace std
{
	template <class T, class Allocator = std::allocator<T>>
	class list
	{
	public:
		using value_type = T;
		using allocator_type = Allocator;
		using size_type = std::size_t;
		using difference_type = std::ptrdiff_t;
		using reference = value_type &;
		using const_reference = const value_type &;
		using pointer = typename std::allocator_traits<Allocator>::pointer;
		using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
		// using iterator = typename list<T, Allocator>::iterator;
		// using const_iterator = typename list<T, Allocator>::const_iterator;
		// using reverse_iterator = typename list<T, Allocator>::reverse_iterator;
		// using const_reverse_iterator = typename list<T, Allocator>::const_reverse_iterator;

	private:
		spin_lock lock;
		Allocator alloc;

		struct node
		{
			value_type value;
			node *prev;
			node *next;

			node(const_reference v, node *p = nullptr, node *n = nullptr)
				: value(v), prev(p), next(n) {}
		};

		node *head = nullptr;
		node *tail = nullptr;
		std::atomic_size_t lSize = 0;

	public:
		class iterator
		{
		private:
			node *_node;
			friend class list;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = T;
			using pointer = typename std::allocator_traits<Allocator>::pointer;
			using reference = value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

			iterator(node *p = nullptr) : _node(p) {}

			T &operator*() const { return _node->value; }
			T *operator->() const { return &_node->value; }

			iterator &operator++()
			{
				if (_node)
					_node = _node->next;
				return *this;
			}

			iterator &operator--()
			{
				if (_node)
					_node = _node->prev;
				return *this;
			}

			iterator operator++(int)
			{
				iterator tmp = *this;
				++*this;
				return tmp;
			}

			iterator operator--(int)
			{
				iterator tmp = *this;
				--*this;
				return tmp;
			}

			bool operator==(const iterator &rhs) const { return _node == rhs._node; }
			bool operator!=(const iterator &rhs) const { return _node != rhs._node; }
		};

		class const_iterator
		{
		private:
			node *_node;
			friend class list;

		public:
			using difference_type = std::ptrdiff_t;
			using value_type = T;
			using pointer = typename std::allocator_traits<Allocator>::const_pointer;
			using reference = const value_type &;
			using iterator_category = std::bidirectional_iterator_tag;

			const_iterator(iterator it) : _node(it._node) {}
			const_iterator(node *p = nullptr) : _node(p) {}
			const T &operator*() const { return _node->value; }
			const T *operator->() const { return &_node->value; }

			const_iterator &operator++()
			{
				if (_node)
					_node = _node->next;
				return *this;
			}

			const_iterator &operator--()
			{
				if (_node)
					_node = _node->prev;
				return *this;
			}

			const_iterator operator++(int)
			{
				const_iterator it = *this;
				++*this;
				return it;
			}

			const_iterator operator--(int)
			{
				const_iterator it = *this;
				--*this;
				return it;
			}

			bool operator==(const const_iterator &rhs) const { return _node == rhs._node; }
			bool operator!=(const const_iterator &rhs) const { return _node != rhs._node; }
		};

#pragma region Member Functions

		list()
		{
		}

		explicit list(const Allocator &alloc)
			: alloc(alloc)
		{
		}

		list(size_type count, const T &value,
			 const Allocator &alloc = Allocator())
		{
			for (size_t i = 0; i < count; ++i)
				push_back(value);
		}

		explicit list(size_type count, const Allocator &alloc = Allocator())
		{
			for (size_t i = 0; i < count; ++i)
				push_back(T());
		}

		template <class InputIt>
		list(InputIt first, InputIt last, const Allocator &alloc = Allocator())
		{
			for (InputIt it = first; it != last; ++it)
				push_back(*it);
		}

		list(const list &other)
		{
			*this = other;
		}

		list(const list &other, const Allocator &alloc)
		{
			*this = other;
		}

		list(list &&other)
		{
			*this = std::move(other);
		}

		list(list &&other, const Allocator &alloc)
		{
			*this = std::move(other);
		}

		list(std::initializer_list<T> init, const Allocator &alloc = Allocator())
		{
			foreach (const_reference value in init)
				push_back(value);
		}

		~list() { clear(); }

		list &operator=(const list &other)
		{
			if (this == &other)
				return *this;

			for (const_reference value : other)
				push_back(value);

			return *this;
		}

		list &operator=(list &&other)
		{
			if (this == &other)
				return *this;

			clear();
			head = other.head;
			tail = other.tail;
			lSize.store(other.lSize.load());
			other.head = other.tail = nullptr;
			other.lSize.store(0);
			return *this;
		}

		list &operator=(std::initializer_list<T> ilist)
		{
			clear();
			foreach (const_reference value in ilist)
				push_back(value);
			return *this;
		}

		void assign(size_type count, const T &value)
		{
			clear();
			for (size_t i = 0; i < count; ++i)
				push_back(value);
		}

		template <class InputIt>
		void assign(InputIt first, InputIt last)
		{
			clear();
			for (InputIt it = first; it != last; ++it)
				push_back(*it);
		}

		void assign(std::initializer_list<T> ilist)
		{
			clear();
			foreach (const_reference value in ilist)
				push_back(value);
		}

		allocator_type get_allocator() const
		{
			return alloc;
		}

#pragma endregion Member Functions

#pragma region Element Access

		reference front()
		{
			sl_guard(this->lock);
			return head->value;
		}

		const_reference front() const
		{
			sl_guard(this->lock);
			return head->value;
		}

		reference back()
		{
			sl_guard(this->lock);
			return tail->value;
		}

		const_reference back() const
		{
			sl_guard(this->lock);
			return tail->value;
		}

#pragma endregion Element Access

#pragma region Iterators

		iterator begin()
		{
			return iterator(head);
		}

		const_iterator begin() const
		{
			return const_iterator(head);
		}

		const_iterator cbegin() const
		{
			return const_iterator(head);
		}

		iterator end()
		{
			return iterator(nullptr);
		}

		const_iterator end() const
		{
			return const_iterator(nullptr);
		}

		const_iterator cend() const
		{
			return const_iterator(nullptr);
		}

		/* FIXME: rbegin, rend, crbegin, crend */

#pragma endregion Iterators

#pragma region Capacity

		[[nodiscard]] bool empty() const
		{
			return lSize.load() == 0; /*  or begin() == end() ? */
		}

		size_type size() const
		{
			return lSize.load();
		}

		size_type max_size() const
		{
			return std::numeric_limits<difference_type>::max();
		}

#pragma endregion Capacity

#pragma region Modifiers

		void clear()
		{
			while (!empty())
				pop_back();
		}

		iterator insert(const_iterator pos, const T &value)
		{
			if (pos == end())
			{
				push_back(value);
				return iterator(tail);
			}
			else if (pos == begin())
			{
				push_front(value);
				return iterator(head);
			}
			else
			{
				sl_guard(this->lock);
				node *p = pos._node;
				node *nNode = new node(value, p->prev, p);
				p->prev->next = nNode;
				p->prev = nNode;
				lSize.fetch_add(1);
				return iterator(nNode);
			}
		}

		iterator insert(const_iterator pos, T &&value)
		{
			if (pos == end())
			{
				push_back(value);
				return iterator(tail);
			}
			else if (pos == begin())
			{
				push_front(value);
				return iterator(head);
			}
			else
			{
				sl_guard(this->lock);
				node *p = pos._node;
				node *nNode = new node(std::move(value), p->prev, p);
				p->prev->next = nNode;
				p->prev = nNode;
				lSize.fetch_add(1);
				return iterator(nNode);
			}
		}

		iterator insert(const_iterator pos, size_type count, const T &value)
		{
			iterator ret;
			for (size_t i = 0; i < count; ++i)
				ret = insert(pos, value);
			return ret;
		}

		template <class InputIt>
		iterator insert(const_iterator pos, InputIt first, InputIt last)
		{
			iterator ret;
			for (InputIt it = first; it != last; ++it)
				ret = insert(pos, *it);
			return ret;
		}

		iterator insert(const_iterator pos, std::initializer_list<T> ilist)
		{
			iterator ret;
			foreach (const_reference value in ilist)
				ret = insert(pos, value);
			return ret;
		}

		template <class... Args>
		iterator emplace(const_iterator pos, Args &&...args)
		{
			return insert(pos, T(std::forward<Args>(args)...));
		}

		iterator erase(const_iterator pos)
		{
			if (pos == cend())
				return end();
			else if (pos == cbegin())
			{
				pop_front();
				return begin();
			}
			else
			{
				sl_guard(this->lock);
				node *p = pos._node;
				if (p->prev)
					p->prev->next = p->next;

				if (p->next)
					p->next->prev = p->prev;

				if (head == p)
					head = p->next;

				if (tail == p)
					tail = p->prev;

				iterator ret(p->next);
				delete p;
				lSize.fetch_sub(1);
				return ret;
			}
		}

		iterator erase(const_iterator first, const_iterator last)
		{
			iterator ret;
			while (first != last)
				ret = erase(first++);
			return ret;
		}

		void push_back(const T &value)
		{
			sl_guard(this->lock);

			node *nNode = new node(value, tail);
			if (empty())
				head = tail = nNode;
			else
			{
				tail->next = nNode;
				tail = nNode;
			}
			lSize.fetch_add(1);
		}

		void push_back(T &&value)
		{
			sl_guard(this->lock);

			node *nNode = new node(std::move(value), tail);
			if (empty())
				head = tail = nNode;
			else
			{
				tail->next = nNode;
				tail = nNode;
			}
			lSize.fetch_add(1);
		}

		template <class... Args>
		void emplace_back(Args &&...args)
		{
			assert(sizeof...(args) > 0);

			sl_guard(this->lock);

			node *nNode = new node(T(std::forward<Args>(args)...), tail);
			if (this->empty())
				head = tail = nNode;
			else
			{
				tail->next = nNode;
				tail = nNode;
			}
			lSize.fetch_add(1);
		}

		template <class... Args>
		reference emplace_back(Args &&...args)
		{
			assert(sizeof...(args) > 0);

			sl_guard(this->lock);

			node *nNode = new node(T(std::forward<Args>(args)...), tail);
			if (this->empty())
				head = tail = nNode;
			else
			{
				tail->next = nNode;
				tail = nNode;
			}
			lSize.fetch_add(1);
			return tail->value;
		}

		void pop_back()
		{
			sl_guard(this->lock);

			if (unlikely(empty()))
				assert(!"list is empty");
			else if (head == tail)
			{
				delete tail;
				head = tail = nullptr;
				lSize.fetch_sub(1);
			}
			else
			{
				node *oldTail = tail;
				tail = tail->prev;
				tail->next = nullptr;
				delete oldTail;
				lSize.fetch_sub(1);
			}
		}

		void push_front(const T &value)
		{
			sl_guard(this->lock);

			node *nNode = new node(value, nullptr, head);
			if (empty())
				head = tail = nNode;
			else
			{
				head->prev = nNode;
				head = nNode;
			}
			lSize.fetch_add(1);
		}

		void push_front(T &&value)
		{
			sl_guard(this->lock);

			node *nNode = new node(std::move(value), nullptr, head);
			if (empty())
				head = tail = nNode;
			else
			{
				head->prev = nNode;
				head = nNode;
			}
			lSize.fetch_add(1);
		}

		template <class... Args>
		void emplace_front(Args &&...args)
		{
			assert(sizeof...(args) > 0);

			sl_guard(this->lock);

			node *nNode = new node(T(std::forward<Args>(args)...), nullptr, head);
			if (this->empty())
				head = tail = nNode;
			else
			{
				head->prev = nNode;
				head = nNode;
			}
			lSize.fetch_add(1);
		}

		template <class... Args>
		reference emplace_front(Args &&...args)
		{
			assert(sizeof...(args) > 0);

			sl_guard(this->lock);

			node *nNode = new node(T(std::forward<Args>(args)...), nullptr, head);
			if (this->empty())
				head = tail = nNode;
			else
			{
				head->prev = nNode;
				head = nNode;
			}
			lSize.fetch_add(1);
			return head->value;
		}

		void pop_front()
		{
			if (unlikely(empty()))
			{
				assert(!"list is empty");
			}

			if (head == tail)
			{
				sl_guard(this->lock);
				delete head;
				head = tail = nullptr;
				lSize.fetch_sub(1);
			}
			else
			{
				sl_guard(this->lock);
				node *old_head = head;
				head = head->next;
				head->prev = nullptr;
				delete old_head;
				lSize.fetch_sub(1);
			}
		}

		void resize(size_type count)
		{
			if (count < lSize.load())
			{
				while (lSize.load() > count)
					pop_back();
			}
			else if (count > lSize.load())
			{
				while (lSize.load() < count)
					push_back(T());
			}
		}

		void resize(size_type count, const value_type &value)
		{
			if (count < lSize.load())
			{
				while (lSize.load() > count)
					pop_back();
			}
			else if (count > lSize.load())
			{
				while (lSize.load() < count)
					push_back(value);
			}
		}

		void swap(list &other)
		{
			sl_guard(this->lock);
			other.lock.lock("list::swap");

			std::swap(head, other.head);
			std::swap(tail, other.tail);

			size_t oSize = other.lSize.load();
			other.lSize.store(lSize.load());
			lSize.store(oSize);

			other.lock.unlock();
		}

#pragma endregion Modifiers

#pragma region Operations

		void merge(list &other)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				push_back(fr);
				other.pop_front();
			}
		}

		void merge(list &&other)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				push_back(fr);
				other.pop_front();
			}
		}

		template <class Compare>
		void merge(list &other, Compare comp)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				if (comp(tail->value, fr))
					push_back(fr);
				else
					push_front(fr);
				other.pop_front();
			}
		}

		template <class Compare>
		void merge(list &&other, Compare comp)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				if (comp(tail->value, fr))
					push_back(fr);
				else
					push_front(fr);
				other.pop_front();
			}
		}

		void splice(const_iterator pos, list &other)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				insert(pos, fr);
				other.pop_front();
			}
		}

		void splice(const_iterator pos, list &&other)
		{
			while (other.empty() == false)
			{
				T &fr = other.front();
				insert(pos, fr);
				other.pop_front();
			}
		}

		void splice(const_iterator pos, list &other, const_iterator it)
		{
			insert(pos, *it);
			other.erase(it);
		}

		void splice(const_iterator pos, list &&other, const_iterator it)
		{
			insert(pos, *it);
			other.erase(it);
		}

		void splice(const_iterator pos, list &other, const_iterator first, const_iterator last)
		{
			while (first != last)
			{
				insert(pos, *first);
				other.erase(first++);
			}
		}

		void splice(const_iterator pos, list &&other, const_iterator first, const_iterator last)
		{
			while (first != last)
			{
				insert(pos, *first);
				other.erase(first++);
			}
		}

		size_type remove(const T &value)
		{
			sl_guard(this->lock);
			node *p = head;
			size_type count = 0;
			while (p != nullptr)
			{
				if (p->value == value)
				{
					if (p->prev)
						p->prev->next = p->next;
					if (p->next)
						p->next->prev = p->prev;
					if (p == head)
						head = p->next;
					if (p == tail)
						tail = p->prev;
					delete p;
					lSize.fetch_sub(1);
					++count;
				}
				p = p->next;
			}
			return count;
		}

		template <class UnaryPredicate>
		size_type remove_if(UnaryPredicate p)
		{
			sl_guard(this->lock);
			node *n = head;
			size_type count = 0;
			while (n != nullptr)
			{
				if (p(n->value))
				{
					if (n->prev)
						n->prev->next = n->next;
					if (n->next)
						n->next->prev = n->prev;
					if (n == head)
						head = n->next;
					if (n == tail)
						tail = n->prev;
					delete n;
					lSize.fetch_sub(1);
					++count;
				}
				n = n->next;
			}
			return count;
		}

		void reverse()
		{
			if (empty())
				return;

			sl_guard(this->lock);
			node *p = head;
			while (p != nullptr)
			{
				node *tmp = p->next;
				p->next = p->prev;
				p->prev = tmp;
				p = tmp;
			}
			node *tmp = head;
			head = tail;
			tail = tmp;
		}

		size_type unique()
		{
			sl_guard(this->lock);
			node *p = head;
			size_type count = 0;
			while (p != nullptr)
			{
				node *n = p->next;
				while (n != nullptr)
				{
					if (p->value == n->value)
					{
						if (n->prev)
							n->prev->next = n->next;
						if (n->next)
							n->next->prev = n->prev;
						if (n == head)
							head = n->next;
						if (n == tail)
							tail = n->prev;
						delete n;
						lSize.fetch_sub(1);
						++count;
					}
					n = n->next;
				}
				p = p->next;
			}
			return count;
		}

		template <class BinaryPredicate>
		size_type unique(BinaryPredicate p)
		{
			sl_guard(this->lock);
			node *n = head;
			size_type count = 0;
			while (n != nullptr)
			{
				node *m = n->next;
				while (m != nullptr)
				{
					if (p(n->value, m->value))
					{
						if (m->prev)
							m->prev->next = m->next;
						if (m->next)
							m->next->prev = m->prev;
						if (m == head)
							head = m->next;
						if (m == tail)
							tail = m->prev;
						delete m;
						lSize.fetch_sub(1);
						++count;
					}
					m = m->next;
				}
				n = n->next;
			}
			return count;
		}

		void sort()
		{
			if (empty())
				return;

			sl_guard(this->lock);
			bool swapped = true;
			while (swapped)
			{
				swapped = false;
				node *p = head;
				while (p->next != nullptr)
				{
					if (p->value > p->next->value)
					{
						T tmp = p->value;
						p->value = p->next->value;
						p->next->value = tmp;
						swapped = true;
					}
					p = p->next;
				}
			}
		}

		template <class Compare>
		void sort(Compare comp)
		{
			if (empty())
				return;

			sl_guard(this->lock);
			bool swapped = true;
			while (swapped)
			{
				swapped = false;
				node *p = head;
				while (p->next != nullptr)
				{
					if (comp(p->value, p->next->value))
					{
						T tmp = p->value;
						p->value = p->next->value;
						p->next->value = tmp;
						swapped = true;
					}
					p = p->next;
				}
			}
		}

#pragma endregion Operations
	};

	template <class T, class Alloc>
	bool operator==(const std::list<T, Alloc> &lhs, const std::list<T, Alloc> &rhs)
	{
		if (lhs.size() != rhs.size())
			return false;
		auto it1 = lhs.begin();
		auto it2 = rhs.begin();
		while (it1 != lhs.end())
		{
			if (*it1 != *it2)
				return false;
			++it1;
			++it2;
		}
		return true;
	}
}