/**
	This file is a part of rexy's general purpose library
	Copyright (C) 2022 rexy712

	This program 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.

	This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef REXY_LLIST_HPP
#define REXY_LLIST_HPP

#include <cstddef> //size_t, ptrdiff_t
#include "allocator.hpp"
#include "detail/hasallocator.hpp"
#include "traits.hpp"
#include <iterator> //bidirectional_iterator_tag, reverse_iterator
#include <memory> //allocator_traits
#include <initializer_list>
#include <utility> //pair
#include <type_traits>

namespace rexy{

	template<class T, class Alloc>
	class list;

	namespace detail{
		struct list_node_base{
			list_node_base* next = nullptr;
			list_node_base* prev = nullptr;
		};

		template<class T>
		struct list_iterator;
		template<class T>
		struct const_list_iterator;
		template<class T>
		struct list_node;
	}

	template<class T, class Alloc = rexy::allocator<T>>
	class list : protected detail::hasallocator<typename std::allocator_traits<Alloc>::template rebind_alloc<detail::list_node<T>>>
	{
	private:
		using node_allocator_type = detail::hasallocator<typename std::allocator_traits<Alloc>::template rebind_alloc<detail::list_node<T>>>;

	public:
		using value_type = T;
		using allocator_type = Alloc;
		using size_type = std::size_t;
		using difference_type = std::ptrdiff_t;
		using reference = value_type&;
		using const_reference = const value_type&;
		using pointer = value_type*;
		using const_pointer = const value_type*;
		using iterator = detail::list_iterator<T>;
		using const_iterator = detail::const_list_iterator<T>;
		using reverse_iterator = std::reverse_iterator<iterator>;
		using const_reverse_iterator = std::reverse_iterator<const_iterator>;

	public:
		using node = detail::list_node<T>;

	private:
		detail::list_node_base m_sentinel = {&m_sentinel, &m_sentinel};
		size_type m_size = 0;

	public:
		constexpr list(void)noexcept = default;

		constexpr explicit list(const allocator_type& alloc)noexcept;

		REXY_CPP20_CONSTEXPR
		list(size_type count, const_reference value = value_type(), const allocator_type& = allocator_type())noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		explicit list(size_type count, const allocator_type& alloc = allocator_type())noexcept(
				std::is_nothrow_default_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class InputIt>
		REXY_CPP20_CONSTEXPR
		list(InputIt first, InputIt last, const allocator_type& alloc = allocator_type())noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		list(const list& other, const allocator_type& alloc = allocator_type())noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		list(list&& other, const allocator_type& alloc = allocator_type())noexcept;

		REXY_CPP20_CONSTEXPR
		list(std::initializer_list<value_type> l, const allocator_type& alloc = allocator_type())noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		~list(void)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		list& operator=(const list& other)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		list& operator=(list&& other)noexcept;

		REXY_CPP20_CONSTEXPR
		list& operator=(std::initializer_list<value_type> l)noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
				is_nothrow_allocator_v<node_allocator_type>);

		constexpr bool operator==(const list& other)const noexcept;
#if __cpp_impl_three_way_comparison
		constexpr auto operator<=>(const list& other)const noexcept;
#else
		constexpr bool operator!=(const list& other)const noexcept;
		constexpr bool operator<(const list& other)const noexcept;
		constexpr bool operator<=(const list& other)const noexcept;
		constexpr bool operator>(const list& other)const noexcept;
		constexpr bool operator>=(const list& other)const noexcept;
#endif


		REXY_CPP20_CONSTEXPR
		void assign(size_type count, const_reference value)noexcept(
				std::conditional_t<
					std::is_copy_assignable_v<value_type>,
					std::is_nothrow_copy_assignable<value_type>,
					std::true_type>::value &&
				std::is_nothrow_copy_constructible_v<value_type> &&
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class InputIt>
		REXY_CPP20_CONSTEXPR
		void assign(InputIt first, InputIt last)noexcept(
				std::conditional_t<
					std::is_assignable_v<value_type, decltype(*first)>,
					std::is_nothrow_assignable<value_type, decltype(*first)>,
					std::true_type>::value &&
				std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void assign(std::initializer_list<value_type> l)noexcept(
				std::conditional_t<
					std::is_assignable_v<value_type, decltype(*l.begin())>,
					std::is_nothrow_assignable<value_type, decltype(*l.begin())>,
					std::true_type>::value &&
				std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		constexpr allocator_type get_allocator(void)const noexcept;

		constexpr reference front(void)noexcept;
		constexpr const_reference front(void)const noexcept;
		constexpr reference back(void)noexcept;
		constexpr const_reference back(void)const noexcept;

		constexpr iterator begin(void)noexcept;
		constexpr const_iterator begin(void)const noexcept;
		constexpr const_iterator cbegin(void)const noexcept;
		constexpr iterator end(void)noexcept;
		constexpr const_iterator end(void)const noexcept;
		constexpr const_iterator cend(void)const noexcept;

		constexpr iterator next(iterator i)noexcept;
		constexpr const_iterator next(const_iterator i)noexcept;

		constexpr iterator prev(iterator i)noexcept;
		constexpr const_iterator prev(const_iterator i)noexcept;

		constexpr reverse_iterator rbegin(void)noexcept;
		constexpr const_reverse_iterator rbegin(void)const noexcept;
		constexpr const_reverse_iterator crbegin(void)const noexcept;
		constexpr reverse_iterator rend(void)noexcept;
		constexpr const_reverse_iterator rend(void)const noexcept;
		constexpr const_reverse_iterator crend(void)const noexcept;

		constexpr bool empty(void)const noexcept;
		constexpr size_type size(void)const noexcept;
		constexpr size_type max_size(void)const noexcept;


		REXY_CPP20_CONSTEXPR
		void clear(void)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		iterator insert(const_iterator pos, const_reference value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		iterator insert(const_iterator pos, value_type&& value)noexcept(
				std::is_nothrow_move_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		iterator insert(const_iterator pos, size_type count, const_reference value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class InputIt>
		REXY_CPP20_CONSTEXPR
		iterator insert(const_iterator pos, InputIt first, InputIt last)noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		iterator insert(const_iterator pos, std::initializer_list<value_type> l)noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class... Args>
		REXY_CPP20_CONSTEXPR
		iterator emplace(const_iterator pos, Args&&... args)noexcept(
				std::is_nothrow_constructible_v<value_type, Args&&...> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		iterator erase(const_iterator pos)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		iterator erase(const_iterator first, const_iterator last)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		reference push_back(const_reference value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		reference push_back(value_type&& value)noexcept(
				std::is_nothrow_move_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class... Args>
		REXY_CPP20_CONSTEXPR
		reference emplace_back(Args&&... args)noexcept(
				std::is_nothrow_constructible_v<value_type, Args&&...> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void pop_back(void)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		reference push_front(const_reference value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		reference push_front(value_type&& value)noexcept(
				std::is_nothrow_move_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class... Args>
		REXY_CPP20_CONSTEXPR
		reference emplace_front(Args&&... args)noexcept(
				std::is_nothrow_constructible_v<value_type, Args&&...> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void pop_front(void)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		void resize(size_type count)noexcept(
				std::is_nothrow_default_constructible_v<value_type> &&
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void resize(size_type count, value_type value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);


		REXY_CPP20_CONSTEXPR
		void swap(list& other)noexcept;


		REXY_CPP20_CONSTEXPR
		void merge(list&& other)noexcept;
		template<class Comp>
		REXY_CPP20_CONSTEXPR
		void merge(list&& other, Comp comp)noexcept;


		REXY_CPP20_CONSTEXPR
		void splice(const_iterator pos, list&& other)noexcept;

		REXY_CPP20_CONSTEXPR
		void splice(const_iterator pos, list&& other, const_iterator it)noexcept;

		REXY_CPP20_CONSTEXPR
		void splice(const_iterator pos, list&& other, const_iterator first, const_iterator last)noexcept;


		REXY_CPP20_CONSTEXPR
		size_type remove(const_reference value)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class UnaryPred>
		REXY_CPP20_CONSTEXPR
		size_type remove_if(UnaryPred p)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void reverse(void)noexcept;

		REXY_CPP20_CONSTEXPR
		size_type unique(void)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class BinaryPred>
		REXY_CPP20_CONSTEXPR
		size_type unique(BinaryPred p)noexcept(
				std::is_nothrow_destructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void sort(void)noexcept;

		template<class Comp>
		REXY_CPP20_CONSTEXPR
		void sort(Comp comp)noexcept;


	private:

		template<class InputIt>
		REXY_CPP20_CONSTEXPR
		void iterator_initialize_(InputIt first, InputIt last)noexcept(
				std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void constant_initialize_(size_type count, const_reference value)noexcept(
				std::is_nothrow_copy_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		REXY_CPP20_CONSTEXPR
		void default_initialize_(size_type count)noexcept(
				std::is_nothrow_default_constructible_v<value_type> &&
				is_nothrow_allocator_v<node_allocator_type>);

		template<class Comp>
		static iterator mergesort(iterator first, size_type firstlen, Comp comp)noexcept;
		static std::pair<iterator,size_type> ms_split(iterator it, size_type len)noexcept;

		static void insert_node_(detail::list_node_base* prev, detail::list_node_base* n)noexcept;
		static void remove_node_(detail::list_node_base* rm)noexcept;
		static detail::list_node_base* get_next_then_move_node_(detail::list_node_base* dest, detail::list_node_base* n)noexcept;
	};

}

#include "list.tpp"

#endif