#ifndef theplu_yat_utility_segment_tree
#define theplu_yat_utility_segment_tree

// $Id: SegmentTree.h 2788 2012-07-25 22:51:16Z peter $

/*
	Copyright (C) 2010, 2011, 2012 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 "Segment.h"

#include "yat_assert.h"

#include <algorithm>
#include <functional>

namespace theplu {
namespace yat {
namespace utility {

	/**
		 \brief Base Class for SegmentSet and SegmentMap

		 - Container: underlying container (set or map)
		 - Compare: functor comparing elements (same as in Segment)
		 - Value2Key: functor translating a \c const_reference to \c
       key_type (or \c const&)
	 */
	template<class Container, class Compare, class Value2Key>
	class SegmentTree
	{
	public:
		/**
			 \brief key type is same as \c Container 's \c key_type.

			 Typically Segment<element_type>.
		*/
		typedef typename Container::key_type key_type;

		/**
			 \brief value type is same as \c Container 's \c value_type.

			 Typically a Segment<element_type> or pair<const
			 Segment<element_type>, Data>.
		*/
		typedef typename Container::value_type value_type;

		/**
			 \brief element type is same as \c key_type 's value_type.

			 If the key held is \c Segment<T>, \c value_type is \c T.
		*/
		typedef typename key_type::value_type element_type;

		///  \brief key compare
		typedef typename Container::key_compare key_compare;
		/// \brief value compare
		typedef typename Container::value_compare value_compare;
		/// \brief element compare
		typedef Compare element_compare;

		/// \brief pointer
		typedef typename Container::pointer pointer;
		/// \brief reference
		typedef typename Container::reference reference;
		/// \brief const reference
		typedef typename Container::const_reference const_reference;
		/// \brief size_type
		typedef typename Container::size_type size_type;
		/// \brief difference_type
		typedef typename Container::difference_type difference_type;
		/// \brief iterator
		typedef typename Container::iterator iterator;
		/// \brief const_iterator
		typedef typename Container::const_iterator const_iterator;

		/**
			 \brief creates a SegmentTree with no segments
		 */
		SegmentTree(void) {}

		/**
			 \brief Destructor
		*/
		virtual ~SegmentTree(void) {}

		/**
			 \return const iterator pointing to beginning of container
		 */
		const_iterator begin(void) const { return container_.begin(); }

		/**
			 \return iterator pointing to beginning of container
		 */
		iterator begin(void) { return container_.begin(); }

		/**
			 \brief erases all values
		 */
		void clear(void) { container_.clear(); }

		/**
			 \return 1 if there is a Segment that overlaps with \a element
		 */
		size_type count(const element_type& element) const;

		/**
			 \return \c true if size is zero
		*/
		bool empty(void) const { return container_.empty(); }

		/**
			 \return a const_iterator pointing to the end of container
		 */
		const_iterator end(void) const { return container_.end(); }

		/**
			 \return end of container
		 */
		iterator end(void) { return container_.end(); }

		/**
			 \brief erase values in range [first, last)

			 \since New in yat 0.8
		 */
		void erase(iterator first, iterator last) { container_.erase(first, last);}

		/**
			 erase value pointed to by \a pos

			 \since New in yat 0.8
		 */
		void erase(iterator pos) { container_.erase(pos); }

		/**
			 \return iterator pointing to value containing \a element

			 If no value contains \a element, end() is returned.
		 */
		iterator find(const element_type& element);

		/**
			 \return const iterator pointing to value containing \a element

			 If no value contains \a element, end() is returned.

			 \return an iterator pointing to the Segment that contains \a
			 vt. If no Segment contains \a vt, end() is returned.
		 */
		const_iterator find(const element_type& vt) const;

		/**
			 \brief insert value

			 if \a value does not overlap with container, insert
			 segment; otherwise do nothing.

			 \return a pair where pair.first points to the inserted \a value
			 or if \a value was not inserted it points to a value in
			 container that overlaps with \a value; pair.second is true if
			 \a value was inserted.
		 */
		std::pair<iterator, bool> insert(const value_type& value);

		/**
			 \return Comparison functor to compare two keys (Segment)
		 */
		key_compare key_comp(void) const
		{
			return key_compare(compare);
		}

		/**
			 \brief similar to lower_bound in std::set and std::map

			 \return iterator pointing to first value whose key overlaps
			 with \a element or is greater than \a element.
		 */
		iterator lower_bound(const element_type& element);

		/**
			 \brief similar to lower_bound in std::set and std::map

			 \return const iterator pointing to first value whose key
			 overlaps with \a element or is greater than \a element.
		 */
		const_iterator lower_bound(const element_type& element) const;

		/**
			 \return number of values in container
		 */
		size_type size(void) const { return container_.size(); }

		/**
			 \return iterator pointing to first segment that is greater than
			 \a segment.
		 */
		iterator upper_bound(const element_type& element);

		/**
			 \brief similar to upper_bound in std::set and std::map

			 \return iterator pointing to first value whose key is greater
			 than \a element.
		 */
		const_iterator upper_bound(const element_type& element) const;

		/**
			 \return the \c value_compare object used by the class to sort
			 \c values
		 */
		value_compare value_comp(void) const { return key_comp(); }

	protected:
		/// underlying container
		Container container_;

		/**
			 pair.first first (smallest) segment that overlaps with \a
			 segment and pair.second first (smallest) segment that does not
			 overlap with \a segment.
		 */
		std::pair<iterator, iterator> overlap_range(const key_type& segment)
		{
			iterator first = container_.lower_bound(segment);
			if (first!=begin()) {
				--first;
				if (compare(*first, segment))
					++first;
			}
			iterator last = first;
			while (last!=end() && !compare(segment, *last))
				++last;
			YAT_ASSERT(last==end() || compare(segment, *last));
			return std::make_pair(first, last);
		}

		// using compiler generated copying
		//SegmentTree(const SegmentTree&);
		//SegmentTree& operator=(const SegmentTree&);
	};

	template<class Container, class Compare, class Value2Key>
	typename SegmentTree<Container, Compare, Value2Key>::size_type
	SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
	{
		if (find(element)==end())
			return 0;
		return 1;
	}


	template<class Container, class Compare, class Value2Key>
	typename SegmentTree<Container, Compare, Value2Key>::const_iterator
	SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
	{
		const_iterator iter = lower_bound(vt);
		element_compare comp;
		//		if (iter==end() || comp(vt, iter->begin()))
		if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
			return end();
		return iter;
	}


	template<class Container, class Compare, class Value2Key>
	typename SegmentTree<Container, Compare, Value2Key>::iterator
	SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
	{
		iterator iter = lower_bound(vt);
		element_compare comp;
		if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
			return end();
		return iter;
	}


	template<typename T, class Compare, class Value2Key>
	std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
	SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
	{
		return container_.insert(segment);
	}


	template<typename T, class Compare, class Value2Key>
	typename SegmentTree<T, Compare, Value2Key>::iterator
	SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
	{
		key_type segment(element, element);
		iterator result = container_.lower_bound(segment);
		// result is larger or overlapping with segment (i.e.! result<segment)
		YAT_ASSERT(result==end()
							 || !compare(Value2Key()(*result),segment));
		return result;
	}


	template<typename T, class Compare, class Value2Key>
	typename SegmentTree<T, Compare, Value2Key>::const_iterator
	SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
	{
		key_type segment(element, element);
		const_iterator result = container_.lower_bound(segment);
		// result is larger or overlapping with segment (i.e.! result<segment)
		YAT_ASSERT(result==end()
							 || !compare(Value2Key()(*result),segment));
		return result;
	}


	template<typename T, class Compare, class Value2Key>
	typename SegmentTree<T, Compare, Value2Key>::iterator
	SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
	{
		key_type segment(element, element);
		iterator result = container_.upper_bound(segment);
		Compare comp;
		Value2Key value2key;
		if (result==end() || comp(element, value2key(*result).begin()))
			return result;
		++result;
		// result is larger than segment
		YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
		return result;
	}


	template<typename T, class Compare, class Value2Key>
	typename SegmentTree<T, Compare, Value2Key>::const_iterator
	SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
	{
		Segment<element_type, Compare> segment(element, element);
		const_iterator result = container_.upper_bound(segment);
		Compare comp;
		Value2Key value2key;
		if (result==end() || comp(element, value2key(*result).begin()))
			return result;
		++result;
		// result is larger than segment
		YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
		return result;
	}

}}}
#endif