/*
 * Author: Dmitriy Morozov 
 * Department of Computer Science, Duke University, 2006
 */

#ifndef __ORDERLIST_H__
#define __ORDERLIST_H__

#include <iterator>
#include <iostream>
#include <list>
#include "types.h"
//#include "counter.h"

#include <boost/utility.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
//#include <boost/type_traits/is_convertible.hpp>
//#include <boost/utility/enable_if.hpp>


typedef					unsigned int					OrderType;

template<class T> 		struct 	OrderListNode;
template<class T>		class   OrderListIterator;
template<class T>		class   const_OrderListIterator;

/**
 * OrderList stores a list of objects while keeping track of two orders: proper order and consistency order.
 * Consistency order is guaranteed not to change, while proper order is affected by the swap() operation.
 */
template<class T>
class OrderList: std::list<OrderListNode<T> >
{
	public:
		class 			OrderComparison;				
		class 			LessThanComparison;
		class 			GreaterThanComparison;
		class 			ConsistencyComparison;

		/// \name Comparison types
		/// @{
		// Explicit typedefs for Doxygen
		typedef			LessThanComparison							LessThanComparison;
		typedef			GreaterThanComparison						GreaterThanComparison;
		typedef			ConsistencyComparison						ConsistencyComparison;
		/// @}
	
		typedef			OrderListNode<T>							NodeType;
		typedef			OrderList<T>								Self;
		typedef			std::list<NodeType >						Parent;
		
		typedef			T											value_type;
		typedef			T&											reference;
		typedef			const T&									const_reference;
		typedef			OrderListIterator<T>						iterator;
		typedef			const_OrderListIterator<T>					const_iterator;
	
						OrderList()									{}
						~OrderList() 								{ clear(); }
	
		/// \name Order operations
		void			swap(iterator i, iterator j);				///< Exchanges the order of simplices pointed to by i and j

		/// \name Container operations
		/// @{
		// Explicit calls instead of using declarations for Doxygen
		iterator		push_back(const_reference x);
		void			clear()										{ return Parent::clear(); }	
		bool			empty() const								{ return Parent::empty(); }
		SizeType		size()	const								{ return Parent::size(); }
		iterator		begin()										{ return iterator(Parent::begin()); }
		const_iterator	begin() const								{ return const_iterator(Parent::begin()); }
		iterator		end()										{ return iterator(Parent::end()); }
		const_iterator	end() const									{ return const_iterator(Parent::end()); }
		reference		back()										{ return Parent::back(); }
		const_reference	back() const								{ return Parent::back(); }
		void			pop_back()									{ return Parent::pop_back(); }
		                                                			
		iterator		last()										{ return iterator(boost::prior(end())); }
		const_iterator	last() const								{ return const_iterator(boost::prior(end())); }
		/// @}
};

/// Basic comparison that LessThan and GreaterThan derive from
template<class T>
class OrderList<T>::OrderComparison
{
	public:
		typedef			typename OrderList<T>::const_iterator		ComparableType;				

		int 			compare(ComparableType a, ComparableType b) const;				/// (-1,0,1) = a (precedes, ==, succeeds) b 
};

/// Determines if the first element is less than the second one
template<class T>
class OrderList<T>::LessThanComparison: public OrderComparison 
{
	public:
		typedef			OrderComparison								Parent;
		typedef			typename Parent::ComparableType				ComparableType;				
		
		int 			compare(ComparableType a, ComparableType b) const;	
		bool 			operator()(ComparableType a, ComparableType b) const;
};

/// Determines if the first element is greater than the second one
template<class T>
class OrderList<T>::GreaterThanComparison: public OrderComparison 
{
	public:
		typedef			OrderComparison								Parent;
		typedef			typename Parent::ComparableType				ComparableType;				
		
		int 			compare(ComparableType a, ComparableType b) const;
		bool 			operator()(ComparableType a, ComparableType b) const;
};

/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
template<class T>
class OrderList<T>::ConsistencyComparison
{
	public:
		typedef			typename OrderList<T>::const_iterator		ComparableType;				
		
		int 			compare(ComparableType a, ComparableType b) const;				///< (-1,0,1) = a (precedes, ==, succeeds) b 
		bool 			operator()(ComparableType a, ComparableType b) const;		
};

/// Structure storing auxilliary information requred for each node of OrderList
template<class T>
struct OrderListNode
{
	OrderListNode(const T& d, unsigned int orig, unsigned int cur):
		data(d), original(orig), current(cur)
	{}
	
	T 				data;
	OrderType		original;
	OrderType		current;
};

template<class T>
class OrderListIterator: public boost::iterator_adaptor<OrderListIterator<T>,
						 								typename OrderList<T>::Parent::iterator,
						 								T>
{
	private:
		struct			enabler										{};
		
	public:
		typedef			typename OrderList<T>::Parent				OrderListParent;
		typedef 		boost::iterator_adaptor<OrderListIterator<T>,
												typename OrderListParent::iterator,
												T>					Parent;
		typedef			typename Parent::reference					reference;
		typedef			typename Parent::base_type					base_type;

						OrderListIterator()							{}
						OrderListIterator(const typename OrderListParent::iterator& iter):
    						OrderListIterator::iterator_adaptor_(iter)	
						{}
						OrderListIterator(const OrderListIterator<T>& other):
							OrderListIterator::iterator_adaptor_(other.base())			
						{}

	private:
		friend class	boost::iterator_core_access;
		reference		dereference() const							{ return Parent::base_reference()->data; }
		base_type&		get_base()									{ return Parent::base_reference(); }

		friend class 	OrderList<T>;
};

template<class T>
class const_OrderListIterator: public boost::iterator_adaptor<const_OrderListIterator<T>,
						 									  typename OrderList<T>::Parent::const_iterator,
						 									  const T>
{
	private:
		struct			enabler										{};
		
	public:
		typedef			typename OrderList<T>::Parent				OrderListParent;
		typedef 		boost::iterator_adaptor<const_OrderListIterator<T>,
												typename OrderListParent::const_iterator,
												const T>			Parent;
		typedef			typename Parent::reference					reference;
		typedef			typename Parent::base_type					base_type;

						const_OrderListIterator()					{}
						const_OrderListIterator(const typename OrderListParent::const_iterator& iter):
    						const_OrderListIterator::iterator_adaptor_(iter)	
						{}
						const_OrderListIterator(const const_OrderListIterator<T>& other):
							const_OrderListIterator::iterator_adaptor_(other.base())			
						{}
						const_OrderListIterator(const OrderListIterator<T>& other):
							const_OrderListIterator::iterator_adaptor_(other.base())			
						{}

	private:
		friend class	boost::iterator_core_access;
		reference		dereference() const							{ return Parent::base_reference()->data; }
		const base_type&
						get_base()									{ return Parent::base_reference(); }

		friend class 	OrderList<T>::OrderComparison;
		friend class 	OrderList<T>::ConsistencyComparison;
};


#include "orderlist.hpp"

#endif // __ORDERLIST_H__