#ifndef theplu_yat_utility_segment
#define theplu_yat_utility_segment

// $Id$

/*
	Copyright (C) 2010 Peter Johansson

	This file is part of the yat library, http://dev.thep.lu.se/yat

	The yat library 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.

	The yat library 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 yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "yat_assert.h"

#include <algorithm>
#include <functional>

namespace theplu {
namespace yat {
namespace utility {

	/**
		 \brief a class for a Segment or Interval

		 A Segment is defined by its \a begin and \a end. The end is not
		 included in the Segment, i.e., you could write the Segment as
		 [begin, end). Type T must be comparable, optionally with a
		 comparator Compare, which should implement <a
		 href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
		 Strict Weak Ordering.</a>.		 

		 \since new in yat 0.7
	 */
	template<typename T, class Compare = std::less<T> >
	class Segment
	{
	public:
		/**
			 type the Segment holds
		 */
		typedef T value_type;

		/**
			 \brief default constructor
		 */
		Segment(void) {}

		/**
			 \brief Constructor

			 Creates a segment [begin, end)
		 */
		Segment(const T& begin, const T& end)
			: begin_(begin), end_(end) {}

		/**
			 \return reference to first element in Segment
		 */
		T& begin(void) { return begin_; }

		/**
			 \return const reference to first element in Segment
		 */
		const T& begin(void) const { return begin_; }

		/**
			 \return reference to first element greater than Segment
		 */
		T& end(void) { return end_; }

		/**
			 \return const reference to first element greater than Segment
		 */
		const T& end(void) const { return end_; }
		
	private:
		T begin_;
		T end_;
		
		// using compiler generated copying
		//Segment(const Segment&);
		//Segment& operator=(const Segment&);
	};

	/**
		 This function takes two Segment and compare them with comparator
		 Compare. If all elements in \a lhs is less than all elements in
		 \a rhs, \c true is returned. In other words, \c false is returned
		 if \a rhs.begin() is less than \a lhs.end().

		 The exception is if both \a lhs and \a rhs are empty Segment
		 (i.e. begin equals end) and their begins and ends are equal, in
		 which case \c false is returned. This exception implies that
		 compare(x,x) always returns false.

		 \relates Segment

		 \since new in yat 0.7
	 */
	template<typename T, class Compare>
	bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
	{
		Compare c;
		// begin <= end
		YAT_ASSERT(!c(lhs.end(), lhs.begin()));
		YAT_ASSERT(!c(rhs.end(), rhs.begin()));
		// take care of case when both sides are zero segments
		if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
			return c(lhs.begin(), rhs.begin());
		}

		return ! c(rhs.begin(), lhs.end());
	}

	/**
		 \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
		 lhs) is \c true, and 0 otherwise

		 \relates Segment

		 \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)

		 \since new in yat 0.7
	 */
	template<typename T, class Compare>
	int compare_3way(const Segment<T, Compare>& lhs, 
									 const Segment<T, Compare>& rhs)
	{
		if (compare(lhs, rhs))
			return -1;
		if (compare(rhs, lhs))
			return 1;
		return 0;
	}

	/**
		 \return -1 if \a element is less than all elements in \a segment,
		 0 if \a element overlaps with \a segment, and 1 otherwise.

		 \relates Segment

		 \since new in yat 0.7
	 */
	template<typename T, class Compare>
	int compare_3way(const T& element, 
									 const Segment<T, Compare>& segment)
	{
		Compare comp;
		if (comp(element, segment.begin()))
			return -1;
		if (comp(element, segment.end()))
			return 0;
		return 1;
	}

	/**
		 \return intersection of \a a and \a b. If \a a and \a b do not
		 overlap an empty Section is returned (begin==end), but the exact
		 value of begin is undefined.

		 \relates Segment

		 \since new in yat 0.7
	 */
	template<typename T, class Compare>
	Segment<T, Compare> intersection(const Segment<T, Compare>& a, 
																	 const Segment<T, Compare>& b)
	{
		Compare comp;
		Segment<T, Compare> result;

		result.begin() = std::max(a.begin(), b.begin(), comp);
		// the first max is needed in case a and b don't overlap
		result.end() = std::max(result.begin(), 
														std::min(a.end(), b.end(), comp),
														comp);
		return result;
	}

	/**
		 \brief functor using compare
	 */
	template<typename T, class Compare>
	struct SegmentCompare : 
		public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
	{
		/**
			 \see compare(const Segment<T,Compare>&, const Segment<T,Compare>&)
		 */
		bool operator()(const Segment<T, Compare>& lhs, 
										const Segment<T, Compare>& rhs) const
		{ return compare(lhs, rhs); }
	};

}}}
#endif