#pragma once

#include <assert.h>
#include "list_node.h"

namespace JTL // Jack's template library
{
	template <typename T>
	class List
	{
	private:
		int _size;
		ListNodePosi(T) header;
		ListNodePosi(T) trailer;

	protected:
		void init();
		int clear();
		void copy_nodes(ListNodePosi(T), int);
		void merge(ListNodePosi(T)&, int, List<T>&, ListNodePosi(T), int);
		void merge_sort(ListNodePosi(T)&, int);
		void selection_sort(ListNodePosi(T), int);
		void insertion_sort(ListNodePosi(T), int);

	public:
		// Constructor
		List() { init(); }
		List(List<T> const& L);
		List(List<T> const& L, Rank r, int n);
		List(ListNodePosi(T) p, int n);

		// Destructor
		~List();

		// Read only
		Rank size() const { return _size; }
		bool empty() const { return _size <= 0; }
		ListNodePosi(T) first() const { return header->succ; }
		ListNodePosi(T) last() const { return trailer->pred; }
		bool valid(ListNodePosi(T) p) const { return p && p != header && p != trailer; }
		T& operator[] (Rank r) const;
		int disordered() const;
		ListNodePosi(T) find(T const& e) const { return find(e, _size, trailer); }
		ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p) const;
		ListNodePosi(T) search(T const& e) const { return search(e, _size, trailer); }
		ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const;
		ListNodePosi(T) select_max() { return selectMax(header->succ, _size); }
		ListNodePosi(T) select_max(ListNodePosi(T) p, int n);

		// Writable
		ListNodePosi(T) insert_as_first(T const& e);
		ListNodePosi(T) insert_as_last(T const& e);
		ListNodePosi(T) insert_after(ListNodePosi(T) p, T const& e);
		ListNodePosi(T) insert_before(ListNodePosi(T) p, T const& e);
		T remove(ListNodePosi(T) p);
		void merge(List<T>& L) { merge(first(), _size, L, L.first(), L._size); }
		void sort(ListNodePosi(T) p, int n);
		void sort() { sort(first(), _size); }
		int deduplicate();	// unsorted
		int uniquify();		// sorted
	};
};

#include "list_implementation.h"