/*!
	@file
	@brief 侵入型単方向連結リストコンテナ

	特徴
	- 要素はコピー可能でなくても構わない。
	- 内部でメモリ確保操作をしない。
	- ポインタのリストより少しだけメモリ効率がいい。

	- intrusive_slist_nodeを継承しなければならない。
	- 要素自体は別の安定した場所で確保しなければならない。

	@author Juna
*/

#ifndef Juna_Intrusive_Singly_Linked_List_Hpp
#define Juna_Intrusive_Singly_Linked_List_Hpp

#include <stddef.h>
#include <iterator>
#include <assert.h>


//!	namespace Juna
namespace Juna {

//!	リスト要素の侵入部分の基礎部分
/*!
*/
class base_intrusive_slist_node
{
protected:
//!	デフォルトコンストラクタ
/*!
	@post linked() == false
*/
	base_intrusive_slist_node(void) {next = this;}
//!	デストラクタ
/*!
	@pre assert(linked() == false)
*/
	~base_intrusive_slist_node()
	{
		assert(!linked());
	}
//!	リストに繋がっているかどうか
/*!
	@retval true 繋がっている
	@retval false 繋がっていない
*/
	bool linked(void) const {return next != this;}

private:
//	privateメンバアクセスクラス
friend class base_intrusive_slist;
//	次の要素へのポインタ
	base_intrusive_slist_node *next;
private:
	base_intrusive_slist_node(base_intrusive_slist_node &);
	void operator=(base_intrusive_slist_node &);
};

//!	リスト要素の侵入部分
/*!
	これを継承することでリストの要素となることができる。
	テンプレート引数は、要素が複数のリストに登録される場合に利用する。
*/
template<int TagNumber>
class intrusive_slist_node_ : public base_intrusive_slist_node {};

//!	リスト要素の侵入部分
/*!
	単一の要素のための別名
*/
typedef intrusive_slist_node_<0> intrusive_slist_node;


/*===========================================================================*/


//	侵入型単方向リストの共通部分
class base_intrusive_slist
{
protected:
	typedef base_intrusive_slist_node islist_node;
	typedef size_t size_type;

	base_intrusive_slist(void) : header() {header.next = 0;}
	~base_intrusive_slist() {header.next = &header;}

	void clear(void) {while (header.next != 0) erase_after(&header);}

	static islist_node *insert_after(islist_node *pos,islist_node *ins)
	{
		assert(!ins->linked());
		ins->next = pos->next;
		pos->next = ins;
		return ins;
	}
	static islist_node *erase_after(islist_node *pos)
	{
		islist_node *erase = pos->next;
		pos->next = erase->next;
		erase->next = erase;
		return pos->next;
	}
	static void splice_after(islist_node *pos,islist_node &head);
	static void splice_after(islist_node *pos,islist_node *prev);
	static void splice_after(islist_node *pos,islist_node *before_first,islist_node *before_last);


	size_type size(void) const
	{
		size_type count = 0;
		for (const islist_node *ln = header.next;ln != 0;ln = ln->next)
			count++;
		return count;
	}
	bool empty(void) const {return !header.linked();}

	islist_node *prev(islist_node *pos)
	{
		islist_node *r;
		for (r = &header;r->next != pos;r = r->next) ;
		return r;
	}
	const islist_node *prev(const islist_node *pos) const
	{
		const islist_node *r;
		for (r = &header;r->next != pos;r = r->next)
			;
		return r;
	}

	static islist_node *next(const islist_node *node) {return node->next;}

	static void swap(islist_node &head1,islist_node &head2)
	{
		islist_node *tmp = head1.next;
		head1.next = head2.next;
		head2.next = tmp;
	}

	class list_header : public base_intrusive_slist_node
	{
	public:
		list_header(void) : base_intrusive_slist_node() {}
		~list_header() {}
	};
	list_header header;

private:
	base_intrusive_slist(base_intrusive_slist &);
	void operator=(base_intrusive_slist &);
};


inline void base_intrusive_slist::splice_after(
	islist_node *pos,islist_node &head)
{
	if (pos->next != 0)
	{
		if (head.next == 0)
			return;
		islist_node *n;
		for (n = head.next;n->next != 0;n = n->next)
			;
		n->next = pos->next;
	}
	pos->next = head.next;
	head.next = 0;
}
inline void base_intrusive_slist::splice_after(
	islist_node *pos,islist_node *prev)
{
	assert(prev->next != pos);
	islist_node *s = prev->next;
	prev->next = s->next;
	s->next = pos->next;
	pos->next = s;
}
inline void base_intrusive_slist::splice_after(
	islist_node *pos,
	islist_node *before_first,islist_node *before_last)
{
	assert(before_first != before_last);
	islist_node *last = before_last->next;
	before_last->next = pos->next;
	pos->next = before_first->next;
	before_first->next = last;
}


template<int TagNumber>
class base_intrusive_slist_ : public base_intrusive_slist
{
protected:
	typedef base_intrusive_slist base_class;
	typedef intrusive_slist_node_<TagNumber> islist_node;


	static islist_node *insert_after(islist_node *pos,islist_node *ins)
		{return static_cast<islist_node *>(base_class::insert_after(pos,ins));}
	static islist_node *erase_after(islist_node *pos)
		{return static_cast<islist_node *>(base_class::erase_after(pos));}
	static void splice_after(islist_node *pos,islist_node &head)
		{base_class::splice_after(pos,head);}
	static void splice_after(islist_node *pos,islist_node *prev)
		{base_class::splice_after(pos,prev);}
	static void splice_after(islist_node *pos,islist_node *before_first,islist_node *before_last)
		{base_class::splice_after(pos,before_first,before_last);}

	islist_node *prev(islist_node *pos)
		{return static_cast<islist_node *>(base_class::prev(pos));}
	const islist_node *prev(const islist_node *pos) const
		{return static_cast<const islist_node *>(base_class::prev(pos));}

	static islist_node *next(const islist_node *pos)
		{return static_cast<islist_node *>(base_class::next(pos));}

	static void swap(islist_node &head1,islist_node &head2)
		{base_class::swap(head1,head2);}

};

/*===========================================================================*/

//!	マージソート
template <int sort_stack_size,class IntrusiveSListT,class BinaryPredicate>
void intrusive_slist_sort(IntrusiveSListT &list,BinaryPredicate less);

//!	マージ
template <class IntrusiveSListT,class BinaryPredicate>
void intrusive_slist_merge(IntrusiveSListT &list,IntrusiveSListT &other,BinaryPredicate less);

/*===========================================================================*/

//!	侵入型単方向リストクラステンプレート
/*!
	@sa intrusive_slist.hpp
*/
template<class DerivedNode,int TagNumber = 0>
class intrusive_slist : private base_intrusive_slist_<TagNumber>
{
	typedef base_intrusive_slist_<TagNumber> base_class;
	typedef DerivedNode			node_type;
	typedef DerivedNode *		pointer;
	typedef const DerivedNode *	const_pointer;
	typedef DerivedNode &		reference;
	typedef const DerivedNode &	const_reference;

//	イテレータクラステンプレート
	template<class T>
	class base_iterator
	{
	public:
		typedef std::forward_iterator_tag iterator_category;
		typedef T value_type;
		typedef T *pointer;
		typedef T &reference;
		typedef ptrdiff_t difference_type;
		typedef ptrdiff_t distance_type;
	private:
		friend class intrusive_slist<node_type,TagNumber>;
		base_iterator(pointer p) : node(p) {}
	public:
		base_iterator(void) : node(0) {}
		template<class U>
		base_iterator(base_iterator<U> &i) : node(i.get()) {}

		reference operator*(void) const {return *node; }
		pointer operator->(void) const {return node; }

		base_iterator operator++(void) {increment();return *this;}
		base_iterator operator++(int) {base_iterator r = *this;increment();return r;}

		template<class U>
		bool operator==(const base_iterator<U> &rhs) const {return node == rhs.get();}
		template<class U>
		bool operator!=(const base_iterator<U> &rhs) const {return node != rhs.get();}

		pointer get(void) const {return node;}
	private:
		void increment(void) {node = next(node);}
		pointer node;
	};
//	nodeポインタ操作権を与える
	friend class base_iterator<node_type>;
	friend class base_iterator<const node_type>;

//	便利関数
	static pointer next(const islist_node *node) {return static_cast<pointer>(base_class::next(node));}
	static pointer cast(islist_node *node) {return static_cast<pointer>(node);}
	static const_pointer cast(const islist_node *node) {return static_cast<const_pointer>(node);}

	islist_node &header(void) {return static_cast<islist_node &>(static_cast<base_intrusive_slist_node &>(base_class::header));}
	const islist_node &header(void) const {return static_cast<const islist_node &>(static_cast<const base_intrusive_slist_node &>(base_class::header));}

public:
//!	イテレータ (forward_iterator)
	typedef base_iterator<node_type> iterator;
//!	コンストイテレータ (forward_iterator)
	typedef base_iterator<const node_type> const_iterator;

//!	デフォルトコンストラクタ
/*!	これ以外にコンストラクタは無い */
	intrusive_slist(void) : base_intrusive_slist_<TagNumber>() {}
//!	デストラクタ
/*!	clear()を呼ぶ */
	~intrusive_slist() {clear();}

//!	@name 全要素排除
//@{
//!	全要素排除
/*!	このリストの全要素をリストから排除する。*/
	void clear(void) {base_class::clear();}
//@}

//!	@name 要素数
//@{
//!	要素数
/*!	いちいちリストをたどって数えます。 */
	size_type size(void) const {return base_class::size();}
//!	リストが空かどうか
/*!	size()より速い size() == 0 */
	bool empty(void) const {return base_class::empty();}
//@}

//!	@name 先頭要素参照
//@{
//!	先頭要素参照
/*! @pre empty() == false */
	reference front(void) {return *next(&header());}
//!	先頭要素コンスト参照
/*! @pre empty() == false */
	const_reference front(void) const {return *next(&header());}
//@}

//!	@name スタック操作
//@{
//!	push
/*!
	リストの先頭にinsを挿入する。
	@pre assert(ins.linked() == false)
*/
	void push_front(reference ins) {base_class::insert_after(&header(),&ins);}
//!	pop
/*!
	先頭要素を排除する。
	@pre empty() == false
*/
	void pop_front(void) {base_class::erase_after(&header());}
//@}


//!	@name イテレータ
//@{
//!	先頭イテレータ
	iterator begin(void) {return next(&header());}
//!	先頭コンストイテレータ
	const_iterator begin(void) const {return next(&header());}
//!	終端イテレータ
	iterator end(void) {return (0);}
//!	終端コンストイテレータ
	const_iterator end(void) const {return (0);}

//! 先頭の前イテレータ
/*!
	_after系をbeginの要素にも適応したい用
*/
	iterator begin_before(void) {return cast(&header());}

//!	直前のイテレータ
/*!	++prev == pos がtrueとなるprevの取得 */
	iterator previous(iterator pos)
		{return cast(base_class::prev(pos.get()));}
//!	直前のコンストイテレータ
/*!	++prev == pos がtrueとなるprevの取得 */
	const_iterator previous(const_iterator pos) const
		{return cast(base_class::prev(pos.get()));}
//@}


//!	@name 挿入
//@{
//!	要素の挿入
/*!
	posの位置にinsを挿入する。
	@return 挿入した要素を指すイテレータ
	@pre assert(ins.linked() == false)
*/
	iterator insert(iterator pos,reference ins)
		{return insert_after(previous(pos),ins);}
//!	要素の挿入
/*!
	posの次の位置にinsを挿入する。
	@return 挿入した要素を指すイテレータ
	@pre assert(ins.linked() == false)
*/
	iterator insert_after(iterator pos,reference ins)
		{return cast(base_class::insert_after(pos.get(),&ins));}
//@}

//!	@name 排除
//@{
//!	要素の排除
/*!
	posの要素をリストから排除する。
	@return 削除した要素の次の要素を指すイテレータ
*/
	iterator erase(iterator pos)
		{return erase_after(previous(pos));}
//!	要素の排除
/*!
	posの次の要素をリストから排除する。
	@return 削除した要素の次の要素を指すイテレータ
*/
	iterator erase_after(iterator pos)
		{return cast(base_class::erase_after(pos.get()));}
//@}


//!	@name 要素の繋ぎ替え
//@{
//!	要素の繋ぎ替え
/*!
	lの全要素をposの位置に繋ぎ替える。lは空になる。
*/
	void splice(iterator pos,intrusive_slist &l)
		{splice_after(previous(pos),l);}
//!	要素の繋ぎ替え
/*!
	lのiの要素をposの位置に繋ぎ替える。
	@note lは呼び出したインスタンス自身でも構わない。
	@pre assert(pos != ++i)
	@pre i == pos は正しく処理される。
*/
	void splice(iterator pos,intrusive_slist &l,iterator i)
		{splice_after(previous(pos),l.previous(i));}
//!	要素の繋ぎ替え
/*!
	lの[first-last)の範囲にある要素をposの位置に繋ぎ替える。
	@note lは呼び出したインスタンス自身でも構わない。
	@pre assert(first == last)
	@pre first-last間にposがあってはならない。
*/
	void splice(iterator pos,intrusive_slist &l,
				iterator first,iterator last)
		{splice_after(previous(pos),l.previous(first),l.previous(last));}

//!	要素の繋ぎ替え
/*!
	lの全要素をposの次の位置に繋ぎ替える。lは空になる。
*/
	void splice_after(iterator pos,intrusive_slist &l)
		{base_class::splice_after(pos.get(),l.header());}
//!	要素の繋ぎ替え
/*!
	prevの次の要素をposの次の位置に挿入する。
	@pre assert(pos != ++prev)
	@pre prev == pos は正しく処理される。
*/
	void splice_after(iterator pos,iterator prev)
		{base_class::splice_after(pos.get(),prev.get());}
//!	要素の繋ぎ替え
/*!
	(berofer_first-berofer_last]の範囲にある要素をposの次の位置に繋ぎ替える。
	@pre assert(berofer_first != berofer_last)
	@pre berofer_first-berofer_last間にposがあってはならない。
*/
	void splice_after(iterator pos,
					  iterator before_first,iterator before_last)
	{
		base_class::splice_after(pos.get(),before_first.get(),before_last.get());
	}
//@}

//!	@name アルゴリズム
//@{
//!	リスト間の要素の全交換
/*!	lと要素を全て交換する */
	void swap(intrusive_slist &l) {base_class::swap(header(),l.header());}

//!	マージ
/*!
	otherの全要素を取り入れる。otherは空になる。\n
	自身、other共にlessでソートされていればlessでソートした順列で格納される。\n
	そうでなければ格納される順列は不定。
	@param other マージして空になるリスト
	@param less 要素比較述語関数オブジェクト
*/
	template <class BinaryPredicate>
	void merge(intrusive_slist &other,BinaryPredicate less)
		{intrusive_slist_merge(*this,other,less);}

//!	マージソート
/*!
	要素をlessで比較した結果によって並び替える。
	@pre assert(size() <= (2^16 * 2))\n
		実際にはsize()を呼ぶわけではなく、
		処理した数が限界に達した時点でassert(false)となる。
	@param less 要素比較述語関数オブジェクト
*/
	template <class BinaryPredicate>
	void sort(BinaryPredicate less)
		{intrusive_slist_sort<16>(*this,less);}

//	これだけのために#include <functional>も何なので
	struct less
	{bool operator()(const_reference lhs,const_reference rhs) const {return lhs < rhs;}};

//!	マージ
/*!
	otherの全要素を取り入れる。otherは空になる。\n
	自身、other共にソートされていればソートした順列で格納される。\n
	そうでなければ格納される順列は不定。
	@param other マージして空になるリスト
*/
	void merge(intrusive_slist &other) {merge(other,less());}

//!	マージソート
/*!
	要素を<演算子で比較した結果によって並び替える。
	@pre assert(size() <= (2^16 * 2))\n
		実際にはsize()を呼ぶわけではなく、
		処理した数が限界に達した時点でassert(false)となる。
*/
	void sort(void) {sort(less());}
//!	要素を逆順に並べ替える
	void reverse(void)
	{
		if (empty()) return;
		for (iterator it = begin();next(it.get()) != 0;splice_after(begin_before(),it))
			;
	}
//!	一致する要素を排除する
/*!	x == val がtrueとなる要素xをerase()する。 */
	void remove(const_reference val)
	{
		for (iterator it = begin();it != end();)
			if (*it == val)
				it = erase(it);
			else
				++it;
	}
//!	条件に一致する要素を排除する
/*!	test(x) がtrueとなる要素xをerase()する。 */
	template <class UnaryPredicate>
	void remove_if(UnaryPredicate test)
	{
		for (iterator it = begin();it != end();)
			if (test(*it))
				it = erase(it);
			else
				++it;
	}
//@}

//	void unique(void);
//	template <class BinaryPredicate>
//	void unique(BinaryPredicate equal);



//operator==()とか使うか？

//! @name ソート済み操作
//@{
//!	ソート済み挿入
/*!
	lessでソートされていれば、insもソートされた位置に挿入される。\n
	そうでなければ挿入される位置は不定。
	@return 挿入した要素を指すイテレータ
	@pre assert(ins.linked() == false)
*/
	template <class BinaryPredicate>
	iterator insert(reference ins,BinaryPredicate less)
	{
		iterator i = begin_before();
		for (;next(i.get()) != 0 && !less(ins,*next(i.get()));++i)
			;
		return insert_after(i,ins);
	}
//!	ソート済み繋ぎ替え
/*!
	lessでソートされていれば、iもソートされた位置に繋ぎ替えられる。\n
	そうでなければ繋ぎ替えられる位置は不定。
	@pre assert(ins.linked() == false)
	@post iは繋ぎ替えられた後の要素を指している。
*/
	template <class BinaryPredicate>
	void splice(iterator i,BinaryPredicate less)
	{
		iterator it = begin_before();
		for (;next(it.get()) != 0 && !less(*i,*next(it.get()));++it)
			;
		splice_after(it,i);
	}
//!	ソート済み挿入
/*!
	ソートされていれば、insもソートされた位置に挿入される。\n
	そうでなければ挿入される位置は不定。
	@return 挿入した要素を指すイテレータ
	@pre assert(ins.linked() == false)
*/
	iterator insert(reference ins) {return insert(ins,less());}
//!	ソート済み繋ぎ替え
/*!
	ソートされていれば、iもソートされた位置に繋ぎ替えられる。\n
	そうでなければ繋ぎ替えられる位置は不定。
	@pre assert(ins.linked() == false)
	@post iは繋ぎ替えられた後の要素を指している。
*/
	void splice(iterator i) {return splice(i,less());}
//@}

};

//!	リスト間の要素の全交換
/*!	l1とl2の要素を全て交換する */
template<class T,int N>
void swap(intrusive_slist<T,N> &l1,intrusive_slist<T,N> &l2) {l1.swap(l2);}


/*!
	otherの全要素をlistに取り入れる。otherは空になる。\n
	list,other共にlessでソートされていればlessでソートした順列で格納される。\n
	そうでなければ格納される順列は不定。
	@param list マージして結果を格納するリスト
	@param other マージして空になるリスト
	@param less 要素比較述語関数オブジェクト
*/
template <class IntrusiveSListT,class BinaryPredicate>
void intrusive_slist_merge(IntrusiveSListT &list,IntrusiveSListT &other,BinaryPredicate less)
{
	assert(&list != &other);
	if (list.empty() || other.empty())
	{
		list.splice_after(list.begin_before(),other);
		return;
	}
	for (IntrusiveSListT::iterator pos = list.begin_before();;)
	{
		IntrusiveSListT::iterator next = pos;++next;
		if (less(other.front(),*next))
		{
			list.splice_after(pos,other.begin_before());
			if (other.empty())
				break;
		}
		else
		{
			IntrusiveSListT::iterator nn = next;++nn;
			if (nn == list.end())
			{
				list.splice_after(next,other);
				break;
			}
		}
	}
}

/*!
	要素をlessで比較した結果によって並び替える。\n
	テンプレート引数でソート用スタックサイズを指定できる
	@pre assert(size() <= (2^sort_stack_size * 2))
		実際にはsize()を呼ぶわけではなく、
		処理した数が限界に達した時点でassert(false)となる。

	@param sort_stack_size スタックサイズ

	@param list ソートするリスト
	@param less 要素比較述語関数オブジェクト
*/
template <int sort_stack_size,class IntrusiveSListT,class BinaryPredicate>
void intrusive_slist_sort(IntrusiveSListT &list,BinaryPredicate less)
{
	IntrusiveSListT stack[sort_stack_size];	//作業領域
	int m_count[sort_stack_size] = {0};		//マージ回数

	int n = 0;
	while (!list.empty())
	{
		list.splice_after(stack[n].begin_before(),list.begin_before());
		if (!list.empty())
		{
			if (less(list.front(),stack[n].front()))
				list.splice_after(stack[n].begin_before(),list.begin_before());
			else
				list.splice_after(stack[n].begin(),list.begin_before());
		}
		m_count[n] = 1;

		int i;
		for (i = n;i > 0;i--)
		{
			if (m_count[i] != m_count[i-1])
				break;
			stack[i-1].merge(stack[i],less);
			m_count[i-1] += m_count[i];
		}
		n = i+1;
//	スタックオーバーフローすると死
		assert(n < sort_stack_size);
	}
//	for (int i = 0;i < n;i++)
//		merge(stack[i],less);
	for (int i = n-1;i > 0;i--)
		stack[i-1].merge(stack[i],less);
	list.splice_after(list.begin_before(),stack[0]);
}

}//namespace Juna


#endif