#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 2820 2012-08-30 00:47:58Z peter $

/*
	Copyright (C) 2010 Peter Johansson
	Copyright (C) 2012 Jari Häkkinen

	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 "SegmentTree.h"
#include "stl_utility.h"
#include "yat_assert.h"

#include <set>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

	/**
		 \brief a set of Segments

		 A container that holds a set of Segment. The Segments cannot overlap.

		 \since new in yat 0.7
	 */
	template<typename T, class Compare = std::less<T> >
	class SegmentSet 
		: public SegmentTree<std::set<Segment<T, Compare>, 
																	SegmentCompare<T, Compare> >,
												 Compare,
												 Identity<const Segment<T, Compare>&> >
	{
		typedef SegmentSet<T, Compare> me;
	public:
		/**
			 \brief creates a set with no segments
		 */
		SegmentSet(void) {}

		/**
			 insert \a segment into set. If there is no gap between \a
			 segment and neighboring segments the segments are merged.
		 */
		typename me::const_iterator 
		insert_merge(const typename me::value_type& segment)
		{
			std::pair<typename me::iterator, typename me::iterator> p = 
				this->overlap_range(segment);
			if (p.first==p.second) { // no overlap between set and segment
				return this->container_.insert(p.first, segment);
			}
			/*
				p.first           last         p.second
				--->    --->      --->         --->
				
				----------------------->
				segment
			*/
			Compare comp;
			typename me::iterator last=p.second;
			YAT_ASSERT(last==this->end() || compare(segment, *last));
			YAT_ASSERT(last!=this->begin()); // last!=p.first
			--last;
			YAT_ASSERT(compare_3way(segment, *last)==0);
			
			Segment<T, Compare> segment2(std::min(p.first->begin(),
																						segment.begin(), comp),
																	 std::max(last->end(), segment.end(), comp));
			this->container_.erase(p.first, p.second); 
			// FIXME: use a better hint than end()
			return this->container_.insert(this->end(), segment2);
		}

	private:
		// using compiler generated copying
		//SegmentSet(const SegmentSet&);
		//SegmentSet& operator=(const SegmentSet&);
	};

}}}
#endif